最近打算把所有的数据挖掘领域的算法研究一遍并用python实现写成文章。本篇是对KMeans算法的上半段代码的实现的大概总结。下篇会尽快更新，共勉！

聚类算法用于根据数据的特征发现数据项的相似性，并将相似的数据项放在同一个组中，相似性采用距离进行描述。

K-means聚类

简单的说，一般流程如下：先随机选取k个点，将每个点分配给它们，得到最初的k个分类；在每个分类中计算均值，将点重新分配，划归到最近的中心点；重复上述步骤直到点的划归不再改变。

K-Means算法的SAS实现

K-means算法可以用SAS的proc fastclus实现。主要涉及两个问题。首先是初始点的选择。如果指定replace=random，则系统随机选取maxcluster选项指定个数的完整观测作为凝聚点。如果分析员对研究情景比较了解，可以利用专业知识指定初始分类，那么可以在proc fastclus中设定seed=dataset选项，SAS会从dataset中读取前k个观测作为初始凝聚点。此外，SAS还提供了系统自动选择初始凝聚点的方法，该方法需要指定maxclusters和radius选项，其中radius为凝聚点之间允许的最小距离。默认值是maxclusters=100，radius=0，效果是选取数据集中的前100个观测作为凝聚点。fastclus过程总是选择第一个完整观测作为第一个凝聚点，然后依次考察剩余观测，与第一个凝聚点的距离大于radius指定值的观测作为第二个凝聚点。当凝聚点的个数未达到maxcluster，且所考察观测与已有凝聚点间距离均大于radius指定值时，则所考察的观测成为下一个凝聚点。如果一个观测完整且与所有凝聚点距离均大于radius，但凝聚点个数已经达到最大值，此时fastclus过程进行两种替换检验，检验能否用当前观测替换已有凝聚点。第一个检验是替换距离最近两凝聚点检验，如果凝聚点与当前观测的最小距离大于已有凝聚点的最小距离，则一个已有凝聚点将被替换，当前观测将替换距离最近的两个凝聚点中的一个，使得替换后当前观测与最近距离两凝聚点中未被替换的那个距离最远。第二个检验是替换当前观测最近凝聚点检验，如果当前观测到除最近凝聚点外的所有凝聚点的最小距离大于当前观测最近凝聚点到所有其他凝聚点的最小距离，进行替换。如果两种检验都说明该观测不能替换已有凝聚点，则转向下一个观测，直到考察完数据集中的所有观测。当然，这种检测可以用replace=none|part|full来控制，none表示不进行替换检验，part表示只进行第一种替换检验；full为默认值，两种替换检验都进行。 另一个问题是分类的修改方法。默认的方法是按批修改法，即选定一批凝聚点后；将所有观测按与其距离最近的凝聚点归类；计算每一类重心，将重心作为新的凝聚点，若新凝聚点与旧凝聚点完全重合，则终止算法，否则重新归类。批量修改法是全部观测调整完毕后，才改变类的凝聚点，而逐个修改法是每个观测一旦调整后立即改变类凝聚点，而立即改变需要算法即时验证改变后的凝聚点集合是否仍然满足radius的约束。如果不满足radius的约束，SAS会将小于radius的两类合并，计算重心，作为合并后类的凝聚点，如此往复，直到凝聚点满足radius条件。要让SAS执行逐个修改法，需要声明drift选项。

补充 K-means聚类算法的问题是，均值的计算受异常点的干扰比较严重。为了克服这个问题，可以采用K中值法。

K-medoid聚类

PAM（Partition Around Medoids）是K-medoid的基础算法，基本流程如下：首先随机选择k个对象作为中心，把每个对象分配给离它最近的中心。然后随机地选择一个非中心对象替换中心对象，计算分配后的距离改进量。聚类的过程就是不断迭代，进行中心对象和非中心对象的反复替换过程，直到目标函数不再有改进为止。

PAM算法的问题在于伸缩性不好，需要测试所有的替换，只适用于小数据量的聚类。为了提高该算法的可伸缩性，有人提出了CLARAN算法，本质如下：从总体数据中生成多个样本数据，在每个样本数据上应用PAM算法得到一组K中值点；取出所有样本中结果最好的那一组作为最后的解。

CLARAN算法存在的问题是，算法的聚类质量依赖于样本的质量。 为了提高PAM和CLARAN算法的聚类质量，有人在CLARAN算法的基础上提出了CLARANS算法。与CLARAN相比，最大的区别在于没有一个时刻算法局限于固定的一个样本中，自始自终，算法的样本数据都是随机抽样的。其算法过程如下。将每套k个中值点作为一个节点，若两个节点之间有k-1个点相同，则成为邻居。用户事先指定两个数，一是最大的邻居数，二是最大的局部最优点数。算法随机选取一个当前点，随机地取出其中的一个邻居，看目标值是否有改进，如果有改进，则用邻居替代当前点，重新开始搜索邻居的过程；若抽取了最大邻居数的邻居，发现当前点最优，那么就找到了一个局部最优点。找到一个局部最优点后，再随机抽取一个当前点，进行上面的过程，直到找到了用户指定最大数量的局部最优点。比较每个局部最优点的目标值，取最优的那个点作为结果，即可得到k个中值点，于是k个类就可以轻松得到。CLARANS算法的效果不错，但算法复杂度更高。

python3 kMeans 算法实现：

# coding=utf-8

import numpy

from numpy import *

from numpy.random.mtrand import power

from numpy import mat

#加载数据

def loadDataMat(fileName):

dataMat = []

fr = open(fileName)

for line in fr.readlines():

#print line

curLine = line.strip().split(',')

#print curLine

fltLine =list(map(float,curLine)) #map all elements to float() ，map函数在python2与python3中输出结果不同，python2中map函数输出的是一个list，python3中map函数输出的是一个迭代，所以这里要转换成list.

#print(fltLine)

dataMat.append(fltLine)

#print(dataMat)

return dataMat

# 计算欧式距离

def distEclud(vecA, vecB):

return sqrt(sum(numpy.power(abs(vecA-vecB),2))) #power函数在numpy与matplotlib中都存在，但这里的power函数是numpy模块里的，所以引用时要说明，不然会报错。

# 寻找K个随机质心

def randCent(dataMat, k):

n =shape(dataMat)[1]

centroids =mat(zeros((k,n))) #这里的zeros函数是numpy里的，所以必须要import numpy

for j in range(n):

# 每列中的最小值

minJ = numpy.min(dataMat[:,j]) #这里的min与max函数也是numpy里的，当时运行时报错，加了numpy.就没问题了

# 每列中的最大值减去最小值

rangeJ = float(numpy.max(dataMat[:,j]) - minJ)

# 得到k个质心

centroids[:,j] =mat(minJ +rangeJ * random.rand(k,1))

return centroids

def kMeans(dataMat, k, distMeas=distEclud,createCent=randCent):

m =shape(dataMat)[0]

#注意数据格式的转化，这里的clusterAssment是matrix格式的

clusterAssment = mat(zeros((m,2)))

#print(clusterAssment)

centroids = createCent(dataMat, k)

#print(centroids)

clusterChanged =True

while clusterChanged:

clusterChanged = False

#数据是二维的，有m行，对每一行即每个样本进行迭代计算

for i in range(m):

minDist =inf;minIndex =-1

for j in range(k):

# 计算任意点和数k个质心的距离

distJI =distMeas(centroids[j,:],dataMat[i,:])

#选出最小的距离

if distJI < minDist:

minDist =distJI ;minIndex=j

#更新数据，直到最小值的索引不变

if clusterAssment[i,0] != minIndex :clusterChanged=True

#clusterAssment存储的是每行即每个样本对应的质心的最小索引和值

clusterAssment[i,:] = minIndex,minDist**2

#print (centroids)

#print(clusterAssment)

#更新质心，取对应相同质心的所有行索引的平均值，作为新的质心axis=0表示沿着二维数组的列来取的平均值。

for cent in range(k):

#clusterAssment[i,0].A操作是将numpy的mat格式矩阵转换为数组

ptsInClust = dataMat[nonzero(clusterAssment[:,0].A==cent)[0]]

centroids[cent,:] =mean(ptsInClust,axis=0)

return centroids,clusterAssment

if __name__=='__main__':#主函数调用

import matplotlib

matplotlib.use('Agg')#后面的savefig保存照片时要用到这个

from matplotlib import pyplot as plt

from matplotlib.pyplot import savefig

#要划分的聚类数目

k=3

#加载数据

dataMat = mat(loadDataMat('C:/Users/HZF/Desktop/python数据挖掘十大算法实现/11.csv'))

#print (dataMat)

numSamples = dataMat.shape[0]

#print(numSamples)

#计算聚类中心

centroids,clusterAssment =kMeans(dataMat,k)

print (centroids,clusterAssment)

#画出所有的聚类数据，根据所处聚类中心的不同用不同的表示方法

mark = ['or', 'ob', 'og', 'ok', '^r', '+r', 'sr', 'dr', '

for i in range(numSamples):

markIndex = int(clusterAssment[i, 0])

plt.plot(dataMat[i, 0], dataMat[i, 1], mark[markIndex])

#画出聚类中心

mark = ['Dr', 'Db', 'Dg', 'Dk', '^b', '+b', 'sb', 'db', '

# 画聚类中心，一共有四类

for i in range(k):

plt.plot(centroids[i, 0], centroids[i, 1], mark[i], markersize = 12)

plt.savefig('glp.png', dpi = 75)#savefig可以保存照片到当前位置

plt.show()

#plt.savefig('glp.png', dpi = 75)

#if __name__=='__main__':

#k=4

#dataMat = mat(loadDataMat('testSet.txt'))

#myCentroids,clusterAssment =kMeans(dataMat,k)

#plt.show()

#savefig('glp.jpg', dpi = 75)

（未完待续）