通常,人们根据样本间的某种距离或者相似性来定义聚类,即把相似的(或距离近的)样本聚为同一类,而把不相似的(或距离远的)样本归在其他类。
所谓聚类问题,就是给定一个元素集合D,其中每个元素具有n个可观察属性,使用某种算法将D划分成k个子集,要求每个子集内部的元素之间相异度尽可能低,而不同子集的元素相异度尽可能高。其中每个子集叫做一个簇。
k-means算法是一种很常见的聚类算法,它的基本思想是:通过迭代寻找k个聚类的一种划分方案,使得用这k个聚类的均值来代表相应各类样本时所得的总体误差最小。
看起来还不错
分析一个公司的客户分类,这样可以对不同的客户使用不同的商业策略,或是电子商务中分析商品相似度,归类商品,从而可以使用一些不同的销售策略,等等。
函数
loadDataSet(fileName)
从文件中读取数据集
distEclud(vecA, vecB)
计算距离,这里用的是欧氏距离,当然其他合理的距离都是可以的
randCent(dataSet, k)
随机生成初始的质心,这里是虽具选取数据范围内的点
kMeans(dataSet, k, distMeas=distEclud, createCent=randCent)
kmeans算法,输入数据和k值。后面两个事可选的距离计算方式和初始质心的选择方式
show(dataSet, k, centroids, clusterAssment)
可视化结果
1 #coding=utf-8 2 from numpy import * 3 4 def loadDataSet(fileName): 5 dataMat = [] 6 fr = open(fileName) 7 for line in fr.readlines(): 8 curLine = line.strip().split('\t') 9 fltLine = map(float, curLine)10 dataMat.append(fltLine)11 return dataMat12 13 #计算两个向量的距离,用的是欧几里得距离14 def distEclud(vecA, vecB):15 return sqrt(sum(power(vecA - vecB, 2)))16 17 #随机生成初始的质心(ng的课说的初始方式是随机选K个点)18 def randCent(dataSet, k):19 n = shape(dataSet)[1]20 centroids = mat(zeros((k,n)))21 for j in range(n):22 minJ = min(dataSet[:,j])23 rangeJ = float(max(array(dataSet)[:,j]) - minJ)24 centroids[:,j] = minJ + rangeJ * random.rand(k,1)25 return centroids26 27 def kMeans(dataSet, k, distMeas=distEclud, createCent=randCent):28 m = shape(dataSet)[0]29 clusterAssment = mat(zeros((m,2)))#create mat to assign data points
30 #to a centroid, also holds SE of each point31 centroids = createCent(dataSet, k)32 clusterChanged = True33 while clusterChanged:34 clusterChanged = False35 for i in range(m):#for each data point assign it to the closest centroid36 minDist = inf37 minIndex = -138 for j in range(k):39 distJI = distMeas(centroids[j,:],dataSet[i,:])40 if distJI <minDist:41 minDist = distJIminIndex = j42 if clusterAssment[i,0] != minIndex:
43 clusterChanged = True44 clusterAssment[i,:] = minIndex,minDist**245 print centroids46 for cent in range(k):#recalculate centroids47 ptsInClust = dataSet[nonzero(clusterAssment[:,0].A==cent)[0]]#get all the point in this cluster48 centroids[cent,:] = mean(ptsInClust, axis=0) #assign centroid to mean
49 return centroids, clusterAssment50 51 def show(dataSet, k, centroids, clusterAssment):52 from matplotlib import pyplot as plt
53 numSamples, dim = dataSet.shape
54 mark = ['or', 'ob', 'og', 'ok', '^r', '+r', 'sr', 'dr', '<r', 'pr']
55 for i in xrange(numSamples):
56 markIndex = int(clusterAssment[i, 0])
57 plt.plot(dataSet[i, 0], dataSet[i, 1], mark[markIndex])
58 mark = ['Dr', 'Db', 'Dg', 'Dk', '^b', '+b', 'sb', 'db', '<b', 'pb']
59 for i in range(k):
60 plt.plot(centroids[i, 0], centroids[i, 1], mark[i], markersize = 12)
61 plt.show()62 63 def main():64 dataMat = mat(loadDataSet('testSet.txt'))65 myCentroids, clustAssing= kMeans(dataMat,4)66 print myCentroids67 show(dataMat, 4, myCentroids, clustAssing)
68 69 70 if __name__ == '__main__':71 main()
这里是聚类结果,还是很不错的啦
但是有时候也会收敛到局部最小值,就像下面这样,就是不幸收敛到局部最优了