作者：韩信子@ShowMeAI
教程地址：http://www.showmeai.tech/tutorials/34
本文地址：http://www.showmeai.tech/article-detail/197
声明：版权所有，转载请联系平台与作者并注明出处

---

引言

聚类（Clustering）是最常见的无监督学习算法，它指的是按照某个特定标准（如距离）把一个数据集分割成不同的类或簇，使得同一个簇内的数据对象的相似性尽可能大，同时不在同一个簇中的数据对象的差异性也尽可能地大。也即聚类后同一类的数据尽可能聚集到一起，不同类数据尽量分离。

聚类算法在很多场景下都有应用，例如新闻自动分组，用户分群，图像分割等等。很多时候，无监督的聚类算法，得到的聚类结果还可以作为特征在后续监督学习中应用，提升整体效果。本篇内容ShowMeAI带大家一起来学习一下聚类算法。

（本篇聚类算法部分内容涉及到机器学习基础知识，没有先序知识储备的宝宝可以查看ShowMeAI的文章 图解机器学习 | 机器学习基础知识。

1.聚类问题

1）聚类问题与核心概念

俗话说人以类聚物以群分，聚类算法做的事情，就是对无标签的数据，基于数据分布进行分群分组，使得相似的数据尽量落在同一个簇内。

我们先对比区分一下聚类和分类：

• 聚类是一种无监督学习，而分类是一种有监督的学习。
• 聚类只需要人工指定相似度的标准和类别数就可以，而分类需要从训练集学习分类的方法。

2）聚类算法用途

聚类算法应用非常广泛。在面对未知的世界时，先分类，再逐个研究，是人类探索未知世界的一个基本方法。聚类算法可以应用于探索性数据挖掘、统计分析、生物信息学、数据压缩、计算机图像识别、医学影像分析等，在商业领域可以用来做市场研究、商品归类，在社会科学领域可以用来做犯罪区域分析等等。

下图中有一些样本点，我们根据物理距离的远近，把所有的点分成3类。你只需要告诉算法这些信息，算法就可以按照你的要求完成聚类：

• 分类数量为3；
• 分类标准是物理距离；
• 分好的类分别用红、绿、蓝表示。

实际上，除了物理距离，现实生活中任何你能想到、计算机可以通过运算和逻辑进行判断的规则，都可以作为分类标准。

下面我们用图像压缩作为例子来解释一下。最左边是一张彩色照片，大小约1Mb，通过压缩可以把它变成几十到几百Kb，这就是压缩软件的实现过程。那么压缩软件的实现原理是什么呢？其中一种就是聚类算法。

从原始图片到压缩存储的过程如下图所示：

聚类算法同样可以用于图像分割。图像中每一个像素点是一个3维向量，对应 [R, G, B] 像素值。给定聚类中类别个数K，算法用K个不同的颜色来表示原来的图像，每个像素点用K个颜色中一个表示。具体如下：

对于文档、新闻、商品而言，很多时候我们会使用嵌套的归类方法，这是一种层次化聚类：

3）主流聚类算法

我们先对聚类算法做个了解，主流的聚类算法可以分成两类：划分聚类（Partitioning Clustering）和层次聚类（Hierarchical Clustering）。他们的主要区别如图中所示：

划分聚类算法会给出一系列扁平结构的簇（分开的几个类），它们之间没有任何显式的结构来表明彼此的关联性。

• 常见算法有 K-Means/K-Medoids、Gaussian Mixture Model （高斯混合模型）、Spectral Clustering（谱聚类）、Centroid-based Clustering等。

层次聚类会输出一个具有层次结构的簇集合，因此能够比划分聚类输出的无结构簇集合提供更丰富的信息。层次聚类可以认为是是嵌套的划分聚类。

• 常见算法有 Single-linkage、Complete-linkage、Connectivity-based Clustering等。

这两类算法在聚类过程中用到的具体算法不一样，后文我们会重点展开讲一下K-Means算法、Single-linkage算法和Complete-linkage算法。

2.K-Means聚类算法

K-Means算法是聚类算法中一个非常基础的算法，同时应用又非常广泛，下面ShowMeAI给大家展开讲解算法原理。

1）K-Means算法核心概念

我们提到了聚类算法要把n个数据点按照分布分成k类（很多算法的k是人为提前设定的）。我们希望通过聚类算法得到k个中心点，以及每个数据点属于哪个中心点的划分。

• 中心点可以通过迭代算法来找到，满足条件：所有的数据点到聚类中心的距离之和是最小的。

• 中心点确定后，每个数据点属于离它最近的中心点。

在进入「如何寻找中心点」这个核心问题之前，我们先解决几个小问题：

Q1：数据点到中心点的距离如何计算？

• 我们一般选择几何距离，就是L2距离的平方。

Q2：中心点是否唯一，或者说，是不是存在全局最优解？

• 对于多个中心点的情况，全局最优是一个相当难的问题。理论上存在一个全局最优解，但是不一定能找到。既然全局最优解不好找，那我们退而求其次，看能不能找到局部最优解。

Q3：聚类结果如何表示？

• 采用空间分割的方式：将空间分割成多个多边形，每个多边形对应一个cluster中心。

2）K-Means算法步骤

K-Means采用EM算法迭代确定中心点。流程分两步：

• ① 更新中心点：初始化的时候以随机取点作为起始点；迭代过程中，取同一类的所有数据点的重心（或质心）作为新中心点。

• ② 分配数据点：把所有的数据点分配到离它最近的中心点。

重复上面的两个步骤，一直到中心点不再改变为止。过程如图所示：

• 左侧Assignments：一开始随机选取三个点，作为三个类的中心，基于其它点和这三个中心点的距离分配簇；每一类重新计算和分配中心。

• 右侧Refitted Means：根据新的中心点，重新分配所有的数据点（原来属于绿色中心点的1个点，此次迭代后变成属于红色中心点了）。

下图的示例展示了K-Means动态迭代收敛的过程：

• 图（a）上有一群散落的点，我们设定簇数K=2。

• 图（b）为随机找2个点作为中心初始化后，第一次分类的结果。

  • 可以看到，红蓝分界线在这群点的中央穿过。这显然有问题，不过没关系，算法继续往下走。对红蓝两类分别计算它们的中心。

• 图（c）可以看到，一个落在左下方这一团里，另一个落在右上方那一团里。以新的中心点进行第二次分类。

• 图（d）的分界线就基本是已经可以把两团分开了。

• 图（f）、（g）显示后续重复计算你「中心点-分类数据点」的过程已经收敛，数据点分配基本不动了，聚类完成。

下方的动图能更清晰地展示这个过程：

3.K-Means缺点与改进

1）K-Means算法缺点

K-Means算法简单易用，它有什么缺点呢？我们将K-Means算法的一些缺点总结如下：

• 缺点1：中心点是所有同一类数据点的质心，所以聚类中心点可能不属于数据集的样本点。

• 缺点2：计算距离时我们用的是L2距离的平方。对离群点很敏感，噪声（Noisy Data）和离群点（Outlier）会把中心点拉偏，甚至改变分割线的位置。

2）K-Medoids算法

针对K-Means算法的缺点改进得到了K-Medoids算法：

（1）限制聚类中心点必须来自数据点。

• 求中心点的计算方法，由原来的直接计算重心，变成计算完重心后，在重心附近找一个数据点作为新的中心点。

• K-Medoids重拟合步骤比直接求平均的K-Means要复杂一些。

（2）为避免平方计算对离群点的敏感，把平方变成绝对值。

总结来说，K-Medoids算法的迭代过程与K-Means是一致的，不同点如下所示：

• 起始点不是随机点，而是任意选择数据集中的点。

• 距离使用L1距离，而不是L2距离。

• 新的中心点，也不是同类所有点的重心，而是同一类别所有数据点中，离其它点最近的点。

• 复杂度方面，相比于K-Means的 $O(n)$ ，K-Medoids更新中心点的复杂度 $O(n^2)$ 要更高一些。

下图是K-Means和K-Medoids两个算法的一个系统对比：

4.层次聚类算法

相比于K-Means这类划分聚类，我们有另外一类层次化聚类算法。

1）层次聚类vs划分聚类

划分聚类得到的是划分清晰的几个类，而层次聚类最后得到的是一个树状层次化结构。

从层次化聚类转换为划分聚类很简单，在层次化聚类的某一层进行切割，就得到1个划分聚类。如下图所示：

2）Single-Linkage 算法

接下来我们介绍一个层次聚类中的Single-Linkage算法。这个算法是构造一棵二叉树，用叶节点代表数据，而二叉树的每一个内部节点代表一个聚类。如图所示：

这是一个从下而上的聚类。这棵树是先有叶子，顺着叶子逐渐长树枝，树枝越长越大一直到树根。

如果叶子很多，这个生长过程需要合并的类就会很多。图中有11个数据点，一共发生了10次合并。

3）Complete-Linkage算法

与Single-Linkage算法相似，Complete-Linkage的迭代思路是一样的，不同的是在合并类时，Single-Linkage是用两个类中距离最小的两个点作为类之间的距离，而Complete-Linkage恰恰相反，用距离最远的两个数据点之间的距离作为这两个类之间的距离。

这两种计算方法各有利弊。总的来说，层次聚类的计算复杂度是 $O(n^3)$ 级别，算是很高的了。可以用优先队列的数据结构对算法加速，加速后能减低到 $O(n^2\log n)$ 的级别。

5.DB-SCAN算法

1）DB-SCAN算法

在前面的内容中我们介绍了划分聚类和层次聚类的算法，接下来我们学习另外一个聚类算法：DB-SCAN算法。

DB-SCAN是一个基于密度的聚类。如下图中这样不规则形态的点，如果用K-Means，效果不会很好。而通过DB-SCAN就可以很好地把在同一密度区域的点聚在一类中。

2）DB-SCAN算法的关键概念

核心对象（Core Object），也就是密度达到一定程度的点。

• 若$x_j$的$\in -$邻域至少包含MinPts个样本，即$|N_{\in }(x_j)|\ge MinPts$，则$x_j$是一个核心对象。

密度直达（directly density-reachable），密度可达（density-reachable）：核心对象之间可以是密度直达或者密度可达。

• 若$x_i$位于$x_j$的$\in -$邻域中，且$x_j$是核心对象，则称$x_j$由$x_j$密度直达。

• 对$x_i$与$x_j$，若存在样本序列$p_1,p_2,\dots ,p_n$，其中$p_1=x_i$，$p_n=x_j$且$p_i+1$由$p_i$密度直达，则称$x_j$由$x_i$密度可达。

密度相连（density-connected）：所有密度可达的核心点就构成密度相连。

• 对$x_i$与$x_j$，若存在$x_k$使得$x_i$与$x_j$，均由$x_k$密度可达，则称$x_i$与$x_j$密度相连。

我们通过下图深入理解一下刚才提到的几个基本概念。

先假设要求的最小点密度MinPts是3。

• 在一个半径范围内，$x_1$这个点周围的点数是5，超过了阈值3，所以$x_1$是一个核心对象。同样，$x_2$、$x_3$和$x_4$也是核心对象。

• $x_1$与$x_2$处于一个邻域，所以二者是密度直达的关系，而$x_3$与$x_2$也是密度直达的关系，通过$x_2$，$x_1$与$x_3$是密度可达的关系。

• $x_3$与$x_4$通过多个核心对象实现密度相连。

3）DB-SCAN算法伪代码

这个过程用直白的语言描述就是：

• 对于一个数据集，先规定最少点密度MinPts和半径范围。

• 先找出核心对象：如果在半径范围内点密度大于MinPts，则这个点是核心对象。把所有的核心对象放到一个集合中。

• 从这个核心对象集合中，随机找一个核心对象，判断其它的数据点与它是否密度直达，如果是，则归入聚类簇中。

• 继续判断其它点与聚类簇中的点是否密度直达，直到把所有的点都检查完毕，这时候归入聚类簇中的所有点是一个密度聚类。

更多无监督学习的算法模型总结可以查看ShowMeAI的文章 AI知识技能速查 | 机器学习-无监督学习。

视频教程

可以点击 B站 查看视频的【双语字幕】版本

【双语字幕+资料下载】MIT 6.036 | 机器学习导论(2020·完整版)

https://www.bilibili.com/video/BV1y44y187wN?p=13

ShowMeAI相关文章推荐

• 1.机器学习基础知识
• 2.模型评估方法与准则
• 3.KNN算法及其应用
• 4.逻辑回归算法详解
• 5.朴素贝叶斯算法详解
• 6.决策树模型详解
• 7.随机森林分类模型详解
• 8.回归树模型详解
• 9.GBDT模型详解
• 10.XGBoost模型最全解析
• 11.LightGBM模型详解
• 12.支持向量机模型详解
• 13.聚类算法详解
• 14.PCA降维算法详解

ShowMeAI系列教程推荐

• 图解Python编程：从入门到精通系列教程
• 图解数据分析：从入门到精通系列教程
• 图解AI数学基础：从入门到精通系列教程
• 图解大数据技术：从入门到精通系列教程
• 图解机器学习算法：从入门到精通系列教程

聚类简介

在“无监督学习”中，训练样本的标记信息是未知的，目标是通过对无标记训练样本的学习来揭示数据的内在性质及规律，为进一步的数据分析提供基础。此类学习任务中研究最多、应用最广的是“聚类”(clustering) 

聚类的目的是寻找一组一组相似的object，聚类希望类目内数据较近，类目之间的距离较远。

原型聚类：

• K-means （对噪声敏感）
  • 随机选取K个中心点
  • 将数据分配到与之接近的中心点
  • 使用数据均值去更新中心点，当中心点不再发生变化时停止
• 学习向量化
• 高斯混合聚类：使用概率模型来表示聚类效果

密度聚类（类似人眼分类）

• 核心对象：对象xj的ε−邻域中至少包含MinPts个样本Nε(xj)≥MinPts，则称xj为核心对象。
• 密度直达：若xj位于xi的ε−邻域中，且xi是核心对象，则称xj由xi密度直达。
• 密度可达：对xj与xi，存在样本序列p1,p2,...,pn且p1=xj,pn=xi,p1=xj,pn=xi 且pi+1由pi密度直达，则称xj由xi密度可达。
• 密度相连：对xj与xi，若存在xk使得xj与xi均由xk密度可达，则称xj由xi密度相连。

 DBSCAN将‘簇’定义为：由密度可达关系导出的最大的密度相连的集合。

层次聚类

层次聚类试图在不同层次对数据集进行划分，从而形成树形的聚类结构。数据集的划分可采用‘自底向上’的聚合策略，也可以采用‘自顶向下’的分拆策略。

AGNES是一种采用自底向上聚合策略的层次聚类算法。它将数据集中的每个样本看作一个初始聚类簇，然后算法运行的每一步找到距离最近的两个簇类进行合并，该过程不断重复，直到达到预设的聚类个数。这里的关键是如何计算聚类之间的距离，这里给出了三种距离。

最小距离：

最大距离：

平均距离：

 

Sklearn实现聚类

机器学习代码KMeans（聚类）

前言

我们之前遇到的所有机器学习算法都属于带标签的监督算法，而实现生活中大部分数据是不带标签的，从今天起我们要学一些处理不带标签数据的非监督算法，先从Kmeans聚类算法开始，我们将从以下几个方面来介绍Kmeans聚类算法

• 什么是聚类？
• 聚类与分类的区别
• Kmeans算法常用的距离公式
• Kmeans算法流程
• Kmeans算法实践
• Kmeans算法优缺点分析
• Kmeans算法应用场景

什么是聚类？

俗话说：“物以类聚，人以群分”，意思是说具有共同特质的人或物更容易聚集在一起，聚类算法正是依循这一客观规律，通过技术手段，将相似的研究对象聚集在同一个类里面，将相异的研究对象聚集在不同类里面，使得同一个类里面的研究对象具有极大的相似性，不同类的研究对象具有极大的差异性，聚类后的研究对象的内在结构就更加清楚明了。

聚类与分类的区别

聚类和分类看起来都是把一些样本分到相同或者不同的类，但是两者却有着本质区别，尤其是初学者对聚类和分类还是很难分清楚的，可以从以下几个方面来进行区分

(1) 目的

聚类的目的是要找出数据之间的相似性和相异性，在聚类之前并不清楚到底分多少类，也不清楚每个类里面包含哪些样本，甚至用什么方式方法来分也不确定，侧重总结归纳，而分类是在“分”之前就清楚知道总共有多少类，现在要确定新的样本到底属于哪个类，侧重预测。

(2) 操作

聚类是不需要利用已知数据进行训练的，直接聚类出结果，而分类是需要利用已有的数据训练出一个可靠的模型，然后利用这个模型去预测新的样本并给出判定，是一个训练加预测的过程；

(2) 范畴

正如上面所提，聚类是不需要利用已有的训练模型来对未知数据做预测，不需要数据类别标签，属于无监督学习，而分类是需要有一个训练过程得到一个训练模型，这个训练是有数据类别标签参与的，属于有监督学习。

Kmeans算法常用的距离公式

数学上常用距离来度量两个对象之间相隔多远，除此之外，距离还可以用来表示研究对象之间的近似程度，而聚类算法就是要根据研究对象的相似程度来决定哪些应该聚在一起，哪些不应该聚在一起，在聚类算法里面常用的一些距离公式有欧几里得距离，曼哈顿距离，闵可夫斯基距离，切比雪夫距离，夹角余弦距离和杰卡德距离等。设$x^{(i)}$ 和$x^{(j)}$是样本空间里的两个样本点，其分量分别如下

$$(x_1^{(i)},x_2^{(i)},...,x_n^{(i)})$$

$$(x_1^{(j)},x_2^{(j)},...,x_n^{(j)})$$

(1) 欧几里得距离

欧几里得距离，又叫欧式距离，是生活，研究中最常用的距离公式，用来表示欧式空间里面两个对象的远近程度，$x^{(i)}$ 和$x^{(j)}$的欧式距离可以用如下表达式来计算

$$d(x^{(i)},x^{(j)})=\sqrt{\sum _{s=1}^n(x_s^{(i)}-x_s^{(j)}{)}^2}$$

Kmeans算法默认的就是欧式距离。

(2) 曼哈顿距离

曼哈顿距离也叫出租车距离或者城市距离，常用来刻画网格上面两点之间距离，其表达式如下

$$d(x^{(i)},x^{(j)})=\sum _{s=1}^n|x_s^{(i)}-x_s^{(j)}|$$

(3) 闵可夫斯基距离

稍微复杂的距离公式还有闵可夫斯基距离公式，其表达式如下

$$d(x^{(i)},x^{(j)})=(\sum _{s=1}^n(x_s^{(i)}-x_s^{(j)}{)}^q{)}^{1/q}$$
可以看到曼哈顿距离是闵科夫斯基距离当q=1的特例，欧几里得距离是闵科夫斯基距离当q=2的特例。

(4) 切比雪夫距离

$$d(x^{(i)},x^{(j)})=\underset{1\le s\le n}{\max }|x_s^{(i)}-x_s^{(j)}|$$

由上式可以看到切比雪夫距离是闵科夫斯基距离的q趋向无穷大的极限形式，如果$x^{(i)}$ 和$x^{(j)}$某些个分量差距很大，用切比雪夫距离有天然优势。

(5) 夹角余弦距离

如果把两个样本看成向量的话，可以计算向量之间的夹角，于是有了夹角余弦距离，一般的，如果夹角越小，相似度越高，反之，相似度越小，其表达式如下

$$cos(\theta )=\frac{(x^{(i)},x^{(j)})}{|x^{(i)}||x^{(j)}|}=\frac{\sum _{s=1}^n{x}_s^{(i)}{x}_s^{(j)}}{\sqrt{\sum _{s=1}^n(x_s^{(i)}{)}^2}\sqrt{\sum _{s=1}^n(x_s^{(j)}{)}^2}}$$

夹角余弦距离常用来刻画文本相似度。

(6) 杰卡德距离

如果是两个集合，不关心集合里面具体元素，还可以用杰卡德距离，先介绍杰卡德相似系数，假设现有集合A和集合B, 其杰卡德相似系数公式如下

$$J(A,B)=\frac{|A\cap B|}{|A\cup B|}$$

杰卡德相似系数表示两个集合的交的元素占两个集合的并的元素的比例，特别的，A与B完全相同，则$|A\cap B|=|A\cup B|$，则J(A,B)=1

而杰卡德距离是在杰卡德系数的基础上再进一步加工

$$dist(A,B)=1-J(A,B)=\frac{|A\cup B|-|A\cap B|}{|A\cup B|}$$

dist(A,B)表示A与B之间的距离，距离越小，相似度越高，反之，相似度越低。

Kmeans算法流程

Kmeans算法包括簇分配和质心移动两个基本步骤，具体的

(1)初始化K个质心；

(2)计算每个样本到K个质心的距离，把每个样本分配予最近的质心，完成簇分配，记录此时每个样本的簇标签和整体损失函数；

(3)重新计算每一簇的质心，移动质心，同时，计算此时的整体损失函数；

(4)如果(3)的整体损失函数比(2)的整体损失函数小，重复第二步第三步，直到整体损失函数不再下降为止；

Kmeans算法流程如下

Kmeans实践

我们以吴恩达机器学习第七次作业为例子来进行实践，详细具体的掌握Kmeans算法。

读取数据并可视化

原始数据能够可视化的尽量可视化，原始数据可视化最大的好处就是非常直观的看到数据分布，猜到最佳聚类的数目和最后的大致效果。

import math
import numpy as np
import pandas as pd
import scipy.io as scio
import matplotlib.pyplot as plt

#数据可视化
data = scio.loadmat("D:\项目\机器学习\吴恩达机器学习课件\CourseraML\ex7\data\ex7data2.mat") #读取数据
X = data["X"]  #50*2维数组
plt.figure(figsize=(6,4)) #新建画布
plt.scatter(X[:,0], X[:,1]) #散点图
plt.xlabel("X1")
plt.ylabel("X2")
plt.show()

由于原来的数据是mat格式的，这里我们要用scipy模块io类的loadmat函数读取数据，查看数据基础信息，发现数据主体 X 其实是一个50*2维的数组，只有2个特征，那么可以用matplotlib模块可视化，从样本的散点图能够非常直观的看到最佳的聚类数目为 3。

簇分配和质心移动

利用散点图知道聚多少类之后，就有的非常关键参数K，接下来要做的就是严格按照Kmeans算法流程中的簇分配和质心移动。

初始化K个质心

实践表明第一步K个质心的选择好坏直接关系到最终的收敛效果和收敛步数，在初始质心的选择上面有两个关键因素需要考虑

一个是随机性

随机性是指初始质心的选择可以有很多种可能，可以是原样本点，也可以是非原样本点，一般选择原样本点比较好。

一个是离散性

虽然随机性可以让初始质心有很多种选择，但是质心又有牵引的作用，为保障最终收敛效果和收敛步数，初始质心还应该尽可能离散。

initial_centroids = X[np.random.permutation(len(X))[0:K],:] #随机取K个样本作为初始质心

这行代码是将原样本空间随机打乱再取打乱后样本空间的前面K个，相当于从原样本空间随机抽取了K个样本。

把每个样本分配予最近的质心

有了初始K个质心，就可以计算每一个样本到这些质心的距离，这样每个样本就会产生K个距离，可以比较这K个距离的大小，选出最小距离对应的那个质心，并将该样本划归到这个质心簇里，并标记该样本的所属的簇号，这样每个样本也有了一个簇标签，完成了第一轮簇分配。

def find_closet_centroids(myX, my_init_centroids): #给出初始聚类中心点，计算每个样本到中心点的距离并划分类
    m = myX.shape[0] #样本数
    K = my_init_centroids.shape[0] #聚类个数
    idx = np.zeros([m, 1]) #用来存放簇中心
    for i in range(m): #对每一个样本循环
        distance = [] #用来存放距离，每一个样本有k个距离
        for j in range(K):
            #print(myX[i,:], centeriods[j,:], myX[i,:] - centeriods[j, :])
            dist = np.linalg.norm(myX[i,:] - my_init_centroids[j,:]) #每个样本都有k个距离，二阶范数即欧氏距离
            distance.append(dist) 
        idx[i] = np.argmin(distance) #k个距离中取最小的
    return idx

重新计算每一簇的质心，移动质心

每个样本都有了自己所属的簇标签后，就可以重新计算该簇的质心，一般以该簇的算术平均值作为新的质心，该簇的质心移动到新的质心上。

def compute_centroids(myX, myidx): #重新计算簇中心
    m = myX.shape[0] #样本数
    n = myX.shape[-1] #特征数
    K = 3 #簇数
    centroids = np.zeros((K, n)) #簇*特征数,如同前面的initial_centroids
    counts = np.zeros((K, n)) #簇*特征数,用来存放各簇的样本数
    for i in range(m):
        centroids[int(myidx[i])] += myX[i] #簇求和
        counts[int(myidx[i])] +=1 #簇计数
    new_centroids = centroids/counts #簇平均值
    return new_centroids

判定移动质心是否对结果提升

在评价质心的移动对聚类结果是否有提升需要一个评价尺度，也就是要设计一个整体损失函数来刻画每一步的操作是否对结果是否有提升，如果有提升，那么就沿着这个方向继续进行下去，如果没有提升就要考虑停下来，或者转变方向。在设计整体损失函数时候，需要考虑样本情况，也需要质心情况，以及前后可对比性。Kmeans聚类算法的整体损失函数可以设计成

$$Cost(c_1,...,c_m,u^{c_1},...,u^{c_K})=\frac{1}{m}\sum _{i=1}^m(x^{(i)}-u^{c_i}{)}^2$$

其中，$c_i$ 代表样本 $x^{(i)}$ 被分配的簇标签， c i ∈ { 1 , 2 , . . . , K } c_i\in \{1,2,...,K\} ci​∈{1,2,...,K}，${\mu }^{c_i}$代表$x^{(i)}$被分配簇标签所对应的质心。 整体损失函数是一个收敛函数，如果下一轮算出的值比上一轮的值小，说明质心的移动确对结果有所提升，反之，质心移动没有对结果提升，达到收敛状态。

def cost(myX, myidx, centroids): #计算损失函数
    cost_value = 0
    for i in range(len(myX)):
        cost_value += np.sum((X[i] - centroids[int(myidx[i])])**2)
    cost_value /= len(myX) #整体损失值
    return cost_value

直至收敛

有了前面几小步的准备工作，现在要做的就是将其封装起来，给出整体损失函数，并设置收敛条件让其一步一步的去进行簇分配和质心移动工作，直至收敛为止。

def run_kmeans(myX, K): #在样本上运行kmeans算法
    m = myX.shape[0] #样本数
    n = myX.shape[1] #特征数
    centroids = [] #用来存放每一步的簇中心
    cost_values = [] #用来存放每一步的整体损失值
    initial_centroids = myX[np.random.permutation(m)[0:K],:] #随机取K个样本作为初始中心点
    centroids.append(initial_centroids) #把初始中心点追加进去
    initial_idx = find_closet_centroids(myX, initial_centroids) #计算每个样本到中心点的距离，并返回类别标签
    initial_cost_value = cost(myX, initial_idx, initial_centroids) #计算第一次的整体损失函数
    cost_values.append(initial_cost_value) #把第一次整体损失函数追加进去
    new_centroids = compute_centroids(myX, initial_idx) #重新计算聚类中心
    centroids.append(new_centroids) #把新的聚类中心追加进去
    new_cost_value = cost(myX, initial_idx, new_centroids) #重新计算整体损失函数,此时只是质心改变，类别标签并没改变
    cost_values.append(new_cost_value) #把新损失函数值追加进去
    while cost_values[-2]>cost_values[-1]: #判定损失函数值是否降低
        idx = find_closet_centroids(myX, centroids[-1]) #以新的质心进行簇分配
        centroid = compute_centroids(myX, idx)
        cost_value = cost(myX, idx, centroid)
        centroids.append(centroid)
        cost_values.append(cost_value)   
    return idx, centroids, cost_values

聚类过程可视化

虽然前面实现了聚类模型，如果能够将聚类过程可视化呈现一定是锦上添花，更加能够明白聚类原理。

质心分割

由于之前的质心是以数组统一保存起来，但是在绘制质心移动轨迹的时候并不好用，所以需要做一个质心分割工作，简单的来说就是将所有质心分成K组，代表K个簇，每一组都有迭代次数个质心点坐标， 这样没一簇的质心移动就清晰了

def centroid_split(mycentroids, K): #将所有中心点分簇
    step = len(mycentroids) #收敛步数
    cluster_center = []#用来存放各簇的中心点坐标
    for k in range(K):
        for i in range(step):
            cluster_center.append(tuple(mycentroids[i][k]))
    cluster_center_k = [cluster_center[i:i+step] for i in range(0, len(cluster_center), step) ]  #每簇的簇中心点坐标
    return cluster_center_k

质心移动轨迹和簇分布

这一部分需要将最后收敛状态下每簇的样本分布区分开来，并且把各簇的质心移动轨迹绘制出来

def visual_Kmeans(myX, K): #可视化Kmeans过程
    plt.figure(figsize=(6,4)) #新建画布
    plt.subplot(1,2,1) #第一个子图
    plt.xlabel("X1")
    plt.ylabel("X2")
    idx, centroids, cost_values = run_kmeans(myX, K)
    plt.scatter(myX[:,0], myX[:,1], c = idx) #根据idx标签绘制各簇散点图
    cluster_center = centroid_split(centroids, K) #中心点分簇
    for k in range(K): #绘制K个簇中心移动轨迹
        centroid_x = [] #用来存放每簇的中心点的每一步的x1值
        centroid_y = [] #用来存放每簇的中心点的每一步的x2值
        cluster_xy = cluster_center[k]
        for s in range(len(cluster_xy)):
            centroid_x.append(cluster_xy[s][0])
            centroid_y.append(cluster_xy[s][1])
        plt.plot(centroid_x, centroid_y, '-->' , linewidth = 0.7)
    plt.subplots_adjust(left=None, bottom=None, right=None, top=None, wspace=0.3, hspace=0.2) #调整子图间距
    plt.subplot(1,2,2) #第二个子图
    plt.plot([i for i in range(len(cost_values))], cost_values) #损失函数折线图
    plt.xlabel("iteration")
    plt.ylabel("cost")
    plt.show()

Kmeans算法优缺点分析

• 优点

(1) 适用性强

很多未知特性的数据集都可以先用K-means去试试，探索数据内在结构。

(2) 过程简单

• 缺点

Kmeans聚类算法的缺点也很明显，如

(1) 需要事先知道聚类数目；

参数K作为一个输入参数，是在聚类之前就要根据业务或者经验来确定；

(2) 初始质心选择影响很大；

因为初始质心选择上要具备随机性，存在一些不确定因素，并不能保证每一次初始化聚类操作都能开始于一个合适的状态，不恰当的初始质心可能使得损失函数在聚类过程中陷入局部最小值，达不到全局最优的状态，下图是多次初始质心选择聚类结果和损失函数收敛情况。

从上图可以看到前3次聚类并没有达到全局最优化，这正是因为初始质心的选择不当导致的。

Kmeans算法应用场景

Kmeans聚类算法的应用场景很多，凡是一些不代标签的数据需要聚类的都可以用Kmeans算法试一试。这里重点介绍一下Kmeans在反欺诈领域的应用，在反欺诈领域经常利用过往欺诈性索赔的黑数据，根据数据的相似性来提炼欺诈方式和欺诈模式，还可以识别新的欺诈行为。

参考文献

1, permutation用法

https://blog.csdn.net/ljyljyok/article/details/102929918

2, 调整子图间距

https://blog.csdn.net/zengbowengood/article/details/103279583

3, 多张静态图变成动图imageio

https://blog.csdn.net/zengbowengood/article/details/109336369