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)  # 算出这些数据的中心点

    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