k-means算法Python实现

#!/usr/bin/python # coding=utf-8 from numpy import * # 加载数据 def loadDataSet(fileName):  # 解析文件，按tab分割字段，得到一个浮点数字类型的矩阵     dataMat = []              # 文件的最后一个字段是类别标签     fr = open(fileName)     for line in fr.readlines():         curLine = line.strip().split('\t')         fltLine = map(float, curLine)    # 将每个元素转成float类型         dataMat.append(fltLine)     return dataMat # 计算欧几里得距离 def distEclud(vecA, vecB):     return sqrt(sum(power(vecA - vecB, 2))) # 求两个向量之间的距离 ，power(a,b)即计算a的b次方，sqrt计算平方根 # 构建聚簇中心，取k个(此例中为4)随机质心 def randCent(dataSet, k):     n = shape(dataSet)[1]  #计算数据集的列数，特征数     centroids = mat(zeros((k,n)))   # 每个质心有n个坐标值，总共要k个质心，形成k行n列的零矩阵     for j in range(n):         minJ = min(dataSet[:,j])#取每列最小值即取第k列的最小值         maxJ = max(dataSet[:,j])#取每列的最大值         rangeJ = float(maxJ - minJ)#最大值减去最小值         centroids[:,j] = minJ + rangeJ * random.rand(k, 1)#改变第j列 #random.rand(k,1)构建k行一列,每行代表二维的质心坐标     return centroids  #centroids为k行n列的质心矩阵 # k-means 聚类算法

def kMeans(dataSet, k, distMeans =distEclud, createCent = randCent):

                #randCent(dataSet, k)随机生成初始的质心，这里是随机选取数据集内的k个点                   #distEclud(vecA, vecB)计算距离，这里用的是欧氏距离，当然其他合理的距离都是可以的

        m = shape(dataSet)[0]   #计算数据集的行数         clusterAssment = mat(zeros((m,2)))    #评价簇矩阵m行两列，第一列存所属的簇序号，第二列存该点到该簇质点的距离的平方 分配样本到最近的簇：存[簇序号,距离的平方] 用于存放该样本属于哪类及质心距离 ,mat()即将二维数组转化为m行2列矩阵           # 建立簇分配结果矩阵，第一列存索引，第二列存误差 # clusterAssment第一列存放该数据所属的中心点，第二列是该数据到中心点的距离         centroids = createCent(dataSet, k)#从数据集中随机选取k个点构建k行N列质心矩阵        clusterChanged = True   # 用来判断聚类是否已经收敛        while clusterChanged:            clusterChanged = False;            for i in range(m):  # 把每一个数据点划分到离它最近的中心点                  minDist = inf; minIndex = -1;  # inf表示无穷大量，-inf表示负无穷大量                  for j in range(k):                          distJI = distMeans(centroids[j,:], dataSet[i,:])#计算每个样本与k个中心点的距离                          if distJI < minDist:                                 minDist = distJI; minIndex = j  #簇序号即按序递增的j #设置两个变量，分别存放数据点到质心的距离， 及数据点属于哪个质心如果第i个数据点到第j个中心点更近，则将i归属为j即获取最小距离,及对应的簇序号

               if clusterAssment[i,0] != minIndex:

                    clusterChanged = True;  # 如果分配发生变化，则需要继续迭代

               clusterAssment[i,:] = minIndex,minDist**2   # 并将第i个数据点的分配情况存入字典 分配样本到最近的簇          print centroids         for cent in range(k):   # 重新计算中心点               ptsInClust = dataSet[nonzero(clusterAssment[:,0].A == cent)[0]]   # 取第一列等于cent的所有列，获取该簇所有的样本点               centroids[cent,:] = mean(ptsInClust, axis = 0)  # 算出这些数据的中心点 #更新聚类中心：axis=0沿列方向求均值     return centroids, clusterAssment # --------------------测试---------------------------------------------------- # 用测试数据及测试kmeans算法 datMat = mat(loadDataSet('testSet.txt')) myCentroids,clustAssing = kMeans(datMat,4) print myCentroids

print clustAssing

对给定的数据集进行聚类

本案例采用二维数据集，共80个样本，有4个类。

如下图所示：

具体算法步骤可参考http://www.cnblogs.com/zhzhang/p/5437778.html