Researches On Nonnegative Matrix Factorization Algorithms And Its Applications

With the rapid development of Internet,the scale of the data is getting larger and larger,the correlation of data also becomes more and more complicated,such as huge volumn of high resolution monitor videos,images,and complex network relationships,etc.Therefore,the processing of large data becomes important and urgent.Low rank approximation of matrix is a method used to approximate large scale data matrix.So the dimension of the matrix can be reduced.Nonnegative matrix factorization(NMF)is one of the low rank approximation methods.It de-composes a nonnegative matrix as a product of two low rank nonnegative matrices.Then the low rank approximation of the given nonnegative matrix is obtained.The nonnegative data obtained after decomposition have good explanation and better physical meaning in real-world applications.Since the idea of the original NMF algorithm is proposed,many advanced NMF algorithms have been proposed and used in real-world applications.On the basis of former research results,this thesis proposes several novel NMF algorithms and applies them to applications of image processing and overlapping community discovery.In the application of image pro-cessing,it mainly focuses on the problems of image reconstruction,image feature extraction and other issues.In the application of overlapping community discovery,it mainly solves the problem of overlapping communities found.This thesis is organized as follows:The introduction part mainly introduces the research background and signifi-cance of NMF together with the classification of NMF algorithms.Moreover,each class of NMF algorithms is elaborated in chronological order.An overview of the status and development of research on NMF is presented.At the end of this chapter,it summarizes the thesis's main work and its organization structure.In chapter one,it mainly introduces the related knowledge of NMF and several classical NMF algorithms.In chapter two,we propose a general NMF algorithm based on Newton method(NBA algorithm)aimed to solve the shortcoming of the traditional Newton based NMF algorithm that if the current point's Hessian matrix is not reversible then the algorithm does not go on.The proposed NBA algorithm uses the strategy of gradient direction to decrease the value of the objective when the Newton direction does not go on.So as to solve the above problem well.Finally,the NBA algorithm is applied to three public image data sets.The experimental results show that the proposed algorithm is suitable for all nonnegative matrixs and has faster convergence speed and better effect than the other algorithms in the same period.In chapter three,as computation consumption of the NBA algorithm in com-puting the inverse of Hessian matrix is relatively large,in order to reduce the amount of calculation and taking into account the convergence rate,two rank-one correc-tion algorithms are proposed.One is a modified rank-one residue iteration(MRRI)algorithm,the other is an elementwisely residue iteration(ERI)algorithm.In order to avoid some of the hidden information in original image easily lost in traditional 1DNMF,we combine two dimensional NMF(2DNMF)with the MRRI algorith-m and the ERI algorithm respectively.The two combined algorithms are denoted as MRRI-2DNMF and ERI-2DNMF respectively.We validate the effectiveness of MRRI,ERI,MRRI-2DNMF,ERI-2DNMF and some existed algorithms in the lit-erature on three common image data sets and an image data set from real-world application.The experimental results show that the MRRI and ERI algorithm have smaller relative error,absolute error,Euclidean distance and better image recon-struction quality under the same conditions.The MRRI-2DNMF algorithm and the ERI-2DNMF algorithm have better image quality and less running time than their corresponding 1DNMF algorithms under the similar compression ratio.In chapter four,in view of the important nodes(including overlapping nodes,central nodes and outlier nodes)in overlapping community and the inherent overlap-ping community structure discovery problem,a novel symmetric nonnegative matrix factorization algorithm(SNMFP)is proposed.The SNMFP algorithm uses the sum of the error approximation and the asymmetric penalty term as the objective func-tion and is derived by using the principle of gradient update and the nonnegative constraint conditions.The experimental results of the SNMFP algorithm carried out on five public network data sets show that the SNMFP algorithm can effec-tively discover the important nodes and their inherent community structure of the actual network.From the experimental results,the average conductance and the al-gorithm's execution time of SNMFP are better than those of Community Detection with Nonnegative Matrix Factorization(CDNMF)method.From the experimental results of the weighted average of the accuracy and recall rate's harmonic mean value it is justified that the proposed SNMFP method is more suitable for large databases.In chapter five,a SNMF algorithm(AULAG)based on augmented Lagrangian alternating direction method is proposed aimed to improve the stability of the SNM-F algorithm.We analyze the convergence of the proposed algorithm,and prove that the new algorithm has 1-order stability.Moreover,a new algorithm called AUCD-SNMF is proposed through combination of the AULAG algorthm with an improved overlapping community discovery method.The AUCDSNMF algorithm is tested on five public network data sets.The experimental results show that AUCDSNMF is stable and can find out the inherent structure of overlapping communities,and has better performance in several general indicators.In the last chapter,we summarize the whole work of this thesis and make a prospect of the future research direction.