# An Attribute-Value Block Based Method of Acquiring Minimum Rule Sets: A Granulation Method to Construct Classifier

Zuqiang Meng, Qiuling Gan

► To cite this version:

Zuqiang Meng, Qiuling Gan. An Attribute-Value Block Based Method of Acquiring Minimum Rule Sets: A Granulation Method to Construct Classifier. 9th International Conference on Intelligent Information Processing (IIP), Nov 2016, Melbourne, VIC, Australia. pp.3-11, 10.1007/978-3-319-48390-0_1. hal-01615000

HAL Id: hal-01615000

https://inria.hal.science/hal-01615000

Submitted on 11 Oct 2017

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# An Attribute-value Block based Method of Acquiring Minimum Rule Sets: A Granulation Method to Construct Classifier

Zuqiang Meng, Qiuling Gan

College of Computer, Electronics and Information, Guangxi University
Nanning, Guangxi, 530004, China
zqmeng@126.com

**Abstract.** Decision rule acquisition is one of the important topics in rough set theory and is drawing more and more attention. In this paper, decision logic language and attribute-value block technique are introduced first. And then realization methods of rule reduction and rule set minimum are relatively systematically studied by using attribute-value block technique, and as a result effective algorithms of reducing decision rules and minimizing rule sets are proposed, which, together with related attribute reduction algorithm, constitute an effective granulation method to acquire minimum rule sets, which is a kind of classifier and can be used for class prediction. At last, related experiments are conducted to demonstrate that the proposed methods are effective and feasible.

**Keywords:** rule acquisition, attribute-value blocks, decision rule set, classifier

## 1 Introduction

Rough set theory [1], as a powerful mathematical tool to deal with insufficient, incomplete or vague information, has been widely used in many fields. In rough set theory, the study of attribute reduction seems to attract more attention than that of rule acquisition. But in recent years there have been more and more studies involving the decision rule acquisition. Papers [2,3] gave discernibility matrix or the discernibility function-based methods to acquire decision rules. These methods are able to acquire all minimum rule sets for a given decision system theoretically, but they usually would pay both huge time cost and huge space cost, which extremely narrow their applications in real life. In addition, paper [4] discussed the problem of producing a set of certain and possible rules from incomplete data sets based on rough sets and gave corresponding rule learning algorithm. Paper [5] discussed optimal certain rules and optimal association rules, and proposed two quantitative measures, random certainty factor and random coverage factor, to explain relationships between the condition and decision parts of a rule in incomplete decision systems. Paper [6] also discussed the rule acquisition in incomplete decision contexts. This paper presented the notion of an approximate decision rule, and then proposed an approach for extracting non-redundant approximate decision rules from an incomplete decision context. But the proposed method is also based on discernibility matrix and discernibility function, which determines that it is relatively difficult to acquire decision rules from large data sets.

Attribute-value block technique is an important tool to analyze data sets [7,8].
Actually, it is a granulation method to deal with data. Our paper will use the attribute-value block technique and other related techniques to systematically study realization methods of rule reduction and rule set minimum, and propose effective algorithms of reducing decision rules and minimizing decision rule sets. These algorithms, together with related attribute reduction algorithm, constitute an effective solution to the acquisition of minimum rule sets, which is a kind classifier and can be used for class prediction.

The rest of the paper is organized as follows. In Section 2, we review some basic notions linked to decision systems. Section 3 introduces the concept of minimum rule sets. Section 4 gives specific algorithms for rule reduction and rule set minimum based on attribute-value blocks. In Section 5, some experiments are conducted to verify the effectiveness of the proposed methods. Section 6 concludes this paper.

## 2 Preliminaries

In this section, we first review some basic notions, such as attribute-value blocks, decision rule sets, which are prepared for acquiring minimum rule sets in next sections.

### 2.1 Decision systems and relative reducts

A decision system (DS) can be expressed as the following 4-tuple: $DS = (U, A = C \cup D, V = \bigcup_{a \in A} V_a, \{f_a\})$, where $U$ is a finite nonempty set of objects; $C$ and $D$ are condition attribute set and decision attribute set, respectively, and $C \cap D = \emptyset$; $V_a$ is a value domain of attribute $a$; $f_a: U \to V$ is an information function from $U$ to $V$, which maps an object in $U$ to a value in $V_a$.

For simplicity, $(U, A = C \cup D, V = \bigcup_{a \in A} V_a, \{f_a\})$ is expressed as $(U, C \cup D)$ if $V$ and $f_a$ are understood. Without loss of generality, we suppose $D$ is supposed to be composed of only one attribute.

For any $B \subseteq C$, let $U/B = \{[x]_B | x \in U\}$, where $[x]_B = \{y \in U | f_a(y) = f_a(x) \text{ for any } a \in B\}$, which is known as equivalence class. For any subset $X \subseteq U$, the lower approximation $\underline{BX}$ and the upper approximation $\overline{BX}$ of $X$ with respect to $B$ are defined by: $\underline{BX} = \{x \in U | [x]_B \subseteq X\}$, $\overline{BX} = \{x \in U | [x]_B \cap X \neq \emptyset\}$. And then the concepts of positive region $POS_B(X)$, boundary region $BND_B(X)$ and negative region $NEG_B(X)$ of $X$ are defined as: $POS_B(X) = \underline{BX}$, $BND_B(X) = \overline{BX} - \underline{BX}$, $NEG_B(X) = U - \overline{BX}$.

Suppose that $U/D = \{[x]_D | x \in U\} = \{D_1, D_2, ..., D_m\}$, where $m = |U/D|$, $D_i$ is a decision class, $i \in \{1,2,...,m\}$. Then for any $B \subseteq C$, the concepts of positive region $POS_B(D)$, boundary region $BND_B(D)$ and negative region $NEG_B(D)$ of a decision system $(U, C \cup D)$ can be defined as follows:

$$POS_B(D) = POS_B(D_1) \cup POS_B(D_2) \cup \dots \cup POS_B(D_m),$$

$$BND_B(D) = BND_B(D_1) \cup BND_B(D_2) \cup \dots \cup BND_B(D_m),$$

$$NEG_B(D) = U - POS_B(D) \cup BND_B(D).$$

With the positive region, the concept of reducts can be defined as follows: given a decision system $(U, C \cup D)$ and $B \subseteq C$, $B$ is a **relative reduct** of $C$ with respect to $D$ if
the following conditions are satisfied: (1) POS<sub>B</sub>(D) = POS<sub>C</sub>(D), and (2) for any a ∈ B, POS<sub>B-{a}</sub>(D) ≠ POS<sub>B</sub>(D).

## 2.2 Decision logic and attribute-value blocks

Decision rules are in fact related formulae in decision logic. In rough set theory, a decision logic language depends on a specific information system, while a decision system (U, C ∪ D) can be regarded as being composed of two information systems: (U, C) and (U, D). Therefore, there are two corresponding decision logic languages, while attribute-value blocks just act as a bridge between the two languages. For the sake of simplicity, let IS(B) = (U, B, V = ⋃<sub>a∈A</sub> V<sub>a</sub>, {f<sub>a</sub>}) is an information system with respect to B,

where B ⊆ C or B ⊆ D. Then a decision logic language DL(B) is defined as a system being composed of the following formulae [3]:

(1) (a, v) is an atomic formula, where a ∈ B, v ∈ V<sub>a</sub>;

(2) an atomic formula is a formula in DL(B);

(3) if φ is a formula, then ¬φ is also a formula in DL(B);

(4) if both φ and ψ are formulae, then φ ∨ ψ, φ ∧ ψ, φ → ψ, φ ≡ ψ are all formulae;

(5) only the formulae obtained according to the above Steps (1) to (4) are formulae in DL(B).

The atomic formula (a, v) is also called **attribute-value pair** [7]. If φ is a simple conjunction, which consists of only atomic formulae and connectives ∧, then φ is called a **basic formula**.

For any $x \in U$, the relationship between $x$ and formulae in $DL(B)$ is defined as following:

(1) $x \models (a, v) \text{ iff } f_a(x) = v$;

(2) $x \models \neg \varphi \text{ iff not } x \models \varphi$;

(3) $x \models \varphi \wedge \psi \text{ iff } x \models \varphi \text{ and } x \models \psi$;

(4) $x \models \varphi \vee \psi \text{ iff } x \models \varphi \text{ or } x \models \psi$;

(5) $x \models \varphi \rightarrow \psi \text{ iff } x \models \neg \varphi \vee \psi$;

(6) $x \models \varphi \equiv \psi \text{ iff } x \models \varphi \rightarrow \psi \text{ and } x \models \psi \rightarrow \varphi$.

For formula φ, if xmodels φ, then we say that the object x satisfies formula φ. Let [φ] = { x ∈ U | x = φ}, which is the set of all those objects that satisfy formula φ. Obviously, formula φ consists of several attribute-value pairs by using connectives. Therefore, [φ] is so-called an **attribute-value block** and φ is called the (**attribute-value pair**) **formula** of the block. For DL(C) and DL(D), they are distinct decision logic languages and have no formulae in common. However, through attribute-value blocks, an association between DL(C) and DL(D) can be established. For example, suppose φ ∈ DL(C) and ψ ∈ DL(D) and obviously φ and ψ are two different formulae; but if [φ] ⊆ [ψ], we can obtain a decision rule φ→ψ. Therefore, attribute-value blocks play an important role in acquiring decision rules, especially in acquiring certainty rules.

# 3 Minimum rule sets

Suppose that φ ∈ DL(C) and ψ ∈ DL(D). Implication form φ→ψ is said to be a (**decision**) **rule** in decision system (U, C ∪ D). If both φ and ψ are basic formula, then
$\varphi \to \psi$ is called **basic decision rule**. A decision rule is not necessarily useful unless it satisfies some given indices. Below we introduce these indices.

A decision rule usually has two important measuring indices, confidence and support, which are defined as: $conf(\varphi \to \psi) = |[\varphi] \cap [\psi]| / |[\varphi]|$, $sup(\varphi \to \psi) = |[\varphi] \cap [\psi]| / |U|$, where $conf(\varphi \to \psi)$ and $sup(\varphi \to \psi)$ are **confidence** and **support** of decision rule $\varphi \to \psi$, respectively.

For decision system $DS = (U, C \cup D)$, if rule $\varphi \to \psi$ is true in $DL(C \cup D)$, i.e., for any $x \in U$, $x \models \varphi \to \psi$, then rule $\varphi \to \psi$ is said to be **consistent** in $DS$, denoted by $\models_{DS} \varphi \to \psi$; if there exists at least object $x \in U$ such that $x \models \varphi \land \psi$, then rule $\varphi \to \psi$ is said to be **satisfiable** in $DS$. Consistency and satisfiability are the basic properties that must be satisfied by decision rules.

For object $x \in U$ and decision rule $r: \varphi \to \psi$, if $x \models r$, then it is said that rule $r$ **covers** object $x$, and let $coverage(r) = \{x \in U | x \models r\}$, which is the set of all objects that are **covered** by rule $r$; for two rules, $r_1$ and $r_2$, if $coverage(r_1) \subseteq coverage(r_2)$, then it is said that $r_2$ **functionally covers** $r_1$, denoted by $r_1 \leq r_2$. Obviously, if there exist such two rules, then rule $r_1$ is redundant and should be deleted, or in other words, those rules that are functionally covered by other rules should be removed out from rule sets.

In addition, for a rule $\varphi \to \psi$, we say that $\varphi \to \psi$ is **reduced** if $[\varphi] \subseteq [\psi]$ does not hold any more when any attribute-value pair is removed from $\varphi$. And this is just known as rule reduction, which will be introduced in next section.

A decision rule set $\mathcal{D}$ is said to be **minimal** if it satisfies the following properties [3]: (1) any rule in $\mathcal{D}$ should be consistent; (2) any rule in $\mathcal{D}$ should be satisfiable; (3) any rule in $\mathcal{D}$ should be reduced; (4) for any two rules $r_1, r_2 \in \mathcal{D}$, neither $r_1 \leq r_2$ nor $r_2 \leq r_1$.

In order to obtain a minimum rule set from a given data set, it is required to complete three steps: attribute reduction, rule reduction and rule set minimum. This paper does not introduce attribute reduction methods any more, and we try to propose new methods for rule reduction and for rule set minimum in next sections.

# 4 Methods of acquiring decision rules

## 4.1 Rule reduction

Rule reduction is to keep the minimal attribute-value pairs in a rule such that the rule is still consistent and satisfiable by removing redundant attributes from the rule. For the convenience of discussion, we let $r(x)$ denote a decision rule that is generated with object $x$, and introduce the following definitions and properties.

**Definition 1.** For decision system $DS = (U, C \cup D)$, $B = \{a_1, a_2, ..., a_m\} \subseteq C$ and $x \in U$, let $pairs(x, B) = (a_1, f_{a_1}(x)) \land (a_2, f_{a_2}(x)) \land ... \land (a_m, f_{a_m}(x))$ and let $block(x, B) = [pairs(x, B)] = [(a_1, f_{a_1}(x)) \land (a_2, f_{a_2}(x)) \land ... \land (a_m, f_{a_m}(x))]$, and the number $m$ is called the lengths of $pairs(x, B)$ and $block(x, B)$, denoted by $|pairs(x, B)|$ and $|block(x, B)|$, respectively.

**Property 1.** Suppose $B_1, B_2 \subseteq C$ with $B_1 \subseteq B_2$, then $block(x, B_2) \subseteq block(x, B_1)$.

The proof of Property 1 is straightforward. According to this property, for an attribute subset $B$, $block(x, B)$ increases with removing attributes from $B$, but with the prerequisite that $block(x, B)$ does not "exceed" the decision class $[x]_D$, to which $x$
belongs. Therefore, how to judge whether *block(x, B)* is still contained in [*x*]D or not is
crucial for rule reduction.

**Property 2.** For decision system $DS = (U, C \cup D)$ and $B \subseteq C$, $block(x, B) \subseteq [x]_D$
(=$block(x, D)$) if and only if $f_d(y) = f_d(x)$ for all $y \in block(x, B)$.

The proof of Property 2 is also straightforward. This property shows that the problem of judging whether *block(x, B)* is contained in [*x*]D becomes that of judging whether *f*<sub>*d*</sub>(*y*) = *f*<sub>*d*</sub>(*x*) for all *y* ∈ *block(x, B)*. Evidently, the latter is much easier than the former. Thus, we give the following algorithm for reducing a decision rule.

**Algorithm 1:** an algorithm for reducing a decision rule

**Input:** decision system (U, C ∪ D) and object x ∈ U, where C = {a₁, a₂, ..., aₙ}, n = |C|, D = {d}

**Output:** reduced decision rule *r(x)*

Begin

Step 1. Let $B = C$;

Step 2. For $i = 1$ to $|C|$ do

Step 3. Let $B = B - \{a_i\}$;

Step 4. Compute *block(x, B)*;

Step 5. For each $y \in block(x, B)$ do

Step 6. If $f_d(y) \neq f_d(x)$ then { Let $B = B \cup \{a_i\}$; break; }

Step 7. Let $\varphi = \text{pairs}(x, B)$ and $\psi = (d, f_d(x))$;

Step 8. Let $r(x) = \varphi \rightarrow \psi$;

Step 9. return $r(x)$;

End.

The time-consuming step in this algorithm is to compute *block(x, B)*, whose
comparison number is |*U*||*B*|. Therefore, the complexity of this algorithm is *O*(|*U*||*C*|²)
in the worst case. According to Algorithm 1, it is guaranteed at any time that *block(x, B)*
⊆ [*x*]D=*block(x, D)*, so the confidence of rule *r(x)* is always equal to 1.

**4.2 Minimum of decision rule sets**

Using Algorithm 1, each object in *U* can be used to generate a rule. This means that after
reducing rules, there are still |*U*| rules left. Obviously, there must be many rules that are
covered by other rules, and hereby we need to delete those rules which are covered by
other rules.

For decision system (U, C ∪ D), after using Algorithm 1 to reduce each object x ∈ U,
all generated rules *r(x)* constitute a rule set, denoted by *RS*, i.e., *RS* = {*r(x)* | x ∈ *U*}.
Obviously, |*RS*| = |*U*|. Our purpose in this section is to delete those rules which are
covered by other rules, or in other words, to minimize *RS* such that each of the
remaining rules is consistent, satisfiable, reduced, and is not covered by other rules.

Suppose $V_d = \{v_1, v_2, ..., v_i\}$. We use decision attribute *d* to partition *U* into *t* attribute-value blocks (equivalence classes): [*d*, *v*₁], [*d*, *v*₂], ..., [*d*, *v*ᵢ]. Let $U_{v_i} = [ (d, v_i) ]$, and thus $\bigcup_{i \in \{1, 2, ..., t\}} U_{v_i} = U$ and $U_{v_i} \cap U_{v_j} = \emptyset$, where $i \neq j$, $i, j \in \{1, 2, ..., t\}$.
Accordingly, let $RS_{v_i} = \{r(x) | x \in U_{v_i}\}$, where $i \in \{1, 2, ..., t\}$. Obviously, $\{RS_{v_i} | i \in \{1, 2, ..., t\}\}$ is a partition of *RS*. According to Algorithm 1, for any $r' \in RS_{v_i}$ and $r'' \in RS_{v_j}$, where $i \neq j$, neither $r' \le r''$ nor $r'' \le r'$, because $\text{coverage}(r') \subseteq U_{v_i}$ while
coverage(r'') ⊆ $U_{v_j}$ and then coverage(r') ∩ coverage(r'') = Ø. This means that a rule in $RS_{v_i}$ does not functionally covers any rule in $RS_{v_j}$. Thus, we can independently minimize each $RS_{v_i}$, and the union of all the generated rule subsets is the final minimum rule set that we want.

Let independently consider $RS_{v_i}$, where $i \in \{1,2,...,t\}$. For $r(x) \in RS_{v_i}$, if there exists $r(y) \in RS_{v_i}$ such that $r(x) \le r(y)$ ($r(y)$ functionally covers $r(x)$), where $x \ne y$, then $r(x)$ should be removed from $RS_{v_i}$, otherwise it should not. Suppose after removing, the set of all remaining rules in $RS_{v_i}$ is denoted by $RS'_{v_i}$, and thus we can give an algorithm for minimizing $RS_{v_i}$, which is described as follows.

**Algorithm 2:** an algorithm for minimizing $RS_{v_i}$

**Input:** $U_{v_i} = \{x_1, x_2, ..., x_q\}$ and $RS_{v_i} = \{r(x_1), r(x_2), ..., r(x_q)\}$

**Output:** $RS'_{v_i}$

Begin

Step 1. Let $\wp = RS_{v_i}$;

Step 2. For $j = 1$ to $q$ do $// q = |RS_{v_i}|$

Step 3. Let $\wp = \wp - \{r(x_j)\}$;

Step 4. Let flag = 1;

Step 5. For each $r \in \wp$ do

Step 6. If $x_j \in \text{coverage}(r)$ then $\{ \text{flag} = 0; \text{break;} \}$

Step 7. If flag = 1 then $\wp = \wp \cup \{r(x_j)\}$;

Step 8. Let $RS'_{v_i} = \wp$;

Step 9. Return $RS'_{v_i}$;

End.

In Algorithm 2, judging if $x_j \in \text{coverage}(r)$ takes at most $|C|$ comparison times. But because all rules in $RS_{v_i}$ have been reduced by Algorithm 1, the comparison number should be much smaller than $|C|$. Therefore, the complexity of Algorithm 2 is $O(q^2 \cdot |C|) = O(|U_{v_i}|^2 \cdot |C|)$ in the worst case.

### 4.3 An algorithm for acquiring minimum rule sets

Using the above proposed algorithms and related attribute reduction algorithms, we now can give an entire algorithm for acquiring a minimum rule set from a given data set. The algorithm is described as follows.

**Algorithm 3:** an algorithm for acquiring a minimum rule set from a data set

**Input:** decision system $DS = (U, C \cup D)$

**Output:** a minimum rule set, $minRS$

Begin

Step 1. Use an attribute reduction algorithm to find a reduct of $DS$, and suppose the reduct is $R$;

Step 2. Compute $U/R$, and then select one object in each equivalence class
in $U/R$ to constitute a new decision system $(U', R \cup D)$;

Step 3. Reduce each object (rule) in $(U', R \cup D)$ using Algorithm 1, and suppose the obtained rule set is denoted by $RS$;

Step 4. Use decision attribute set $D$ to partition $U'$ into several decision classes: $U'_{v_1}, U'_{v_2}, \dots, U'_{v_r}$, and then let $RS_{v_i} = \{r(x) \mid x \in U'_{v_i}\}$, where $i \in \{1, 2, \dots, t\}$;

Step 5. In turn or in parallel minimize $RS_{v_1}, RS_{v_2}, \dots, RS_{v_r}$ using Algorithm 2, and suppose corresponding results are $RS'_{v_1}, RS'_{v_2}, \dots, RS'_{v_r}$;

Step 6. Let $minRS = RS'_{v_1} \cup RS'_{v_2} \cup \dots \cup RS'_{v_r}$;

Step 7. Return $minRS$;

End.

In Algorithm 3, there are three steps used to "evaporating" redundant data: Steps 2, 3, 5. These steps also determine the complexity of the entire algorithm. Actually, the newly generated decision system $(U', R \cup D)$ in Step 2 is completely determined by Step 1, which is attribute reduction and has the complexity of about $O(|C|^2|U|^2)$. The complexity of Step 3 is $O(|U'|^2|C|^2)$ in the worst case. Step 5's complexity is $O(|U'_{v_1}|^2|C|) + O(|U'_{v_2}|^2|C|) + \dots + O(|U'_{v_r}|^2|C|)$. Because this step can be performed in parallel, so it can be more efficient under parallel environment. Generally, after attribute reduction, the size of a data set would greatly decrease, i.e., $|U'| \ll |U|$. Therefore, computation time of Algorithm 3 is mainly determined by Step 1, so it has the complexity of $O(|C|^2|U|^2)$ in most cases.

# 5 Experiment analysis

This section aims to verify the effectiveness of the proposed methods through experiments. There are four UCI data sets (http://archive.ics.uci.edu/ml/datasets.html) used in our experiments, and they are outlined in Table 1. For missing values, they were replaced with the most frequently occurring value on the corresponding attribute.

We executed Algorithm 3 on the four data sets to obtain minimum rule sets. Suppose that the set of finally obtained decision rules on each data set is denoted by $minRS$. The indices that we are interesting in and their meanings are as follows.

* Number of rules: $|minRS|$, i.e., the number of decision rules in $minRS$

* Average value of support: $\frac{1}{|minRS|} \sum_{r \in minRS} sup(r)$, and $minValue = \min\{sup(r)\}, maxValue = \max\{sup(r)\} \quad r \in minRS$

* Average value of confidence: $\frac{1}{|minRS|} \sum_{r \in minRS} conf(r)$

* Evaporation ratio: the ratio of removed items (attribute values) to all items (all attribute values)

* Running time: the running time of Algorithm 3, which includes attribute reduction, rule reduction and minimum of decision rule sets, and this index is measured in seconds.
The experimental results on the four data sets are shown in Table 2.

<table><caption>**Table 1.** Description of the four data sets.</caption><thead><tr><th>No.</th><th>Data sets</th><th>Abbreviation</th><th>|U|</th><th>|C|</th><th>|V<sub>d</sub>|</th></tr></thead><tbody><tr><td>1</td><td>Dermatology Database</td><td>Dermatology</td><td>366</td><td>34</td><td>6</td></tr><tr><td>2</td><td>Tic-Tac-Toe Endgame database</td><td>Tic-Tac-Toe</td><td>958</td><td>9</td><td>2</td></tr><tr><td>3</td><td>Mushroom Database</td><td>Mushroom</td><td>8124</td><td>22</td><td>2</td></tr><tr><td>4</td><td>Nursery Database</td><td>Nursery</td><td>12960</td><td>8</td><td>5</td></tr></tbody></table>

<table><caption>**Table 2.** Experimental results on the four data sets.</caption><thead><tr><th>Data set</th><th>Number of rules</th><th>Average value of support (minValue, maxValue)</th><th>Average value of confidence</th><th>Evaporation ratio</th><th>Running time (Sec.)</th></tr></thead><tbody><tr><td>Dermatology</td><td>72</td><td>0.0146<br>(0.0027, 0.1257)</td><td>1</td><td>0.9794</td><td>0.14</td></tr><tr><td>Tic-Tac-Toe</td><td>176</td><td>0.0066<br>(0.0010, 0.0940)</td><td>1</td><td>0.9072</td><td>0.16</td></tr><tr><td>Mushroom</td><td>17</td><td>0.0689<br>(0.0010, 0.2166)</td><td>1</td><td>0.9998</td><td>2.37</td></tr><tr><td>Nursery</td><td>305</td><td>0.0031<br>(0.00008, 0.3333)</td><td>1</td><td>0.9831</td><td>31.34</td></tr></tbody></table>

From Table 2, it can be found that the obtained rule sets on the four data sets all have very high evaporation ratio, and each rule in these rule sets has certain support. Specially, there are averagely 0.0689*8124 = 560 objects supporting each rule in the rule set obtained on Mushroom. This shows that these rule sets have relatively strong generalization ability. Furthermore, the running time of Algorithm 3 on each data set is not long and hereby can be accepted by users. In addition, Algorithm 1 can guarantee at any time that $block(x, B) \subseteq [x]_D=block(x, D)$ for all $x \in U$, so the confidence of each rule is always equal to 1, or in other words all the obtained decision rules are deterministic. All these results demonstrate Algorithm 3 is effective and has better application value.

# 6 Conclusion

Acquiring decision rules from data sets is an important task in rough set theory. This paper conducted our study through the following three aspects so as to provide an effective granulation method to acquire minimum rule sets. Firstly, we introduced decision logic language and attribute-value block technique. Secondly, we used attribute-value block technique to study how to reduce rules and to minimize rule sets, and then proposed effective algorithms for rule reduction and rule set minimum. Thus, together with related attribute reduction algorithm, the proposed granulation method constituted an effective solution to the acquisition of minimum rule sets, which is a kind classifier and can be used for class prediction. Thirdly, we conducted a series of experiments to show that our methods are effective and feasible.

# Acknowledgements

This work is supported by the National Natural Science Foundation of China (No. 61363027), the Guangxi Natural Science Foundation (No. 2015GXNSFAA139292).
References

1. Pawlak, Z.: Rough Set. International Journal of Computer of Computer and Information Sciences, 11(5): 341-356 (1982)

2. Guan, Y.Y., Wang, H.K., Wang, Y., and Yang, F.: Attribute Reduction and Optimal Decision Rules Acquisition for Continuous Valued Information Systems. Information Sciences, 179(17): 2974-2984 (2009)

3. Meng, Z.Q., Jiang, L., and Chang, H.Y.: A Heuristic Approach to Acquisition of Minimum Decision Rule Sets in Decision Systems. IFIP 8th International Conference on Intelligent Information Processing (IIP2014), Hangzhou, China (2014)

4. Hong, T.P., Tseng, L.H., and Wang, S.L.: Learning Rules from Incomplete Training Examples by Rough Sets. Expert Systems with Applications, 22(4): 285-293 (2002)

5. Leung, Y., Wu, W.Z., and Zhang, W.X.: Knowledge Acquisition in Incomplete Information Systems: A Rough Set Approach. European Journal of Operational Research 168(1): 164-180 (2006)

6. Li, J.H., Mei, C.L., and Lv, Y.J.: Incomplete Decision Contexts: Approximate Concept Construction, Rule Acquisition and Knowledge Reduction. International Journal of Approximate Reasoning, 54(1): 149-165 (2013)

7. Grzymala-Busse, J.W., Clark, P. G., and Kuehnhausen, M.: Generalized Probabilistic Approximations of Incomplete Data. International Journal of Approximate Reasoning, 55(1): 180-196 (2014)

8. Patrick, G.C., Grzymala-Busse, J.W.: Mining Incomplete Data with Attribute-Concept Values and “Do Not Care” Conditions. IEEE International Conference on Big Data, IEEE (2015)