利用CUR矩阵分解提高特征选择与矩阵恢复能力

doi:10.11772/j.issn.1001-9081.2017.03.640

计算机应用 ›› 2017, Vol. 37 ›› Issue (3): 640-646.DOI: 10.11772/j.issn.1001-9081.2017.03.640

• 第四届大数据学术会议(CCF BIGDATA2016) • 上一篇下一篇

利用CUR矩阵分解提高特征选择与矩阵恢复能力

雷恒鑫, 刘惊雷

烟台大学计算机与控制工程学院, 山东烟台 264005

收稿日期:2016-09-28 修回日期:2016-10-16 出版日期:2017-03-10 发布日期:2017-03-22
通讯作者: 刘惊雷
作者简介:雷恒鑫(1993-),男,山东阳谷人,硕士研究生,主要研究方向:矩阵分解及其应用;刘惊雷(1970-),男,山西临猗人,副教授,硕士,CCF会员,主要研究方向:人工智能、理论计算机科学。
基金资助:
国家自然科学基金资助项目（61572419，61572418，61403328，61403329）；山东省自然科学基金资助项目（ZR2014FQ016，ZR2014FQ026，2015GSF115009，ZR2013FM011）。

Improving feature selection and matrix recovery ability by CUR matrix decomposition

LEI Hengxin, LIU Jinglei

School of Computer and Control Engineering, Yantai University, Yantai Shandong 264005, China

Received:2016-09-28 Revised:2016-10-16 Online:2017-03-10 Published:2017-03-22
Supported by:
This work is partially supported by the National Natural Science Foundation of China (61572419, 61572418, 61403328, 61403329), the Natural Science Foundation of Shandong Province (ZR2014FQ016, ZR2014FQ026, 2015GSF115009, ZR2013FM011).

摘要/Abstract

摘要： 针对在规模庞大的数据中不能快速准确地选择用户和产品的特征以及不能准确预测用户行为偏好的问题，提出一种CUR矩阵分解方法。该方法是从原始矩阵中选取少量列构成C矩阵，选取少量行构成R矩阵，然后利用正交三角分解（QR）构造U矩阵。分解后的C矩阵和R矩阵分别是用户和产品的特征矩阵，并且C和R矩阵是由真实的数据构成的，因此能够分析出具体的用户和产品特征；为了能够比较准确地预测用户的行为偏好，改进了CUR算法，使其在矩阵恢复方面有更高的稳定性和准确性。最后在真实的数据集（Netflix数据集）上的实验表明，与传统的奇异值分解、主成分分析等矩阵分解方法相比：在特征选择方面，CUR矩阵分解方法具有较高的准确度和很好的可解释性；在矩阵恢复方面，改进的CUR矩阵分解方法具有较高的稳定性和精确度，其准确度能达到90%以上。CUR矩阵分解在推荐系统对用户的推荐方面和交通系统预测交通流量方面有重要的应用价值。

关键词: 行列联合选择算法, 特征选择, 矩阵恢复, 可解释性, 稳定性

Abstract: To solve the problem that users and products can not be accurately selected in large data sets, and the problem that user behavior preference can not be predicted accurately, a new method of CUR (Column Union Row) matrix decomposition was proposed. A small number of columns were selected from the original matrix to form the matrix C, and a small number of rows were selected to form the matrix R. Then, the matrix U was constructed by Orthogonal Rotation (QR) matrix decomposition. The matrixes C and R were feature matrixes of users and products respectively, which were composed of real data, and enabled to reflect the detailed characters of both users as well as products. In order to predict behavioral preferences of users accurately, the authors improved the CUR algorithm in this paper, endowing it with greater stability and accuracy in terms of matrix recovery. Lastly, the experiment based on real dataset (Netflix dataset) indicates that, compared with traditional singular value decomposition, principal component analysis and other matrix decomposition methods, the CUR matrix decomposition algorithm has higher accuracy as well as better interpretability in terms of feature selection, as for matrix recovery, the CUR matrix decomposition also shows superior stability and accuracy, with a preciseness of over 90%. The CUR matrix decomposition has a great application value in the recommender system and traffic flow prediction.

Key words: Column Union Row (CUR) algorithm, feature selection, matrix recovery, interpretability, stability

中图分类号:

TP181

雷恒鑫, 刘惊雷. 利用CUR矩阵分解提高特征选择与矩阵恢复能力[J]. 计算机应用, 2017, 37(3): 640-646.

LEI Hengxin, LIU Jinglei. Improving feature selection and matrix recovery ability by CUR matrix decomposition[J]. Journal of Computer Applications, 2017, 37(3): 640-646.

参考文献

[1] BUSA-FEKETE R, SZÖRÉNYI B, WENG P, et al. Preference-based reinforcement learning:evolutionary direct policy search using a preference-based racing algorithm[J]. Machine Learning, 2014, 97(3):327-351.
[2] BOBADILLA J, ORTEGA F, HERNANDO A. Recommender systems survey[J]. Knowledge-Based Systems, 2013, 46(1):109-132.
[3] 吴金龙.Netflix Prize中的协同过滤算法[D].北京:北京大学,2010:7-10.(WU J L, Collaborative filtering algorithm in Prize Netflix[D]. Beijing:Peking University, 2010:7-10.)
[4] GERBRANDS J J. On the relationships between SVD, KLT and PCA[J]. Pattern Recognition, 1981, 14(1/2/3/4/5/6):375-381.
[5] SHNAYDERMAN A, GUSEV A, ESKICIOGLU A M. An SVD-based grayscale image quality measure for local and global assessment[J]. IEEE Transactions on Image Processing, 2006, 15(2):422-429.
[6] KUMAR R, VERMA B K, RASTOGI S S. Social popularity based SVD++ recommender system[J]. International Journal of Computer Applications, 2014, 87(14):33-37.
[7] JIA Y, ZHANG C, LU Q, et al. Users' brands preference based on SVD++ in recommender systems[C]//Proceedings of the 2014 IEEE Workshop on Advanced Research and Technology in Industry Applications. Piscataway, NJ:IEEE, 2014:1175-1178.
[8] GAO C, ZHOU H H. Rate-optimal posterior contraction for sparse PCA[J]. The Annals of Statistics, 2015, 43(2):785-818.
[9] BERTOLINI A C, SCHIOZER D J. Principal component analysis for reservoir uncertainty reduction[J]. Journal of the Brazilian Society of Mechanical Sciences and Engineering, 2016, 38(4):1345-1355.
[10] XU F, GU G, KONG X, et al. Object tracking based on two-dimensional PCA[J]. Optical Review, 2016, 23(2):231-243.
[11] WATKINS D S. Fundamentals of Matrix Computations[M]. New York:John Wiley & Sons, 1991:2-30.
[12] ACHLIOPTAS D, MCSHERRY F. Fast computation of low-rank matrix approximations[C]//Proceedings of the 33rd Annual ACM Symposium on Theory of Computing. New York:ACM, 2001:611-618.
[13] PFINGSTNER J, SCHULTE D, SNUVERINK J, et al. SVD-based filter design for the trajectory feedback of CLIC[EB/OL].[2016-03-10]. http://epaper.kek.jp/IPAC2011/papers/mopo014.pdf.
[14] DRINEAS P, MAHONEY M W, MUTHUKRISHNAN S. Relative-error CUR matrix decompositions[J]. SIAM Journal on Matrix Analysis and Applications, 2008, 30(2):844-881.
[15] BOUTSIDIS C, WOODRUFF D P. Optimal CUR matrix decompositions[C]//Proceedings of the 46th Annual ACM Symposium on Theory of Computing. New York:ACM, 2014:353-362.
[16] BIEN J, XU Y, MAHONEY M W. CUR from a sparse optimization viewpoint[EB/OL].[2016-03-08]. http://www.stat.berkeley.edu/~mmahoney/pubs/cur-spca.pdf.
[17] WANG L, REGE M, DONG M, et al. Low-rank kernel matrix factorization for large scale evolutionary clustering[J]. IEEE Transactions on Knowledge and Data Engineering, 2012, 24(6):1036-1050.
[18] BELL R M, KOREN Y, VOLINSKY C. The BellKor 2008 solution to the Netflix Prize[EB/OL].[2016-02-21]. http://xueshu.baidu.com/s?wd=paperuri%3A%289ef8f488c3613e6a70daca0f02435bb8%29&filter=sc_long_sign&tn=SE_xueshusource_2kduw22v&sc_vurl=http%3A%2F%2Fciteseerx.ist.psu.edu%2Fviewdoc%2Fdownload%3Bjsessionid%3D3DFEC03FEB7FC3D400E97763E310721E%3Fdoi%3D10.1.1.448.222%26rep%3Drep1%26type%3Dpdf&ie=utf-8&sc_us=13947115770219594334.
[19] 刘惊雷.CP-nets及其表达能力研究[J].自动化学报,2011,37(3):290-302.(LIU J L. CP-nets and study of expression ability[J]. Acta Automatica Sinica, 2011, 37(3):290-302.)
[20] WANG S, ZHANG Z. Improving CUR matrix decomposition and the Nystr m approximation via adaptive sampling[J]. Journal of Machine Learning Research, 2013, 14(1):2729-2769.
[21] WEIMER M, KARATZOGLOU A, SMOLA A. Improving maximum margin matrix factorization[J]. Machine Learning, 2008, 72(3):263-276.
[22] GURUSWAMI V, SINOP A K. Optimal column-based low-rank matrix reconstruction[C]//Proceedings of the 23rd Annual ACM-SIAM Symposium on Discrete Algorithms. Philadelphia, PA:Society for Industrial and Applied Mathematics, 2012:1207-1214.
[23] BOUTSIDIS C, DRINEAS P, MAGDON-ISMAIL M. Near-optimal column-based matrix reconstruction[C]//Proceedings of the 2011 IEEE 52nd Annual Symposium on Foundations of Computer Science. Washington, DC:IEEE Computer Society, 2011:305-314.

利用CUR矩阵分解提高特征选择与矩阵恢复能力

Improving feature selection and matrix recovery ability by CUR matrix decomposition

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

[1]	湛航, 何朗, 黄樟灿, 李华峰, 张蔷, 谈庆. 改进的基于层次距离的基因表达式编程特征选择分类算法[J]. 计算机应用, 2021, 41(9): 2658-2667.
[2]	祝承, 赵晓琦, 赵丽萍, 焦玉宏, 朱亚飞, 陈建英, 周伟, 谭颖. 基于谱聚类半监督特征选择的功能磁共振成像数据分类[J]. 计算机应用, 2021, 41(8): 2288-2293.
[3]	李蒙蒙, 秦伟, 刘艺, 刁兴春. 结合头脑风暴优化的混合蚁群优化算法[J]. 计算机应用, 2021, 41(8): 2412-2417.
[4]	林筠超, 万源. 基于图结构优化的自适应多度量非监督特征选择方法[J]. 计算机应用, 2021, 41(5): 1282-1289.
[5]	贾鹤鸣, 姜子超, 李瑶, 孙康健. 基于改进斑点鬣狗优化算法的同步优化特征选择[J]. 计算机应用, 2021, 41(5): 1290-1298.
[6]	张志浩, 林耀进, 卢舜, 郭晨, 王晨曦. 缺失标记下基于类属属性的多标记特征选择[J]. 计算机应用, 2021, 41(10): 2849-2857.
[7]	黄学雨, 徐浩特, 陶剑文. 具有特征选择的多源自适应分类框架[J]. 计算机应用, 2020, 40(9): 2499-2506.
[8]	刘风. 基于防治策略的毒品滥用流行病学模型[J]. 计算机应用, 2020, 40(9): 2768-2773.
[9]	顾桐, 许国良, 李万林, 李家浩, 王志愿, 雒江涛. 基于集成LightGBM和贝叶斯优化策略的房价智能评估模型[J]. 计算机应用, 2020, 40(9): 2762-2767.
[10]	刘丹, 姚立霜, 王云锋, 裴作飞. 面向类不平衡流量数据的分类模型[J]. 计算机应用, 2020, 40(8): 2327-2333.
[11]	肖跃雷, 张云娇. 基于特征选择和超参数优化的恐怖袭击组织预测方法[J]. 计算机应用, 2020, 40(8): 2262-2267.
[12]	汪志远, 降爱莲, 奥斯曼·穆罕默德. 基于正则互表示的无监督特征选择方法[J]. 计算机应用, 2020, 40(7): 1896-1900.
[13]	谢琪, 徐旭, 程耕国, 陈和平. 基于新的森林优化算法的特征选择算法[J]. 计算机应用, 2020, 40(5): 1266-1271.
[14]	曹堉, 王成, 王鑫, 高悦尔. 基于时空节点选择和深度学习的城市道路短时交通流预测[J]. 计算机应用, 2020, 40(5): 1488-1493.
[15]	张战成, 张大龙, 罗晓清. 带有语义特征得分的肺结节检测方法[J]. 计算机应用, 2020, 40(3): 925-930.