=Paper=
{{Paper
|id=Vol-2240/paper17
|storemode=property
|title=A Novel Ensemble Model - The Random Granular Reflections
|pdfUrl=https://ceur-ws.org/Vol-2240/paper17.pdf
|volume=Vol-2240
|authors=Piotr Artiemjew,Krzysztof Ropiak
|dblpUrl=https://dblp.org/rec/conf/csp/ArtiemjewR18
}}
==A Novel Ensemble Model - The Random Granular Reflections==
https://ceur-ws.org/Vol-2240/paper17.pdf
A Novel Ensemble Model - The Random
Granular Reflections
Piotr Artiemjew, Krzysztof Ropiak
Faculty of Mathematics and Computer Science
University of Warmia and Mazury in Olsztyn
Poland
email:artem@matman.uwm.edu.pl, kropiak@matman.uwm.edu.pl
Abstract. One of the most significant achievements in machine learning
is the development of Ensemble techniques, which gave a powerful tool
for tuning classifiers. The most popular methods are Random Forests,
Bagging and Boosting. In this paper we present a novel ensemble model,
named Random Granular Reflections. This algorithm creates an ensem-
ble of homogenous granular decision systems. In each iteration of learning
process, the training decision system is covered by random homogenous
granules and the granular reflection is created, which takes part in clas-
sification process. Seeing the initial results - our approach is promising
and seems to be comparable with the selected popular models.
Keywords: Random Granular Reflections, Homogenous Granulation,
CSG Classifier, Ensemble Model, Rough Sets, Decision Systems, Classi-
fication
1 Introduction
This paper is about the application of granular rough computing in new Ensem-
ble 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 classification processes.
In our recent works - see [24] and [25] - we have developed a new granula-
tion 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 in-
discernibility 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 classification is really effective 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. Addi-
tionally to Random Forests, Bagging and Boosting we propose a novel algorithm
- Ensemble of Random Granular Reflections. The method is based on represen-
tation of original training system by its granular reflections formed from random
homogenous granules, which covers it in each iteration of learning process. Each
granular reflection of training decision system is additionally reduced in size in
comparison with original training decision system. The granular reflection 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 first 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 classifier - the classifier 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 in-
troduction to homogenous granulation algorithm. In Sect 3 we have brief intro-
duction to selected Ensemble models. In Sect. 4 we present our novel ensemblme
model - The Random Granular Reflections 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 defined as
|IN D(u, v)|
µ(v, u, r) ⇔ ≥r (1)
|A|
where
IN D(u, v) = {a ∈ A : a(u) = a(v)}, (2)
The homogenous granules are formed as follows,
grhomogenous
u
= {v ∈ U : |grcdu |−|gru | == 0, f or minimal ru f ulf ills the equation}
where
IN D(u, v)
grcdu = {v ∈ U : ≤ ru AN D d(u) == d(v)}
|A|
and
IN D(u, v)
gru = {v ∈ U : ≤ ru }
|A|
0 1 |A|
ru = { , , ..., }
|A| |A| |A|
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 effective
method among studied ones - see [21]).
The last step of the granulation process is shown in the next section.
2.2 Granular reflections
In this step we formed the granular reflections of the original training sys-
tem 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 ∈ COV (U, µ, r) from the coverage is finally represented by single object formed
using the Majority Voting (M V ) strategy (choice the most common values).
{M V ({a(u) : u ∈ g}) : a ∈ A ∪ {d}} (3)
The granular reflection of the decision system D = (U, A, d) is the decision
system (COV (U, µ, r), the set of objects formed from granules.
v ∈ grcd (u) if and only if µ(v, u, r) and (d(u) = d(v)) (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:
g0 .75(u1 ) = (u1 )
g1 (u2 ) = (u2 )
g1 (u3 ) = (u3 )
g1 (u4 ) = (u4 )
Table 1. Training data system (Utrn , A, d), (a sample from Quinlan data set [23])
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:
g0 .75(u1 ) = (u1 )
g1 (u2 ) = (u2 )
g1 (u4 ) = (u4 )
g0 .75(u6 ) = (u6 , u10 )
g0 .75(u7 ) = (u7 , u11 )
g0 .75(u8 ) = (u8 )
g0 .75(u9 ) = (u9 )
g0 .5(u11 ) = (u3 , u5 , u6 , u7 , u11 )
Granular decision system from above granules is as follows:
Table 2. Granular decision system formed from Covering granules
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 En-
semble 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 fixed number of iterations, we form a new
Training systems (N ewT RN ) by random choice with returning of card{T RN }
objects. In all iterations we classify the TRNvalid system in two ways: the first
based on the actual N ewT RN system and the second based on the committee
of all performed classifications. In the committee majority voting is performed
and the ties are resolved randomly.
Bagging based on Arcing - Bagging: The main difference 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 first classification of the NewTST using
NewTRN weights are lowered for well-classified objects. The next step is normal-
ization 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 classifiers is the last step of this method. In Arcing weights are
modified with the factor equal to 1−Accuracy
Accuracy .
Boosting based on Ada-Boost with Monte Carlo split: Classification method used
in this algorithm is similar to the previously described with the difference that
the NewTRN and NewTST are formed in a different way - see [9], [28] and [34].
Objects for NewTRN are chosen based on weights and fixed 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 classification process in each
iteration. This method can be usefull in other classifiers using the random set
of attributes before usage in classification 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 Reflections
In each iteration of our new ensemble model we have used a different homoge-
nous 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.
Fig. 1. Ensemble of Random Granular Reflections
5 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 itera-
tions 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 classifier we used CSG classifier [4] with radius
0.5. The effectiveness is evaluated by percentage of properly classified objects -
the accuracy.
The first result of Random Granular Reflections 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.
Fig. 2. Ensemble of Random Granular Reflections for australian credit dataset - the
accuracy of classification - 5 times 50 iterations of learning
Fig. 3. Bagging ensemble model for australian credit dataset - the accuracy of classi-
fication - 5 times 50 iterations of learning
Fig. 4. AdaBoost ensemble model for australian credit dataset - the accuracy of clas-
sification - 5 times 50 iterations of learning
Fig. 5. Pure Bagging ensemble model for australian credit dataset - the accuracy of
classification - 5 times 50 iterations of learning
6 Conclusions
The results of the experiments show the effectivenes of our new technique. The
Ensemble of Random Granular Reflections 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 effectiveness and set of applications of this new
method.
In the future works we have a plan to extensively check the effectiveness
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 Sci-
ence and Higher Education of the Republic of Poland.
References
1. Artiemjew, P. : Classifiers from Granulated Data Sets: Concept Dependent and Lay-
ered 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 classifiers obtained from weak rough set inclu-
sions. In Proceedings of Int. Conference on Rough Set and Knowledge Technol-
ogy RSKT’08, Chengdu China, Lecture Notes in Artificial Intelligence, vol. 5009.
Springer Verlag, Berlin, 2008, pp 229–236 (2008)
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 Effect of Classifier Based on Simple Granules of Knowledge,
In: Information technolojy and control, Print ISSN: 1392-124X, Vol 47, No 2 (2018)
5. Breiman, L.: Arcing classifier (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 Classifiers based on Rough Sets Theory and
Database Operations, Proc. of the IEEE International Conference on Data Mining
(ICDM2001), (2001)
7. Hu, X.: Ensembles of classifiers based on rough sets theory and set-oriented database
operations, Presented at the 2006 IEEE International Conference on Granular Com-
puting, Atlanta, GA (2006)
8. Murthy, C., Saha, S., Pal, S.K.: Rough Set Based Ensemble Classifier, 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-medical-
decision-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 Sci-
ences 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 Artificial Intelligencevol. 2639, Springer
Verlag, Berlin, pp 70–78 (2003)
13. Polkowski, L.: Toward rough set foundations. Mereological approach. In Proceed-
ings RSCTC04, Uppsala, Sweden. Lecture Notes in Artificial 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 Artificial 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 Unified Approach to Granulation of Knowledge and Granular
Computing Based on Rough Mereology: A Survey, in: Handbook of Granular Com-
puting, Witold Pedrycz, Andrzej Skowron, Vladik Kreinovich (Eds.), John Wiley &
Sons, New York, 375-401 (2008)
19. Polkowski, L.: Granulation of Knowledge: Similarity Based Approach in Informa-
tion 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 Mere-
ology. 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 homoge-
nous 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 granu-
lation. In: Dregvaite G., Damasevicius R. (eds) Information and Software Technolo-
gies. 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 classifier for web page
classification. 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
Classification (2003)
29. Shi, L., Weng, M., Ma, X., Xi, L.: Rough Set Based Decision Tree Ensemble Algo-
rithm for Text Classification, 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 meth-
ods 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)