说明
这篇文章主要是梳理聚类分析的基本算法以及步骤，每个步骤除了给出数学公式之外，还会附上R语言实现代码。
如果要跑以下的代码，你需要确保自己的电脑里安装有R环境以及这些包：cluster, NbClust, flexclust, fMultivar, ggplot2, rattle
所有引用的资料都在最底处References处。
【注意：此文目前还在更新中，所以你可以等这行字消失的时候再来阅读此文。】
（如果目前有疑问可以先在评论区里询问，我看到了会回复你哒~）
聚类分析是什么？
我们都知道，机器学习的算法通常被分为有监督、无监督、半监督等类型。
- 有监督任务就是指数据集本身有标签，在训练的过程中，我们可以参考标签进行监督学习生成的一种，类似于有一个“老师”随时给我们提供参考答案督促我们进步的存在，常见的算法有贝叶斯、逻辑回归、支持向量机等等。
- 无监督任务就是指数据集本身无标签，只有一系列的特征，而我们要想办法把他们用合理的方式区分开来，并打上标签，常见的算法有聚类、关联规则、异常检测等。
- 半监督是将有监督和无监督结合起来的方式，常见算法有生成模型和联合训练等。
那么聚类就是在无监督任务里占据有很重要地位的一种算法，它这个算法的思路和它的名字一样，“物以类聚，人以群分”。 聚类分析通过将一组数据依照内在相似性划分为多个类别，这个类别称之为“簇”（cluster），将相似度高的样本聚在一起，相似度低的样本拆分开来，从而使得簇内数据相似度较大而簇间数据相似度较小，达到分类的目的。
因为实际工业环境中，大多数数据都是没有标签的，同时数据量巨大的话，也不可能采用人力的方法去打标签，因此虽然聚类的准确率比不上有监督的方法，但聚类在工业环境里还是占据了非常重要的地位。
聚类分析的典型步骤
聚类分析的典型步骤一般有以下几步：
- 选择合适的变量
- 数据归一化
- 寻找异常点
- 计算距离
- 选择聚类算法
- 获得一种或多种聚类方法
- 确定类的数目
- 获得最终的聚类解决方案
- 结果可视化
- 解读类
- 验证结果
我们通常说的聚类算法都聚集在了 第5步 选择聚类算法 上，因此如果你主要想看那部分的内容，可以直接用右边的导航栏快速跳过去。 那么下面从最初的步骤一点一点开始说起。
选择合适的变量
这一步主要就是特征选择了，虽然也是非常重要的步骤，但因为话题太大，以后有机会再单独提出来说吧。
缩放数据——即数据归一化
数据标准化（归一化）处理是数据挖掘的一项基础工作，不同评价指标往往具有不同的量纲和量纲单位，这样的情况会影响到数据分析的结果，为了消除指标之间的量纲影响，需要进行数据标准化处理，以解决数据指标之间的可比性。原始数据经过数据标准化处理后，各指标处于同一数量级，适合进行综合对比评价。主要有以下两种常用的方法
- min-max标准化（Min-Max Normalization） 也称为离差标准化，是对原始数据的线性变换，使结果值映射到[0-1]之间。转换函数如下： $$x^{*}=\frac{x-min}{max-min}$$ 其中max为样本数据的最大值，min为样本数据的最小值。这种方法有个缺陷就是当有新数据加入时，可能导致max和min的变化，需要重新定义。 R代码：
df1 <- apply(mydata, 2, function(x){(x-min(x))/(max(x)-min(x))})
- Z-score标准化方法 这种方法给予原始数据的均值（mean）和标准差（standard deviation）进行数据的标准化。经过处理的数据符合标准正态分布，即均值为0，标准差为1，转化函数为： $$x^{*}=\frac{x-μ}{σ}$$ 其中μ为所有样本数据的均值，σ为所有样本数据的标准差。 R代码：
df1 <- apply(mydata, 2, function(x){(x-mean(x))/sd(x)})
or
scale()
- 每个变量被其最大值相除 $$x^{*}=\frac{x}{max}$$ R代码：
df1 <- apply(mydata, 2, function(x){x/max(x)})
- 该变量减去它的平均值并除以变量的平均绝对偏差(Mean Absolute Deviation) $$x^{*}=\frac{x-mean}{mad(x)}$$ R代码：
df1 <- apply(mydata, 2, function(x){(x-mean(x))/mad(x)})
寻找异常点
许多聚类方法对异常值是十分敏感的，它能扭曲我们得到的聚类方案，因此我们应该把异常点找出来并剔除掉。 方法：
outliers包中函数来筛选和删除异常单变量离群点mvoutlier包中有能识别多元变量的离群点的函数- 使用对异常值稳健的聚类方法，如 围绕中心点的划分。
计算距离
聚类算法的本质，其实就是不停计算样本之间的距离（相似度），然后把它们放到合群的位置上去。 因此距离计算是其中很基础但也很关键的一步。
这里给定样本$x_i=(x_{i1};x_{i2};…;x_{in};)$与$x_j=(x_{j1};x_{j2};…;x_{jn};)$
距离度量需满足的基本性质
- 非负性：$dist(x_i,x_j)≧0$
- 同一性：$dist(x_i,x_j)=0$当且仅当$x_i=x_j$
- 对称性：$dist(x_i,x_j)=dist(x_j,x_i)$
- 直递性：$dist(x_i,x_j)≦dist(x_i,x_k)+dist(x_k,x_j)$（三角定理）
常用的距离度量方法有：
- 闵可夫斯基距离(Minkowski distance) $$dist(x_i,x_j) = (\sum_{u=1}^n|x_{iu} - x_{ju}|^p)^{\frac{1}{p}}$$ (1) 对p≧1,式(1)显然满足四条基本性质准则。
- 欧几里得距离(Euclidean distance)（最常用）（即p=2的时候） 通常作为连续型数据的距离度量。公式为： $$dist(x_i,x_j) = \sqrt{\sum_{u=1}^n |x_{iu}-x_{ju}|^2}$$
- 曼哈顿距离(Manhattan distance)（即p=1的时候） $$dist(x_i,x_j) = \sum_{u=1}^n|x_{ip}-x_{jp}|$$
- 兰氏距离
- 非对称二元距离
- 最大距离
R代码
d <- dist(x, method=) # 默认返回一个下三角矩阵
as.matrix(d)[1:4][1:4] # 使用标准括号符号得到距离
（可在R console中使用?dist查看详细信息，method对应有几种常见的距离计算方法）
属性划分方式：
第一种划分方式——
- 连续属性 定义域上有无穷个可能取值
- 离散属性 定义域上有有限个取值
第二种划分方式——
- 有序属性 能直接在属性上计算距离。如{1,2,3} 可采用闵可夫斯基距离来计算。
- 无序属性 不能直接在属性上计算距离。如{飞机，火车，轮船} 可采用VDM（Value Difference Metric）来计算 可以用的包：cluster包的daisy()，距离使用gower
VDM
令$m_{u,a}$表示在属性u上取值为a的样本数，$m_{u,a,i}$表示在第i个样本簇中在属性u上取值为a的样本数,k为样本簇数，则属性u上两个离散值a与b之间的VDM距离为 $$VDM_p(a,b) = \sum_1^k|\frac{m_{u,a,i}}{m_{u,a})}-\frac{m_{u,b,i}}{m_{u,b}}|^p$$
处理混合属性
将闵可夫斯基距离和VDM结合起来即可处理混合属性。 假定有$n_c$个有序属性，$n-n_c$个无序属性，不失一般性，令有序属性排列在无序属性之前，则公式为 $$MinkovDM_p(x_i,x_j)=(\sum_{u=1}^{n_c} |x_{iu}-x_{ju}|^p + \sum_{u=n_c+1}^n VDM_p(x_{iu},x_{ju}))^{\frac{1}{p}}$$
加权距离(weighted distance)
当样本空间中不同属性的重要性不同时，可使用“加权距离” $$dist(x_i,x_j)=(\omega_1·|x_{i1}-x_{j1}|^p+…+\omega_n·|x_{in}-x_{jn}|^p)^{\frac{1}{p}}$$ 其中权重$\omega_i≧0(i=1,2,…,n)$表征不同属性的重要性，通常$\sum_{i=1}^{n} \omega_i=1$
选择聚类算法
聚类算法分类
第一种分类方法——
- 层次聚类 每个观测值自成一类，这些类每次两两合并，直到所有类被聚成一类为止
- 划分聚类 首先指定类的个数K，然后观测值被随机分成K类，再重新形成聚合的类
第二种分类方法——
- 互斥的(exclusive) 每个对象都被指派到单个簇
- 重叠的(overlapping) 将对象合理的同时指派到多个簇中
- 模糊的(fuzzy clustering) 对象以一个0（绝对不属于）和1（绝对属于）之间的隶属权值属于每个簇
第三种分类方法——
- 完全聚类(complete clustering) 将每个对象指派到一个簇
- 部分聚类
不指派所有对象
- 离群点，不感兴趣的事件
簇类型
- 明显分离的簇 每个对象到同簇中每个对象的距离比到不同簇中任意对象的距离更近（或更相似）
- 基于原型的簇 每个对象到定义该簇的原型的距离比到其他簇的原型的距离更近 常见算法：K-means算法，学习向量量化，高斯混合聚类，密度聚类 clustMixType是k-prototype聚类的包
- 基于图的簇
结点是对象，边代表对象之间的联系，簇定义为互相连通但不与组外对象连通的对象组
- 每个对象到该簇某个对象的距离比到不同簇中任意点的距离更近
- 基于邻近的簇
- 基于密度的簇 簇是对象的稠密区域，被低密度的区域环绕。当具有噪声和离群点时，常常使用基于密度的簇定义。 常见算法：DBSCAN(Density-Based Spatial Clustering of Applications with Noise)
- 概念簇 簇定义为具有某种共同性质的对象的集合
层次聚类
每个观测值自成一类，这些类每次两两合并，直到所有类被聚成一类为止 算法如下：
- 定义每个观测值（行或单元）为1类
- 计算每类和其他各类的距离
- 把距离最短的两类合并为一类，这样类的个数就减少一个
- 重复步骤2,3，直到包含所有观测值的类合并成单个的类为止。
在层次聚类算法中，主要的区别是他们对类的定义不同
常用算法
| 算法名字 | 类的定义 | 聚类结果 |
| 单联动 | 一个类中的点和另一个类中的点的最小距离 | 倾向于发现细长的、雪茄型的类，通常展示一种链式的现象，即不相似的观测值分到一类中，因为它们和它们的中间值很相像 |
| 全联动 | 一个类中的点和另一个类中的点的最大距离 | 倾向于发现大致相等的直径紧凑类，对异常值很敏感 |
| 平均联动 | 一个类中的点和另一个类中的点的平均距离（也称作UPGMA, 即非加权对组平均） | 提供了以上两种方式的折中办法，不像链式，而且对异常值没有那么敏感，倾向于把方差小的类聚合。 |
| Ward方法 | 两个类之间所有变量的方差分析的平方和。 | 倾向于把有少量观测值的类聚合在一起，并且倾向于产生与观测值个数大致相等的类。对异常值敏感。 |
| 质心 | 两类中质心（变量均值向量）之间的距离。对单个的观测值来说，质心就是变量的值。 | 类距离的定义比较简单、易于理解，相比其他方法对异常值不是很敏感，但是可能不如平均联动法或Ward方法表现得好。 |
R代码
hclust(d, method=)
d是通过dist()产生的距离矩阵
method包括single, complete, average, centroid, ward
划分聚类
首先指定类的个数K，然后观测值被随机分成K类，再重新形成聚合的类。常用算法有——
- K-means算法
- 围绕中心点的划分（PAM）
K-means算法
- 选择K个中心点（随机选择K行）
- 把每个数据点分配到离它最近的中心点（计算距离一般采用欧几里得距离）
- 重新计算每类中的点到该类中心点距离的平均值
- 分配每个数据到它最近的中心点
- 重复步骤3和4，直到所有的观测值不再被分配或是达到最大的迭代次数（R把10次作为默认迭代次数）
评价： 可以处理比层次聚类更大的数据集，另外观测值不会永远被分到一类中。当我们提高整体解决方案时，聚类方案也会改动，但是均值的使用意味着所有的变量必须是连续的，并且这个方法很有可能被异常值影响。 它在非凸聚类（如U型）情况下会变得很差。
R代码
kmeans(x, centers)
# x表示数值数据集（矩阵或数据框），centers是要提取的聚类数目。函数返回类的成员、类中心、中心和（类内平方和、类间平方和、总平方和）和类大小。
由于聚类方法对初始中心值的选择很敏感，kmeans()有一个nstart选项可以供你尝试多种初始配置并输出最好的一个。
围绕中心点的划分
- 随机选择K个观测值（每个都称为中心点）
- 计算观测值到每个中心的距离/相异性
- 把每个观测值分配到最近的中心点
- 计算每个中心点到每个观测值的距离的总和（总成本）
- 选择一个该类中不是中心的点，并和中心点互换。
- 重新把每个点分配到距它最近的中心点
- 再次计算总成本
- 如果总成本比步骤4计算的总成本少，把新的点作为中心点
- 重复步骤5-8直到中心点不再改变
评价： 更稳健，可容纳混合数据类型，并且不仅限于连续变量。 K-means一般使用欧几里得距离，PAM可以使用任意的距离来计算。
R代码 Cluster包中的pam()
pam(x, k, metric="euclidean", stand=FALSE)
x表示数据矩阵或数据框，k表示聚类的个数，metric表示使用的相似性/相异性的度量，而stand是一个逻辑值，表示是否有变量应该在计算该指标之前被标准化。
获得一种或多种聚类方法
这一步可以使用步骤5选择的方法
确定类的数目
为了得到最终的聚类方案，你必须确定类的数目。 常用方法：
- 尝试不同的类数（如2~K）并比较解的质量。
NbClust包中的NbClust()提供了30个不同的指标来帮助你进行选择。
获得最终的聚类解决方案
一旦类的个数确定下来，就可以提取出子群，形成最终的聚类方案了。
对于层次聚类
cutree()函数用来把树状图分成k类
aggregate()函数用来获取每类的中位数
rect.hclust()函数用来叠加k类的解决方案
结果可视化
帮助判定聚类方案的意义和用处。
- 层次聚类结果通常表示为一个树状图。
- 划分聚类结果通常利用可视化双变量聚类图来表示。
解读类
需要注意，因为聚类是根据样本之间的相似性将它们分到一堆的，其实它并不知道这一簇簇样本，在现实世界里有什么意义。所以这里我们需要解读这一簇簇样本。 这一步通常通过获得类中的每个变量的汇总统计来完成。
- 连续型数据： 计算每一类中变量的均值和中位数
- 混合数据（数据中包含分类变量）： 返回各类的众数或类别分布
验证结果
相当于在问“这种划分并不是因为数据集或聚类方法的某种特性，而是确实给出了一个某种程度上有实际意义的结果吗？” 希望结果：簇内相似度高，簇间相似度低。
性能度量方式
- 外部指标（external index）
将聚类结果与某个参考模型进行比较
常用度量指标：
- Jaccard系数（JC）
- FM指数
- Rand指数
- 内部指标（internal index）
直接考察聚类结果而不利用任何参考模型
常用度量指标：
- DB指数（DBI）
- Dunn指数（DI）
在fpc, clv, clValid包里包含了评估聚类解的稳定性的函数。
References
- 《R语言实战（第2版）》[美]Robert I.Kabacoff
- 数据归一化和两种常用的归一化方法
- 《机器学习》周志华
- 《聚类分析：基本概念和算法》-MC Lab
