第1页 / 共10页
第2页 / 共10页
第3页 / 共10页
第4页 / 共10页
第5页 / 共10页
第6页 / 共10页
第7页 / 共10页
第8页 / 共10页
K-means聚类算法的实现 源码+详细步骤.pdf
利用卜均值聚类
注数据分组/ /
考去#未标
本章内容
□ K-均值聚类算法
□ 对聚类得到的簇进行后处理
□ 二分1 均值聚类算法
□ 对地理位置进行聚类
在2000年和2004年的美国总统大选中，候选人的得票数比较接近或者说非常接近。任一候选
人得到的普选票数的最大百分比为50.7% ,而最小百分比为47.9%。如果1%的选民将手中的选票
投向另外的候选人，那么选举结果就会截然不同。实际上，如果妥善加以引导与吸引，少部分选
民就会转换立场。尽管这类选举者占的比例较低，但当候选人的选票接近时，这些人的立场无疑
会对选举结果产生非常大的影响®。如何找出这类选民，以及如何在有限的预算下采取措施来吸
引他们？答案就是聚类（Clustering)。
接下来介绍如何通过聚类实现上述目标。首先，收集用户的信息，可以同时收集用户满意或
不满意的信息，这是因为任何对用户重要的内容都可能影响用户的投票结果。然 后 ，将这些信息
输人到某个聚类算法中。接着，对聚类结果中的每一个簇（最好选择最大簇），精心构造能够吸
引该簇选民的消息。最后，开展竞选活动并观察上述做法是否有效。
聚类是一种无监督的学习，它将相似的对象归到同一个簇中。它有点像全自动分类®。聚类
方法几乎可以应用于所有对象，簇内的对象越相似，聚类的效果越好。本章要学习一种称为尺-
均 值 （1 « ^ 咖 ）聚类的算法。之所以称之为艮-均值是因为它可以发现&个不同的簇，且每个簇的
中心采用簇中所含值的均值计算而成。下面会逐步介绍该算法的更多细节。
在介绍尺-均值算法之前，先讨论一下装识别（clusteridentification)。簇识别给出聚类结
© 对 于 微 目 标 策 略 如 何 成 功 用 于 2004年 的 美 国 总 统 大 选 的 细 节 ，请 参 见 Foumier、303他 与 0(^11合著的却尸/66從\
America ( Simon & Schuster, 2006) 一 书 。
② 这 里 的 自 动 意 思 是 连 类 别 体 系 都 是 自 动 构 建 的 。一 译 者 注
10.1 K -均值聚类算法
185
果的含义。假定有一些数据，现在将相似数据归到一起，簇识别会告诉我们这些簇到底都是
些什么。聚类与分类的最大不同在于，分类的目标事先巳知，而聚类则不一样。因为其产生
的结果与分类相同，而只是类别没有预先定义，聚类有时也被称为无监督分类（皿8叩6代丨86£1
classification )。
聚类分析试图将相似对象归人同一簇，将不相似对象归到不同簇。相似这一概念取决于所选
择的相似度计算方法。前面章节已经介绍了不同的相似度计箅方法，后续章节它们会继续出现。
到底使用哪种相似度计算方法取决于具体应用。
下面会构建反-均值方法并观察其实际效果。接下来还会讨论简单尺-均值算法中的一些缺陷。
为了解决其中的一些缺陷，可以通过后处理来产生更好的簇。接着会给出一个更有效的称为二分
K-均 值 （bisectingk-means)的聚类算法。本章的最后会给出一个实例，该实例应用二分尺-均值
算法来寻找同时造访多个夜生活热点地区的最佳停车位。
10.1 K-均值聚类算法
K-均值聚类
优 点 ：容易实现。
缺 点 ：可能收敛到局部最小值，在大规模数据集上收敛较慢。
适用数据类型：数值型数据。
1 均值是发现给定数据集的&个簇的算法。簇个数^ 1 用户给定的，每一个簇通过其质心
( centroid) , 即族中所有点的中心来描述。
K-均值算法的工作流程是这样的。首先，随机确定&个初始点作为质心。然后将数据集中的
每个点分配到一个簇中，具体来讲，为每个点找距其最近的质心，并将其分配给该质心所对应的
簇。这一步完成之后，每个簇的质心更新为该簇所有点的平均值。
.
上述过程的伪代码表示如下：
创建女个点作为起始质心（经常是随机选择）
当任意一个点的簇分配结果发生改变时
对养据集中的每个数据点
. 对每个质心
计算质心与数据点之间的距离
将数据点分配到距其最近的簇
对每一个簇，计算簇中所有点的均值并将均值作为质心
186
第 10 章 利 用 反 - 均 值 聚 类 算 法 对 未 标 注 数 据 分 组
' K-均值聚类的一般流程
(1)收集数据：使用任意方法。
⑵ 准 备 数 据 ：需要数值型数据来计算距离，也可以将标称型数据映射为二值型数据再用
于距离计算。
(3)分析数据：使用任意方法。
(4)训练算法：不适用于无监督学习，即无监督学习没有训练过程。
(5)测试算法：应用聚类算法、观察结果。可以使用量化的误差指标如误差平方和（后面
会 介 绍 ）来评价算法的结果。
(6)使用算法：可以用于所希望的任何应用。通常情况下，簇质心可以代表整个簇的数据
来做出决策。
上 面 提 到 “最 近 ”质心的说法，意味着需要进行某种距离计算。读者可以使用所喜欢的
任意距离度量方法。数据集上艮-均值算法的性能会受到所选距离计算方法的影响。下面给出
K -均值算法的代码实现。首先创建一个名为^ 從^ 砂的文件，然后将下面程序清单中的代码
添加到文件中。
程序清单10-1 K -均值聚类支持函数
from n u m p y import ★
def l o a d D a t a S e t {file N a m e ) :
dataMat = H
fr = o p e n {fileName)
for line in f r .r e a d l i n e s ( ) ：
c u r L i n e = l i n e .s t r i p {).s p l i t ( 1\ t 1)
f l t L i n e = m a p ( f l o a t , cu r L i n e )
d a t a M a t . append(fltLine)
return dataMat
def distEclud(vecA, v e c B ) :
return s q r t ( s u m ( p o w e r (vecA - vecB, 2)))
def r a n d C e n t (dataSet, k ) ：
n = s h a p e ( d a t a S e t ) [1]
centroids = mat{zeros{ (k,n)))
for j in range (n) ：
I 构建簇质心
<~~l
m i n J = m i n ( d a t a S e t [ ：,j ])
rangeJ = f l o a t ( m a x ( d a t a S e t [：,j ]) - minJ)
c e n t r o i d s [ ：,j ] = m i n J + rangeJ * r a n d o m . r a n d ( k , 1)
return centroids
程序清单 10-1中的代码包含几个&-均值算法中要用到的辅助函数。第一个函数103^^3亡& -
Set ( ) 和上一章完全相同 , 它将文本文件导人到一个列表中。文本文件每一行为〖31)分隔的浮点数。
每一个列表会被添加到此七碰社中，最后返回£^七3过3七。该返回值是一^"^^>含许多其他列表的列
表。这种格式可以很容易将很多值封装到矩阵中。
10.1 K-均值聚类算法
187
下一个函数< ^ 七£011«1()计算两个向量的欧式距离。这是本章最先使用的距离函数，也可
以使用其他距离函数。
最后一个函数是『3 1 ^ 6 1 ^ ( ) ， 该函数为给定数据集构建一个包含&个随机质心的集合。随机
质心必须要在整个数据集的边界之内，这可以通过找到数据集每一维的最小和最大值来完成。然
后生成0到 1.0之间的随机数并通过取值范围和最小值，以便确保随机点在数据的边界之内 。 接下
来看一下这三个函数的实际效果。保 存 说 681^仍 文 件 ，然后在?)^100提本符下输人：
>>> i m p o r t k M e a n s
>>> f r o m n u m p y i m p o r t *
要 从 文 本 文 件 中 构 建 矩 阵 ， 输 人 下 面 的 命 令 （第 1 0 章 的 源 代 码 中 给 出 了 (6818过.加 的 内 容 ) ：
>>> d a t M a t = m a t ( k M e a n s .l o a d D a t a S e t ( 't e s t S e t •t x t 1 ))
读者可以了解一下这个二维矩阵，后面将使用该矩阵来测试完整的1 均值算法。下面看看
厂31^061^()函数是否正常运行。首先，先看一下矩阵中的最大值与最小值：
>>> m i n { d a t M a t [ ：, 0])
m a t r i x ( [ [ - 5 . 3 7 9 7 1 3 ] ] )
>>> m i n ( d a t M a t [ ：, 1])
m a t r i x ( [ [ - 4 . 2 3 2 5 8 6 ] ] )
>>> m a x { d a t M a t [ :, 1])
m a t r i x ([[ 5 . 1904]])
>>> m a x ( d a t M a t [ ：, 0])
m a t r i x ([[ 4 . 8 3 8 1 3 8 ] ] )
然后看看3^1«^61^ ()函数能否生成^ 通 _^3\之间的值：
>>> k M e a n s .r a n d C e n t ( d a t M a t ; 2)
m a t r i x ( [ [ - 3 . 2 4 2 7 8 8 8 9 , - 0 . 0 4 2 1 3 8 4 2 ] ,
3 . 1 9 5 2 4 2 3 1 ] ] )
[ - 0 . 9 2 4 3 7 1 7 1 ,
从上面的结果可以看到，函数181^^6址 ( >确实会生成1 ^0到1^乂之间的值。上述结果表明，
这些函数都能够按照预想的方式运行。最后测试一下距离计算方法：
>>> k M e a n s . d i s t E c l u d ( d a t M a t [ 0] , d a t M a t [ l ] )
5 . 1 8 4 6 3 2 8 1 6 6 8 1 3 3 2
所有支持函数正常运行之后，就可以准备实现完整的艮-均值算法了。该算法会创建&个质心，
然后将每个点分配到最近的质心，再重新计算质心。这个过程重复数次，直到数据点的簇分配结
果不再改变为止。打开_ 6 3 ^ ?7文件输人下面程序清单中的代码。
程序清单10-2 K -均值聚类算法
d e f k M e a n s ( d a t a S e t , k, d i s t M e a s = d i s t E c l u d , c r e a t e C e n t = r a n d C e n t ) ：
m = s h a p e ( d a t a S e t ) [0]
c l u s t e r A s s m e n t = m a t { z e r o s ( (m,2)))
c e n t r o i d s = c r e a t e C e n t (dataSet, k)
c l u s t e r C h a n g e d = T r u e
w h i l e c l u s t e r C h a n g e d ：
c l u s t e r C h a n g e d = F a l s e
f o r i i n r a n g e {m) ：
188
第 10 章 利 用 尺 - 均 值 聚 类 算 法 对 未 标 注 数 据 分 组
minDist - i n f ； minlndex = -1
for j in r an g e (k ) ：
寻找最近的质心
d i s t J I = d is tM e as (c e n t r o i d s [ j, ：] / d a t a S e t [ i , :])
i f d i s t J I < m in D ist ；
minDist = d i s t J I ； minlndex = j
i f c lu ste r A s sm e n t[i,0]
c lu s t e r A s s m e n t [i,：] = m in In de x ,m in D ist**2
!= m in lnd ex ： clusterChanged
T r u e
p rin t centroids
for cent in r a n g e (k ) ：
更新质心的位置
p t s I n C l u s t = d a t a S e t [ n o n z e r o ( c l u s t e r A s s m e n t [ : , 0 ] .A：
c e n t r o i d s [ c e n t , ：] = m e a n ( p t s I n C l u s t , a xis=0)
=cent) [0]]
return c e n tro id s , clusterAssment
上述清单给出了尺-均值算法。咖 631^()函数接受4个输人参数。只有数据集及簇的数目是必
选参数，而用来计算距离和创建初始质心的函数都是可选的。恤 时 郎 （）函数一开始确定数据集中
数据点的总数，然后创建一个矩阵来存储每个点的簇分配结果。簇分配结果矩阵。1^^杠 如 帥 即 七
包含两列：一列记录簇索引值，第二列存储误差。这里的误差是指当前点到簇质心的距离，后边
会使用该误差来评价聚类的效果。
按照上述方式（即计算质心-分配-重新计算 )反复迭代，直到所有数据点的簇分配结果不再
改变为止。程序中可以创建一个标志变量。1咖 1^比 化 即 的 ，如 果该值为竹此，则继续迭代。
上述迭代使用设1^16循环来实现。接下来遍历所有数据找到距离每个点最近的质心，这可以通过
对每个点遍历所有质心并计算点到每个质心的距离来完成0 。计算距离是使用& ^ 风@3参数给
出的距离函数，默认距离函数是也3邙 01此 （>，该函数的实现已经在程序清单10-1中给出。如果
任一点的簇分配结果发生改变，则更新。1即七6比 1^叩 0(^标志。
最 后 ，遍历所有质心并更新它们的取值® 。具体实现步骤如下：首先通过数组过滤来获得给
定簇的所有点；然后计算所有点的均值，选项3 \仕 = 0表示沿矩阵的列方向进行均值计算；最
后 ，程序返回所有的类质心与点分配结果。图10-1给出了一个聚类结果的示意图。
图10-1 K -均值聚类的结果示意图。图中数据集在三次迭代之后收敛。形状相似的
数据点被分到同样的簇中，簇中心使用十字来表示
1 0 . 2 使 用后 处 理来 提高 聚类 性 能
189
接下来看看程序清单10-2的运行效果。保存^ 6 3 卩3.9¥文件后，在Python提75符下输人：
>>> r e l o a d ( k M e a n s )
< m o d u l e 'kMeans' f r o m ' k M e a n s . p y c ' >
如果没有将前面例子中的6社过社数据复制过来，则可以输人下面的命令(i S t t ^ ^ A N u m P y )：
>>> d a t M a t = m a t ( k M e a n s .l o a d D a t a S e t ( 't e s t S e t .t x t '))
现在就可以对(^1^&七中的数据点进行聚类处理。从图像中可以大概预先知道最后的结果应
该有4个 簇 ，所以可以输人如下命令：
c l u s t A s s i n g = k M e a n s .k M e a n s ( d a t M a t , 4)
>>> m y C e n t r o i d s ,
[[-4 . 0 6 7 2 4 2 2 8
[ 0 .7 3 6 3 3 5 5 8
[-2 .59754537.
E 4 . 4 9 1 9 0 0 8 4
0 . 2 1 9 9 3 9 7 5 ]
-1 .41299247]
3 .15378974]
3 .46005807]]
[[-3 . 6 2 1 1 1 4 4 2 -2 .36505947]
[ 2 , ■21588922 "2 .88365904]
[-2.. 3 8 7 9 9 6 2 8
2 .96837672]
[ 2 . 6 2 6 5 2 9 9
3 .10868015JJ
[ [ - 3 . 5 3 9 7 3 8 8 9 -2..89384326]
[ 2 . 6 5 0 7 7 3 6 7 - 2 . 7 9 0 1 9 0 2 9 ]
[-2,. 4 6 1 5 4 3 1 5
2 .78737555]
[ 2 . 6 2 6 5 2 9 9
3 .10868015]]
上面的结果给出了4个质心。可以看到，经过3次迭代之后&-均值算法收敛。这4个质心以及
原始数据的散点图在图10-1中给出。
到目前为止，关于聚类的一切进展都很顺利，但事情并不总是如此。接 下 来会 讨 论 ^均 值 算
法可能出现的问题及其解决办法。
1 0 . 2 使用后处理来提高聚类性能
前 面 提 到 ，在^ 均值聚类中簇的数目&是一个用户预先定义的参数，那么用户如何才能知道乂
的选择是否正确？如何才能知道生成的簇比较好呢？在包含簇分配结果的矩阵中保存着每个点
的误差，即该点到簇质心的距离平方值。下面会讨论利用该误差来评价聚类质量的方法。
考 虑 图10-2中的聚类结果，这是在一个包含三个簇的数据集上运行尺-均值算法之后的结果，
但是点的簇分配结果值没有那么准确。K-均值算法收敛但聚类效果较差的原因是，K-均值算法收
敛到了局部最小值，而 非 全局 最小 值（局部最小值指结果还可以但并非最好结果，全局最小值是
可能的最好结果)。
一种用于度量聚类效果的指标是88丑(SumofSquaredError,误差平方和），对应程序清单10-2
中0 1 ^ ^ 6 沒 33爪6扯矩阵的第一歹1_]之和。88£ 值越小表示数据点越接近于它们的质心，聚类效果也
越好。因为对误差取了平方，因此更加重视那些远离中心的点。一种肯定可以降低88£值的方法是
增加簇的个数，但这违背了聚类的目标。聚类的目标是在保持族数目不变的情况下提高簇的质量。
那么如何对图10-2的结果进行改进？你可以对生成的簇进行后处理，一种方法是将具有最大
88£ 值的簇划分成两个簇。具体实现时可以将最大簇包含的点过滤出来并在这些点上运行尺-均值
190
第 10章 利 用 K-均值聚类算法对未标注数据分组
算 法 ，其 中 的 嫩 为 2。
图1 0 - 2 由于质心随机初始化导致艮-均值算法效果不好的一个例子，这需要额外的
后处理操作来清理聚类结果
为了保持簇总数不变，可以将某两个簇进行合并。从图 10-2中很明显就可以看出，应该将图
下部两个出错的簇质心进行合并。可以很容易对二维数据上的聚类进行可视化，但是如果遇到40
维的数据应该如何去做？
有两种可以量化的办法：合并最近的质心，或者合并两个使得33£增幅最小的质心。第一种
思路通过计算所有质心之间的距离，然后合并距离最近的两个点来实现。第二种方法需要合并两
个簇然后计算总38£值。必须在所有可能的两个簇上重复上述处理过；程 ，直到找到合并最佳的两
个簇为止。接下来将讨论利用上述簇划分技术得到更好的聚类结果的方法。
10.3 二 分 1<-均值算法
为克服&-均值算法收敛于局部最小值的问题，有人提出了另一个称为二分^ 均 值 （bisecting
K -means)的算法^ 该算法首先将所有点作为一个簇，然后将该簇一分为二。之后选择其中一个
簇继续进行划分，选择哪一个簇进行划分取决于对"其划分是否可以最大程度降低38£的值。上述
基于3 8£的划分过程不断重复，直到得到用户指定的簇数目为止。
二分&-均值算法的伪代码形式如下：
将所有点看成一个襄
当簇数目小于灸时
10.3 二分反-均值算法
191
对于每一个簇
计算总误差
在给定的簇上面进行艮-均 值 聚 类 （^^2)
计算将该簇一分为二之后的总误差
选择使得误差最小的那个族进行划分操作
另一种做法是选择88£最大的簇进行划分，直到簇数目达到用户指定的数目为止。这个做法
听起来并不难实现。下面就来看一下该算法的实际效果。打开^ 抓!^^7文件然后加人下面程序
清单中的代码。
程序清单10-3 二 分 ^均 值 聚 类 算 法
d e f b i K m e a n s ( d a t a S e t , k, d i s t M e a s = d i s t E c l u d ) ：
m = s h a p e (dataSet) [0]
c l u s t e r A s s m e n t = m a t ( z e r o s { (m,2)))
c e n t r o i d 0 = m e a n ( d a t a S e t 7 axis=0) . tolist() [0]
c e n t L i s t = [centroid0]
f o r j in r a n g e (m) ：
命
Y
创建一个初始簇
c l u s t e r A s s m e n t [j,1] = d i s t M e a s ( m a t ( c e n t r o i d 0 ) , d a t a S e t [ j (
: ] ) * * 2
w h i l e ( l e n ( c e n t L i s t ) < k ) ：
l o w e s t S S E = inf
f o r i in r a n g e { l e n { c e n t L i s t ) ) ：
p t s I n C u r r C l u s t e r =\
d a t a S e t [ n o n z e r o ( c l u s t e r A s s m e n t [ ：,0] .A==i) [01 , ：
]
c e n t r o i d M a t , s p l i t C l u s t A s s = \
k M e a n s { p t s I n C u r r C l u s t e r , 2 , d i s t M e a s )
s s e S p l i t = s u m ( s p l i t C l u s t A s s [ ：,1])
s s e N o t S p l i t = \
A 尝试划分
, 每一簇
s u m ( c l u s t e r A s s m e n t [ n o n z e r o ( c l u s t e r A s s m e n t [：•0] .A!=i) [0],1]}
p r i n t " s s eSplit, a n d n o t S p X i t ： u ,s s e S p l i t , s s e N o t S p l i t
if ( s s e S p l i t + s s e N o t S p l i t ) < l o w e s t S S E
b e s t C e n t T o S p l i t = i
b e s t N e w C e n t s = c e n t r o i d M a t
b e s t C l u s t A s s = s p l i t C l u s t A s s .c o p y ()
l o w e s t S S E = s s e S p l i t + s s e N o t S p l i t
b e s t C l u s t A s s [ n o n z e r o ( b e a t C l u s t A s s [ :, 0 ] .A ==
i ) [ o ] , o ]
b e s t C l u s t A s s [ n o n z e r o ( b e s t C l u s t A s s [ ：, 0 ] .A ==
0 ) [ 0 ] , 0 ]
l e n (centList)
=\
=\
J O 更新簇的
K 分配结果
b e s t C e n t T o S p l i t
p r i n t 1 t h e b e s t C e n t T o S p l i t is: ', b e s t C e n t T o S p l i t
p r i n t 1 t h e l e n of b e s t C l u s t A s s is: ■, l e n { b e s t C l u s t A s s )
c e n t L i s t [ b e s t C e n t T o S p l i t ] = b e s t N e w C e n t s [0,:]
c e n t L i s t .a p p e n d ( b e s t N e w C e n t s [ 1 , ：])
c l u s t e r A s s m e n t t n o n z e r o ( c l u s t e r A s s m e n t [:,0] .A == \
b e s t C e n t T o S p l i t ) [0],:]= b e s t C l u s t A s s
r e t u r n m a t ( c e n t L i s t ) , c l u s t e r A s s m e n t
上述程序中的函数与程序清单10-2中函数咖扭^ ( > 的参数相同。在给定数据集、所期望的
簇数目和距离计算方法的条件下，函数返回聚类结果。同咖时 1^()一 样，用户可以改变所使用
的距离计算方法。
相关推荐
2023年江西萍乡中考道德与法治真题及答案.doc
2012年重庆南川中考生物真题及答案.doc
2013年江西师范大学地理学综合及文艺理论基础考研真题.doc
2020年四川甘孜小升初语文真题及答案I卷.doc
2020年注册岩土工程师专业基础考试真题及答案.doc
2023-2024学年福建省厦门市九年级上学期数学月考试题及答案.doc
2021-2022学年辽宁省沈阳市大东区九年级上学期语文期末试题及答案.doc
2022-2023学年北京东城区初三第一学期物理期末试卷及答案.doc
2018上半年江西教师资格初中地理学科知识与教学能力真题及答案.doc
2012年河北国家公务员申论考试真题及答案-省级.doc
2020-2021学年江苏省扬州市江都区邵樊片九年级上学期数学第一次质量检测试题及答案.doc
2022下半年黑龙江教师资格证中学综合素质真题及答案.doc
