Random subspace oracle (RSO) ensemble to solve small sample-sized classification problems

Abstract

Under certain situations, researchers were forced to work with small sample-sized (SSS) data. With very limited sample size, SSS data have the tendency to undertrain a machine learning algorithm and rendered it ineffective. Some extreme cases in SSS problems will have to deal with large feature-to-instance ratio, where the high number of features compared to small number of instances will overfit the classification algorithm. This paper intends to solve small sample-sized classification problems through hybrid of random subspace method and random linear oracle ensemble by utilizing binary feature subspace splitting and oracle selection scheme. Experimental results on artificial data indicate the proposed algorithm can outperform single decision tree and linear discriminant classifiers in small sample-sized data, but its performance is identical to k-nearest neighbor classifier due to both shared similar selection approach. Results from real-world medical data indicate the proposed method has better classification performance than its corresponding single base classifier especially in the case of decision tree.

Keywords

Ensemble method classification small sample Euclidian’s distance

1 Introduction

Due to the rapid development of modern technologies such as computers, networks, sensors and digital storage systems, data collection has become much cheaper and effortless. Thus, researchers are overwhelmed with massive size of data, which in fact, leads to the popularity of a new research field called the big data analysis [25]. However, not every data sets are made publicly accessible, information such as medical status and industrial process are confidential, resulting very limited sample data available for public researchers. So, the importance of small sample-sized (SSS) data classification should not be ignored [4 , 21]. The term “small” is rather subjective. Let the number of instances in a data set be N, and the number of features is M. According to Vapnik, a data set was considered small when the ratio N/M is less than 20 [21].

Ensemble methods have been the saviors for SSS data classification, especially the Bootstrap Aggregating (Bagging) and Random Subspace Methods (RSM) approaches. Bagging utilized random sampling with replacement approach, allowing each classifier to train on randomly generated training sets, providing a much more diverse result. Similar approach had been employed by RSM, except that the data generation is done in the feature space. RSM randomly selects a subset of feature for the classifier to train on, resulting in several classifiers which each expert in different feature space. Thus, RSM have been considered for problems with limited number of samples thanks to its ability to reduce data dimension while maintaining the number of training objects [17, 20].

Even though overall information can be preserved by aggregating many individual classifiers expert in different feature subspaces, there will still be loss of information from the base classifier perspective. Every base classifier in an ensemble will contribute to the final decision made through a method called classifier combination, the process usually involves a majority voting scheme whereby the result from each base classifier will be considered. Base classifiers that suffer from information loss have greater possibilities to undertake wrong judgement, which eventually will provide an impact to the final decision.

This research aims to design an ensemble method that capable in solving SSS classification problems through feature data manipulation approach inspired by hybridization of RSM with Random Linear Oracle (RLO) ensemble, namely Random Subspace Oracle (RSO).

This paper is structured as follow: Section 2 reviews the materials and concepts of learning algorithm. Section 3 gives the working principle of proposed method. Section 4 explains the experimental setup for this work. Section 5 presents the results obtained from experiment and briefly discuss it. This paper ends with Section 6 drawing conclusion to this work.

2 Materials and concepts

This section reviews the principle of basic classifiers, and structure of RSM and RLO ensemble methods.

2.1 Decision tree (DT)

DT algorithm is a flowchart-like tree structure, where each internal node in the tree was represented by a test on a feature, each branch denotes an outcome, and each leaf node contains a class label [22].

The construction of DT model revolves around three main aspects: feature evaluation criterion, leaf creating criterion, and pruning. It is common to describe tree classifier using a graph terminology, starting with a root node which contains all the training samples. If the node is pure enough to satisfy the stopping rules, a leaf holding the dominant class label will be added to the tree. Else, each feature in the data will be examined, and the most discriminative feature will be used to make a split (usually a binary split for continuous-valued problem) according to the best threshold. The process will be repeated on the Left and Right child nodes using data that satisfied respective conditions from the previous test.

With greedy growing approach, DT algorithm is sure to select feature with the most information gain to split on each node, without considering the tests conducted by the other nodes [8]. This approach will lead to a situation where a single feature will be tested several times on different nodes, each with a different threshold value.

Prediction of new data will start from root node of the tree, travel down the path according to the respective feature being tested on each node, and eventually reaching a leaf node. Due to the binary threshold split, the decision boundaries of DT algorithm take the form of lines (or planes/hyperplanes in higher dimensions).

2.2 Linear discriminant classifier (LDC)

Discriminant classifier is named after the discriminant function used by the classifier to determine the classification boundaries [3, 16]. Assuming N data samples from one experiment, x _n = {x₁, …, x_m} is the feature vector for n-th instance, ω = {ω₁, …, ω_C} is the class vector that are available for label. LDC is defined by the function: $g_{i} (x_{n}) = w_{i 0} + w_{i}^{T} x_{n}$ (1)

Where sample will be assigned with the tag of largest g_i ( x _n), for i ∈ [1, C], n ∈ [1, N].

In pattern recognition, each category of feature is referred as a dimension, so the classification boundaries of LDC in two-dimensioned problem will consists of several straight lines depending on the number of classes, several number of planes in three-dimensioned problem, and hyperplanes for higher number of dimensions.

2.3 K-nearest neighbor (KNN)

Although with the name of “lazy” algorithm, KNN is said as the simplest and most attractive pattern classification approach [14]. The term “lazy” refers to that learner did not attempt to formulate a discriminative function from the training data, but it “memorizes” the data instead [1]. Doing so will requires a massive memory storage, but the training process ends almost instantly. In [7], KNN classifier outperform any other algorithms that were being compared.

During classification phase, KNN calculates distances between the new data point and all training data. Several training data which are nearest to the new data point will be selected, whereby each data point will provide a vote to determine the final label to be assigned to the new data point. The number of training data selected was controlled by the value K (usually odd numbered), so a KNN algorithm with one nearest neighbor will be called 1-NN, 3-NN for three nearest neighbors, and so on.

2.4 Random subspace method (RSM)

RSM is an ensemble method introduced in [24], the author proposed to construct multiple tree classifiers by training on different randomly chosen feature subspace. Due to how easily decision tree algorithm can overfits the training data especially when the sample size is small, RSM was originally proposed to solve this overfitting issue by limiting the number of features provided to the learner. Thus, a fully-grown tree in the ensemble does not requires pruning because the tree overfits only the data subspace provided to it, instead of the whole data space.

Assuming a training set with N number of instances, and M number of features. RSM first decides the number of subspace features, D to be selected for generation of new training subset, where D < M (usually D = M/2). For each subset generated, a base classifier will be applied to train on that subset, thus for an ensemble with size of L, L subsets of feature will be generated, and L number of classifiers will be trained.

The classification stage of RSM was done by the individual classifiers in ensemble, by having each base classifier provides a prediction to the new sample, and a fusion scheme will be used to combine all predictions into one final decision.

Due to the working principles of RSM, it is highly suitable for the use in SSS problem. RSM reduces the dimensionality of the data while maintaining the same number of samples, relatively increases the amount of training samples [19, 20].

2.5 Random linear oracle (RLO)

Random Linear Oracle (RLO), introduced by Kuncheva and Rodríguez in year 2007, is a unique ensemble method that combines both classifier fusion and selection approaches [18]. In RLO ensemble method, each classifier in the ensemble is replaced with two mini-ensembles plus a random oracle function that choose between them.

Training of RLO ensemble involved a randomly generated oracle of hyperplane over the whole feature space, separating it into two different subspaces. Two base classifiers will be trained on each subspace respectively, yielding two different classifiers.

Figure 1 illustrate how the RLO method be applied to a 2-class problem. Moreover, several RLO ensembles will be trained on the same feature space, each with a randomly generated oracle, and two classifiers that trained on separated feature subspaces.

Fig.1

RLO ensemble method applied to 2-class problem [10].

When a new sample data comes to test, the location of that data will first be determined by oracle in each ensemble, and corresponding classifier expert in that region will be selected to classify the object. Finally, a fusion scheme will be applied to combine all predictions into one final decision.

3 Proposed method

This research proposes a hybrid of RSM and RLO ensemble methods and named as random subspace oracle (RSO) due to its feature subspace splitting and oracle selection scheme.

RSM is good in dealing with SSS data sets but in some extreme cases where the number of features can easily exceed the number of instances, massive number of redundant features will also present in the data set. The high number of redundant features will lower the chance of a significant feature being selected during subset generation, rendering the training of classifier ineffective. As well in [2], the authors pointed out that due to effect from random selection, classifiers trained by subsets with low class separability will affect the final decision of whole ensemble because it suffered from loss of information.

To cover up the drawback in random feature selection, the oracle approach in RLO ensemble is implemented in the feature level.

The building of RSO model starts with a split of training set in the feature level, using random selection approach from RSM to create one training subset, another subset will be created with the remaining non-selected features, yielding two subsets with distinctive features but same number of instances. Thus, a total number of M2 / - 2 - 1 different combinations can be formed through this approach.

Each classifier in the ensemble will be replaced with two mini-ensembles according to RLO approach, and each mini-ensemble will be trained on one of the previously created training subsets. This approach allowed every classifier in the ensemble to approach a single problem from two different perspectives.

Since both mini-ensembles expert in different dimensions, the hyperplane oracle selection of classifier based on the data point’s location is not viable. This research will investigate the simplest yet elegant form of dynamic selection through Euclidian’s distance. Benchmark for each mini-ensemble was recorded by the mean point of respective training subset. So, distances are measured from the new data point to benchmarking point of corresponding mini-ensemble. Mini-ensemble with the shortest distance from its benchmarking point to the new data point will be used to carry out classification process.

The fusion approach of RSO ensemble is made by simple majority voting, the final label of new data point is assigned to the class with highest votes. Figure 2 provides the pseudo code of RSO ensemble method in its training and operation phases.

Fig.2

Pseudo code for RSO ensemble training and operation phases.

4 Experiment

This section introduces the methodology of this research, discussing the generation of artificial data sets, data manipulation layout, analysis tool, and experiment procedure.

4.1 Data generation

This experiment starts with generation of artificial data using Waikato Environment for Knowledge Analysis (WEKA) software [11]. Data sets are generated with RandomRBF generator in WEKA according to properties in Table 1.

Table 1
Naming and properties of artificial data sets

Data Set Instance Feature Class N/M Data Set Instance Feature Class N/M

V1_2 100 200 2 0.5 X6_2 600 1000 2 0.6

V2_2 200 200 2 1 X7_2 700 1000 2 0.7

V3_2 300 200 2 1.5 X8_2 800 1000 2 0.8

V4_2 400 200 2 2 X9_2 900 1000 2 0.9

V5_2 500 200 2 2.5 X10_2 1000 1000 2 1

V6_2 600 200 2 3 Y1_2 100 2000 2 0.05

V7_2 700 200 2 3.5 Y2_2 200 2000 2 0.1

V8_2 800 200 2 4 Y3_2 300 2000 2 0.15

V9_2 900 200 2 4.5 Y4_2 400 2000 2 0.2

V10_2 1000 200 2 5 Y5_2 500 2000 2 0.25

W1_2 100 500 2 0.2 Y6_2 600 2000 2 0.3

W2_2 200 500 2 0.4 Y7_2 700 2000 2 0.35

W3_2 300 500 2 0.6 Y8_2 800 2000 2 0.4

W4_2 400 500 2 0.8 Y9_2 900 2000 2 0.45

W5_2 500 500 2 1 Y10_2 1000 2000 2 0.5

W6_2 600 500 2 1.2 Z1_2 100 5000 2 0.02

W7_2 700 500 2 1.4 Z2_2 200 5000 2 0.04

W8_2 800 500 2 1.6 Z3_2 300 5000 2 0.06

W9_2 900 500 2 1.8 Z4_2 400 5000 2 0.08

W10_2 1000 500 2 2 Z5_2 500 5000 2 0.1

X1_2 100 1000 2 0.1 Z6_2 600 5000 2 0.12

X2_2 200 1000 2 0.2 Z7_2 700 5000 2 0.14

X3_2 300 1000 2 0.3 Z8_2 800 5000 2 0.16

X4_2 400 1000 2 0.4 Z9_2 900 5000 2 0.18

X5_2 500 1000 2 0.5 Z10_2 1000 5000 2 0.2

Data Set	Instance	Feature	Class	N/M	Data Set	Instance	Feature	Class	N/M
V1_2	100	200	2	0.5	X6_2	600	1000	2	0.6
V2_2	200	200	2	1	X7_2	700	1000	2	0.7
V3_2	300	200	2	1.5	X8_2	800	1000	2	0.8
V4_2	400	200	2	2	X9_2	900	1000	2	0.9
V5_2	500	200	2	2.5	X10_2	1000	1000	2	1
V6_2	600	200	2	3	Y1_2	100	2000	2	0.05
V7_2	700	200	2	3.5	Y2_2	200	2000	2	0.1
V8_2	800	200	2	4	Y3_2	300	2000	2	0.15
V9_2	900	200	2	4.5	Y4_2	400	2000	2	0.2
V10_2	1000	200	2	5	Y5_2	500	2000	2	0.25
W1_2	100	500	2	0.2	Y6_2	600	2000	2	0.3
W2_2	200	500	2	0.4	Y7_2	700	2000	2	0.35
W3_2	300	500	2	0.6	Y8_2	800	2000	2	0.4
W4_2	400	500	2	0.8	Y9_2	900	2000	2	0.45
W5_2	500	500	2	1	Y10_2	1000	2000	2	0.5
W6_2	600	500	2	1.2	Z1_2	100	5000	2	0.02
W7_2	700	500	2	1.4	Z2_2	200	5000	2	0.04
W8_2	800	500	2	1.6	Z3_2	300	5000	2	0.06
W9_2	900	500	2	1.8	Z4_2	400	5000	2	0.08
W10_2	1000	500	2	2	Z5_2	500	5000	2	0.1
X1_2	100	1000	2	0.1	Z6_2	600	5000	2	0.12
X2_2	200	1000	2	0.2	Z7_2	700	5000	2	0.14
X3_2	300	1000	2	0.3	Z8_2	800	5000	2	0.16
X4_2	400	1000	2	0.4	Z9_2	900	5000	2	0.18
X5_2	500	1000	2	0.5	Z10_2	1000	5000	2	0.2

Using artificial data in this experiment is to test the default ability of each algorithm as generated data are noise-free, and the behavior of data can be controlled through generator.

Data sets will be generated with number of features ranging from 200, 500, 1000, 2000, and 5000. Furthermore, for each feature number, ten data sets will be produced, each with different number of instances ranging from 100 to 1000 with an interval of 100, yielding a total of 50 data sets. Class number is fixed at 2.

For clarification, naming of data sets with 200 features will be prefixed with alphabet ‘V’, 500 features will be prefixed with alphabet ‘W’, ‘X’ for data sets with 1000 features, ‘Y’ for data sets with 2000 features, and data sets with 5000 features will be prefixed with ‘Z’. Each prefix will be followed by a value representing its number of instances divided by 100. The class number will be after the name of data set with an ‘_’ separator. For example, data set with name ‘X3_2’ will has 300 instances, 1000 features, and 2 classes. The instance-to-feature ratio will also be given in Table 1.

Furthermore, to properly investigate the performance of algorithms, 4 private medical data sets from [15] were used. Table 2 gives the properties of 4 data sets.

Table 2

Properties of medical data sets

Data Set	Instance	Feature	Class	N/M
contractions	98	27	2	3.63
rds	85	17	2	5.00
laryngeal1	213	16	2	13.31
weaning	302	17	2	17.76

The “contractions” data set recorded intestinal contractions of patient through wireless capsule video endoscopy. Data set “rds” contains clinical records of 85 premature new-born children with two types of respiratory distress syndrome (RDS), also known as Hyaline Membrane Disease (HMD) and non-HMD. The “laryngeal1” data set extracted 16 features in time, spectral, cepstral domains from 213 normal or pathological voices used for computer decision support system. Finally, “weaning” data set consists of 151 patients suffering from acute respiratory insufficiency on a long-term mechanical ventilation measured once before weaning and once at the start of weaning, so each patient will be an instance in both classes, yielding a total of 302 instances. All four data sets have an instance-to-feature ratio less than 20.

4.2 Data manipulation

Data manipulation process is here to avoid the circumstances of overfitting or peeking, this research utilized the well-known cross-validation paradigm. K-fold cross-validation divides the data set into K regions using stratified sampling method, with this, it can minimize the bias in data due to random separation of data space [13]. This experiment separates the fold by K = 10, with leave-one-out approach, one region will be reserved as testing set, while the remaining 9 regions were used for training. This process will be repeated for 10 iterations, each with a different fold as the testing set, thus 10 results will be obtained for each algorithm. These recorded results will be used to evaluate the performances of all algorithms throughout one data set. The overall performance of an algorithm can be obtained by averaging all 10 results.

4.3 Wilcoxon signed-rank (WSR) test

Wilcoxon signed-ranks (WSR) test introduced in [9] provides a non-parametric pairwise comparison based on ranking of treatments will be used as the analysis tool to draw conclusion on algorithms’ performance. WSR was termed as the non-parametric alternative of paired t-test approach. For each data set, this method assigns a rank to the differences in performances of two algorithms in test, considers only the absolute values. Average ranks will be assigned in case of ties.

In [12], the author recommended that non-parametric tests are preferred over parametric tests in typical machine learning studies, because most results from machine learning experiment are distribution-free in nature and could not fulfil the safe usage of parametric tests.

Assuming classification results of two algorithms over N number of data sets were organized as N × 2 matrix. Given d_i be the difference between classification accuracies from two algorithms on i-th among all N number of data sets. Let R⁺ be the sum of ranks when second algorithm performed better than the first algorithm, and vice versa for R^-. The sums are calculated by Equations (2 and 3). $R^{+} = \sum_{d_{i} > 0} rank (d_{i}) + \frac{1}{2} \sum_{d_{i} = 0} rank (d_{i})$ (2) $R^{-} = \sum_{d_{i} < 0} rank (d_{i}) + \frac{1}{2} \sum_{d_{i} = 0} rank (d_{i})$ (3)

As seen from the equations, sum of ranks for tied cases are distributed evenly in both sums. Next, Equation (4) can be used to obtain the z-score of test. $z = \frac{T - \frac{1}{4} N (N + 1)}{\sqrt{\frac{1}{24} N (N + 1) (2 N + 1)}}$ (4)

Where T is the smaller sum of ranks among R⁺ and R^-, T = min(R⁺, R^-). If the test successfully rejected null hypothesis, indicating there is a significant different between two algorithms, the signed sums of ranks will be used to determine which algorithm performed better.

4.4 Experiment procedure

The experiment compares RSO ensemble with three distinct single classifiers by having RSO ensemble use the respective single classifier as its base. The size of ensemble was set to 25, as it was stated in [23] that this number of ensemble size provided the largest profit in accuracy.

Data sets were arranged according to number of features, prefixed with distinct alphabets (“V” until “Z”) for easy identification. Experiments were done in batches of five, based on data sets’ prefix.

The performance analysis will be done with the overall classification accuracies using pairwise WSR test between the single classifier and RSO ensemble using that classifier as base by stating the null and alternative hypotheses as: $\begin{matrix} H_{0} : Both algorithms have similar performance \\ H_{1} : Both algorithms have distinct performance \end{matrix}$ (5)

The test will be carried out with a standard α-value of 0.05. If the resulting p-value from the test was less than 0.05, indicating there is a significant difference in performance in those two algorithms, signed rank should be checked to determine which algorithm has better performance.

5 Results and discussion

This section discusses the results obtained from experiment, and separated them into two components: artificial data, and real-world data.

5.1 Artificial data

Table 3 gives the definition of acronyms used in this experiment.

Table 3
Definition of acronyms

Acronym Definition

TREE Single decision tree classifier with CART algorithm

RSO_TREE RSO ensemble with TREE base classifier

LDC Single Linear Discriminant Classifier

RSO_LDC RSO ensemble with LDC base classifier

KNN Single 1-nearest neighbour classifier

RSO_KNN RSO ensemble with KNN base classifier

Acronym	Definition
TREE	Single decision tree classifier with CART algorithm
RSO_TREE	RSO ensemble with TREE base classifier
LDC	Single Linear Discriminant Classifier
RSO_LDC	RSO ensemble with LDC base classifier
KNN	Single 1-nearest neighbour classifier
RSO_KNN	RSO ensemble with KNN base classifier

Results of prefix “V” data sets are recorded in Table 4, bolded algorithms’ name indicates better algorithm among the pair when there is a significant different from test results. RSO outperformed single classifier only in two cases, TREE and LDC in term of mean classification accuracy, a stalemate in the case of KNN.

Table 4

Overall results of prefix “V” data sets

Algorithm	Mean accuracy (%)	p-value	Decision
TREE	95.41	0.0020	Reject
RSO_TREE	97.83
LDC	98.27	0.0313	Reject
RSO_LDC	98.92
KNN	98.74	1.0000	Failed to reject
RSO_KNN	98.75

However, based on [6], “no free lunch” (NFL) theorem stating that no search algorithm can outperforms any other algorithms when their performances are averaged across all potential problems. This theorem also holds true in supervised machine learning. So, mean accuracy does not provide a good indication of algorithm performance, WSR test decision should be considered instead.

With p-value as small as 0.0020 and level of significant α= 0.05, RSO ensemble with TREE as base classifier significantly outperformed single TREE classifier. Followed by LDC/RSO_LDC pair with p-value = 0.0313, succeeded in rejecting the null hypothesis, proving that RSO_LDC performed better than single LDC in the case of 200 features data sets.

On the other hand, KNN/RSO_KNN pairs failed to reject null hypothesis, showing that RSO ensembles have similar performance as corresponding single classifiers. The p-value ranged from 0 to 1. KNN/RSO_KNN pairs attained the maximum p-values of 1, indicates that there is exactly no difference between the performance of RSO and its KNN single classifier. Thus, both algorithms will always provide the same classification results.

Prefix “V” data sets contained data with 200 features and distinct number of instances. Since RSO ensemble works by splitting the feature space into two subsets, the number of features available should have an impact to the performance of algorithm. Observing Table 5 where the overall results of prefix “W” data sets (500 features) are presented, the mean accuracies from all algorithms received slight increment except RSO_LDC.

Table 5

Overall results of prefix “W” data sets

Algorithm	Mean accuracy (%)	p-value	Decision
TREE	97.70	0.0039	Reject
RSO_TREE	98.63
LDC	98.36	0.0938	Failed to reject
RSO_LDC	98.83
KNN	99.58	1.0000	Failed to reject
RSO_KNN	99.58

From Table 5, TREE/RSO_TREE pair with p-value of 0.0039 can reject null hypothesis in favor of alternative hypothesis stating that both algorithms are significantly different. The same case happened for KNN/RSO_KNN pair, where their p-value = 1 showing that the performance of RSO ensemble is identical to single KNN classifier. A change in decision happened for LDC/RSO_LDC pair where its p-value = 0.0938 and failed to reject null hypothesis, which majorly caused by the slight decrement in mean accuracy of RSO_LDC.

The overall results of data sets with prefix “X”, “Y”, and “Z” (1000, 2000, and 5000 features) are presented in Tables 6– 8, respectively. All three sets of data arrived at same decision as in Table 5, where only TREE/RSO_TREE pair can reject null hypothesis in favor of alternative hypothesis at 95% confidence level. Further proving the ability of RSO ensemble in improving the performance of single TREE classifier in SSS cases.

Table 6

Overall results of prefix “X” data sets

Algorithm	Mean accuracy (%)	p-value	Decision
TREE	96.12	0.0195	Reject
RSO_TREE	97.11
LDC	98.72	0.6406	Failed to reject
RSO_LDC	98.78
KNN	98.92	0.5000	Failed to reject
RSO_KNN	98.77

Table 7

Overall results of prefix “Y” data sets

Algorithm	Mean accuracy (%)	p-value	Decision
TREE	97.97	0.0020	Reject
RSO_TREE	98.68
LDC	99.46	1.0000	Failed to reject
RSO_LDC	99.48
KNN	99.18	0.4375	Failed to reject
RSO_KNN	99.30

Table 8

Overall results of prefix “Z” data sets

Algorithm	Mean accuracy (%)	p-value	Decision
TREE	97.97	0.0156	Reject
RSO_TREE	98.28
LDC	99.07	1.0000	Failed to reject
RSO_LDC	99.05
KNN	98.94	1.0000	Failed to reject
RSO_KNN	98.89

Finally, to get a generalized performance analysis, all results from 50 data sets were combined, and WSR test was carried out on the combined result. From Table 9, two pairs of algorithms, TREE/RSO_TREE and LDC/RSO_LDC, able to reject null hypothesis in favor of alternative hypothesis with p-value less than the designated α-value. Especially in the case of TREE/RSO_TREE pair, WSR test concluded that RSO_TREE is significantly better than single TREE classifier with possibility of error occurrence as small as 1.88×10^–8.

Table 9

Overall results of all data sets

Algorithm	Mean accuracy (%)	p-value	Decision
TREE	97.03	1.88×10^–8	Reject
RSO_TREE	98.11
LDC	98.77	0.0074	Reject
RSO_LDC	99.01
KNN	99.07	0.4023	Failed to reject
RSO_KNN	99.06

Next, with p-value of 0.0074, LDC/RSO_LDC pair showed significant difference in performance. The performance of RSO ensemble with LDC as base classifier is relatively unstable than using TREE as base classifier. RSO_LDC outperformed single LDC in prefix “V” data sets (200 features) as shown in Table 4. However, as the number of features increases, the difference between two algorithms getting smaller, and eventually single LDC attained a slightly higher mean accuracy than RSO_LDC as in Table 8. In the case of KNN/RSO_KNN pair, RSO ensemble never did once managed to perform better than single KNN classifier. Thus, using RSO ensemble with KNN as base classifier to solve SSS problems is not recommended.

5.2 Real-world data

Artificial data without noises only allow investigation of algorithm operation in its ideal form, but a reliable classification algorithm should include noise tolerance when solving complex real-world problems. Table 10 recorded the classification accuracies, as well as the average accuracy of each algorithm across all four medical data sets. Bolded values indicate the cases when RSO ensemble outperformed its corresponding base classifier.

Table 10
Results of four real-world medical data sets

Data Set TREE RSO_TREE LDC RSO_LDC KNN RSO_KNN

contractions 80.56 84.67 81.56 83.78 85.56 84.56

rds 85.69 84.58 92.92 90.56 65.42 69.17

laryngeal1 76.54 77.51 85.41 84.00 78.44 80.37

weaning 79.82 82.80 82.77 83.11 74.22 78.51

Average accuracy 80.65 82.39 85.66 85.36 75.91 78.15

Data Set	TREE	RSO_TREE	LDC	RSO_LDC	KNN	RSO_KNN
contractions	80.56	84.67	81.56	83.78	85.56	84.56
rds	85.69	84.58	92.92	90.56	65.42	69.17
laryngeal1	76.54	77.51	85.41	84.00	78.44	80.37
weaning	79.82	82.80	82.77	83.11	74.22	78.51
Average accuracy	80.65	82.39	85.66	85.36	75.91	78.15

Ranking of performance was done by observing each data set, algorithm with the highest accuracy will be ranked at 1, algorithm with lowest accuracy ranked at 6, average of rank will be assigned in the case of tie. Table 11 presents the summarized ranking of all algorithms.

Table 11

Ranking of each algorithm across all real-world medical data sets

Data Set	TREE	RSO_TREE	LDC	RSO_LDC	KNN	RSO_KNN
contractions	6	2	5	4	1	3
rds	3	4	1	2	6	5
laryngeal1	6	5	1	2	4	3
weaning	4	2	3	1	6	5
Average rank	4.75	3.25	2.5	2.25	4.25	4

Observed from the average rank, all RSO ensembles have a better ranking than their corresponding base classifier, TREE/RSO_TREE pair has the largest rank increment (from rank 4.75 to 3.25) with 1.74% difference in average accuracy. Also, RSO_LDC has the best performance among all six algorithms with rank of 2.25, slightly better than single LDC ranked at 2.5. However, single LDC (85.66%) has a little advantage than RSO_LDC (85.36%) in term of average classification accuracy. On the other hand, single KNN received minor improvement from RSO method when dealing with real-world data sets, increasing its average accuracy from 75.91% to 78.15%.

6 Conclusion

This research proposed a hybrid of RSM and RLO ensemble methods named as Random Subspace Oracle (RSO) to solve small sample-sized classification problems. The method involved binary feature splitting through random sub-spacing, and an oracle selection approach to choose between mini-ensembles that expert from different dimensions, finally fusing all decision from base classifiers by majority voting scheme.

From Section 5, RSO ensemble with TREE base classifier showed significant result when compared to single TREE classifier with p-value as small as 1.88×10^–8 from pairwise WSR test, and improvement of rank from 4.75 to 3.25 when dealing with real-world data sets. Followed by RSO ensemble with LDC base classifier that succeeded in rejecting null hypothesis when dealing with prefix “V” (200 features) data sets and combined result. Although RSO_LDC achieved higher ranking in real-world data sets when compared to single LDC, the average accuracy of RSO_LDC incurred by some slight drawback.

RSO ensemble failed in WSR test when using KNN as its base classifier. The incapability of RSO ensemble possibly caused by the inappropriate oracle selection mechanism. Euclidian’s distance was used as the oracle in this case with mean point of each training subset as the benchmark. Mini-ensemble with the shortest Euclidian’s distance from its benchmarking point to the new data point will be used for classification. This approach is same as the principle used in single KNN classifier where the distance to the nearest neighbor will decides the outcome. Resulting in similar performance across all data sets.

The success of RSO ensemble can be attributed to two main aspects: the random selection of feature, and the splitting of feature space. Random selection of feature reduces the dimensionality of data while maintaining the same number of samples, relatively increases the total amount of training samples. On top of that, oracle splitting was used to maintain the loss of data integrity due to random feature selection, provides two options for each classifier in the ensemble to solve a problem from two different viewpoints.

However, due to the splitting of feature space that requires each classifier to be formed from two mini-ensembles, the training time for each classifier in the ensemble is two-fold. In that case, the overall training and classification time is the same as RLO ensemble.

For future development, strategy such as altering the number of criteria required to make decision can be made. So, with the original Euclidian’s distance measurement, aspects such as correlation and probability can be added as oracle, each with its own evaluation condition, and a fusing approach will be used to combine all decision made. Thus, the mini-ensemble selection can be more dynamic through more inspection from different perspectives.

Footnotes

Acknowledgments

To everyone that contributed and supported in this research.

References

Andrade , “K nearest neighbor and lazy learning,” Data Science Guide, 2016 [Online]. Available: http://datascienceguide.github.io/k-nearest-neighbor [Accessed: 13-Aug-2017].

Mert

, Kılıc

and Bilgili

, Random subspace method with class separability weighting, Expert Syst33(3) (2016), 275–285.

Bishop

C.M.

, Pattern recognition and machine learning, 4(4) (2006).

Zhang

, Liang

, Matsuyama

, Small sample size face recognition using random quad-tree based ensemble algorithm, in International Conference on Imaging for Crime Detection and Prevention, 2013.

Zhang

, Liang

, Matsuyama

, Generic learning-based ensemble framework for small sample size face recognition in multi-camera networks, Sensors14(12) (2014), 23509–23538.

Wolpert

D.H.

, Macready

W.G.

, No free lunch theorems for optimization, IEEE Trans Evol Comput1(1) (1997), 67–82.

Amancio

D.R.

, Comin

C.H.

, Casanova

, Travieso

, Bruno

O.M.

, Rodrigues

F.A.

, da Fontoura Costa

, A systematic comparison of supervised classifiers, PLoS One9(4) (2014).

Riskin

E.A.

, Gray

R.M.

, A greedy tree growing algorithm for the design of variable rate vector quantizers, IEEE Trans Signal Process39(11) (1991), 2500–2507.

Wilcoxon

, Individual comparisons by ranking methods, Biometrics Bull1(6) (1945), 80–83.

10.

Armano

, Hatami

, Random prototype-based oracle for selection-fusion ensembles, 2010 20th Int Conf Pattern Recognit, 2010, pp. 77–80.

11.

Witten

I.H.

, Frank

, Hall

M.A.

Data mining: Practical machine learning tools and techniques, 3rd ed. San Francisco: Morgan Kaufmann, 2011.

12.

Demsar

, Statistical comparisons of classifiers over multiple data sets, J Mach Learn Res7 (2006), 1–30.

13.

Schneider

, Cross validation, Carnegie Mellon School of Computer Science (1997). [Online]. Available: https://www.cs.cmu.edu/~schneideAut5/node42.html . [Accessed: 29-Jun-2017].

14.

Wang

, Neskovic

, Cooper

L.N.

, Improving nearest neighbor rule with a simple adaptive distance measure, Pattern Recognit Lett28(2) (2007), 207–213.

15.

Kuncheva

L.I.

, A bound on kappa-error diagrams for analysis of classifier ensembles, IEEE Trans Knowl Data Eng25(3) (2013), 494–501.

16.

Kuncheva

L.I.

, Combining partem classifiers: Methods and algorithms, 2nd ed. Hoboken. New Jersey: John Wiley & Sons, Inc, 2014.

17.

Kuncheva

L.I.

, Plumpton

C.O.

, Choosing parameters for random subspace ensembles for fMRI classification, in Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 5997 LNCS, 2010, pp. 54–63.

18.

Kuncheva

L.I.

, Rodríguez

J.J.

, Classifier ensembles with a random linear oracle, IEEE Trans Knowl Data Eng19(4) (2007), 500–508.

19.

Skurichina

, Duin

R.P.W.

, Bagging and the random subspace method for redundant feature spaces, inMultiple Classifier Systems, 2001.

20.

Skurichina

, Duin

R.P.W.

, Bagging, boosting and the random subspace method for linear classifiers, Pattern Anal Appl5(2) (2002), 121–135.

21.

Ruparel

N.H.

, Shahane

N.M.

, Bhamare

D.P.

, Learning from small data set to build classification model: A survey, in International Conference on Recent Trends in engineering & Technology. 2013, pp. 23–26.

22.

Entezari-Maleki

, Rezaei

, Minaei-Bidgoli

, Comparison of classification methods based on the type of attributes and sample size, J Converg Inf Technol4(3) (2009), 94–102.

23.

Sun

, Zhang

, An experimental evaluation of ensemble methods for EEG signal classification, Pattern Recognit Lett28(15) (2007), 2157–2163.

24.

T.K.

, The random subspace method for constructing decision forests, IEEE Trans Pattern Anal Mach Intell20(8) (1998), 832–844.

25.

Ren

, Zhang

, Suganthan

P.N.

, Ensemble classification and regression: Recent developments, applications and future directions, IEEE Comput Intell Mag11(1) (2016), 41–53.