Semi-Supervised Fuzzy-Rough Feature Selection

Yiyu Yao · Qinghua Hu · Hong Yu Jerzy W. Grzymala-Busse (Eds.) 123 LNAI 9437 15th International Conference, RSFDGrC 2015 Tianjin, China, November 20–23, 2015 Proceedings Rough Sets, Fuzzy Sets, Data Mining, and Granular Computing Lecture Notes in Artificial Intelligence 9437 Subseries of Lecture Notes in Computer Science LNAI Series Editors Randy Goebel University of Alberta, Edmonton, Canada Yuzuru Tanaka Hokkaido University, Sapporo, Japan Wolfgang Wahlster DFKI and Saarland University, Saarbrücken, Germany LNAI Founding Series Editor Joerg Siekmann DFKI and Saarland University, Saarbrücken, Germany More information about this series at http://www.springer.com/series/1244 Yiyu Yao •Qinghua Hu Hong Yu Jerzy W. Grzymala-Busse (Eds.) Rough Sets, Fuzzy Sets, Data Mining, and Granular Computing 15th International Conference, RSFDGrC 2015 Tianjin, China, November 20–23, 2015 Proceedings 123 • Editors Yiyu Yao University of Regina Regina, SK Canada Qinghua Hu Tianjin University Tianjin China Hong Yu Chongqing Universtiy of Posts and Telecommunications Chongqing China Jerzy W. Grzymala-Busse University of Kansas Lawrence, KS USA ISSN 0302-9743 ISSN 1611-3349 (electronic) Lecture Notes in Artificial Intelligence ISBN 978-3-319-25782-2 ISBN 978-3-319-25783-9 (eBook) DOI 10.1007/978-3-319-25783-9 Library of Congress Control Number: 2015952762 LNCS Sublibrary: SL7 –Artificial Intelligence Springer Cham Heidelberg New York Dordrecht London ©Springer International Publishing Switzerland 2015, corrected publication 2018 This work is subject to copyright. All rights are reserved by the Publisher, whether the whole or part of the material is concerned, specifically the rights of translation, reprinting, reuse of illustrations, recitation, broadcasting, reproduction on microfilms or in any other physical way, and transmission or information storage and retrieval, electronic adaptation, computer software, or by similar or dissimilar methodology now known or hereafter developed. The use of general descriptive names, registered names, trademarks, service marks, etc. in this publication does not imply, even in the absence of a specific statement, that such names are exempt from the relevant protective laws and regulations and therefore free for general use. The publisher, the authors and the editors are safe to assume that the advice and information in this book are believed to be true and accurate at the date of publication. Neither the publisher nor the authors or the editors give a warranty, express or implied, with respect to the material contained herein or for any errors or omissions that may have been made. Printed on acid-free paper Springer International Publishing AG Switzerland is part of Springer Science+Business Media (www.springer.com) Semi-Supervised Fuzzy-Rough Feature Selection Richard Jensen1(B), Sarah Vluymans2,3, Neil Mac Parthal´ain1, Chris Cornelis2,4, and Yvan Saeys3,5 1Department of Computer Science, Aberystwyth University, Aberystwyth, Ceredigion, Wales, UK {rkj,ncm}@aber.ac.uk 2Department of Applied Mathematics, Computer Science and Statistics, Ghent University, Ghent, Belgium {Sarah.Vluymans,Chris.Cornelis}@ugent.be 3VIB Inflammation Research Center, Zwijnaarde, Belgium {Sarah.Vluymans, Yvan.Saeys}@irc.vib-ugent.be 4Department of Computer Science and AI CITIC-UGR, University of Granada, Granada, Spain [email protected] 5Department of Respiratory Medicine, Ghent University, Ghent, Belgium [email protected] Abstract. With the continued and relentless growth in dataset sizes in recent times, feature or attribute selection has become a necessary step in tackling the resultant intractability. Indeed, as the number of dimensions increases, the number of corresponding data instances required in order to generate accurate models increases exponentially. Fuzzy-rough set-based feature selection techniques offer great flexibility when dealing with real-valued and noisy data; however, most of the current approaches focus on the supervised domain where the data object labels are known. Very little work has been carried out using fuzzy-rough sets in the areas of unsupervised or semi-supervised learning. This paper proposes a novel approach for semi-supervised fuzzy-rough feature selection where the object labels in the data may only be partially present. The approach also has the appealing property that any generated subsets are also valid (super)reducts when the whole dataset is labelled. The experimental evaluation demonstrates that the proposed approach can generate stable and valid subsets even when up to 90 % of the data object labels are missing. Keywords: Fuzzy-rough sets ·Feature selection ·Semi-supervised learning 1 Introduction Supervised learning operates on labelled data and attempts to learn the underlying functional relationships in that data. It is the most common paradigm in machine learning and is concerned with the learning of classifiers which can accurately reflect the predictive regularities of the underlying model from the feature c Springer International Publishing Switzerland 2015 Y. Yao et al. (Eds.): RSFDGrC 2015, LNAI 9437, pp. 185–195, 2015. DOI: 10.1007/978-3-319-25783-9 17 186 R. Jensen et al. values and decision class labels. For unsupervised learning, on the other hand, there are no decision class labels and the task is to construct or reconstruct class information from some inherent structure in the data. These techniques attempt to find groups in the data such that objects in the same group are similar to each other in some way and those in different groups are dissimilar. The notion of similarity is however subjective and as such, unsupervised learning approaches are forced to make assumptions about groupings as well as the number of groups into which data objects belong. The semi-supervised learning (SSL) paradigm lies between that of supervised learning and unsupervised learning. It is typically employed when some (but not all) of the data is labelled. The primary aim of SSL is to try to utilise both labelled and unlabelled data and it has therefore attracted much interest due to the abundance of unlabelled data which is available for many real-world problems. The main obstacle for traditional learning methods is that they cannot utilise unlabelled data for knowledge discovery. This has led to a growth in the number of SSL approaches. Rough sets [7] and fuzzy-rough sets [3] have recently enjoyed much attention particularly for the task of feature selection (FS), due to their domain independence and, in the case of fuzzy-rough sets, the additional ability to handle real-valued data. The vast majority of work carried out in the areas of rough sets and fuzzy-rough sets has been focused on supervised learning approaches, i.e. where all of the class labels are known. There has been very little work in the area of unsupervised learning for fuzzy-rough sets and even less still for semisupervised learning. The motivation for a fuzzy-rough based semi-supervised feature selection approach is based on the success of the supervised approaches [5,6] and the fact that the subsets produced by the proposed approaches are also shown to be valid (super)reducts for fully labelled data. The remainder of the paper is structured as follows. In Sect. 2, the preliminaries for fuzzy-rough set theory and FS are covered. In Sect. 3, the proposed approach for semi-supervised fuzzy-rough set FS is presented. Section 4details an experimental evaluation of the technique, where its performance is assessed through the random removal of class labels from a number of benchmark datasets and using non-parametric statistical analysis. Finally, in Sect. 5, the paper is concluded and some directions for future work are suggested. 2 Rough and Fuzzy-Rough Set Theory In rough set analysis [7], data is represented as an information system (X, A), where X={x1,...,x n}and A={a1,...,a m}are finite, non-empty sets of objects and features, respectively. Each a∈Acorresponds to a mapping from Xto Va, which is the value set of aover X. For every subset Bof A,the B-indiscernibility relation1RBis defined as RB={(x, y)∈X2|(∀a∈B)(a(x)=a(y))}.(1) Clearly, RBis an equivalence relation. Its equivalence classes [x]RBcanbeused to approximate concepts, i.e., subsets of the universe X.GivenA⊆X, its lower 1When B={a}, i.e., Bis a singleton, Rais written rather than R{a}. Semi-Supervised Fuzzy-Rough Feature Selection 187 and upper approximation w.r.t. RBare respectively defined as RB↓A={x∈X|[x]RB⊆A}(2) RB↑A={x∈X|[x]RB∩A=∅}.(3) An element xbelongs to the lower approximation if it belongs to Aand all other instances in its equivalence class do so as well. It belongs to the upper approximation when it does not necessarily belong to Aitself, but there is at least one element in its equivalent class that does. Adecision system (X, A∪{d}) is a special kind of information system, used in the context of classification. Attribute d(d∈A) is called the decision feature. Its equivalence classes [x]Rd(or [x]d) are called decision classes. Given B⊆A, the B-positive region POSBcontains those objects from Xfor which the values of Ballow to predict the decision class unequivocally. This can be modeled using the lower approximation (2), i.e., POSB= x∈X RB↓[x]Rd.(4) Indeed, if x∈POSB, it means that whenever an object has the same values as xfor the features in B, it will also belong to the same decision class as x.The predictive ability w.r.t. dof the features in Bis measured by the following value (degree of dependency of don B): γB=|POSB| |X|.(5) (X, A∪{d}) is called consistent if γA= 1. A subset Bof Ais called a decision reduct if it satisfies POSB=POSA, i.e., Bpreserves the decision making power of A, and moreover it cannot be further reduced, i.e., there exists no proper subset Bof Bsuch that POSB=POSA. When the latter constraint is removed, i.e. Bis not necessarily minimal, this is then termed a decision superreduct. Fuzzy-rough set theory extends the above notions. A subset Bof Acan be defined using the fuzzy B-indiscernibility relation: RB(x, y)=T(Ra(x, y)   a∈B ),(6) in which Trepresents a t-norm2. It can easily be seen that if only qualitative features (possibly originating from discretisation) are used, then the traditional concept of the B-indiscernibility relation is recovered. For the lower and upper approximation of a fuzzy set Ain Xby means of a fuzzy tolerance relation R, the definitions proposed in [8] are adopted and defined, for all xin X, (R↓A)(x)= inf y∈XI(R(x, y),A(y)) (7) (R↑A)(x)=sup y∈X T(R(x, y),A(y)).(8) 2A t-norm Tis an increasing, commutative, associative [0,1]2→[0,1] mapping satisfying T(x, 1) = xfor xin [0,1]. 188 R. Jensen et al. Here, Iis an implicator3. When dis crisp, the fuzzy positive region can be defined as follows [2]: POSB(x)=(RB↓[x]d)(x).(9) Using the Lukasiewicz implicator ((∀a, b ∈[0,1])(I(a, b) = min(1 −a+b, 1)), it is found for each data instance x∈X: POSB(x)=(RB↓[x]d)(x) =inf y∈XI(RB(x, y),[x]d(y)) = min[ inf y∈[x]d I(RB(x, y),[x]d(y)),inf y/∈[x]d I(RB(x, y),[x]d(y))] = min[ inf y∈[x]d I(RB(x, y),1),inf y/∈[x]d I(RB(x, y),0)] = min[ inf y∈[x]d min(1 −RB(x, y)+1,1),inf y/∈[x]d min(1 −RB(x, y)+0,1)] = min[1,inf y/∈[x]d (1 −RB(x, y))] =inf y/∈[x]d (1 −RB(x, y)).(10) From this, an increasing [0,1]-valued measure to gauge the degree of dependency of a subset of features on another subset of features can be defined. For FS, it is useful to phrase this in terms of the dependency of the decision feature on a subset of the conditional features: γB=|POSB| |X|=  x∈X POSB(x) |X|.(11) This measure is used in the fuzzy-rough FS method (FRFS) of [5]. This technique is a hill-climbing algorithm to determine a (super)reduct B⊆A. It initialises B as an empty set and iteratively adds the attribute a∈A\Bthat leads to the largest increase in the value (11). The algorithm halts when γB=γA. 3 Semi-Supervised Fuzzy-Rough Feature Selection One of the primary motivating factors for semi-supervised approaches is the abundance of unlabelled data. Indeed, it is often expensive and time-consuming for domain experts to label data and this is where semi-supervised techniques can take advantage of small amounts of labelled data and (larger) amounts of unlabelled data in order to learn about the underlying predictive regularities. Using the definitions described in Sect. 2, the original FRFS approach can be altered to handle both labelled and unlabelled data. Consider a feature subset B⊆A, the membership degree to the positive region is computed as defined in 3An implicator Iis a [0,1]2→[0,1] mapping that is decreasing in its first and increasing in its second argument, satisfying I(0,0) = I(0,1) = I(1,1) = 1 and I(1,0) = 0. Semi-Supervised Fuzzy-Rough Feature Selection 195 6. Jensen, R., Tuson, A., Shen, Q.: Finding rough and fuzzy-rough set reducts with SAT. Inf. Sci. 255, 100–120 (2014) 7. Pawlak, Z.: Rough Sets: Theoretical Aspects of Reasoning About Data. Kluwer Academic Publishing, Dordrecht (1991) 8. Radzikowska, A.M., Kerre, E.E.: A comparative study of fuzzy rough sets. Fuzzy Sets Syst. 126(2), 137–155 (2002) 9. Widz, S., ´ Sl ezak, D.: Attribute Subset Quality Functions over a Universe of Weighted Objects. In: Kryszkiewicz, M., Cornelis, C., Ciucci, D., Medina-Moreno, J., Motoda, H., Ra´s, Z.W. (eds.) RSEISP 2014. LNCS, vol. 8537, pp. 99–110. Springer, Heidelberg (2014) 10. Wilcoxon, F.: Individual comparisons by ranking methods. Biometrics Bull. 1(6), 80–83 (1945)