6.4.2Dynamic fuzzy tree hierarchy relationship learning algorithm

1. ID3 algorithm and sample analysis

Decision tree learning is one of the most widely used inductive reasoning algorithms for learning disjunctive expressions. The decision tree classifies an instance from the root node to a leaf node, and the leaf nodes are the classification of instances. Each node in the tree specifies a test for a property of the instance, and each successive layer of the node corresponds to a possible value of the property. The method of classification is to start from the root node of the tree, test the properties specified by the node, and then move down according to the branch corresponding to the value of the property for the given instance. This process is then repeated with the new node as the root of the sub-tree.

ID3 is based on the information entropy decision tree classification algorithm, using the top-down structure of the decision tree to learn [52]. According to the attribute value used to judge the category of samples, the statistical attribute of information gain is introduced to measure the ability of the given attribute to distinguish the training samples.

Consider a set of training samples X consisting of Ni training samples belonging to class i. The probability of a sample belonging to class i is pi, and

$p_i=\frac{N_i}{\left|X\right|},\left(6.17\right)$

where |X| is the number of samples in X.

To precisely define the information gain, the entropy metric is widely used in information theory to describe the purity of any sample set [52].

Assume the objective attribute has k different values. The entropy of the training set X corresponding to k classification states is defined as

$\mathrm{Entropy}\left(X\right)={\displaystyle \sum _{i=1}^k-p_i\text{lb}{p}_i.\left(6.18\right)}$

The definition of some attribute A corresponding to the information gain Gain(X, A) is

$\mathrm{Gain}\left(X,A\right)=\mathrm{Entropy}\left(X\right)-{\displaystyle \sum _{v\in Values\left(A\right)}\frac{\left|X_y\right|}{\left|X\right|}\mathrm{Entropy}\left(X_v\right).\left(6.19\right)}$

where Values(A) is the set of all possible values for attribute A, Xv is the subset of values v of attribute A; that is, Xv = {x ∈ X|A(x) = v}. The first term of this formula is the entropy of the original set X, and the second term is the expectation of the entropy of attribute A classified by X.

The following uses the traffic situation of a city as an example to explain the actual procedure of the ID3 algorithm. The training samples are listed in Tab. 6.6.

When the algorithm starts, all samples are contained in the root node. To determine the best division attribute, calculate the entropy of the training samples according to (6.18):

$\mathrm{Entropy}\left(X\right)\equiv \frac{6}{12}lb\frac{6}{12}-\frac{6}{12}lb\frac{6}{12}=1.$

Tab. 6.6: Sample set of traffic conditions in a city.

Then, we can calculate the entropy of each attribute in the training sample set:

$\mathrm{Entropy}\left(X_{rushour},true\right)\equiv -\frac{4}{12}lb\frac{4}{12}-\frac{2}{6}lb\frac{2}{6}=0.918$

and

$\mathrm{Entropy}\left(X_{rushour},false\right)\equiv -\frac{2}{6}lb\frac{2}{6}-\frac{4}{6}lb\frac{4}{6}=0.918$

Calculate the information gain of attribute “Rushhour” according to (6.19):

$\begin{array}{l}\mathrm{Gain}\left(X,Rushour\right)\equiv \mathrm{Entropy}\left(X\right)-{\displaystyle \sum _{v\in \left\{true,false\right\}}\frac{\left|X_v\right|}{\left|X\right|}\mathrm{Entropy}\left(X_v\right)}\\ =1-\left(\frac{1}{2}\times 0.918+\frac{1}{2}\times 0.918\right)=\mathrm{0.082.}\end{array}$

In the same way, we can obtain information for attributes “Weather” and “Trafficjam”: Gain(X, Weather) = 0.459 and Gain(X, Trafficjam) = 0.

Overall, the information gain of “Weather” is the greatest, so the classification attribute on this node is “Weather”. This procedure is repeated to obtain the decision tree shown in Fig. 6.4.

2. Analysis and representation of dynamic fuzzy problems using decision trees

The ID3 decision tree algorithm eventually establishes the final decision tree, from which we identify information on the relevant attributes of the example set. Tab. 6.6 presents the sample set, including “Rushhour”, “Weather”, “Trafficjam”, and “Annlate”. Taking “"Weather” as an example to illustrate the analysis, its range is {good, normal, bad}. These three properties are not clear – there is no exact standard to measure what is good, normal, or bad, that is, the condition of the attribute value of “Weather” is blurred; on the other hand, the “Weather” is constantly changing and developing, which indicates that it has a dynamic and fuzzy character. It can be seen that the decision tree learning system, which is based on the operation of the attribute, is a system with dynamic fuzziness.

Knowledge representation of dynamic fuzzy problems in decision trees is as follows.

(1)For attribute xi, use a value of attribute xi to replace xi. This is represented as $\left({\overleftarrow{x}}_i,{\overrightarrow{x}}_j\right),$ where the attribute has dynamic fuzziness and is a dynamic fuzzy number; in Tab. 6.6, the attribute “Rushhour” is replaced by “Rushhour=true”, and its range is $\left(\overleftarrow{0.7},\overrightarrow{0.3}\right),$ which is the attribute value after being transformed using the dynamic fuzzy number $\left(\overleftarrow{\alpha },\overrightarrow{\alpha }\right)$ to represent the degree to which Rushhour is true or false.

(2)For samples <x, c(x)>, where x = <x1, x2, . . ., xi>, x represents the training samples, and xi represents the attributes contained in the attribute. According to (1), the attribute has dynamic fuzziness, and the dynamic fuzziness of the samples is reflected by its attribute value. Thus, we replace $\left(\overleftarrow{x},\overrightarrow{x}\right)$ by x and use the dynamic fuzzy number $\left(\overleftarrow{\alpha },\overrightarrow{\alpha }\right)$ to represent c(x), that is, $c\left(\overleftarrow{x},\overrightarrow{x}\right)=\left(\overleftarrow{\alpha },\overrightarrow{\alpha }\right)\in$

(3)Every hypothesis h in the hypothesis space H is represented by the dynamic fuzzy Boolean quantity $\left(\overleftarrow{\alpha },\overrightarrow{\alpha }\right)$ because h ∈ H represents the function on X: h:X → $\left[0,1\right]\times \left[\leftarrow ,\to \right].\text{Now,}h\left(\overleftarrow{x},\overrightarrow{x}\right)=\left(\overleftarrow{\alpha },\overrightarrow{\alpha }\right)\in \left[\stackrel{\leftharpoondown }{0},\stackrel{\rightharpoondown }{0}\right]\times \left[\overleftarrow{1},\overrightarrow{1}\right].$

(4)The sample set U contains samples whose dynamic fuzziness is represented by its attribute values. Thus, replace U with the dynamic fuzzy set $\left(\overleftarrow{U},\overrightarrow{U}\right)$ representing the range of the sample set in the dynamic fuzzy space.

Use the above knowledge to represent sample D9 in Tab. 6.6 as given in Tab. 6.7.

After representing the sample with a dynamic fuzzy set and DFL, the decision tree constructed by the samples has also changed. After dynamic fuzzification, Fig. 6.4 becomes Fig. 6.5.

The tree produced by the samples based on DFS and DFL is called a dynamic fuzzy tree (DFT).

Definition 6.12 Assume $h_i=<\left({\overleftarrow{\alpha }}_1,{\overrightarrow{\alpha }}_2\right),\left({\overrightarrow{\alpha }}_2,{\overrightarrow{\alpha }}_2\right),\mathrm{...},\left({\overrightarrow{\alpha }}_m,{\overrightarrow{\alpha }}_m\right)>,h_i=<\left({\overleftarrow{\beta }}_1,{\overrightarrow{\beta }}_1\right),$$\left({\overleftarrow{\beta }}_2,{\overrightarrow{\beta }}_2\right),\mathrm{...},\left({\overleftarrow{\beta }}_m,{\overrightarrow{\beta }}_m\right)>,$ and hi, hj are functions defined in $\left(\overleftarrow{X},\overrightarrow{X}\right)$ hi is equal to or more general than hj if and only if

$\forall \left(\overleftarrow{x},\overrightarrow{x}\right)\in \left(\overleftarrow{X},\overrightarrow{X}\right),\left[\left(h_i\right)\left(\overleftarrow{x},\overrightarrow{x}\right)=\left(\overleftarrow{\alpha },\overrightarrow{\alpha }\right))\to \left(h_j\left(\overleftarrow{x},\overrightarrow{x}\right)=\left(\overleftarrow{\beta },\overrightarrow{\beta }\right))\right)\right]\le \left(\overleftarrow{\beta },\overrightarrow{\beta }\right).$

We write this as hi ≥ hj. Here, $\left(\overleftarrow{x},\overrightarrow{x}\right)$ represents a sample. We write hi ≥g hj when hi is strictly more general than hj.

The relationship ≥g represents a kind of partial ordering relation on the sample $\left(\overleftarrow{U},\overrightarrow{U}\right)$ (the relation is reflexive, anti-symmetric, and transitive). This provides an effective structure for learning problems. For the relationship ≥g, a more general explanation for hi contains fewer instances of constraints, any of which may be divided into a class of the samples placed into the same category by hj. This is because hj contains more constraints than hi, so hi is more general than hj.

In Fig. 6.5, the attributes “Weather = good”, “Rushhour = true”, and “Trafficjam = true” divide the training samples. The left side of the tree structure consists of samples in each node of the decision tree, where the relation between the upper set and lower set is ≥g. For example, {D3, D5, D10, D11} ≥g {D3, D5}, {D3, D5, D10, D11} ≥g {D10, D11}. Therefore, the set consists of samples in the decision tree divided by a partial order relation. The right side is the result of dividing each layer of the sample set. From the division of each layer, the classification attribute progressively divides the sample set.

Tab. 6.7: D9 knowledge representation after dynamic fuzzification.

3. Dynamic fuzzy tree HRL algorithm

In dynamic fuzzy tree HRL, let $\left({\overleftarrow{a}}_i,{\overrightarrow{a}}_i\right)$ represent an attribute with value range $(\overleftarrow{V_{{\overleftarrow{a}}_i}},\overrightarrow{V_{{\overleftarrow{a}}_i}})=\left\{\left(\overleftarrow{V_1},\overrightarrow{V_1}\right),\left(\overleftarrow{V_2},\overrightarrow{V_2}\right),\mathrm{...},\left({\overleftarrow{v}}_k,{\overrightarrow{v}}_k\right)\right\}.\text{Then,}\left|\overleftarrow{V_{{\overleftarrow{a}}_i}},\overrightarrow{V_{{\overrightarrow{a}}_i}}\right|=k$ represents the number of attribute values of $\left({\overleftarrow{a}}_i,{\overrightarrow{a}}_i\right).$ A sample can be represented by

$\left(\overleftarrow{I_i},{\overrightarrow{I}}_i\right)=<\left(v\overleftarrow{\frac{1}{a_1}},v\overrightarrow{\frac{1}{a_1}}\right)\left(v\overleftarrow{\frac{2}{a_1}},v\overrightarrow{\frac{2}{a_1}}\right),\cdots ,\left(v\overleftarrow{\frac{m}{a_m}},v\overrightarrow{\frac{m}{a_m}}\right)>,$

where $\left(\overleftarrow{v_{{\overleftarrow{a}}_i}^i},\overrightarrow{v_{{\overleftarrow{a}}_i}^i}\right)$ represents the i th attribute of $\left({\overleftarrow{a}}_i,{\overrightarrow{a}}_i\right)$ and the sample set can be represented as $\left(\overleftarrow{U},\overrightarrow{U}\right)=\left\{{\overleftarrow{I}}_i,{\overrightarrow{I}}_i|i=1,2,\mathrm{...},n\right\}.$

Above all, the set consists of the value $\left(\overleftarrow{t},\overrightarrow{t}\right)$ of attribute $\left({\overleftarrow{a}}_i,{\overrightarrow{a}}_i\right)$ in sample set $\left(\overleftarrow{U},\overrightarrow{U}\right),$ which can be represented by

$\begin{array}{l}Pa{r}_{\left({\overleftarrow{a}}_1,{\overrightarrow{a}}_2\right)}^{\left(\overleftarrow{t},\overrightarrow{t}\right)}\left(\overleftarrow{U,}\overrightarrow{U}\right)=\left\{\overleftarrow{S},\overrightarrow{S}|\left(\overleftarrow{S},\overrightarrow{S}\right)\subseteq \left(\overleftarrow{U},\overrightarrow{U}\right),\left({\overleftarrow{I}}_j,{\overrightarrow{I}}_j\right)\in \left(\overleftarrow{S},\overrightarrow{S}\right),\left(\overleftarrow{V_{\overleftarrow{a_1}}}\overrightarrow{V_{\overrightarrow{a_1}}}\right)\left(\overleftarrow{I_j},\overrightarrow{I_j}\right)\right\}\\ =\left(\overleftarrow{t},\overrightarrow{t}\right)\},\end{array}$

where $\left(\overleftarrow{t},\overrightarrow{t}\right)=\left(\overleftarrow{v_{{\overleftarrow{a}}_i}^k},\overrightarrow{v_{{\overleftarrow{a}}_i}^k}\right)$ represents the k th attribute value of attribute and $k\le \left|\left(\overleftarrow{V_{{\overleftarrow{a}}_i}},\overrightarrow{V_{{\overleftarrow{a}}_i}}\right)\right|.$

According to the difference among the values of attribute $\left({\overleftarrow{a}}_i,{\overrightarrow{a}}_i\right).$ we obtain the division of $\left(\overleftarrow{U},\overrightarrow{U}\right),$ written as

$Di{v}_{\left(\overleftarrow{a_i},\overrightarrow{a_j}\right)}\left(\overleftarrow{U},\overrightarrow{U}\right)=\left\{\left(\overleftarrow{S_1},\overrightarrow{S_2}\right),\left(\overleftarrow{S_2},\overrightarrow{S_2}\right),\dots ,\left(\overleftarrow{S_n},\overrightarrow{S_n}\right)|\left(\overleftarrow{S_i},\overrightarrow{S_i}\right)=Par\frac{\overleftarrow{(t}}{a_1}\cdot \overrightarrow{\frac{t}{a_1}}\left(\overleftarrow{U},\overrightarrow{U}\right)\right\},$

where $n\le \left|\overleftarrow{V_{{\overleftarrow{a}}_i}},\overrightarrow{V_{{\overleftarrow{a}}_i}}\right|.$

We write the condition attribute as $\left(\overleftarrow{A},\overrightarrow{A}\right)=\left\{\left(\overleftarrow{A_1},\overrightarrow{A_1}\right),\left(\overleftarrow{A_2},\overrightarrow{A_2}\right),\mathrm{...},\left(\overleftarrow{A_m},\overrightarrow{A_m}\right)\right\},$ and the decision attribute is $\left(\overleftarrow{A_d},\overrightarrow{A_d}\right).$ Because $\left(\overleftarrow{A_d},\overrightarrow{A_d}\right)$ relies on condition attribute $\left({\overleftarrow{A}}_i,{\overrightarrow{A}}_i\right),$ there is a relationship between the condition attribute and decision attribute that satisfies one of the following three relationships. For the division $pa{r}_{\left({\overleftarrow{A}}_d,{\overrightarrow{A}}_d\right)}^{\left({\overleftarrow{V}}_j,{\overrightarrow{V}}_j\right)}\left(\overleftarrow{U},\overrightarrow{U}\right)$ given by dividing the sample set $\left(\overleftarrow{U},\overrightarrow{U}\right)$ by the j th value of the decision attribute $\left({\overleftarrow{A}}_d,{\overrightarrow{A}}_d\right),\exists \left({\overleftarrow{A}}_i,{\overrightarrow{A}}_i\right)$ such that one of $Pa{r}_{\left({\overleftarrow{A}}_i,{\overrightarrow{A}}_i\right)}^{\left({\overrightarrow{V}}_k,{\overrightarrow{V}}_k\right)}\left(\overleftarrow{U},\overrightarrow{U}\right)\underset{\_}{\subset }Pa{r}_{\left({\overleftarrow{A}}_d,{\overrightarrow{A}}_d\right)}^{\left({\overrightarrow{V}}_j,{\overrightarrow{V}}_j\right)}\left(\overleftarrow{U},\overrightarrow{U}\right),$$Pa{r}_{\left({\overleftarrow{A}}_i,{\overrightarrow{A}}_i\right)}^{\left({\overrightarrow{V}}_k,{\overrightarrow{V}}_k\right)}\left(\overleftarrow{U},\overrightarrow{U}\right)=Pa{r}_{\left({\overleftarrow{A}}_d,{\overrightarrow{A}}_d\right)}^{\left({\overrightarrow{V}}_j,{\overrightarrow{V}}_j\right)}\left(\overleftarrow{U},\overrightarrow{U}\right),\text{or}Pa{r}_{\left({\overleftarrow{A}}_i,{\overrightarrow{A}}_i\right)}^{\left({\overrightarrow{V}}_k,{\overrightarrow{V}}_k\right)}\left(\overleftarrow{U},\overrightarrow{U}\right)\supseteq Pa{r}_{\left({\overleftarrow{A}}_d,{\overrightarrow{A}}_d\right)}^{\left({\overrightarrow{V}}_j,{\overrightarrow{V}}_j\right)}\left(\overleftarrow{U},\overrightarrow{U}\right)$ holds. Considering that “Include” and “Included” are reciprocal computations, and “=” can be viewed as a special situation of “Include”, we take the first case as an example. $Pa{r}_{\left({\overleftarrow{A}}_i,{\overrightarrow{A}}_i\right)}^{\left({\overrightarrow{V}}_k,{\overrightarrow{V}}_k\right)}\left(\overleftarrow{U},\overrightarrow{U}\right)\underset{\_}{\subset }Pa{r}_{\left({\overleftarrow{A}}_d,{\overrightarrow{A}}_d\right)}^{\left({\overrightarrow{V}}_j,{\overrightarrow{V}}_j\right)}\left(\overleftarrow{U},\overrightarrow{U}\right)$ represents the case when the value of the decision attribute $\left({\overleftarrow{A}}_d,{\overrightarrow{A}}_d\right)\text{is}\left({\overleftarrow{V}}_j,{\overrightarrow{V}}_j\right),$ and the sample set contains the set consisting of condition attribute $\left({\overleftarrow{A}}_i,{\overrightarrow{A}}_i\right)$ whose value is $\left({\overrightarrow{V}}_k,{\overrightarrow{V}}_k\right);$; that is, when the value of the decision attribute $\left({\overleftarrow{A}}_i,{\overrightarrow{A}}_i\right)\text{is}\left(\overleftarrow{v_j},\overrightarrow{v_j}\right),$ the determined sample division is class $\left({\text{<mover accent="true"> V <mo>→</mo> </mover>}}_{\text{i}},{\text{<mover accent="true"> V <mo>→</mo> </mover>}}_{\text{i}}.\right)$ Because $Pa{r}_{\left({\overleftarrow{A}}_i,{\overrightarrow{A}}_i\right)}^{\left({\overrightarrow{V}}_k,{\overrightarrow{V}}_k\right)}\left(\overleftarrow{U},\overrightarrow{U}\right)\underset{\_}{\subset }Pa{r}_{\left({\overleftarrow{A}}_d,{\overrightarrow{A}}_d\right)}^{\left({\overrightarrow{V}}_j,{\overrightarrow{V}}_j\right)}\left(\overleftarrow{U},\overrightarrow{U}\right),$ it is known that the other attribute values of condition attribute $\left({\overleftarrow{A}}_i,{\overrightarrow{A}}_i\right)$ except $({\overleftarrow{v}}_k,{\overrightarrow{v}}_k)$ can divide the sample into class $({\overleftarrow{v}}_j,{\overrightarrow{v}}_j).$