机器学习十讲(五)

聚类:物以类聚,人以群分

  • 假设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))
上一篇:【转载】分级页表如何节约内存


下一篇:Nginx请求处理流程