《机器学习实战》kMeans算法(K均值聚类算法)
机器学习中有两类的大问题,一个是分类,一个是聚类。分类是根据一些给定的已知类别标号的样本,训练某种学习机器,使它能够对未知类别的样本进行分类。这属于supervised learning(监督学习)。而聚类指事先并不知道任何样本的类别标号,希望通过某种算法来把一组未知类别的样本划分成若干类别,这在机器学习中被称作 unsupervised learning (无监督学习)。在本文中,我们关注其中一个比较简单的聚类算法:k-means算法。
k-means算法是一种很常见的聚类算法,它的基本思想是:通过迭代寻找k个聚类的一种划分方案,使得用这k个聚类的均值来代表相应各类样本时所得的总体误差最小。
其Python实现的代码如下:
- #encoding:utf-8
- from numpy import *
- def loadDataSet(filename):
- dataMat = [] #创建元祖
- fr = open(filename)
- for line in fr.readlines():
- curLine = line.strip().split("\t")
- fltLine = map(float,curLine) #使用map函数将curLine里的数全部转换为float型
- dataMat.append(fltLine)
- return dataMat
- def distEclud(vecA,vecB): #计算两个向量的欧式距离
- return sqrt(sum(power(vecA-vecB,2)))
- def randCent(dataSet,k): #位给定数据集构建一个包含k个随机质心的集合
- n = shape(dataSet)[1] #shape函数此时返回的是dataSet元祖的列数
- centroids = mat(zeros((k,n))) #mat函数创建k行n列的矩阵,centroids存放簇中心
- for j in range(n):
- minJ = min(dataSet[:,j]) #第j列的最小值
- rangeJ = float(max(dataSet[:,j]) - minJ)
- centroids[:,j] = minJ + rangeJ * random.rand(k,1) #random.rand(k,1)产生shape(k,1)的矩阵
- return centroids
- def kMeans(dataSet,k,disMeas = distEclud,createCent = randCent):
- m = shape(dataSet)[0] #shape函数此时返回的是dataSet元祖的行数
- clusterAssment = mat(zeros((m,2))) #创建一个m行2列的矩阵,第一列存放索引值,第二列存放误差,误差用来评价聚类效果
- centroids = createCent(dataSet,k) #创建k个质心,调用createCent()函数
- clusterChanged =True #标志变量,若为true则继续迭代
- print "质心位置更新过程变化:"
- while clusterChanged:
- clusterChanged = False
- for i in range(m):
- minDist = inf #inf为正无穷大
- minIndex = -1 #创建索引
- for j in range(k):
- #寻找最近的质心
- disJI = disMeas(centroids[j,:],dataSet[i,:]) #计算每个点到质心的欧氏距离
- if disJI(array([0, 0, 1]), array([0, 2, 0]))
- #print array(nonzero(b2))
- #=>[[0, 0, 1],[0, 2, 0]]
- centroids[cent,:] = mean(ptsInClust,axis=0) #计算所有点的均值,选项axis=0表示沿矩阵的列方向进行均值计算
- return centroids,clusterAssment #返回所有的类质心与点分配结果
- datMat = mat(loadDataSet('data.txt'))
- myCentroids,clustAssing = kMeans(datMat,2)
- print "最终质心:\n",myCentroids
- print "索引值和均值:\n",clustAssing
k-means算法比较简单,但也有几个比较大的缺点:
1)k值的选择是用户指定的,不同的k得到的结果会有挺大的不同,如下图所示,左边是k=3的结果,这个就太稀疏了,蓝色的那个簇其实是可以再划分成两个簇的。而右图是k=5的结果,可以看到红色菱形和蓝色菱形这两个簇应该是可以合并成一个簇的:
2)对k个初始质心的选择比较敏感,容易陷入局部最小值。例如,我们上面的算法运行的时候,有可能会得到不同的结果,如下面这两种情况。K-means也是收敛了,只是收敛到了局部最小值:
3)存在局限性,如下面这种非球状的数据分布就搞不定了
4)数据库比较大的时候,收敛会比较慢.
K均值聚类中簇的值k是用户预先定义的一个参数,那么用户如何才能知道k的选择是否正确?如何才能知道生成的簇比较好?在计算的过程中保留了每个点的误差,即该点到簇质心的距离平方值,下面将讨论利用该误差来评价聚类质量好坏的方法,引入度量聚类效果的指标SSE(sum of squared Error,误差平方和),SSE值越小,越接近于他们的质心,聚类效果也越好,有一种可以肯定减小SSE值得方法是增加k的数目,但这个违背了聚类的目标,聚类的目标是在保持簇数目不变的情况下提高簇的质量。
接下来要讨论的是利用簇划分技术得到更好的聚类效果——二分K-均值算法