where ${\text{pro}}_k=\left|\text{Par}\begin{array}{c}\left({\overleftarrow{v}}_k,{\overrightarrow{v}}_k\right)\\ \left({\overleftarrow{A}}_D,{\overrightarrow{A}}_D\right)\end{array}\left(\overleftarrow{U},\overrightarrow{U}\right)\right|/\left|\left(\overleftarrow{U},\overrightarrow{U}\right)\right|$ denotes the ratio of the number of instances belonging to class $\left({\overleftarrow{v}}_k,{\overrightarrow{v}}_k\right)$ in instance set $\left(\overleftarrow{U},\overrightarrow{U}\right)$ to the total set of instances.

We set $T_{\left({\overleftarrow{A}}_i,{\overrightarrow{A}}_i\right)}\left(\overleftarrow{U},\overrightarrow{U}\right)=1-{\text{Cer}}_{\left({\overleftarrow{A}}_i,{\overrightarrow{A}}_i\right)}\left(\overleftarrow{U},\overrightarrow{U}\right)=1-{\displaystyle {\sum }_{k=1}^n{\text{pro}}_k{\text{Cer}}_{\left({\overleftarrow{A}}_i,{\overrightarrow{A}}_i\right)}^k\left(\overleftarrow{U},\overrightarrow{U}\right)}$ as the attribute selection criteria in the decision tree classification. The range of $T_{\left({\overleftarrow{A}}_i,{\overrightarrow{A}}_i\right)}\left(\overleftarrow{U},\overrightarrow{U}\right)$

If $T_{\left({\overleftarrow{A}}_i,{\overrightarrow{A}}_i\right)}\left(\overleftarrow{U},\overrightarrow{U}\right)=0,$ the conditional attribute $\left({\overleftarrow{A}}_i,{\overrightarrow{A}}_i\right)$ has a degree of certainty of 1 for the entire set of instances, indicating that the conditional attribute $\left({\overleftarrow{A}}_i,{\overrightarrow{A}}_i\right)$ can definitely divide the instance set. If ${\Gamma }_{\left({\overleftarrow{A}}_i,{\overrightarrow{A}}_i\right)}\left(\overleftarrow{U},\overrightarrow{U}\right)=1,$ we have a maximum indefinite partition of the instance set in conditional attribute $\left({\overleftarrow{A}}_i,{\overrightarrow{A}}_i\right).$ Therefore, the smaller the value of ${\Gamma }_{\left({\overleftarrow{A}}_i,\overrightarrow{A}\right)}\left(\overleftarrow{U},\overrightarrow{U}\right),$ the better the attributes divide the instance set. In the attribute selection algorithm, the condition attribute $\left({\overleftarrow{A}}_i,{\overrightarrow{A}}_i\right),$ which enables ${\Gamma }_{\left({\overleftarrow{A}}_i,{\overrightarrow{A}}_i\right)}\left(\overleftarrow{U},\overrightarrow{U}\right)$ to obtain the minimum value, is selected as the branch attribute.

1. Basic idea and description of the algorithm

In the process of constructing the decision tree, branch attribute $\left({\overleftarrow{A}}_i,{\overrightarrow{A}}_i\right)$ should be able to cover as many instances as possible, reducing the number of instances to be classified. This effectively reduces the whole branch of the tree and achieves the purpose of simplification. The attributes of min $\left({\Gamma }_{\left({\overleftarrow{A}}_i,{\overrightarrow{A}}_i\right)}\left(\overleftarrow{U},\overrightarrow{U}\right)\right)$ satisfy the above conditions, and the contribution of each partition to the entire set of decision instances is considered more comprehensively by using prok. We select the best attribute from the available set of attributes to create the branch, and the attributes that have been used to branch can no longer be selected.

The basic description of the algorithm is as follows:

(1)For each condition attribute, calculate ${\text{Div}}_{\left({\overleftarrow{A}}_i,{\overrightarrow{A}}_i\right)}\left(\overleftarrow{U},\overrightarrow{U}\right),{\text{Div}}_{\left({\overleftarrow{A}}_i,{\overrightarrow{A}}_i\right)}\left(\overleftarrow{U},\overrightarrow{U}\right)=$$\{{\displaystyle {\cup }_{k=1}^{\left|{\overleftarrow{V}}_{{\overleftarrow{A}}_i},{\overrightarrow{V}}_{{\overleftarrow{A}}_i}\right|}\text{Par}\begin{array}{c}\left({\overleftarrow{v}}_k,{\overrightarrow{v}}_k\right)\\ \left({\overleftarrow{A}}_i,{\overrightarrow{A}}_i\right)\end{array}\left(\overleftarrow{U},\overrightarrow{U}\right)};$

(2)Compute the degree of certainty ${\text{Cer}}_{\left({\overleftarrow{A}}_i,{\overrightarrow{A}}_i\right)}^j\left(\overleftarrow{U},\overrightarrow{U}\right)$ of condition attribute $\left({\overleftarrow{A}}_i,{\overrightarrow{A}}_i\right)$ classifying the instance into class $\left({\overleftarrow{v}}_j,{\overrightarrow{v}}_j\right),$ and the ratio of the number of instances with decision attribute $\left({\overleftarrow{v}}_j,{\overrightarrow{v}}_j\right)$ to the total number of instances;

(3)Compute ${\Gamma }_{\left({\overleftarrow{A}}_i,{\overrightarrow{A}}_i\right)}\left(\overleftarrow{U},\overrightarrow{U}\right),$ select the attribute that satisfies min $\left({\Gamma }_{\left({\overleftarrow{A}}_i,{\overrightarrow{A}}_i\right)}\left(\overleftarrow{U},\overrightarrow{U}\right)\right)$ the branch attribute, then divide the instance set as $\{\text{Par}\begin{array}{c}\left({\overleftarrow{v}}_1,{\overrightarrow{v}}_1\right)\\ \left({\overleftarrow{A}}_i,{\overrightarrow{A}}_i\right)\end{array}\left(\overleftarrow{U},\overrightarrow{U}\right),\text{Par}\begin{array}{c}\left({\overleftarrow{v}}_2,{\overrightarrow{v}}_2\right)\\ \left({\overleftarrow{A}}_i,{\overrightarrow{A}}_i\right)\end{array}$$\left(\overleftarrow{U},\overrightarrow{U}\right),\dots ,\text{Par}\begin{array}{c}\left({\overleftarrow{v}}_k,{\overrightarrow{v}}_k\right)\\ \left({\overleftarrow{A}}_i,{\overrightarrow{A}}_i\right)\end{array}\left(\overleftarrow{U},\overrightarrow{U}\right)\};$

(4)Determine whether the instances contained in $\text{Par}\begin{array}{c}\left(\overleftarrow{t},\overrightarrow{t}\right)\\ \left({\overleftarrow{A}}_t,{\overrightarrow{A}}_t\right)\end{array}\left(\overleftarrow{U},\overrightarrow{U}\right)$ belong to the same category. If so, the corresponding node is a leaf node; otherwise, return to (1) and repeat the first three steps. The attributes that have been used to branch are no longer selected.

The pseudocode is described in Algorithm 3.1.

2. Algorithm application examples

We use the data in [29] (see Tab. 3.3) to illustrate the flow of the proposed classification attribute selection algorithm. First, the data of the source data table are expressed by dynamic fuzzy mathematics theory. The DFDT is then generated by classifying the training set according to the steps of the algorithm.

The data in Tab. 3.4 are classified according to the algorithm described in Section 3.2.4.1. For convenience, $\left(\overleftarrow{a},\overrightarrow{a}\right)$ replaces Outlook = Sunny, $\left(\overleftarrow{b},\overrightarrow{b}\right)$ replaces Temperature = Hot, $\left(\overleftarrow{c},\overrightarrow{c}\right)$ replaces Humidity = High, $\left(\overleftarrow{d},\overrightarrow{d}\right)$ replaces Wind = Strong, $\left(\overleftarrow{e},\overrightarrow{e}\right)$ replaces PlayTennis = Yes, and $\left(\overleftarrow{U},\overrightarrow{U}\right)$ denotes the instance set in Tab. 3.4. We substitute instances with the numbers in the instance set to simplify the representation (same below). That is, $\left(\overleftarrow{U},\overrightarrow{U}\right)=\left\{D1,D2,\dots ,D14\right\}.$ The process is as follows.

First, the attribute set $\left(\overleftarrow{U},\overrightarrow{U}\right)$ is divided:

$\begin{array}{l}{\text{Div}}_{(\overleftarrow{a}.\overrightarrow{a})}(\overleftarrow{U},\overrightarrow{U})=\left\{\{1,2,8,9,11\},\{3,7,12,13\},\{4,5,6,10,14\}\right\}\\ {\text{Div}}_{(\overleftarrow{b}.\overrightarrow{b})}(\overleftarrow{U},\overrightarrow{U})=\left\{\{1,2,3,13\},\{4,8,10,11,12,14\},\{5,6,7,9\}\right\}\\ {\text{Div}}_{(\overleftarrow{c}.\overrightarrow{c})}(\overleftarrow{U},\overrightarrow{U})=\left\{\{1,2,3,4,8,12,14\},\{5,6,7,9,10,11,13\}\right\}\\ {\text{Div}}_{(\overleftarrow{d}.\overrightarrow{d})}(\overleftarrow{U},\overrightarrow{U})=\left\{\{2,6,7,11,12,14\},\{1,3,4,5,8,9,10,13\}\right\}\\ {\text{Div}}_{(\overleftarrow{a}.\overrightarrow{a})}(\overleftarrow{U},\overrightarrow{U})=\left\{\{3,4,5,7,9,10,11,12,13\},\{1,2,6,8,14\}\right\}\end{array}$

Tab. 3.3: Training instance set of PlayTennis.

Tab. 3.4: The training instance set PlayTennis after dynamic fuzzification.

The degree of certainty of the classification of each attribute on $\left(\overleftarrow{U},\overrightarrow{U}\right)$ is then calculated:

$\begin{array}{l}{\Gamma }_{(\overleftarrow{a}.\overrightarrow{a})}(\overleftarrow{U},\overrightarrow{U})=1-{\displaystyle \sum _{k=1}^2{\text{pro}}_k{\text{Cer}}_{(\overleftarrow{a}.\overrightarrow{a})}^j(\overleftarrow{U},\overrightarrow{U}})\\ =1-\left(\frac{4}{14}\times \frac{9}{14}+0\right)=\mathrm{0.8163.}\end{array}$

Similarly, ${\Gamma }_{\left(\overleftarrow{b},\overrightarrow{b}\right)}\left(\overleftarrow{U},\overrightarrow{U}\right)=1,{\Gamma }_{\left(\overleftarrow{c},\overrightarrow{c}\right)}\left(\overleftarrow{U},\overrightarrow{U}\right)=1.$

We select attribute $\left(\overleftarrow{a},\overrightarrow{a}\right)$ as the first branch point, that is, the root node.

As the instances in $\text{Par}\begin{array}{c}\overrightarrow{0.4}\\ \left(\overleftarrow{a},\overrightarrow{b}\right)\end{array}\left(\overleftarrow{U},\overrightarrow{U}\right)=\left\{3,7,12,13\right\}$ belong to the same class, the branch is ended. Look at the other classes.

$\begin{array}{rl}& \text{When}\text{(}\stackrel{\leftarrow <!--\; ?\; -->}{a},\stackrel{\to <!--\; ?\; -->}{a})=\stackrel{\to <!--\; ?\; -->}{0.7},\\ & \text{Di}{\text{v}}_{(\stackrel{\leftarrow <!--\; ?\; -->}{b}.\stackrel{\to <!--\; ?\; -->}{b})}({\text{Par}}_{\text{(}\stackrel{\leftarrow <!--\; ?\; -->}{a}.\stackrel{\to <!--\; ?\; -->}{a})}^{\stackrel{\to <!--\; ?\; -->}{0.7}}(\stackrel{\leftarrow <!--\; ?\; -->}{U},\stackrel{\to <!--\; ?\; -->}{U}))=\left\{\{1,2\},\{8,11\},\{9\}\right\}\\ & \text{Di}{\text{v}}_{(\stackrel{\leftarrow <!--\; ?\; -->}{c}.\stackrel{\to <!--\; ?\; -->}{c})}({\text{Par}}_{\text{(}\stackrel{\leftarrow <!--\; ?\; -->}{a}.\stackrel{\to <!--\; ?\; -->}{a})}^{\stackrel{\to <!--\; ?\; -->}{0.7}}(\stackrel{\leftarrow <!--\; ?\; -->}{U},\stackrel{\to <!--\; ?\; -->}{U}))=\left\{\{1,2,8\},\{9,11\}\right\}\\ & \text{Di}{\text{v}}_{(\stackrel{\leftarrow <!--\; ?\; -->}{d}.\stackrel{\to <!--\; ?\; -->}{d})}({\text{Par}}_{\text{(}\stackrel{\leftarrow <!--\; ?\; -->}{a}.\stackrel{\to <!--\; ?\; -->}{a})}^{\stackrel{\to <!--\; ?\; -->}{0.7}}(\stackrel{\leftarrow <!--\; ?\; -->}{U},\stackrel{\to <!--\; ?\; -->}{U}))=\left\{\{1,8,9\},\{2,11\}\right\}\\ & \text{Di}{\text{v}}_{(\stackrel{\leftarrow <!--\; ?\; -->}{e}.\stackrel{\to <!--\; ?\; -->}{e})}({\text{Par}}_{\text{(}\stackrel{\leftarrow <!--\; ?\; -->}{a}.\stackrel{\to <!--\; ?\; -->}{a})}^{\stackrel{\to <!--\; ?\; -->}{0.7}}(\stackrel{\leftarrow <!--\; ?\; -->}{U},\stackrel{\to <!--\; ?\; -->}{U}))=\left\{\{1,2,8\},\{9,11\}\right\}\\ & {\mathrm{\Gamma <!--\; G\; -->}}_{(\stackrel{\leftarrow <!--\; ?\; -->}{b}.\stackrel{\to <!--\; ?\; -->}{b})}({\text{Par}}_{\text{(}\stackrel{\leftarrow <!--\; ?\; -->}{a}.\stackrel{\to <!--\; ?\; -->}{a})}^{\stackrel{\to <!--\; ?\; -->}{0.7}}(\stackrel{\leftarrow <!--\; ?\; -->}{U},\stackrel{\to <!--\; ?\; -->}{U}))=0.5,\\ & {\mathrm{\Gamma <!--\; G\; -->}}_{(\stackrel{\leftarrow <!--\; ?\; -->}{c}.\stackrel{\to <!--\; ?\; -->}{c})}({\text{Par}}_{\text{(}\stackrel{\leftarrow <!--\; ?\; -->}{a}.\stackrel{\to <!--\; ?\; -->}{a})}^{\stackrel{\to <!--\; ?\; -->}{0.7}}(\stackrel{\leftarrow <!--\; ?\; -->}{U},\stackrel{\to <!--\; ?\; -->}{U}))=0,{\mathrm{\Gamma <!--\; G\; -->}}_{(\stackrel{\leftarrow <!--\; ?\; -->}{d}.\stackrel{\to <!--\; ?\; -->}{d})}({\text{Par}}_{\text{(}\stackrel{\leftarrow <!--\; ?\; -->}{a}.\stackrel{\to <!--\; ?\; -->}{a})}^{\stackrel{\to <!--\; ?\; -->}{0.7}}(\stackrel{\leftarrow <!--\; ?\; -->}{U},\stackrel{\to <!--\; ?\; -->}{U})=1.\end{array}$

Therefore, when $\left(\overleftarrow{a},\overrightarrow{a}\right)=\overrightarrow{0.7},$ the branch attribute is $\left(\overleftarrow{c},\overrightarrow{c}\right)$ and the instances in $\text{Par}\begin{array}{c}\overline{0.4}\\ \left(\overleftarrow{c},\overrightarrow{c}\right)\end{array}\left(\text{Par}\begin{array}{c}\overline{0.7}\\ \left(\overleftarrow{c},\overrightarrow{c}\right)\end{array}\text{Par}\begin{array}{c}0.6\\ \left(\overleftarrow{c},\overrightarrow{c}\right)\end{array}\left(\text{Par}\begin{array}{c}\overline{0.7}\\ \left(\overline{a},\overline{a}\right)\end{array}\right)\right)$ are in the same class. Thus, the branch is ended.

Similarly, when $\left(\overleftarrow{a},\overrightarrow{b}\right)=\overleftarrow{0.2},{\Gamma }_{\left(\overleftarrow{b},\overleftarrow{a}\right)}(\text{Par}\begin{array}{c}\overleftarrow{0.2}\\ \left(\overleftarrow{a},\overrightarrow{a}\right)\end{array}\left(\overleftarrow{U},\overrightarrow{U}\right)=1,{\Gamma }_{\left(\overleftarrow{c},\overrightarrow{c}\right)}\left(\text{Par}\begin{array}{c}0.2\\ \left(\overleftarrow{a},\overrightarrow{b}\right)\end{array}\left(\overleftarrow{U},\overrightarrow{U}\right)\right))=$$1,{\Gamma }_{\left(\overleftarrow{d},\overrightarrow{d}\right)}\left(\text{Par}\begin{array}{c}\overleftarrow{0.2}\\ \left(\overleftarrow{a},\overrightarrow{d}\right)\end{array}\left(\overleftarrow{U},\overrightarrow{U}\right)\right)=0.$

Hence, when $\left(\overleftarrow{a},\overrightarrow{a}\right)=\overleftarrow{0.2},$ the branch attribute is $\left(\overleftarrow{d},\overrightarrow{d}\right)$ and the instances in $\text{Par}\begin{array}{c}\stackrel{\rightharpoonup }{0.8}\\ \left(\overleftarrow{d},\overrightarrow{d}\right)\end{array}\left(\text{Par}\begin{array}{c}\overleftarrow{0.2}\\ \left(\overleftarrow{a},\overrightarrow{d}\right)\end{array}\left(\overleftarrow{U},\overrightarrow{U}\right)\right),\text{Par}\begin{array}{c}\overleftarrow{0.1}\\ \left(\overleftarrow{d},\overrightarrow{d}\right)\end{array}\left(\text{Par}\begin{array}{c}\overleftarrow{0.2}\\ \left(\overleftarrow{a},\overrightarrow{a}\right)\end{array}\left(\overleftarrow{U},\overrightarrow{U}\right)\right)$ are in the same class. Again, the branch is ended.

After constructing the decision tree above, we can see that all leaf nodes corresponding to the instance set belong to the same class. This completes the tree structure. The whole instance set is classified and the constructed decision tree is shown in Fig. 3.4.

3.2.5Dynamic fuzzy binary decision tree

A test attribute with multiple attribute values may have two or more branches per internal node. A DFDT with only two branches per internal node is called a Dynamic Fuzzy Binary Decision Tree (DFBDT). There are a number of algorithms that can create binary decision trees. For example, the CRAT algorithm uses entropy to select the best splitting attributes and criteria and produces only two child nodes where each subclass has children [30]. Sun and Zhang [31] described a binary decision tree generation algorithm based on attribute-value information gain optimization and a method of transforming multi-valued attributes into binary attributes.

DFBDT is a special form of DFDT and has a slightly different tree structure. By introducing, the relationship between the corresponding subset of the nodes of the decision tree can be analysed. At the same time, each layer of the decision tree corresponding to the instance set is divided according to a certain relationship. DFBDT is illustrated in Fig. 3.5.

In DFDT, there is a partial ordering relationship between the instance set of upper-level nodes and the directly lower nodes. In DFBDT, the instance set contained in Attribute B = VB and its two sub-nodes is {{1, 4, 5, 6, 7, 8, 9, 10, 11}, {1, 4, 6, 8, 9, 10}, {5,7, 11}}. The elements not only meet the partial order relationship, but also the union of {1, 4, 6, 8, 9, 10} and {5, 7, 11} also equals {1, 4, 5, 6, 7, 8, 9, 10, 11}. This obeys the definition of a semi-lattice. As with DFDT, the branch attribute also divides the entire set of instances. To study the partition of the object domain, a partition lattice has been proposed [32] and was introduced to a decision tree to study the partitioning of the instance set.

A DFDT can be denoted as

$(\overleftarrow{T},\overrightarrow{T})=\langle (\overleftarrow{U},\overrightarrow{U}),(\overleftarrow{C},\overrightarrow{C}),(\overleftarrow{D},\overrightarrow{D}),(\overleftarrow{V},\overrightarrow{V}),(\overleftarrow{F},\overrightarrow{F})\rangle ,$

where $\left(\overleftarrow{U},\overrightarrow{U}\right)$ denotes the instance set, $\left(\overleftarrow{C},\overrightarrow{C}\right)\cup \left(\overleftarrow{D},\overrightarrow{D}\right)=\left(\overleftarrow{A},\overrightarrow{A}\right)$ is the attribute set, subsets $\left(\overleftarrow{C},\overrightarrow{C}\right)\text{and}\left(\overleftarrow{D},\overrightarrow{D}\right)$ are the condition attribute and decision attribute, respec tively, and $\left(\overleftarrow{V},\overrightarrow{V}\right)=\cup \left({\overleftarrow{V}}_{\overleftarrow{r}},{\overrightarrow{V}}_{\overrightarrow{r}}\right)$ denotes the range of attribute.

$\left(\overleftarrow{A},\overrightarrow{A}\right).\left(\overleftarrow{F},\overrightarrow{F}\right):\left(\overleftarrow{U},\overrightarrow{U}\right)\times \left(\overleftarrow{A},\overrightarrow{A}\right)\to \left(\overleftarrow{V},\overrightarrow{V}\right)$ is a mapping that specifies the attribute values for each object in instance set $\left(\overleftarrow{U,}\overrightarrow{U}\right),\text{and}\left(\overleftarrow{F,}\overrightarrow{F}\right)\subseteq \left[0,1\right]\times \left[\leftarrow ,\to \right].$

Definition 3.2 Given a finite universe U, π = {Xi|1 ≤ i ≤ m} is a division of U if π satisfies the following conditions [33]:

Xi is not empty;

Xi⋂, i ⋂ j;

We can define a partial order relationship to represent the size between partitions. Suppose π1, π2 are two divisions of U. If π1 ≤ π2, any partition of π1 is contained in a certain partition of π2. That is, π1 ≤ π2 if and only if, π1≤ π2 such that Xi ∈ π1 π1 Xj