基于对称非负矩阵分解的重叠社区发现方法

针对重叠社区中的重要节点(重叠节点、中心节点、离群节点)及其固有的重叠社区结构的发现问题,提出了一种新的对称非负矩阵分解算法。首先将误差逼近项和非对称惩罚项的和作为目标函数,然后基于梯度更新的原则及非负约束条件推导出该算法。对5个实际网络进行了仿真实验,结果显示所提算法能将实际网络的重要节点及其固有的社区结构发现出来。从社区发现结果的平均导电率和算法的执行时间看,所提方法优于非负矩阵分解社区发现(CDNMF)方法;从准确率和召回率的调和平均值的加权平均值看,所提方法比较适合较大数据集的重叠社区发现。     

Quadratic nonnegative matrix factorization

In Nonnegative Matrix Factorization (NMF), a nonnegative matrix is approximated by a product of lower-rank factorizing matrices. Most NMF methods assume that each factorizing matrix appears only once in the approximation, thus the approximation is linear in the factorizing matrices. We present a new class of approximative NMF methods, called Quadratic Nonnegative Matrix Factorization (QNMF), where some factorizing matrices occur twice in the approximation. We demonstrate QNMF solutions to four potential pattern recognition problems in graph partitioning, two-way clustering, estimating hidden Markov chains, and graph matching. We derive multiplicative algorithms that monotonically decrease the approximation error under a variety of measures. We also present extensions in which one of the factorizing matrices is constrained to be orthogonal or stochastic. Empirical studies show that for certain application scenarios, QNMF is more advantageous than other existing nonnegative matrix factorization methods.     

Localized user-driven topic discovery via boosted ensemble of nonnegative matrix factorization

Nonnegative matrix factorization (NMF) has been widely used in topic modeling of large-scale document corpora, where a set of underlying topics are extracted by a low-rank factor matrix from NMF. However, the resulting topics often convey only general, thus redundant information about the documents rather than information that might be minor, but potentially meaningful to users. To address this problem, we present a novel ensemble method based on nonnegative matrix factorization that discovers meaningful local topics. Our method leverages the idea of an ensemble model, which has shown advantages in supervised learning, into an unsupervised topic modeling context. That is, our model successively performs NMF given a residual matrix obtained from previous stages and generates a sequence of topic sets. The algorithm we employ to update is novel in two aspects. The first lies in utilizing the residual matrix inspired by a state-of-the-art gradient boosting model, and the second stems from applying a sophisticated local weighting scheme on the given matrix to enhance the locality of topics, which in turn delivers high-quality, focused topics of interest to users. We subsequently extend this ensemble model by adding keyword- and document-based user interaction to introduce user-driven topic discovery.     

Combined new nonnegative matrix factorization algorithms with two-dimensional nonnegative matrix factorization for image processing

In recent years, nonnegative matrix factorization (NMF) has attracted significant amount of attentions in image processing, text mining, speech processing and related fields. Although NMF has been applied in several application successfully, its simple application on image processing has a few caveats. For example, NMF costs considerable computational resources when performing on large databases. In this paper, we propose two enhanced NMF algorithms for image processing to save the computational costs. One is modified rank-one residue iteration (MRRI) algorithm , the other is element-wisely residue iteration (ERI) algorithm. Here we combine CAPG (a NMF algorithm proposed by Lin), MRRI and ERI with two-dimensional nonnegative matrix factorization (2DNMF) for image processing. The main difference between NMF and 2DNMF is that the former first aligns images into one-dimensional (1D) vectors and then represents them with a set of 1D bases, while the latter regards images as 2D matrices and represents them with a set of 2D bases. The three combined algorithms are named CAPG-2DNMF, MRRI-2DNMF and ERI-2DNMF. The computational complexity and convergence analyses of proposed algorithms are also presented in this paper. Three public databases are used to test the three NMF algorithms and the three combinations, the results of which show the enhancement performance of our proposed algorithms (MRRI and ERI algorithms) over the CAPG algorithm. MRRI and ERI have similar performance. The three combined algorithms have better image reconstruction quality and less running time than their corresponding 1DNMF algorithms under the same compression ratio. We also do some experiments on a real-captured image database and get similar conclusions.     

Manifold-respecting discriminant nonnegative matrix factorization

Nonnegative matrix factorization (NMF) is an unsupervised learning method for low-rank approximation of nonnegative data, where the target matrix is approximated by a product of two nonnegative factor matrices. Two important ingredients are missing in the standard NMF methods: (1) discriminant analysis with label information; (2) geometric structure (manifold) in the data. Most of the existing variants of NMF incorporate one of these ingredients into the factorization. In this paper, we present a variation of NMF which is equipped with both these ingredients, such that the data manifold is respected and label information is incorporated into the NMF. To this end, we regularize NMF by intra-class and inter-class k-nearest neighbor (k-NN) graphs, leading to NMF-kNN, where we minimize the approximation error while contracting intra-class neighborhoods and expanding inter-class neighborhoods in the decomposition. We develop simple multiplicative updates for NMF-kNN and present monotonic convergence results. Experiments on several benchmark face and document datasets confirm the useful behavior of our proposed method in the task of feature extraction.     

结构正则化多视图非负矩阵分解

现存非负矩阵分解（non-negative matrix factorization,NMF）研究多考虑单一视图分解数据,忽略了数据信息的全面性。此外,NMF限制其获取数据的内在几何结构。针对以上问题,提出一个结构正则化多视图非负矩阵分解算法（structure regularized multi-view nonnegative matrix factorization,SRMNMF）。首先,通过主成分分析来对数据进行全局结构的判别式学习;其次,利用流形学习来捕获数据的局部结构;然后,通过利用多视图数据的多样性和差异性来学习表征。模型提升了算法聚类的整体性能,更加有效地挖掘数据的结构信息。此外,采用高效的交替迭代算法优化目标函数得到最优的因子矩阵。在六个数据集上与现存的代表性方法比较,所提出的SRMNMF的准确率、NMI和Purity分别最大提高4.4%、6.1%和4.05%。     

一种非负矩阵分解的快速方法

针对超高维数据进行非负矩阵分解的计算代价大,特征提取速度慢问题,提出一种非负矩阵分解的快速算法。该算法通过代数变换,把对原高维矩阵的非负分解转换成非负的低维矩阵的非负分解,其求解过程只需要对一个阶数等于样本数的对角矩阵进行非负矩阵分解,同时提取某样本特征时只需要计算该样本与所有训练样本的内积。对高维小样本的基因表达数据降维后进行k均值聚类分析,实验结果表明,该算法在不影响非负矩阵分解性能的前提下,大大提高了计算速度。     

邻域保持判别非负矩阵分解

非负矩阵分解（NMF）是一种新的矩阵分解技术,为了提高NMF算法的识别率,提出了一种新的方法——邻域保持判别非负矩阵分解（NPDNMF）,该方法通过将邻域保持判别分析（NPDA）与NMF相结合来实现。邻域保持判别分析是一个将线性判别分析（LDA）与局部保持投影（LPP）综合考虑的判别分析方法,该算法既保持了LDA的判别能力,同时又可以保持原始数据的几何结构。通过将NPDA与NMF相结合,提取得到局部化同时又有很强判别能力的基图像。在ORL人脸数据库上进行人脸识别实验,结果表明该方法得到较好的识别效果。     

鲁棒结构正则化非负矩阵分解

现有的非负矩阵分解方法既忽略数据的非局部结构,又难以有效应对噪声和野值点。为了解决上述问题,提出一种新的用于聚类的鲁棒结构正则化非负矩阵分解算法。所提出的算法分别构建一个近邻图和一个最大熵图描述数据的局部结构和非局部结构,并使用L_2,1范数代价函数尝试解决噪声问题,从而学习到鲁棒具有判别力的表征。给出一个最优的迭代算法求解两个非负因子,该优化算法的收敛性已被理论和实验证明。在七个图像数据集上的聚类实验结果表明,所提出的算法在无噪声和有噪声情况下聚类均优于其他主流方法。     

遥感图像配准的稳健投影非负矩阵分解方法

由于要配准的目标存在可能的形变,震前和震后遥感图像的配准变得很困难。为了解决这个问题,提出基于稳健的投影非负矩阵分解（RPNMF）的配准方法来精确的配准形变目标。给出一种稳健的投影非负矩阵分解方法来获得震前震后形变目标的共同投影空间,利用在共同投影空间的投影来配准形变目标。为验证该算法的有效性,做了两个实验：2008年5月12日汶川地震前后的SAR图像的配准;唐家山堰塞湖的变化检测。与现有方法进行比较,结果表明该方法能够有效地得到形变目标的共同投影空间,并取得了很好的配准结果;同时,堰塞湖的变化检测也得到了很好的结果。     

Projected gradient methods for nonnegative matrix factorization

Nonnegative matrix factorization (NMF) can be formulated as a minimization problem with bound constraints. Although bound-constrained optimization has been studied extensively in both theory and practice, so far no study has formally applied its techniques to NMF. In this letter, we propose two projected gradient methods for NMF, both of which exhibit strong optimization properties. We discuss efficient implementations and demonstrate that one of the proposed methods converges faster than the popular multiplicative update approach. A simple Matlab code is also provided.     

Nonsmooth nonnegative matrix factorization (nsNMF)

We propose a novel nonnegative matrix factorization model that aims at finding localized, part-based, representations of nonnegative multivariate data items. Unlike the classical nonnegative matrix factorization (NMF) technique, this new model, denoted "nonsmooth nonnegative matrix factorization" (nsNMF), corresponds to the optimization of an unambiguous cost function designed to explicitly represent sparseness, in the form of nonsmoothness, which is controlled by a single parameter. In general, this method produces a set of basis and encoding vectors that are not only capable of representing the original data, but they also extract highly focalized patterns, which generally lend themselves to improved interpretability. The properties of this new method are illustrated with several data sets. Comparisons to previously published methods show that the new nsNMF method has some advantages in keeping faithfulness to the data in the achieving a high degree of sparseness for both the estimated basis and the encoding vectors and in better interpretability of the factors.     

Using underapproximations for sparse nonnegative matrix factorization

Nonnegative matrix factorization consists in (approximately) factorizing a nonnegative data matrix by the product of two low-rank nonnegative matrices. It has been successfully applied as a data analysis technique in numerous domains, e.g., text mining, image processing, microarray data analysis, collaborative filtering, etc.We introduce a novel approach to solve NMF problems, based on the use of an underapproximation technique, and show its effectiveness to obtain sparse solutions. This approach, based on Lagrangian relaxation, allows the resolution of NMF problems in a recursive fashion. We also prove that the underapproximation problem is NP-hard for any fixed factorization rank, using a reduction of the maximum edge biclique problem in bipartite graphs.We test two variants of our underapproximation approach on several standard image datasets and show that they provide sparse part-based representations with low reconstruction error. Our results are comparable and sometimes superior to those obtained by two standard sparse nonnegative matrix factorization techniques.     

A generalized divergence measure for nonnegative matrix factorization

This letter presents a general parametric divergence measure. The metric includes as special cases quadratic error and Kullback-Leibler divergence. A parametric generalization of the two different multiplicative update rules for nonnegative matrix factorization by Lee and Seung (2001) is shown to lead to locally optimal solutions of the nonnegative matrix factorization problem with this new cost function. Numeric simulations demonstrate that the new update rule may improve the quadratic distance convergence speed. A proof of convergence is given that, as in Lee and Seung, uses an auxiliary function known from the expectation-maximization theoretical framework.     

鲁棒自适应对称非负矩阵分解聚类算法

对称非负矩阵分解SNMF作为一种基于图的聚类算法,能够更自然地捕获图表示中嵌入的聚类结构,并且在线性和非线性流形上获得更好的聚类结果,但对变量的初始化比较敏感。另外,标准的SNMF算法利用误差平方和来衡量分解的质量,对噪声和异常值敏感。为了解决这些问题,在集成学习视角下,提出一种鲁棒自适应对称非负矩阵分解聚类算法RS³NMF(robust self-adaptived symmetric nonnegative matrix factorization)。基于L_2,1范数的RS³NMF模型缓解了噪声和异常值的影响,保持了特征旋转不变性,提高了模型的鲁棒性。同时,在不借助任何附加信息的前提下,利用SNMF对初始化特征的敏感性来逐步增强聚类性能。采用交替迭代方法优化,并保证目标函数值的收敛性。大量实验结果表明,所提RS³NMF算法优于其他先进的算法,具有较强的鲁棒性。     

Algorithms and applications for approximate nonnegative matrix factorization

The development and use of low-rank approximate nonnegative matrix factorization (NMF) algorithms for feature extraction and identification in the fields of text mining and spectral data analysis are presented. The evolution and convergence properties of hybrid methods based on both sparsity and smoothness constraints for the resulting nonnegative matrix factors are discussed. The interpretability of NMF outputs in specific contexts are provided along with opportunities for future work in the modification of NMF algorithms for large-scale and time-varying data sets.     

Rank-two residue iteration method for nonnegative matrix factorization

Rank-one residue iteration (RRI) is a recently developed block coordinate method for nonnegative matrix factorization (NMF). Numerical results show that the decomposed matrices generated by RRI method may have several columns, which are zero vectors. In this paper, by studying two special kinds of quadratic programming, we develop two block coordinate methods for NMF, rank-two residue iteration (RTRI) method and rank-two modified residue iteration (RTMRI) method. In the two algorithms, the exact solution of the subproblem can be obtained directly. We also provide that the consequence generated by our proposed algorithms can converge to a stationary point. Numerical results show that the RTRI method and the RTMRI method can yield better solutions, especially RTMRI method can remedy the limitation of the RRI method.     

采用非负矩阵分解的语音盲分离

针对多通路语音信号的欠定卷积混合模型,提出一种基于非负矩阵分解(NMF)的语音盲分离方法。该方法使用高斯分量对源信号的短时傅里叶变换(STFT)进行表示,高斯分量由基于板仓-斋藤(Itakura-Saito(IS))散度的非负矩阵分解的因子所组成。使用极大期望值算法(EM)求解参数,并对信号进行重组。该方法被应用到双声道立体声信号的盲分离实验,实验结果表明了该方法的有效性。