赞
踩
更多内容关注公众号:数学的旋律
k均值(k-means)是一种聚类算法,其工作流程如下:随机选择k个点作为初始质心(质心即簇中所有点的中心),然后将数据集中的每个点分配到一个簇中,具体来讲,为每个点找距其最近的质心,并将其分配给该质心所对应的簇。这一步完成之后,每个簇的质心更新为该簇所有点的平均值。重复以上步骤,直到质心不发生变化。
k均值的操作解释参见图1。
然而随机地选取初始质心,簇的质量常常很差,为克服该问题,有人提出了二分k均值(bisecting k-means)算法,该算法不太受初始化问题的影响。
本文讨论欧氏空间中的聚类问题,所用距离为欧氏距离(在kNN中已介绍过欧氏距离,这里不再重述)。
k均值是发现给定数据集的k个簇的算法。簇个数k是用户给定的,每一个簇通过其质心(centroid),即簇中所有点的中心来描述。
k均值的基本算法如下:首先,随机选择k个初始质心,其中k即所期望的簇的个数。每个点指派到最近的质心,而指派到一个质心的点集为一个簇。然后,根据指派到簇的点,更新每个簇的质心。重复指派和更新步骤,直到簇不发生变化,或等价地,直到质心不发生变化。
算法1 基本k均值算法
选择k个点作为初始质心
repeat
将每个点指派到最近的质心,形成k个簇
重新计算每个簇的质心
until 质心不发生变化
前面说到,k个初始质心是随机选择的,不同的选择可能产生不同的结果,如图2所示,经过两次迭代,不同的初始质心得出(a)(b)两种不同结果。
如何才能知道生成的簇哪个比较好呢?我们使用误差的平方和(Sum of the Squared Error,SSE)作为度量聚类质量的目标函数。我们计算每个数据点的误差,即它到最近质心的欧氏距离,然后计算误差的平方和。SSE形式地定义如下: S S E = ∑ i = 1 k ∑ x ∈ C i d i s t ( c i , x ) 2 SSE=\sum_{i=1}^k\sum_{x∈C_i}dist(c_i,x)^2 SSE=i=1∑kx∈Ci∑dist(ci,x)2其中,dist是欧氏空间中两个对象之间的标准欧氏距离。若数据集为 D = { x 1 , x 2 , ⋯ , x i , ⋯ , x N } D=\{x_1,x_2,\cdots,x_i,\cdots,x_N\} D={ x1,x2,⋯,xi,⋯,xN}其中 x i = ( x i ( 1 ) , x i ( 2 ) , ⋯ , x i ( i ) , ⋯ , x i ( n ) ) T x_i=({x_i}^{(1)},{x_i}^{(2)},\cdots,{x_i}^{(i)},\cdots,{x_i}^{(n)})^T xi
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。