2.2.3 典型聚类算法
数据聚类就是将本没有类别参考的数据进行分析并划分为不同的聚类，即从这些数据导出类标号。聚类分析本身就是根据数据来发掘数据对象及其关系信息，并将这些数据分类。每个类内的对象之间是相似的，而各个类间的对象是不相关的。不难理解，类内相似性越高，类间相异性越高，则聚类效果越好。
K⁃means算法，应该是聚类算法中最为基础但也最为重要的算法。
1）K⁃means算法思想
由于具有出色的速度和良好的可扩展性，K⁃means聚类算法算得上是最著名的聚类方法。K⁃means算法是一个重复移动聚类中心点的过程，把聚类的中心点，也称重心（centroid），移动到其包含成员的平均位置，然后重新划分其内部成员。K是算法计算出的超参数，表示聚类的数量。K⁃means可以自动分配样本到不同的聚类，但是不能决定究竟要分几个聚类。K必须是一个比训练集样本数小的正整数。有时，聚类的数量是由问题内容指定。例如，一个鞋厂有三种新款式，它想知道每种新款式都有哪些潜在客户，于是它调研客户，然后从数据里找出三个聚类。也有一些问题没有指定聚类的数量，最优的聚类数量是不确定的。
K⁃means的参数是聚类的重心位置和其内部观测值的位置。与广义线性模型和决策树类似，K⁃means参数的最优解也是以成本函数最小化为目标。K⁃means成本函数公式如下：
（2⁃3）
ck指第k个聚类，x
指每个类内部成员，μi指第i个聚类的重心位置。成本函数是各个聚类畸变程度（distortion）之和。每个聚类的畸变程度等于该聚类重心与其内部成员位置距离的平方和。若聚类内部的成员彼此间越紧凑则该聚类的畸变程度越小，反之，若聚类内部的成员彼此间越分散则该聚类的畸变程度越大。求解成本函数最小化的参数就是一个重复配置每个聚类包含的观测值，并不断移动聚类重心的过程。首先，聚类的重心是随机确定的位置。实际上，重心位置等于随机选择的观测值的位置。每次迭代的时候，K⁃means会把观测值分配到离待分类成员最近的聚类，然后把重心移动到该聚类全部成员位置的平均值那里。
2）K⁃means算法流程
输入：聚类个数k，数据集Xmxn。
输出：满足方差最小标准的k个聚类。
①选择k个初始中心点，例如
， … ， 
；
②对于
，分别与
比较，假定与
差值最少，就标记为
；
③对于所有标记为i点，重新计算
｛所有标记为i的样本的每个特征的均值｝；(https://www.daowen.com)
④重复②③，直到所有
值的变化小于给定阈值或者达到最大迭代次数。
3）K⁃means算法优缺点
①在K⁃means算法中k需要事先确定，这个k值有时候比较难确定。
②在K⁃means算法中，首先需要初始k个类中心，然后以此确定一个初始划分，最后对初始划分进行优化。这个初始聚类中心的选择对聚类结果有较大的影响，一旦初始值选择得不好，可能无法得到有效的聚类结果。多设置一些不同的初值，对比最后的运算结果，一直到结果趋于稳定结束。
③该算法需要不断地进行样本分类调整，不断地计算调整后的新的聚类中心，因此当数据量非常大时，算法的时间开销是非常大的。
④对离群点很敏感。
⑤从数据表示角度来说，在K⁃means中，用单个点来对cluster进行建模，这实际上是一种最简化的数据建模形式。这种用点来对cluster进行建模实际上就已经假设了各cluster的数据是呈圆形（或者高维球形）或者方形等分布的。不能发现非凸形状的簇。但在实际生活中，很少能有这种情况。所以在混合高斯分布聚类模型GMM（gaussian mixture model）中，使用了一种更加一般的数据表示，也就是高斯分布。
⑥从数据先验的角度来说，在K⁃means中，假设各个cluster的先验概率是一样的，但是各个cluster的数据量可能是不均匀的。举个例子，cluster A中包含了10 000个样本，cluster B中只包含了100个。那么对于一个新的样本，在不考虑其与cluster A、 cluster B相似度的情况，其属于cluster A的概率肯定是要大于cluster B的。
⑦在K⁃means中，通常采用欧氏距离来衡量样本与各个cluster的相似度。这种距离实际上假设了数据的各个维度对相似度的衡量作用是一样的。
⑧在K⁃means中，各个样本点只属于与其相似度最高的那个cluster ，这实际上是一种hard clustering。
针对K⁃means算法的缺点，很多前辈提出了一些改进的算法。例如K⁃Modes算法，实现对离散数据的快速聚类，保留了K⁃means算法的效率同时将K⁃means的应用范围扩大到离散数据。还有K⁃Prototype算法，可以对离散与数值属性两种混合的数据进行聚类，在K⁃Prototype中定义了一个对数值与离散属性都计算的相异性度量标准。
K⁃means更像是一种top⁃down思想，它们要解决的问题是，确定cluster数量，也就是k的取值。在确定了k后，再来进行数据的聚类。
