如果这篇文章对你有一点小小的帮助,请给个关注,点个赞喔,我会非常开心的~
0. 前言
无监督学习意味着样本的标记信息是未知的,目标是揭示数据的内在规律。
聚类试图将数据集划分为不同的子集,称为“簇”。
1. 性能度量
聚类应达到簇内相似度高,簇间相似度低。
1.1. 外部指标
外部指标意味着将聚类结果与某个参考模型比较。
给出数据集D,聚类结果簇划分C,参考模型簇划分C∗,以及对应簇标记λ, λ∗,定义:
a=∣SS∣, SS={(xi,xj)∣λi=λj,λi∗=λj∗,i<j}b=∣SD∣, SD={(xi,xj)∣λi=λj,λi∗̸=λj∗,i<j}c=∣DS∣, DS={(xi,xj)∣λi̸=λj,λi∗=λj∗,i<j}d=∣DD∣, DD={(xi,xj)∣λi̸=λj,λi∗̸=λj∗,i<j}
名称 |
公式 |
指标 |
Jaccard系数 |
JC=a+b+ca |
越大越好 |
FM指数 |
FMI=a+ba⋅a+ca |
越大越好 |
Rand指数 |
RI=m(m−1)2(a+d) |
越大越好 |
1.2. 内部指标
内部指标意味着直接考察聚类结果。
考虑聚类结果C,定义:
avg(C)=∣C∣(∣C∣−1)21⩽i<j⩽∣C∣∑dist(xi,xj)diam(C)=1⩽i<j⩽∣C∣maxdist(xi,xj)dmin(Ci,Cj)=xi∈Ci,xj∈Cjmindist(xi,xj)dcen(Ci,Cj)=dist(μi,μj)
名称 |
公式 |
指标 |
DB指数 |
DBI=k1i=1∑kj̸=imax(dcen(Ci,Cj)avg(Ci)+avg(Cj)) |
越小越好 |
Dunn指数 |
DI=i⩽i⩽kmin{j̸=imin(max1⩽l⩽kdiam(Cl)dmin(Ci,Cj))} |
越大越好 |
2. 距离计算
距离计算是指dist(xi,xj)。
对于有序的属性:
名称 |
公式 |
备注 |
闵可夫斯基距离 |
dist(xi,xj)=(u=1∑n∣xiu−xju∣p)p1 |
|
欧氏距离 |
dist(xi,xj)=u=1∑n∣xiu−xju∣2 |
p=2 |
曼哈顿距离 |
dist(xi,xj)=u=1∑n∣xiu−xju∣ |
p=1 |
对于无序的属性,令mu,a表示属性u上取值为a的样本数,mu,a,i表示第i个样本簇属性u上取值为a的样本数,则对于属性u上的两个离散属性,有:
VDMp(a,b)=i=1∑k∣mu,amu,a,i−mu,bmu,b,i∣p
3. k-means算法
k-means通过迭代循环两个过程:根据簇中心将每个样本划分入最近的簇,重新计算簇中心。
算法如下图所示(图源:机器学习):
二分k-means:先指定一个簇中心,在这个簇中使用k-means,k=2,将簇一分为二,再选定一个簇,在这个簇中使用k-means,如此循环。
4. 学习向量量化
学习向量量化(Learning Vector Quantization)假设数据样本带有类别标记,利用这些监督信息来辅助聚类。
算法如下图所示(图源:机器学习):
5. 高斯混合聚类
高斯混合聚类采用概率模型来表达聚类,定义高斯混合分布:
pM(x)=i=1∑kαi⋅p(x∣μi,Σi)
其中,该分布有k个混合成分,αi是混合系数,表示选择这个成分的概率。
采用EM算法推导高斯混合模型,首先根据样本计算对应的高斯混合成分的后验概率:
γji=pM(zj=i∣xj)=∑l=1kαl⋅p(xj∣μl,Σl)αi⋅p(xj∣μi,Σi)
则对应的簇标记为:
λj=argi∈{1,2,...,k}maxγji
再根据后验概率更新α, μ, Σ。
算法如下图所示(图源:机器学习):
6. 密度聚类 DBSCAN
密度聚类假设聚类结构能通过样本分布的紧密程度确定。
DBSCAN作如下定义:
-
ε-邻域:对于一个样本x,其ε-邻域是与x距离不大于ε的样本子集
- 核心对象:对于一个样本x,其ε-邻域的样本数目大于某个值,那么x是核心对象
- 密度直达:xi是核心对象,xj在其邻域内,则它们密度直达
- 密度可达:xi与xj密度直达,xj与xk密度直达,则xi与xk密度可达
- 密度相连:对于xi和xj,存在xk使得xi与xj均由xk密度可达,则xi与xj密度相连
DBSCAN将簇定义为由密度可达关系导出的最大密度相连样本集合。
算法如下图所示(图源:机器学习):
7. 层次聚类 AGNES
层次聚类试图在不同层次对数据集进行划分,从而形成树形的聚类结构。
AGNES是一种自底向上的聚类策略,先将数据集中每一个样本看成一个簇,然后找到距离最近的簇,将其合并,该过程不断重复,直到达到指定簇数目。
衡量簇的距离,可以采用最小距离(由两个簇最近的样本决定)、最大距离(由两个簇最远的样本决定)、平均距离,对应的AGNES算法称为单链接、全链接、均链接。
算法如下图所示(图源:机器学习):
如果这篇文章对你有一点小小的帮助,请给个关注,点个赞喔,我会非常开心的~