1. K-Means聚类算法¶
K-Means算法的伪代码如下所示:
创建k个点作为起始质心(经常是随机选择)
当任意一个点的簇分配结果发生改变时
对数据集中的每个数据点
对每个质心
计算质心与数据点之间的距离
将数据点分配到距其最近的簇
对每一个簇，计算簇中所有点的均值并将其均值作为质心In [1]:
import kMeans
In [2]:
from numpy import *
In [3]:
dataMat = mat(kMeans.loadDataSet('testSet.txt'))
In [4]:
min(dataMat[:,0])
Out[4]:
In [5]:
min(dataMat[:,1])
Out[5]:
In [6]:
max(dataMat[:,1])
Out[6]:
In [7]:
max(dataMat[:,0])
Out[7]:
In [8]:
kMeans.randCent(dataMat, 2)
Out[8]:
In [9]:
kMeans.distEclud(dataMat[0], dataMat[1])
Out[9]:
In [10]:
reload(kMeans) #注意在写kMeans的时候，重新计算centroid的循环与计算每个点最近质心的循环平级，而不是嵌套(即注意缩进)
Out[10]:
In [11]:
dataMat = mat(kMeans.loadDataSet('testSet.txt'))
In [12]:
myCentroids, clustAssing = kMeans.kMeans(dataMat, 4)
In [13]:
print shape(dataMat)
In [14]:
print shape(dataMat[:,0].flatten())
In [15]:
dataMat[:,0].flatten().A[0]
Out[15]:
In [16]:
myCentroids
Out[16]:
In [17]:
myCentroids[:,0].flatten().A[0]
Out[17]:
In [18]:
myCentroids[:,1].flatten().A[0]
Out[18]:
2. 使用后处理提高聚类性能¶
K-Means算法会收敛，但聚类效果也可能会较差。原因是K-Means算法收敛到了局部最小值，而非全局最小值。
一种用于度量聚类效果的指标是SSE(Sum of Squared Error, 误差平方和)，对应代码kMeans.py中kMeans函数的clusterAssment矩阵的第二列之和。
SSE值越小表示数据点越接近它们的质心，聚类效果也越好。因为对误差取了平方，所以更重视那些远离中心的点。
一种肯定能降低SSE的方法是增加簇的个数，但这会违背聚类的目标。聚类的目标是在保持簇数目不变的情况下提高簇的质量。
对于K-Means算法陷入局部最小值的情况，有以下的改进方法。可以对生成的簇进行后处理，将具有最大SSE值的簇划分成两个簇。(具体实现时可以将最大簇包含的点过滤出来，然后再上面继续运行K-Means，k值取2)
为保持簇总数不变，我们可以合并两个簇。有两种可以量化的方法：合并最近的质心，或者合并两个使得SSE增幅最小的质心。第一种方法通过计算所有质心之间的距离，然后合并距离最近的两个点来实现。第二种方法需要合并两个簇然后计算总的SSE值，但这种方法需要尝试所有可能的两个簇，不断重复该处理过程，直到找到合并最佳的两个簇为止。
3. 二分K-Means算法¶
该算法的提出是为了改进K-Means算法。
该算法首先将所有点作为一个簇，然后将该簇一分为二。之后选择其中一个簇继续进行划分，选择哪一个簇进行划分取决于对其划分是否可以最大程度降低SSE的值。上述基于SSE的划分过程不断重复，直到得到用户指定的簇数目为止。另一种做法是选择SSE最大的簇进行划分，直到簇数目达到用户指定的数目为止。
二分K-Means算法的伪代码如下：
将所有点看成一个簇
当簇数目小于k时
对于每一个簇
计算总误差
在给定的簇上面进行K-Means聚类(k=2)
计算该簇一分为二之后的总误差
选择使得误差最小的那个簇进行划分操作In [19]:
reload(kMeans)
Out[19]:
In [20]:
dataMat3 = mat(kMeans.loadDataSet('testSet2.txt'))
In [21]:
centList, myNewAssments = kMeans.biKmeans(dataMat3, 3)
In [22]:
centList
Out[22]:
In [23]:
centList[0][:,0]
Out[23]: