K-均值聚类算法(K-means algorithm) & 二分K-均值算法(Bisecting k-means algorithm)
本文主要介绍最常见的一种聚类算法：K-means算法，及其改进算法二分K-均值算法。文中示例代码取源于《Machine Learning in Action》。
机器学习的算法主要分为监督学习和无监督学习监督学习。
监督学习(supervised learning)，利用样本输入和期望输出来学习如何预测的技术叫做监督学习法。一个房地产经理看过一处房子后，可以估算出这处房产的价格，这是因为他根据自己以往的经验得来的。如何让计算机去预估一处房产的价格呢？我们可以给它一些已知价格的房产数据，这些数据包括面积、楼层、是否向阳等一组属性以及对应的价格，计算机可以从这些已知样本训练得到一个公式，这就叫做监督学习。监督学习包括：神经网络、决策树、支持向量机、贝叶斯过滤等。
无监督学习(unsupervised learning)，主要用来处理未被标记的样本集。还是上一个例子，已知一组房产的数据，这些数据包括面积、楼层、是否向阳等一组属性，但是没有对应的价格。这时候，我们仍然可以利用这些数据得到一些信息，利用房产间的相似程度把它们分类，分过类之后可以更合理地定价，也可以根据分类调整营销策略。
K-means算法是一种聚类算法，属于无监督学习算法。
K-means算法，顾名思义，将数据分为K个聚类。 K-means算法将n个数据对象划分为k个聚类，并使所获得的聚类满足：同一聚类中的对象相似度较高；而不同聚类中的对象相似度较小。
K-means算法首先会随机确定k个中心位置(位于空间中代表聚类中心的点)，然后将各个数据项分配给最邻近的中心点。待分配完成后，重新计算聚类中心，聚类中心移动到分配给该聚类的所有节点的平均位置处，然后重复以上分配过程，直到分配过程不再产生变化为止。
下面摘取《Machine Learning in Action》书中第10章的代码例子，本文代码使用Python3.3.2。
from numpy import *
# general function to parse tab-delimited floats
def loadDataSet(fileName):
# assume last column is target value
dataMat = []
fr = open(fileName)
for line in fr.readlines():
curLine = line.strip().split('\t')
# map all elements to float()
fltLine = map(float, curLine)
dataMat.append(list(fltLine))
return dataMat
def distEclud(vecA, vecB):
return sqrt(sum(power(vecA-vecB, 2)))
def randCent(dataSet, k):
n = shape(dataSet)[1]
# create centroid mat
centroids = mat(zeros((k, n)))
# create random cluster centers, within bounds of each dimension
for j in range(n):
minJ = min(dataSet[:,j])
rangeJ = float(max(dataSet[:,j]) - minJ)
centroids[:,j] = mat(minJ + rangeJ * random.rand(k,1))
return centroids
def kMeans(dataSet, k, distMeas=distEclud, createCent=randCent):
m = shape(dataSet)[0]
# create mat to assign data points to a
# centroid, also hods SE of each point
clusterAssment = mat(zeros((m, 2)))
centroids = createCent(dataSet, k)
clusterChanged = True
while clusterChanged:
clusterChanged = False
# for each data point assign it to the
# closest centroid
for i in range(m):
minDist = minIndex = -1
for j in range(k):
distJI = distMeas(centroids[j,:], dataSet[i,:])
if distJI & minDist:
minDist = distJI; minIndex = j
if clusterAssment[i,0] != minIndex:
clusterChanged = True
clusterAssment[i:] = minIndex,minDist**2
print(centroids)
# recalculate centroids
for cent in range(k):
# get all the point in this cluster
ptsInClust = dataSet[nonzero(clusterAssment[:,0].A==cent)[0]]
# assign centroid to mean
centroids[cent,:] = mean(ptsInClust, axis=0)
return centroids, clusterAssment
运行算法：
import kMeans
datMat = mat(kMeans.loadDataSet('testSet.txt'))
myCentroids, clustAssing = kMeans.kMeans(datMat, 4)
K-means算法并不总是能得到正确的聚类，如下图
运行K-means算法实现了聚类，但是却不能保证一个理想的聚类结果，为什么？因为K-means算法总是根据局部最小化原则进行聚类，而没有考虑全局的最小化。每次进行节点分配时都是参考该节点到中心点距离的最小值，没有考虑全局的距离最小值。下面介绍一种改进了的K-means算法，即Bisecting k-means算法，可以解决这一问题。
在这里我们选择一种全局最小值的度量方法，SSE(sum of squared error)。SSE越小，所有的节点距离它们的中心点越近。
算法原理：开始时只有一个聚类，然后将其分割为两个聚类，分割之后根据SSE最小化原则从所有聚类中选择一个聚类继续进行分割，直到聚类个数达到K。
伪代码如下
Start with all the points in one cluster
While the number of clusters is less than k
for every cluster
measure total error
perform k-means clustering with k=2 on the given cluster
measure total error after k-means has split the cluster in two
choose the cluster split that gives the lowest error and commit this split
算法具体实现如下，将biKmeans函数添加到kMeans.py文件中
def biKmeans(dataSet, k, distMeas=distEclud):
m = shape(dataSet)[0]
clusterAssment = mat(zeros((m, 2)))
centroid0 = mean(dataSet, axis=0).tolist()[0]
centList = [centroid0]
for j in range(m):
clusterAssment[j,1] = distMeas(mat(centroid0), dataSet[j,:])**2
while len(centList) & k:
lowestSSE = inf
for i in range(len(centList)):
ptsInCurrCluster = \
dataSet[nonzero(clusterAssment[:,0].A==i)[0],:]
centroidMat,splitClustAss = \
kMeans(ptsInCurrCluster, 2, distMeas)
sseSplit = sum(splitClustAss[:,1])
sseNotSplit = \
sum(clusterAssment[nonzero(clusterAssment[:,0].A!=i)[0],1])
print(&sseSplit, and notSplit: &, sseSplit, sseNotSplit)
if (sseSplit+sseNotSplit) & lowestSSE:
bestCentToSplit = i
bestNewCents = centroidMat
bestClustAss = splitClustAss.copy()
lowestSSE = sseSplit + sseNotSplit
bestClustAss[nonzero(bestClustAss[:,0].A==1)[0],0] = len(centList)
bestClustAss[nonzero(bestClustAss[:,0].A==0)[0],0] = bestCentToSplit
print('the bestCentToSplit is ', bestCentToSplit)
print('the len of bestClustAss is: ', len(bestClustAss))
centList[bestCentToSplit] = bestNewCents[0,:]
centList.append(bestNewCents[1,:])
clusterAssment[nonzero(clusterAssment[:,0].A == \
bestCentToSplit)[0],:] = bestClustAss
return centList, clusterAssment
算法测试：
import kMeans
datMat2 = mat(kMeans.loadDataSet('testSet2.txt'))
centList, myNewAssments = kMeans.biKmeans(datMat2, 3)
看过本文的人也看了：
我要留言技术领域：
取消收藏确定要取消收藏吗？
删除图谱提示你保存在该图谱下的知识内容也会被删除，建议你先将内容移到其他图谱中。你确定要删除知识图谱及其内容吗？
删除节点提示无法删除该知识节点，因该节点下仍保存有相关知识内容！
删除节点提示你确定要删除该知识节点吗？刘艳丽,刘希玉,孟岩,
山东师范大学管理与经济学院,
本文提出了一种改进的K-均值聚类算法，在基本K-均值算法的基础上运用基于密度选择初始中心点并且通过学习特征权值改进聚类效果，克服了基本K-均值算法初始中心点难以确定、聚类结果不稳定的缺点；然后建立了一种基于改进的K-均值算法的人事管理系统聚类分析模型，本模型采用SQL Server2000数据库实现并成功运用于国内一家知名软件企业的人力资源管理系统中，为该企业选聘人才和用好人才提供了有益的参考。k-均值聚类算法中k的确定方法及算法优化，80分问题，截至28日中午！
[问题点数：80分，结帖人springlie]
本版专家分：0
结帖率 100%
CSDN今日推荐
本版专家分：0
本版专家分：0
本版专家分：0
匿名用户不能发表回复！
其他相关推荐聚类是一种无监督的学习，它将相似的对象归到同一个簇中。它有点像全自动分类。聚类方法几乎可以应用于所有对象，簇内的对象越相似，聚类的效果越好
簇识别给出聚类结果的含义。假定有一些数据，现在将相似数据归到一起，簇识别会告诉我们这些簇到底都是些什么。聚类与分类的最大不同在于，分类的目标事先巳知，而聚类则不一样。因为其产生的结果与分类相同，而只是类别没有预先定义，聚类有时也被称为无监督分类（unsupervised classification )。
聚类分析试图将相似对象归人同一簇，将不相似对象归到不同簇。相似这一概念取决于所选择的相似度计算方法
10.1K-均值聚类算法
K-均值聚类
优点：容易实现。
缺点：可能收敛到局部最小值，在大规模数据集上收敛较慢。
适用数据类型：数值型数据。
K-均值是发现给定数据集的k个簇的算法。簇个数k是用户给定的，每一个簇通过其质心( centroid) , 即簇中所有点的中心来描述。
K-均值算法的工作流程是这样的。首先，随机确定k个初始点作为质心。然后将数据集中的每个点分配到一个簇中，具体来讲，为每个点找距其最近的质心，并将其分配给该质心所对应的簇。这一步完成之后，每个簇的质心更新为该簇所有点的平均值。
上述过程的伪代码表示如下：
创建k个点作为起始质心（经常是随机选择）
当任意一个点的簇分配结果发生改变时
对数据集中的每个数据点
对每个质心
计算质心与数据点之间的距离
将数据点分配到距其最近的簇
对每一个簇，计算簇中所有点的均值并将均值作为质心
K-均值聚类的一般流程
(1)收集数据：使用任意方法。
⑵准备数据：需要数值型数据来计算距离，也可以将标称型数据映射为二值型数据再用于距离计算。
(3)分析数据：使用任意方法。
(4)训练算法：不适用于无监督学习，即无监督学习没有训练过程。
(5)测试算法：应用聚类算法、观察结果。可以使用量化的误差指标如误差平方和（后面会介绍）来评价算法的结果。
(6)使用算法：可以用于所希望的任何应用。通常情况下，簇质心可以代表整个簇的数据来做出决策。
K-均值聚类支持函数(即完成K均值聚类的一些辅助函数),代码如下:
from numpy import *
#general function to parse tab -delimited floats
#assume last column is target value
def loadDataSet(fileName):
dataMat = []
fr = open(fileName)
for line in fr.readlines():
curLine = line.strip().split('\t')
#笔者使用的是python3，需要将map映射后的结果转化为list
#map all elements to float()
fltLine = list(map(float,curLine))
dataMat.append(fltLine)
return dataMat
#样本距离计算函数
def distEclud(vecA, vecB):
return sqrt(sum(power(vecA - vecB, 2))) #la.norm(vecA-vecB)
#创建簇中心矩阵,初始化为k个在数据集的边界内随机分布的簇中心
def randCent(dataSet, k):
n = shape(dataSet)[1]
#create centroid mat
centroids = mat(zeros((k,n)))
#create random cluster centers, within bounds of each dimension
for j in range(n):
#求出数据集中第j列的最小值(即第j个特征)
minJ = min(dataSet[:,j])
#用第j个特征最大值减去最小值得出特征值范围
rangeJ = float(max(dataSet[:,j]) - minJ)
#创建簇矩阵的第J列,random.rand(k,1)表示产生(10,1)维的矩阵，其中每行值都为0-1中的随机值
#可以这样理解,每个centroid矩阵每列的值都在数据集对应特征的范围内,那么k个簇中心自然也都在数据集范围内
centroids[:,j] = mat(minJ + rangeJ * random.rand(k,1))
return centroids
测试截图如下:
K -均值聚类算法,代码如下:
#distMeas为距离计算函数
#createCent为初始化随机簇心函数
def kMeans(dataSet, k, distMeas=distEclud, createCent=randCent):
m = shape(dataSet)[0]
#create mat to assign data points to a centroid, also holds SE of each point
#创建一个(m,2)维矩阵，第一列存储每个样本对应的簇心，第二列存储样本到簇心的距离
clusterAssment = mat(zeros((m,2)))
#用createCent()函数初始化簇心矩阵
centroids = createCent(dataSet, k)
#保存迭代中clusterAssment是否更新的状态,如果未更新，那么退出迭代，表示收敛
#如果更新，那么继续迭代，直到收敛
clusterChanged = True
while clusterChanged:
clusterChanged = False
#for each data point assign it to the closest centroid
#对每个样本找出离样本最近的簇心
for i in range(m):
#minDist保存最小距离
#minIndex保存最小距离对应的簇心
minDist = minIndex = -1
#遍历簇心，找出离i样本最近的簇心
for j in range(k):
distJI = distMeas(centroids[j,:],dataSet[i,:])
if distJI & minDist:
minDist = distJI; minIndex = j
#如果clusterAssment更新，表示对应样本的簇心发生变化，那么继续迭代
if clusterAssment[i,0] != minIndex: clusterChanged = True
#更新clusterAssment,样本到簇心的距离
clusterAssment[i,:] = minIndex,minDist**2
print(centroids)
#遍历簇心,更新簇心为对应簇中所有样本的均值
for cent in range(k):#recalculate centroids
#利用数组过滤找出簇心对应的簇(数组过滤真是好东西！)
ptsInClust = dataSet[nonzero(clusterAssment[:,0].A==cent)[0]]#get all the point in this cluster
#对簇求均值,赋给对应的centroids簇心
centroids[cent,:] = mean(ptsInClust, axis=0) #assign centroid to mean
return centroids, clusterAssment
代码测试截图如下:
绘制测试截图:
paint函数为笔者写的绘图函数:
def paint(xArr,yArr,xArr1,yArr1):
fig = plt.figure()
ax = fig.add_subplot(111)
ax.scatter(xArr,yArr,c='blue')
ax.scatter(xArr1,yArr1,c='red')
plt.show()
效果如下(其中红色的点为簇心):
可以看到，经过3次迭代之后K-均值算法收敛
10.2 使用后处理来提高聚类性能
考虑图10-2中的聚类结果，这是在一个包含三个簇的数据集上运行K-均值算法之后的结果，但是点的簇分配结果值没有那么准确。K-均值算法收敛但聚类效果较差的原因是，K-均值算法收敛到了局部最小值，而非全局最小值（局部最小值指结果还可以但并非最好结果，全局最小值是可能的最好结果)。
一种用于度量聚类效果的指标是SSE(Sum of Squared Error,误差平方和），对应clusterAssment矩阵的第一列之和。SSE值越小表示数据点越接近于它们的质心，聚类效果也越好。因为对误差取了平方，因此更加重视那些远离中心的点。一种肯定可以降低SSE值的方法是增加簇的个数，但这违背了聚类的目标。聚类的目标是在保持簇数目不变的情况下提高簇的质量。
那么如何对结果进行改进？你可以对生成的簇进行后处理，一种方法是将具有最大SSE值的簇划分成两个簇。具体实现时可以将最大簇包含的点过滤出来并在这些点上运行K-均值聚类算法，其中的K为2。
为了保持簇总数不变，可以将某两个簇进行合并。从图10-2中很明显就可以看出，应该将图下部两个出错的簇质心进行合并。可以很容易对二维数据上的聚类进行可视化，但是如果遇到40维的数据应该如何去做？
有两种可以量化的办法：合并最近的质心，或者合并两个使得SSE增幅最小的质心。第一种思路通过计算所有质心之间的距离，然后合并距离最近的两个点来实现。第二种方法需要合并两个簇然后计算总SSE值。必须在所有可能的两个簇上重复上述处理过程，直到找到合并最佳的两个簇为止。接下来将讨论利用上述簇划分技术得到更好的聚类结果的方法。
10.3 二分K-均值算法
为克服K-均值算法收敛于局部最小值的问题，有人提出了另一个称为二分K均值（bisectingK-means)的算法,
该算法首先将所有点作为一个簇，然后将该簇一分为二。之后选择其中一个簇继续进行划分，选择哪一个簇进行划分取决于对其划分是否可以最大程度降低SSE的值。上述基于SSE的划分过程不断重复，直到得到用户指定的簇数目为止。
二分K-均值算法的伪代码形式如下：
将所有点看成一个簇
当簇数目小于k时
对于每一个簇
计算总误差
在给定的簇上面进行K-均值聚类（k=2)
计算将该簇一分为二之后的总误差
选择使得误差最小的那个簇进行划分操作
另一种做法是选择SSE最大的簇进行划分，直到簇数目达到用户指定的数目为止。这个做法听起来并不难实现。下面就来看一下该算法的实际效果。
二分K均值聚类算法,代码如下:
#distMeas为距离计算函数
def biKmeans(dataSet, k, distMeas=distEclud):
m = shape(dataSet)[0]
#(m,2)维矩阵,第一列保存样本所属簇,第二列保存样本到簇中心的距离
clusterAssment = mat(zeros((m,2)))
#取数据集特征均值作为初始簇中心
centroid0 = mean(dataSet, axis=<span style="color: #).tolist()[0]
#centList保存簇中心数组,初始化为一个簇中心
#create a list with one centroid
centList =[centroid0]
#calc initial Error
for j in range(m):
clusterAssment[j,1] = distMeas(mat(centroid0), dataSet[j,:])**2
#迭代，直到簇中心集合长度达到k
while (len(centList) & k):
#初始化最小误差
lowestSSE = inf
#迭代簇中心集合，找出找出分簇后总误差最小的那个簇进行分解
for i in range(len(centList)):
#get the data points currently in cluster i
#获取属于i簇的数据集样本
ptsInCurrCluster = dataSet[nonzero(clusterAssment[:,0].A==i)[0],:]
#对该簇进行k均值聚类
centroidMat, splitClustAss = kMeans(ptsInCurrCluster, 2, distMeas)
#获取该簇分类后的误差和
sseSplit = sum(splitClustAss[:,1])#compare the SSE to the currrent minimum
#获取不属于该簇的样本集合的误差和，注意矩阵过滤中用的是!=i
sseNotSplit = sum(clusterAssment[nonzero(clusterAssment[:,0].A!=i)[0],1])
#打印该簇分类后的误差和和不属于该簇的样本集合的误差和
print("sseSplit, and notSplit: ",sseSplit,sseNotSplit)
#两误差和相加即为分簇后整个样本集合的误差和,找出簇中心集合中能让分簇后误差和最小的簇中心，保存最佳簇中心(bestCentToSplit),最佳分簇中心集合(bestNewCents),以及分簇数据集中样本对应簇中心及距离集合(bestClustAss),最小误差(lowestSSE)
if (sseSplit + sseNotSplit) & lowestSSE:
bestCentToSplit = i
bestNewCents = centroidMat
bestClustAss = splitClustAss.copy()
lowestSSE = sseSplit + sseNotSplit
#更新用K-means获取的簇中心集合，将簇中心换为len(centList)和bestCentToSplit,以便之后调整clusterAssment(总样本集对应簇中心与和簇中心距离的矩阵)时一一对应
bestClustAss[nonzero(bestClustAss[:,0].A == 1)[0],0] = len(centList) #change 1 to 3,4, or whatever
bestClustAss[nonzero(bestClustAss[:,0].A == 0)[0],0] = bestCentToSplit
print('the bestCentToSplit is: ',bestCentToSplit)
print('the len of bestClustAss is: ', len(bestClustAss))
#更新簇中心集合,注意与bestClustAss矩阵是一一对应的
centList[bestCentToSplit] = bestNewCents[0,:].tolist()[0]#replace a centroid with two best centroids
centList.append(bestNewCents[1,:].tolist()[0])
#reassign new clusters, and SSE
clusterAssment[nonzero(clusterAssment[:,0].A == bestCentToSplit)[0],:]= bestClustAss
return mat(centList), clusterAssment
二分K值最重要的是记住要将最佳分簇集合与clusterAssment一一对应
测试代码如下:
datMat3 = mat(loadDataSet('testSet2.txt'))
centList,myNewAssments = biKmeans(datMat3,3)
print(centList)
xArr = datMat3[:,0].flatten().A[0]
yArr = datMat3[:,1].flatten().A[0]
xArr1 = centList[:,0].flatten().A[0]
yArr1 = centList[:,1].flatten().A[0]
#paint为笔者自己写的绘图函数
paint(xArr,yArr,xArr1,yArr1)
def paint(xArr,yArr,xArr1,yArr1):
fig = plt.figure()
ax = fig.add_subplot(111)
ax.scatter(xArr,yArr,c='blue')
ax.scatter(xArr1,yArr1,c='red')
plt.show()
测试截图如下:
上述函数可以运行多次，聚类会收敛到全局最小值，而原始的别的!!3 ()函数偶尔会陷人局部最小值。
10.4 示例：对地图上的点进行聚类
假如有这样一种情况：你的朋友Drew希望你带他去城里庆祝他的生日。由于其他一些朋友也会过来，所以需要你提供一个大家都可行的计划。Drew给了你一些他希望去的地址。这个地址列表很长，有70个位置。我把这个列表保存在文件portland-Clubs.txt中，该文件和源代码一起打包。这些地址其实都在俄勒冈州的波特兰地区。
也就是说，一晚上要去70个地方！你要决定一个将这些地方进行聚类的最佳策略，这样就可以安排交通工具抵达这些簇的质心，然后步行到每个簇内地址。Drew的清单中虽然给出了地址，但是并没有给出这些地址之间的距离远近信息。因此，你要得到每个地址的纬度和经度，然后对这些地址进行聚类以安排你的行程。
示例：对于地理数据应用二分K-均值算法
(1)收集数据：使用Yahoo!PlaceFinder API收集数据
(2)准备数据：只保留经纬度信息
(3)分析数据：使用Matplotlib来构建一个二维数据图，其中包含簇与地图
(4)训练算法：训练不适用无监督学习
(5)测试算法：使用10.4节中的biKmeans( )函教
(6)使用算法| 最后的输出是包含簇及簇中心的地图
10.4.1 Yahoo! PlaceFinder API
Yahoo! PlaceFinderAPI，代码如下:
import urllib
import json
def geoGrab(stAddress, city):
#create a dict and constants for the goecoder
apiStem = 'http://where.yahooapis.com/geocode?'
#请求参数字典
params = {}
params['flags'] = 'J'#JSON return type
params['appid'] = 'aaa0VN6k'
params['location'] = '%s %s' % (stAddress, city)
#url编码请求参数,化为x1=xx&x2=xx形式
url_params = urllib.urlencode(params)
#print url_params
yahooApi = apiStem + url_params
print(yahooApi)
c=urllib.urlopen(yahooApi)
#获取json格式的数据
return json.loads(c.read())
from time import sleep
def massPlaceFind(fileName):
fw = open('places.txt', 'w')
#对文件中的每个样本调用geoGrab()获取json数据,解析后写入源文件
for line in open(fileName).readlines():
line = line.strip()
lineArr = line.split('\t')
retDict = geoGrab(lineArr[1], lineArr[2])
if retDict['ResultSet']['Error'] == 0:
lat = float(retDict['ResultSet']['Results'][0]['latitude'])
lng = float(retDict['ResultSet']['Results'][0]['longitude'])
print("%s\t%f\t%f" % (lineArr[0], lat, lng))
fw.write('%s\t%f\t%f\n' % (line, lat, lng))
else: print("error fetching")
fw.close()
测试代码如下:
geoResults = geoGrab('<span style="color: # VA Center', 'Augusta, ME')
print(geoResults)
由于主要不是为了调用YahooAPI，因此笔者没有实际调用API获取数据，理解这个过程就可以了，首先获取数据，然后调用二分K均值聚类对地址聚类分析。
10.4.2 对地理坐标进行聚类
这个例子中要聚类的俱乐部给出的信息为经度和维度，但这些信息对于距离计算还不够。在北极附近每走几米的经度变化可能达到数10度 ；而在赤道附近走相同的距离，带来的经度变化可能只是零点几。可以使用球面余弦定理来计算两个经纬度之间的距离
球面距离计算及簇绘图函数,代码如下:
#利用球面余弦定理计算指定(经度，纬度)两点的距离
def distSLC(vecA, vecB):#Spherical Law of Cosines
a = sin(vecA[0,1]*pi/180) * sin(vecB[0,1]*pi/180)
b = cos(vecA[0,1]*pi/180) * cos(vecB[0,1]*pi/180) * \
cos(pi * (vecB[0,0]-vecA[0,0]) /180)
return arccos(a + b)*6371.0 #pi is imported with numpy
import matplotlib
import matplotlib.pyplot as plt
def clusterClubs(numClust=5):
datList = []
#读取数据集，存储在datList中
for line in open('places.txt').readlines():
lineArr = line.split('\t')
datList.append([float(lineArr[4]), float(lineArr[3])])
datMat = mat(datList)
#调用二分K聚类获取簇中心集合以及clustAssing矩阵
myCentroids, clustAssing = biKmeans(datMat, numClust, distMeas=distSLC)
fig = plt.figure()
rect=[0.1,0.1,0.8,0.8]
scatterMarkers=['s', 'o', '^', '<span style="color: #', 'p', \
'd', 'v', 'h', '&', '&']
axprops = dict(xticks=[], yticks=[])
ax0=fig.add_axes(rect, label='ax0', **axprops)
imgP = plt.imread('Portland.png')
ax0.imshow(imgP)
ax1=fig.add_axes(rect, label='ax1', frameon=False)
#迭代簇集合,根据不同的marker画出对应的簇
for i in range(numClust):
ptsInCurrCluster = datMat[nonzero(clustAssing[:,0].A==i)[0],:]
markerStyle = scatterMarkers[i % len(scatterMarkers)]
ax1.scatter(ptsInCurrCluster[:,0].flatten().A[0], ptsInCurrCluster[:,1].flatten().A[0], marker=markerStyle, s=90)
#画出所有簇中心
ax1.scatter(myCentroids[:,0].flatten().A[0], myCentroids[:,1].flatten().A[0], marker='+', s=300)
plt.show()
测试代码如下:
kMeans.clusterClubs(5)
测试截图如下:
10.5 本章小结
聚类是一种无监督的学习方法。所谓无监督学习是指事先并不知道要寻找的内容，即没有目标变量。聚类将数据点归到多个簇中，其中相似数据点处于同一簇，而不相似数据点处于不同簇中。聚类中可以使用多种不同的方法来计算相似度。
一种广泛使用的聚类算法是K-均值算法，其中K是用户指定的要创建的簇的数目。K-均值聚类算法以K个随机质心开始。算法会计算每个点到质心的距离。每个点会被分配到距其最近的簇质心，然后紧接着基于新分配到簇的点更新簇质心。以上过程重复数次，直到簇质心不再改变。这个简单的算法非常有效但是也容易受到初始簇质心的影响。为了获得更好的聚类效果，可以使用另一种称为二分K-均值的聚类算法。二分K-均值算法首先将所有点作为一个簇，然后使用K-均值算法(K = 2 ) 对其划分。下一次迭代时，选择有最大误差的簇进行划分。该过程重复直到K个簇创建成功为止。二分K-均值的聚类效果要好于K-均值算法。
K-均值算法以及变形的K-均值算法并非仅有的聚类算法, 另外称为层次聚类的方法也被广泛使用
阅读(...) 评论()