博文
两种ONMF的算法_2012/12/26
||
这篇文章主要从聚类角度提出了两种利用聚类思想求解ONMF（$\min_{U\geq 0,V\geq 0}\left \| M-UV \right \|_{F}^{2},VV^{T}=I_{k}$
）的算法，一种是以k-means为基础的类EM算法，一种是以扩展拉格朗日和映射梯度为基础的ONMF算法。 
https://blog.sciencenet.cn/blog-795427-646605.html
上一篇：非负矩阵分解的算法_2012/11/11
下一篇：NMF概要1
1.类EM算法
非负矩阵$M=(m_{1},m_{2},...,m_{n})\in \mathbb{R}_{+}^{m\times n}$,它的列表示n个点的集合$\{m_{j}\}_{j=1}^{n}\in \mathbb{R}_{+}^{m}$.聚类问题即找到一个k个不相交的聚类集合$\{\pi _{i}\}_{i=1}^k$
满足：
$\pi _{i}\subseteq \{1,2,3,...,n\} \forall i,\cup _{1\leq i\leq k}\pi _{i}=\{1,2,...,n\}$
$\pi _{i}\cap \pi _{j}=\varnothing \forall i\neq j$
可以证明NMF和k-means是等价的，而ONMF和sk-means是接近的。
因此在我的理解中对于UV来说，U可以看作聚类中带有权重的质心的集合（基向量），而V可以看作每个点属于每个聚类的表示（基向量的权重表示）。
根据等价性和聚类思想的结合我们可以得到以下的类EM算法的两个步骤的描述：
step1：给定聚类质心$\{u_{i}\}_{i=1}^k$，将一个点分配到离他最近的聚类中$\{\pi _{i}\}_{i=1}^k$：
$j \in \pi_i \Leftrightarrow i= argmax_{1\leq l\leq k }(m_j^T u_l)^2=argmax_{1\leq l\leq k }(m_j^T u_l)$
step2:给定聚类$\{\pi _{i}\}_{i=1}^k$，计算新的聚类质心$\{u_{i}\}_{i=1}^k$。
$u_i^*=argmax _{\{u_i\geq 0,\left \| u_i \right \|=1\}_{i=1}^k}\sum_{j \in \pi_i}(m_j^Tu_i)^2=argmax _{\{u_i\geq 0,\left \| u_i \right \|=1\}_{i=1}^k}\left \| M_i^Tu_i \right \|_2^2$.
对于上式的最优解可以通过 $M_i$的最大奇异值$
sigma _1(M_i) $的左奇异向量来得到,此时我们有$\left \| M_i^Tu_i \right \|_2=\sigma _1(M_i)=\left \| M_i \right \|_2$。
具体算法如图：
就上述算法来说，实际上是将一个非负矩阵矩阵看作一个聚类点的集合，然后对其进行聚类操作，得到的聚类结果经过一定的变换就可以得到非负矩阵的ONMF。
2.基于拉格朗日的ONMF算法 思想：传统的ONMF算法是每一次的迭代中都会保证矩阵的非负性 ，最后以极限的形式来保证矩阵的正交性。而在此算法上是每次迭代利用映射梯度方案来保证矩阵的正交性，并且利用拉格朗日乘法器$\Lambda $
来保证矩阵的非负性。
具体的算法如图：
3.两种算法评价
文章对两种算法和其他传统的ONMF算法作了对比试验，就准确率来说文章提出的两种算法都还不错，但其他方面例如迭代次数、运行时间等等类EM算法表现良好，但第二种算法可以说表现差。根据我的理解，总体来说类EM算法得性能和k-means等传统的算法性能较近，但要优于第二种算法。
https://blog.sciencenet.cn/blog-795427-646605.html
上一篇：非负矩阵分解的算法_2012/11/11
下一篇：NMF概要1
扫一扫，分享此博文