基于Python的K-means算法

最近在上数据挖掘的课，讲到聚类分析这一部分。聚类分析在本专业领域的应用还是很多的，常常在各种方向的文献中见到聚类分析的应用。我还是个菜鸟，没法分门别类把应用都说清楚，直接来看一下Python代码吧。
这个代码也是我仿照之前的一篇博客写的，写得还算清楚。算法原理我在这里就不说了，查查书就能够看明白。

# -*- coding: utf-8 -*-
#################################################  
# kmeans: k-means cluster  
# Author : Ji Fansen
# Date   :  2017.4.26
# HomePage : 
# Email  :   fansenji@mail.bnu.edu.cn
#################################################  
  
#使用import numpy as np的时候，调用函数时用numpy.function；使用from numpy import *的时候，调用函数时用function
from numpy import *  
import time  
import matplotlib.pyplot as plt  
  
  
# calculate Euclidean distance  
def euclDistance(vector1, vector2):  
    return sqrt(sum(power(vector2 - vector1, 2)))  #求这两个矩阵的距离，vector1、2均为矩阵
  
 
#在样本集中随机选取k个样本点作为初始质心
def initCentroids(dataSet, k):  
    numSamples, dim = dataSet.shape   #矩阵的行数、列数 
    centroids = zeros((k, dim))         #初始化全为0
    for i in range(k):  
        index = int(random.uniform(0, numSamples))  #随机产生一个浮点数，然后将其转化为int型，作为抽样的索引
        centroids[i, :] = dataSet[index, :]  
    return centroids  
  

# k-means cluster 
#dataSet为一个矩阵
#k为将dataSet矩阵中的样本分成k个类 
def kmeans(dataSet, k):  
    numSamples = dataSet.shape[0]  #读取矩阵dataSet的第一维度的长度,即获得有多少个样本数据
    # first column stores which cluster this sample belongs to,  
    # second column stores the error between this sample and its centroid  
    clusterAssment = mat(zeros((numSamples, 2)))  #得到一个N*2的零矩阵，用来记录每个样本属于哪一个cluster
    clusterChanged = True#clusterChanged 的真假控制循环是否继续进行  
  
    ## step 1: init centroids  
    centroids = initCentroids(dataSet, k)  #在样本集中随机选取k个样本点作为初始质心
  
    while clusterChanged:  
        clusterChanged = False  
        ## for each sample  
        for i in range(numSamples):  #range
            minDist  = 100000.0  
            minIndex = 0  
            ## for each centroid  
            ## step 2: find the centroid who is closest  
            #计算每个样本点与质点之间的距离，将其归到距离最小的那一簇
            for j in range(k):  
                distance = euclDistance(centroids[j, :], dataSet[i, :])  
                if distance < minDist:  
                    minDist  = distance  
                    minIndex = j+1 #之前博客上的代码minIndex直接等于了j，我认为这样做是存在bug的。我们来仔细想一下，minIndex的作用是记录每一个样本数据是属于哪一个cluster的，并且是通过把j（也就是cluster的索引）记录下来实现的。我们无法保证每一个样本都不属于第一个cluster（也就是对应于j=0）。这样的话就存在一个问题，假如说在while这个大循环进行第一次的时候，遍历到最后一个样本时恰好这个样本属于第一个cluster，minIndex就是0，不要忘了clusterAssment初始化的时候可都是0啊，这样的话clusterChanged就没有更新成True。结果是，while循环执行了一次就终止了。。。。忧桑，仿佛一切都没有发生过。。。所以我加1了之后能够避免这个问题。
              
            ## step 3: update its cluster 
            #k个簇里面与第i个样本距离最小的的标号和距离保存在clusterAssment中
            #若所有的样本不再变化，则退出while循环
            if clusterAssment[i, 0] != minIndex:  
                clusterChanged = True  
            clusterAssment[i, :] = minIndex, minDist**2  #两个**表示的是minDist的平方
  
        ## step 4: update centroids  
        for j in range(k):  
            #clusterAssment[:,0].A==j+1是找出矩阵clusterAssment中第一列元素中等于j的行的下标，返回的是一个以array的列表，第一个array为等于j的下标
            pointsInCluster = dataSet[nonzero(clusterAssment[:, 0].A == j+1)[0]] #将dataSet矩阵中相对应的样本提取出来 
            centroids[j, :] = mean(pointsInCluster, axis = 0)  #计算标注为j的所有样本的平均值
  
    print ('Congratulations, cluster complete!')  
    return centroids, clusterAssment  
  
#后面的这一部分主要是针对只有一个特征值的情况
# show your cluster only available with 2-D data 
#centroids为k个类别，其中保存着每个类别的质心
#clusterAssment为样本的标记，第一列为此样本的类别号，第二列为到此类别质心的距离 
def showCluster(dataSet, k, centroids, clusterAssment):  
    numSamples, dim = dataSet.shape  
    if dim != 2:  
        print ("Sorry! I can not draw because the dimension of your data is not 2!")  
        return 1  
  
    mark = ['or', 'ob', 'og', 'ok', '^r', '+r', 'sr', 'dr', '<r', 'pr']# 不同簇类的标记 'or' --> 'o'代表圆，'r'代表red，'b':blue  
    if k > len(mark):  
        print ("Sorry! Your k is too large! please contact wojiushimogui")  
        return 1 
     
  
    # draw all samples  
    for i in range(numSamples):  
        markIndex = int(clusterAssment[i, 0])  #为样本指定颜色
        plt.plot(dataSet[i, 0], dataSet[i, 1], mark[markIndex])  
  
    mark = ['Dr', 'Db', 'Dg', 'Dk', '^b', '+b', 'sb', 'db', '<b', 'pb'] # 质心标记 同上'd'代表棱形 
    # draw the centroids  
    for i in range(k):  
        plt.plot(centroids[i, 0], centroids[i, 1], mark[i], markersize = 12)  
  
    plt.show() 
#后面的这一部分就是测试数据的部分了
from numpy import *  
import time  
import matplotlib.pyplot as plt 
import KMeans
   
## step 1: load data  
print ("step 1: load data..." ) 
dataSet = []   #列表，用来表示，列表中的每个元素也是一个二维的列表；这个二维列表就是一个样本，样本中包含有我们的属性值和类别号。
#与我们所熟悉的矩阵类似，最终我们将获得N*2的矩阵，每行元素构成了我们的训练样本的属性值和类别号
fileIn = open("C:/Users/lenovo/Desktop/kmeans-master/kmeans-master/testSet.txt")  #是正斜杠
for line in fileIn.readlines(): 
    temp=[]
    lineArr = line.strip().split('\t')  #line.strip()把末尾的'\n'去掉
    temp.append(float(lineArr[0]))
    temp.append(float(lineArr[1]))
    dataSet.append(temp)
    #dataSet.append([float(lineArr[0]), float(lineArr[1])])  
fileIn.close()  
## step 2: clustering...  
print ("step 2: clustering..."  )
dataSet = mat(dataSet)  #mat()函数是Numpy中的库函数，将数组转化为矩阵
k = 4  
centroids, clusterAssment = KMeans.kmeans(dataSet, k)  #调用KMeans文件中定义的kmeans方法。
  
## step 3: show the result  
print ("step 3: show the result..."  )
KMeans.showCluster(dataSet, k, centroids, clusterAssment)