无监督学习/聚类

image.png

什么是无监督学习？

无监督学习是一种在最少人类干预的情况下，在没有标签的情况下寻找数据特殊Pattern的机器学习算法。
可以这样理解：当你在学校参加考试时，会有问题和答案；你的分数取决于你的答案与实际答案(或答案键)的接近程度。但是想象一下，如果没有答案，只有问题。
你如何给自己打分?

聚类

任何企业都需要着重于了解客户：他们是谁，什么驱动他们的购买决定？

通常，您将拥有不同的用户组，可以将其分为几个条件。这些标准可以很简单，例如年龄和性别，也可以很复杂，例如角色和购买过程。无监督学习可以帮助您自动完成此任务。

聚类算法将遍历您的数据并找到这些自然聚类（如果存在）。对于您的客户而言，这可能意味着一群30多岁的艺术家和另一群拥有狗的千禧一代。通常，您可以修改算法查找的群集数量，从而可以调整这些组的粒度。您可以利用几种不同类型的集群：

k-means clustering(均值聚类)

将数据点聚类为（K）个互斥的聚类。如何为K选择正确的数字有很多复杂性。

KMeans算法的终止条件：1）迭代次数 2）簇中心点变化率 3）最小平方误差值
KMeans算法的优点：理解简单容易，凸聚类的效果不错，效率高；对于服从高斯分布的数据集效果相当好。
KMeans算法的缺点：中心点数量K的确定，初始化的中心点位置敏感，对于环形等非凸的数据集的聚类效果不好。

先使用sklearn自带的生成器生成数据

from sklearn.datasets.samples_generator import make_blobs  # make_blobs聚类数据生成器
from matplotlib import pyplot as plt
%matplotlib inline
x,y_true = make_blobs(n_samples=300,centers=4,cluster_std=0.5,random_state=0)
print(x[:5])
print(y_true[:5])

# n_samples 生成的样本总数
# centers 类别数
# cluster_std 每个类别的方差，如果多类数据不同方差可设置为[std1,std2,...stdn]
# random_state 随机数种子
# x 生成的数据，y 数据对应的类别
# n_features 每个样本的特征数

plt.scatter(x[:,0],x[:,1],s=10,alpha=0.8)

image.png

通过sklearn的KMeans进行聚类分析

from sklearn.cluster import KMeans
kmeans = KMeans(n_clusters=4)  #创建模型
kmeans.fit(x)  #导入数据
y_kmeans = kmeans.predict(x)  #预测每个数据属于哪个类
centroids = kmeans.cluster_centers_ #每个类的中心点
plt.scatter(x[:,0],x[:,1],s=30,c=y_kmeans,cmap = 'Dark2',alpha=0.5,marker='x')
plt.scatter(centroids[:,0],centroids[:,1],s=70,c=[0,1,2,3],cmap = 'Dark2',marker='o')
plt.title('K-means 300 points')
plt.xlabel('value1')
plt.ylabel('value2')

image.png

Hierarchical clustering(层次聚类)

将数据点群集到父群集和子群集中。您可以将客户划分为不同年龄段的人，然后将这些组的每个人也划分为各自的单独集群。
AGNES算法（凝聚的层次聚类，自底向上）
DIANA算法（分裂的层次聚类，自顶而下）
BIRCH算法（平衡迭代削减法）---适合大数据集使用的算法

凝聚聚类（Agglomerative Clustering）是一种采用自底向上聚类策略的层次聚类算法。
1.它先将数据集中的每个样本看作一个初始聚类簇。
2.然后在算法运行的每一步中找出距离最近的两个聚类簇进行合并。
3.以合并后的新簇重新计算该新簇与其他簇的距离
4.回到2该过程不断重复，直到达到预设的聚类簇个数。

这里的关键是如何计算聚类簇之间的距离。实际上，每个簇是一个样本集合，因此，只需要采用关于集合的某种距离即可。
下面以单链接为例子，介绍层次聚类的层次图（系统图，dendrogram）。假设我们有以下八个点，使用单链接聚为 3 个类。首先将每个点设为一个单独的簇类，因此此时有 8 个簇，大于预期 3 个簇，故需要继续进行聚类。

image.png

每次将距离最近的两个样本聚为同一簇，对应下图的层次图。不断进行聚类。最终达到了我们所要求的聚类簇数，故算法停止，对应的层次图如下方所示

image.png

from scipy.cluster.hierarchy import dendrogram,linkage
from sklearn.datasets import load_iris
import matplotlib.pyplot as plt
X = load_iris().data[:10]
linkage_matrix = linkage(X,'ward')
dendrogram(linkage_matrix)
plt.show
linkage_matrix

image.png

DIANA算法
分裂的层次聚类与凝聚的层次聚类相反，采用自顶向下的策略，它首先将所有对象置于同一个簇中，然后逐渐细分为越来越小的簇，直到每个对象自成一簇，或者达到了某个终止条件。该种方法一般较少使用。

BIRCH算法
BIRCH使用三元组保存簇的相关信息，通过构建满足两个参数分支因子和类直径的聚类特征树（底层为CF-Tree实现的）来求聚类。

三元组：（数据点个数，数据点特征之和，数据点特征的平方和）--这种方式可以有效地提高计算距离的速度（就是三元组的线性组合求距离）
分支因子：分支因子规定了树的每个节点的样本个数。
类直径：体现这一类点的距离范围。
BIRCH算法中聚类特征树的构建过程是一个动态的过程，可以随时接受数据点并对树进行重新构建，这也是它适用于大规模数据集的主要原因。

密度聚类

简单点说，密度聚类就是通过计算给定样本点附近的邻域内地数据点的个数，如果个数大于给定的阈值，那么就判定该样本点属于这个簇。
密度聚类能够很好的克服前面所讲的划分聚类的缺点（只能发现凸聚类的数据），它可以发现任意形状的聚类，并且对于噪声数据不敏感。
密度聚类将簇的概念重新定义为：密度相连的点的最大集合。

DBSCAN（基于密度的聚类算法）
MDCA（密度最大值聚类算法）

DBSCAN（基于密度的聚类方法--常用的密度聚类方法）
（1）DBSCAN的算法思想：用一个点附近的邻域内的数据点的个数来衡量该点所在空间的密度。
（2）将样本集中的点划分为以下三类：
核心点：在半径r区域内，含有超过MinPts数目（最小数目）的点，称为核心点；
边界点：在半径r区域内，点的数量小于MinPts数目，但是是核心点的直接邻居；
噪声点：既不是核心点也不是边界点的点

image.png

依照上图以及三种点的定义，可以得到：噪声点是不会被聚类纳入的点，边界点与核心点组成聚类的“簇”。
（3）基本概念：
1. 邻域--- 给定点的半径r为内的区域。
2. 密度--- 就是数据点r邻域内的样本点的个数。
3. 阈值--- 给定的值M。
4. 核心点--- 如果数据点的r邻域内的样本点数大于等于阈值M，则该点为核心点。
5. 边界点--- 如果非核心点的r邻域内存在核心点。
6. 噪音点--- 既不是核心点也不是边界点的数据点。
7. 直接密度可达--- 对于核心点X，其附近的r邻域内的样本点对X都叫做直接密度可达。
8. 密度可达--- 对于核心点X，Y为其r邻域内的又一个核心点，则Y的r邻域内的所有数据点对X均为密度可达。（可以理解为间接相关）
9. 密度相连--- 对于核心点X,Y，如果有点Z与X、Y都密度可达，则X、Y密度相连。
10. 簇--- 在DBSCAN中，簇就是最大密度相连的数据点的集合。
如下图所示：
r用一个相应的半径表示，设MinPts=3，分析Q、M、P、S、O、R这5个样本点之间的关系。

image.png

根据以上概念可知：由于有标记的各点M、P、O和R的r邻域均包含3个以上的点，因此它们都是核对象；M是从P的“直接密度可达”；Q是从M的“直接密度可达”；基于上述结果，Q是从P的“密度可达”；但P从Q是无法“密度可达”（非对称的）；类似的，S和R都是从O的“密度可达”；O、R都是从S的“密度相连”。
也就是说：核心点能够连通（密度可达），它们构成的以r为半径的圆形邻域相互连接或重叠，这些连通的核心点及其所处的邻域内的全部点构成一个簇。
（4）DBSCAN聚类算法原理
1.DBSCAN通过检查数据集中每个点的r邻域来搜索簇，如果点p的r邻域包含多于MinPts个点，则创建一个以p为核心对象的簇；
2.然后， DBSCAN迭代的聚集从这些核心对象直接密度可达的对象，这个过程可能涉及一些密度可达簇的合并；
3.当没有新的带你添加到任何簇时，迭代过程结束。
DBSCAN聚类算法效果展示如下图：

（5）DBSCAN聚类算法优缺点
优点：
1、不需要事先给定cluster的数目。
2、可以发现任意形状的cluster。
3、能够找出数据中的噪音，且对噪音不敏感。
4、算法只需要两个输入参数。
5、聚类结果几乎不依赖节点的遍历顺序。
缺点：
1、DBSCAN算法聚类效果依赖距离公式的选取，最常用的距离公式为欧几里得距离。但是对于高维数据，由于维数太多，距离的度量已变得不是那么重要。维度灾难 02 聚类算法 - 相似度距离公式、维度灾难
2、DBSCAN算法不适合数据集中密度差异很小的情况。

MDCA（Maximum Density Clustering Application 密度最大值聚类算法）--- 密度和层次结合的算法
算法基于密度的思想引入划分聚类中，使用密度而不是初始点作为考察簇归属情况的依据，能够自动确定簇数量并发现任意形状的簇；另外MDCA一般不保留噪声，因此也避免了阈值选择不当情况下造成的对象丢弃情况。
（1）MDCA的基本思路：寻找最高密度的对象和它所在的稠密区域；MDCA算法在原理上来讲，和密度的定义没有关系，采用任意一种密度定义公式均可，一般情况下采用DBSCAN算法中的密度定义方式。
（2）MDCA算法聚类过程步骤如下：
一、将数据集划分为基本簇。
1、对数据集X选取最大密度点Pmax，形成以最大密度点为核心的新簇Ci，按照距离排序计算出序列Spmax,对序列的前M个样本数据进行循环判断，如果节点的密度大于等于density0，那么将当前节点添加Ci中；
2、循环处理剩下的数据集X，选择最大密度点Pmax，并构建基本簇Ci+1，直到X中剩余的样本数据的密度均小于density0。
二、使用凝聚层次聚类的思想，合并较近的基本簇，得到最终的簇划分。
在所有簇中选择距离最近的两个簇进行合并，合并要求是：簇间距小于等于dist0,如果所有簇中没有簇间距小于dist0的时候，结束合并操作。
三、处理剩余节点，归入最近的簇。
最常用、最简单的方式是：将剩余样本对象归入到最近的簇

谱聚类

谱聚类概述
谱聚类是从图论中演化出来的算法，后来在聚类中得到了广泛的应用。它的主要思想是把所有的数据看做空间中的点，这些点之间可以用边连接起来。距离较远的两个点之间的边权重值较低，而距离较近的两个点之间的边权重值较高，通过对所有数据点组成的图进行切图，让切图后不同的子图间边权重和尽可能的低，而子图内的边权重和尽可能的高，从而达到聚类的目的。

参考链接：
无监督学习-主成分分析和聚类分析
 Introduction to Unsupervised Learning
无监督学习 | 层次聚类之凝聚聚类原理及Sklearn实现
 无监督学习中的无监督特征学习、聚类和密度估计
 机器学习笔记6——无监督学习（聚类算法）
聚类算法（无监督算法）
【无监督学习】 DBSCAN聚类算法原理介绍，以及代码实现
 【纯干货】无监督核心聚类算法
 层次聚类--凝聚（自底向上）和分裂（自顶向下）
11 聚类算法 - 密度聚类 - DBSCAN、MDCA
谱聚类（spectral clustering）原理总结

无监督学习/聚类