简介
在无监督学习中unsupervised learning
中,训练样本的标记信息是未知的,其目标是通过对无标记训练样本的学习来揭示数据的内在性质及规律,为进一步的数据分析提供基础。而此类学习任务中应用最广、研究最多的即聚类clustering
。
以通俗的语言讲解,聚类学习将数据集中的样本分成若干个互不相交的子集(称为簇cluster
)。保持簇内差异尽可能小而簇间差异尽可能大我们就可以将每个簇映射到一些潜在的类别。
需要注意的是,划分的类别对于聚类而言事先是位置的,聚类过程仅能将数据集自动划分为不同的簇,但每个簇对应的概念语义是需要使用者自己来把握和命名。
数学描述
照旧我们以数学语言描述聚类学习,假定样本集D={x1,x2,...,xm}包含m个无标记样本,每个样本xi=(xi1;xi2;...;xim)是一个n维特征向量,则聚类算法将样本D划分为k个不相交的簇{Cl∣l=1,2,...,k}。我们用λj∈1,2,...,k表示样本xj的簇标记cluster label
,则聚类结果可用包含m个元素的簇标记向量λ=(λ1;λ2;...;λm)表示。
性能度量
从本质上讲,我们希望聚类形成簇内方差尽可能小而簇间方差尽可能大的分类结果,即相同类别的元素尽可能相似而归属不同类别的元素尽可能不同。
对数据集D={x1,x2,...,xm},假定通过聚类给出的簇划分为C={C1,C2,...,Ck},定义:
avg(C)=∣C∣(∣C∣−1))21≤i<j≤∣C∣∑dist(xi,xj)diam(C)=max1≤i<j≤∣C∣dist(xi,xj)dmin(Ci,Cj)=minxi∈Ci,xj∈Cjdist(xi,xj)dcen(Ci,Cj)=dist(μi,μj)μ=∣C∣11≤i≤∣C∣∑xi
其中dist(xi,xj)衡量两个样本之间的距离,μ表示簇C的中心点,avg(C)表示簇C内样本间的平均距离,diam(C)表示簇C内样本间的最远距离,dmin(Ci,Cj)表示两个簇最近样本间的距离,dcen(Ci,Cj)表示两个簇中心点间的距离。
基于这些指标,我们常用下面的聚类性能度量聚类效果:
- DB指数
Davies-Bouldin Index
:值越小表示聚类效果越好
DBI=k1i=1∑kj=imax(dcen(μi,μj)avg(Ci)+avg(Cj))
- Dunn指数
Dunn Index
:值越大表示聚类效果越好
DI=1≤i≤kmin{j=imin(max1≤l≤kdiam(Cl)dmin(Ci,Cj))}
给定样本xi=(xi1;xi2;...;xin)和xj=(xj1;xj2;...;xjn),度量两个样本点间距离dist(xi,xj)的方法有很多种,最常用的就是“闵可夫斯基距离”Minkowski distance
:
distmk(xi,xj)=(u=1∑n∣xiu−xju∣p)p1
当p=2时,闵可夫斯基距离等价于欧式距离Euclidean distance
;p=1时,闵可夫斯基距离等价于曼哈顿距离Manhattan distance
k均值算法
给定样本集D={x1,x2,...,xm},k-means
最小化聚类所得簇划分C={C1,C2,...,Ck}的平方误差:
E=i=1∑kx∈Ci∑∣∣x−μi∣∣22
最小化上式需要遍历样本集D中所有可能的簇划分,这本身就是一个NP
难的问题,因此k-means
算法采取了贪心策略,通过迭代优化来近似求解。
输入:样本集D={x1,x2,...,xm},聚类簇数k
输出:最优的簇划分C={C1,C2,...,Ck}
- 从D中随机抽取k个样本作为初始均值向量{μ1,μ2,...,μk}
- 遍历D中的每个样本xj,计算它与各均值向量μi(1≤i≤k)的距离:dji=∣∣xj−μi∣∣2,将样本划入离它最近的簇中:λj=argmini∈1,2,...,kdji,对应的簇更新为Cλj=Cλj∪{xj}
- 对k个簇重新计算均值向量:μi′=∣Ci∣1∑x∈Cix,更新均值向量
- 重复1-3步骤直至均值向量不再更新
高斯混合聚类
1.多元高斯分布
先回顾以下多元高斯分布的概率密度函数:
p(x)=(2π)2n∣∑∣211e−21(x−μ)T∑−1(x−μ)
其中μ是均值向量,∑是n×n的协方差矩阵,高斯分布完全由均值向量μ和协方差矩阵∑这俩参数确定,因此我们可将其记为p(x∣μ∑)。
2.高斯混合分布
基于多元高斯分布的概念,我们可定义高斯混合分布:
pM(x)=i∑kαi⋅⋅p(x∣μi,i∑)
该分布共由k个混合分布组成,每个混合成分对应一个高斯分布,而αi>0为相应的混合系数mixture coefficient
,且满足∑i=1kαi=1
3.高斯混合聚类原理
假设样本的生成过程由高斯混合分布给出:首先根据αi定义先验分布选择高斯混合成分,然后根据被选择的混合成份的概率密度函数进行采样,从而生成相应的样本。
给定训练集D={x1,x2,...,xm}由上述过程生成,令随机变量zj∈{1,2,...,k}表示生成样本xj的高斯混合成分,其取值未知。根据贝叶斯定理,可以计算zj的后验分布为:
pM(zj=i∣xj)=pM(xj)P(zj=i)×p(M)(xj∣zj=i)=∑l=1kαl×p(xj∣μl,∑l)αi×p(xj∣μi,∑i)
即pM(zj=i∣xj)给定了样本xj由第i个高斯混合成分生成的后验概率,我们将其记为γji,高斯混合聚类将样本集D划分为k个簇C={C1,C2,...,Ck},每个样本xj的簇标记λj确定如下:
λj=argi∈{1,2,...,k}minγji
4.高斯混合聚类算法
输入:样本集D={x1,x2,...,xm};高斯混合成分个数k
输出:簇划分C={C1,C2,...,Ck}
- 初始化高斯混合分布参数{(αi,μi,∑i)∣1≤i≤k}
- 计算xj由高斯各混合部分生成的后验概率,即γji=pM(zj=i∣xj)
- 计算新均值向量μi′=∑j=1mγji∑j=1mγjixj,计算新协方差矩阵∑i′=∑j=1mγji∑j=1mγji(xj−μi′)(xj−μi′)T,计算新混合系数αi′=m∑j=1mγji,并更新对应的三个模型参数
- 重复进行2-3步骤直至满足停止条件(EM算法达到最大迭代次数或者似然函数增长很少)
- 根据λj=argmini∈{1,2,...,k}γji将样本xj划到对应的簇中,即Cλj=Cλj∪{xj}
密度聚类DBSCAN
密度聚类density-based clustering
假设聚类结构能通过样本分布的紧密程度确定,密度聚类算法从样本密度的角度来考察样本之间的可连接性,并基于可连接样本不断扩展聚类簇以获得最终的聚类结果。
1.密度聚类的相关概念
给定数据集D={x1,x2,...,xm},有如下概念:
-
ϵ邻域:Nϵ={xi∈D∣dist(xi,xj)≤ϵ},即样本集中与xj距离不超过ϵ的样本集合
- 核心对象
core object
:若xj的ϵ邻域内至少包含MinPts个样本,则它是一个核心对象
- 密度直达
directly density-reachable
:若xj位于xi的ϵ邻域中,且xi是核心对象,则称xj由xi密度直达
- 密度可达
density-reachable
:对xi和xj,若存在样本序列p1,p2,...,pn,其中p1=xi,pn=xj且pi+1由pi密度直达,则称xj由xi密度可达
- 密度相连
density-connect
:对xi与xj,如果存在xk使得xi与xj均由xk密度可达,则称xi和xj密度相连
下图给出了密度聚类相关概念的直观展示:
在MinPts=3的情况下,虚线表示ϵ邻域,x1是核心对象,x2由x1密度直达,x3由x1密度可达,x3与x4密度相连。
2.密度聚类原理
基于上述的概念,密度聚类将“簇”定义为:由密度可达关系导出的最大密度相连样本集合。从数学角度上讲,即给定邻域参数(ϵ,MinPts),簇C⊆D是满足以下性质的非空样本子集:
- 连接性
connectivity
:xi∈C,xj∈C⇒xi和xj密度相连
- 最大型
maximality
:xi∈C,xj由xi密度可达⇒xj∈C
不难证明,若x为核心对象,则由其密度可达的所有样本组成的集合记为X={x′∈D∣x′由x密度可达}满足连接性与最大性。
3.密度聚类算法
输入:样本集D={x1,x2,...,xm};邻域参数(ϵ,MinPts)
输出:簇划分C={C1,C2,...,Ck}
- 遍历所有样本,如果样本xj的ϵ邻域满足∣Nϵ(xj)∣≥MinPts,那么将其加入核心对象集合Ω=Ω∪{xj}
- 随机抽取一个核心对象o∈Ω,遍历该核心对象ϵ邻域内的所有样本点q(包括它自身),如果该样本也是核心对象,则Δ=Nϵ(q)∩Γ
- 对于2步骤中的核心对象,继续搜寻其ϵ邻域内的所有样本点,更新Δ,生成聚类簇C1=Δ
- 继续随机抽取一个核心对象生成聚类簇,重复2-3步骤,直至所有核心对象均被访问过为止。
直观展示如下:
层次聚类
层次聚类hierarchical clustering
试图在不同层次上对数据集进行划分,从而形成树形的聚类结构,数据集的划分既可以采用“自底向上”的聚合策略,也可以采用“自顶向下”的分拆策略。
AGNES
是一种自底向上聚合策略的层次聚类算法,它先将数据集中每个样本看成一个初始聚类簇,然后在算法运行的每一步中找到最近的两个聚类簇进行合并,该过程不断重复直至达到预设的聚类簇个数,关键在于如何计算连个聚类簇之间的距离。
1.计算距离的方式
最小距离:dmin(Ci,Cj))=minx∈Ci,z∈Cjdist(x,z)
最大距离:dmax(Ci,Cj))=maxx∈Ci,z∈Cjdist(x,z)
平均距离::davg(Ci,Cj))=∣Ci∣∣Cj∣1∑x∈Ci∑z∈Cjdist(x,z)
当聚类簇距离分别由dmin、dmax或davg计算时,AGNES
算法被相应地成为“单链接”single-linkage
、“全链接”complete-linkage
或“均链接”average-linkage
算法。
2.算法
输入:样本集D={x1,x2,...,xm};聚类簇距离度量函数d;聚类簇数k
输出:簇划分C={C1,C2,...,Ck}
- 每个样本最为单独一类,Cj={xj}
- 计算任意两个样本簇间的距离:M(i,j)=d(Ci,Cj)
- 找到距离最近的两个聚类簇Ci∗和Cj∗,将其合并Ci∗=Ci∗∪Cj∗,对于所有下标大于j的簇,将聚类簇Cj重编号为Cj−1
- 根据最新的簇更新一下第2步骤计算的簇间距离矩阵
- 重复2-4步骤直至当前聚类簇个数等于预设的聚类簇数k
3.树状图
令AGNES
算法执行到所有样本出现在同一个簇中,可得到如下的树状图:
在树状图的特定层次上分割即可得到对应的簇划分结果,上图中虚线划分的位置将样本分为7个簇,理解一下背后的原理。
Reference
[1] 周志华 机器学习