Sparse non-negative matrix factorization based on kernel and hypergraph regularization

doi:10.11772/j.issn.1001-9081.2018071617

Journal of Computer Applications ›› 2019, Vol. 39 ›› Issue (3): 742-749.DOI: 10.11772/j.issn.1001-9081.2018071617

Previous Articles Next Articles

Sparse non-negative matrix factorization based on kernel and hypergraph regularization

YU Jianglan^1,2, LI Xiangli^1,2,3, ZHAO Pengfei⁴

1. School of Mathematics and Computing Science, Guilin University of Electronic Technology, Guilin Guangxi 541004, China;
2. Guangxi Key Laboratory of Cryptography and Information Security(Guilin University of Electronic Technology), Guilin Guangxi 541004, China;
3. Guangxi Colleges and Universities Key Laboratory of Data Analysis and Computation(Guilin University of Electronic Technology), Guilin Guangxi 541004, China;
4. School of Mathematics, Southwest Jiaotong University, Chengdu Sichuan 611756, China

Received:2018-08-03 Revised:2018-09-22 Online:2019-03-10 Published:2019-03-11
Contact: 李向利
Supported by:
This work is partially supported by the National Natural Science Foundation of China (11601012, 71561008), the Guangxi Key Laboratory of Cryptography and Information Security (GCIS201708), the Guangxi Natural Science Foundation (2018GXNSFAA138169), the Postgraduate Excellent Dissertation Cultivation Project of Guilin University of Electronic Technology (16YJPYSS22).

基于核技巧和超图正则的稀疏非负矩阵分解

余江兰^1,2, 李向利^1,2,3, 赵朋飞⁴

1. 桂林电子科技大学数学与计算科学学院, 广西桂林 541004;
2. 广西密码学与信息安全重点实验室(桂林电子科技大学), 广西桂林 541004;
3. 广西高校数据分析与计算重点实验室(桂林电子科技大学), 广西桂林 541004;
4. 西南交通大学数学学院, 成都 611756

作者简介:余江兰(1993-),女,重庆人,硕士研究生,主要研究方向:最优化理论及其应用;李向利(1977-),女,陕西宝鸡人,副教授,博士,主要研究方向:最优化理论及其应用;赵朋飞(1993-),男,陕西咸阳人,硕士研究生,主要研究方向:大数据与数据科学。
基金资助:
国家自然科学基金资助项目（11601012，71561008）；广西密码学与信息安全重点实验室研究课题（GCIS201708）；广西自然科学基金资助项目（2018GXNSFAA138169）；桂林电子科技大学研究生优秀学位论文培育项目（16YJPYSS22）。

Abstract

Abstract: 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.

Key words: Non-negative Matrix Factorization (NMF), hypergraph regularization, L_2,1/2-matrix pseudo norm, sparsity, robustness, L_2,1-norm

摘要： 针对传统的非负矩阵分解（NMF）应用于聚类时，没有同时考虑到鲁棒性和稀疏性，导致聚类性能较低的问题，提出了基于核技巧和超图正则的稀疏非负矩阵分解算法（KHGNMF）。首先，在继承核技巧的良好性能的基础上，用L_2，1范数改进标准非负矩阵分解中的F范数，并添加超图正则项以尽可能多地保留原始数据间的内在几何结构信息；其次，引入L_2，1/2伪范数和L_1/2正则项作为稀疏约束合并到NMF模型中；最后，提出新算法并将新算法应用于图像聚类。在6个标准的数据集上进行验证，实验结果表明，相对于非线性正交图正则非负矩阵分解方法，KHGNMF使聚类性能（精度和归一化互信息）成功地提升了39%~54%，有效地改善和提高了算法的稀疏性和鲁棒性，聚类效果更好。

关键词: 非负矩阵分解, 超图正则, L_2,1/2矩阵伪范数, 稀疏性, 鲁棒性, L_2,1范数

CLC Number:

TN919.81

YU Jianglan, LI Xiangli, ZHAO Pengfei. Sparse non-negative matrix factorization based on kernel and hypergraph regularization[J]. Journal of Computer Applications, 2019, 39(3): 742-749.

余江兰, 李向利, 赵朋飞. 基于核技巧和超图正则的稀疏非负矩阵分解[J]. 计算机应用, 2019, 39(3): 742-749.

References

[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 IEEE 26th 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 ACM SIGKDD 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 NMF for 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 l₀-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 2001 IEEE 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 L_2,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. R₁-PCA:rotational invariant L₁-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 L_2,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.(CAO D 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.)

Sparse non-negative matrix factorization based on kernel and hypergraph regularization

基于核技巧和超图正则的稀疏非负矩阵分解

PDF

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 15

Recommended Articles

Metrics

[1]	GAO Gong, YANG Hongyu, LIU Hong. 3D point cloud face recognition based on deep learning [J]. Journal of Computer Applications, 2021, 41(9): 2736-2740.
[2]	LI Xingfeng, HUANG Yuqing, REN Zhenwen, LI Yihong. Robust multi-view clustering algorithm based on adaptive neighborhood [J]. Journal of Computer Applications, 2021, 41(4): 1093-1099.
[3]	Chenyu GE, Liang DONG, Yikun XU, Yi CHANG, Hongming ZHANG. Global-scale radar data restoration algorithm based on total variation and low-rank group sparsity [J]. Journal of Computer Applications, 2021, 41(11): 3353-3361.
[4]	PEI Yiyao, GUO Huiming, ZHANG Danpu, CHEN Wenbo. Robust 3D object detection method based on localization uncertainty [J]. Journal of Computer Applications, 2021, 41(10): 2979-2984.
[5]	LIN Tengtao, ZHA Siming, CHEN Lei, LONG Xianzhong. Graph trend filtering guided noise tolerant multi-label learning model [J]. Journal of Computer Applications, 2021, 41(1): 8-14.
[6]	XING Zhiwei, QIAO Di, LIU Hong’en, GAO Zhiwei, LUO Xiao, LUO Qian. Optimization method of airport gate assignment based on relaxation algorithm [J]. Journal of Computer Applications, 2020, 40(6): 1850-1855.
[7]	WANG Benjie, NONG Liping, ZHANG Wenhui, LIN Jiming, WANG Junyi. 3D point cloud classification and segmentation network based on Spider convolution [J]. Journal of Computer Applications, 2020, 40(6): 1607-1612.
[8]	LIU Ying, LIANG Nannan, LI Daxiang, YANG Fanchao. Hyperspectral image unmixing algorithm based on spectral distance clustering [J]. Journal of Computer Applications, 2019, 39(9): 2541-2546.
[9]	CHEN Shanxue, CHU Chengquan. Hyperspectral unmixing based on sparse and orthogonal constrained non-negative matrix factorization [J]. Journal of Computer Applications, 2019, 39(8): 2276-2280.
[10]	LAI Jie, WANG Xiaodan, LI Rui, ZHAO Zhenchong. Denoising autoencoder based extreme learning machine [J]. Journal of Computer Applications, 2019, 39(6): 1619-1625.
[11]	HUANG Guangqiu, XIE Rong. Cascading failure model of carbon emission spatial correlation system considering load overload [J]. Journal of Computer Applications, 2019, 39(6): 1829-1835.
[12]	YANG Liangdong, YANG Zhixia. Incremental robust non-negative matrix factorization with sparseness constraints and its application [J]. Journal of Computer Applications, 2019, 39(5): 1275-1281.
[13]	LIU Weibo, ZENG Qingning, BU Yuting, ZHENG Zhanheng. Speech recognition method based on dual micro-array and convolutional neural network [J]. Journal of Computer Applications, 2019, 39(11): 3268-3273.
[14]	WANG Yan, LYU Meng, MENG Xiangfu, LI Yuhao. Image matching method with illumination robustness [J]. Journal of Computer Applications, 2019, 39(1): 262-266.
[15]	WEN Kai, ZHU Chuanliang. Regularized matrix decomposition recommendation model integrating social networks and interest correlation [J]. Journal of Computer Applications, 2018, 38(9): 2523-2528.