(上接第二章)

  4.3.1 KMeans 算法流程

  算法的过程如下:

  (1)从N个数据文档随机选取K个文档作为质心

  (2)对剩余的每个文档测量其到每个质心的距离,并把它归到最近的质心的类

  (3)重新计算已经得到的各个类的质心

  (4)迭代(2)~(3)步直至新的质心与原质心相等或者小于指定阀值,算法结束。

  4.3.2 辅助函数

  (1)文件数据转为矩阵:file2matrix

def file2matrix(path,delimiter):
    recordlist = []
    fp         = open(path,"rb")#读取文件内容
    content    = fp.read()
    fp.close()
    rowlist    = content.splitlines()#按行转化为一维表
    #逐行遍历,结果按分割符分割为行向量
    recordlist = [map(eval,row.split(delimiter)) for row in rowlist if row.strip()]#eval:字符串转为、矩阵形式
return mat(recordlist)#返回转换后的矩阵形式

  (2)根据聚类中心绘制散点图,以及绘制聚类中心:默认4个聚类中心

def color_cluster(dataindx,dataSet,plt,k = 4):
    index    = 0
    datalen  = len(dataindx)
    for indx in xrange(datalen):
        if int(dataindx[indx]) == 0:
            plt.scatter(dataSet[indx,0],dataSet[indx,1],c='blue',marker='o')
        elif int(dataindx[indx]) == 1:
            plt.scatter(dataSet[indx,0],dataSet[indx,1],c='green',marker='o')
        elif int(dataindx[indx]) == 2:
            plt.scatter(dataSet[indx,0],dataSet[indx,1],c='red',marker='o')
        elif int(dataindx[indx]) == 3:
            plt.scatter(dataSet[indx,0],dataSet[indx,1],c='cyan',marker='o')
        index += 1
#绘制散点图
def drawScatter(plt,mydata,size = 20,color = 'blue',mrkr = 'o'):
    plt.scatter(mydata.T[0],mydata.T[1],s = size,c = color,marker = mrkr)

  (3)欧式距离公式

#欧式距离
def distEclud(vecA,vecB):
    return linalg.norm(vecA-vecB)

  (4)随机生成聚类的中心

 

def randCenters(dataSet,k):
    n = shape(dataSet)[1]                  #初始化聚类中心矩阵:k*n
    clustercents = mat(zeros(k,n))
    for col in xrange(n):
        mincol = min(dataSet[:,col])
        maxcol = max(dataSet[:,col])
        #random.rand(k,1):产生一个0~1之间的随机数向量:k,1表示k行1列的随机数
        clustercents[:,col] = mat(mincol+float(maxcol-mincol)*random.rand(k,1))
    return clustercents

   4.3.3 聚类主函数

  第一阶段:导入所需要的库,导入数据集,指定聚类中心k:

  

dataMat = file2matrix("./iris.txt"," ") #从文件构建的数据集
dataSet = mat(dataMat[:,1:])              #转换为矩阵的形式
m = dataSet.shape[0]
k = 4 #外部指定的聚类中心 #与数据等长,共两列。 #:列1:数据集对应的聚类中心k: #列2:数据集行向量到聚类中心的距离 ClusDist = mat(zeros((m,2))) clutercents = randCenters(dataSet,k) #随机生成聚类中心  flag = True #初始化迭代所需的标志位 counter = []

  第二阶段:算法停止迭代,即dataSet的所有向量都能找到某个聚类中心,到此中心的距离均小于其他k-1个中心的距离。

  

while flag:                               #主循环
    flag = False                          #默认设置退出标志(False)

   第三阶段:内循环1遍历dataSet数据集,计算dataSet每行与聚类的最小欧氏距离,并以此更新聚类中心。

  算法停止条件:ClustDist[i,0] == minIndex

for i in xrange(m):
    #遍历k个聚类中心,获取最短距离
    distlist = [distEclud(clustercents[j,:],dataSet[i,:]) for j in range(k)]
    minDist  = min(distlist)
    minIndex = distlist.index(minDist)
    
    if ClusDist[i,0] != minIndex: #找到一个新聚类中心
        flag = True               #重置标志位True,继续迭代
        
    #更新聚类中心
    ClusDist[i,:] = minIndex,minDist

  第四阶段:内循环2遍历每个聚类中心,计算DataSet已聚类的子列均值,并以此更新聚类中心。

  

for cent in xrange(k):
    #从ClustDist的第一列筛选出等于cent的行下标
    pstInClust = dataSet[nonzero(ClusDist[:,0].A == cent)[0]]
    #计算pstInClust各列的均值:mean(ptsInClust,axis = 0):axis=0 #按列计算
    clustercents[cent,:] = mean(ptsInClust,axis = 0)

  4.3.4  评估分类结果:
  第五阶段:分类结果可视化。

  

#返回计算完成的聚类中心
print "clustercents:\n",clustercents

#根据ClustDist分类和描绘数据点
color_cluster(ClusDist[:,0:1],dataSet,plt)
#绘制聚类中心
drawScatter(plt,clustercents,size=60,color='red',mrkr='D')
plt.show()