This article presents a comparison of classi cation e ects using an exhaustive set of decision-making rules and a granular set of rules. Standard approach is that we perform granulation of the chosen data set looking for the optimal granulation radius and at the end we generate new decision rules, where on the other side, our method is based on the idea of building decision rules rst and then granulating them using known methods.
Data approximation methods are especially important in big data analysis where
often the internal knowledge is more important than the single data sample itself.
One of the most important paradigms is granular rough computing. This idea
introduces the concept of data granules in terms of rough sets theory [
In [
New techniques and their applications were developed and described in
([
There are many other granulation techniques like concept-dependent granulation, layered granulation and recently developed homogeneous granulation [28]. Main goal of granulation process is to reduce the amount of data but at the same time the internal knowledge must be maintained to allow acceptable level of classi cation accuracy.
One of the simplest idea of data classi cation is by building decision rules based on those data and then combine them with a classi er. Once again there are many know methods of rules generation algorithms starting from exhaustive rules, by LEM2 algorithm or sequential covering . When we consider the fact, that the granulation is reducing the amount of data that is being processed during classi cation, and in some cases we can further reduce this amount by generating decision rules, we thought of an idea of rules granulation as an extension of this approach. In the next part of this section we will present some theoretical introduction to the classical methods we were using as a base of comparison to our approach.
The rest of the paper has the following content. In Sect. 1 we present the theoretical introduction to granular rough computing and decision rules. In Sect. 2 we detail the description of our approach to rules granulation with a toy example. In Sect. 3 we introduce the classi er used in experimental part. In Sect. 4 experiment results are presented, and we conclude the paper in Sect. 5.
The granulation process consists of three basic steps, the granules are formed around the training objects, the covering of universe of training objects is chosen, and nally granular re ection from covering granules is obtained by majority voting procedure. As a nal step decision rules are built and a classi cation process is being performed. We begin with the basic notions of rough inclusions to introduce the rst step. 1.1
Theoretical background - granular rough inclusions
The models for rough mereology which give us methods by which the rough
inclusions are de ned, are presented in Polkowski [
For a rough inclusion on the universe U of a decision system D = (U; A; d). We introduce the parameter rgran, the granulation radius with values 0; j A1j ; j A2j ; :::; 1. For each object u 2 U , and r = rgran, the standard granule g(u; r; ), of radius r about u, is de ned as
The standard rough inclusion is de ned as g(u; r; ) is fv 2 U : (v; u; r)g: (v; u; r) , jInd(u; v)j
A j j
r v 2 grcd(u) if and only if (v; u; r) and (d(u) = d(v)) for a given rough (weak) inclusion .
In the next section rules granulation method is presented. (1) (2) (3) (4) (5) where
IN D(u; v) = fa 2 A : a(u) = a(v)g;
It follows that this rough inclusion extends the indiscernibility relation to a degree of r. 1.2
In this step the universe of training objects should be covered by computed
granules using a selected strategy. One of the most e ective methods among the
studied ones (see [
Once the granular covering is selected, the idea is to represent granules by single objects. The strategy for obtaining it can be the majority voting M V , so for each granule g 2 COV (U; ; r), the nal representation is formed as follows fM V (fa(u) : u 2 gg) : a 2 A [ fdgg where for numerical data we treat the descriptors as indiscernible in case jmaia(xua) amji(nua)j ", i; j are the numbers of objects in granule,
The granular re ection of the decision system D = (U; A; d),(where U is the universe of objects, A the set of conditional attributes and d is decision attribute), (COV (U; ; r)) is formed from granules.
Approach which was used for rules granulation can be described in following steps.
Exhaustive rules from given dataset are generated.
Rules with length = 1 (only one descriptor) are omitted and moved to nal set.
Rules are divided into separate sets with rules of the same length. For each set the concept granulation is being performed, it means that only rules from the same decision class are compared when computing the indiscernibility. New rules are created using majority voting method and possible con icts are resolved by random.
Newly created rules for each length and indiscernibility radius are being put together. Support (number of occurrences) for each rule is calculated and possible con icting rules are removed. This approach favors longer rules because of the higher support value.
Because of the fact that this granulation approach brings just slightly bigger
number of rules, especially for the larger datasets it is hard to present a solid
toy example. Following sample from Australian-credit dataset will show the
concepts of concept dependent rules granulation.
10 randomly selected rules from exhaustive set generated on Australian-credit.
Rules with length 1 were omitted.
(a2=34.08) (a6=4.0) ) d = 0:0[
Let's take three rules into consideration
(a3 = 1:0) (a9 = 1:0) (a11 = 0:0) ) d = 1:0[
Final set of granuled rules looks as follows.
(a2 = 34:08) (a6 = 4:0) ) d = 0:0[
We have designed rule based classi er, which consists of tting the set of decision rules into classi ed objects and vote for decision. The ties are resolved randomly. We have measured the e ectiveness using global accuracy parameter, which can be de ned as the percentage of correctly classi ed objects. We use exhaustive set of rules in our experiments, with minimal descriptors length. We are generating no con icting decision rules starting from the ones with length equal to one. This algorithm nishes his work with the rule length, in which there are no more candidates or minor number of rules, in comparison with the whole computed set, is generated.
We have carried out experiments on exemplary real data from UCI Repository. Used dataset description is presented in Table 1 while results of granulation and classi cation in Table 2 and Table 3 respectively.
We have used our own implementation of exhaustive algorithm, basic method for results evaluation is Cross Validation 5 technique.
In this work we have considered the technique of exhaustive set of rules granulation. We have compared the set of decision rules after their granulation vs rules computed from granulated decision systems. It was proven that its better to granulate and compute rules than compute rules and granulate them. In the latter case we have lose of the information. It is di cult to merge rules after their granulation. The granulation process of exhaustive decision rules seems to be ine ective, because the rules are designed in MDL (minimal description length) model, and they are not redundant. Granulation process works good in case there are many indiscernible values in the granulated entity. 6
The research has been supported by grant 23:610:007-300 from Ministry of Science and Higher Education of the Republic of Poland. 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) 26. University of California, Irvine Machine Learning Repository: https://archive.ics.uci.edu/ml/index.php 27. 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) 28. 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)