5.2 K-means、K中心点方法及其改进方法

K-means、K中心点方法及其改进方法主讲人：李侃K-means、K中心点方法及其改进方法K-means以簇数目k为输入参数，把n个对象划分为k个簇，使得簇内的相似度高，而簇间的相似度低。簇作为运算对象参与度量时，使用簇中对象的均值代表簇。随机地选择k个对象，每个对象代表一个簇的初始均值。对于剩余的每个对象，根据其与每个簇均值的距离，将它分配到最相似的簇。计算每个簇的新均值。这个过程不断重复，直到簇稳定不再变化。这里的不再变化，实质上是准则函数的收敛。K-means、K中心点方法及其改进方法K-meansK-means算法所选择的准则函数是平方误差函数：其中，p是空间中的点，表示给定对象；是簇的均值。K-means、K中心点方法及其改进方法K-means输入：n个对象的数据集D，簇数目k输出：k个簇1.从D中随机选择k个对象作为初始簇中心；2.将每个对象分配到中心与其最近的簇；3.重新计算簇的均值，使用新的均值作为每个簇的中心；4.重复步骤2、3直到所有簇中的对象不再变化算法K-means、K中心点方法及其改进方法K-meansK-means算法是一种期望最大化（expectation-maximization，EM）算法：

E步：每个对象分配到一个簇中。

M步：重新计算簇中心参数。K-means算法的计算复杂度是，其中n是数据对象的总数，k是簇的个数，t是迭代的次数，通常，K-means、K中心点方法及其改进方法K-means局限性算法可能终止于局部最优解算法只有当簇均值可求或者定义可求时才能使用簇的数目k必须事先给定，而在一些实际应用中是k是很难事先知道算法不适合发现非凸形状的簇，或者大小差别很大的簇算法对噪声和离群点数据敏感K-means、K中心点方法及其改进方法K中心点K中心点算法的过程：随机选择初始中心点在迭代过程中，只要能够提高聚类结果质量，就用非中心点替换中心点聚类结果的质量由代价函数评估，该函数度量对象与其簇的中心点之间的平均相异度。该算法也依靠迭代，最终使得所有点或者为簇中心或者属于离它最近的簇。K-means、K中心点方法及其改进方法K中心点用表示正在被考察的非中心点、表示中心点，p表示每一个非中心点对象，替换规则如下：p当前隶属于中心点。如果被所代替作为中心点，

p离最近，，那么p被重新分配给。

p离最近，那么p被重新分配给。p当前隶属于中心点，。如果被代替作为一个中心点，p离最近，那么对象的隶属不发生变化。

p离最近，那么p被重新分配给。规则一：规则二：K-means、K中心点方法及其改进方法K中心点K中心点算法采用的评判准则是绝对误差标准，定义：其中，p是空间中的点，代表簇中的一个给定对象；

是代表簇的对象。K-means、K中心点方法及其改进方法K中心点K中心点算法也有许多变种，其中最早提出的算法：围绕中心点的划分（PartitionAroundMedoids,PAM）算法K中心点输入：n个对象的数据集D，簇数目k输出：k个簇1.从D中随机选择k个对象作为初始的簇的中心点；2.将每个剩余对象分配到最近的中心点所对应的簇中；3.随机选择一个非中心点对象；4.计算用交换中心点的总代价S；5.如果S小于0，则用替换，形成新的k个中心点集；6.重复步骤2到步骤5，直到聚类稳定K-means、K中心点方法及其改进方法K中心点K中心点算法使用位于簇“中心”的实际点代表簇，所以它不易受到离群点之类的极端值的影响；当数据对象中存在噪声和离群点时，K中心点算法较之于K-means算法具有更高的鲁棒性；K中心点算法同K-means算法一样，需要事先由用户给出簇的数目k。K中心点K-means、K中心点方法及其改进方法核K-meansK-means算法中簇之间的分割边界是线性的，但它不适用非凸簇的数据。采用核（kernel）方法应用于K-means中，即：核K-means（kernelK-means）算法，通过核方法来提取簇之间的非线性边界。主要思想将输入空间中的数据点映射到某个高维特征空间中的点，其中是非线性映射。K-means、K中心点方法及其改进方法核K-means假设所有的点已经映射到特征空间中的。令代表n×n的对称核矩阵，其中。令定义将n个点聚类为k个簇的划分，并令对应的簇均值在特征空间中对应，其中代表在特征空间中的均值，其中。核K-means

K-means、K中心点方法及其改进方法核K-means在特征空间中，核K-means的平方误差的目标函数为：核K-meansK-means、K中心点方法及其改进方法核K-means将E目标展开，用核函数表示，可得：核K-means

K-means、K中心点方法及其改进方法核K-means特征空间中一个点到簇均值的距离仅用核函数就可以计算。在核K-means算法的簇赋值步骤中，按如下方式将一个点赋给最近的簇均值：其中去掉了项，因为它对所有的k个簇保持不变，且不影响簇赋值。

核K-meansK-means、K中心点方法及其改进方法输入：簇的数目k,任意小的正数，核函数K输出：每个数据所属的簇1.t←02.//将所有点随机分成k个簇3.repeat4.

t←t+15.foreach

do//计算分簇均值的平方范数6.

7.foreach

do//对应和的平均核值8.

foreach

do

//找出距离每个点最近的分簇核K-means核K-meansK-means、K中心点方法及其改进方法核K-means算法10.foreach

do11.foreach

do12.

13.

14.//重新赋分簇15.16.until

核K-means核K-meansK-means、K中心点方法及其改进方法核K-means通过检查所有点的簇赋值，判断是否收敛。未发生簇变化的点的数目为，其中t表示当前迭代。被赋予新簇的点的比例为：当以上比例小于某一阈值时，核K-means方法终止。

K-means、K中心点方法及其改进方法核K-means计算复杂度分析核K-means方法的总计算复杂度为，其中t为收敛时迭代的次数。I/O复杂度为次对核矩阵K的扫描。核K-means

K-means、K中心点方法及其改进方法EM聚类K-means方法是硬分（hardassignment）聚类方法的一种，每个点只属于一个簇。EM聚类是一种软分（softassignment）聚类方法,每个点都有属于每个簇的概率。EM聚类d维中的EMd维中的EM方法，其中每一个簇由一个多元正态分布刻画：其中，簇均值，协方差矩阵，|Σ|

表示矩阵Σ的行列式，是x属于簇Ci的概率密度。EM聚类d维中的EM假设X的概率密度函数是在所有k个簇之上的高斯混合模型：其中，先验概率满足d维中的EMEM聚类d维中的EM高斯混合模型是由均值，协方差矩阵，以及k个正态分布对应的混合概率刻画，因此模型参数可表示为：d维中的EMEM聚类d维中的EM对每一个簇，估计d维的均值向量：，以及的协方差矩阵：由于协方差矩阵是对称阵，需要估计对协方差和d个方差，因此一共有个参数。实际中，难有足够的数据来对这么多的参数进行估计。

EM聚类d维中的EM一种简化方法是假设各个维度彼此独立，从而可以得到一个对角协方差矩阵：在这一独立性假设之下，只需要估计d个参数来估计该对角协方差矩阵。d维中的EM初始化对每一个簇，初始化均值：从每个维度中，在其取值范围内均匀地随机选取一个值。协方差矩阵初始化为的单位矩阵。簇的先验概率初始化为，每一个簇的概率相等。

d维中的EM期望步骤给定点，计算簇的后验概率。记为。

可看作点对簇的权值，表示簇在所有n个点上的权向量。

d维中的EM最大化步骤给定权值，重新估计、和。簇的均值可以估计为：令为簇的居中数据矩阵。令表示中的第j个点。将表示为外积形式：d维中的EM最大化步骤考虑成对属性的情况，维度