天天看点
返回

小瓜讲机器学习——聚类算法（一）K-Means算法原理Python代码实现

K-Means聚类算法

        • 1. K-Means聚类算法
          • 1.1 聚类算法概述
          • 1.2 K-Means算法原理
            • 1.2.1 相似性度量
            • 1.2.2 K-Means算法原理
            • 1.2.3 K-Means算法过程
            • 1.2.4 K-Means存在的问题
          • 1.3 K-Means算法Python代码实现
          • 附录：Python源代码
            • 文章导引列表：
            • 机器学习
            • 数据分析
            • 数据可视化

1. K-Means聚类算法

1.1 聚类算法概述

前面我们介绍的机器学习主要聚焦在分类算法，而且很重要的一个前提条件（或者说输入）是训练样本都是已有类别标签了，这些需要在已有类别标签条件下的机器学习一般叫监督学习（Supervised Learning）。

类别标签往往需要人工标记，那么有没有自动标记呢？聚类算法能够满足你的需求。

聚类算法仅仅依赖训练样本本身的特征信息，将具有相似属性的样本划分到同一集合中（不需要标记），显然聚类算法是典型的无监督学习（Unsupervised Learning）。聚类算法可以单独使用，也可以配合其他学习算法一同使用，典型的是通过聚类算法获得训练样本的分类信息，然后使用分类算法，建立分类模型预测目标值。

1.2 K-Means算法原理

1.2.1 相似性度量

K-Means算法是基于相似性的聚类算法，那么首先需要定义的就是相似性该如何度量。

“距离”是一种很好的度量相似性的工具，这是显而易见的。

例如小王月收入5000，小赵月收入4500，李总月收入100000，小王和小赵的月收入距离（Manhattan distance）=|5000-4500|<<<小王和李总的月收入距离=|100000-5000|，可以推断小王和小赵是同阶层的，小王和李总不同阶层。

当然距离定义也有好几种，在不同问题中可以选择不同距离定义。但是距离定义都满足

常用有：

闵可夫斯基距离（）

d ( X ( 1 ) , X ( 2 ) ) = [ ∑ i = 1 n ( x i ( 1 ) − x i ( 2 ) ) p ] 1 / p d(X^{(1)},X^{(2)})=[\sum_{i=1}^n(x_i^{(1)}-x_i^{(2)})^p]^{1/p} d(X(1),X(2))=[i=1∑n​(xi(1)​−xi(2)​)p]1/p

曼哈顿距离（）

d ( X ( 1 ) , X ( 2 ) ) = ∑ i = 1 n ∣ x i ( 1 ) − x i ( 2 ) ∣ d(X^{(1)},X^{(2)})=\sum_{i=1}^n|x_i^{(1)}-x_i^{(2)}| d(X(1),X(2))=i=1∑n​∣xi(1)​−xi(2)​∣

欧几里得距离

d ( X ( 1 ) , X ( 2 ) ) = [ ∑ i = 1 n ( x i ( 1 ) − x i ( 2 ) ) 2 ] 1 / 2 d(X^{(1)},X^{(2)})=[\sum_{i=1}^n(x_i^{(1)}-x_i^{(2)})^2]^{1/2} d(X(1),X(2))=[i=1∑n​(xi(1)​−xi(2)​)2]1/2

注不难发现曼哈顿距离和欧式距离都是闵可夫斯基距离的具体形式。

1.2.2 K-Means算法原理

假设训练样本为 T = { X ( 1 ) , X ( 2 ) , . . . , X ( m ) } T=\{X^{(1)},X^{(2)},...,X^{(m)}\} T={X(1),X(2),...,X(m)}，其中 X ( i ) = ( x 1 ( i ) , x 2 ( i ) , . . . , x l ( i ) ) X^{(i)}=(x_1^{(i)},x_2^{(i)},...,x_l^{(i)}) X(i)=(x1(i)​,x2(i)​,...,xl(i)​)。假定分类类别总共是 k k k个，为 ( z 1 , z 2 , . . . , z k ) (z_1,z_2,...,z_k) (z1​,z2​,...,zk​)，每一类的中心坐标为 { Ω 1 , Ω 2 , . . . , Ω k } \{\Omega_1,\Omega_2,...,\Omega_k\} {Ω1​,Ω2​,...,Ωk​}，其中 Ω i = ( ω 1 i , ω 2 i , . . . , ω l i ) \Omega_i=(\omega_1^i,\omega_2^i,...,\omega_l^i) Ωi​=(ω1i​,ω2i​,...,ωli​)。

定义下述示性函数

γ i j = { 1 , X ( i ) ∈ z j 0 , X ( i ) ∉ z j \gamma_{ij}= \begin{cases}1,\qquad X^{(i)}\in z_j \\0,\qquad X^{(i)}\notin z_j \end{cases} γij​={1,X(i)∈zj​0,X(i)∈/​zj​​

每一个样本被分到某一类均可以用上述示性函数表达（此处为非模糊聚类）。

K-Means聚类算法的基本原理是求取一个聚类结果，使得每一个样本到对应聚类中心得距离之和取到最小，即如下。

min ⁡ ∑ i = 1 m ∑ j = 1 k γ i j ∣ ∣ X ( i ) − Ω j ∣ ∣ 2 2 = min ⁡ J \min \sum_{i=1}^m\sum_{j=1}^k\gamma_{ij}||X^{(i)}-\Omega_j||_2^2=\min J mini=1∑m​j=1∑k​γij​∣∣X(i)−Ωj​∣∣22​=minJ

当 ∂ J ∂ Ω ^ j = 0 \frac{\partial J}{\partial \hat \Omega_j}=0 ∂Ω^j​∂J​=0，即可取到极小值。

∂ J ∂ Ω ^ j = − 2 ∑ i = 1 m ( X ( i ) − Ω j ) ∙ ∂ Ω j ∂ Ω ^ j ( j : X ( i ) ∈ z j ) = 0 ⇒ ∑ i = 1 m X ( i ) γ i j ( j : X ( i ) ∈ z j ) − Ω j ∑ i = 1 m γ i j ( j : X ( i ) ∈ z j ) = 0 \frac{\partial J}{\partial \hat \Omega_j}=-2\sum_{i=1}^m(X^{(i)}-\Omega_j)\bull \frac{\partial \Omega_j}{\partial \hat \Omega_j}(j:X^{(i)}\in z_j)=0\Rightarrow \sum_{i=1}^mX^{(i)}\gamma_{ij}(j:X^{(i)}\in z_j)-\Omega_j\sum_{i=1}^m\gamma_{ij}(j:X^{(i)}\in z_j)=0 ∂Ω^j​∂J​=−2i=1∑m​(X(i)−Ωj​)∙∂Ω^j​∂Ωj​​(j:X(i)∈zj​)=0⇒i=1∑m​X(i)γij​(j:X(i)∈zj​)−Ωj​i=1∑m​γij​(j:X(i)∈zj​)=0

所以 Ω j \Omega_j Ωj​的更新公式如下

Ω j = ∑ i = 1 m X ( i ) γ i j ∑ i = 1 m γ i j ( j : X ( i ) ∈ z j ) \Omega_j=\frac{\sum_{i=1}^mX^{(i)}\gamma_{ij}}{\sum_{i=1}^m\gamma_{ij}}(j:X^{(i)}\in z_j) Ωj​=∑i=1m​γij​∑i=1m​X(i)γij​​(j:X(i)∈zj​)

1.2.3 K-Means算法过程

输入：

　　　训练样本为 T = { X ( 1 ) , X ( 2 ) , . . . , X ( m ) } T=\{X^{(1)},X^{(2)},...,X^{(m)}\} T={X(1),X(2),...,X(m)}，其中 X ( i ) = ( x 1 ( i ) , x 2 ( i ) , . . . , x l ( i ) ) X^{(i)}=(x_1^{(i)},x_2^{(i)},...,x_l^{(i)}) X(i)=(x1(i)​,x2(i)​,...,xl(i)​)，分类类别总共是 k k k个。

过程：

　　　1.随机选定 k k k个样本为类别的中心，坐标为 { X ( 1 ) , . . . , X ( k ) } \{X^{(1)},...,X^{(k)}\} {X(1),...,X(k)}

　　　2.计算样本点 X ( i ) X^{(i)} X(i)到聚类中心的距离，选择距离最小的点作为 X ( i ) X^{(i)} X(i)聚类簇

　　　3.连续执行以下操作

　　　　①.更新中心坐标 { X ‾ ( 1 ) , . . . , X ‾ ( k ) } \{\overline X^{(1)},...,\overline X^{(k)}\} {X(1),...,X(k)}

　　　　②.计算样本点 X ( i ) X^{(i)} X(i)到聚类中心的距离，选择距离最小的点作为 X ( i ) X^{(i)} X(i)聚类簇

　　　　③.检查所有样本归属类别是否有更新，如果没有则退出，否则继续

输出：

　　　最终的类别中心和样本类别属性

1.2.4 K-Means存在的问题

K-Means聚类算法简单易于实现，但存在两个问题①：需要人工设定聚类类别个数 k k k，有的时候 k k k没法正确的设定，这导致K-Means存在很大局限性，②：K-Means算法对于初始中心存在较大的敏感性，不同的初始中心很可能导致不同的聚类结果，这是我们不想得到的结果。

对于第一个问题，人们开发了其他聚类算法，对于第二个问题，人们补充定义了初始中心的条件，变成了K-Means++算法。

K-Means++算法

K-Means++算法主要特点就是在K-Means算法的初始中心的时候加了条件，在初始中心时要尽可能保证各中心距离最远。

初始中心：

  • 随机选定第一个类别中心
  • 计算所有样本到已有聚类中心的最短距离 D ( i ) D(i) D(i)，并以概率选择新的聚类中心
  • 直到所有聚类中心都选定

在第二步中，将所有的 D ( i ) D(i) D(i)相加， D = ∑ D ( i ) D=\sum D(i) D=∑D(i)，选取 ( 0 , D ] (0, D] (0,D]的随机数 r r r，显然 D &gt; r D&gt;r D>r，按序弹出 D ( i ) D(i) D(i)，直到 r &gt; D ( i ) r&gt;D(i) r>D(i)，选定该样本点为聚类中心（轮盘法）。

注采用概率形式取点主要为了尽可能减小噪声点的干扰。

1.3 K-Means算法Python代码实现

计算样本点 X ( i ) X^{(i)} X(i)到聚类中心的距离列阵，并找到距离最近的聚类中心。

def distance(dataloop, center):
    m = center.shape[0]
    dis = np.zeros((m,1))
    dataloop = np.array(dataloop)
    deltavector = center - dataloop
    
    for loop in range(m):
        dis[loop] = deltavector[loop].dot(deltavector[loop].T)
    return dis

def find(dis):
    return np.argmin(dis)

K-Means主要的部分如下

def kmeans(data, k, inicenter):
    m = int(data.shape[0])
    label = np.ones((m,1))*-1
    center = inicenter
    changed = True
    
    while changed:
        changed = False

        for loopi in range(m):
            dis = distance(data.iloc[loopi], center)
            index = find(dis)
            
            if label[loopi]!=index:
            # label changed
                label[loopi] = index
                changed = True

        if changed:
        # calculate new center if label changed
            for loopj in range(0,k):
                temp = data[label==loopj].mean()
                newcenter = np.array(temp)
                center[loopj] = newcenter
    return label

在K-Means算法对于初始中心位置具有很大的敏感性，不同的初始中心很有可能会得到不同的聚类结果，下图就是采用不同的初始聚类中心得到的结果

小瓜讲机器学习——聚类算法（一）K-Means算法原理Python代码实现
小瓜讲机器学习——聚类算法（一）K-Means算法原理Python代码实现

　　　inicenter =[[-3.,4.],[4.,4.],[-4.,-4.],[4.,-4.]]　　　　　　inicenter = [[-6.,-6.],[-1.6,-6.9],[2.7,6.9],[7.3,-5.1]]

为了改善这种情况，需要在初始中心的选取上面取一定的策略。K-Mean++方法就是如此，下面采用轮盘法实现K-Means++方法

K-means++

def inicenter(data, k):
    m,n = data.shape
    loop = np.random.randint(0,m)
    center = np.zeros((k, n))
    center[0] = data.iloc[loop]

    for loopi in range(1,k):
        dis_sum = 0
        nearlist = []
        for loopj in range(m):
            dis = distance(data.iloc[loopj], center[0:loopi])
            index = find(dis)
            nearlist.append(np.float(dis[index]))
            dis_sum += np.float(dis[index])
        dis_sum = dis_sum * np.random.random()
        for loopk in range(m):
            dis_sum -= nearlist[loopk]
            if dis_sum<0:
                center[loopi] = np.copy(data.iloc[loopk])
                break

    return center

这样的话，结果比较稳定，如下

小瓜讲机器学习——聚类算法（一）K-Means算法原理Python代码实现
附录：Python源代码 
def inicenter(data, k):
    m,n = data.shape
    loop = np.random.randint(0,m)
    center = np.zeros((k, n))
    center[0] = data.iloc[loop]

    for loopi in range(1,k):
        dis_sum = 0
        nearlist = []
        for loopj in range(m):
            dis = distance(data.iloc[loopj], center[0:loopi])
            index = find(dis)
            nearlist.append(np.float(dis[index]))
            dis_sum += np.float(dis[index])
        dis_sum = dis_sum * np.random.random()
        for loopk in range(m):
            dis_sum -= nearlist[loopk]
            if dis_sum<0:
                center[loopi] = np.copy(data.iloc[loopk])
                break

    return center


def distance(dataloop, center):
    m = center.shape[0]
    dis = np.zeros((m,1))
    dataloop = np.array(dataloop)
    deltavector = center - dataloop
    
    for loop in range(m):
        dis[loop] = deltavector[loop].dot(deltavector[loop].T)
    return dis

def find(dis):
    return np.argmin(dis)


def kmeans(data, k, inicenter):
    m = int(data.shape[0])
    label = np.ones((m,1))*-1
    center = inicenter
    changed = True
    
    while changed:
        changed = False

        for loopi in range(m):
            dis = distance(data.iloc[loopi], center)
            index = find(dis)
            
            if label[loopi]!=index:
            # label changed
                label[loopi] = index
                changed = True

        if changed:
        # calculate new center if label changed
            for loopj in range(0,k):
                temp = data[label==loopj].mean()
                newcenter = np.array(temp)
                center[loopj] = newcenter
    return label


if __name__=='__main__':
    data = []
    with open(r'H:\python dataanalysis\kmean\data.txt') as f:
        for loopi in f.readlines():
            line = loopi.strip().split('\t')
            temp = [float(line[0]), float(line[1])]
            data.append(temp)
    data = pd.DataFrame(data, columns=['x','y'])
    center = inicenter(data,4)
    label = kmeans(data, 4, center)
        colors = ['green', 'red', 'blue','yellow']
    for loopi in range(4):
    	plt.scatter(data[label==loopi].x, data[label==loopi].y, color='green' )
    plt.show()

数据集如下

-2.29693419524775	5.59018489409611
-1.65945644047067	1.24998175001933
-7.11109228594546	6.94390514108144
-1.60636900702686	7.53795273430285
-3.57348527642213	5.75114608400441
-7.31721716500413	6.30418091404833
-6.05051246793066	6.20192727687441
-4.17182936556511	3.74558913673918
-1.29745215195992	5.58834523124290
-1.24578025360506	2.19830681468093
-6.89670842825716	5.94232261613726
-1.20585052767569	1.22282992464194
-1.29983136229938	2.93846089472623
-4.60237045894011	1.32319973441808
-2.39803671777840	1.67992246865093
-7.00679562960949	6.76420479829105
-5.04767102161608	5.86380036083072
-1.58985132367653	3.21969636042602
-2.45454869308312	7.65155434186849
-1.28355301524968	1.24112256352036
4.07121051759479	6.25886941513957
3.67090919965106	2.78566580821488
6.35861751704302	4.54169936165600
6.56639930795944	5.89353705859680
2.30810823188065	7.23632276775059
4.42835077051762	7.71503997643811
4.11910340497630	4.83050870974662
5.52419107077885	1.97037109980075
5.96555381600651	2.04505803891340
6.28280677387653	2.80255777886616
2.93217553899005	6.88502079188564
5.75791873797572	2.77997525280072
5.58568602781689	6.69999378248171
2.13828214636241	2.70467478107493
1.83298377090864	7.50484536231059
4.48854836387500	3.44988636189366
7.71820770961257	2.37616675301846
3.38270008666293	2.75758700583222
5.09687425685844	5.31231273302647
2.56668357643796	4.31302194231911
-5.53838345055902	-6.86472384264730
-2.18419960472596	-2.44000821521265
-3.90315136193093	-5.82149470568637
-4.15193474196202	-4.30026805145651
-1.57964435319133	-6.84045889350153
-5.99912686825739	-3.78612641018854
-2.69959839622495	-6.15920100821899
-2.72389634005053	-3.42144631066252
-5.33687907117250	-3.17549847801995
-4.02524851492345	-2.76293885023403
-7.46901997305856	-4.84620881048252
-7.62234916933375	-7.41325035402147
-4.28441712893719	-6.39716121898227
-2.54582938928592	-1.60663846948831
-1.46192521039572	-6.93335386721544
-7.09065654068389	-2.21928115757317
-4.01823437389465	-4.23160295317960
-4.71426551259256	-1.02705698361180
-7.91668551349131	-7.45277129872771
-5.64014148920783	-4.90125211157188
1.74656939126409	-2.02878217594675
7.73328656598538	-3.64561407960454
1.03243956893847	-5.54333333375410
6.42437325298052	-4.40725322093063
6.72112254457403	-5.18734376373641
7.08086293754457	-7.46823315816411
1.59105091857637	-6.32058692512439
3.79847854369228	-7.13676745615384
2.81909281995458	-6.71264548202308
6.60047936157015	-6.32033232034568
4.01989679224481	-5.07913051640941
7.37453316100666	-7.65241898771981
2.27292919811997	-1.68098723059303
2.84662041565393	-1.38648967194848
2.01877286269302	-4.56395135272344
1.95247991096065	-4.57523153119987
7.08504545348063	-5.63596413125036
5.05793211155899	-1.69962307507637
4.84902141285432	-5.41527253215850
2.01468358756609	-7.22158071294349

文章导引列表：

机器学习

  1. 小瓜讲机器学习——分类算法（一）logistic regression(逻辑回归)算法原理详解
  2. 小瓜讲机器学习——分类算法（二）支持向量机（SVM）算法原理详解
  3. 小瓜讲机器学习——分类算法（三）朴素贝叶斯法（naive Bayes）
  4. 小瓜讲机器学习——分类算法（四）K近邻法算法原理及Python代码实现
  5. 小瓜讲机器学习——分类算法（五）决策树算法原理及Python代码实现
  6. 小瓜讲机器学习——聚类算法（一）K-Means算法原理Python代码实现
  7. 小瓜讲机器学习——聚类算法（二）Mean Shift算法原理及Python代码实现
  8. 小瓜讲机器学习——聚类算法（三）DBSCAN算法原理及Python代码实现

数据分析

  1. 小呆学数据分析——使用pandas中的merge函数进行数据集合并
  2. 小呆学数据分析——使用pandas中的concat函数进行数据集堆叠
  3. 小呆学数据分析——pandas中的层次化索引
  4. 小呆学数据分析——使用pandas的pivot进行数据重塑
  5. 小呆学数据分析——用duplicated/drop_duplicates方法进行重复项处理
  6. 小呆学数据分析——缺失值处理（一）
  7. 小呆学数据分析——异常值判定与处理（一）
  8. 小瓜讲数据分析——数据清洗

数据可视化

  1. 小瓜讲数据分析——数据可视化工程（matplotlib库使用基础篇）
  2. 小瓜讲matplotlib高级篇——坐标轴设置（坐标轴居中、坐标轴箭头、刻度设置、标识设置）
python数据分析 Python 机器学习 k-means k-means++ 聚类
上一篇: mongodb数据库的简单增删改查
下一篇: 聚类算法：Mean Shift聚类算法之Mean Shift

继续阅读