[置顶] 聚类之均值聚类（k-means）算法的python实现

聚类之均值聚类（k-means）算法的python实现    最近在学习机器学习算法，主要参考了周志华老师的《机器学习》这本教材。最近读了聚类这一章节，为了加深对机器学习算法的了解，用python实现了该算法。
(1）k-means算法
k-means是一种非常常见的聚类算法，在处理聚类任务中经常使用。k-means算法是一种原型聚类算法。何为原型聚类呢？算法首先对原型进行初始化，然后对原型进行迭代更新求解，采用不同的原型表示、不同的求解方式，将产生不同的求解方式。 k-means聚类算法又叫k均值聚类算法。对于样本集。"k均值"（k-means）算法就是针对聚类划分最小化平方误差：   其中是簇Ci的均值向量。从上述公式中可以看出，该公式刻画了簇内样本围绕簇均值向量的紧密程度，E值越小簇内样本的相似度越高。
k-means聚类算法的描述如下：
输入：样本集 过程： 从样本集中随机选择k个样本作为初始向量，即k个初始质心点 repeat
对样本集中的每个数据 对于当前数据 计算当前数据与k个质心之间的距离 将当前数据加入到距离其最近的簇 对于每个簇，计算其均值，即得到新的k个质心点   util 迭代终止条件满足为止（对于本程序其迭代终止条件为连续两次迭代的均方误差小于0.0001）
输出：簇划分
（2）Python实现
Python我使用的2.7版本，附加的库有numpy、matplotlib，这两个库的安装和配置网上的教程也比较多。代码中的注释部分比较多，可以供大家参考，如果有啥问题，希望大家可以指正~最后程序的运算结果将会以视图的形式呈现出来，这样便于直观的显示。

# -*- coding: UTF-8 -*-
import numpy
import random
import codecs
import copy
import re
import matplotlib.pyplot as plt

def calcuDistance(vec1, vec2):
    # 计算向量vec1和向量vec2之间的欧氏距离
    return numpy.sqrt(numpy.sum(numpy.square(vec1 - vec2)))

def loadDataSet(inFile):
# 载入数据测试数据集
    # 数据由文本保存，为二维坐标
    inDate = codecs.open(inFile, 'r', 'utf-8').readlines()
    dataSet = list()
    for line in inDate:
    line = line.strip()
    strList = re.split('[ ]+', line)  # 去除多余的空格
    # print strList[0], strList[1]
    numList = list()
    for item in strList:
    num = float(item)
    numList.append(num)
    # print numList
    dataSet.append(numList)

    return dataSet      # dataSet = [[], [], [], ...]

def initCentroids(dataSet, k):
# 初始化k个质心，随机获取
return random.sample(dataSet, k)  # 从dataSet中随机获取k个数据项返回

def minDistance(dataSet, centroidList):
    # 对每个属于dataSet的item，计算item与centroidList中k个质心的欧式距离，找出距离最小的，
    # 并将item加入相应的簇类中

clusterDict = dict()                 # 用dict来保存簇类结果
for item in dataSet:
vec1 = numpy.array(item)         # 转换成array形式
flag = 0                         # 簇分类标记，记录与相应簇距离最近的那个簇
minDis = float("inf")            # 初始化为最大值

for i in range(len(centroidList)):
vec2 = numpy.array(centroidList[i])
distance = calcuDistance(vec1, vec2)  # 计算相应的欧式距离
if distance < minDis:    
minDis = distance
flag = i                          # 循环结束时，flag保存的是与当前item距离最近的那个簇标记

if flag not in clusterDict.keys():   # 簇标记不存在，进行初始化
clusterDict[flag] = list()
# print flag, item
clusterDict[flag].append(item)       # 加入相应的类别中

return clusterDict                       # 返回新的聚类结果

def getCentroids(clusterDict):
    # 得到k个质心
    centroidList = list()
    for key in clusterDict.keys():
        centroid = numpy.mean(numpy.array(clusterDict[key]), axis = 0)  # 计算每列的均值，即找到质心
        # print key, centroid
        centroidList.append(centroid)

    return numpy.array(centroidList).tolist()

def getVar(clusterDict, centroidList):
    # 计算簇集合间的均方误差
    # 将簇类中各个向量与质心的距离进行累加求和

    sum = 0.0
    for key in clusterDict.keys():
        vec1 = numpy.array(centroidList[key])
        distance = 0.0
        for item in clusterDict[key]:
            vec2 = numpy.array(item)
            distance += calcuDistance(vec1, vec2)
        sum += distance

    return sum

def showCluster(centroidList, clusterDict):
    # 展示聚类结果

    colorMark = ['or', 'ob', 'og', 'ok', 'oy', 'ow']      # 不同簇类的标记 'or' --> 'o'代表圆，'r'代表red，'b':blue
    centroidMark = ['dr', 'db', 'dg', 'dk', 'dy', 'dw']   # 质心标记 同上'd'代表棱形
    for key in clusterDict.keys():
        plt.plot(centroidList[key][0], centroidList[key][1], centroidMark[key], markersize = 12)  # 画质心点
        for item in clusterDict[key]:
            plt.plot(item[0], item[1], colorMark[key]) # 画簇类下的点

    plt.show()

if __name__ == '__main__':

    inFile = "D:/ML/clustering/testSet.txt"            # 数据集文件 
    dataSet = loadDataSet(inFile)                      # 载入数据集
    centroidList = initCentroids(dataSet, 4)           # 初始化质心，设置k=4
    clusterDict = minDistance(dataSet, centroidList)   # 第一次聚类迭代
    newVar = getVar(clusterDict, centroidList)         # 获得均方误差值，通过新旧均方误差来获得迭代终止条件
    oldVar = -0.0001                                   # 旧均方误差值初始化为-1
    print '***** 第1次迭代 *****'
    print 
    print '簇类'
    for key in clusterDict.keys():
        print key, ' --> ', clusterDict[key]
    print 'k个均值向量: ', centroidList
    print '平均均方误差: ', newVar
    print 
    showCluster(centroidList, clusterDict)             # 展示聚类结果

    k = 2
    while abs(newVar - oldVar) >= 0.0001:              # 当连续两次聚类结果小于0.0001时，迭代结束          
        centroidList = getCentroids(clusterDict)          # 获得新的质心
        clusterDict = minDistance(dataSet, centroidList)  # 新的聚类结果
        oldVar = newVar                                   
        newVar = getVar(clusterDict, centroidList)

        print '***** 第%d次迭代 *****' % k
        print 
        print '簇类'
        for key in clusterDict.keys():
            print key, ' --> ', clusterDict[key]
        print 'k个均值向量: ', centroidList
        print '平均均方误差: ', newVar
        print
        showCluster(centroidList, clusterDict)            # 展示聚类结果

        k += 1

（3）结果分析 数据样本集我是从网上下载的，属于二维坐标点，一共有80组数据。数据集如下（供大家参考）：

1.658985    4.285136  
-3.453687   3.424321  
4.838138    -1.151539  
-5.379713   -3.362104  
0.972564    2.924086  
-3.567919   1.531611  
0.450614    -3.302219  
-3.487105   -1.724432  
2.668759    1.594842  
-3.156485   3.191137  
3.165506    -3.999838  
-2.786837   -3.099354  
4.208187    2.984927  
-2.123337   2.943366  
0.704199    -0.479481  
-0.392370   -3.963704  
2.831667    1.574018  
-0.790153   3.343144  
2.943496    -3.357075  
-3.195883   -2.283926  
2.336445    2.875106  
-1.786345   2.554248  
2.190101    -1.906020  
-3.403367   -2.778288  
1.778124    3.880832  
-1.688346   2.230267  
2.592976    -2.054368  
-4.007257   -3.207066  
2.257734    3.387564  
-2.679011   0.785119  
0.939512    -4.023563  
-3.674424   -2.261084  
2.046259    2.735279  
-3.189470   1.780269  
4.372646    -0.822248  
-2.579316   -3.497576  
1.889034    5.190400  
-0.798747   2.185588  
2.836520    -2.658556  
-3.837877   -3.253815  
2.096701    3.886007  
-2.709034   2.923887  
3.367037    -3.184789  
-2.121479   -4.232586  
2.329546    3.179764  
-3.284816   3.273099  
3.091414    -3.815232  
-3.762093   -2.432191  
3.542056    2.778832  
-1.736822   4.241041  
2.127073    -2.983680  
-4.323818   -3.938116  
3.792121    5.135768  
-4.786473   3.358547  
2.624081    -3.260715  
-4.009299   -2.978115  
2.493525    1.963710  
-2.513661   2.642162  
1.864375    -3.176309  
-3.171184   -3.572452  
2.894220    2.489128  
-2.562539   2.884438  
3.491078    -3.947487  
-2.565729   -2.012114  
3.332948    3.983102  
-1.616805   3.573188  
2.280615    -2.559444  
-2.651229   -3.103198  
2.321395    3.154987  
-1.685703   2.939697  
3.031012    -3.620252  
-4.599622   -2.185829  
4.196223    1.126677  
-2.133863   3.093686  
4.668892    -2.562705  
-2.793241   -2.149706  
2.884105    3.043438  
-2.967647   2.848696  
4.479332    -1.764772  
-4.905566   -2.911070  

数据集分布如下：

由数据分布可以直观看出，数据可划分为4类，设置k = 4。初始的k个质心点从上述的80个数据中随机选取，由于每次选取的数据不同，聚类的结果会有偏差。              初始的k个数据是随机选取的，数据集为：[[-2.579316, -3.497576], [2.321395, 3.154987], [2.668759, 1.594842], [4.196223, 1.126677]]。下面展示其迭代过程：                     
该过程一共迭代了6次，不同颜色代表不同的簇，其中棱形代表该簇的质心。