聚类：物以类聚，人以群分
- 假设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))