无监督学习

无监督学习是一类机器学习算法，在无监督学习中，训练样本的标记信息是未知的，目标是通过对无标记训练样本的学习来揭示数据的内在性质及规律，为进一步数据分析提供基础。通俗的讲，无监督学习就是“从无规律中找到规律”，在未知样本的真实结果的情况下，通过自主学习找到样本之间的一些规律，并将这些规律用于预测。

聚类是常见的一类无监督学习任务。简单地说，聚类就是把杂乱的数据划归为特定的几类，并且这些数据没有标记。举个例子，假设一个电商平台获得了一批新用户，但由于是新用户，还不知道他们的各种习惯爱好，因此我们无法直接对这些用户划分类型。我们可以通过一些算法将他们划分为几类，然后再对他们的用户类型进行判别。聚类就是类似这么个过程。

形式化表述一下，假定样本集D={x1,…,xm}，每个样本xi={x_i1,…,x_in}没有标记，聚类算法将样本集D划分为k个不相交的簇{Cj|j=1,2,…,k}。我们用λd∈{1,…,k}表示样本xd的簇标记，即xd∈C_λd。聚类的结果可用包含m个元素的簇标记向量λ={λ1;…;λm}表示。

性能度量

什么样的聚类结果比较好呢？当然是同一簇的样本越相似，而不同簇的样本尽可能的不同。

聚类性能度量大致有两类：

1. 外部指标(external index)：将聚类结果与某个“参考模型”(reference model)进行比较；
2. 内部指标(internal index)：直接考察聚类结果而不利用任何参考模型。

定义数据集D={x1,…,xm}，聚类出簇划分为C={C_1,…,C_k}，参考模型给出簇划分为C*={C*_1,…,C*_S}，λ与λ*为C与C*对应的簇标记向量。将样本两两配对考虑，定义：

 

上面几个公式中：

SS包含：在C中属于相同簇，在C*中也属于相同簇的样本对；

SD包含：在C中属于相同簇，但在C*中属于不同簇的样本对；

DS包含：在C中属于不同簇，但在C*中属于相同簇的样本对；

DD包含：在C中属于不同簇，在C*中也属于不同簇的样本对。

因为每个样本对仅能出现在一个集合中，因此a+b+c+d=m(m-1)/2成立。

基于上面四个式子可推导出以下一些常用的性能度量，度量外部指标：

 

上述性能度量的结果值均在[0,1]区间内，值越大越好。

考虑聚类结果的簇划分C={C1,…,Ck}，定义：

 

其中，dist用于计算两个样本之间的距离，μ代表簇C的中心点：

avg(C)对应于簇C内样本间的平均距离，diam(C)对应于簇C内样本间的最远距离，d_min对应于两簇之间的最近样本的距离，d_cen对应于两簇之间中心点间的距离。

基于上面四个式子可以导出以下常用的性能度量，度量内部指标：

DBI值越小越好，相反，DI值越大越好。

距离计算

对于前面的距离函数dist()，满足一些基本性质：

给定样本 和 ，常用距离有以下几种：

• 闵可夫斯基距离(Minkowski distance)：

• p=2时，闵可夫斯基距离就变成欧氏距离(Euclidean distance)：

• p=1时，闵可夫斯基距离就变成曼哈顿距离(Manhattan distance)，也称街区距离(city block distance)：

 

• p→∞时，闵可夫斯基距离变为切比雪夫距离(Chebyshev distance)：

• 余弦距离：

余弦相似度：两个向量间夹角的相似度，公式如下：

余弦距离就是dist = 1-sim。

• 马氏距离(Mahalanobis distance)：

其中，Σ^(-1)是数据协方差矩阵的逆。马氏距离考虑了数据属性之间的相关性，排除了属性间相关性的干扰，而且与量纲无关。若协方差矩阵是对角阵，则马氏距离变成了标准欧式距离；若协方差矩阵是单位矩阵，各个样本向量之间独立同分布，则变成欧式距离。

• VDM(Value Difference Metric)距离：

其中，m_u,a表示在属性u上取值为a的样本数；m_u,a,i表示在第i个样本簇中属性上取值为a的样本数，k为样本簇数。VDM距离用于无序距离，即不能直接在属性值上计算距离，如属性{飞机，轮船，火车}.

将闵可夫斯基距离与VDM距离结合可处理混合属性；当样本空间中不同属性的重要程度不同时可使用“加权距离”(weighted distance)。

原型聚类

原型聚类亦称"基于原型的聚类" (prototype-based clustering)，此类算法假设聚类结构能通过一组原型刻画，在现实聚类任务中极为常用。通常情形下，算法先对原型进行初始化，然后对原型进行迭代更新求解.采用不同的原型表示、不同的求解方式，将产生不同的算法。

k-means算法

设有m条数据，n个属性，要分为k个簇，k均值算法的基本思想如下：

1. 随机选取k个点作为起始中心；
2. 遍历数据集中的每一条数据，计算它与每个中心的距离；
3. 将数据分配到距离最近的中心所在的簇；
4. 使用每个簇数据的均值作为新的簇中心；
5. 如果簇的中心点发生变化，则转到第2步继续执行；否则，结束聚类。

k均值算法对聚类所得簇划分C最小化平方误差公式为：

其中，是簇Ci的均值向量。

学习向量量化

“学习向量量化”(Learning Vector Quantization，简称LVQ)也是试图找到一组原型向量来刻画聚类结构，与一般聚类算法不同，LVQ假设数据样本带有类别标记，学习过程利用样本的这些监督信息来辅助聚类。

LVQ算法通过计算样本与每个原型向量之间的距离，选出距离最小的原型向量，然后与假设的样本标记进行比对，再进行相应的更新。

LVQ算法如下：

                                                                                   图 LVQ算法，来源西瓜书

 

高斯混合聚类

高斯混合(Mixture-of-Gaussian)聚类是采用概率模型来表达聚类原型。

我们假设数据点是服从高斯分布的，那么每个簇将服从单独的高斯分布，我们通过寻找每个簇的高斯分布参数（均值和标准差）实现聚类。常使用EM算法进行优化。高斯混合聚类算法如下：

1. 选定聚类的簇的个数k，随机初始化每个簇的高斯分布参数，为各个簇建立高斯分布；
2. 通过计算样本点与距离每个高斯分布中心的距离，将样本划分到距离最近的簇中；
3. 通过计算出的概率更新各分布的参数，然后返回第二步继续迭代，直至收敛。

层次聚类

层次聚类(hierarchical clustering)基于簇间的相似度在不同层次上分析数据，从而形成树形的聚类结构，层次聚类一般有两种划分策略：自底向上的聚合（agglomerative）策略和自顶向下的分拆（divisive）策略

AGNES算法是一种自底向上的层次聚类算法。其基本思想是：一开始先将数据集中的每个样本作为一个簇，然后找到距离最近的两个簇，将他们合并，不断重复这个过程，直至簇的个数减少到预设的聚类数目为止。

聚类簇之间的距离可通过如下公式计算：

可以看出，最小距离由两个簇的最近样本决定，最大距离由两个样本簇的最远样本决定。

密度聚类

密度聚类假设聚类结构通过样本分布的紧密程度。此算法是基于密度的角度来考察样本之间的连接性，并基于连接性不断扩展聚类簇最后获得最终的结果。通过判断样本在区域空间内是否大于某个阈值来决定是否将其放到与之相近的样本中。

DBSCAN是一种著名的密度聚类算法，其主要思想是：先任选数据集中的一个核心对象为“种子”，再由此出发确定相应的聚类簇。算法伪代码如下：

                                                                              图 DBSCAN算法，来源西瓜书

DBSCAN算法的优点与缺点

优点：

1. 相比k-均值算法，DBSCAN不需要预先声明聚类数量。
2. DBSCAN可以找出任何形状的聚类，甚至能找出一个聚类，它包围但不连接另一个聚类，另外，由于MinPts参数，single-link effect（不同聚类以一点或极幼的线相连而被当成一个聚类）能有效地被避免。
3. DBSCAN能分辨噪音（局外点）。
4. DBSCAN只需两个参数，且对数据库内的点的次序几乎不敏感（两个聚类之间边缘的点有机会受次序的影响被分到不同的聚类，另外聚类的次序会受点的次序的影响）。
5. DBSCAN 被设计成能配合可加速范围访问的数据库结构，例如R*树。
6. 如果对资料有足够的了解，可以选择适当的参数以获得最佳的分类。

缺点：

1. DBSCAN不是完全决定性的：在两个聚类交界边缘的点会视乎它在数据库的次序决定加入哪个聚类，幸运地，这种情况并不常见，而且对整体的聚类结果影响不大——DBSCAN对核心点和噪音都是决定性的。DBSCAN* 是一种变化了的算法，把交界点视为噪音，达到完全决定性的结果。
2. DBSCAN聚类分析的质素受函数regionQuery(P,ε)里所使用的度量影响，最常用的度量是欧几里得距离，尤其在高维度资料中，由于受所谓“维数灾难”影响，很难找出一个合适的ε，但事实上所有使用欧几里得距离的算法都受维数灾难影响。
3. 如果数据库里的点有不同的密度，而该差异很大，DBSCAN将不能提供一个好的聚类结果，因为不能选择一个适用于所有聚类的minPts-ε参数组合。
4. 如果没有对资料和比例的足够理解，将很难选择适合的ε参数。

 

 

参考资料

1. k-means聚类算法https://blog.csdn.net/yjp19871013/article/details/79937149
2. 余弦距离与欧式距离https://zhuanlan.zhihu.com/p/84643138
3. 度量学习中的马氏距离https://www.jianshu.com/p/5706a108a0c6
4. 数据挖掘——聚类分析总结https://www.cnblogs.com/rix-yb/p/985151html
5. 5种主要聚类算法的简单介绍 http://www.sohu.com/a/225353030_99992181
6. 机器学习——学习向量量化https://cloud.tencent.com/developer/news/391329
7. 学习向量量化https://baike.baidu.com/item/%E5%AD%A6%E4%B9%A0%E5%90%91%E9%87%8F%E9%87%8F%E5%8C%96/22814173?fr=aladdin
8. 《统计学习方法》.李航
9. 《机器学习》.周志华