机器学习-聚类算法-k-均值聚类-python详解
- 2019 年 11 月 27 日
- 筆記
本文中，算法实现代码笔者自行做了详细的注释，别的内容系引用原文：http://blog.csdn.net/zouxy09/article/details/17589329
算法优缺点：
优点：容易实现 缺点：可能收敛到局部最小值，在大规模数据集上收敛较慢 使用数据类型：数值型数据
算法思想
k-means算法实际上就是通过计算不同样本间的距离来判断他们的相近关系的，相近的就会放到同一个类别中去。
1.首先我们需要选择一个k值，也就是我们希望把数据分成多少类，这里k值的选择对结果的影响很大，Ng的课说的选择方法有两种一种是elbow method，简单的说就是根据聚类的结果和k的函数关系判断k为多少的时候效果最好。另一种则是根据具体的需求确定，比如说进行衬衫尺寸的聚类你可能就会考虑分成三类（L,M,S）等
2.然后我们需要选择最初的聚类点（或者叫质心），这里的选择一般是随机选择的，代码中的是在数据范围内随机选择，另一种是随机选择数据中的点。这些点的选择会很大程度上影响到最终的结果，也就是说运气不好的话就到局部最小值去了。这里有两种处理方法，一种是多次取均值，另一种则是后面的改进算法（bisecting K-means）
3.终于我们开始进入正题了，接下来我们会把数据集中所有的点都计算下与这些质心的距离，把它们分到离它们质心最近的那一类中去。完成后我们则需要将每个簇算出平均值，用这个点作为新的质心。反复重复这两步，直到收敛我们就得到了最终的结果
开发包的导入
本次实践导入的包有numpy（更强的数值表达和计算能力），matplotlib（主要是用里面的pyplot，画图展示用的），因为针对不同的应用，会用到不同的包，所以强烈建议需要用到python的朋友下一个setuptools工具，安装完成之后，在cmd（windows）下输入easy_install ，
基本K均值算法
############################################################################
1：选择K个点作为初始质心（实现部分用的是随机选取质心）
2：repeat
3： 将每个点指派到最近的质心，形成K个簇
4： 重新计算每个簇的质心
5：until 质心不发生改变
######################################################################
数据集合下载
代码部分（解析全在注释里）
from numpy import * import time import matplotlib.pyplot as plt # 计算欧式距离 def euclDistance(vector1, vector2): return sqrt(sum(power(vector2 - vector1, 2))) # 0ρ = sqrt( (x1-x2)^2+(y1-y2)^2 ) |x| = √( x2 + y2 ) # power 对列表计算2次方 求和后开方 # 初始化质心随机样本 def initCentroids(dataSet, k): numSamples, dim = dataSet.shape #获取数据集合的行列总数 centroids = zeros((k, dim)) for i in range(k): index = int(random.uniform(0, numSamples)) # uniform() 方法将随机生成下一个实数，它在[x,y]范围内。 centroids[i, :] = dataSet[index, :] return centroids # k-means cluster def kmeans(dataSet, k): numSamples = dataSet.shape[0]#行数 clusterAssment = mat(zeros((numSamples, 2))) # clusterChanged = True #停止循环标志位 ## step 1: init 初始化k个质点 centroids = initCentroids(dataSet, k) while clusterChanged: clusterChanged = False ## for each 行 for i in xrange(numSamples): minDist = 100000.0 # 设定一个极大值 minIndex = 0 ## for each centroid ## step 2: 寻找最接近的质心 for j in range(k): distance = euclDistance(centroids[j, :], dataSet[i, :]) # 将centroids（k个初始化质心）的j行和dataset（数据全集）的i行 算欧式距离，返回数值型距离 if distance < minDist: # 找距离最近的质点，记录下来。 minDist = distance minIndex = j ## step 3: update its cluster # 跟新这个簇 if clusterAssment[i, 0] != minIndex: clusterChanged = True # clusterAssment 是一个n行2列的矩阵 Assment 评估 clusterAssment[i, :] = minIndex, minDist**2 #赋值为 新的质点标号 ## step 4: update centroids for j in range(k): # 属于j这个质点的所有数值的平均值算出成为新的质点 pointsInCluster = dataSet[nonzero(clusterAssment[:, 0].A == j)[0]] centroids[j, :] = mean(pointsInCluster, axis = 0) print 'Congratulations, cluster complete!' return centroids, clusterAssment # show your cluster only available with 2-D data def showCluster(dataSet, k, centroids, clusterAssment): numSamples, dim = dataSet.shape if dim != 2: print "Sorry! I can not draw because the dimension of your data is not 2!" return 1 mark = ['or', 'ob', 'og', 'ok', '^r', '+r', 'sr', 'dr', '<r', 'pr'] if k > len(mark): print "Sorry! Your k is too large! please contact Zouxy" return 1 # 画出所有样例点 属于同一分类的绘制同样的颜色 for i in xrange(numSamples): markIndex = int(clusterAssment[i, 0]) plt.plot(dataSet[i, 0], dataSet[i, 1], mark[markIndex]) mark = ['Dr', 'Db', 'Dg', 'Dk', '^b', '+b', 'sb', 'db', '<b', 'pb'] #设定颜色 # draw the centroids # 画出质点，用特殊图型 for i in range(k): plt.plot(centroids[i, 0], centroids[i, 1], mark[i], markersize = 12) plt.show() if __name__ == '__main__': ## step 1: 加载数据 print "step 1: load data..." dataSet = [] fileIn = open('./data.txt') for line in fileIn.readlines(): lineArr = line.strip().split(' ') # Python strip() 方法用于移除字符串头尾指定的字符（默认为空格） # 再按照数据之间的空格作为分隔符。 dataSet.append([float(lineArr[0]), float(lineArr[1])]) # 返回加入到dataset中的每组数据为一个列表。形成二维数组 ## step 2: 开始聚类... print "step 2: clustering..." dataSet = mat(dataSet) # mat 函数，将数组转化为矩阵 k = 3 centroids, clusterAssment = kmeans(dataSet, k) ## step 3: show the result print "step 3: show the result..." showCluster(dataSet, k, centroids, clusterAssment)
聚类结果：
分别是2,3,4个k值情况下的
四、算法分析
分析部分来源于 http://blog.csdn.net/zouxy09/article/details/17589329
k-means算法比较简单，但也有几个比较大的缺点：
（1）k值的选择是用户指定的，不同的k得到的结果会有挺大的不同，如下图所示，左边是k=3的结果，这个就太稀疏了，蓝色的那个簇其实是可以再划分成两个簇的。而右图是k=5的结果，可以看到红色菱形和蓝色菱形这两个簇应该是可以合并成一个簇的：
（2）对k个初始质心的选择比较敏感，容易陷入局部最小值。例如，我们上面的算法运行的时候，有可能会得到不同的结果，如下面这两种情况。K-means也是收敛了，只是收敛到了局部最小值：
（3）存在局限性，如下面这种非球状的数据分布就搞不定了：
（4）数据库比较大的时候，收敛会比较慢。
k-means老早就出现在江湖了。所以以上的这些不足也被世人的目光敏锐的捕捉到，并融入世人的智慧进行了某种程度上的改良。例如问题（1）对k的选择可以先用一些算法分析数据的分布，如重心和密度等，然后选择合适的k。而对问题（2），有人提出了另一个成为二分k均值（bisecting k-means）算法，它对初始的k个质心的选择就不太敏感，这个算法我们下一个博文再分析和实现。
原创文章，转载请注明： 转载自URl-team
本文链接地址: 机器学习-聚类算法-k-均值聚类-python详解
No related posts.
