Active learning of constraints for weighted feature selection. (English) Zbl 07363877

Summary: Pairwise constraints, a cheaper kind of supervision information that does not need to reveal the class labels of data points, were initially suggested to enhance the performance of clustering algorithms. Recently, researchers were interested in using them for feature selection. However, in most current methods, pairwise constraints are provided passively and generated randomly over multiple algorithmic runs by which the results are averaged. This leads to the need of a large number of constraints that might be redundant, unnecessary, and under some circumstances even inimical to the algorithm’s performance. It also masks the individual effect of each constraint set and introduces a human labor-cost burden. Therefore, in this paper, we suggest a framework for actively selecting and then propagating constraints for feature selection. For that, we benefit from the graph Laplacian that is defined on the similarity matrix. We assume that when a small perturbation of the similarity value between a data couple leads to a more well-separated cluster indicator based on the second eigenvector of the graph Laplacian, this couple is definitely expected to be a pairwise query of higher and more significant impact. Constraints propagation on the other side ensures increasing supervision information while decreasing the cost of human-labor. Finally, experimental results validated our proposal in comparison to other known feature selection methods and proved to be prominent.


15A18 Eigenvalues, singular values, and eigenvectors
65F15 Numerical computation of eigenvalues and eigenvectors of matrices
62H30 Classification and discrimination; cluster analysis (statistical aspects)
68T10 Pattern recognition, speech recognition
47N10 Applications of operator theory in optimization, convex analysis, mathematical programming, economics


UCI-ml; Outex
Full Text: DOI


[1] Abin, AA; Beigy, H., Active selection of clustering constraints: a sequential approach, Pattern Recognit, 47, 3, 1443-1458 (2014)
[2] Alon, U.; Barkai, N.; Notterman, DA; Gish, K.; Ybarra, S.; Mack, D.; Levine, AJ, Broad patterns of gene expression revealed by clustering analysis of tumor and normal colon tissues probed by oligonucleotide arrays, Proc Natl Acad Sci, 96, 12, 6745-6750 (1999)
[3] Basu S, Banerjee A, Mooney RJ (2004) Active semi-supervision for pairwise constrained clustering. In: Proceedings of the 2004 SIAM international conference on data mining, SIAM, pp 333-344
[4] Benabdeslem, K.; Hindawi, M., Efficient semi-supervised feature selection: constraint, relevance, and redundancy, IEEE Trans Knowl Data Eng, 26, 5, 1131-1143 (2014)
[5] Benabdeslem, K.; Elghazel, H.; Hindawi, M., Ensemble constrained laplacian score for efficient and robust semi-supervised feature selection, Knowl Inf Syst, 49, 3, 1161-1185 (2016)
[6] Bishop, C.; Bishop, CM, Neural networks for pattern recognition (1995), Oxford: Oxford University Press, Oxford · Zbl 0868.68096
[7] Cheng Y, Cai Y, Sun Y, Li J (2008) Semi-supervised feature selection under logistic i-relief framework. In: ICPR 2008. In: 19th international conference on pattern recognition, IEEE, pp 1-4
[8] Davidson I, Wagstaff KL, Basu S (2006) Measuring constraint-set utility for partitional clustering algorithms. In: European conference on principles of data mining and knowledge discovery, Springer, pp 115-126
[9] Gilad-Bachrach R, Navot A, Tishby N (2004) Margin based feature selection-theory and algorithms. In: Proceedings of the twenty-first international conference on Machine learning, ACM, p 43 · Zbl 1078.68120
[10] Givoni I, Frey B (2009) Semi-supervised affinity propagation with instance-level constraints. In: Artificial intelligence and statistics, pp 161-168
[11] Golub, TR; Slonim, DK; Tamayo, P.; Huard, C.; Gaasenbeek, M.; Mesirov, JP; Coller, H.; Loh, ML; Downing, JR; Caligiuri, MA, Molecular classification of cancer: class discovery and class prediction by gene expression monitoring, Science, 286, 5439, 531-537 (1999)
[12] He X, Cai D, Niyogi P (2006) Laplacian score for feature selection. In: Advances in neural information processing systems, pp 507-514
[13] Hijazi S, Kalakech M, Hamad D, Kalakech A (2018) Feature selection approach based on hypothesis-margin and pairwise constraints. In: 2018 IEEE Middle East and North Africa communications conference (MENACOMM), IEEE, pp 1-6
[14] Hindawi M, Allab K, Benabdeslem K (2011) Constraint selection-based semi-supervised feature selection. In: 2011 IEEE 11th international conference on data mining (ICDM). IEEE, pp 1080-1085
[15] Huang L, Yan D, Taft N, Jordan MI (2009) Spectral clustering with perturbed data. In: Advances in neural information processing systems, pp 705-712
[16] Jiang Y, Ren J (2011) Eigenvector sensitive feature selection for spectral clustering. In: Joint European conference on machine learning and knowledge discovery in databases, Springer, pp 114-129
[17] Kalakech, M.; Biela, P.; Macaire, L.; Hamad, D., Constraint scores for semi-supervised feature selection: a comparative study, Pattern Recognit Lett, 32, 5, 656-665 (2011)
[18] Kamvar K, Sepandar S, Klein K, Dan D, Manning M, Christopher C (2003) Spectral learning. In: International joint conference of artificial intelligence, Stanford InfoLab
[19] Kira K, Rendell LA (1992) A practical approach to feature selection. In: Proceedings of the ninth international workshop on Machine learning, pp 249-256
[20] Klein D, Kamvar SD, Manning CD (2002) From instance-level constraints to space-level constraints: making the most of prior knowledge in data clustering. Tech. rep, Stanford
[21] Kononenko I (1994) Estimating attributes: analysis and extensions of relief. In: European conference on machine learning. Springer, pp 171-182
[22] Li Z, Liu J, Tang X (2008) Pairwise constraint propagation by semidefinite programming for semi-supervised classification. In: Proceedings of the 25th international conference on Machine learning. ACM, pp 576-583
[23] Lichman M (2013) Uci machine learning repository. http://archive.ics.uci.edu/ml
[24] Liu, H.; Motoda, H.; Yu, L., A selective sampling approach to active feature selection, Artif Intell, 159, 1-2, 49-74 (2004) · Zbl 1086.68572
[25] Lu Z, Carreira-Perpinan MA (2008) Constrained spectral clustering through affinity propagation. In: IEEE conference on computer vision and pattern recognition, 2008. CVPR 2008. IEEE, pp 1-8
[26] Lu Z, Ip HH (2010) Constrained spectral clustering via exhaustive and efficient constraint propagation. In: European conference on computer vision. Springer, pp 1-14
[27] Mäenpää, T.; Pietikäinen, M., Classification with color and texture: jointly or separately?, Pattern Recognit, 37, 8, 1629-1640 (2004)
[28] Mallapragada PK, Jin R, Jain AK (2008) Active query selection for semi-supervised clustering. In: 19th international conference on pattern recognition, 2008. ICPR 2008. IEEE, pp 1-4
[29] Ning, H.; Xu, W.; Chi, Y.; Gong, Y.; Huang, TS, Incremental spectral clustering by efficiently updating the eigen-system, Pattern Recognit, 43, 1, 113-127 (2010) · Zbl 1176.68186
[30] Ojala, T.; Pietikäinen, M.; Harwood, D., A comparative study of texture measures with classification based on featured distributions, Pattern Recognit, 29, 1, 51-59 (1996)
[31] Ojala, T.; Maenpaa, T.; Pietikainen, M.; Viertola, J.; Kyllonen, J.; Huovinen, S., Outex-new framework for empirical evaluation of texture analysis algorithms, IEEE object recognition supported by user interaction for service robots, 1, 701-706 (2002)
[32] Peng, H.; Long, F.; Ding, C., Feature selection based on mutual information criteria of max-dependency, max-relevance, and min-redundancy, IEEE Trans Pattern Anal Mach Intell, 27, 8, 1226-1238 (2005)
[33] Pietikäinen M, Mäenpää T, Viertola J (2002) Color texture classification with color histograms and local binary patterns. In: Workshop on texture analysis in machine vision, pp 109-112
[34] Porebski A, Vandenbroucke N, Hamad D (2013) LBP histogram selection for supervised color texture classification. In: 2013 IEEE international conference on image processing, IEEE, pp 3239-3243
[35] Porebski, A.; Hoang, VT; Vandenbroucke, N.; Hamad, D., Multi-color space local binary pattern-based feature selection for texture classification, J Electron Imaging, 27, 1, 011010 (2018)
[36] Qian M, Zhai C (2013) Robust unsupervised feature selection. In: Proceedings of the twenty-third international joint conference on artificial intelligence. AAAI Press, pp 1621-1627
[37] Sheikhpour, R.; Sarram, MA; Gharaghani, S.; Chahooki, MAZ, A survey on semi-supervised feature selection methods, Pattern Recognit, 64, 141-158 (2017) · Zbl 1429.68239
[38] Shi L, Du L, Shen YD (2014) Robust spectral learning for unsupervised feature selection. In: 2014 IEEE international conference on data mining. IEEE, pp 977-982
[39] Sotoca, JM; Pla, F., Supervised feature selection by clustering using conditional mutual information-based distances, Pattern Recognit, 43, 6, 2068-2081 (2010) · Zbl 1191.68514
[40] Stewart, GW; Sun, JG, Matrix perturbation theory (1990), Cambridge: Academic Press, Cambridge · Zbl 0706.65013
[41] Sun Y, Li J (2006) Iterative relief for feature weighting. In: Proceedings of the 23rd international conference on Machine learning. ACM, pp 913-920
[42] Urbanowicz RJ, Meeker M, LaCava W, Olson RS, Moore JH (2017) Relief-based feature selection: introduction and review. arXiv preprint arXiv:1711.08421
[43] Wagstaff, K.; Cardie, C.; Rogers, S.; Schrödl, S., Constrained k-means clustering with background knowledge, ICML, 1, 577-584 (2001)
[44] Wagstaff KL, desJardins M, Xu Q, (2005) Active constrained clustering by examining spectral eigenvectors. Jet Propulsion Laboratory, National Aeronautics and Space Administration, Pasadena, CA
[45] Wang S, Tang J, Liu H (2015) Embedded unsupervised feature selection. In: Twenty-ninth AAAI conference on artificial intelligence
[46] Wang X, Wang J, Qian B, Wang F, Davidson I (2014) Self-taught spectral clustering via constraint augmentation. In: Proceedings of the 2014 SIAM international conference on data mining, SIAM, pp 416-424
[47] Wauthier FL, Jojic N, Jordan MI (2012) Active spectral clustering via iterative uncertainty reduction. In: Proceedings of the 18th ACM SIGKDD international conference on Knowledge discovery and data mining, ACM, pp 1339-1347
[48] Xiong, C.; Johnson, DM; Corso, JJ, Active clustering with model-based uncertainty reduction, IEEE Trans Pattern Anal Mach Intell, 39, 1, 5-17 (2017)
[49] Xu Q, Wagstaff KL, et al (2005) Active constrained clustering by examining spectral eigenvectors. In: International conference on discovery science. Springer, pp 294-307
[50] Yang, M.; Song, J., A novel hypothesis-margin based approach for feature selection with side pairwise constraints, Neurocomputing, 73, 16, 2859-2872 (2010)
[51] Zelnik-Manor L, Perona P (2005) Self-tuning spectral clustering. In: Advances in neural information processing systems, pp 1601-1608
[52] Zhang, D.; Chen, S.; Zhou, ZH, Constraint score: a new filter method for feature selection with pairwise constraints, Pattern Recognit, 41, 5, 1440-1451 (2008) · Zbl 1140.68490
[53] Zhao Z, Liu H (2007) Semi-supervised feature selection via spectral analysis. In: Proceedings of the 2007 SIAM international conference on data mining. SIAM, pp 641-646
[54] Zhou D, Bousquet O, Lal TN, Weston J, Schölkopf B (2004) Learning with local and global consistency. In: Advances in neural information processing systems, pp 321-328
[55] Zoidi, O.; Tefas, A.; Nikolaidis, N.; Pitas, I., Person identity label propagation in stereo videos, IEEE Trans Multimed, 16, 5, 1358-1368 (2014)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.