Introduction

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 [1].

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.

Decisiontrees

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 [1].

Decision trees create efficient models for machine learning [11,12]. Let us give the following characteristics of decision trees:

 they are easily interpretable and visible;  the model can be expressed both graphically and with text rules;  they are competitive in comparison with more expensive approaches;  decisiontrees are scalable;  they can process discrete and continuous data;  decision trees can be applied to different sizes of data sets, including large sample sets.

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.

Fuzzy decisiontrees

To construct a fuzzy decision tree, the following procedure is proposed [4]:

1. Define the fuzzy data base, i.e., the fuzzy granulation for the domains of the continuous features. The entropy and information gain formulas remain the same for the classical version of the ID3 algorithm [10]. Let us introduce the following notation:

set of data samples; set of attributes; a singleton set with a solution attribute or class attribute. Let this attribute have m different values, thens i is the number of samples of set U in class d i .

Information gain I relative to subset S j is equal to: , , where the number of samples in a subset of S. Entropy E(c i ) 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 [9], which has 4 attributes: the length and width of the cup, the length and width of the petal and the three resultant classes -setosa, versicolor and virginica.

Theresearch results

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 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.

Table 1. Comparison of classification results obtained using fuzzy decision trees and classical decision

trees.

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.

Fuzzy decision trees

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.

Table 3 shows the dependence of the accuracy of the data classification on the value of the information gain. In this method, the increment of information will be the breakpoint of the algorithm, that is, when the specified value is reached, further building of the tree stops. According to the data it is clear that the lower the information gain, the more accurate and "deeper" the tree will be built. 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 [3]. The second method of fuzzy decision trees which is proposed in this article was used. Fig. 7 gives visual illustration of comparison between the two methods for sequentially growing number of terms.

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. 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.

Conclusion

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 [2, 7,8]. Usage of this type of decision tree gives us several solutions with different probabilities of belonging to a particular class.

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 [13].

References