聚类问题

1. 概述

• 聚类分析（cluster analysis ） 是一种常用的无监督学习算法，它试图将一组不带标签的样本（或变量）根据彼此至今的相似度划分成若干个类，使得相似的样本归到一个小的分类单元中，不相似的样本归到一个大的分类单元中，知道所有的样本都分类完毕，由于这些样本并不带标签，因此，对于各个类的含义需要使用者结合业务知识进行解读和定义。

• 聚类分析既能作为一个单独的过程，用来寻找一组不带标签的数据的内在结构和规律，也可以作为其他分类算法的前期工作，例如：我们可以先用聚类算法对一批产品的消费进行分类，并给予业务上的定义，再基于这个人为定义的类型训练有监督的分类模型，用来对新用户进行预测分类。

• 在实际应用场景中，聚类分析常用来对目标用户群体分类，把目标群体分为几个特征鲜明的细分群体，从而可以在运营活动中对这些不同群体开展差异化的服务。另外，聚类分析也常用来发现异常和孤立点，比如，在电子商务服务网站的购物交易中，通过聚类分析发现异常的有欺诈风险的交易行为。

• -聚类（cluster）与分类（class）问题不同，聚类是属于无监督学习模型，而分类属于有监督学习。聚类使用一些算法把样本分为N个群落，群落内部相似度较高，群落之间相似度较低。在机器学习中，通常采用“距离”来度量样本间的相似度，距离越小，相似度越高；距离越大，相似度越低.

相似度度量方式

① 欧氏距离

相似度使用欧氏距离来进行度量. 坐标轴上两点$x_1,x_2$之间的欧式距离可以表示为：
$$|x_1-x_2|=\sqrt{(x_1-x_2{)}^2}$$
平面坐标中两点$(x_1,y_1),(x_2,y_2)$欧式距离可表示为：
$$|(x_1,y_1)-(x_2,y_2)|=\sqrt{(x_1-x_2{)}^2+(y_1-y_2{)}^2}$$
三维坐标系中$(x_1,y_1,z_1),(x_2,y_2,z_2)$欧式距离可表示为：
$$|(x_1,y_1,z_1),(x_2,y_2,z_2)|=\sqrt{(x_1-x_2{)}^2+(y_1-y_2{)}^2+(z_1-z_2{)}^2}$$
以此类推，可以推广到N维空间.

② 曼哈顿距离

二维平面两点$a(x_1,y_1)$与$b(x_2,y_2)$两点间的曼哈顿距离为：
$$d(a,b)=|x_1-x_2|+|y_1-y_2|$$
推广到N维空间，$x(x_1,x_2,...,x_n)$与$y(y_1,y_2,...,y_n)$之间的曼哈顿距离为：
$$d(x,y)=|x_1-y_1|+|x_2-y_2|+...+|x_n-y_n|=\sum _{i=1}^n|x_i-y_i|$$

绿色线条表示的为欧式距离，红色线条表示的为曼哈顿距离，黄色线条和蓝色线条表示的为曼哈顿距离的等价长度。
那个直角边相加就是那个曼哈顿距离了 you know？

③ 闵可夫斯基距离

闵可夫斯基距离（Minkowski distance）又称闵氏距离，其定义为：
$$D(x,y)=(\sum _{i=1}^n|x_i-y_i{|}^p{)}^{\frac{1}{p}}$$

• 当$p=1$时，即为曼哈顿距离

• 当$p=2$时，即为欧式距离

• 当$p\to \infty$时，即为切比雪夫距离

可见，曼哈顿距离、欧氏距离、切比雪夫距离都是闵可夫斯基的特殊形式.

聚类算法的划分

① 原型聚类

原型聚类也称“基于原型的聚类”（prototype-based clustering），此类算法假设聚类结构能通过一组原型刻画，在现实聚类任务中极为常用. 通常情况下，算法先对原型进行初始化，然后对原型进行迭代更新求解. 采用不同的原型表示、不同的求解方式，将产生不同的算法. 最著名的原型聚类算法有K-Means.

② 密度聚类

密度聚类也称“基于密度的聚类”（density-based clustering），此类算法假定聚类结构能通过样本分布的紧密程度确定. 通常情况下，密度聚类算法从样本密度的角度来考察样本之间的可连接性，并基于可连接样本不断扩展聚类簇以获得最终的聚类结果. 著名的密度聚类算法有DBSCAN.

③ 层次聚类

层次聚类（hierarchical clustering）试图在不同层次对数据集进行划分，从而形成树形的聚类结构. 数据集的划分可以采用“自底向上”或“自顶向下”的策略. 常用的层次聚类有凝聚层次算法等.

常用聚类算法

K均值聚类

① 定义

K均值聚类（k-means clustering）算法是一种常用的、基于原型的聚类算法，简单、直观、高效。其步骤为：

第一步：根据事先已知的聚类数，随机选择若干样本作为聚类中心，计算每个样本与每个聚类中心的欧式距离，离哪个聚类中心近，就算哪个聚类中心的聚类，完成一次聚类划分.

第二步：计算每个聚类的几何中心，如果几何中心与聚类中心不重合，再以几何中心作为新的聚类中心，重新划分聚类. 重复以上过程，直到某一次聚类划分后，所得到的各个几何中心与其所依据的聚类中心重合或足够接近为止.

注意事项：

（1）聚类数（K）必须事先已知，来自业务逻辑的需求或性能指标.

（2）最终的聚类结果会因初始中心的选择不同而异，初始中心尽量选择离中心最远的样本.，初始随机点是随机产生的。

import sklearn.cluster as sc# 创建模型
model = sc.KMeans(n_clusters)  # n_cluster为聚类数量# 获取聚类(几何)中心
centers = model.cluster_centers_ ，记录一组坐标值 # 获取聚类标签（聚类结果）
pred_y = model.labels_  

③ 特点及使用

• 优点

（1）原理简单，实现方便，收敛速度快；

（2）聚类效果较优，模型的可解释性较强；

• 缺点

（1）需要事先知道聚类数量；就是需要是先设置K，选取不当会影响聚类结果

（2）聚类初始中心的选择对聚类结果有影响；

（3）采用的是迭代的方法，只能得到局部最优解；

（4）对于噪音和异常点比较敏感. ，因为他是根据所有的样本点进行计算中心点的

• 什么时候选择k-means

（1）事先知道聚类数量

（2）数据分布有明显的中心

噪声密度

定义

噪声密度（Density-Based Spatial Clustering of Applications with Noise， 简写DBSCAN）随机选择一个样本做圆心，以事先给定的半径做圆，凡被该圆圈中的样本都被划为与圆心样本同处一个聚类，再以这些被圈中的样本做圆心，以事先给定的半径继续做圆，不断加入新的样本，扩大聚类的规模，直到再无新的样本加入为止，即完成一个聚类的划分. 以同样的方法，在其余样本中继续划分新的聚类，直到样本空间被耗尽为止，即完成整个聚类划分过程. 示意图如下：
没有被样本圈进来的样本点丢弃，就是噪声样本，也有可能一个样本同时被多个圈圈 圈进去，这个圈只圈没有样本归属的样本点

DBSCAN算法中，样本点被分为三类：

• 边界点（Border point）：可以划分到某个聚类，但无法发展出新的样本；就是那个最后的一个样本点，无法圈出新的样本点，那么这个点也就是边界点
• 噪声点（Noise）：无法划分到某个聚类中的点；
• 核心点（Core point）：除了噪声点和边界点以外的样本都是核心点；
• 

上图中，A和B为核心点，C为边界点，D为噪声点. 此外，DBSCAN还有两个重要参数：

• 邻域半径：设置邻域半径大小；半径太大也不能太小
• 最少样本数目：邻域内最小样本数量，某个样本邻域内的样本超过该数，才认为是核心点.，圈圈至少圈进多少的样本才算数

model = sc.DBSCAN(eps,   # 半径min_samples) # 最小样本数#这两个参数的选择很重要

③ 特点及使用

• 算法优点

（1）不用人为提前确定聚类类别数K；
（2）聚类速度快；
（3）能够有效处理噪声点（因为异常点不会被包含于任意一个簇，则认为是噪声）；
（4）能够应对任意形状的空间聚类.，适合那种数据分布中心不明显的。

• 算法缺点

（1）当数据量过大时，要求较大的内存支持I/O消耗很大；几何增长嘞
（2）当空间聚类的密度不均匀、聚类间距差别很大时、聚类效果有偏差；
（3）邻域半径和最少样本数量两个参数对聚类结果影响较大.，直接影响聚类的结果

• 何时选择噪声密度

（1）数据稠密、没有明显中心；

（2）噪声数据较多；

（3）未知聚簇的数量.

凝聚层次聚类

定义

凝聚层次（Agglomerative）算法，首先将每个样本看做独立的聚类，如果聚类数大于预期，则合并两个距离最近的样本作为一个新的聚类，如此反复迭代，不断扩大聚类规模的同时，减少聚类的总数，直到聚类数减少到预期值为止. 这里的关键问题是如何计算聚类之间的距离.

依据对距离的不同定义，将Agglomerative Clustering的聚类方法分为三种：

• ward：默认选项，挑选两个簇来合并，是的所有簇中的方差增加最小。这通常会得到大小差不多相等的簇。
• average链接：将簇中所有点之间平均距离最小的两个簇合并。
• complete链接：也称为最大链接，将簇中点之间最大距离最小的两个簇合并。

ward适用于大多数数据集。如果簇中的成员个数非常不同（比如其中一个比其他所有都大得多），那么average或complete可能效果更好。

特点及使用

（1）需要事先给定期望划分的聚类数（k），来自业务或指标优化；

（2）没有聚类中心，无法进行聚类预测，因为不依赖于中心的划分，所以对于中心特征不明显的样本，划分效果更佳稳定.

（3）适合于中心不明显的聚类.

3. 聚类的评价指标

理想的聚类可以用四个字概况：内密外疏，即同一聚类内部足够紧密，聚类之间足够疏远. 学科中使用“轮廓系数”来进行度量，见下图：

假设我们已经通过一定算法，将待分类数据进行了聚类，对于簇中的每个样本，分别计算它们的轮廓系数。对于其中的一个点 i 来说：
​ a(i) = average(i向量到所有它属于的簇中其它点的距离)
​ b(i) = min (i向量到各个非本身所在簇的所有点的平均距离)找的就是离它最近距离的那个簇的平均值
那么 i 向量轮廓系数就为：
$$S(i)=\frac{b(i)-a(i)}{max(b(i),a(i))}$$
由公式可以得出:

（1）当$b(i)>>a(i)$时，$S(i)$越接近于1，这种情况聚类效果最好；

（2）当$b(i)<<a(i)$时，$S(i)$越接近于-1，这种情况聚类效果最差；

（3）当$b(i)=a(i)$时，$S(i)$的值为0，这种情况分类出现了重叠.

#sklearn提供的计算轮廓系数API：
score = sm.silhouette_score(x, # 样本pred_y, # 标签sample_size=len(x), # 样本数量metric="euclidean")  # 欧式距离度量

（1）聚类属于无监督学习；

（2）聚类是根据数据的特征，将相似度最高的样本划分到一个聚簇中；

（3）相似度的度量方式：曼哈顿距离、欧式距离、切比雪夫距离，都可以用闵式距离公式表示；

（4）聚类算法

• 基于原型聚类：k-means算法
• 基于密度聚类：DBSCAN算法
• 基于层次聚类：凝聚算法

（5）评价指标：轮廓系数