使用Numpy实现K-Means算法

1. 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. 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

发表评论

电子邮件地址不会被公开。 必填项已用*标注