Integrating Symmetric Nonnegative Matrix Factorization and Normalized Cut

Integrating Symmetric Nonnegative Matrix Factorization and Normalized CutSpectral ClusteringZhichen Xia a and Chris Ding ba College of Electronic Science&Engineering,Jilin University,Changchun,Chinab Department of Comp.Sci.&Eng.,University of Texas,Arlington,Texas,USAEmails:xiazhichenjlu@,chqding@AbstractIn this paper,we integrate symmetric NMF and nor-malized cut into a single clustering framework and derive the computational algorithm.Another contribution is to provide a new matrix inequality which is useful for the analysis of4-th order matrix polynomials.We perform experiments on three real-life data sets to show the effec-tiveness of the proposed algorithm.We also demonstrate the importance of the orthogonality among matrix factors.I.IntroductionNonnegative Matrix Factorization(NMF)has been pop-ularly studied in data mining and machine learning areas since the initial work of Lee and Seung[9].Originally proposed as method forfinding matrix factors with parts-of-whole interpretations[9],NMF has been applied to a number of applied areas,environmetrics[13],chemo-metrics[19],pattern recognition[10],multimedia data analysis[3],text mining[14]and DNA gene expression analysis[1].Algorithmic extensions of NMF have been developed to accommodate a variety of objective func-tions[4],[6]and a variety of data analysis problems,in-cluding classification[15]and collaborativefiltering[17], constrained clustering[11],[18].One of the important features of NMF is its clustering capabilities.It was shown [5],[7]that NMF essentially solves a matrix clustering problem.Symmetric NMF(SNMF)[5],[12]deals with nonneg-ative factorization of a symmetric matrix.In its simple form,SNMF essentially solves a graph clustering problem with a pairwise similarity matrix W.On the other hand, Laplacian-based spectral clustering such as normalized cut[16]is now a standard approach for graph clustering.In this paper,we integrate the SNMF graph clustering and normalized cut graph clustering into a single frame-work.We derive a computational algorithm with rigorous analysis.As another contribution of this paper,we provide a new matrix inequality which is useful for analysis of4-th order matrix polynomials involved in the SNMF problem.We mention that combining NMF with Laplacian reg-ularization have been studied in[2],[8].However,both papers study one matrix factor at a time which involves a2nd order matrix polynomials.The symmetric case is harder to analysis due to the4th order matrix polynomial. Our new matrix inequality resolves this problem.The rest of the paper is organized as follows.Section 2we discuss integrating SNMF and Normalized Cut and computational algorithm.Section3we present the new matrix inequality and its proof.Section4provides a detailed analysis of algorithm in Section2.Section5-7 presents experimental results.Section8gives a summary.II.Integrating NMF and Normalized CutGiven input pairwise similarity matrix W,the symmet-ric NMFminH∥W−HH T∥2,s.t.H≥0(1)has been a popular clustering algorithm.The essence of the symmetric NMF is to discover the block structure in W as represented by HH T.On the other hand,the Lapplacian based normalized cut clustering algorithm solve the following optimization minHTr H T(D−W)H,s.t.H≥0,H T DH=I(2) In this paper,we integrate these two approaches into a unified formulationminH∥W−HH T∥2+2αTr H T(D−W)H,(3) s.t.H≥0,H T DH=I (4)2010 IEEE International Conference on Data Mining WorkshopsOne contribution of this paper is to derive a computational algorithm to solve the integrated clustering formulation.The iterative algorithm is given belowH ik ←H ik[(1+α)(W H )ik(HH T H +DH Λ)ik ]1/4(5)where Λis the Lagrangian multiplier that enforce the condition H T DH =I and its value is given byΛ=[(1+α)H T W H −H T HH T H ]+(6)Here A +=(A +abs (A ))/2is the positive part of A .The correctness and convergence of the above algorithm can be rigorously proved.Details are provided in §4.III.A useful matrix inequalityAnother contribution of this paper is to provide a new generic matrix inequality:Tr (HAH T HBH T )(7)≤∑ik(H ′AH ′T H ′B +H ′BH ′T HA 2)ik H 4ikH ′3ikwhere A,B ∈ℜK ×K +,H,H ′∈ℜn ×K+are nonnegative matrices;and A,B are symmetric:A =A T ,B =B T .This inequality is useful when analyzing objective func-tions involving 4-th order matrix polynomials,such as the symmetric NMF of Eq.(1).We will use this inequality to prove the convergence of the algorithm of Eq.(6).Proof of the inequality Eq.(7)Let H ik =H ′iku ik .The 2nd term in RHS of Eq.(7)is ∑ik(H ′BH ′TH ′A )ik H 4ikH ′3ik=∑ijkrpqH ′ip B pq H ′jq H ′jr A rk H ′ik u 4ik(8)Now,switching indexes:i <=>j,p <=>q,r <=>k ,we obtain∑ik (H ′BH ′T H ′A )ik H 4ik H ′3ik =∑ijkrpqH ′jq B qp H ′ip H ′ik A kr H ′jr u 4jr(9)The 1st term in RHS of Eq.(7)is∑ik(H ′AH ′TH ′B )ik H 4ikH ′3ik=∑ijkrpqH ′jr A rk H ′ik H ′ip B pq H ′jq u 4jq(10)Now,switching indexes:i <=>j,p <=>q,r <=>k ,we obtain∑ik (H ′AH ′T H ′B )ik H 4ik H ′3ik=∑ijkrpqH ′ik A kr H ′jr H ′jq B qp H ′ip u 4ip (11)Carefully examination of the RHS of Eqs.(8-11)show thatthey are identical except u 4terms.Adding Eqs.(8-11),we obtain that the RHS of Eq.(7)is equal to ∑ijkrpqH ′ip B pq H ′jq H ′jr A rk H ′iku 4ik +u 4jr +u 4jq +u 4ip4(12)The LHS of Eq.(7)is equal to∑ijkrpqH ′ip B pq H ′jq H ′jr A rk H ′ik u ik u jr u jq u ip(13)Therefore,if we can establishu ik u jr u jq u ip ≤u 4ik +u 4jr +u 4jq +u 4ip4,(14)then the inequality Eq.(7)holds.For any a,b,c,d >0,we havea 4+b 4≥2a 2b 2,c 4+d 4≥2c 2d 2,(ab )2+(cd )2≥2(ab )(cd ).Thusa 4+b 4+c 4+d 4≥2(a 2b 2+c 2d 2)≥4(ab )(cd ).This is Eq.(14).QED.IV .Analysis of Algorithm Eq.(5)Here we prove the correctness and convergence of Algorithm Eq.(5).We note that since ∥W −HH T ∥2=Tr (W 2−2H T W H +HH T HH T ),the optimization of Eq.(3)becomesmin Tr [−2(1+α)H T W H+HH T HH T (15)+W 2+2αH TDH ]The last two terms are constants.Thus the optimizationbecomesmax HTr [2(1+α)H T W H −HH T HH T ](16)s.t.H ≥0,H T DH =I(17)Correctness .We first prove the correctness of the algorithm,i.e.,we haveTheorem 1.At convergence,the solution of Eq.(5)satisfies the KKT condition of optimization theory.Proof .Introducing Lagrangian multipliers Λto enforce H T DH =I ,we maximizeℒ=Tr [2(1+α)H T W H −HH T HH T −2Λ(H T DH −I )]The KKT optimality condition for complementary slack-ness for the constraint H ≥0is(∂ℒ∂H )ik H ik=4[(1+α)W H −HH T H −DH Λ]ik H ik =0(18)At convergence,Eq.(5)can be written as[(1+α)W H −HH TH −DH Λ]ik H 4ik=0(19)Eq.(18)is identical to Eq.(17).This is because for Eq.(18)to hold,at least one of the two factors must be zero.If the first factor is zero,then Eq.(17)also holds.If the secondfactor H 4ik=0,then H ik =0and Eq.(17)holds again.We can see that the inverse is true,i.e.,if Eq.(17)holds,so does Eq.(18).This proves that if the algorithm Eq.(5)converges,the solution satisfies the KKT condition,i.e.,the solution is an optimal solution.QED.From the KKT condition Eq.(17),summing over i ,we obtainΛkk =[(1+α)H T W H −H T HH T H ]kk(20)This gives Lagrangian multipliers the values on the diag-onal.For non-diagonal elements,we use the Lagrangianwithout nonnegativity bining these two together,we obtain Eq.(6).Convergences .We now prove that the algorithm converges.We have Theorem 2.The Lagrangian functionℒ=Tr [2(1+α)H T W H −HH T HH T −2ΛH T DH ](21)increase monotonically under successive update of thealgorithm Eq.(5).Using this theorem,we have ℒ(H 0)≤ℒ(H 1)≤ℒ(H 2)≤⋅⋅⋅≤ℒ(H t)≤ℒ(Ht +1)⋅⋅⋅Because ℒ(H )is bounded from above due to H T DH =I .Therefore,algorithm Eq.(5)converges.Proof of Theorem 2.We use the auxiliary function approach (Lee and Seung,2001b).If a function satisfies G (H,H )=ℒ(H );G (H,H ′)≤ℒ(H ),we say G (H,H ′)is an aux-iliary function of L (H ).We defineH (t +1)=arg max HG (H,H (t ))(22)Then by construction,we haveℒ(H (t ))=G (H (t ),H (t ))≤G (H (t +1),H (t ))≤ℒ(H (t +1))(23)This proves that L (H (t ))is monotonically increasing.The key steps in the remainder of the proof are:(1)Find an appropriate auxiliary function;(2)Find the global maxima of the auxiliary function.Now we show that an auxiliary function of ℒ(H )isG (H,H ′)=2(1+α)∑ijkH ′ik W ij H ′jk (1+log H ik H jk H ′ik H ′jk)−∑ik(H ′H ′TH ′)ik H 4ikH ′3ik(24)−∑ik (DH ′Λ)ik H 4ik +H ′4ikH ′3ik.(25)where 1st term uses inequality z ≥1+log z with z =H ik H jk /H ′ik H ′jk ,the 2nd term uses the inequality Eq.(7),and 3rd term usesTr (ΛH T DH )≤∑ik(DH ′Λ)ik H 2ik H ′ik(26)and2H 2ik≤H 4ik +H ′4ik H ′2ikThis inequality is just 2ab <a 2+b 2and Eq.(23)is from[7].Now,we solve the optimization of Eq.(21)by setting ∂G (H,H ′)/∂H =0gives(1+α)H ′ik (W H ′)ikH ik=(H ′H ′T H ′)ik H 3ik H ′3ik +(DH ′Λ)ik H 3ik H ′3ik(27)To show that this is a maxima,we compute the 2nd order derivatives,∂2G (H,H ′)∂H ik ∂H jl=−A ik δij δklwhere A ik=(1+α)H ′ik (W H ′)ikH 2ik+3(H ′H ′T H ′)ik H 2ik H ′2ik +3(DH ′Λ)ik H 2ik H ′2ik(28)Therefore,∂2G (H,H ′)∂H ik ∂H jl is negative definite.This implies function F (H )=G (H,H ′)is a concave function and there is a unique global maxima.The maxima is obtained by solving Eq.(27)which is equivalent toH 4ik=H ′4ik(1+α)(W H ′)ik(H ′H ′T H ′)ik +(DH ′Λ)ik(29)Noting H (t +1)←H and H (t )←H ′,the above recovers the algorithm Eq.(5).This proves that under the updating algorithm Eq.(5)which is Eq.(29),ℒ(H )monotonically increasing.QED.V.The importance of orthogonalityOrthogonality in NMF plays an important role[5].A rigorous orthogonality among columns of H provides a hard clustering that each data object belongs to only one cluster(due to orthogonality and nonnegativity,each row of H has only one nonzero element).Without orthogo-nality,however,each row of H could have more nonzero elements and thus NMF provides a soft clustering.Here we note another important role of orthogonality. In the spectral clustering formulation of Eq.(2),without orthogonality constraint H T DH=I,the optimal solution H∗will contains identical columns.This can be seen asfollows.The objective can be written asTr H T(D−W)H=K∑k=1ℎT k(D−W)ℎkWithout the orthogonality constraint,different columns become independent of each other.and thus reach the same minimum with the same solution,i.e.,ℎ∗1=⋅⋅⋅=ℎ∗k.Notice that in SNMF formulation of Eq.(1),orthogonal-ity is not necessary:without orthogonality constraint,the optimal solution H∗will have different columns.The main reason for this desirable feature[5]is due to the matrix approximation nature of Eq.(1),as opposed to the trace minimization of Eq.(2).To summarize,we have show that(A)Orthogonality is not a necessary constraint for SNMF of Eq.(1)and(B)Orthogonality is a necessary constraint for spectral clustering Eq.(2).A.An investigation of orthogonalityIn our approach of integrating SNMF and Spectral Clus-tering,we enforce the orthogonality.Here,we provide an investigation of this issue,since in previous work[2],[8], orthogonality is not incorporated into their formulations.To see the exact difference due to incorporating orthog-onality or not,we adopt our main SNMF-Ncut formulation Eqs.(3,4)but without orthogonality constraint:minH≥0∥W−HH T∥2+2TrαH T(D−W)H.(30)Repeat the derivation of the computational algorithm of Eq.(5),we obtain the following iterative algorithmH ik←H ik [(1+α)(W H)ik(HH T H+αDH)ik]1/4(31)The correctness and convergence of this algorithm are established in the same fashion as the algorithm Eq.(5). Details are skipped here.We provide extensive experiments in later sections.A general picture is the following:whenαis small (α≃0.01),the solution and performance of NonOrthog-onal formulation of Eq.(3)is similar to the Orthogonal formulation of Eqs.(3,4)(but generally the accuracy is not as good);Whenαis medium or large(α≃1),the solution to NonOrthogonal formulation gives poor accuracy;in this case,different columns of obtained optimal H∗are very similar as explained above.Details are given in later sections.VI.Data Sets DescriptionWe demonstrate the clustering ability of the integrated SNMF and Ncut on three real-life datasets,including facial expression,hand-written digits,and hand-written letters. Human face images.In the AT&T database1,there are 400human face images for40human subjects and ten different images of each subject were taken at different times,varying the lighting,facial expression,and facial details.The original112×92images are resized to32×32 and form1024=32×32dimensional vectors.The weight matrix W is constructed asW ij=exp(−∥x i−x j∥2/r2),(32) where the parameter r isfixed tor=0.7×(average distances between all pairs).Hand-written English Alphabet letters.Hand-written capital English letters“A”-“Z”are clustered into26 clusters.Each letter is a20×16binary image.The input data are26×20=520images.They are from the BinAlha dataset which can be downloaded from “/roweis/data.html”.The weight matrix W is constructed as Eq.(32).Hand-written Digits.Hand-written digits of“0”through “9”are clustered into10clusters.Each digit is a20×16 binary image.The input data are10×39=390images. They are from the same BinAlha dataset above for the hand-written capital English letters.The weight matrix W is constructed as Eq.(32).VII.Experiment Results DemonstrationTo illustrate the clustering result,we show a typical clustering solution in Figure1for the alphabet data.Here we should all26clusters.For this clustering solution,the accuracy as evaluated against the ground truth is60.0%.For the digits data,we show a typical clustering solution in Figure 2.Here we should all10clusters.For this clustering solution,the accuracy as evaluated against the ground truth is72.3%.1/research/dtg/attarchive/facedatabase.htmlFor the human face data,we show a typical clustering solution in Figure3.Here we should10clusters out of the40clusters.For this clustering solution,the accuracy as evaluated against the ground truth is65.8%.VIII.Experiment Results Comparison In Tables1-3,we list the clustering accuracy as evalu-ated according to the ground true of the original images. It should benoted that because of the large variations of real data,many objects from different class mix,as seen from Figures1-3.For algorithm comparison,we also run the symmetric NMF algorithm(settingα=0.01in the Algorithm Eq.(5)) and the pure Ncut algorithm(settingα=10in the Algorithm Eq.(5)).For each clustering method,we run50runs starting from randomly initialized H.We average the obtained accuracy and list them in Tables1-3.We also list the maximum accuracy and minimum accuracy from these runs.From the tables,one can see the integrated approach consistantly perform better than SNMF and Ncut,although not very significantly.It is amazing that the algorithm is very stable with respect to the parameterα.methods average maximum minimumNew75.681.568.8Ncut74.179.268.2SNMF70.076.365.8Table I.Clustering accuracy(in percentage)for face data.methods average maximum minimumNew53.856.747.5Ncut52.155.546.3SNMF41.145.837.5Table II.Clustering accuracy(in percentage)for alphabet data.methods average maximum minimumNew62.074.453.9Ncut60.874.152.9SNMF54.360.549.5Table III.Clustering accuracy(in percentage)for digits data.A.Importance of orthogonalityHere we perform the same experiments using the non-orthogonal SNMF-Ncut formulation of Eqs.(30,31).Theresults on the three data sets are listed in Tables4-6.For the AT&T Face data,the non-orthogonal SNMF-Ncut performs reasonable at smallα=0.01:the clusteraccuracy isη=61.17vs70.0for orthogonal SNMF-Ncut(see Tables1,4).Asαincrease gradually toα=1,the non-orthogonal SNMF-Ncut performance gradually decreases;Atα=1,clustering accuracy is rather low:η=3.03.Thisis because the Laplacian term becomes dominant here andin the solution H∗,different columns become very similar—they are all close to the trivial solution of the Laplacian: H∗≈(e,⋅⋅⋅,e),because e is the lowest eigenvector solution for the Ncut.Thus the cluster assignment at thiscase is rather random,resulting low accuracy.This same trend also occur in Alphabet data(Table5)and Digits data(Table6).Asαincreases fromα=0.01toα=1,the average clustering accuracy of the non-orthogonal SNMF-Ncut decreases fromη=39.62to η=3.93for the Alphabet data(see Table5);For the Digits data,the performance(average clustering accuracy) decreases fromη=53.89toη=10.69(see Table6).In conclusion,the mutual orthogonality of columnsof H are necessary for the integration of NMF andLaplacian-based clustering.Without the orthogonality,theperformance of the integrated SNMF-Ncut deteriorate sig-nificantly at even moderateα=1.αaverage maximum minimum0.0161.1766.7555.00.0254.1961.7549.50.0537.1142.7530.50.126.8232.0020.50.217.0122.2512.750.57.5110.50 5.01.0 3.038.252.5Table IV.Non-orthogonal SNMF-Ncut Cluster-ing accuracy for AT&T Face data at different α.αaverage maximum minimum0.0139.6245.7733.850.0238.1843.6532.310.0531.8236.3528.080.121.3518.4627.50.212.3513.857.690.5 4.258.08 3.851.0 3.93 5.38 3.85Table V.Non-orthogonal SNMF-Ncut Cluster-ing accuracy for Alphabet data at differentα.αaverage maximum minimum0.0153.8959.4948.210.0254.3663.0847.690.0553.9462.3147.440.149.6957.4441.540.232.9144.3628.720.511.4827.1810.001.010.6918.4610.00Table VI.Non-orthogonal SNMF-Ncut Cluster-ing accuracy for Digits data at differentα.IX.SummaryWe integrate symmetric NMF and normalized cut into a single clustering framework,derive the computational algorithm.and prove rigorously the correctness and con-vergence of the proposed algorithm.We also provide a new matrix inequality which is useful for the analysis of 4-th order matrix polynomials.We perform experiments on three real-life data sets to show the effectiveness of the proposed algorithm.We also demonstrate the importance of the orthogonality among matrix factors. Acknowledgments.This research is supported by NSF CCF-0830780,NSF CCF-0939187,NSF CCF-0917274, NSF DMS-0915228.References[1]J.-P.Brunet,P.Tamayo,T.Golub,and J.Mesirov.Metagenes and molecular pattern discovery using matrix factorization.Proc.Nat’l Academy of Sciences USA, 102(12):4164–4169,2004.[2] D.Cai,X.He,X.Wu,and J.Han.Non-negative matrixfactorization on manifold.In ICDM,pages63–72,2008.[3]M.Cooper and J.Foote.Summarizing video using non-negative similarity matrix factorization.In Proc.IEEE Workshop on Multimedia Signal Processing,pages25–28, 2002.[4]I.Dhillon and S.Sra.Generalized nonnegative matrixapproximations with Bregman divergences.In Advances in Neural Information Processing Systems17,Cambridge, MA,2005.MIT Press.[5] C.Ding,X.He,and H.Simon.On the equivalence ofnonnegative matrix factorization and spectral clustering.Proc.SIAM Data Mining Conf,2005.[6] C.Ding,T.Li,and W.Peng.Nonnegative matrix factoriza-tion and probabilistic latent semantic indexing:Equivalence, chi-square statistic,and a hybrid method.Proc.National Conf.Artificial Intelligence,2006.[7] C.Ding,T.Li,W.Peng,and H.Park.Orthogonal nonneg-ative matrix tri-factorizations for clustering.In Proceedings of ACM SIGKDD,pages126–135,2006.[8]Q.Gu and J.Zhou.Co-clustering on manifolds.In KDD,pages359–368,2009.[9] D.D.Lee and H.S.Seung.Algorithms for non-negativematrix factorization.In NIPS,2000.[10]S.Li,X.Hou,H.Zhang,and Q.Cheng.Learning spatiallylocalized,parts-based representation.In Proc.IEEE Conf.Computer Vision and Pattern Recognition,pages207–212, 2001.[11]T.Li, C.Ding,and M.I.Jordan.Solving consensusand semi-supervised clustering problems using nonnegative matrix factorization.In ICDM,pages577–582,2007. [12] B.Long,Z.M.Zhang,X.Wu,and P.S.Yu.Relationalclustering by symmetric convex coding.In ICML,pages 569–576,2007.[13]P.Paatero and U.Tapper.Positive matrix factorization:Anon-negative factor model with optimal utilization of error estimates of data values.Environmetrics,5:111–126,1994.[14]V.P.Pauca,F.Shahnaz,M.Berry,and R.Plemmons.Textmining using non-negative matrix factorization.In Proc.SIAM Int’l conf on Data Mining,pages452–456,2004. [15] F.Sha,L.K.Saul,and D.D.Lee.Multiplicative updatesfor nonnegative quadratic programming in support vector machines.In Advances in Neural Information Processing Systems15.MIT Press,Cambridge,MA,2003.[16]J.Shi and J.Malik.Normalized cuts and image segmen-tation.IEEE.Trans.on Pattern Analysis and Machine Intelligence,22:888–905,2000.[17]N.Srebro,J.Rennie,and T.Jaakkola.Maximum marginmatrix factorization.In Advances in Neural Information Processing Systems,Cambridge,MA,2005.MIT Press. [18] F.Wang,T.Li,and C.Zhang.Semi-supervised clusteringvia matrix factorization.In SDM,pages1–12,2008. [19]Y.-L.Xie,P.Hopke,and P.Paatero.Positive matrixfactorization applied to a curve resolution problem.Journal of Chemometrics,12(6):357–364,1999.clusters are shown as26rows;all member of the same cluster are shown in the same row.Figure4.Face data.Figure5.Clustering results for the Face data using the proposed algorithm.There are total40 discovered clusters.Here we show only10clusters,as10rows;all member of the same clusterare shown in the same row.。