A method for constructing decision trees based on the mutual similarity of objects is proposed. The method allows obtaining complex decision boundaries, which have a clear logical interpretation. The results of the experiments confirm the effectiveness of the method for multispectral image recognition. - automatically determine the most informative features for each classified object and use them for making a decision;
– give one an opportunity to analyze information of different types (i.e., for quantitative and qualitative characteristics describing objects), in the presence of missed feature values; – find probabilistic logical rules that reflect cause-and-effect relationships of the phenomenon under study;
– in combination with an ensemble approach (e.g., decision forest, boosting on trees [
A recent review of existing methods for DT induction is given in [
A “classical” DT is a tree-like graph, in the nodes of which conditions of two possible types are tested. If X is a numerical attribute, then the condition “X(a) < b” is examined, where a is an arbitrary object from the statistical population, X(a) is the value of X for object a, b is some value of the attribute. If X is a categorical attribute, then the condition “X(a)=b” is checked. Depending on the truth or false of the test, the left or the right sub-node is chosen. The leaves (terminal nodes) of the tree are associated with the values (class labels) of the predicted feature. The paths from the root node to leaves represent classification rules. To find an optimal DT, a recursive partition of feature space is performed.
This approach has a significant drawback: the partitioning of feature space occurs strictly parallel to the feature axes (in the case of numerical features), even if the real boundary between classes has a linear shape (Figure 1). To approximate the boundary, it is necessary to use a more complex tree structure (with many additional nodes) that often has a negative influence on the efficiency of decisions.
Some works (e.g., [
–
Based on Support Vector Machine (SVM-ODT) [
yes class 0
Despite the significant improvement of prediction accuracy, this approach also has a number of limitations. First of all, the found linear boundaries are not-easy to interpret in contrast with simple rules of “classical” univariate DT. Another limitation is ODT is applicable only for multivariate data and cannot be used for data described with pairwise similarity matrices.
To overcome the latter difficulty, the work [
The method proposed in this paper aims to eliminate the above-mentioned drawbacks. We propose to use a more general type of statements regarding the similarity of observations. The similarity can be calculated using various metrics in different feature subspaces. This type of decision tree allows one to get more complex decision boundaries, which at the same time have a clear logical interpretation for the user.
The developed algorithm was experimentally investigated on model data and multispectral satellite images. 2
In this work, we consider a pattern recognition problem formulated as follows. Let us denote by a general population of objects under consideration, and by point = ( ) = ( (1), … , ( )) ∈ a feature description of object ∈ , where m is feature space F dimensionality. Let be a set of class labels. We consider a binary classification problem: = {−1, +1}, although the results can be extended to a multi-class scenario. Denote by the set of feature descriptions of objects from . Let ∗: → be an objective function with values assigned to the points of the finite set (training or learning sample) ⊂ . We need to build a decision function : → which belongs to a given family; should approximate y∗ and minimize the estimate of misclassification probability for any point ∈ . Let be another subset of used for evaluating the performance of the decision function, ∩ = ∅. Denote by = ∪ , and let d be the size of X and l be the size of .
We propose a modification of DT in which instead of standard tests, more general statements of the type “object a is more similar to the set A than to the set B in feature subspace F’ according to metrics ” are examined in the internal nodes. Here A, B are subsets of learning sample, typically of small cardinality. In this work, we assume that each set A, B includes exactly one object (its description is called a support point). We also shall assume that F’=F and metrics is the Euclidian metrics.
Suppose is a binary tree with t internal nodes, and = { 1, … }, = { 1, … , } are the sets of support points from positive and negative classes respectively. For each internal node of the tree, = 1, . . , , we define the tested statement as follows: " ∈ M1 ", where M1 are the points from feature space, which are closer to than to (figure 2). Thus, the data is separated linearly (figure 3).
For any ∈ we define matrix with elements: ( , ) = { 1,
0, ℎ where is a metric in feature space .
( , ) − ( , ) < 0
, i=1,…, p, j=1,…,n, objects represented by triangles, = 0.
Let us transform matrix into a vector ⃗⃗⃗⃗⃗ of the size by the reshaping procedure. Then each point is described by vector ⃗⃗⃗⃗⃗⃗ of the size . In this way, ′ = {⋃ ∈ ⃗⃗⃗⃗⃗ } is a new feature representation of .
Consider an example of feature transformation based on data shown in figure 2. As the number of all possible pairs equals one, matrix
has only one element. For objects represented by circles we have = 1, and for
The proposed form of DT splits data points based on their relative position. The support points selection method should consider their informativity for a given sample . In this work, three methods of support points selection were implemented.
The first approach uses Relief feature selection algorithm introduced in [
⊂ − reducing feature dimension.
The second way is based on Support vector machine (SVM) [
The last method is based on k-means clustering algorithm. We generate subsamples of the size from and apply k-means (k=2) to each subsample to extract cluster’s medoids which are considered as support points.
In addition, we used kernel k-means algorithm that uses kernel function instead of a scalar product. Kernel function implicitly transforms initial feature space into another space of larger dimensionality, where the configuration of data points is changed, often resulting in linearly separable form. 3 4 5
When using SVM or k-means based selection methods, we get linear computational complexity, while using Relief or kernel k-means results in quadratic complexity depending on the sample size.
The proposed method was experimentally studied on three two-dimensional model datasets. Each dataset consists of 100 elements belonging to one of two classes. Figure 4 shows the original datasets: «Moons», «Circles» and «Linear». The parameter values for the CART algorithm were selected by default. Support points for the SBDT algorithm were selected with k-means algorithm. Figures 5 and 6 show the classification results obtained by CART and SBDT algorithms respectively. They also indicate classification mistake probability values obtained by the
o o o
Step 1. Find sets of support points and of classes +1, –1.
Step 2. Compute vector ⃗⃗ for all ∈ .
Step 3. Build a decision tree in new feature space {⋃ ∈ ⃗⃗⃗⃗⃗ } by CART method.
We chose CART algorithm [
«moving exam» method. These examples demonstrate that the SBDT method provides higher classification accuracy compared to the CART algorithm. These figures also show that the decision boundaries constructed by the CART algorithm are coarser. 6
To compare CART and SBDT algorithms performance on real data, Landsat 8 satellite image of Iskitim city (Novosibirsk region) was used. The RGB composite of this image is introduced in Figure 7a. Figure 7b shows the map of this image made by visual-instrumental methods containing representatives of six classes. It was used to train and to test the classifiers. 10% of the mapped pixels were used for training. As a result, classification accuracy of CART and SBDT algorithms is 88% and 98% respectively. Figure 7c shows SBDT image classification result.
Thus, the proposed SBDT decision tree construction method based on the mutual objects similarity provides higher classification quality compared to the CART method not only on model, but also on real data. The SBDT (b) (b) (a) (a) method allows obtaining more accurate decision boundaries, which have a clear logical interpretation. The results of the experiments confirm the effectiveness of the method for multispectral satellite image classification. a b c
Acknowledgements. This work was supported by the RFBR (Grant No. 18-04-0063a) and the Interdisciplinary Integration Research program of the SB RAS for 2018-2020 (project No. 37).