聚类：物以类聚，人以群分

• 假设f(x)f(x)为多元函数，如果对任意t∈[0,1]t∈[0,1]，均满足：

 

f(tx1+(1−t)x2)≤tf(x1)+(1−t)f(x2)f(tx1+(1−t)x2)≤tf(x1)+(1−t)f(x2)

 

则称f(x)f(x)为凸函数

• JensenJensen不等式：如果ff是凸函数，XX是随机变量，则：f(E[X])≤E[f(X)]f(E[X])≤E[f(X)]
• JensenJensen不等式另一种描述

 

f(∑i=1naixi)≤∑i=1naif(xi)f(∑i=1naixi)≤∑i=1naif(xi)

 

• 取等号的条件是：f(xi)f(xi)是常量

• 聚类的本质：将数据集中相似的样本进行分组的过程

• 每个组称为一个簇(cluster)(cluster)每个簇的样本对应一个潜在的类别

• 样本没有类别标签，一种典型的无监督学习方法

• 这些簇满足以下两个条件

  • 相同簇的样本之间距离较近
  • 不同簇的样本之间距离较远

• 聚类方法：层次聚类、K−MeansK−Means、谱聚类等

• K−MeansK−Means最初起源于信号处理，是一种比较流行的聚类方法

• 数据集为{xi}ni=1{xi}i=1n，将样本划分为kk个簇，每个簇中心为cj(1≤j≤k)cj(1≤j≤k)

• 优化目标：最小化所有样本点到所属簇中心的距离平方和

 

J(r,c)=∑j=1k∑i=1nrij||xi−cj||22J(r,c)=∑j=1k∑i=1nrij||xi−cj||22

 

• 其中rij∈{0,1}rij∈{0,1}，若样本xixi被划分到簇kk中，那么rij=1rij=1，且对于j≠kj≠k，有rij=0rij=0，∑kj=1rij=1∑j=1krij=1

• 模型：minr,cJ(r,c)=∑kj=1∑ni=1rij||xi−cj||22minr,cJ(r,c)=∑j=1k∑i=1nrij||xi−cj||22

• 交替迭代法：

  • 固定cc，优化rr
  • 固定rr，优化cc

• 优化目标：J(r)=∑nj=1∑ki=1rij||xi−cj||22=∑ni=1Ji(ri)J(r)=∑j=1n∑i=1krij||xi−cj||22=∑i=1nJi(ri)

• 算法流程：

  • 随机选择kk个点作为初始中心
  • RepeatRepeat：
    • 将每个样本指派到最近的中心，形成kk个类
    • 重新计算每个类的中心为该类样本均值
  • 直到中心不发生变化

高斯混合模型(GMM)

• 假设数据集{xi}ni=1{xi}i=1n从kk个高斯模型中生成{N(x|μj,∑j)}kj=1{N(x|μj,∑j)}j=1k，样本来自第jj个高斯的概率为πj，∑kj=1πj=1πj，∑j=1kπj=1，记θ={μ,∑,π}θ={μ,∑,π}
• rijrij表示xixi来自高斯jj的概率，rij∈[0,1]，∑kj=1rij=1rij∈[0,1]，∑j=1krij=1
• p(xi)=∑kj=1πjN(xi|μj,∑j)p(xi)=∑j=1kπjN(xi|μj,∑j)
• 优化目标为最大化对数似然函数：

 

LL(θ)=∑i=1nln(∑j=1kπjN(xi|μj,∑j))LL(θ)=∑i=1nln(∑j=1kπjN(xi|μj,∑j))

 

EM算法

• 假设数据集为xini=1xii=1n，隐含变量为{zi}ni=1，zi∈{1,2,...,k}{zi}i=1n，zi∈{1,2,...,k}模型参数为θθ

• 似然函数LL(θ)=∑ni=1ln(∑kj=1p(xi,zi|θ))LL(θ)=∑i=1nln(∑j=1kp(xi,zi|θ))

• 算法流程：

  • 初始化参数θ(0)θ(0)
  • 不断重复以下两步直到收敛：
    • (E−step)(E−step)求解L(θ)L(θ)的下界函数，等价于求QQ函数：Qi(zi|θ(t))=p(zi|xi,θ(t))Qi(zi|θ(t))=p(zi|xi,θ(t))
    • (M−step)(M−step)下界函数最大化θ(t+1)=argmaxθ∑ni=1∑kj=1qi(zi|θ(t))lnP(xi,zi|θ)Qi(zi|θ(t))