Decision trees are widely used in the field of machine learning and artificial intelligence. Such popularity is due to the fact that with the help of decision trees graphic models, text rules can be built and they are easily understood by the final user. Because of the inaccuracy of observations, uncertainties, the data, collected in the environment, often take an unclear form. Therefore, fuzzy decision trees are becoming popular in the field of machine learning. This article presents a method that includes the features of the two above-mentioned approaches: a graphical representation of the rules system in the form of a tree and a fuzzy representation of the data. The approach uses such advantages as high comprehensibility of decision trees and the ability to cope with inaccurate and uncertain information in fuzzy representation. The received learning method is suitable for classifying problems with both numerical and symbolic features. In the article, solution illustrations and numerical results are given.Also the comparison of fuzzy logic approaches for building fuzzy rules and classification trees are given.
Nowadays, in the era of big data, the extraction of knowledge is a bottleneck in the field of knowledge
engineering. Computer programs that extract knowledge from data successfully try to solve this
problem.Among these programs, systems for building decision trees for decision-making and
classification tasks are very popular. The knowledge acquired in the form of decision trees and
inference procedures is highly valued for the clarity and visibility of the data. Such assessment, at one
time, aroused interest of scientists, which led to a number of methodological and empirical
achievements. However, initially decision trees were popularized by Quinlan and his ID3 algorithm
[
One of the extensions of the classical construction of decision trees is an approach based on fuzzy logic. Fuzzy approach is becoming increasingly popular in solving problems of uncertainty, noise and inaccurate data. It is successfully applied to problems in many industrial spheres. Most studies on the application of this representative framework to existing methodologies are focused mainly on new areas, such as neural networks and genetic algorithms. Nowadays, the fuzzy approach that integrates the concepts of fuzzy sets and entropy is becoming popular.
This article presents a method that includes the features of the two above-mentioned approaches: a graphical representation of the rules system in the form of a tree and the fuzzy representation of the data. Section 2 describes the principle of the decision trees, their advantages and disadvantages, algorithms for their construction. Section 3 shows the principle of constructing fuzzy decision trees, introduces the concepts of fuzzy logic. Section 4 describes the results of the study and the last section gives a conclusion.
A decision tree (DT) is a common formalization for mapping the transitions of attribute values to
classes in the form of a map, which consists of attribute nodes or so-called tests that can have two or
more subtrees, leaves, or decision nodes that are labeled with a class indicating the solution. The main
advantage of this approach is the visualization of the solution. One of the most commonly used
algorithms for constructing decision trees is the ID3 method, formalized by Quinlan in 1986 [
Decision trees create efficient models for machine learning [
In the process of tree constructing, the pattern is represented by a set of features that are expressed in some descriptive language. Samples whose characteristics are known are called examples. The purpose of constructing a tree is to solve the problem of classification or regression.
ID3 and CART are the two most important discriminating learning algorithms that work by recursive partitioning. Their basic ideas are approximately the same: splitting the incoming sample into subsets and representing the partitions as a tree. An important property of these algorithms is that they simultaneously try to minimize the size of the tree with the optimization of some quality measure. Subsequently, they use the same logical inference.
To construct a fuzzy decision tree, the following procedure is proposed [
The first block of Figure 1 illustrates a dataset with n examples, three attributes (At1, At2,At3) and a class attribute. The fuzzified version of this dataset is presented in the second block. This fuzzified set of examples is used to induce the final DT, illustrated in the last block of Figure 1.
The entropy and information gain formulas remain the same for the classical version of the ID3
algorithm [
– set of data samples; – set of attributes; – a singleton set with a solution attribute or class attribute. Let this attribute have m different values, thensi is the number of samples of set U in class di.
Information gain I relative to subset Sj is equal to: , , ; where – the number of samples in a subset of S.
Entropy E(ci) is: accordingly, the criterion for selecting an attribute is the increase in information: .
The difference between common algorithm ID3 and the fuzzy version of algorithm ID3 is that the attributes of objects have degrees of belonging to a particular node, and it is quite possible that an attribute with certain probabilities belongs to several nodes.
Figure 2 shows two decision trees that were built using the above-mentioned algorithms.
As an example, a classic data set was taken, Fisher's iris [
As a research object, just as in the previous example, a Fisher's iris data set was used.To construct a fuzzy decision tree at the first stage, it is necessary to perform a fuzzification procedure.
While performing the fuzzification procedure, the definition set of fuzzy attributes is divided into fuzzy subsets. The value of the fuzzy attribute is put in correspondence with the term, and this correspondence is found using the membership function. The division of the definition set into fuzzy subsets can be made evenly, that is, the definition set is divided into equal intervals. However, in most real data sets obtained from the environment, it is preferable to perform the partitioning taking into account the features of the original sample. For example, it may happen that most of the sampling objects lie in the first third of the definition set and, in this case, uniform partitioning will not give the desired effect.The results of fuzzification for attributes SepalLength, SepalWidth, PetalLength and PetalWidthare shown in Figures 3, 4, 5 and 6 respectively.
Numeric attributes have been assigned 3 terms (low, medium, high). Let us present the results of the classification obtained with the help of fuzzy decision trees. In the context of this studies, let us introduce the following notations:
Correct - the number of correctly classed sample objects.
Incorrect - the number of incorrectly classified sample objects.
WithoutClass - the number of objects without a class.
PercentCorrect is the percentage of correctly-categorized sample objects that is calculated as follows:
To study the hypothesis that with a decrease of the sample size, the accuracy of the classification of fuzzy decision trees is better than classifying with classical ones, the dependence of the classification accuracy on the number of instances in the data set was constructed.
In this study, the trees were constructed for 3 randomly selected N samples and the table shows the averaged values obtained (the sum of the values of the attributes / 3).
According to the data presented in Table 1, it can be seen that when the sample is reduced from 150 to 90, the accuracy of classification using fuzzy decision trees is three percent higher than results of classifying with classical decision trees, and when the sample is reduced to 60, the accuracy is higher by 0.82 percent.
The number of instances in the data set (N) Table 2 shows the dependence of the accuracy of data classification on the number of terms.
According to the data in the table, it is clear that the optimal number of terms for the test set of data is 5. Such quantity gave a higher percentage of correctly classified data compared to 3 terms.
As a part of fuzzy decision trees research, we compare two methods of classification based on
fuzzy logic. The first one is algorithm of direct generating fuzzy linguistic rules, proposed in [
Here we can observe that the classification accuracy for sequentially growing number of terms (from 3 cases to 7) remains quite high. Method of fuzzy decision trees is better for medium and high sizes of terms while the method of direct generating fuzzy rules is better for small size of training sample. Further research will be in development of algorithm based on combination of both approaches.
On fig. 8 we can observe that the classification accuracy for sequentially reducing size of training sample (from 105 cases to 45) remains quite high. Method of fuzzy decision trees is better for medium size of training sample while the method of direct generating fuzzy rules is better for small size of training sample. Further research will be in development of algorithm based on combination of both approaches.
Fig. 9 and Fig. 10 illustrate the comparison between the two methods with sequentially reducing size of training sample using T-class and S- class membership functions respectively.
T – class membership function also known as triangular is specified by three parameters {a, b, c} as follows: ( , , , ) = { − − − − 0, ≤ , ≤ ≤ , ≤ ≤ 0, ≤ 1 + − ( − )
0, ≥
For T-class membership functions, we observe that fuzzy decision trees method is better for large size of training sample while the method of direct generating fuzzy rules is better for small and medium size of training sample. In case of S-class membership functions, we observe the same situation.
Decision trees are successfully used to solve regression and classification problems. They are popular in the field of machine learning, because decision trees build graphic models, along with text rules that are easily interpreted by the users. On the other hand, fuzzy systems can solve classification problems with input inaccurate and noisy data.
The combination of fuzzy trees and fuzzy logic makes it possible to construct intuitive graphic
models for qualitative and quantitative data [
In addition, in the course of the conducted studies, the advantage of classification using fuzzy decision trees with respect to classical ones was revealed, by comparing the percentage of correctly classed objects. Also, a direct correlation between the accuracy of the classification and the value of the information gain was revealed (the increment is a criterion for stopping the further construction of the tree).
The comparison between algorithm of direct generating fuzzy linguistic rules and method of fuzzy
decision trees didn’t reveal the one and only right one. Both methods show high classification
accuracy under certain conditions. The proposed approach can be applied to built fuzzy neural
networks [