# A Classification Methodology based on
Subspace Graphs Learning

Riccardo La Grassa, Ignazio Gallo, Alessandro Calefati  University of Essex,
School of Computer Science and Electronic Engineering,
Colchester, UK
Email<EMAIL_ADDRESS>University of Insubria,
Department of Theoretical and Applied Sciences,
Varese, Italy
Email: {rlagrassa, ignazio.gallo<EMAIL_ADDRESS>and Dimitri
Ognibene

###### Abstract

In this paper, we propose a design methodology for one-class classifiers using
an ensemble-of-classifiers approach. The objective is to select the best
structures created during the training phase using an ensemble of spanning
trees. It takes the best classifier, partitioning the area near a pattern into
$\gamma^{\gamma-2}$ sub-spaces and combining all possible spanning trees that
can be created starting from $\gamma$ nodes. The proposed method leverages on
a supervised classification methodology and the concept of minimum distance.
We evaluate our approach on well-known benchmark datasets and results obtained
demonstrate that it achieves comparable and, in many cases, state-of-the-art
results. Moreover, it obtains good performance even with unbalanced datasets.

##  I Introduction

In Machine Learning, the usage of multiple classifiers (ensemble-of-
classifiers) is a well-known technique employed to get a boost on performance
compared to single classifiers [1]. Even though it has been applied to
different scenarios with great results, the sensitivity of the system on long
tailed datasets still remains an open problem [2]. Another key aspect related
to ensemble learning is the margin [3]: several studies have shown that the
generalization ability of an ensemble of classifiers is strictly bound to the
distribution of its margins on the training examples [3, 4]. A good margin
distribution means that most examples have large margins [5]. Moreover,
ensemble margin theory is an effective way to improve the performance of
classification models [6]. This theory has been successfully applied in
unbalanced data sampling [7, 8, 9, 10], noise removal [11, 12, 13], instance
selection [14], feature selection [15] and classifier design [16, 17, 18]. In
decision-boundary classifiers, finding best margin settings is a hard task
because many parameters must be estimated in order to obtain a good
approximation of the final model. In recent works [19, 20, 21] many graph-
based models with optimization are introduced. These approaches combine graph
theory structures and Machine Learning, modelling the data within the
euclidean space. Their aim is to find a better boundary representation in
order to make more accurate predictions. In this paper, we developed a novel
approach to improve classification results. Main contributions of our paper
can be summarized as follows:

  * •

A design methodology for one-class classifiers capable of predicting the class
of a pattern using different partitions created from the surrounding area.

  * •

An objective function based on information extracted during the training phase
which selects the best partition among all possible $\gamma^{\gamma-2}$
combinations, built on top of most similar objects from a specific target.

##  II Related Work

In literature, there are plenty of works dealing with decision-boundary
models. For instance, Pekalska et al. [22] use a non-parametric model based on
one-class classifiers with a decision-boundary handled through a threshold. In
order to handle margins in the final model a threshold based on median (or a
parameter) of weighted-edge of minimum spanning tree is set to expand or
deflate the decision-boundary. They achieve good results also on long-tail
datasets. However, the high computational training time required to find the
minimum spanning tree in a high-dimensional dataset represents a drawback. In
[19] authors describe an interesting graph-based approach for one-class
classifiers with optimizator learning in a binary classification problem
finding the best partition exploiting a criterion based on mutual information
minimization. The idea is original and uses many complex concepts based on
graph theory and subspace learning. They don’t use an ensembles approach to
find out best partitions but provide a non-parametric model to estimate
information-theoretic quantities, such as entropy and divergence. The decision
regions are computed partitioning the k-nearest neighbour graph vertices
related to the components of the training set. The main issue of this approach
is the high computational time required caused by the computation of all
possible combinations.

Many recent state-of-the-art works employ a distance metric for
classification. Snell et al. [21] compares the euclidean distance between the
query example and the mean class of embedded support examples. Authors propose
this prototypical network for pattern recognition, where a classifier, given
few examples of training, creates a model able to achieve excellent results.
However, a weakness of this approach is about possible outliers within a class
that make the mean unstable and the problem of the overlapping patterns among
classes. Furthermore, considering only few examples or using $k$ object to
search the neighbours of an object can lead to bad partition of that area that
result in wrong classifications.

In [23] authors propose a mixed bagging model where each bootstrap have
varying degrees of hardness. Instance hardness is the probability that an
instance will be misclassified by a classifier built from other instances of
the dataset. Outliers, instance near the decision boundary and instances
surrounded by other instances from the opposite class are usually harder to
classify [24], they propose to remove the harder instances from the training
set to obtain a clear model, instead to use random bootstrap created through a
bagging method, they [23] create different subsets considering the hardness of
a group of instances. Our work, use a generator of spanning trees (we
calculate all possible spanning trees) near to the neighbours of an object to
classify, and create $\gamma^{\gamma-2}$ initial partitions. The selection
criterion to reduce these subsets is based on bagging approach and will be
widely discussed into proposal approach. For fair comparison, we use the same
$47$ publicly available datasets for binary classification problem, used in
[20, 23].

In [25], La Grassa et al., creates a binary model based on the combination of
two one-class classifiers. Authors propose three non-parametric approaches
that improve the model described in [22] showing good results in term of final
accuracy on many well-known datasets. More precisely, the first model creates
two minimum spanning trees, one per class, using weighted edges based on the
euclidean metric. However, strongly nonlinear datasets with unbalanced or high
dimensional data can be a serious problem in terms of accuracy or performance.
In order to improve this issues, [25] creates two models based on a
combination of two minimum spanning trees (or n-ary trees), created from the
neighbourhood of an instance to classify, instead of the whole training set,
avoiding data overlapping from different classes and partition different areas
to make the classification. In this way, authors, show better results in terms
of accuracy and computational time, also investigating the size of MST created
by neighbours. The main idea is very interesting but suffers from an issue:
the rule to adjust the boundary decision from neighbours is always the same
(MST) and that model does not discover new structures to improve the
performance, furthermore, as a non-parametric models, they do not extract
parameters from the training phase.

Major differences of our approach from existing ones are listed below:

  * •

We do not create a close partition to make predictions, but we use jointly a
spanning tree and a threshold. This information is useful to extract some
parameters during the training phase.

  * •

We use the information coming from the training phase to search similar
partitions around an instance to classify and combine decision boundaries to
make final predictions based on a ensemble method.

  * •

We use euclidean metric instead to use entropic information by spanning graph.

  * •

We compute all spanning trees starting to k-neighbours of an instance $x$ to
find partitions.

##  III The proposed approach

In this work, we introduce a model that extracts parameters from the training
phase that will be used during the test in order to increase the performance
in terms of final accuracy. The strength of our model is that it creates
$\gamma^{\gamma-2}$ different sub-spaces creating all possible spanning trees,
as described in [26], and selects the best structures that will be used during
the test, as shown in Fig. 2.

###  III-A Partition of the dataset

The classifier used in this work is the same used in [25], but we partition
different area to try to discover a new pattern able to recognize correctly
new instances.

We consider a binary classification task. Given a training set
$X=\\{x_{0},x_{1},\dots,x_{n-1}\\}$, where a generic $x_{i}$ is a vector
defined as:

$x=[a_{0},a_{1},\dots,a_{m-1}]$ (1)

$X$ is partitioned in two subsets $S$ and $(X-S)$. In turn $(X-S)$ is
partitioned in $X_{0}\bigcup X_{1}$ which respectively contain all the
elements with label $1$ and $-1$. Here, $|X|=n$ and $|x|=m$ are respectively
the size of training set and a generic instance $x\in X$.

###  III-B Creation of Spanning Trees

We use a discriminative function [25] (modified under certain condition, see
algorithm 4) $f_{1}({x)}\xrightarrow{}y$ capable of mapping a generic vector
$x$ into a label $y$. For each $s\in S$ and $X_{i}$ with $i\in\\{0,1\\}$, we
compute the euclidean distance and create the lists of pairs:

$\displaystyle D_{i}(s)=\\{(x_{j},\sqrt{(s-x_{j})^{2}})\mid x_{j}\in
X_{i},s\in S,s\neq x_{j}\\}$ (2)

The lists $D_{i}(s)$ are sorted in ascending order of distance, the second
element of the pair. For each element $s$ of the set, we take the $\gamma$
nearest elements, formally:

$\displaystyle V_{i}(s)=\\{d_{j,1}\ \mid d_{j}\in D_{i}(s),0\leq
j\leq\gamma\\}$ (3)

Starting from $V_{0}(s)$ and $V_{1}(s)$, we build the two corresponding sets
of spanning trees $H_{0}(s)$ and $H_{1}(s)$.

$\displaystyle H_{0}(s)=\\{h_{0},h_{1},\dots,h_{(\gamma^{\gamma-2})-1}\\}$ (4)
$\displaystyle
H_{1}(s)=\\{h^{\prime}_{0},h^{\prime}_{1},\dots,h^{\prime}_{(\gamma^{\gamma-2})-1}\\}$

where $h=(V,E)$ is a generic spanning tree, $V\in\\{V_{0}(s),V_{1}(s)\\}$ the
sets of nodes of its $\gamma$ nearest neighbours and $E$ the selected set
edge. For each $s\in S$, we take all pairs of spanning trees in $H_{0}(s)$ and
$H_{1}(s)$ and use the classifier described in [25] using a Bootstrap
Aggregating approach to select a subset of them (SPT_CD) for each label class
(see Fig. 1).

###  III-C Selection of best sub-graphs

We define two sets $\zeta_{0}$ and $\zeta_{1}$ that represent two dictionaries
used in the test phase to predict the labels. Each key of this dictionary is
an element of a class of the training set and values are all spanning trees
that performed a correct classification using the classifier proposed in [25].
For each element, we store also the euclidean distance from the spanning tree
and the weighted sum of all edges. Finally, the dictionary will contain a set
of triplets for each instance based on right classifications. More formally:

$\displaystyle\zeta_{0}=\\{(s,q)\mid s\in S,q=\Gamma(s,h,H_{1}(s))\ \forall
h\in H_{0}(s)\\}$ (5) $\displaystyle\zeta_{1}=\\{(s,q)\mid s\in
S,q=\Gamma(s,h,H_{0}(s))\ \forall h\in H_{1}(s)\\}$

where $\Gamma$ is the function $\Gamma:s\rightarrow q$:

$\Gamma(s,h,H_{j}(s))=\begin{cases}(h,d(s,h),\sum_{e\in h}w(e))&\quad\text{if
}C\geq 0\\\ \emptyset&\text{otherwise}\end{cases}$

$h$ is a specific spanning tree selected from all possible generated, $d$ is
the distance between $s$ to $h$ and the last element of the triplet represents
the weighted sum of every couple of spanning trees.

We use a counter $C$ to assign a label:

$C=\begin{cases}+1&\text{if SPT\\_CD}(H_{j}(s),h)=y\\\
-1&\text{otherwise}\end{cases}$ (6)

where $y$ is the label of s.

We sort $\zeta$ in ascending way using the already computed distances
$d(s,h)$. Finally, we use these dictionaries for the classification task
described in the next section.

Figure 1: Ensemble methodology used in the training phase to select spanning
trees that correctly classify an instance $x$. The information of these
spanning trees will be combined and used in an objective function to improve
the accuracy in the test phase. Blue points represent instances from class $1$
and green points represents class $-1$. In this example, we fix $\gamma=3$ to
create all spanning trees.

In Fig. 1, we show a toy example of the training phase, based on graphs
created considering k-neighbours of a specific object (see Eq. 4). We
highlight the ensemble approach applied in each row $A,B,C$ where a spanning
tree recognizes the pattern, while the other refuses it. If the number of
positive responses is greater than the number of rejections, we keep that
spanning tree. As described before, we are partitioning the neighbourhood of
an element to get a model (decision-boundary) able to make the right
predictions. For instance, in the first row the blue object is correctly
classified by the model generated with same label, but in the second row it is
refused leading to wrong prediction (see pseudocode 1).

###  III-D Classification Task

In test phase, we use Eq. 2 and define a vector $S^{*}$ as the set of
distances between a generic instance of test $z$ and each $x\in X$. For easier
understanding, we introduce the pseudocode 2.

Algorithm 1 Training step

1:for $s\in\mathcal{S}$ do

2: for $x\in\mathcal{X}_{0}$ do class 1

3: $euclidean\ distance\ list\leftarrow(||s-x||,x)$

4: Sort euclidean distant list

5: Take k-neighbours of s and create a complete graph with them

6: Generate all spanning trees

7: end for

8:end for

9:for $s\in\mathcal{S}$ do

10: for $x\in\mathcal{X}_{1}$ do class -1

11: $euclidean\ distance\ list=\leftarrow(||s-x||,x)$

12: Sort euclidean distant list

13: Take k-neighbours of s and create a complete graph with them

14: Generate all spanning trees

15: end for

16:end for

17:for $h\in\mathcal{H}_{0}(s)$ do

18: for $h^{\prime}\in\mathcal{H}_{1}(s)$ do

19: prediction SPT_CD(h, h’) (see eq. 6)

20: end for

21: majority vote ($C\geq 0$)

22: $dictionary_{0}$ $\leftarrow$ Save (h, distances (s, h), sum_weighted h)

23:end for

24:repeat line 17-21 for each $h^{\prime}\in H_{1}(s)\ and\ h\in H_{0}(s)$ and

25:$dictionary_{1}$ $\leftarrow$ Save (h’, distances (s, h’), sum_weighted h’)

Algorithm 2 Beta assignment (pre-test step)

1:Given Z be the test set

2:for $z\in\mathcal{Z}$ do

3: for $x\in\mathcal{X}_{0}$ do

4: $S^{*}\leftarrow(||z-x||,x)$

5: end for

6:end for

7:sorted(euclidean_distance)

8:for $i\in\mathcal{[}1,k]$ do

9: best_similarity= [$r[3]$ for r in $\zeta_{0}$($S^{*}[i][2])]$

10:end for

11:$weight\\_all\\_spt$ = sorted($best\\_similarity$)

12:$\theta_{0}$ = $|weight\\_all\\_spt|*alpha\\_best\\_sub\\_graph$

13:$\beta_{0}=weight\\_all\\_spt_{\theta_{0}}$

14:repeat line 2-13 considering for each $x\in X_{1}$, $\zeta_{1}$,
$\theta_{1}$ and find $\beta_{1}$

15:return $\beta_{0},\beta_{1}$

Algorithm 3 Classify($z$)

1:$\beta_{0},\beta_{1}$ = Call Algorithm 2: Beta assignment

2:N0=getK-Neighbours(z,X0,k)

3:T0=getSPTs(z,N0)

4:N1=getK-Neighbours(z,X1,k)

5:T1=getSPTs(z,N1)

6:$H_{0}^{*}$,$H_{1}^{*}$ = Sub-graphs selection(T0,T1) (see Equ 7)

7:for $h\in\mathcal{H}_{0}^{*}(s)$ do

8: for $h^{\prime}\in\mathcal{H}_{1}^{*}(s)$ do

9: SPT_CD(h, h’) with couple of spt’s returning a prediction $\pm 1$ see eq. 6

10: end for

11: majority vote ($C\geq 0$) for each $h\in H_{0}(s)$

12:end for

13:Final majority vote ($C\geq 0$) and assign prediction

Algorithm 4 SPT_CD (h, h’, z)

1:for $(x_{i},x_{j})\in E(h)$ do

2: if $0<=\frac{(x_{j}-x_{i})^{T}*(z-x_{i})}{||x_{j}-x_{i}||^{2}}<=1$ then

3:
$P_{e_{{}_{i_{j}}}}(z)=x_{i}+\frac{(x_{j}-x_{i})^{T}*(z-x_{i})}{||x_{j}-x_{i}||^{2}}*(x_{j}-x_{i})$

4: $d(z|e_{{}_{i_{j}}})\leftarrow||z-P_{e_{{}_{i_{j}}}}(z)||$

5: else

6: $d(z|e_{{}_{i_{j}}})\leftarrow
min\big{\\{}||z-x_{i}||,||z-x_{j}||\big{\\}}$

7: end if

8:end for

9:Repeat line 1-8 for spanning tree $h^{\prime}\ of\ H_{1}$

10:Find the boundary of spanning tree h of $H_{0}$ and h’ of $H_{1}$ based on
$\alpha$ parameter

11:$e(h)=(||e_{0}||,||e_{1}||,..||e_{n}||)$

12:$e(h^{\prime})=(||e_{0}||,||e_{1}||,..||e_{n}||)$

13:$\theta_{0}=||e_{(\alpha n)}||$

14:$\theta_{1}=||e_{(\alpha n)}||$

15:min dist0 = $min(d(z|e_{ij}))$

16:min dist1 = $min(d1(z|e_{ij}))$

17:make prediction

18:1 $\leftarrow$ if $d_{SPT\\_CD_{0}}(z|h)<=\theta$ and
$d_{SPT\\_CD_{1}}(z|h)>\theta_{1}$

19:-1 $\leftarrow$ if $d_{SPT\\_CD_{0}}(z|h)>\theta$ and
$d_{SPT\\_CD_{1}}(z|h)<=\theta_{1}$

20:if min dist0 $<=\theta$ and min dist1 $<=\theta_{1}$ then

21: knn weight1=order($d_{1}(z|u)$) and take $k_{1}$-elements

22: knn weight0=order($d_{0}(z|v)$) and take $k_{1}$-elements

23: euclidean distance vectors = (knn weight1 - knn weight0)

24: positive $=$ Count $n_{i}>0$ in euclidean distance vectors

25: negative $=$ Count $n_{i}<0$ in euclidean distance vectors

26: if negative $>=$ positive then

27: prediction $\leftarrow 1$

28: else

29: prediction $\leftarrow-1$

30: end if

31:end if

32:if min dist0 $>\theta$ and min dist1 $>\theta_{1}$ then

33: The approach is equal to lines [20-31]

34:end if

35:return

Furthermore, in Fig 1 we consider a boundary decision derived from the
weighted edge sum of a specific spanning trees (blue and green boundaries).
The reason we don’t consider only the edge couples among k-neighbours of
instance nearest to it (in training and test step) is to create a boundary
more detailed thanks to his neighbourhood. This task plays a crucial role in
the classification task because is able to model instances of the same classes
and to represents these as a unique decision boundary. Similarly, we apply the
Pseudocode 2 considering the euclidean distance between $z$ and each $x\in
X_{1}$ and $\zeta_{1}$ Then, we find all spanning trees considering the
neighborhood of $z$ using Eq. 2 and Eq. 3 to find Eq. 4. Finally, we choose
two subsets of spanning trees $\widetilde{H}_{0}\subseteq H_{0}$ of $z$ and
$\widetilde{H}_{1}\subseteq H_{1}$ of $z$ such that:

$\Delta\widetilde{H}_{z}(\beta,h)=\sum_{e\in h}{w(e)-\beta}$ (7)

where $w(e)$ is the weight for an edge of the considered spanning tree and
$\beta$ is the weighted sum of a spanning trees extracted considering a index
from $weighted\\_all\\_spt$ (see 2). We use a parameter $best\\_spt$ to
consider only a subset of distance-ordered $\Delta\widetilde{H}_{x}$. We
compute all minimum distances between an object with a specific sub-graph
according to the orthogonal projection of $x$ onto a line of sub-graph or
minimum Euclidean distance. Given a training set $X$, split into two sets
$X_{0},X_{1}$, we consider $\widetilde{H}_{0}$ and $\widetilde{H}_{1}$ as sets
of spanning trees.

From the previously computed $H^{*}_{0}$, $H^{*}_{1}$ sets, we create all
possible combinations and sum the number of correct classifications for a
pattern $z$. The label assigned is the one which obtained most votes according
to the bagging method and using SPT_CD as classifier. In other words, we
define a learning approach to find the best partitions through the $k$ nearest
neighbours of the target object. Let us define the objective function:

$\eta(h,H(s))=\frac{1}{1+\Delta\widetilde{H}_{x}(\beta,h)}$

that goes to $1$ when the variation is low and goes to $0$ when the
variability of data becomes higher. Therefore, the problem is to minimize the
following function:

$\min_{h,H(s)}\eta(h,H(s))$

Therefore, in the prediction phase, we use the same the classifier of [25]
under certain conditions (see Pseudocodes 2, 3, 4) considers two aspects:

  * •

Projection of point $x$ on a line defined by vertices ${x_{i},x_{j}}$

  * •

Minimum Euclidean distance between $(x,x_{i})$ and $(x,x_{j})$

The projection of $x$ is defined as follow:

$p_{e_{i,j}}(x)=x_{i}+\frac{(x_{j}-x_{i})^{T}(x-x_{i})}{||x_{j}-x_{i}||^{2}}(x_{j}-x_{i})$

if $p_{e_{i,j}}(x)$ lies on the edge $e_{i,j}$= ($x_{i}$,$x_{j}$), we compute
$p_{e_{i,j}}(x)$ and the Euclidean distance between $x$ and $p_{e_{i,j}}(x)$,
more formally:

$0<=\frac{(x_{j}-x_{i})^{T}(x-x_{i})}{||x_{j}-x_{i}||^{2}}<=1$

then

$d(x|e_{i,j})=||x-p_{e_{i,j}}(x)||$

Otherwise we compute the Euclidean distance of $x$ and pairs ($x_{i}$,
$x_{j}$), precisely:

$d(x|e_{i,j})=min(||x-x_{j}||,||x-x_{i}||)$

Then, a new instance $x$ is recognized from a spanning tree if it lies within
the boundary, otherwise, the object is considered as outlier. The decision
whether an object is recognized by classifier or not is based on the threshold
of the shape created in this phase, more formally:

$d_{h}(x|X)<=\theta$

The threshold $\theta$ is a parameter used to assign the boundary dimension of
a spanning tree. Then, given $\hat{e}=(||e_{1}||,||e_{2}||,...,||e_{n}||)$ as
an ordered edge weights values, we define $\theta$ as $\theta=||e_{[\alpha
n]}||$, where $\alpha\in[0,1]$. For instance, with $\alpha=0.5$, we assign the
median value of all edge weights of the spanning tree.

Figure 2: Pre-test step: The model computes all euclidean distance between the
instance to classify and other instances of the datasets. Then, it takes the
information of instances nearer to an instance $z$. Finally, we extract beta
value, using different parameters described in II. Figure 3: Training step:
For each instance in the training set, the model uses Euclidean distance than
other instances into datasets split per classes. The model generates all
possible spanning tree and applies an ensemble method based on majority vote
using the same classifier in [25] on different decision boundaries. Finally,
the model saves the best-spanning trees, weighted sum of them and euclidean
distance between instance and the spanning trees. Figure 4: Test step: For
each new instance, the model computes all euclidean distance with train split
per classes and generate all possible spanning trees from his neighbourhood.
Then, we use the parameters extracted in the training step to minimize an
objective function to select a subset of spanning trees generated. Last, we
apply an ensemble method based on majority vote to classify the instance.

##  IV Datasets

To evaluate the effectiveness of our approach, we tested it on many well-known
datasets. As can be seen from Table I, there is huge variability in terms of
the number of features for each dataset. Another aspect which makes
experiments more challenging is the displacement of patterns between classes.

TABLE I: Number of features, instances and positive-negative samples for all the datasets used in our experiment. Datasets (Acronyms) | Features | Instances | pos-neg
---|---|---|---
Arcene (A) | 10000 | 100 | 44-56
Gisette (G) | 5000 | 6000 | 3000-3000
Hill (HL) | 101 | 606 | 305-301
Sonar (S) | 60 | 208 | 97-111
Pima (PM) | 8 | 768 | 268-500
Banana (BN) | 2 | 5300 | 2924-2376
Banknote authentication (BK) | 4 | 1372 | 762-610
Breast cancer ws Pr (BC-P) | 32 | 198 | 151-47
Liver (L) | 6 | 345 | 145-200
Breast cancer ws (BW) | 9 | 699 | 458-241

##  V Experiments

Performance of $SPT\\_CD$ is evaluated using well-known metrics: Sensitivity,
Specificity, Precision, F1 score, AUC score and accuracy. In addition to these
measures, we computed the ROC curve. In our experiments, we employed a 5-Fold
Cross Validation approach and computed the average testing on different
parameters described in II. The ratio between train and test sets is 80% and
20 % respectively. For a deeper evaluation of the proposed approach, we used
also different ratios, from 30% to 90% of the training split 6, to measure the
impact of the training size on the speed of training and on the final
accuracy. In all our experiments we have not applied any feature selections or
deep feature extraction models on datasets. In Table III we compare our model
in terms of AUC score and many classifiers well-known into the literature on
$5$ different datasets. Results are comparable with the state-of-the-art and,
in some cases, they outperform it. Furthermore, we compares different metrics
such as sensitivity, specificity, precision and final accuracy on three
variations of Multi-layer Perceptron (Table IV). We highlight the best
performance of our model than neural networks reported. Tables V and VI show
more comparisons in terms of final accuracy, reporting some well-known
classifiers and ensemble methods.

TABLE II: Parameters list Alpha | Threshold used to find beta value in $weight\\_all\\_spt$ |  |  |  |
---|---|---|---|---|---
Gamma | Number of neighbor nodes |  |  |  |
Best_spt | Number of best spt to consider (in test phase) |  |  |  |
k_neighbours | Number of instances (into training set) nearest to z |  |  |  |
K | Number of neighborhood nodes to consider when |  |  |  |
| all classifiers refuse or accept z |  |  |  |
TABLE III: AUC of suggested classifiers and other one-class classifiers in [19][27]. In the first row average results by our model on 5-fold cross validation. The highest score in each row is marked in Bold | Classifiers | BC-P | BW | L | S | PM
---|---|---|---|---|---|---
Our work | SPT_CD | 0.646 | 0.951 | 0.655 | 0.841 | 0.666
[19] | EOCC-MI | 0.569 | 0.989 | 0.481 | - | -
EOCC-1 | 0.554 | 0.99 | 0.461 | - | -
EOCC-2 | 0.585 | 0.989 | 0.536 | - | -
[27] | Gauss | 0.591 | 0.823 | 0.586 | 0.603 | 0.705
MoG | 0.511 | 0.785 | 0.607 | 0.663 | 0.674
Näıve Parzen | 0.538 | 0.965 | 0.614 | 0.67 | 0.679
Parzen | 0.586 | 0.723 | 0.59 | 0.681 | 0.676
k-Means | 0.536 | 0.846 | 0.578 | 0.56 | 0.659
1-NN | 0.595 | 0.694 | 0.59 | 0.682 | 0.667
k-NN | 0.595 | 0.694 | 0.59 | 0.682 | 0.667
Auto-encoder | 0.548 | 0.384 | 0.564 | 0.611 | 0.598
PCA | 0.574 | 0.303 | 0.549 | 0.564 | 0.587
SOM | 0.523 | 0.79 | 0.596 | 0.655 | 0.692
MST_CD | 0.611 | 0.765 | 0.58 | 0.671 | 0.659
k-Centres | 0.584 | 0.715 | 0.537 | 0.6 | 0.606
SVDD | 0.498 | 0.7 | 0.47 | 0.589 | 0.577
MPM | 0.053 | 0.694 | 0.587 | 0.59 | 0.656
LPDD | 0.539 | 0.8 | 0.564 | 0.639 | 0.668
TABLE IV: Comparison in terms of sensitivity, specificity, precision and accuracy between our model (SPT_CD) and results of three variations of Multilayer Perceptron in [28]. Acronyms in this Table are defined in I. Datasets | Method | Sens | Spec | Pr | Acc
---|---|---|---|---|---
BN | SPT_CD | 85.29 | 85.29 | 85.1 | 85.3
CMLP | 71.97 | 71.97 | 80.09 | 65.55
SGMLP | 72.54 | 72.54 | 80.71 | 69.65
CWMLP | 77.08 | 77.08 | 78.95 | 73.42
BW | SPT_CD | 95.16 | 95.16 | 94.46 | 95.27
CMLP | 74.88 | 72.13 | 70.93 | 78.11
SGMLP | 76.25 | 76.25 | 76.25 | 77.76
CWMLP | 77.32 | 77.22 | 77.02 | 78.7
BK | SPT_CD | 100 | 100 | 100 | 100
CMLP | 90 | 90 | 90 | 90
SGMLP | 100 | 100 | 100 | 100
CWMLP | 100 | 100 | 100 | 100
TABLE V: 5-fold Cross-Validation accuracy results. Results obtained with our model (SPT_CD) are compared with results published in [29] on the same dataset. | Krakovna et al. [29] and La Grassa et al. [25] | Our model
---|---|---
Dataset | Bart | c5.0 | Cart | Lasso | LR | NB | RF | SBFC | SVM | TAN | CD | CD_GP | N-ary | SPT_CD
A | 71.6 | 66 | 63 | 65.6 | 52 | 69 | 71.8 | 72.2 | 72 | - | 79.6 | 77.7 | 80.3 | 84
TABLE VI: 5-fold Cross-Validation accuracy results on different datasets. Results obtained with our model (SPT_CD) are compared with the results of different ensemble methods published. | Abpeykar et al. [30] and La Grassa et al. [25] | Our model
---|---|---
Dataset | AdaB. | Bagg. | Dagg. | LogitB. | Mod. | Decor. | Grad. | Mt.B | Stack.C | CD | CD_GP | N-ary | SPT_CD
A | 79.5 | 82.5 | 74.5 | 85.5 | 86.0 | - | 56.0 | 80.0 | 56.0 | 79.6 | 77.7 | 80.3 | 84.0
S | 71.6 | 76.9 | 69.7 | 79.3 | 70.6 | 84.1 | 53.3 | 74.5 | 53.3 | 85.4 | 85.2 | 87.3 | 84.1
HL | 50.4 | 50.2 | 50.4 | 50.4 | - | - | 50.4 | 50.4 | 50.4 | 58.1 | 57.9 | 61.1 | 57.5
G | 88.9 | 75.0 | 82.2 | 89.4 | - | 82.2 | 48.1 | 82.7 | 48.1 | 96.8 | - | - | 97.2

Figure 5: Average accuracy (dot) on 5-fold cross-validation on different train
size of the Breast cancer Wisconsin datasets. Vertical lines represent the
upper (max accuracy) and lower (min accuracy) bound of 5-fold.

Figure 6: Average accuracy (dot) on 5-fold cross-validation on different train
size of the Arcene datasets. Vertical lines represent the upper (max accuracy)
and lower (min accuracy) bound of 5-fold.

##  VI Conclusion and Future Work

Multiclass problems can be solved by combining the decision boundary of many
one-class classifiers trained on different classes. Finding the best
partitions is a hard task but necessary to finalize the classification
objective. In this work, the methodology proposed has the aim to find out best
partitions with ensemble method from the neighbourhood of an instance, based
on subspace graph in training step and use this information as parameter in
the objective function to improve final accuracy. The presented results are
competitive with classical classifiers and show a boost in many of them even
when we use a few data to train the model. Against, it is computationally
expensive to find the right combination of parameters and set up $\gamma$
value greater than 4. A one-class classifier is trained using only one class
and all rejected object are considered as outliers class. Our method, as a
combination of two one-class classifiers, does not consider outliers and all
instances will be classified. Future research efforts will focus on adapting
the proposed approach to multi-class problems. We will also apply the proposed
approach to large scale datasets to evaluate the accuracy and time required.
Furthermore, we want to use deep feature extraction models and compare our
work with well-known models typically used in computer vision tasks. In order
to reach these goals, we will focus on improving the computational complexity,
modifying the algorithm and making it parallelizable. Finally, we will
evaluate the effectiveness of using different distance metrics and objective
functions.

## References

  * [1] I. Gallo, A. Calefati, and S. Nawaz, “Multimodal classification fusion in real-world scenarios,” in _2017 14th IAPR International Conference on Document Analysis and Recognition (ICDAR)_ , vol. 5. IEEE, 2017, pp. 36–41.
  * [2] J. Błaszczyński and J. Stefanowski, “Neighbourhood sampling in bagging for imbalanced data,” _Neurocomputing_ , vol. 150, pp. 529–542, 2015.
  * [3] R. E. Schapire, Y. Freund, P. Bartlett, W. S. Lee _et al._ , “Boosting the margin: A new explanation for the effectiveness of voting methods,” _The annals of statistics_ , vol. 26, no. 5, pp. 1651–1686, 1998.
  * [4] D. M. Tax and R. P. Duin, “Using two-class classifiers for multiclass classification,” in _Object recognition supported by user interaction for service robots_ , vol. 2. IEEE, 2002, pp. 124–127.
  * [5] Q. Hu, L. Li, X. Wu, G. Schaefer, and D. Yu, “Exploiting diversity for optimizing margin distribution in ensemble learning,” _Knowledge-Based Systems_ , vol. 67, pp. 90–104, 2014.
  * [6] I. Cantador and J. R. Dorronsoro, “Boosting parallel perceptrons for label noise reduction in classification problems,” in _International Work-Conference on the Interplay Between Natural and Artificial Computation_. Springer, 2005, pp. 586–593.
  * [7] X. Fan, K. Tang, and T. Weise, “Margin-based over-sampling method for learning from imbalanced datasets,” in _Pacific-Asia Conference on Knowledge Discovery and Data Mining_. Springer, 2011, pp. 309–320.
  * [8] Y. Qian, Y. Liang, M. Li, G. Feng, and X. Shi, “A resampling ensemble algorithm for classification of imbalance problems,” _Neurocomputing_ , vol. 143, pp. 57–67, 2014.
  * [9] T.-Y. Liu, “Easyensemble and feature selection for imbalance data sets,” in _2009 International Joint Conference on Bioinformatics, Systems Biology and Intelligent Computing_. IEEE, 2009, pp. 517–520.
  * [10] W. Feng and W. Bao, “Weight-based rotation forest for hyperspectral image classification,” _IEEE Geoscience and Remote Sensing Letters_ , vol. 14, no. 11, pp. 2167–2171, 2017.
  * [11] W. Feng, “Investigation of training data issues in ensemble classification based on margin concept: application to land cover mapping,” Ph.D. dissertation, Université Michel de Montaigne-Bordeaux III, 2017.
  * [12] W. Feng, S. Boukir, and L. Guo, “Identification and correction of mislabeled training data for land cover classification based on ensemble margin,” in _2015 IEEE International Geoscience and Remote Sensing Symposium (IGARSS)_. IEEE, 2015, pp. 4991–4994.
  * [13] W. Feng and S. Boukir, “Class noise removal and correction for image classification using ensemble margin,” in _2015 IEEE International Conference on Image Processing (ICIP)_. IEEE, 2015, pp. 4698–4702.
  * [14] E. Marchiori, “Class conditional nearest neighbor for large margin instance selection,” _IEEE Transactions on Pattern Analysis and Machine Intelligence_ , vol. 32, no. 2, pp. 364–370, 2009.
  * [15] M. Alshawabkeh, “Hypothesis margin based weighting for feature selection using boosting: theory, algorithms and applications,” Ph.D. dissertation, Northeastern University, 2013.
  * [16] W. Gao and Z.-H. Zhou, “The kth, median and average margin bounds for adaboost,” _Computing Research Repository - CORR_ , 01 2010.
  * [17] L. Li, B. Zou, Q. Hu, X. Wu, and D. Yu, “Dynamic classifier ensemble using classification confidence,” _Neurocomputing_ , vol. 99, pp. 581–591, 2013\.
  * [18] Z. Xie, Y. Xu, Q. Hu, and P. Zhu, “Margin distribution based bagging pruning,” _Neurocomputing_ , vol. 85, pp. 11–19, 2012.
  * [19] L. Livi and C. Alippi, “One-class classifiers based on entropic spanning graphs,” _IEEE transactions on neural networks and learning systems_ , vol. 28, no. 12, pp. 2846–2858, 2016.
  * [20] I. Jeong, D. G. Kim, J. Y. Choi, and J. Ko, “Geometric one-class classifiers using hyper-rectangles for knowledge extraction,” _Expert Systems with Applications_ , vol. 117, pp. 112–124, 2019.
  * [21] J. Snell, K. Swersky, and R. Zemel, “Prototypical networks for few-shot learning,” in _Advances in Neural Information Processing Systems_ , 2017, pp. 4077–4087.
  * [22] P. Juszczak, D. M. Tax, E. Pe, R. P. Duin _et al._ , “Minimum spanning tree based one-class classifier,” _Neurocomputing_ , vol. 72, no. 7-9, pp. 1859–1869, 2009.
  * [23] A. Kabir, C. Ruiz, and S. A. Alvarez, “Mixed bagging: A novel ensemble learning framework for supervised classification based on instance hardness,” in _2018 IEEE International Conference on Data Mining (ICDM)_. IEEE, 2018, pp. 1073–1078.
  * [24] M. R. Smith, T. Martinez, and C. Giraud-Carrier, “An instance level analysis of data complexity,” _Machine learning_ , vol. 95, no. 2, pp. 225–256, 2014\.
  * [25] R. La Grassa, I. Gallo, A. Calefati, and D. Ognibene, “Binary classification using pairs of minimum spanning trees or n-ary trees,” in _Computer Analysis of Images and Patterns_ , M. Vento and G. Percannella, Eds. Cham: Springer International Publishing, 2019, pp. 365–376.
  * [26] R. C. Read and R. E. Tarjan, “Bounds on backtrack algorithms for listing cycles, paths, and spanning trees,” _Networks_ , vol. 5, no. 3, pp. 237–252, 1975.
  * [27] “Results on one-class classification”,” http://homepage.tudelft.nl/n9d04/occ/index.html, last assessed: 2016-4-6. [Online].
  * [28] U. Iqbal, R. Ghazali, M. F. Mushtaq, and A. Kanwal, “Functional expansions based multilayer perceptron neural network for classification task,” _Computación y Sistemas_ , vol. 22, no. 4, 2018.
  * [29] V. Krakovna, J. Du, and J. S. Liu, “Interpretable selection and visualization of features and interactions using bayesian forests,” _Statistics and Its Interface_ , vol. 11, pp. 503–513, 2018.
  * [30] G. M. Abpeykar S. and Z. H., “Ensemble decision forest of rbf networks via hybrid feature clustering approach for high-dimensional data classification,” _Computational Statistics and Data Analysis_ , 2019.