[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$ 个类簇(包括类簇中心和类簇中的对象)
算法过程:
- 将 $ n$ 个对象的数据进行标准化。
- 随机选取 $ K$ 个对象作为初始的聚类中心。
- 计算每个对象到 $ K$ 个聚类中心的距离,将对象加入距离最近的类簇中。
- 根据类簇内的对象更新类簇的中心。
- 计算代价函数值 $ E $。
- 迭代第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