聚类学习是按照某种特定标准(如距离等)把一个数据集划分为不同的类或簇（子集），使得同一个簇内的数据对象的相似性尽可能大，不在同一个簇中的数据对象的差异性也尽可能地大（即聚类后同一类的数据尽可能聚集到一起，不同类数据尽量分离）。这些划分后的概念对于聚类算法而言是未知的，簇所对应的概念语义需要我们自行接着探索，所以经常聚类被用作分类等其他学习任务的前驱过程。

二、聚类性能度量

整体希望簇内相似度高，簇间相似度低。

1、分类

聚类性能度量分为两类：
一类是将聚类结果与某个“参考模型”进行比较，称为“外部指标”；
一类是直接考察聚类结果而不利用任何参考模型，称为“内部指标”。

2、符号假设

数据集 $D = \left \{ x_{1},x_{2},...,x_{m} \right \}$ ；聚类得到的簇划分为 $C = \left \{ C_{1},C_{2},...,C_{k} \right \}$ ；参考模型给出的簇划分为 $C^{*} = \left \{ C_{1}^{*},C_{2}^{*},...,C_{s}^{*} \right \}$ ；相应的， $\lambda$ 与 $\lambda ^{*}$ 分别为 $C$ 和 $C^{*}$ 对应的簇标记向量。

将样本两两配对考虑，得：

$\left.a=|S S|, \quad S S=\left\{\left(\boldsymbol{x}_{i}, \boldsymbol{x}_{j}\right) \mid \lambda_{i}=\lambda_{j}, \lambda_{i}^{*}=\lambda_{j}^{*}, i<j\right)\right\}$

$\left.b=|S D|, \quad S D=\left\{\left(\boldsymbol{x}_{i}, \boldsymbol{x}_{j}\right) \mid \lambda_{i}=\lambda_{j}, \lambda_{i}^{*} \neq \lambda_{j}^{*}, i<j\right)\right\}$

$\left.c=|D S|, \quad D S=\left\{\left(\boldsymbol{x}_{i}, \boldsymbol{x}_{j}\right) \mid \lambda_{i} \neq \lambda_{j}, \lambda_{i}^{*}=\lambda_{j}^{*}, i<j\right)\right\}$

$\left.d=|D D|, \quad D D=\left\{\left(\boldsymbol{x}_{i}, \boldsymbol{x}_{j}\right) \mid \lambda_{i} \neq \lambda_{j}, \lambda_{i}^{*} \neq \lambda_{j}^{*}, i<j\right)\right\}$

那么有 $a+b+c+d = \frac{m(m-1)}{2}$ ；m为样本总数。

3、外部指标

（1）Jaccard系数（JC）

$JC = \frac{a}{a+b+c}$ ，取值为[0,1]。

意义：在所有判定为同一类中，两种方法都判定为同一类的比例。

用于比较聚类结果与参考模型得出的结果之间的相似性与差异性。Jaccard系数值越大，两者的相似度越高。

JC的原始定义：（其中A，B是两个不同的集合）

（2）FM指数（FMI）

$FMI = \sqrt{\frac{a}{a+b} \cdot \frac{a}{a+c}}$ ，取值为[0,1]。

从两者预测的准确率的角度入手，进行对比。值越大说明两者的预测越接近，相似度越高。

（3）Rand指数（RI）

$RI = \frac{2(a+d)}{m(m-1)}$ ，取值为[0,1]。

描述两种方法都判定相同在所有预测中的占比，值越大，相似度越高。

4、有关簇的距离的定义

（1）簇C内样本间的平均距离

$\operatorname{avg}(C)=\frac{2}{|C|(|C|-1)} \sum_{1 \leqslant i<j \leqslant|C|} \operatorname{dist}\left(\boldsymbol{x}_{i}, \boldsymbol{x}_{j}\right)$

（2）簇C内样本间的最远距离

$\operatorname{diam}(C)=\max _{1 \leqslant i<j \leqslant|C|} \operatorname{dist}\left(\boldsymbol{x}_{i}, \boldsymbol{x}_{j}\right)$

（3）簇 $C_{i}$ 与簇 $C_{j}$ 最近样本间的距离

$d_{\min }\left(C_{i}, C_{j}\right)=\min _{\boldsymbol{x}_{i} \in C_{i}, \boldsymbol{x}_{j} \in C_{j}} \operatorname{dist}\left(\boldsymbol{x}_{i}, \boldsymbol{x}_{j}\right)$

（4）簇 $C_{i}$ 与簇 $C_{j}$ 中心点间的距离

$d_{\text {cen }}\left(C_{i}, C_{j}\right)=\operatorname{dist}\left(\boldsymbol{\mu}_{i}, \boldsymbol{\mu}_{j}\right)$

其中，u代表簇的中心点。

5、内部指标

（1）DB指数（DBI）

$\mathrm{DBI}=\frac{1}{k} \sum_{i=1}^{k} \max _{j \neq i}\left(\frac{\operatorname{avg}\left(C_{i}\right)+\operatorname{avg}\left(C_{j}\right)}{d_{\text {cen }}\left(\boldsymbol{\mu}_{i}, \boldsymbol{\mu}_{j}\right)}\right)$

其意义为：任意两个簇的簇内平均距离之和与它们簇中心间距离的比值的最大值。

值越小，代表聚类结果的簇间距离越大，而簇内距离越小。

（2）Dunn指数（DI）

$\mathrm{DI}=\min _{1 \leqslant i \leqslant k}\left\{\min _{j \neq i}\left(\frac{d_{\min }\left(C_{i}, C_{j}\right)}{\max _{1 \leqslant l \leqslant k} \operatorname{diam}\left(C_{l}\right)}\right)\right\}$

值越大，簇间距离越大，簇内距离越小。

5、实际场景中的聚类分数定义

（1）SSE—误差平方和

每类中的点到对应簇中心的欧氏距离平方的和，值越小，聚类效果越好

只体现了衡量簇内样本的距离远近。

（2）轮廓系数法

该方法结合了聚类的凝聚度和分离度

a(i)：样本 i 到所有它属于的同一簇中其它点的距离的平均值，称为凝聚度；

$a(i)=\frac{1}{C}\sum_{p\in C}^{}(p-x_{i})^{2}$

b(i)：样本 i 到所有它不属于的簇内所有点的平均距离的最小值，称为分离度；

样本i的轮廓系数为：

取值为[-1,1]，越接近1聚类效果越好（即簇内样本的距离越近，簇间样本距离越远）。

对于衡量整个聚类体系，则采取取所有点的轮廓系数的平均值。

同时考虑到簇内/簇间距离远近。

（3）Calinski-Harbasz Score（CH）

它是通过评估类之间方差和类内方差来计算得分的。

其中k代表聚类类别数，N代表全部数据数目。 $SS_{B}$ 是类间方差矩阵， $SS_{W}$ 是类内方差矩阵。

三、距离度量

在聚类中，距离被当作一种描述相似度大小的工具，距离越大，相似度越小。相似度度量距离是“非度量距离”（不满足直递性）。

1、闵可夫斯基距离

适用于有序属性。

$D(x, y)=\left(\sum_{u=1}^{n}\left|x_{u}-y_{u}\right|^{p}\right)^{\frac{1}{p}}$

其中p>=1。

（1）欧氏距离（p=2）

$\mathrm{d}(\mathrm{x}, \mathrm{y})=\sqrt{\sum_{\mathrm{i}=1}^{\mathrm{n}}\left(\mathrm{x}_{\mathrm{i}}-\mathrm{y}_{\mathrm{i}}\right)^{2}}$

表明的是空间点间的最短距离。

十分适合低维数据

缺点：尽管他很常用，但欧式距离并不是尺度不变的，这意味着所计算的距离可能会根据特征的单位发生倾斜。通常，在使用欧式距离度量之前，需要对数据进行归一化处理。此外，随着数据维数的增加，欧氏距离的作用也就越小。这与维数灾难有关。

（2）曼哈顿距离（p=1）

$\mathrm{d}(\mathrm{x}, \mathrm{y})=\sum_{\mathrm{i}=1}^{\mathrm{n}}\left|\mathrm{x}_{\mathrm{i}}-\mathrm{y}_{\mathrm{i}}\right|$

表明的是两个点在标准坐标系上的绝对轴距总和。

缺点：尽管曼哈顿距离在高维数据中似乎可以工作，但它比欧式距离直观性差，尤其是在高维数据中使用时。

（3）切比雪夫距离（p=无穷）

$D(p,q) = \lim _{k \rightarrow \infty}\left(\sum_{i=1}^{n}\left|p_{i}-q_{i}\right|^{k}\right)^{1 / k}$

若在二维空间中则被简化为：

$D_{\text {Chebyshev }}(p, q)=\max _{i}\left(\left|p_{i}-q_{i}\right|\right)$

切比雪夫距离定义为两个向量在任意坐标维度上的最大差值。换句话说，它就是沿着一个轴的最大距离。

缺点：切比雪夫距离通常用于特定的用例（比如一个方块移动到另一个方块所需的最小移动次数），这使得它很难像欧氏距离或余弦相似度那样作为通用的距离度量。

2、VDM

该距离针对于无序属性（比如：{飞机，火车，汽车}），不能简单的转化为{1，2，3}，因为原先的属性间没有明显的大小远近等“序”的关系，而是转化为向量处理，比如转化为{[1,0,0],[0,1,0],[0,0,1]}。

描述属性u上两个离散值a与b间的距离

$\operatorname{VDM}_{p}(a, b)=\sum^{k}_{i=1}\left|\frac{m_{u, a, i}}{m_{u, a}}-\frac{m_{u, b, i}}{m_{u, b}}\right|^{p}$

其中 $m_{u,a}$ 表示在属性u上取值为a的样本数； $m_{u,a,i}$ 表示在第i个样本簇中在属性u上取值为a的样本数；k为样本簇数。

3、MinkovDM距离

针对混合属性（有序+无序）

即将闵可夫斯基距离和VDM结合在一起，令有序属性排列在无序属性之前，则有

$\operatorname{MinkovDM}_{p}\left(\boldsymbol{x}_{i}, \boldsymbol{x}_{j}\right)=\left(\sum_{u=1}^{n_{c}}\left|x_{i u}-x_{j u}\right|^{p}+\sum_{u=n_{c}+1}^{n} \operatorname{VDM}_{p}\left(x_{i u}, x_{j u}\right)\right)^{\frac{1}{p}}$

其中有序属性个数为 $n_{c}$ ，无序属性个数为 $n-n_{c}$ 。

4、加权距离

上述的方法都是基于对于每个属性而言重要性一致，但是有些情况下我们可以获悉哪些属性权重更大，哪些更小，因此可以对于不同属性进行加权处理以作距离度量。

四、原型聚类

1、k-means聚类

（1）算法思想

k-means算法属于无监督学习。

补：

监督学习：输入的数据有标签；

无监督学习：输入的数据没有标签；

K-Means聚类算法是一种迭代求解的聚类分析算法。

算法思想是：我们需要随机选择K个对象作为初始的聚类中心，然后计算每个对象和各个聚类中心之间的距离，然后将每个对象分配给距离它最近的聚类中心。聚类中心及分配给它们的对象就代表着一个聚类。每分配一个样本，聚类的中心会根据聚类中现有的对象被重新计算。此过程将不断重复，直至满足设置的终止条件。

（2）算法步骤

A. 首先需要随机初始化k个聚类中心（其中，n为样本数）

B. 然后通过计算每一个样本到每一个聚类中心的欧式距离，如下式所示：

其中， $X_{i}$ 表示第i个样本； $C_{j}$ 表示第j个聚类中心； $X_{it}$ 表示第i个样本的第t个属性； $C_{jt}$ 表示第j个聚类中心的第t个属性，m为属性种类数。

C. 然后依次比较每个样本到每一个聚类中心的距离，将样本分配到距离最近的聚类中心的类簇中，得到k个类簇

D. 根据不同的类簇，更新每个类簇的聚类中心，计算公式如下：

其中：

$C_{t}$ 表示第t个聚类的中心；

$|S_{t}|$ 表示第t个类簇中样本的个数；

$X_{i}$ 表示第t个类簇中第i个样本。

E. 重复步骤B到D，直至聚类中心不再改变或者改变幅度很小（新计算出来的质心和原来的质心之间的距离小于某一个设置的阈值），得到最终的聚类结果。

（3）k值选择

k值决定了将数据划分成多少个簇类。k个初始化的质心的位置选择对最后的聚类结果和整个大代码的运行时间都有非常大的影响。因此需要选择合适的k个质心

一般k值是通过先验知识来选取的。如果没有什么先验知识，我们可以通过交叉验证的方式来选择一个合适的k值

（4）python实现k-means算法


import matplotlib.pyplot as plt
from sklearn.datasets import make_blobs#为了生成数据集
from sklearn.cluster import KMeans
 
# X为样本特征,共1000个样本，每个样本2个特征，对应x和y轴，共2个簇，
# 簇中心在[-1,-1],[1,1], 簇方差分别为[0.4,0.8]
X, _ = make_blobs(n_samples=1000, n_features=2, centers=[[-1, -1], [1, 1]],
                  cluster_std=[0.4, 0.8], random_state=4)
                  
#k-means算法聚类分类结果
y_pred = KMeans(n_clusters=2, random_state=9).fit_predict(X)
plt.scatter(X[:, 0], X[:, 1], c=y_pred)
plt.show()

结果：

注：如果非二，三维数据，无法可视化，可以采取将预测的簇标签输出，再以这些标签来反推簇的性质。

（5）优缺点

A、优点

原理简单，易实现
可解释度较强

B、缺点

K值难以确定
局部最优
对噪声点和异常点敏感
要求样本存在均值的意义（限定数据种类，比如说：一些性质的有无就不太好用这个方法，难以表示）
聚类效果依赖于聚类中心的初始化
对于非凸数据集或类别规模差异太大的数据效果不好（见下面与密度聚类的对比）

2、学习向量量化（LVQ）

（1）算法思想

LVQ与一般聚类算法思路类似，只是LVQ假设数据样本带有类别标记，学习过程利用样本的这些监督信息来辅助聚类。

（2）算法步骤

A、输入数据集： $D=\left(x_{1}, y_{1}\right),\left(x_{2}, y_{2}\right), \ldots,\left(x_{m}, y_{m}\right)$ ，原型向量个数为q，各原型向量预设的类别标记 $t_{1}, t_{2}, \ldots, t_{q}$ ，学习率为 $\eta \in(0,1)$ ；

B、初始化一组原型向量 $p_{1}, p_{2}, \ldots, p_{q}$ ；

C、从样本集D随机选取样本 $\left(x_{j}, y_{j}\right)$ ，计算样本 $x_{j}$ 与 $p_{i}(1 \leq i \leq q)$ 的距离： $d_{j i}=\left\|x_{j}-p_{i}\right\|_{2}$ ；

D、找出与 $x_{j}$ 距离最近的原型向量 $p_{i^{*}}$ ， $i^{*}=\operatorname{argmin}{ }_{i \in\{1,2, \ldots, q\}} d_{j i}$ ；

E、如果 $y_{j}=t_{i^{*}}$ ，那么 $p^{\prime}=p_{i^{*}}+\eta\left(x_{j}-p_{i^{*}}\right)$ ；否则， $p^{\prime}=p_{i^{*}}-\eta\left(x_{j}-p_{i^{*}}\right)$ ，将原型向量 $p_{i^{*}}$ 更新为 $p^{\prime}$ ；

F、重复C到E步骤，直至满足停止条件，输出原型向量 $p_{1}, p_{2}, \ldots, p_{q}$

（3）python实现LVQ


from sklearn import datasets
 
from sklearn.model_selection import train_test_split
from sklearn.metrics import accuracy_score
from sklearn_lvq import LgmlvqModel
 
iris = datasets.load_iris()
x = iris.data
y = iris.target
 
train_x,test_x,train_y,test_y = train_test_split(x,y,test_size=0.3,random_state=0)
 
model = LgmlvqModel()
model.fit(train_x,train_y)
pred = model.predict(test_x)
acc = accuracy_score(test_y, pred)
print(acc)

结果：

（4）优缺点

与k-means类似。

3、高斯混合聚类

（1）算法思想与推导

高斯混合聚类采用概率模型来表述聚类原型。

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/一键难忘520/article/detail/990139

机器学习之聚类_机器学习聚类

一、聚类介绍

二、聚类性能度量

1、分类

2、符号假设

3、外部指标

（1）Jaccard系数（JC）

（2）FM指数（FMI）

（3）Rand指数（RI）

4、有关簇的距离的定义

（1）簇C内样本间的平均距离

（2）簇C内样本间的最远距离

（3）簇与簇最近样本间的距离

（4）簇与簇中心点间的距离

5、内部指标

（1）DB指数（DBI）

（2）Dunn指数（DI）

5、实际场景中的聚类分数定义

（1）SSE—误差平方和

（2）轮廓系数法

（3）Calinski-Harbasz Score（CH）

三、距离度量

1、闵可夫斯基距离

（1）欧氏距离（p=2）

（2）曼哈顿距离（p=1）

（3）切比雪夫距离（p=无穷）

2、VDM

3、MinkovDM距离

4、加权距离

四、原型聚类

1、k-means聚类

（1）算法思想

（2）算法步骤

（3）k值选择

（4）python实现k-means算法

（5）优缺点

2、学习向量量化（LVQ）

（1）算法思想

（2）算法步骤

（3）python实现LVQ

（4）优缺点

3、高斯混合聚类

（1）算法思想与推导

（3）簇 $C_{i}$ 与簇 $C_{j}$ 最近样本间的距离

（4）簇 $C_{i}$ 与簇 $C_{j}$ 中心点间的距离