K-Means聚类若干问题
2024-05-15
1. K-Means聚类若干问题
1 K-Means聚类收敛性怎么证明？一定会收敛？？？
2 聚类中止条件：迭代次数、簇中心变化率、最小平方误差MSE？？？
3 聚类初值的选择，对聚类结果的影响？？？（K-Means对初值是敏感的）
4 肘部选择法——确定聚类数K
没有所谓最好的选择聚类数的方法，通常是需要根据不同的问题，人工进行选择的。选择的时候思考我们运用 K-均值算法聚类的动机是什么，然后选择能最好服务于该目的标聚类数。当人们在讨论，选择聚类数目的方法时，有一个可能会谈及的方法叫作“肘部法则”。 关于“肘部法则”，我们所需要做的是改变 K 值，也就是聚类类别数目的总数 。我们 用一个聚类来运行 K 均值聚类方法。这就意味着，所有的数据都会分到一个聚类里，然后计算成本函数J，K 代表聚类种类 。
我们可能会得到一条类似于这样的曲线。像一个人的肘部。这就是“肘部法则”所做的，让我们来看这样一个图，看起来就好像有一个很清楚的肘在那儿。好像人的手臂，如果你伸出你的胳膊，那么这就是你的肩关节、肘关节、手。这就是“肘部法则”。你会发现这种模式，它的畸变值会迅速下降，从 1 到 2，从 2 到 3 之后，你会在 3 的时候达到一个肘点。在此之后，畸变值就下降的非常慢，看起来就像使用 3 个聚类来进行聚类是正确的，这是因为 那个点是曲线的肘点，畸变值下降得很快 ，K 等于 3 之后就下降得很慢，那么我们就选 K 等于 3。 当你应用“肘部法则”的时候，如果你得到了一个像上面这样的图，那么这将是一种用来选择聚类个数的合理方法。
uk是第k 个类的重心位置。成本函数是各个类畸变程度（distortions）之和。每个类的畸变程度等于该类重心与其内部成员位置距离的平方和。若类内部的成员彼此间越紧凑则类的畸变程度越小，反之，若类内部的成员彼此间越分散则类的畸变程度越大。求解成本函数最小化的参数就是一个重复配置每个类包含的观测值，并不断移动类重心的过程。
importnumpyasnpimportmatplotlib.pyplotaspltfromsklearn.clusterimportKMeansfromscipy.spatial.distanceimportcdistx = np.array([1,2,3,1,5,6,5,5,6,7,8,9,7,9])y = np.array([1,3,2,2,8,6,7,6,7,1,2,1,1,3])data = np.array(list(zip(x, y)))# 肘部法则 求解最佳分类数# K-Means参数的最优解也是以成本函数最小化为目标# 成本函数是各个类畸变程度（distortions）之和。每个类的畸变程度等于该类重心与其内部成员位置距离的平方和# 画肘部图aa=[]K = range(1,10)forkinrange(1,10): kmeans=KMeans(n_clusters=k) kmeans.fit(data) aa.append(sum(np.min(cdist(data, kmeans.cluster_centers_,'euclidean'),axis=1))/data.shape[0])plt.figure()plt.plot(np.array(K), aa,'bx-')plt.show()# 绘制散点图及聚类结果中心点plt.figure()plt.axis([0,10,0,10])plt.grid(True)plt.plot(x, y,'k.')kmeans = KMeans(n_clusters=3)kmeans.fit(data)plt.plot(kmeans.cluster_centers_[:,0], kmeans.cluster_centers_[:,1],'r.')plt.show()
5 K-Means优缺点及适用范围
K值需要预先给定，属于预先知识，很多情况下K值的估计是非常困难的，对于像计算全部微信用户的交往圈这样的场景就完全的没办法用K-Means进行 。对于可以确定K值不会太大但不明确精确的K值的场景，可以进行迭代运算，然后 找出Cost Function最小时所对应的K值，这个值往往能较好的描述有多少个簇类 。
K-Means算法对 初始选取的聚类中心点是敏感的 ，不同的随机种子点得到的聚类结果完全不同
K-Means算法 并不是适用所有的样本类型 。它 不能处理非球形簇、不同尺寸和不同密度的簇 。
K-Means算法对离群点的数据进行聚类时，K均值也有问题，这种情况下，离群点检测和删除有很大的帮助。（ 异常值对聚类中心影响很大，需要离群点检测和剔除 ）
5.K-Means算法对噪声和离群点敏感，最重要是结果不一定是全局最优，只能保证局部最优。
6 从K-Means 到 Gaussian Mixture Model
数据表示
在 k-means 中，我们用单个点来对 cluster 进行建模，这实际上是一种最简化的数据建模形式。这种用点来对 cluster 进行建模实际上就已经假设了各 cluster 的数据是呈圆形（或者高维球形）分布的。但在实际生活中，很少能有这种情况。 所以在 GMM 中，我们使用一种更加一般的数据表示，也就是高斯分布。
数据先验
在 k-means 中，我们假设各个 cluster 的先验概率是一样的，但是各个 cluster 的数据量可能是不均匀的。举个例子，cluster A 中包含了10000个样本，cluster B 中只包含了100个。那么对于一个新的样本，在不考虑其与 A B cluster 相似度的情况，其属于 cluster A 的概率肯定是要大于 cluster B的。 在 GMM 中，同样对数据先验进行了建模。
相似度衡量
在 k-means 中，我们通常采用 欧氏距离来衡量样本与各个 cluster 的相似度 。这种距离实际上假设了数据的 各个维度对于相似度的衡量作用是一样的 。 但在 GMM 中，相似度的衡量使用的是后验概率
通过引入协方差矩阵，我们就可以对各维度数据的不同重要性进行建模。
数据分配
在 k-means 中，各个 样本点只属于与其相似度最高的那个cluster ，这实际上是一种 hard clustering 。 在 GMM 中则使用的是后验概率来对各个cluster 按比例分配，是一种 fuzzy clustering 。
Hierarchical Clustering 与 K-Means 和 GMM 这一派系的聚类算法不太相同：
K-Means 与 GMM 更像是一种 top-down 的思想，它们首先要解决的问题是，确定 cluster 数量，也就是 k 的取值。在确定了 k 后，再来进行数据的聚类。
Hierarchical Clustering 则是一种 bottom-up 的形式，先有数据，然后通过不断选取最相似的数据进行聚类。
K-Means业界用得多的原因之一就是 收敛快 ，现在还能通过分布式计算加速，别的原因有调参就一个K。
链接：https://www.jianshu.com/p/cc74c124c00b
来源：
2. Kmeans聚类算法简介
由于具有出色的速度和良好的可扩展性，Kmeans聚类算法算得上是最著名的聚类方法。Kmeans算法是一个重复移动类中心点的过程，把类的中心点，也称重心(centroids)，移动到其包含成员的平均位置，然后重新划分其内部成员。k是算法计算出的超参数，表示类的数量；Kmeans可以自动分配样本到不同的类，但是不能决定究竟要分几个类。k必须是一个比训练集样本数小的正整数。有时，类的数量是由问题内容指定的。例如，一个鞋厂有三种新款式，它想知道每种新款式都有哪些潜在客户，于是它调研客户，然后从数据里找出三类。也有一些问题没有指定聚类的数量，最优的聚类数量是不确定的。后面我将会详细介绍一些方法来估计最优聚类数量。
Kmeans的参数是类的重心位置和其内部观测值的位置。与广义线性模型和决策树类似，Kmeans参数的最优解也是以成本函数最小化为目标。Kmeans成本函数公式如下：
μiμi是第kk个类的重心位置。成本函数是各个类畸变程度(distortions)之和。每个类的畸变程度等于该类重心与其内部成员位置距离的平方和。若类内部的成员彼此间越紧凑则类的畸变程度越小，反之，若类内部的成员彼此间越分散则类的畸变程度越大。求解成本函数最小化的参数就是一个重复配置每个类包含的观测值，并不断移动类重心的过程。首先，类的重心是随机确定的位置。实际上，重心位置等于随机选择的观测值的位置。每次迭代的时候，Kmeans会把观测值分配到离它们最近的类，然后把重心移动到该类全部成员位置的平均值那里。
2.1 根据问题内容确定
这种方法就不多讲了，文章开篇就举了一个例子。
2.2 肘部法则
如果问题中没有指定kk的值，可以通过肘部法则这一技术来估计聚类数量。肘部法则会把不同kk值的成本函数值画出来。随着kk值的增大，平均畸变程度会减小；每个类包含的样本数会减少，于是样本离其重心会更近。但是，随着kk值继续增大，平均畸变程度的改善效果会不断减低。kk值增大过程中，畸变程度的改善效果下降幅度最大的位置对应的kk值就是肘部。为了让读者看的更加明白，下面让我们通过一张图用肘部法则来确定最佳的kk值。下图数据明显可分成两类：
从图中可以看出，k值从1到2时，平均畸变程度变化最大。超过2以后，平均畸变程度变化显著降低。因此最佳的k是2。
2.3 与层次聚类结合
经常会产生较好的聚类结果的一个有趣策略是，首先采用层次凝聚算法决定结果粗的数目，并找到一个初始聚类，然后用迭代重定位来改进该聚类。
2.4 稳定性方法
稳定性方法对一个数据集进行2次重采样产生2个数据子集，再用相同的聚类算法对2个数据子集进行聚类，产生2个具有kk个聚类的聚类结果，计算2个聚类结果的相似度的分布情况。2个聚类结果具有高的相似度说明kk个聚类反映了稳定的聚类结构，其相似度可以用来估计聚类个数。采用次方法试探多个kk，找到合适的k值。
2.5 系统演化方法
系统演化方法将一个数据集视为伪热力学系统，当数据集被划分为kk个聚类时称系统处于状态kk。系统由初始状态k=1k=1出发，经过分裂过程和合并过程，系统将演化到它的稳定平衡状态 kiki ，其所对应的聚类结构决定了最优类数 kiki 。系统演化方法能提供关于所有聚类之间的相对边界距离或可分程度，它适用于明显分离的聚类结构和轻微重叠的聚类结构。
2.6 使用canopy算法进行初始划分
基于Canopy Method的聚类算法将聚类过程分为两个阶段
(1) 聚类最耗费计算的地方是计算对象相似性的时候，Canopy Method在第一阶段选择简单、计算代价较低的方法计算对象相似性，将相似的对象放在一个子集中，这个子集被叫做Canopy，通过一系列计算得到若干Canopy，Canopy之间可以是重叠的，但不会存在某个对象不属于任何Canopy的情况，可以把这一阶段看做数据预处理；
(2) 在各个Canopy内使用传统的聚类方法(如Kmeans)，不属于同一Canopy的对象之间不进行相似性计算。
从这个方法起码可以看出两点好处：首先，Canopy不要太大且Canopy之间重叠的不要太多的话会大大减少后续需要计算相似性的对象的个数；其次，类似于Kmeans这样的聚类方法是需要人为指出K的值的，通过(1)得到的Canopy个数完全可以作为这个k值，一定程度上减少了选择k的盲目性。
其他方法如贝叶斯信息准则方法(BIC)可参看文献[4]。
选择适当的初始质心是基本kmeans算法的关键步骤。常见的方法是随机的选取初始中心，但是这样簇的质量常常很差。处理选取初始质心问题的一种常用技术是：多次运行，每次使用一组不同的随机初始质心，然后选取具有最小SSE(误差的平方和)的簇集。这种策略简单，但是效果可能不好，这取决于数据集和寻找的簇的个数。
第二种有效的方法是，取一个样本，并使用层次聚类技术对它聚类。从层次聚类中提取kk个簇，并用这些簇的质心作为初始质心。该方法通常很有效，但仅对下列情况有效：(1)样本相对较小，例如数百到数千(层次聚类开销较大)；(2) kk相对于样本大小较小。
第三种选择初始质心的方法，随机地选择第一个点，或取所有点的质心作为第一个点。然后，对于每个后继初始质心，选择离已经选取过的初始质心最远的点。使用这种方法，确保了选择的初始质心不仅是随机的，而且是散开的。但是，这种方法可能选中离群点。此外，求离当前初始质心集最远的点开销也非常大。为了克服这个问题，通常该方法用于点样本。由于离群点很少(多了就不是离群点了)，它们多半不会在随机样本中出现。计算量也大幅减少。
第四种方法就是上面提到的canopy算法。
常用的距离度量方法包括：欧几里得距离和余弦相似度。两者都是评定个体间差异的大小的。
欧氏距离是最常见的距离度量，而余弦相似度则是最常见的相似度度量，很多的距离度量和相似度度量都是基于这两者的变形和衍生，所以下面重点比较下两者在衡量个体差异时实现方式和应用环境上的区别。
借助三维坐标系来看下欧氏距离和余弦相似度的区别：
从图上可以看出距离度量衡量的是空间各点间的绝对距离，跟各个点所在的位置坐标(即个体特征维度的数值)直接相关；而余弦相似度衡量的是空间向量的夹角，更加的是体现在方向上的差异，而不是位置。如果保持A点的位置不变，B点朝原方向远离坐标轴原点，那么这个时候余弦相似cosθ是保持不变的，因为夹角不变，而A、B两点的距离显然在发生改变，这就是欧氏距离和余弦相似度的不同之处。
根据欧氏距离和余弦相似度各自的计算方式和衡量特征，分别适用于不同的数据分析模型：欧氏距离能够体现个体数值特征的绝对差异，所以更多的用于需要从维度的数值大小中体现差异的分析，如使用用户行为指标分析用户价值的相似度或差异；而余弦相似度更多的是从方向上区分差异，而对绝对的数值不敏感，更多的用于使用用户对内容评分来区分用户兴趣的相似度和差异，同时修正了用户间可能存在的度量标准不统一的问题(因为余弦相似度对绝对数值不敏感)。
因为欧几里得距离度量会受指标不同单位刻度的影响，所以一般需要先进行标准化，同时距离越大，个体间差异越大；空间向量余弦夹角的相似度度量不会受指标刻度的影响，余弦值落于区间[-1,1]，值越大，差异越小。但是针对具体应用，什么情况下使用欧氏距离，什么情况下使用余弦相似度？
从几何意义上来说，n维向量空间的一条线段作为底边和原点组成的三角形，其顶角大小是不确定的。也就是说对于两条空间向量，即使两点距离一定，他们的夹角余弦值也可以随意变化。感性的认识，当两用户评分趋势一致时，但是评分值差距很大，余弦相似度倾向给出更优解。举个极端的例子，两用户只对两件商品评分，向量分别为(3,3)和(5,5)，这两位用户的认知其实是一样的，但是欧式距离给出的解显然没有余弦值合理。
我们把机器学习定义为对系统的设计和学习，通过对经验数据的学习，将任务效果的不断改善作为一个度量标准。Kmeans是一种非监督学习，没有标签和其他信息来比较聚类结果。但是，我们还是有一些指标可以评估算法的性能。我们已经介绍过类的畸变程度的度量方法。本节为将介绍另一种聚类算法效果评估方法称为轮廓系数(Silhouette Coefficient)。轮廓系数是类的密集与分散程度的评价指标。它会随着类的规模增大而增大。彼此相距很远，本身很密集的类，其轮廓系数较大，彼此集中，本身很大的类，其轮廓系数较小。轮廓系数是通过所有样本计算出来的，计算每个样本分数的均值，计算公式如下：
aa是每一个类中样本彼此距离的均值，bb是一个类中样本与其最近的那个类的所有样本的距离的均值。
输入：聚类个数k，数据集XmxnXmxn。
输出：满足方差最小标准的k个聚类。
(1) 选择k个初始中心点，例如c[0]=X[0] , … , c[k-1]=X[k-1]；
(2) 对于X[0]….X[n]，分别与c[0]…c[k-1]比较，假定与c[i]差值最少，就标记为i；
(3) 对于所有标记为i点，重新计算c[i]={ 所有标记为i的样本的每个特征的均值}；
(4) 重复(2)(3)，直到所有c[i]值的变化小于给定阈值或者达到最大迭代次数。
Kmeans的时间复杂度：O(tkmn)，空间复杂度：O((m+k)n)。其中，t为迭代次数，k为簇的数目，m为样本数，n为特征数。
7.1 优点
(1). 算法原理简单。需要调节的超参数就是一个k。
(2). 由具有出色的速度和良好的可扩展性。
7.2 缺点
(1). 在 Kmeans 算法中 kk 需要事先确定，这个 kk 值的选定有时候是比较难确定。
(2). 在 Kmeans 算法中，首先需要初始k个聚类中心，然后以此来确定一个初始划分，然后对初始划分进行优化。这个初始聚类中心的选择对聚类结果有较大的影响，一旦初始值选择的不好，可能无法得到有效的聚类结果。多设置一些不同的初值，对比最后的运算结果，一直到结果趋于稳定结束。
(3). 该算法需要不断地进行样本分类调整，不断地计算调整后的新的聚类中心，因此当数据量非常大时，算法的时间开销是非常大的。
(4). 对离群点很敏感。
(5). 从数据表示角度来说，在 Kmeans 中,我们用单个点来对 cluster 进行建模，这实际上是一种最简化的数据建模形式。这种用点来对 cluster 进行建模实际上就已经假设了各 cluster的数据是呈圆形(或者高维球形)或者方形等分布的。不能发现非凸形状的簇。但在实际生活中，很少能有这种情况。所以在 GMM 中，使用了一种更加一般的数据表示，也就是高斯分布。
(6). 从数据先验的角度来说，在 Kmeans 中,我们假设各个 cluster 的先验概率是一样的,但是各个 cluster 的数据量可能是不均匀的。举个例子,cluster A 中包含了10000个样本,cluster B 中只包含了100个。那么对于一个新的样本,在不考虑其与A cluster、 B cluster 相似度的情况,其属于 cluster A 的概率肯定是要大于 cluster B的。
(7). 在 Kmeans 中，通常采用欧氏距离来衡量样本与各个 cluster 的相似度。这种距离实际上假设了数据的各个维度对于相似度的衡量作用是一样的。但在 GMM 中，相似度的衡量使用的是后验概率 αcG(x|μc,∑c)αcG(x|μc,∑c) ，通过引入协方差矩阵,我们就可以对各维度数据的不同重要性进行建模。
(8). 在 Kmeans 中，各个样本点只属于与其相似度最高的那个 cluster ，这实际上是一种 hard clustering 。
针对Kmeans算法的缺点，很多前辈提出了一些改进的算法。例如 K-modes 算法，实现对离散数据的快速聚类，保留了Kmeans算法的效率同时将Kmeans的应用范围扩大到离散数据。还有K-Prototype算法，可以对离散与数值属性两种混合的数据进行聚类，在K-prototype中定义了一个对数值与离散属性都计算的相异性度量标准。当然还有其它的一些算法，这里我 就不一一列举了。
Kmeans 与 GMM 更像是一种 top-down 的思想，它们首先要解决的问题是，确定 cluster 数量，也就是 k 的取值。在确定了 k 后,再来进行数据的聚类。而 hierarchical clustering 则是一种 bottom-up 的形式，先有数据，然后通过不断选取最相似的数据进行聚类。
3. 聚类算法--KMeans
与分类、序列标注等任务不同，聚类是在事先并不知道任何样本标签的情况下，通过数据之间的内在关系把样本划分为若干类别，使得同类别样本之间的相似度高，不同类别之间的样本相似度低(即增大类内聚，减少类间距)。
聚类属于非监督学习，K均值聚类是最基础常用的聚类算法。它的基本思想是，通过迭代寻找K个簇(Cluster)的一种划分方案，使得聚类结果对应的损失函数最小。其中，损失函数可以定义为各个样本距离所属簇中心点的误差平方和。
其中 代表第i个样本， 是 所属的簇， 代表簇对应的中心点，M是样本总数。
相关概念：
K值： 要得到的簇的个数。
质心： 每个簇的均值向量。即向量各维取平均即可。
距离量度： 常用欧几里得距离和余弦相似度(先标准化)。
KMeans的主要思想是：在给定K值和K个初始类簇中心点的情况下，把每个点(亦即数据记录)分到离其最近的类簇中心点所代表的类簇中，所有点分配完毕之后，根据一个类簇内的所有点重新计算该类簇的中心点(取平均值)，然后再迭代的进行分配点和更新类簇中心点的步骤，直至类簇中心点的变化很小，或者达到指定的迭代次数。
KMeans的核心目标是将给定的数据集划分成K个簇(K是超餐)，并给出每个样本数据对应的中心点。具体步骤非常简单：
（1）首先确定一个K值，即我们希望将数据集经过聚类得到k个集合。
（2）从数据集中随机选择K个数据点作为质心。
（3）对数据集中每一个点，计算其与每一个质心的距离(如欧式距离)，离哪个质心近，就划分到哪个质心所属的集合。
（4）把所有数据归好集合后，一共有K个集合。然后重新计算每个集合的质心。
（5）如果新计算出来的质心和原来的质心之间的距离小于某一个设置的阈值(表示重新计算的质心的位置变化不大，趋于稳定，或者说收敛)，我们可以认为聚类已经达到期望的结果，算法终止。
（6）如果新质心和原质心距离变化很大，需要迭代3-5步骤。
KMeans最核心的部分是先固定中心点，调整每个样本所属的类别来减少J；再固定每个样本的类别，调整中心点继续减小J。两个过程交替循环，J单调递减直到极小值，中心点和样本划分的类别同时收敛。
KMeans的优点 ：
高效可伸缩，计算复杂度为O(NKt)接近于线性(N是数据量，K是聚类总数，t是迭代轮数)。
收敛速度快，原理相对通俗易懂，可解释性强。
当结果簇是密集的，而簇与簇之间区别是明显时，他的效果较好。主要需要调参的参数仅仅是簇数K。
缺点 ：
受初始值和异常点影响，聚类结果可能不是全局最优而是局部最优。K-Means算法对初始选取的质心点是敏感的，不同的随机种子点得到的聚类结果完全不同，对结果影响很大。
K是超参数，一般需要按经验选择。
对噪音和异常点比较的敏感，用来检测异常值。
只能发现球状的簇。在K-Means中，我们用单个点对cluster进行建模，这实际上假设各个cluster的数据是呈高维球型分布的，但是在生活中出现这种情况的概率并不算高。例如，每一个cluster是一个一个的长条状的，K-Means的则根本识别不出来这种类别( 这种情况可以用GMM )。实际上，K-Means是在做凸优化，因此处理不了非凸的分布。
根据以上特点，我们可以从下面几个角度对算法做调优。
（1）数据预处理：归一化和异常点过滤
KMeans本质是一种基于欧式距离度量的数据划分方法，均值和方差大的维度将对数据的聚类结果产生决定性影响 。所以在聚类前对数据( 具体的说是每一个维度的特征 )做归一化和单位统一至关重要。此外，异常值会对均值计算产生较大影响，导致 中心偏移 ，这些噪声点最好能提前过滤。
（2）合理选择K值
K值的选择一般基于实验和多次实验结果。例如采用 手肘法 ，尝试不同K值并将对应的损失函数画成折线。手肘法认为图上的 拐点就是K的最佳值 (k=3)。
为了将寻找最佳K值的过程自动化，研究人员提出了Gap Statistic方法。不需要人们用肉眼判断，只需要找到最大的Gap Statistic对应的K即可。
损失函数记为 ，当分为K类时，Gap Statistic定义为： 。 是 的期望 ，一般由蒙特卡洛模拟产生。我们在样本所在的区域内按照均匀分布随机地产生和原始样本数一样多的随机样本，并对这个随机样本做KMeans，得到一个 ，重复多次就可以计算出 的近似值。
的物理含义是随机样本的损失与实际样本的损失之差。Gap越大说明聚类的效果越好 。一种极端情况是，随着K的变化 几乎维持一条直线保持不变。说明这些样本间没有明显的类别关系，数据分布几乎和均匀分布一致，近似随机。此时做聚类没有意义。
（3）改进初始值的选择
之前我们采用随机选择K个中心的做法，可能导致不同的中心点距离很近，就需要更多的迭代次数才能收敛。如果在选择初始中心点时能 让不同的中心尽可能远离 ，效果往往更好。这类算法中，以K-Means++算法最具影响力。
（4）采用核函数
主要思想是通过一个非线性映射，将输入空间中的数据点映射到高维的特征空间中，并在新的空间进行聚类。非线性映射增加了数据点线性可分的概率(与SVM中使用核函数思想类似)对于非凸的数据分布可以达到更为准确的聚类结果。
(1）初始的K个质心怎么选？
最常用的方法是随机选，初始质心的选取对最终聚类结果有影响，因此算法一定要多执行几次，哪个结果更合理，就用哪个结果。当然也有一些优化的方法，第一种是选择彼此距离最远的点，具体来说就是先选第一个点，然后选离第一个点最远的当第二个点，然后选第三个点，第三个点到第一、第二两点的距离之和最小，以此类推。第二种是先根据其他聚类算法(如层次聚类)得到聚类结果，从结果中每个分类选一个点
（2）关于离群值？
离群值就是远离整体的，非常异常、非常特殊的数据点，在聚类之前应该将这些"极大""极小"之类的离群数据都去掉，否则会对于聚类的结果有影响。但是，离散值往往自身就很有分析的价值，可以把离群值单独作为一类来分析。
（3）单位要一致！
（4）标准化
数据中X整体都比较小，比如都是1到10之间的数，Y很大，比如都是1000以上的数，那么在计算距离的时候Y起到的作用就比X大很多，X对于距离的影响几乎可以忽略，这也有问题。因此，如果K-Means聚类中选择欧几里得距离计算距离，数据集又出现了上面所述的情况，就一定要进行数据的标准化(normalization)，即将数据按比例缩放，使之落入一个小的特定区间。
K-Means是无监督学习的聚类算法，没有样本输出；而KNN是监督学习的分类算法，有对应的类别输出 。KNN基本不需要训练，对测试集里面的点，只需要找到在训练集中最近的K个点，用这最近的K个点的类别来决定测试点的类别。而K-Means则有明显的训练过程，找到K个类别的最佳质心，从而决定样本的簇类别。当然，两者也有一些相似点，两个算法都包含一个过程，即找出和某一个点最近的点。 两周都利用了最近邻的思想 。
4. 聚类分析：k-means和层次聚类
尽管我个人非常不喜欢人们被划分圈子，因为这样就有了歧视、偏见、排挤和矛盾，但“物以类聚，人以群分”确实是一种客观的现实——这其中就蕴含着聚类分析的思想。
前面所提到的机器学习算法主要都是 分类 和 回归 ，这两类的应用场景都很清晰，就是对分类型变量或者数值型变量的 预测 。 聚类分析 是一种根据样本之间的距离或者说是相似性（亲疏性），把越相似、差异越小的样本聚成一类（簇），最后形成多个簇，使同一个簇内部的样本相似度高，不同簇之间差异性高。
有人不理解 分类 和 聚类 的差别，其实这个很简单：分类是一个已知具体有几种情况的变量，预测它到底是哪种情况；聚类则是尽量把类似的样本聚在一起，不同的样本分开。举个例子，一个人你判断他是男是女这是分类，让男人站一排女人站一排这是聚类。
聚类分析算法很多，比较经典的有 k-means 和 层次聚类法 。
k-means的k就是最终聚集的簇数，这个要你事先自己指定。k-means在常见的机器学习算法中算是相当简单的，基本过程如下：
k-means的聚类过程演示如下：
k-means聚类分析的原理虽然简单，但缺点也比较明显：
值得一提的是，计算距离的方式有很多种，不一定非得是笛卡尔距离；计算距离前要归一化。
尽管k-means的原理很简单，然而层次聚类法的原理更简单。它的基本过程如下：
层次聚类不指定具体的簇数，而只关注簇之间的远近，最终会形成一个树形图。
通过这张树形图，无论想划分成几个簇都可以很快地划出。
以下以癌细胞细据为例，演示K-means和层次聚类法的过程。
可见选择不同的距离指标，最终的聚类效果也不同。其中最长距离和类平均距离用得比较多，因为产生的谱系图较为均衡。
图中一条红线将簇划分成4类，很容易看出哪些样本各属于哪一簇。
以上是层次聚类法的结果，但如果用k-means聚类的话，结果很可能就不一样了。
5. 聚类算法 - kmeans
kmeans即k均值算法。k均值聚类是最著名的划分聚类算法，由于简洁和效率使得他成为所有聚类算法中最广泛使用的。给定一个数据点集合和需要的聚类数目k，k由用户指定，k均值算法根据某个距离函数反复把数据分入k个聚类中。
简易动画过程在这， 传送门 第一步 ，输入k的值，即我们希望将数据集经过聚类得到k类，分为k组 第二步 ，从数据集中随机选择k个数据点作为初识的聚类中心（质心，Centroid） 第三步 ，对集合中每一个数据点，计算与每一个聚类中心的距离，离哪个中心距离近，就标记为哪个中心。待分配完全时，就有第一次分类。 第四步 ，每一个分类根据现有的数据重新计算，并重新选取每个分类的中心（质心） 第五至N步 ，重复第三至四步，直至符合条件结束迭代步骤。条件是如果新中心和旧中心之间的距离小于某一个设置的阈值（表示重新计算的质心的位置变化不大，趋于稳定，或者说收敛），可以认为我们进行的聚类已经达到期望的结果，终止迭代过程。
该算法的核心就是选择合适的k值，不同的k值出来有不同的结果。
手肘法的核心指标是SSE(sum of the squared errors，误差平方和)，
其中，Ci是第i个簇，p是Ci中的样本点，mi是Ci的质心（Ci中所有样本的均值），SSE是所有样本的聚类误差，代表了聚类效果的好坏。
手肘法的核心思想是：随着聚类数k的增大，样本划分会更加精细，每个簇的聚合程度会逐渐提高，那么误差平方和SSE自然会逐渐变小。并且，当k小于真实聚类数时，由于k的增大会大幅增加每个簇的聚合程度，故SSE的下降幅度会很大，而当k到达真实聚类数时，再增加k所得到的聚合程度回报会迅速变小，所以SSE的下降幅度会骤减，然后随着k值的继续增大而趋于平缓，也就是说SSE和k的关系图是一个手肘的形状，而这个肘部对应的k值就是数据的真实聚类数。当然，这也是该方法被称为手肘法的原因。
该方法的核心指标是轮廓系数（Silhouette Coefficient），某个样本点Xi的轮廓系数定义如下：
其中，a是Xi与同簇的其他样本的平均距离，称为凝聚度，b是Xi与最近簇中所有样本的平均距离，称为分离度。而最近簇的定义是
其中p是某个簇Ck中的样本。事实上，简单点讲，就是用Xi到某个簇所有样本平均距离作为衡量该点到该簇的距离后，选择离Xi最近的一个簇作为最近簇。
求出所有样本的轮廓系数后再求平均值就得到了 平均轮廓系数 。平均轮廓系数的取值范围为[-1,1]，且簇内样本的距离越近，簇间样本距离越远，平均轮廓系数越大，聚类效果越好。那么，很自然地，平均轮廓系数最大的k便是最佳聚类数。
（1）容易理解，聚类效果不错，虽然是局部最优， 但往往局部最优就够了 （2）处理大数据集的时候，该算法可以保证较好的伸缩性 （3）当簇近似高斯分布的时候，效果非常不错 （4）算法复杂度低
（1）K 值需要人为设定，不同 K 值得到的结果不一样 （2）对初始的簇中心敏感，不同选取方式会得到不同结果 （3）对异常值敏感 （4）样本只能归为一类，不适合多分类任务 （5）不适合太离散的分类、样本类别不平衡的分类、非凸形状的分类
6. 关于k-means算法的聚类分析
7. K-means聚类分析案例（二）
之前的笔记： 聚类介绍： 点这里 层次聚类分析案例（一）：世界银行样本数据集 层次聚类分析案例（二）：亚马逊雨林烧毁情况 层次聚类分析案例（三）：基因聚类 K-means聚类分析案例（一）
K-means聚类案例（二）食品
我们所吃的食物中的营养成分可以根据它们在构建身体构成的作用来分类。这些营养元素可分为宏量营养元素和微量元素。一些宏量营养元素包括碳水化合物、蛋白质、脂肪，一些微量元素的例子是维生素、矿物质和水。
准备工作
让我们从准备数据开始。
第1步：收集和描述数据
为了应用k均值聚类，我们使用采自不同食物种类的数据集进行实验，其中包含了每种食物各自的能量（Energy）、蛋白质（Protein）、脂肪（Fat）、钙（Calcium）、铁（Iron）等含量。 数据获取
其中数值型变量如下： Energy Protein Fat Calcium Iron 非数值型变量如下： Food
具体实施步骤 以下为实现细节。
第2步：探索数据
载入cluster（）库。
探索数据并理解数据变量间的关系。从导入名为foodstuffs.txt的文本文件开始，将其保存在food.energycontent数据框中。
head（）函数返回向量、矩阵、表、数据框或函数的首尾部分。将food.energycontent数据框传入head（）函数：
结果如下：
str（）函数返回food.energycontent数据框的结构信息。结果简洁地显示了其内部结构。
str(food.energycontent)
结果如下：
第3步：转换数据
apply（）函数执行了数据框和矩阵中逐个元素的数据变换。它返回一个向量、数组、链表，其中的值是通过应用一个函数到一个数组或矩阵的边缘。其中2代表了函数要应用的列下标。sd是标准差函数，用于这个数据框。
结果如下：
sweep（）函数返回一个数组，从一个输入数组中清除一些统计信息。food.energycontent[，-1]作为一个数组传入。其中2代表了函数要应用的列下标。standard.deviation是需要被清除的统计信息。
结果如下：
第4步：聚类
kmeans（）函数施行k均值聚类到数据矩阵上。数据矩阵foodergycnt.stddev被当作一个对象传入，该对象是一个数值型矩阵。centers＝5代表初始的簇中心数量。iter.max=100代表最大的迭代轮数。因为簇数量由一个数字指定，nstart＝25定义了随机被指定的组数量。
结果如下：
指定4个中心簇：
结果如下：
输出4个簇的聚类向量，结果如下：
接下来，输出4个聚类方案的聚类以及食品标签。
lapply（）函数返回一个与X同样长度的链表：
结果如下：
第5步：可视化聚类结果
使用pair（）函数生成一个散点图矩阵。
food.energycontent[，-1]通过给定一个矩阵或数据框的数值来提供点的坐标。
结果如下：
princomp（）函数在给定数值型数据矩阵上进行主成分分析。该函数产生了非旋转的主成分分析结果。cor＝T代表一个逻辑值，指明了计算需要使用相关矩阵。
par（）函数整合多个绘图结果到一个统一的图中。s产生一个正方形绘图区域。
par(pty="s")
绘制这个聚类：
结果如下：
8. K-means聚类分析案例（一）
之前的笔记： 聚类介绍： 点这里 层次聚类分析案例（一）：世界银行样本数据集 层次聚类分析案例（二）：亚马逊雨林烧毁情况 层次聚类分析案例（三）：基因聚类
食品消费模式是医学和营养学领域关注的一大热点。食物消费与个人的整体健康、食物的营养价值、购买食品的经济性和消费环境有关。这项分析涉及25个欧洲国家肉类和其他食品之间的关系。观察肉类和其他食品的相关性是很有意思的。这些数据包括：红肉、白肉、蛋类、牛奶、鱼类、谷类、淀粉类食品、坚果（包括豆类和油籽）、水果和蔬菜。
准备工作
为了应用k均值聚类，我们使用欧洲25个国家的蛋白质消费量数据集。
第1步：收集和描述数据
该任务使用名为protein的数据集，该数据集以标准格式存储在CSV格式的文件中，其中包含25行数据和10个变量。 数据获取路径
数值型变量如下： RedMeat WhiteMeat Eggs Milk Fish Cereals Starch Nuts Fr&Veg 非数值型变量如下： Country 具体实施步骤 以下为实现细节。
第2步：探索数据
让我们探索数据并理解变量间的关系。从导入名为Europenaprotein.csv的CSV文件开始，将该数据保存到protein数据框：
head（）函数返回了一个向量、矩阵、表、数据框或函数首或尾的部分。将protein数据框传入head（）函数。
结果如下：
第3步：聚类
开始在三个簇的基础上进行聚类。为了在初始阶段产生随机的簇数量，调用set.seed（）函数。set.seed（）函数能够产生随机数。
kmeans（）函数能够在数据矩阵上执行k均值聚类。protein数据矩阵被当作一个对象传入该函数，该对象必须是数值型矩阵。centers＝3代表初始化簇中心数量。因为簇的数量由一个数字指定，nstart＝10定义了随机被选择的中心数。
结果如下：
接下来，生成簇指派列表。order（）函数返回一个序列，以升序或者降序重新生成它的第一个参数。groupMeat数据框被当作一个数据框对象传入：
调用data.frame（）函数，显示了国家和这些国家所处的簇：
结果如下：
plot（）函数是一个绘制R对象的通用函数。参数类型指明了要被显示的图的种类。xlim参数的意思是参数应该被给定范围的边界，而不是一个范围。xlab和ylab提供了x轴和y轴各自的标题：
结果如下：
第4步：改进模型
接下来，在所有9个蛋白质组上进行聚类，并且7个簇已经被创建了。在散点图上不同颜色的点代表了吃白肉和红肉的国家。地理上临近的国家倾向于分到同一组。
center＝7代表初始的聚类中心数量：
7个不同的聚类形成了。25个国家都一一被分配到了某一个簇中。
结果如下：
clustplot（）函数创造了一个二变量的图，其中可以看到数据的可视化划分。所有观测值使用主成分以点的方式表示。在每个簇周围绘制椭圆形。protein数据框被当作对象传入：
结果如下：
另一个层次化形式展现的方法如下。这里使用agnes（）函数。通过设置diss＝FALSE，不相似度矩阵被用来计算原始数据。metric="euclidean"表明使用欧氏距离进行计算：
结果如下：
plot()画出图形：按回车可查看下一章图，共两张图。
结果如下：
cutree（）函数切割树到几个组中，通过设定期望的组数量或者切割的高度来进行划分：
结果如下：
结果如下：
最新文章
热门文章
推荐阅读