基于核技巧和超图正则的稀疏非负矩阵分解
|
摘要
针对传统的非负矩阵分解(NMF)应用于聚类时,没有同时考虑到鲁棒性和稀疏性,导致聚类性能较低的问题,提出了基于核技巧和超图正则的稀疏非负矩阵分解算法(KHGNMF)。首先,在继承核技巧的良好性能的基础上,用L_(2,1)范数改进标准非负矩阵分解中的F范数,并添加超图正则项以尽可能多地保留原始数据间的内在几何结构信息;其次,引入L_(2,1/2)伪范数和L_(1/2)正则项作为稀疏约束合并到NMF模型中;最后,提出新算法并将新算法应用于图像聚类。在6个标准的数据集上进行验证,实验结果表明,相对于非线性正交图正则非负矩阵分解方法,KHGNMF使聚类性能(精度和归一化互信息)成功地提升了39%～54%,有效地改善和提高了算法的稀疏性和鲁棒性,聚类效果更好。
Focused on the problem that when traditional Non-negative Matrix Factorization(NMF) is applied to clustering, robustness and sparsity are not considered at the same time, which leads to low clustering performance, a sparse Non-negative Matrix Factorization algorithm based on Kernel technique and HyperGraph regularization(KHGNMF) was proposed. Firstly, on the basis of inheriting good performance of kernel technique, L_(2,1) norm was used to improve F-norm of standard NMF, and hyper-graph regularization terms were added to preserve inherent geometric structure information among the original data as much as possible. Secondly, L_(2,1/2) pseudo norm and L_(1/2) regularization terms were merged into NMF model as sparse constraints. Finally, a new algorithm was proposed and applied to image clustering. The experimental results on six standard datasets show that KHGNMF can improve clustering performance(accuracy and normalized mutual information) by 39% to 54% compared with nonlinear orthogonal graph regularized non-negative matrix factorization, and the sparsity and robustness of the proposed algorithm are increased and the clustering effect is improved.
Focused on the problem that when traditional Non-negative Matrix Factorization(NMF) is applied to clustering, robustness and sparsity are not considered at the same time, which leads to low clustering performance, a sparse Non-negative Matrix Factorization algorithm based on Kernel technique and HyperGraph regularization(KHGNMF) was proposed. Firstly, on the basis of inheriting good performance of kernel technique, L_(2,1) norm was used to improve F-norm of standard NMF, and hyper-graph regularization terms were added to preserve inherent geometric structure information among the original data as much as possible. Secondly, L_(2,1/2) pseudo norm and L_(1/2) regularization terms were merged into NMF model as sparse constraints. Finally, a new algorithm was proposed and applied to image clustering. The experimental results on six standard datasets show that KHGNMF can improve clustering performance(accuracy and normalized mutual information) by 39% to 54% compared with nonlinear orthogonal graph regularized non-negative matrix factorization, and the sparsity and robustness of the proposed algorithm are increased and the clustering effect is improved.
引文
[1]LEE D,SEUNG H S.Learning the parts of objects by non-negative matrix factorization[J].Nature,1999,401:788-791.
[2]LIU W,ZHENG N.Non-negative matrix factorization based methods for object recognition[J].Pattern Recognition Letters,2004,25(8):893-897.
[3]LEE D D,SEUNG H S.Algorithms for non-negative matrix factorization[J].Neural Information Processing Systems,2000(12):556-562.
[4]COSTA G,ORTALE R.XML document co-clustering via non-negative matrix tri-factorization[C]//Proceedings of the 2014 IEEE26th International Conference on Tools with Artificial Intelligence.Washington,DC:IEEE Computer Society,2014:607-614.
[5]DHILLON I S.Co-clustering documents and words using bipartite spectral graph partitioning[C]//Proceedings of the 2001 ACMSIGKDD International Conference on Knowledge Discovery and Data Mining.New York:ACM,2001:269-274.
[6]SUN P,KIM K J.Document clustering using non-negative matrix factorization and fuzzy relationship[J].Korea Communications Society Journal,2010,14(2):239-246.
[7]LIAO Q,ZHANG Q.Local coordinate based graph-regularized NMFfor image representation[J].Signal Processing,2016,124:103-114.
[8]EGGERT J,WERSING H,KORNER E.Transformation-invariant representation and NMF[C]//Proceedings of the 2004 IEEE International Joint Conference on Neural Networks.Piscataway,NJ:IEEE,2004:2535-2539.
[9]LONG X,LU H,PENG Y,et al.Graph regularized discriminative non-negative matrix factorization for face recognition[J].Multimedia Tools and Applications,2014,72(3):2679-2699.
[10]WANG Y,JIA Y,HU C,et al.Non-negative matrix factorization framework for face recognition[J].International Journal of Pattern Recognition and Artificial Intelligence,2005,19(4):495-511.
[11]PEHARZ R,PERNKOPF F.Sparse non-negative matrix factorization with l0-constraints[J].Australasian Journal of Special Education,2012,80(1):38-46.
[12]LU N,MIAO H.Structure constrained non-negative matrix factorization for pattern clustering and classification[J].Neurocomputing,2016,171:400-411.
[13]LI S Z,HOU X W,ZHANG H J,et al.Learning spatially localized,parts-based representation[C]//Proceedings of the 2001IEEE Computer Society Conference on Computer Vision and Pattern Recognition.Washington,DC:IEEE Computer Society,2001,1:207-212.
[14]XU W,LIU X,GONG Y,et al.Document clustering based on non-negative matrix factorization[C]//Proceedings of the 26th Annual International ACM SIGIR Conference on Research and Development in Informaion Retrieval.New York:ACM,2003:267-273.
[15]HUA W,HE X.Discriminative concept factorization for data representation[J].Neurocomputing,2011,74(18):3800-3807.
[16]TENENBAUM J B,SILVA V D,LANGFORD J C.A global geometric framework for nonlinear dimensionality reduction[J].Science,2000,290(5500):2319-2323.
[17]ROWEIS S T,SAUL L K.Nonlinear dimensionality reduction by locally linear embedding[J].Science,2000,290(5500):2323-2326.
[18]BELKIN M,NIYOGI P.Laplacian eigenmaps and spectral techniques for embedding and clustering[C]//Proceedings of the 14th International Conference on Neural Information Processing Systems:Natural and Synthetic.Cambridge,MA:MIT Press,2001:585-591.
[19]ZHANG Z,ZHA H.Principal manifolds and nonlinear dimensionality reduction via tangent space alignment[J].Journal of Shanghai University(English Edition),2004,8(4):406-424.
[20]ZHANG T,TAO D,LI X,et al.Patch alignment for dimensionality reduction[J].IEEE Transactions on Knowledge and Data Engineering,2009,21(9):1299-1313.
[21]HOYER P O.Non-negative matrix factorization with sparseness constraints[J].Journal of Machine Learning Research,2004,5(1):1457-1469.
[22]DING C H Q,LI T,JORDAN M I.Convex and semi-nonnegative matrix factorizations[J].IEEE Transactions on Pattern Analysis and Machine Intelligence,2009,32(1):45-55.
[23]CAI D,HE X,HAN J,et al.Graph regularized non-negative matrix factorization for data representation[J].IEEE Transactions on Pattern Analysis and Machine Intelligence,2011,33(8):1548-1560.
[24]LIU H,WU Z,CAI D,et al.Constrained non-negative matrix factorization for image representation[J].IEEE Transactions on Pattern Analysis and Machine Intelligence,2012,34(7):1299-1311.
[25]HU W,CHOI K S,WANG P,et al.Convex non-negative matrix factorization with manifold regularization[J].Neural Networks,2015,63:94-103.
[26]BABAEE M,TSOUKALAS S,BABAEE M,et al.Discriminative nonnegative matrix factorization for dimensionality reduction[J].Neurocomputing,2016,173(P2):212-223.
[27]YANG S,HOU C,ZHANG C,et al.Robust non-negative matrix factorization via joint sparse and graph regularization for transfer learning[J].Neural Computing and Applications,2013,23(2):541-559.
[28]WANG W,QIAN Y,TANG Y.Hypergraph-regularized sparse NMF for hyperspectral unmixing[J].IEEE Journal of Selected Topics in Applied Earth Observations and Remote Sensing,2016,9(2):681-694.
[29]TOLIC D,ANTULOVFANTULIN N,KOPRIVA I.A nonlinear orthogonal non-negative matrix factorization approach to subspace clustering[EB/OL].[2018-07-12].https://arxiv.org/pdf/1709.10323.pdf.
[30]GAO Y,JI R,CUI P,et al.Hyperspectral image classification through bilayer graph-based learning[J].IEEE Transactions on Image Processing,2014,23(7):2769-2778.
[31]KONG D,DING C,HUANG H.Robust nonnegative matrix factorization using L2,1-norm[C]//Proceedings of the 20th ACM International Conference on Information and Knowledge Management.New York:ACM,2011:673-682.
[32]DING C,ZHOU D,HE X,et al.R1-PCA:rotational invariant L1-norm principal component analysis for robust subspace factorization[C]//Proceedings of the 23rd International Conference on Machine Learning.New York:ACM,2006:281-288.
[33]SHI C,RUAN Q,AN G,et al.Hessian semi-supervised sparse feature selection based on L2,1/2-matrix norm[J].IEEE Transactions on Multimedia,2014,17(1):16-28.
[34]HUANG T-M,KECMAN V,KOPRIVA I.Kernel based algorithm for mining huge data set[J].Studies in Computational Intelligence,2006,17:11-60.
[35]PAPADIMITRIOU C H,STEIGLITZ K.Combinatorial optimization:algorithms and complexity[J].IEEE Transactions on Acoustics,Speech and Signal Processing,1998,32(6):1258-1259.
[36]曹大为,贺超波,陈启买,等.基于加权核非负矩阵分解的短文本聚类算法[J].计算机应用,2018,38(8):2180-2184.(CAOD W,HE C B,CHEN Q M,et al.Short text clustering algorithm based on weighted kernel nonnegative matrix factorization[J].Journal of Computer Applications,2018,38(8):2180-2184.)
[2]LIU W,ZHENG N.Non-negative matrix factorization based methods for object recognition[J].Pattern Recognition Letters,2004,25(8):893-897.
[3]LEE D D,SEUNG H S.Algorithms for non-negative matrix factorization[J].Neural Information Processing Systems,2000(12):556-562.
[4]COSTA G,ORTALE R.XML document co-clustering via non-negative matrix tri-factorization[C]//Proceedings of the 2014 IEEE26th International Conference on Tools with Artificial Intelligence.Washington,DC:IEEE Computer Society,2014:607-614.
[5]DHILLON I S.Co-clustering documents and words using bipartite spectral graph partitioning[C]//Proceedings of the 2001 ACMSIGKDD International Conference on Knowledge Discovery and Data Mining.New York:ACM,2001:269-274.
[6]SUN P,KIM K J.Document clustering using non-negative matrix factorization and fuzzy relationship[J].Korea Communications Society Journal,2010,14(2):239-246.
[7]LIAO Q,ZHANG Q.Local coordinate based graph-regularized NMFfor image representation[J].Signal Processing,2016,124:103-114.
[8]EGGERT J,WERSING H,KORNER E.Transformation-invariant representation and NMF[C]//Proceedings of the 2004 IEEE International Joint Conference on Neural Networks.Piscataway,NJ:IEEE,2004:2535-2539.
[9]LONG X,LU H,PENG Y,et al.Graph regularized discriminative non-negative matrix factorization for face recognition[J].Multimedia Tools and Applications,2014,72(3):2679-2699.
[10]WANG Y,JIA Y,HU C,et al.Non-negative matrix factorization framework for face recognition[J].International Journal of Pattern Recognition and Artificial Intelligence,2005,19(4):495-511.
[11]PEHARZ R,PERNKOPF F.Sparse non-negative matrix factorization with l0-constraints[J].Australasian Journal of Special Education,2012,80(1):38-46.
[12]LU N,MIAO H.Structure constrained non-negative matrix factorization for pattern clustering and classification[J].Neurocomputing,2016,171:400-411.
[13]LI S Z,HOU X W,ZHANG H J,et al.Learning spatially localized,parts-based representation[C]//Proceedings of the 2001IEEE Computer Society Conference on Computer Vision and Pattern Recognition.Washington,DC:IEEE Computer Society,2001,1:207-212.
[14]XU W,LIU X,GONG Y,et al.Document clustering based on non-negative matrix factorization[C]//Proceedings of the 26th Annual International ACM SIGIR Conference on Research and Development in Informaion Retrieval.New York:ACM,2003:267-273.
[15]HUA W,HE X.Discriminative concept factorization for data representation[J].Neurocomputing,2011,74(18):3800-3807.
[16]TENENBAUM J B,SILVA V D,LANGFORD J C.A global geometric framework for nonlinear dimensionality reduction[J].Science,2000,290(5500):2319-2323.
[17]ROWEIS S T,SAUL L K.Nonlinear dimensionality reduction by locally linear embedding[J].Science,2000,290(5500):2323-2326.
[18]BELKIN M,NIYOGI P.Laplacian eigenmaps and spectral techniques for embedding and clustering[C]//Proceedings of the 14th International Conference on Neural Information Processing Systems:Natural and Synthetic.Cambridge,MA:MIT Press,2001:585-591.
[19]ZHANG Z,ZHA H.Principal manifolds and nonlinear dimensionality reduction via tangent space alignment[J].Journal of Shanghai University(English Edition),2004,8(4):406-424.
[20]ZHANG T,TAO D,LI X,et al.Patch alignment for dimensionality reduction[J].IEEE Transactions on Knowledge and Data Engineering,2009,21(9):1299-1313.
[21]HOYER P O.Non-negative matrix factorization with sparseness constraints[J].Journal of Machine Learning Research,2004,5(1):1457-1469.
[22]DING C H Q,LI T,JORDAN M I.Convex and semi-nonnegative matrix factorizations[J].IEEE Transactions on Pattern Analysis and Machine Intelligence,2009,32(1):45-55.
[23]CAI D,HE X,HAN J,et al.Graph regularized non-negative matrix factorization for data representation[J].IEEE Transactions on Pattern Analysis and Machine Intelligence,2011,33(8):1548-1560.
[24]LIU H,WU Z,CAI D,et al.Constrained non-negative matrix factorization for image representation[J].IEEE Transactions on Pattern Analysis and Machine Intelligence,2012,34(7):1299-1311.
[25]HU W,CHOI K S,WANG P,et al.Convex non-negative matrix factorization with manifold regularization[J].Neural Networks,2015,63:94-103.
[26]BABAEE M,TSOUKALAS S,BABAEE M,et al.Discriminative nonnegative matrix factorization for dimensionality reduction[J].Neurocomputing,2016,173(P2):212-223.
[27]YANG S,HOU C,ZHANG C,et al.Robust non-negative matrix factorization via joint sparse and graph regularization for transfer learning[J].Neural Computing and Applications,2013,23(2):541-559.
[28]WANG W,QIAN Y,TANG Y.Hypergraph-regularized sparse NMF for hyperspectral unmixing[J].IEEE Journal of Selected Topics in Applied Earth Observations and Remote Sensing,2016,9(2):681-694.
[29]TOLIC D,ANTULOVFANTULIN N,KOPRIVA I.A nonlinear orthogonal non-negative matrix factorization approach to subspace clustering[EB/OL].[2018-07-12].https://arxiv.org/pdf/1709.10323.pdf.
[30]GAO Y,JI R,CUI P,et al.Hyperspectral image classification through bilayer graph-based learning[J].IEEE Transactions on Image Processing,2014,23(7):2769-2778.
[31]KONG D,DING C,HUANG H.Robust nonnegative matrix factorization using L2,1-norm[C]//Proceedings of the 20th ACM International Conference on Information and Knowledge Management.New York:ACM,2011:673-682.
[32]DING C,ZHOU D,HE X,et al.R1-PCA:rotational invariant L1-norm principal component analysis for robust subspace factorization[C]//Proceedings of the 23rd International Conference on Machine Learning.New York:ACM,2006:281-288.
[33]SHI C,RUAN Q,AN G,et al.Hessian semi-supervised sparse feature selection based on L2,1/2-matrix norm[J].IEEE Transactions on Multimedia,2014,17(1):16-28.
[34]HUANG T-M,KECMAN V,KOPRIVA I.Kernel based algorithm for mining huge data set[J].Studies in Computational Intelligence,2006,17:11-60.
[35]PAPADIMITRIOU C H,STEIGLITZ K.Combinatorial optimization:algorithms and complexity[J].IEEE Transactions on Acoustics,Speech and Signal Processing,1998,32(6):1258-1259.
[36]曹大为,贺超波,陈启买,等.基于加权核非负矩阵分解的短文本聚类算法[J].计算机应用,2018,38(8):2180-2184.(CAOD W,HE C B,CHEN Q M,et al.Short text clustering algorithm based on weighted kernel nonnegative matrix factorization[J].Journal of Computer Applications,2018,38(8):2180-2184.)
© 2004-2018 中国地质图书馆版权所有 京ICP备05064691号 京公网安备11010802017129号 地址：北京市海淀区学院路29号 邮编：100083 电话：办公室：(+86 10)66554848；文献借阅、咨询服务、科技查新：66554700 |