K-Means 聚类原理
2024-05-16 22:33
1. K-Means 聚类原理
K-Means 是聚类算法中的最常用的一种，算法最大的特点是简单，好理解，运算速度快，但是只能应用于连续型的数据，并且一定要在聚类前需要手工指定要分成几类。
假设有一些点分散在直线上，现在需要对这些点进行聚类分析。
第一步，想一下我们希望最终将这些点聚为多少类？
假设我们希望聚为3类
第二步，在这些点中随机选择3个点，作为初始簇(initial cluster)
第三步，计算第一个点f分别到这3个initial cluster的距离
第四步，将第一个点归属为距离最近的那个cluster
重复第三/四步
一一判断所有点的归属
第五步，计算每一个cluster的均值
然后像之前一样，通过计算每个点到这些均值的距离，重新判断每个点归属于哪个cluster
判断完每个点的归属之后，重新计算均值……判断归属……计算均值……判断归属……直到聚出来的cluster不再变化
很明显，上面的聚类效果很差，还不如我们肉眼聚类出来的效果。是否有办法判断不同聚类结果的好坏呢？
第一步，计算每一个cluster的总变差(total variation)
第二步，重新选择3个initial cluster，并且多次迭代判断cluster，计算total variation
第三步，多次重复上一步的内容，选择total variation最小的聚类结果
在本文的案例中，我们通过肉眼可以判断出K选择3比较好。但是如果我们自己无法判断时，如何处理？
一种方法是直接尝试不同的K值进行聚类
K=1是最差的一种结果，total variation此时最大
K=2的效果会稍微好些
随着K值增大，total variation也逐渐减小；当K=N(样本数)时，total variation降至0。
绘制total variation随K值变化的elbow plot
可以看出，K>3时，variation的降低速率明显降低。所以K=3是较好的选择。
二维平面上的点，可以通过欧式距离来判断聚类
然后同之前一般，计算平面上同一cluster的中心，重新判断点的归属，寻找中心……判断归属……
对于热图相关数据，也可以通过欧式距离来判断样本的聚类
https://blog.csdn.net/huangfei711/article/details/78480078
https://www.biaodianfu.com/k-means-choose-k.html
https://www.youtube.com/watch?v=4b5d3muPQmA&feature=youtu.be
2. 分层聚类和K-means聚类
hierarchical clustering： 分层聚类通过连续不断地将最为相似的群组两两合并，来构造出一个群组的层级结构。其中的每个群组都是从单一元素开始的。在每次迭代的过程中，分层聚类算法会计算每两个群组间的距离，并将距离最近的两个群组合并成一个新的群组。这一过程会一直重复下去，直至只剩一个群组为止。 来源参考： https://blog.csdn.net/sysu_xiamengyou/article/details/68524182
K-means聚类： k-means聚类算法不同于分级聚类算法，它会预先告诉算法希望生成的聚类数量，然后算法会根据数据的结构状况来确定聚类的大小。 与分级聚类相比，该算法产生最终结果所需的迭代次数是非常少的，由于函数选用随机数来生成中心点进行聚类，那么可以想象其实每次聚类所产生的顺序几乎是不同的，根据中心点位置的不同，最终聚类所包含的内容可能也会有所不同。 来源参考： https://blog.csdn.net/sysu_xiamengyou/article/details/68941900
3. K-Means聚类算法原理是怎么样的？
一，K-Means聚类算法原理
k-means 算法接受参数 k
；然后将事先输入的n个数据对象划分为
k个聚类以便使得所获得的聚类满足：同一聚类中的对象相似度较高；而不同聚类中的对象相似度较小。聚类相似度是利用各聚类中对象的均值所获得一个“中心对
象”（引力中心）来进行计算的。
K-means算法是最为经典的基于划分的聚类方法，是十大经典数据挖掘算法之一。K-means算法的基本思想是：以空间中k个点为中心进行聚类，对最靠近他们的对象归类。通过迭代的方法，逐次更新各聚类中心的值，直至得到最好的聚类结果。
假设要把样本集分为c个类别，算法描述如下：
（1）适当选择c个类的初始中心；
（2）在第k次迭代中，对任意一个样本，求其到c个中心的距离，将该样本归到距离最短的中心所在的类；
（3）利用均值等方法更新该类的中心值；
（4）对于所有的c个聚类中心，如果利用（2）（3）的迭代法更新后，值保持不变，则迭代结束，否则继续迭代。
该算法的最大优势在于简洁和快速。算法的关键在于初始中心的选择和距离公式。
4. 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
来源：
5. K-Means聚类算法
所谓聚类算法是指将一堆没有标签的数据自动划分成几类的方法，属于无监督学习方法，这个方法要保证同一类的数据有相似的特征，如下图所示：
根据样本之间的距离或者说是相似性（亲疏性），把越相似、差异越小的样本聚成一类（簇），最后形成多个簇，使同一个簇内部的样本相似度高，不同簇之间差异性高。
相关概念：
K值 ：要得到的簇的个数
质心 ：每个簇的均值向量，即向量各维取平均即可
距离量度 ：常用欧几里得距离和余弦相似度（先标准化）
算法流程：
1、首先确定一个k值，即我们希望将数据集经过聚类得到k个集合。
2、从数据集中随机选择k个数据点作为质心。
3、对数据集中每一个点，计算其与每一个质心的距离（如欧式距离），离哪个质心近，就划分到那个质心所属的集合。
4、把所有数据归好集合后，一共有k个集合。然后重新计算每个集合的质心。
5、如果新计算出来的质心和原来的质心之间的距离小于某一个设置的阈值（表示重新计算的质心的位置变化不大，趋于稳定，或者说收敛），我们可以认为聚类已经达到期望的结果，算法终止。
6、如果新质心和原质心距离变化很大，需要迭代3~5步骤。
K-Means采用的启发式方式很简单，用下面一组图就可以形象的描述:
上图a表达了初始的数据集，假设k=2。在图b中，我们随机选择了两个k类所对应的类别质心，即图中的红色质心和蓝色质心，然后分别求样本中所有点到这两个质心的距离，并标记每个样本的类别为和该样本距离最小的质心的类别，如图c所示，经过计算样本和红色质心和蓝色质心的距离，我们得到了所有样本点的第一轮迭代后的类别。此时我们对我们当前标记为红色和蓝色的点分别求其新的质心，如图d所示，新的红色质心和蓝色质心的位置已经发生了变动。图e和图f重复了我们在图c和图d的过程，即将所有点的类别标记为距离最近的质心的类别并求新的质心。最终我们得到的两个类别如图f。
坐标系中有六个点：
1、我们分两组，令K等于2，我们随机选择两个点：P1和P2
2、通过勾股定理计算剩余点分别到这两个点的距离：
3、第一次分组后结果：
组A：P1
组B：P2、P3、P4、P5、P6
4、分别计算A组和B组的质心：
A组质心还是P1=（0，0）
B组新的质心坐标为：P哥=（（1+3+8+9+10）/5，（2+1+8+10+7）/5）=（6.2，5.6）
5、再次计算每个点到质心的距离：
6、第二次分组结果：
组A：P1、P2、P3
组B：P4、P5、P6
7、再次计算质心：
P哥1=（1.33，1）
P哥2=（9，8.33）
8、再次计算每个点到质心的距离：
9、第三次分组结果：
组A：P1、P2、P3
组B：P4、P5、P6
可以发现，第三次分组结果和第二次分组结果一致，说明已经收敛，聚类结束。
优点：
1、原理比较简单，实现也是很容易，收敛速度快。
2、当结果簇是密集的，而簇与簇之间区别明显时, 它的效果较好。
3、主要需要调参的参数仅仅是簇数k。
缺点：
1、K值需要预先给定，很多情况下K值的估计是非常困难的。
2、K-Means算法对初始选取的质心点是敏感的，不同的随机种子点得到的聚类结果完全不同 ，对结果影响很大。
3、对噪音和异常点比较的敏感。用来检测异常值。
4、采用迭代方法， 可能只能得到局部的最优解，而无法得到全局的最优解 。
1、K值怎么定？
答：分几类主要取决于个人的经验与感觉，通常的做法是多尝试几个K值，看分成几类的结果更好解释，更符合分析目的等。或者可以把各种K值算出的 E 做比较，取最小的 E 的K值。
2、初始的K个质心怎么选？
答：最常用的方法是随机选，初始质心的选取对最终聚类结果有影响，因此算法一定要多执行几次，哪个结果更reasonable，就用哪个结果。 当然也有一些优化的方法，第一种是选择彼此距离最远的点，具体来说就是先选第一个点，然后选离第一个点最远的当第二个点，然后选第三个点，第三个点到第一、第二两点的距离之和最小，以此类推。第二种是先根据其他聚类算法（如层次聚类）得到聚类结果，从结果中每个分类选一个点。
3、关于离群值？
答：离群值就是远离整体的，非常异常、非常特殊的数据点，在聚类之前应该将这些“极大”“极小”之类的离群数据都去掉，否则会对于聚类的结果有影响。但是，离群值往往自身就很有分析的价值，可以把离群值单独作为一类来分析。
4、单位要一致！
答：比如X的单位是米，Y也是米，那么距离算出来的单位还是米，是有意义的。但是如果X是米，Y是吨，用距离公式计算就会出现“米的平方”加上“吨的平方”再开平方，最后算出的东西没有数学意义，这就有问题了。
5、标准化
答：如果数据中X整体都比较小，比如都是1到10之间的数，Y很大，比如都是1000以上的数，那么，在计算距离的时候Y起到的作用就比X大很多，X对于距离的影响几乎可以忽略，这也有问题。因此，如果K-Means聚类中选择欧几里德距离计算距离，数据集又出现了上面所述的情况，就一定要进行数据的标准化（normalization），即将数据按比例缩放，使之落入一个小的特定区间。
参考文章： 聚类、K-Means、例子、细节
6. 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")
绘制这个聚类：
结果如下：
7. 聚类k-means++、k-means参数、Mini Batch K-Means
1.1 KMeans介绍
k-means 优缺点：
1.算法快速、简单;
2.对大数据集有较高的效率并且是可伸缩性的;
3.时间复杂度近于线性，而且适合挖掘大规模数据集。K-Means聚类算法的时间复杂度是O(n×k×t) ,其中n代表数据集中对象的数量，t代表着算法迭代的次数，k代表着簇的数目 。计算复杂度在最坏的情况下为 O(n^(k+2/p))，其中n是样本量，p是特征个数。
注 在实践中，k-means算法时非常快的，属于可实践的算法中最快的那一类。但是它的解只是由特定初始值所产生的局部解。所以为了让结果更准确真实，在实践中要用不同的初始值重复几次才可以。
k-means的缺点：
1、在 K-means 算法中 K 是事先给定的，这个 K 值的选定是非常难以估计的。很多时候，事先并不知道给定的数据集应该分成多少个类别才最合适。
2、 在 K-means 算法中，首先需要根据初始聚类中心来确定一个初始划分，然后对初始划分进行优化。这个初始聚类中心的选择对聚类结果有较大的影响，一旦初始值选择的不好，可能无法得到有效的聚类结果，这也成为 K-means算法的一个主要问题。
3、从 K-means 算法框架可以看出，该算法需要不断地进行样本分类调整，不断地计算调整后的新的聚类中心，因此当数据量非常大时，算法的时间开销是非常大的。所以需要对算法的时间复杂度进行分析、改进，提高算法应用范围。
对于上述的初始聚类中心的选择可以用**k-means++**来解决
1.2 KMeans() 参数
参数：
n_clusters：整形，缺省值=8 【生成的聚类数，即产生的质心（centroids）数。】
max_iter：整形，缺省值=300 ,执行一次k-means算法所进行的最大迭代数。
n_init：整形，缺省值=10 ,用不同的质心初始化值运行算法的次数，最终解是在inertia意义下选出的最优结果。
init：有三个可选值：’k-means++’， ‘random’，或者传递一个ndarray向量。
此参数指定初始化方法，默认值为 ‘k-means++’。
（1）‘k-means++’ 用一种特殊的方法选定初始质心从而能加速迭代过程的收敛（即上文中的k-means++介绍）
（2）‘random’ 随机从训练数据中选取初始质心。
（3）如果传递的是一个ndarray，则应该形如 (n_clusters, n_features) 并给出初始质心。
precompute_distances：三个可选值，‘auto’，True 或者 False。
预计算距离，计算速度更快但占用更多内存。
（1）‘auto’：如果 样本数乘以聚类数大于 12million 的话则不预计算距离。This corresponds to about 100MB overhead per job using double precision.
（2）True：总是预先计算距离。
（3）False：永远不预先计算距离。
tol：float形，默认值= 1e-4 与inertia结合来确定收敛条件。
n_jobs：整形数。 指定计算所用的进程数。内部原理是同时进行n_init指定次数的计算。
（1）若值为 -1，则用所有的CPU进行运算。若值为1，则不进行并行运算，这样的话方便调试。
（2）若值小于-1，则用到的CPU数为(n_cpus + 1 + n_jobs)。因此如果 n_jobs值为-2，则用到的CPU数为总CPU数减1。
random_state：整形或 numpy.RandomState 类型，可选
用于初始化质心的生成器（generator）。如果值为一个整数，则确定一个seed。此参数默认值为numpy的随机数生成器。
copy_x：布尔型，默认值=True
当我们precomputing distances时，将数据中心化会得到更准确的结果。如果把此参数值设为True，则原始数据不会被改变。如果是False，则会直接在原始数据 上做修改并在函数返回值时将其还原。但是在计算过程中由于有对数据均值的加减运算，所以数据返回后，原始数据和计算前可能会有细小差别。
属性：
cluster_centers_：向量，[n_clusters, n_features] (聚类中心的坐标)
Labels_: 每个点的分类
inertia_：float形 ,每个点到其簇的质心的距离之和。
Methods：
fit(X[,y]): 计算k-means聚类。
fit_predictt(X[,y]): 计算簇质心并给每个样本预测类别。
fit_transform(X[,y])： 计算簇并 transform X to cluster-distance space。
get_params([deep])： 取得估计器的参数。
predict(X):predict(X) 给每个样本估计最接近的簇。
score(X[,y]): 计算聚类误差
set_params(params): 为这个估计器手动设定参数。
transform(X[,y]): 将X转换为群集距离空间。 在新空间中，每个维度都是到集群中心的距离。 请注意，即使X是稀疏的，转换返回的数组通常也是密集的。
k-means++算法选择初始seeds的基本思想就是：初始的聚类中心之间的相互距离要尽可能的远。
2.1 算法步骤
（1）从输入的数据点集合中随机选择一个点作为第一个聚类中心
（2）对于数据集中的每一个点x，计算它与最近聚类中心(指已选择的聚类中心)的距离D(x)
（3）选择一个新的数据点作为新的聚类中心，选择的原则是：D(x)较大的点，被选取作为聚类中心的概率较大
（4）重复2和3直到k个聚类中心被选出来
（5）利用这k个初始的聚类中心来运行标准的k-means算法
从上面的算法描述上可以看到，算法的关键是第3步，如何将D(x)反映到点被选择的概率上，一种算法如下：
（1）先从我们的数据库随机挑个随机点当“种子点”
（2）对于每个点，我们都计算其和最近的一个“种子点”的距离D(x)并保存在一个数组里，然后把这些距离加起来得到Sum(D(x))。
（3）然后，再取一个随机值，用权重的方式来取计算下一个“种子点”。这个算法的实现是，先取一个能落在Sum(D(x))中的随机值Random，然后用Random -= D(x)，直到其<=0，此时的点就是下一个“种子点”。
（4）重复2和3直到k个聚类中心被选出来
（5）利用这k个初始的聚类中心来运行标准的k-means算法
可以看到算法的第三步选取新中心的方法，这样就能保证距离D(x)较大的点，会被选出来作为聚类中心了。
3.1 介绍
在统的K-Means算法中，要计算所有的样本点到所有的质心的距离。如果样本量非常大，比如达到10万以上，特征有100以上，此时用传统的K-Means算法非常的耗时，就算加上elkan K-Means优化也依旧。在大数据时代，这样的场景越来越多。此时Mini Batch K-Means应运而生。
顾名思义，Mini Batch，也就是用样本集中的一部分的样本来做传统的K-Means，这样可以避免样本量太大时的计算难题，算法收敛速度大大加快。当然此时的代价就是我们的聚类的精确度也会有一些降低。一般来说这个降低的幅度在可以接受的范围之内。
在Mini Batch K-Means中，我们会选择一个合适的批样本大小batch size，我们仅仅用batch size个样本来做K-Means聚类。那么这batch size个样本怎么来的？一般是通过无放回的随机采样得到的。
为了增加算法的准确性，我们一般会多跑几次Mini Batch K-Means算法，用得到不同的随机采样集来得到聚类簇，选择其中最优的聚类簇。
8. K-Means 聚类算法
问题导入
假如有这样一种情况，在一天你想去某个城市旅游，这个城市里你想去的有70个地方，现在你只有每一个地方的地址，这个地址列表很长，有70个位置。事先肯定要做好攻略，你要把一些比较接近的地方放在一起组成一组，这样就可以安排交通工具抵达这些组的“某个地址”，然后步行到每个组内的地址。那么，如何确定这些组，如何确定这些组的“某个地址”？答案就是聚类。而本文所提供的k-means聚类分析方法就可以用于解决这类问题。
一，聚类思想
所谓聚类算法是指将一堆没有标签的数据自动划分成几类的方法，属于无监督学习方法，这个方法要保证同一类的数据有相似的特征，如下图：
根据样本之间的距离或者说相似性，把越相似，差异越小的样本聚成一类（簇），最后形成多个簇，使同一个簇内部的样本相似度高，不同簇之间差异性高。
二，K-Means聚类分析算法
K-Means是一种基于自下而上的聚类分析方法，基本概念就是空间中有N个点，初始选择K个点作为中心聚类点，将N个点分别与K个点计算距离，选择自己最近的点作为自己的中心点，不断地更新中心聚集点。
相关概念：
K值：要得到的簇的个数
质心：每个簇的均值向量，即向量各维取品军即可
距离度量：常用欧几里得距离和余弦相似度(先标准化)
两点之间的距离：
算法流程：
1 首先确定一个K值，即我们希望将数据集经过聚类得到 K个集合；
2 从数据集中随机选择K个数据点作为质心；
3 对数据集中每一个点，计算其与每个质心的距离(如欧式距离)，离哪个质心近，就划分到哪个质心所属的集合
4 把所有数据归好集合，一共有K个集合，然后重新计算每个集合的质心；
5 如果新计算出来的质心和原来的质心之间的距离小于某一个设置的阈值(表示重新计算的质心的位置变化不大，趋于稳定，或者说收敛)，我们可以认为聚类已经达到期望的结果，算法终止。
6 如果新质心和原质心距离变化大，需要迭代3-5步骤
K-means实现过程
K-means 聚类算法是一种非监督学习算法，被用于非标签数据（data without defined categories or groups）。该算法使用迭代细化来产生最终结果。算法输入的是集群的数量 K 和数据集。数据集是每个数据点的一组功能。
算法从 Κ 质心的初始估计开始，其可以随机生成或从数据集中随机选择 。然后算法在下面两个步骤之间迭代：
1.数据分配：
每个质心定义一个集群。在此步骤中，基于平方欧氏距离将每个数据点分配到其最近的质心。更正式一点， ci 属于质心集合 C ，然后每个数据点 x 基于下面的公式被分配到一个集群中。
其中 dist（·）是标准（L2）欧氏距离。让指向第 i 个集群质心的数据点集合定为 Si 。
2. 质心更新：
在此步骤中，重新计算质心。这是通过获取分配给该质心集群的所有数据点的平均值来完成的。公式如下：
K-means 算法在步骤 1 和步骤 2 之间迭代，直到满足停止条件（即，没有数据点改变集群，距离的总和最小化，或者达到一些最大迭代次数）。
K 值的选择
上述算法找到特定预选 K 值和数据集标签。为了找到数据中的集群数，用户需要针对一系列 K 值运行 K-means 聚类算法并比较结果。通常，没有用于确定 K 的精确值的方法，但是可以使用以下技术获得准确的估计。
Elbow point 拐点方法
通常用于比较不同 K 值的结果的度量之一是数据点与其聚类质心之间的平均距离。由于增加集群的数量将总是减少到数据点的距离，因此当 K 与数据点的数量相同时，增加 K 将总是减小该度量，达到零的极值。因此，该指标不能用作唯一目标。相反，绘制了作为 K 到质心的平均距离的函数，并且可以使用减小率急剧变化的“拐点”来粗略地确定 K 。
DBI（Davies-Bouldin Index）
DBI 是一种评估度量的聚类算法的指标，通常用于评估 K-means 算法中 k 的取值。简单的理解就是：DBI 是聚类内的距离与聚类外的距离的比值。所以，DBI 的数值越小，表示分散程度越低，聚类效果越好。
还存在许多用于验证 K 的其他技术，包括交叉验证，信息标准，信息理论跳跃方法，轮廓方法和 G 均值算法等等。
三，数学原理
K-Means采用的启发式很简单，可以用下面一组图来形象的描述：
上述a表达了初始的数据集，假设 k=2 。在图b中，我们随机选择了两个 k 类所对应的类别质点，即图中的红色质点和蓝色质点，然后分别求样本中所有点到这两个质心的距离，并标记每个样本类别为和该样本距离最小的质心的类别，如图c所示，经过计算样本和红色质心和蓝色质心的距离，我们得到了所有样本点的第一轮迭代后的类别。此时我们对我们当前标记为红色和蓝色的点分别求其新的质心，如图d所示，新的红色质心和蓝色质心大热位置已经发生了变化。图e和图f重复了我们在图c和图d的过程，即将所有点的类别标记为距离最近的质心的类别并求出新的质心。最终我们得到的两个类别如图f.
四，实例
坐标系中有六个点：
1、我们分两组，令K等于2，我们随机选择两个点：P1和P2
2、通过勾股定理计算剩余点分别到这两个点的距离：
3、第一次分组后结果：
组A：P1
组B：P2、P3、P4、P5、P6
4、分别计算A组和B组的质心：
A组质心还是P1=（0，0）
B组新的质心坐标为：P哥=（（1+3+8+9+10）/5，（2+1+8+10+7）/5）=（6.2，5.6）
5、再次计算每个点到质心的距离：
6、第二次分组结果：
组A：P1、P2、P3
组B：P4、P5、P6
7、再次计算质心：
P哥1=（1.33，1）
P哥2=（9，8.33）
8、再次计算每个点到质心的距离：
9、第三次分组结果：
组A：P1、P2、P3
组B：P4、P5、P6
可以发现，第三次分组结果和第二次分组结果一致，说明已经收敛，聚类结束。
五、K-Means的优缺点
优点：
1、原理比较简单，实现也是很容易，收敛速度快。
2、当结果簇是密集的，而簇与簇之间区别明显时, 它的效果较好。
3、主要需要调参的参数仅仅是簇数k。
缺点：
1、K值需要预先给定，很多情况下K值的估计是非常困难的。
2、K-Means算法对初始选取的质心点是敏感的，不同的随机种子点得到的聚类结果完全不同 ，对结果影响很大。
3、对噪音和异常点比较的敏感。用来检测异常值。
4、采用迭代方法， 可能只能得到局部的最优解，而无法得到全局的最优解 。
六、细节问题
1、K值怎么定？
答：分几类主要取决于个人的经验与感觉，通常的做法是多尝试几个K值，看分成几类的结果更好解释，更符合分析目的等。或者可以把各种K值算出的 E 做比较，取最小的 E 的K值。
2、初始的K个质心怎么选？
答：最常用的方法是随机选，初始质心的选取对最终聚类结果有影响，因此算法一定要多执行几次，哪个结果更reasonable，就用哪个结果。 当然也有一些优化的方法，第一种是选择彼此距离最远的点，具体来说就是先选第一个点，然后选离第一个点最远的当第二个点，然后选第三个点，第三个点到第一、第二两点的距离之和最小，以此类推。第二种是先根据其他聚类算法（如层次聚类）得到聚类结果，从结果中每个分类选一个点。
3、关于离群值？
答：离群值就是远离整体的，非常异常、非常特殊的数据点，在聚类之前应该将这些“极大”“极小”之类的离群数据都去掉，否则会对于聚类的结果有影响。但是，离群值往往自身就很有分析的价值，可以把离群值单独作为一类来分析。
4、单位要一致！
答：比如X的单位是米，Y也是米，那么距离算出来的单位还是米，是有意义的。但是如果X是米，Y是吨，用距离公式计算就会出现“米的平方”加上“吨的平方”再开平方，最后算出的东西没有数学意义，这就有问题了。
5、标准化
答：如果数据中X整体都比较小，比如都是1到10之间的数，Y很大，比如都是1000以上的数，那么，在计算距离的时候Y起到的作用就比X大很多，X对于距离的影响几乎可以忽略，这也有问题。因此，如果K-Means聚类中选择欧几里德距离计算距离，数据集又出现了上面所述的情况，就一定要进行数据的标准化（normalization），即将数据按比例缩放，使之落入一个小的特定区间。
最新文章
热门文章
推荐阅读