A Novel Ensemble Model - The Random Granular Re ections

Abstract

One of the most signi cant achievements in machine learning is the development of Ensemble techniques, which gave a powerful tool for tuning classi ers. The most popular methods are Random Forests, Bagging and Boosting. In this paper we present a novel ensemble model, named Random Granular Re ections. This algorithm creates an ensemble of homogenous granular decision systems. In each iteration of learning process, the training decision system is covered by random homogenous granules and the granular re ection is created, which takes part in classi cation process. Seeing the initial results - our approach is promising and seems to be comparable with the selected popular models.

Keywords

• Random Granular Re ections
• Homogenous Granulation
• CSG Classi er
• Ensemble Model
• Rough Sets
• Decision Systems
• Classication

-

This paper is about the application of granular rough computing in new Ensemble model. The techique that we use to prepare the data for each iteration of learning process was inspired by Polkowski standard granulation - see [16]. This method was the beginning of many new algorithms with diverse applications, for instance in Artiemjew [ 1 ]-[3], Polkowski [15]{[ 20 ], Polkowski and Artiemjew [ 21 ] we have the presentation of standard granulation, concept dependent and layered granulation in the context of training data size reduction, missing values absorbtion and usage in the classi cation processes.

In our recent works - see [ 24 ] and [ 25 ] - we have developed a new granulation technique - homogenous granulation (see. detail decription and toy example in Sect. 2). This approximation technique is based on creation of groups of r-indiscernible objects around each training object by lowering the ratio of indiscernibility until the granules contain only homogoneus objects in the sense of their decision class. In this method - what distinguishes it from previously studied - there is no need to estimate optimal parameter of approximation. The r-indiscernibility level for each central training object is formed in automatic way and depends on the homogeneity in decision classes.

The ensemble scheme of classi cation is really e ective in many contexts, for instance in rough set methods the exemplary succesfull applications can be found in [6{8, 26, 29]. The recently developed approximation technique - homogenous granulation - gave us motivation to check it in ensemble model creation. Additionally to Random Forests, Bagging and Boosting we propose a novel algorithm - Ensemble of Random Granular Re ections. The method is based on representation of original training system by its granular re ections formed from random homogenous granules, which covers it in each iteration of learning process. Each granular re ection of training decision system is additionally reduced in size in comparison with original training decision system. The granular re ection of each iteration represents the internal knowledge from original system using the random coverage. The level of data reduction is up to 50 per cent of original data.

In this work we have rst sight into this method and for simplicity we treat all attributes as cathegorical. For experiments we performed 50 iterations of learning process with use of CSG classi er - the classi er based on simple granules of knowledge - see [4].

We have compared our new method with selected ensemble models - see Sect. 3.

The rest of the work contains the following content. In Sect. 2 we have introduction to homogenous granulation algorithm. In Sect 3 we have brief introduction to selected Ensemble models. In Sect. 4 we present our novel ensemblme model - The Random Granular Re ections technique. In Sect. 5 we show the results of the experiments, and we conclude the paper in Sect. 6. 2

Homogenous granulation

Detailed theoretical introduction to rough inclusions is available in Polkowski [15] { [ 20 ].

For given objects u; v from training decision system, r granulation radius, and A the set of attributes, the standard rough inclusion is de ned as (v; u; r) , jIN D(u; v)j

A j j

r IN D(u; v) = fa 2 A : a(u) = a(v)g; (1) (2)

The homogenous granules are formed as follows, grhuomogenous = fv 2 U : jgrcud j jgru j == 0; f or minimal ru f ulf ills the equationg grcud = fv 2 U :

rug ru = f j A0j ; jA1 j ; :::; jjAAjj g 2.1

The process of training system covering

In the process of covering - the objects from training system are covered based on chosen strategy. We use simple random choice because it is the most e ective method among studied ones - see [ 21 ]).

The last step of the granulation process is shown in the next section. 2.2

Granular re ections

In this step we formed the granular re ections of the original training system based on the granules from the found coverage (the coverage is the set of granules, which cover the universe of traning objects completly). Each granule g 2 COV (U; ; r) from the coverage is nally represented by single object formed using the Majority Voting (M V ) strategy (choice the most common values).

fM V (fa(u) : u 2 gg) : a 2 A [ fdgg The granular re ection of the decision system D = (U; A; d) is the decision system (COV (U; ; r), the set of objects formed from granules.

v 2 grcd(u) if and only if (v; u; r) and (d(u) = d(v)) (3) (4) for a given rough (weak) inclusion .

Toy example of described granulation method is presented in the next section. 2.3

Toy example of homogenous granulation

Considering training decision system from Tab. 1.

Homogenous granules for all training objects:

g1(u4) = (u4) a1 a2 a3 a4 d u1 sunny hot high strong no u2 rain cool normal strong no u3 overcast cool normal strong yes u4 sunny mild high weak no u5 sunny cool normal weak yes u6 rain mild normal weak yes u7 overcast hot high weak yes u8 sunny mild normal strong yes u9 overcast mild high strong yes u10 rain mild high weak yes u11 overcast hot normal weak yes

g0:75(u5) = (u5) g0:75(u6) = (u6; u10) g0:75(u7) = (u7; u11) g0:75(u8) = (u8) g0:75(u9) = (u9) g1(u10) = (u10) g0:5(u11) = (u3; u5; u6; u7; u11) Granules covering training system by random choice: Granular decision system from above granules is as follows: g0:75(u1) sunny hot high strong no g1(u2) rain cool normal strong no g1(u4) sunny mild high weak no g0:75(u6) rain mild normal weak yes g0:75(u7) overcast hot high weak yes g0:75(u8) sunny mild normal strong yes g0:75(u9) overcast mild high strong yes g0:5(u11) overcast cool normal weak yes

In the next section there is a brief description of the selected popular Ensemble models. 3

Selected popular ensemble models

There are many techniques in the family of Enssemble models. One of the most popular are Random Forests, Bagging and Boosting - see [ 31 ]. Short description of mentioned models is to be found below.

Bootstrap Ensembles - Pure Bagging: It is the random committee of bootstraps [ 33 ]. It is a method in which the original decision system - the basic knowledge - is split into (T RN ) training data set, and (T ST valid) validation test data set. And from the TRN system, for a xed number of iterations, we form a new Training systems (N ewT RN ) by random choice with returning of cardfT RN g objects. In all iterations we classify the TRNvalid system in two ways: the rst based on the actual N ewT RN system and the second based on the committee of all performed classi cations. In the committee majority voting is performed and the ties are resolved randomly.

Bagging based on Arcing - Bagging: The main di erence between this method and Bootstrap Ensembles is that the T RN is split into two data sets N ewT RN and N ewT ST - see [5] and [ 27 ]. This split is based on Bootstraps where weights determine the probability with which objects are assigned to NewTRN set. Initially weights are equal, but after rst classi cation of the NewTST using NewTRN weights are lowered for well-classi ed objects. The next step is normalization of weights. This algorithm which shows forming of Bootstraps is called Arcing. Classifying the T ST valid with N ewT RN in a single iteration as the committee of classi ers is the last step of this method. In Arcing weights are modi ed with the factor equal to 1 AAcccucruarcaycy .

Boosting based on Ada-Boost with Monte Carlo split: Classi cation method used in this algorithm is similar to the previously described with the di erence that the NewTRN and NewTST are formed in a di erent way - see [9], [ 28 ] and [ 34 ]. Objects for NewTRN are chosen based on weights and xed ratio is used to split the T RN data set. Previous experiments show that split ratio equal to 0.6 is optimal, as it is close to the approximate size of the distinguishable objects in the bootstraps. Other parts of this algorithm works like in the previous one. Random forests: In this model random trees are created based on randomly chosen attributes and then they take part in the classi cation process in each iteration. This method can be usefull in other classi ers using the random set of attributes before usage in classi cation process. The number of attributes, which should be chosen depending on internal data logic, have to be found in an experimental way.

In the following section we present introduction to our new Ensemble method. 4

Ensemble of Random

Granular Re ections

In each iteration of our new ensemble model we have used a di erent homogenous granular decision system formed from random homogenous granules, which covers the original training system. The visualization of the model can be found in Fig. 1.

The time comlexity of this model is quadratic. The most time consuming part is granulation, which main component takes ((no: of obj:)2) (no: of att:) operations.

Experimental Session

To perform initial experiments we used the australian credit data set from UCI Machine Learning Repository [ 30 ]. We have run our algorithm with 50 iterations of learning for each tested Ensemble model. As a reference point we have chosen Committee of Bootstraps (Pure Bagging) [ 33 ], Boosting based on Arcing (Bagging) [5], [ 27 ], and Ada-Boost with Monte Carlo split [9], [ 28 ] and [ 34 ] - for details see Sect. 3. As a reference classi er we used CSG classi er [4] with radius 0:5. The e ectiveness is evaluated by percentage of properly classi ed objects the accuracy.

The rst result of Random Granular Re ections technique for chosen data set is presented in Fig. 2. The results of the other popular ensemble models are to be found in Figs. 3, 4 and 5. For selected data set our new technique outperformed the other checked methods. The results of the experiments show the e ectivenes of our new technique. The Ensemble of Random Granular Re ections turn out to be competitive with other techniqes like Bagging and Boosting. Despite promising initial results, much is left to be done to evaluate the e ectiveness and set of applications of this new method.

In the future works we have a plan to extensively check the e ectiveness of new model and we are planning to apply the other types of granules in the proposed ensemble model. 7

Acknowledgements

The research has been supported by grant 23.610.007-300 from Ministry of Science and Higher Education of the Republic of Poland. 3. Artiemjew, P. (2013): A Review of the Knowledge Granulation Methods: Discrete vs. Continuous Algorithms. In Skowron A., Suraj Z. (eds.)(2013): Rough Sets and Intelligent Systems. ISRL 43, Springer-Verlag, Berlin, 2013, pp 41{59. 4. Artiemjew, P.: Boosting E ect of Classi er Based on Simple Granules of Knowledge,

In: Information technolojy and control, Print ISSN: 1392-124X, Vol 47, No 2 (2018) 5. Breiman, L.: Arcing classi er (with discussion and a rejoinder by the author). Ann.

Statist. 26 (3): 801849. Retrieved 18 January 2015. Schapire (1990) proved that boosting is possible. (Page 823) (1998) 6. Hu, X., Construction of An Ensemble of Classi ers based on Rough Sets Theory and Database Operations, Proc. of the IEEE International Conference on Data Mining (ICDM2001), (2001) 7. Hu, X.: Ensembles of classi ers based on rough sets theory and set-oriented database operations, Presented at the 2006 IEEE International Conference on Granular Computing, Atlanta, GA (2006) 8. Murthy, C., Saha, S., Pal, S.K.: Rough Set Based Ensemble Classi er, In: Rough Sets, Fuzzy Sets, Data Mining and Granular Computing Lecture Notes in Computer Science Volume 6743, p. 27 (2001) 9. Ohno-Machado, L.: Cross-validation and Bootstrap Ensembles, Bagging, Boosting, Harvard-MIT Division of Health Sciences and Technology, http://ocw.mit.edu/courses/health-sciences-and-technology/hst-951j-medicaldecision-support-fall-2005/lecture-notes/hst951 6.pdf HST.951J: Medical Decision Support, Fall (2005) 10. Pawlak, Z.: Rough sets. International Journal of Computer and Information Sciences 11, pp 341{356 (1982) 11. Polkowski, L.: Rough Sets. Mathematical Foundations. Physica Verlag, Heidelberg (2002) 12. Polkowski, L.: A rough set paradigm for unifying rough set theory and fuzzy set theory. Fundamenta Informaticae 54, pp 67{88; and : In Proceedings RSFDGrC03, Chongqing, China, 2003. Lecture Notes in Arti cial Intelligencevol. 2639, Springer Verlag, Berlin, pp 70{78 (2003) 13. Polkowski, L.: Toward rough set foundations. Mereological approach. In Proceedings RSCTC04, Uppsala, Sweden. Lecture Notes in Arti cial Intelligence vol. 3066, Springer Verlag, Berlin, pp 8{25 (2004) 14. Polkowski, L.: Granulation of knowledge in decision systems: The approach based on rough inclusions. The method and its applications In Proceedings RSEISP'07, Lecture Notes in Arti cial Intelligence vol. 4585. Springer Verlag, Berlin, pp 69{ (2004) 15. Polkowski, L.: Formal granular calculi based on rough inclusions. In Proceedings of IEEE 2005 Conference on Granular Computing GrC05, Beijing, China. IEEE Press, pp 57{62 (2005) 16. Polkowski, L.: A model of granular computing with applications. In Proceedings of IEEE 2006 Conference on Granular Computing GrC06, Atlanta, USA. IEEE Press, pp 9{16 (2006) 17. Polkowski, L.: The paradigm of granular rough computing. In Proceedings ICCI'07,

Lake Tahoe NV. IEEE Computer Society, Los Alamitos CA, pp 145{163 (2007) 18. Polkowski, L.: A Uni ed Approach to Granulation of Knowledge and Granular Computing Based on Rough Mereology: A Survey, in: Handbook of Granular Computing, Witold Pedrycz, Andrzej Skowron, Vladik Kreinovich (Eds.), John Wiley & Sons, New York, 375-401 (2008)

References

1. Artiemjew , P. : Classi ers from Granulated Data Sets: Concept Dependent and Layered Granulation . In Proceedings RSKD'07. The Workshops at ECML/PKDD'07 , Warsaw Univ. Press, Warsaw, 2007 , pp 1{9 ( 2007 )

2. Artiemjew , P. : Rough mereological classi ers obtained from weak rough set inclusions . In Proceedings of Int. Conference on Rough Set and Knowledge Technology RSKT'08 , Chengdu China , Lecture Notes in Arti cial Intelligence , vol. 5009 . Springer Verlag, Berlin, 2008 , pp 229 { 236 ( 2008 )

19. Polkowski , L. : Granulation of Knowledge: Similarity Based Approach in Information and Decision Systems . In Meyers, R. A.(ed.): Encyclopedia of Complexity and System Sciences . Springer Verlag, Berlin, article 00788 ( 2009 )

20. Polkowski , L. : Approximate Reasoning by Parts . An Introduction to Rough Mereology. Springer Verlag, Berlin, ( 2011 )

21. Polkowski , L. , Artiemjew , P. : Granular Computing in Decision Approximation - An Application of Rough Mereology , in: Intelligent Systems Reference Library 77 , Springer, ISBN 978-3-319-12879-5 , 1 - 422 ( 2015 )

22. Poap , D. , Woniak , M. , Wei , W. , Damaeviius , R. : Multi-threaded learning control mechanism for neural networks . Future Generation Computer Systems , Elsevier 2018 .

23. Quinlan , J. , R.: C4 . 5: Programs for Machine Learning . Morgan Kaufmann, Kluwer Academic Publishers ( 1993 )

24. Ropiak , K. , Artiemjew , P. : On Granular Rough Computing: epsilon homogenous granulation , In: Proceedings of International Joint Conference on Rough Sets, IJCRS'18 , Quy Nhon , Vietnam, Lecture Notes in Computer Science (LNCS) , vol. 11103 , Springer, Heidelberg, pp 546 { 558 ( 2018 )

25. Ropiak , K. , Artiemjew , P. : A Study in Granular Computing: homogenous granulation . In: Dregvaite G., Damasevicius R . (eds) Information and Software Technologies. ICIST 2018 . Communications in Computer and Information Science, Springer ( 2018 ) in print

26. Saha , S. , Murthy , C.A. , Pal , S.K. : Rough set based ensemble classi er for web page classi cation . Fundamenta Informaticae 76 ( 1-2 ), 171187 ( 2007 )

27. Schapire , R.E.: A Short Introduction to Boosting ( 1999 )

28. Schapire , R.E. : The Boosting Approach to Machine Learning: An Overview , MSRI (Mathematical Sciences Research Institute) Workshop on Nonlinear Estimation and Classi cation ( 2003 )

29. Shi , L. , Weng , M. , Ma , X. , Xi , L. : Rough Set Based Decision Tree Ensemble Algorithm for Text Classi cation , In: Journal of Computational Information Systems6:1 , 89 - 95 ( 2010 )

30. University of California, Irvine Machine Learning Repository: https://archive.ics.uci.edu/ml/index.php

31. Yang , P. , Yang , Y. , H. , Zhou , B. , B. ; Zomaya , A. , Y. : A review of ensemble methods in bioinformatics: Including stability of feature selection and ensemble feature selection methods . In Current Bioinformatics , 5 , ( 4 ): 296 - 308 , 2010 (updated on 28 Sep . 2016 )

32. Zadeh , L. A. : Fuzzy sets and information granularity . In Gupta, M. , Ragade , R. , Yager , R.R . (eds.): Advances in Fuzzy Set Theory and Applications . North{Holland, Amsterdam, 1979 , pp 3 { 18 ( 1979 )

33. Zhou , Z.-H. : Ensemble Methods: Foundations and Algorithms . Chapman and Hall/CRC. p. 23 . ISBN 978- 1439830031 . The term boosting refers to a family of algorithms that are able to convert weak learners to strong learners ( 2012 )

34. Zhou , Z.-H. : Boosting 25 years , CCL 2014 Keynote ( 2014 )