机器学习——第九章 聚类
目录
9.1 聚类任务
9.2 性能度量
9.3 距离计算
9.4 原型聚类
9.4.1 均值算法
9.4.2 学习向量量化
9.4.3 高斯混合聚类
9.5 密度聚类
9.6 层次聚类
9.1 聚类任务
聚类试图将数据集中的样本划分为若干个通常是不相交的子集，每个子集称为一个“簇”，通过这样的划分，每个簇可能对应于一些潜在的概念（类别），这些概念对聚类算法而言事先是未知的，聚类过程仅能自动形成簇结构，簇所对应的概念语义需由使用者来把握和命名。
聚类既能作为一个单独过程，用于寻找数据内在的分布结构，也可作为分类等其他学习任务的前驱过程。例如，在一些商业应用中需对新用户的类型进行判别，但定义“用户类别”对商家来说却可能不太容易，此时往往可先对用户数据进行聚类，根据聚类结果将每个簇定义为一个类，然后再基于这些类训练分类模型，用于判别新用户的类型。
9.2 性能度量
对聚类结果来说，通过某种性能度量可以评估其好坏，同时也可以直接将其作为聚类过程的优化目标，从而更好地得到符合要求的聚类结果，最后希望聚类结果的“簇内相似度”高且“簇间相似度”低。
外部指标是将聚类结果与某个专家给定的或者公认的参考模型进行比较，衡量两者之间的一致性。
常见的外部指标有：
- Jaccard系数：计算聚类结果与参考模型之间的交集与并集的比值，值越大表示一致性越高。
\begin{equation}\mathrm{JC}=\frac{a}{a+b+c}\end{equation}
- FM指数：计算聚类结果与参考模型之间的精确度和召回率的调和平均数，值越大表示一致性越高。
\begin{equation}\mathrm{FMI}=\sqrt{\frac{a}{a+b}\cdot\frac{a}{a+c}}\end{equation}
- Rand指数：计算聚类结果与参考模型之间的一致决策和不一致决策的比值，值越大表示一致性越高。
\begin{equation}\mathrm{RI}=\frac{2(a+d)}{m(m-1)}\end{equation}
- NMI指数：计算聚类结果与参考模型之间的互信息与熵的比值，值越大表示一致性越高。
内部指标是直接考察聚类结果本身，不需要任何参考模型。
常见的内部指标有：
- 紧密度：反映一个簇内样本点之间的相似程度，值越大表示簇内越紧密。
- 分割度：反映一个簇与其他簇之间的差异程度，值越大表示簇间越分离。
- SSE指数：计算所有样本点与其所属簇中心之间的距离平方和，值越小表示聚类效果越好。
- 轮廓系数：计算每个样本点的簇内相似度与簇间相似度之差与最大值之比，值越大表示聚类效果越好。
- CH指数：计算所有样本点与全局中心之间的距离平方和与所有样本点与其所属簇中心之间的距离平方和之比，值越大表示聚类效果越好。
- DB指数：计算每个簇内样本点与其所属簇中心之间的距离平均值与每两个簇中心之间的距离之比的最大值，值越小表示聚类效果越好。
\begin{equation}\mathrm{DBI}=\frac{1}{k}\sum_{i=1}^{k}\max_{j\neq i}\left(\frac{\mathrm{avg}(C_{i})+\mathrm{avg}(C_{j})}{d_{\mathrm{cen}}(\mu_{i},\mu_{j})}\right)\end{equation}
9.3 距离计算
对函数dist(. ， .)，若它是一个"距离度量" (distance measure) ，则需满足一些基本性质:
- 非负性:\( \begin{equation}\mathrm{dist}(\boldsymbol{x}_i,\boldsymbol{x}_j)\geqslant0 \end{equation} \)；
- 同一性:\( \begin{equation}\mathrm{dist}(\boldsymbol{x}_i,\boldsymbol{x}_j)=0 \text{当且仅当} \boldsymbol{x}_i=\boldsymbol{x}_j \end{equation}\)；
- 对称性: \(\begin{equation}\mathrm{dist}(\boldsymbol{x}_{i},\boldsymbol{x}_{j})=\mathrm{dist}(\boldsymbol{x}_{j},\boldsymbol{x}_{i})\end{equation}\)；
- 直递性:\(\begin{equation}\mathrm{dist}(\boldsymbol{x}_{i},\boldsymbol{x}_{j})\leqslant\mathrm{dist}(\boldsymbol{x}_{i},\boldsymbol{x}_{k})+\mathrm{dist}(\boldsymbol{x}_{k},\boldsymbol{x}_{j})\end{equation} \)
给定样本\(x_{i}=(x_{i1};x_{i2};\ldots;x_{in})\)与\(\boldsymbol{x}_{j}=(x_{j1};x_{j2};\ldots;x_{jn})\)最常用的是"闵可夫斯基距离" (Minkowski distance)：
\(\mathrm{dist}_{\mathrm{mk}}(\boldsymbol{x}_i,\boldsymbol{x}_j)=\left(\sum_{u=1}^n|x_{iu}-x_{ju}|^p\right)^{\frac{1}{p}}\)
- p=2时，闵可夫斯基距离即欧氏距离(Euclidean distance)
\(\mathrm{dist}_{\mathrm{ed}}(x_{i},x_{j})=||x_{i}-x_{j}||_{2}=\sqrt{\sum^{n}|x_{iu}-x_{ju}|^{2}}\)
欧式距离在机器学习中有很多作用和应用场景，例如：
- 在聚类算法中，可以用欧式距离来衡量样本之间的相似度，例如K-means算法就是基于欧式距离的最小化来划分簇。
- 在回归分析中，可以用欧式距离来衡量预测值和真实值之间的误差，例如最小二乘法就是基于欧式距离的最小化来拟合模型。
- 在降维算法中，可以用欧式距离来衡量数据在低维空间中的保持程度，例如主成分分析就是基于欧式距离的最大化来提取主成分。
- p=1时，闵可夫斯基距离即曼哈顿距离(Manhattan distance)
\(\mathrm{dist}_{\mathrm{man}}(\boldsymbol{x}_i,\boldsymbol{x}_j)=||\boldsymbol{x}_i-\boldsymbol{x}_j||_1=\sum_{u=1}^n|x_{iu}-x_{ju}|\)
曼哈顿距离在机器学习中也有很多作用和应用场景，例如：
- 在聚类算法中，可以用曼哈顿距离来衡量样本之间的相似度，例如K-medoids算法就是基于曼哈顿距离的最小化来划分簇。
- 在回归分析中，可以用曼哈顿距离来衡量预测值和真实值之间的误差，例如最小绝对偏差法就是基于曼哈顿距离的最小化来拟合模型。
- 在计算机图形学中，可以用曼哈顿距离来优化浮点运算的速度和精度，例如在屏幕上绘制两点之间的直线时，可以用曼哈顿距离代替欧式距离来避免浮点运算。
9.4 原型聚类
原型聚类亦称“基于原型的聚类”，此类算法假设聚类结构能通过一组原型刻画，在现实聚类任务中极为常用。通常情形下，算法先对原型进行初始化，然后对原型进行迭代更新求解。
9.4.1 
均值算法
给定样本集\(D=\{x_1,x_2,...,x_m\}\)，“均值”算法针对聚类所得簇划分\(C=\{C_{1},C_{2},...,C_{k}\}\)最小化平方误差
\(E=\sum_{i=1}^k\sum_{x\in C_i}\left\|x-\mu_i\right\|_2^2\)
其中\(\mu_{i} = \frac{1}{|C_{i}|} \sum_{x\in C_{i}} x\)是簇\(C_{i}\)的均值向量，上述式子在一定程度上刻画了簇内样本围绕簇均值向量的紧密程度，E值越小则簇内样本相似度越高，同时k均值算法采用了贪心策略，通过迭代优化来近似求解。
算法步骤：
- 随机初始化K个簇的中心点。
- 将每个样本分配到最近的簇。
- 更新每个簇的中心点。
- 重复2-3步骤，直到收敛或达到预定迭代次数。
K均值聚类是一种简单而有效的聚类算法，特别适用于对数据集进行分组的场景。然而，它对初始值和K值的选择较为敏感，因此在使用时需要考虑这些因素以获得更好的聚类效果。
# 导入必要的库
import numpy as np
import matplotlib.pyplot as plt
from sklearn.cluster import KMeans
from sklearn.datasets import make_blobs# 生成模拟数据
data, labels = make_blobs(n_samples=300, centers=4, random_state=42)# 创建K均值聚类模型
kmeans = KMeans(n_clusters=4, random_state=42)# 拟合模型
kmeans.fit(data)# 获取聚类结果
predicted_labels = kmeans.labels_# 获取聚类中心
centroids = kmeans.cluster_centers_# 可视化聚类结果和聚类中心
plt.scatter(data[:, 0], data[:, 1], c=predicted_labels, cmap='viridis', alpha=0.5)
plt.scatter(centroids[:, 0], centroids[:, 1], marker='X', s=200, linewidths=0.2, color='red')
plt.title('K-Means Clustering')
plt.xlabel('Feature 1')
plt.ylabel('Feature 2')
plt.show()
9.4.2 学习向量量化
学习向量量化（LVQ）是一种用于模式分类的有监督的学习算法，也是一种原型聚类算法。它的基本思想是通过对原型向量进行迭代更新，使得同类样本的原型向量靠近，异类样本的原型向量远离。
学习向量量化的过程可以分为以下几个步骤：
- 初始化一组原型向量，每个原型向量代表一个类别，可以随机选择或者根据先验知识指定。
- 从样本集中随机抽取一个样本，计算它与所有原型向量的距离，找出距离最近的原型向量。
- 如果样本的类别标记与原型向量的类别标记一致，则将原型向量向样本方向移动一小步，以增加同类样本的相似度；如果不一致，则将原型向量远离样本方向移动一小步，以减少异类样本的相似度。
- 重复上述步骤，直到达到预设的迭代次数或者原型向量不再发生变化。
学习向量量化与k均值算法的异同如下：
- 相同点：都是通过调整一组原型向量来刻画聚类结构，都是采用贪心策略进行迭代优化，都需要指定原型向量的个数。
- 不同点：k均值算法是无监督的，不利用样本的类别信息，而LVQ算法是有监督的，利用样本的类别信息来辅助聚类；k均值算法使用簇内平方误差作为优化目标，而LVQ算法使用分类误差作为优化目标；k均值算法每次更新一个簇的均值向量，而LVQ算法每次更新一个样本最近的原型向量。
9.4.3 高斯混合聚类
与k均值、LVQ用原型向量来刻画聚类结构不同，高斯混合聚类采用概率模型来表达聚类原型。高斯混合聚类的目标是找到一组高斯分布的参数，使得样本数据能够用这些分布的线性组合来近似表示，高斯混合聚类的过程可以概括为以下几个步骤：
- 初始化一组高斯分布的参数，包括每个分布的均值向量、协方差矩阵和混合系数，可以随机选择或者根据先验知识指定。
- 从样本集中抽取一个样本，计算它属于每个高斯分布的后验概率，即根据贝叶斯公式计算每个分布的条件概率乘以混合系数，并归一化。
- 根据每个样本的后验概率，更新每个高斯分布的参数，包括均值向量、协方差矩阵和混合系数，使得样本的对数似然函数最大化。
- 重复上述步骤，直到达到预设的迭代次数或者参数不再发生变化。
9.5 密度聚类
密度聚类亦称“基于密度的聚类”，此类算法假设聚类结构通过样本分别的紧密程度确定。通常情况下，密度聚类算法从样本密度的角度来考察样本之间的可连接性，并基于可连接样本不断扩展聚类簇以获得最终的聚类结果。
DBSCAN是一种著名的密度聚类算法，它基于一组“领域”参数\((\varepsilon,MinPts)\)来刻画样本分布的紧密程度，给定数据集\(D=\{x_1,x_2,...,x_{m}\}\)，定义下面这几个概念：
-领域：对\(x_{j}\in D\)，其
- 核心对象：若\(x_j\)的
- 密度直达：若\(x_j\)位于\(x_i\)的
- 密度可达：对\(x_i\)与\(x_j\)，若存在样本序列\(p_{1},p_{2},...,p_{n}\)，其中\(p_1 = x_i ,p_n = x_j\)且\(p_{i+1}\)由\(p_{i}\)密度直达，则称\(x_i\)由\(x_j\)密度可达；
- 密度相连：对\(x_i\)与\(x_j\)，若存在\(x_k\)使得\(x_i\)与\(x_j\)均由\(x_k\)密度可达，则称\(x_i\)与\(x_j\)密度相连。
DBSCAN的目标是根据点之间的密度相似性，将数据划分为不同的簇，并能够识别出噪声点。，DBSCAN的过程可以概括为以下几个步骤：
- 选择一个未被访问过的点，计算它的
- 如果
- 如果
- 对于每个核心点，检查它的
- 重复上述步骤，直到所有的点都被访问过或者被分配到某个聚类簇中。
算法特点:
- 核心点： 在ε邻域内包含至少MinPts个样本的点。
- 边界点： 不是核心点，但在某个核心点的ε邻域内。
- 噪音点： 既不是核心点也不是边界点。
import numpy as np
import matplotlib.pyplot as plt
from sklearn.datasets import make_moons
from sklearn.cluster import DBSCAN# 生成月亮形状的数据
data, _ = make_moons(n_samples=200, noise=0.05, random_state=42)# 创建DBSCAN聚类模型
dbscan = DBSCAN(eps=0.3, min_samples=5)# 拟合模型
dbscan.fit(data)# 获取聚类结果
predicted_labels = dbscan.labels_# 可视化聚类结果
plt.scatter(data[:, 0], data[:, 1], c=predicted_labels, cmap='viridis', alpha=0.7)
plt.title('DBSCAN Clustering (Arbitrary Shape)')
plt.xlabel('Feature 1')
plt.ylabel('Feature 2')
plt.show()
9.6 层次聚类
层次聚类试图在不同层次对数据集进行划分，从而形成树形的聚类结构，数据集的划分可采用“自底向上”的聚合策略，也可采用“自顶向下”的分拆策略。AGNES是一种采用自底向上聚合策略的层次聚类算法，它先将数据集中的每个样本看作一个初始聚类簇，然后在算法运行的每一步中找出距离最近的两个聚类簇进行合并，该过程不断重复，直到达到预设的聚类簇个数，所以关键在于如何计算聚类簇之间的距离。
AGNES算法需要指定一个合并簇的准则，即如何计算簇之间的距离。常用的有以下几种方法：
- 最小距离法（Single Linkage）：取两个簇中距离最近的两个样本的距离作为这两个簇的距离。这种方法容易产生长链效应，即将不相似的簇连接在一起。
- 最大距离法（Complete Linkage）：取两个簇中距离最远的两个样本的距离作为这两个簇的距离。这种方法容易产生紧凑的球形簇，但对噪声敏感。
- 平均距离法（Average Linkage）：取两个簇中所有样本两两之间的距离的平均值作为这两个簇的距离。这种方法相对平衡，能够适应不同形状和大小的簇。
- 中心距离法（Centroid Linkage）：取两个簇中各自样本均值点之间的距离作为这两个簇的距离。这种方法类似于K-Means算法，但可能出现反向现象，即合并后导致总距离增大。
import numpy as np
import matplotlib.pyplot as plt
from sklearn.datasets import make_blobs
from sklearn.cluster import AgglomerativeClustering
from scipy.cluster.hierarchy import dendrogram, linkage# 生成模拟数据
data, labels = make_blobs(n_samples=300, centers=4, random_state=42)# 创建凝聚型层次聚类模型
agg_clustering = AgglomerativeClustering(n_clusters=4, linkage='ward')# 拟合模型
agg_clustering.fit(data)# 获取聚类结果
predicted_labels = agg_clustering.labels_# 可视化聚类结果
plt.scatter(data[:, 0], data[:, 1], c=predicted_labels, cmap='viridis', alpha=0.5)
plt.title('Agglomerative Clustering')
plt.xlabel('Feature 1')
plt.ylabel('Feature 2')
plt.show()# 绘制层次聚类的树状图
linked = linkage(data, 'ward')
dendrogram(linked, orientation='top', distance_sort='descending', show_leaf_counts=True)
plt.title('Hierarchical Clustering Dendrogram')
plt.xlabel('Sample Index', rotation = 70)
plt.ylabel('Distance')
plt.show()
