Multi-label dimensionality reduction based on semi-supervised discriminant analysis

Abstract

Multi-label data with high dimensionality often occurs, which will produce large time and energy overheads when directly used in classification tasks. To solve this problem, a novel algorithm called multi-label dimensionality reduction via semi-supervised discriminant analysis (MSDA) was proposed. It was expected to derive an objective discriminant function as smooth as possible on the data manifold by multi-label learning and semi-supervised learning. By virtue of the latent imformation, which was provided by the graph weighted matrix of sample attributes and the similarity correlation matrix of partial sample labels, MSDA readily made the separability between different classes achieve maximization and estimated the intrinsic geometric structure in the lower manifold space by employing unlabeled data. Extensive experimental results on several real multi-label datasets show that after dimensionality reduction using MSDA, the average classification accuracy is about 9.71% higher than that of other algorithms, and several evaluation metrices like Hamming-loss are also superior to those of other dimensionality reduction methods.

Keywords

manifold learning / semi-supervised learning (SSL) / linear discriminant analysis (LDA) / multi-label classification / dimensionality reduction

References

[1] TsoumakasG., KatakisI.. Multi-label classification: An overview [J]. International Journal of Data Warehousing and Mining, 2007, 3(3): 1-13

[2] LiH., LiX., WuM., ChengS.-q., YiL.-jun.. Multi-class classification of high-dimension gene expression profile based on closed patterns [J]. Journal of Central South University: Science and Technology, 2008, 39(5): 1035-1041

[3] van der MaatenL. J. P.An introduction to dimensionality reduction using Matlab [R], 2007, Maastricht, Maastricht University

[4] CaiD., HeX.-f., HanJ.-wei.. Semi-supervised discriminant analysis [C]. Proceedings of the 11th IEEE International Conference on Computer Vision, 2007, New York, IEEE Computer Society: 1-7

[5] ZhuX. J., GoldbergA. B.. Introduction to semi-supervised learning [J]. Synthesis Lectures on Artificial Intelligence and Machine Learning, 2009, 3(1): 1-130

[6] ZhangD.-q., ZhouZ.-h., ChenS.-can.. Semi-supervised dimensionality reduction [C]. Proceedings of the 7th SIAM International Conference on Data Mining, 2007, New York, IEEE Computer Society: 629-634

[7] SongY.-q., NieF.-p., ZhangC.-s., XiangS.-ming.. A unified framework for semi-supervised dimensionality reduction [J]. Pattern Recognition, 2008, 41(9): 2789-2799

[8] ChengH., HuaK. A., VuK., LiuD. Z.. Semi-supervised dimensionality reduction in image feature space [C]. Proceedings of the 2008 ACM Symposium on Applied Computing, 2008, New York, ACM Press: 1207-1211

[9] YuK., YuS. P., TrespV.. Multi-label informed latent semantic indexing [C]. Proceedings of the 28th Annual International ACM SIGIR Conference on Research and Development in Information Retrieval, 2005, New York, ACM Press: 258-265

[10] ZhangY., ZhouZ.-hua.. Multi-label dimensionality reduction via dependency maximization [C]. Proceedings of the 23rd AAAI Conference on Artificial Intelligence, 2008, New York, IEEE Computer Society: 1503-1505

[11] ParkC., LeeM.. On applying linear discriminant analysis for multi-labeled problems [J]. Pattern Recognition Letters, 2008, 29(7): 878-887

[12] BoutellM. R., LuoJ. B., ShenX. P., BrownC. M.. Learning multi-label scene classification [J]. Pattern Recognition, 2004, 37(9): 1757-1771

[13] GodboleS., SarawagiS.. Discriminative methods for multi-labeled classification [C]. Proceedings of the 8th Pacific-Asia Conference on Knowledge Discovery and Data Mining (PAKDD), 2004, New York, IEEE Computer Society: 22-30

[14] LiuY., JinR., YangLiu.. Semi-supervised multi-label learning by constrained non-negative matrix factorization [C]. Proceedings of National Conference on Artificial Intelligence and Innovative Applications of Artificial Intelligence Conference, 2006, New York, IEEE Computer Society: 666-671

[15] KangF., JinR., SukthankarR.. Correlated label propagation with application to multi-label learning [C]. Proceedings of IEEE International Conference on Computer Vision and Pattern Recognition (CVPR), 2006, New York, IEEE Computer Society: 1719-1726

[16] QiG.-j., HuaX.-s., RuiY., TangJ.-h., MeiT., ZhangH.-jiang.. Correlative multi-label video annotation [C]. Proceedings of the 15th International Conference on Multimedia, 2007, New York, ACM Press: 17-26

[17] LevinaE., BickelP. J.Advances in neural information processing systems [M], 2005, Cambridge, MIT Press: 777-784

[18] FanM.-y., QiaoH., ZhangBo.. Intrinsic dimension estimation of manifolds by incising balls [J]. Pattern Recognition, 2009, 42(5): 780-787