使用Numpy实现K-Means算法

[latexpage]

1. $ \quicklatex{size=25}K-Means $算法简介

1967年，MacQueen 首次提出了 $ K$ 均值聚类算法( $ K-Means $算法 )。迄今为止，很多聚类任务都选择该经典算法。$ K-Means $算法的优点是快速高效，其算法复杂度为 $ O(tKmn)$，其中 $ t$ 表示算法迭代的次数，$ K$ 表示聚类的数目，$ m$ 表示每个对象拥有的属性个数，$ n$ 表示待聚类的对象的个数。

该算法的核心思想是找出 $ k$ 个聚类中心，使得每一个数据点 $X_i$ 和与其最近的聚类中心 $ C_l$ 的平方距离和被最小化( 该平方距离和被称为代价函数值 $ E $ )。

$$ D(X_i,C_l) = \sum\limits_{j = 1}^{ m } {Euclid^2(X_{ij},C_{lj})} $$
$$ E = \sum\limits_{l = 1}^k {\sum\limits_{i = 1}^{{n}} {D({X_i},{C_l})} } $$

$ K-Means$算法的 $ mean$ 为类簇的中心，是一个类簇中所有对象在所有属性上的平均。在聚类的初始阶段，我们一般随机指定待聚类对象中的 $ K$ 个对象作为 $ mean$。

但是该方法也存在着一些缺陷：(1)$ K-Means$ 算法往往只能收敛到一个局部最优值。(2)聚类结果对聚类数目 $ K $ 和聚类开始时选取的 $ K$ 个初始对象非常敏感。

2. $ \quicklatex{size=25}K-Means$算法描述

输入：$ n$ 个带聚类对象，聚类中心个数 $ K$
输出：$ K$ 个类簇（包括类簇中心和类簇中的对象）
算法过程:

1. 将 $ n$ 个对象的数据进行标准化。
2. 随机选取 $ K$ 个对象作为初始的聚类中心。
3. 计算每个对象到 $ K$ 个聚类中心的距离，将对象加入距离最近的类簇中。
4. 根据类簇内的对象更新类簇的中心。
5. 计算代价函数值 $ E $。
6. 迭代第3步到第5步直至 $ E$收敛。

3. Python代码

下文的代码实现使用了Python的Numpy库，关于Numpy的安装和使用请参照这里。

import numpy as np

def loadDataFromTxt(fileName):
    dataMat=[]
    fr=open(fileName)
    for line in fr.readlines():
        curLine=line.strip().split('\t')
        fltLine=map(float,curLine)
        dataMat.append(fltLine)
    dataMat=np.mat(dataMat)
    return dataMat

def autoNormal(dataSet):
    dataShape=np.shape(dataSet)
    n=dataShape[0]
    m=dataShape[1]
    for j in range(m):
        colMax=np.max(dataSet[:,j])
        colMin=np.min(dataSet[:,j])
        colRange=colMax-colMin
        dataSet[:,j]=(dataSet[:,j]-colMin)/colRange
    return dataSet

def randomInitCentroids(dataSet,k):
    m=np.shape(dataSet)[1]
    centroids=np.mat(np.zeros((k,m)))
    for j in range(m):
        colMin=np.min(dataSet[:,j])
        colMax=np.max(dataSet[:,j])
        rangeJ=float(colMax-colMin)
        centroids[:,j]=colMin+np.random.rand(k,1)*rangeJ
    return centroids

def euclidDistance(vectA,vectB):
    return np.sqrt(np.sum(np.power(vectA-vectB,2)))

def KMean(dataSet,k,normalMethod=autoNormal,intialMethod=randomInitCentroids,distMethod=euclidDistance):
    n=dataSet.shape[0]
    dataSet=normalMethod(dataSet)
    centroids=intialMethod(dataSet,k)
    clusterAssignment=np.mat(np.zeros((n,2)))
    clusterChanged=True
    while clusterChanged:
        clusterChanged=False
        for i in range(n):
            minIndex=-1;minDist=np.inf
            for j in range(k):
                distance=distMethod(dataSet[i,:],centroids[j,:])
                if distance<minDist:
                    minIndex=j
                    minDist=distance
            if clusterAssignment[i,0] != minIndex :
                clusterChanged=True
                clusterAssignment[i,:]=minIndex,minDist        
        for cent in range(k):
            ptsInCluster=dataSet[np.where(clusterAssignment[:,0].A==cent)[0]]
            centroids[cent,:]=np.mean(ptsInCluster,axis=0)
    return centroids,clusterAssignment

dataSet=loadDataFromTxt('data.txt')
centroids,clusterAssignment=KMean(dataSet,2)
print clusterAssignment
print centroids