Searching for Optimal Classi er Using a Combination of Cluster Ensemble and Kernel Method

Abstract

This work introduces a supervised classi cation algorithm based on a combination of ensemble clustering and kernel method. The main idea of the algorithm lies behind the expectation that the ensemble clustering as a preliminary stage would restore more accurately metric relations between data objects under noise distortions and existence of complex data structures, eventually rising the overall classi cation quality. The algorithm consists in two major steps. On the rst step, the averaged co-association matrix is calculated using cluster ensemble. It is proved that the matrix satis es Mercer's condition, i.e., it de nes symmetric non-negative de nite kernel. On the next step, optimal classi er is found with the obtained kernel matrix as input. The classi er maximizes the width of hyperplane's separation margin in the space induced by the cluster ensemble kernel. Numerical experiments with arti cial examples and real hyperspectral image have shown that the proposed algorithm possesses classi cation accuracy comparable with some state-of-the-art methods, and in many cases outperforms them, especially in noise conditions.

Keywords

• Kernel based learning matrix
• Support vector machine
• Cluster ensemble

-

Co-association Kernel based learning and collective decision making (ensemble approach) stay among top trends in uencing the progress in machine learning.

Kernel (potential) function de nes an implicit non-linear mapping of the initial feature space into a new space with larger or even in nite dimensionality.

Copyright c by the paper's authors. Copying permitted for private and academic purposes.

In: S. Belim et al. (eds.): OPTA-SCL 2018, Omsk, Russia, published at http://ceur-ws.org In the new space, initial con gurations of patterns are transformed (with so called \kernel trick") into the structures which often are more compact and linearly separable. To calculate distances or average values in the new space, it is not necessary to determine coordinates of the transformed points; it is enough to only know the values of kernel function. Such methods as Support Vector Machine (SVM), Kernel Fisher Discriminant (KFD), Kernel K-means, Kernel Principal Component Analysis, etc., are based on this methodology [ 1 ]. The decision function is de ned by a linear combination of kernels determining distances to a number of sample elements. In the existing algorithms, the kernel matrix is usually calculated with use of the Euclidean distance between objects in the input feature space.

Ensemble approach exploits the idea of collective decision making by usage of algorithms working on di erent settings such as subsets of parameters, subsamples of data, combinations of features, etc. Ensemble based systems usually yield robust and e ective solution, especially in case of uncertainty in data model or when it is not clear which of algorithm's parameters are most appropriate for a particular problem. As a rule, properly organized ensemble (even composed of \weak" predictors) signi cantly improves the overall quality of decisions [2{6].

Cluster analysis aims at determining a partition of a dataset on natural clusters using objects descriptions and a certain criterion of compactness-remoteness of groups. Ensemble clustering is one of the successful implementations of the collective methodology. There are a number of major techniques for constructing the ensemble decision [7{9]. Following evidence accumulation approach [ 10 ], the clustering partition is found in two steps. On the rst step, a number of clustering results are obtained (for example, by usage of K-means for di erent number of clusters or random initializations of centroids). For each partition variant, the co-association boolean matrix is calculated. The matrix elements correspond to the pairs of data objects and indicate if the pair belong to the same cluster or not. On the second step, the averaged co-association matrix is calculated over all variants; it is used for constructing the resultant partition: the matrix elements are considered as distances or similarity measures between data points and any clustering algorithm designed for such type of input information is applied to get the nal clustering partition.

This paper introduces an algorithm of classi er construction using a combination of ensemble clustering and kernel based learning. The proposed methodic is based on the hypothesis that the preliminary ensemble clustering allows one to restore more accurately metric relations between objects under noise distortions and existence of complex data structures. The obtained kernel matrix depends on the outputs of clustering algorithms and is less noise-addicted than conventional similarity matrix. Clustering with su ciently large number of clusters can be viewed as Learning Vector Quantization methodic [ 11 ] known for lowering the average distortion in data. These reasons, as supposed, eventually result in an increase of recognition accuracy of the combination. The outline of the method is as follows. First of all, a number of variants of a dataset partitioning are obtained with base clustering algorithm. Then the averaged co-association matrix is calculated, where the averaging is performed with weights dependent on the obtained ensemble's characteristics. The matrix elements play the role of similarity measures between objects in the new feature space induced by implicit non-linear transformation of input features. On the second stage, a kernel classi er is found by usage of the obtained co-association matrix as input kernel matrix (we used SVM in numeric experiments).

The aim of this paper is to verify the practicability of the suggested methodology with theoretical analysis and experimental evaluation.

There are two main types of cluster ensembles: homogeneous (when a single algorithm partitions data by varying its working settings) and heterogeneous ones (which includes a number of di erent algorithms). Heterogeneous cluster ensemble was considered in [ 12, 13 ], where methods for its weights optimization were suggested. Homogeneous cluster ensemble was investigated in [ 14 ] with use of the probabilistic model assuming the validity of some key assumptions. In the current work, we follow a scheme of homogeneous ensemble and perform theoretical investigation of some of its properties using less restrictive assumptions.

The rest of the paper is organized as follows. Section 2 brie y overviews related works. Section 3 introduces necessary notions in the eld of kernel based classi ers and ensemble clustering. In The Next Section We Prove That the Weighted Co-association Matrix obtained with cluster ensemble is a valid kernel matrix. The proposed algorithm of classi er design KCCE is also presented and some details of the optimization procedure are given. Section 5 provides a probabilistic analysis of the ensemble clustering stage. The Final Section Describes the Results of Numerical Experiments with KCCE. The conclusion summarizes the work and describes some of the future plans. 2

Related Works

The idea of combining cluster analysis and pattern recognition methods is rather well-known in machine learning [ 15 ]. There are several natural reasons for the combination: { Cluster analysis can be viewed as a tool for data cleaning to eliminate outliers or noisy items from learning sample [ 16 ]. { Joint learning and control sample provides additional information on data distribution which can be utilized to improve the classi er performance (this way of reasoning is sometimes called the trunsductive learning ). For example, the authors of [ 17 ] make a partition of the united sample into clusters which are used to design more accurate decision rule. { In semi-supervised learning context [ 18 ], usage of small amount of labeled data in combination with a large volume of unlabeled examples is useful for constructing more e cient classi er.

A connection between cluster analysis and kernel based classi ers was established in [ 19 ], where cluster kernels were proposed implementing the cluster assumption in the form: \two points are likely to have the same class label if there is a path connecting them passing through regions of high density only". Three types of kernels were presented: kernels from mixture models, random walk kernels and kernels induced by a cluster representation with spectral clustering [ 20 ].

The usage of a certain similarity function (which not necessarily possesses positive semi-de niteness property) instead of kernel function was proposed in [ 21 ]. A classi er is nding in two stages. On the rst stage, the choice of some \supporting" points is performed. With regard to these points, according to the de ned similarity function, initial observations are mapped into metric space of small dimensionality. On the second stage, a linear classi cation rule is constructed in the new space implementing SVM-type algorithm to nd the classication margin of maximum width.

Following the idea of combining cluster ensembles and supervised classi cation, the authors of [ 22 ] construct new feature space by usage of the degree of belonging of objects to clusters in the obtained variants of data partitioning with cluster ensemble. The transomed feature matrix is utilized as input training set for classi cation using conventional techniques such as Decision Tree, Naive Bayes, K-nearest neighbors, Neural Network. The method showed its e ectiveness in comparison with a number of state-of-the-art procedures.

Unlike the above mentioned works, we apply completely di erent combination scheme based on the notion of kernel function. 3

Basic Preliminaries

Suppose we are given a data set A = fa1; : : : ; aN g consisting of N objects (examples), A , where is a statistical population. Information about the objects is presented in the form of a feature matrix Z = (X; Y) = (xi; yi)iN=1, where xi = (xi;1; : : : ; xi;d) 2 Rd is input feature vector (d is feature space dimensionality), xi;m = Xm(ai) is a value of feature Xm for object ai; yi is a class label attributed to ith object, i = 1; : : : ; N . For binary classi cation task we assume yi 2 f 1; 1g. In multi-class classi cation problem, an arbitrary nite set of unordered class labels is de ned.

On the basis of the information about A (training sample), it is required to nd a classi er (predictor, decision function) y = f (x), optimal in some sense, e.g. having minimal expected losses for unseen examples. To examine the performance of the classi er, it is possible to use test sample B = fb1; : : : ; bNt g, B described with feature matrix Xtest. We shall presume that the objects in A and B are independent and identically distributed (iid), that is, the sets are collected on the basis of independent random choice of objects from without replacement following a xed distribution.

Kernel classi ers [ 1 ] make use of the notion of kernel function K(xi; xj ) 0, where K is a kind of similarity measure between two data points. Linear kernel classi er exempli es a binary decision function introduced within this approach: f (x) = sign( P iyiK(x; xi)); where sign is the sign function, 1; : : : ; N are xi2X non-negative weights. A number of methods for determining weights (Support Vector Machine, Kernel Fisher Discriminate, etc.) exist.

For the SVM classi er, the weights are found as a solution to the constrained quadratic optimization problem of maximizing the width of the margin (separation region) between two classes in Hilbert's space induced by kernel mapping.

KFD is a kernelized version of Fisher's linear discriminant analysis (LDA) which aims at nding such a position of a straight line in feature space, for which the object's projections are separated as better as possible according to a functional minimizing within-class scatter of projections and maximizing between-class distance.

The general multi-class classi cation problem can be solved by the application of a series of binary classi cation tasks for SVM or KFD, e.g., one-againstall, one-against-one or Error Correcting Output Codes (ECOC) schemes [ 23 ].

Kernel k-NN classi er assigns data points according to k Nearest Neighbor rule, where neighboring points are determined with respect to similarity measure de ned by kernel function.

Consider a scheme of homogeneous cluster ensemble. Let a clustering algorithm be running a number of times under di erent conditions such as initial cluster centroids coordinates, subsets of features, number of clusters or other parameters. The joined data set A [ B is the input for the algorithm (if test sample is unavailable in the moment of classi er design, then set A is the input). In each lth trial, algorithm creates a partition of the given dataset composed of Kl clusters, where l = 1; : : : ; L, and L is the given number of runs. For each variant of clustering, we de ne the evaluation function l (cluster validity index or diversity measure). We suppose that the values are scaled to non-negative quantities and the better is the found variant according to certain criterion, the larger is the quantity.

For a pair of di erent data objects (ai; aj ) 2 A [ B, we de ne the value hl(i; j) = I[ l(ai) = l(aj )]; where I[ ] is the indicator function: I[true] = 1; I[f alse] = 0; l(a) is the cluster label assigned by algorithm to object a in lth run. Ensemble matrix M stores the results of clusterings: M = ( l(ai))li==11;;::::::;;LN+Nt .

The averaged co-association matrix H = (h(i; j)) is de ned over all gener

L ated variants: h(i; j) = P ul hl(i; j); where the standardized weights u1; : : : ; uL l=1 indicate the quality of clustering for the given variants: ul = P l0 l ; l = 1 : : : ; L: 4

Kernel Classi cation with Averaged Co-association

Matrix

Let K(x; x0): D D ! R be a symmetric function, either continuous or having a nite domain, D be a closed subset in Rd. According to Mercer's theorem, K(x; x0) is kernel function (i.e., it de nes inner product in some metric space), if and only if for any nite set of m points fxigim=1 in D and real numbers fcigim=1, matrix K = (K(i; j)) = (K(xi; xj ))im;j=1 is nonnegativity de nite: m P cicj K(i; j) 0: Let us prove the following i;j=1 Proposition 1. The averaged co-association matrix satis es Mercer's condition.

Proof. The symmetric property of H is obvious. The domain of H is a nite set A [ B. Let Ir(l) be the set of indices for data points belonging to rth cluster in m lth variant of partitioning. Then for any fcigim=1 it holds true: P cicj h(i; j) = i;j=1 m L L P cicj P ul hl(i; j) = P ul i;j=1 l=1 l=1

Pm ci cj hl(i; j) = PL ul PKl P i;j=1 l=1 k=1 i;j2Ik(l)

cicj

L Kl = P ul P ( P ci)2 l=1 k=1 i2Ik(l) 0:

From this property, it follows that the averaged co-association matrix is a valid kernel matrix and can be used in kernel based classi cation methods.

Let us describe the main steps of the proposed algorithm KCCE (Kernel Classi cation with Cluster Ensemble).

Algorithm KCCE.

Input: training data set Z = (X; Y) = (xi; yi), i = 1; : : : ; N ; test data set Xtest; L: number of runs for base clustering algorithm ;

: set of allowable parameters (working conditions) of .

Output: decision function y = f (x); class labels attributed to Xtest.

Steps: 1. Generate L variants of clustering partition of X [ Xtest using algorithm with randomly chosen working parameters; calculate evaluation functions and weights; 2. For each pair (xi; xj ) 2 X [ Xtest (i 6= j), if the pair are assigned to the same group in lth variant, then hl(i; j) := 1, otherwise hl(i; j) := 0; 3. Calculate the averaged co-association matrix H; 4. Find decision function with the preset type of kernel classi er and matrix H; 5. Classify test sample Xtest using the found decision function and matrix H; end.

In this paper, we use K-means as base clustering algorithm, however it is possible to apply any other clustering technique. As the kernel classi er, we utilize soft margin version of SVM which aims at optimizing the following objective

min i ! w;b; i where w is normal vector to the separating hyperplane in the space induced by kernel, b is hyperplane's bias, i is a penalty imposed on ith example violating the separation margin, C 0 is soft margin parameter. By solving for the Lagrangian dual, one obtains the quadratic optimization problem: W ( ) = X

i i 1 X 2 i;j i j yiyj K(xi; xj ) ! max subject to: P iyi = 0; 0 i C; i = 1; : : : ; N;

i where K( ; ) is kernel function. One may substitute this kernel by the cluster ensemble kernel H and get:

W ( ) = X

i i 1 X 2 i;j i j yiyj X ul hl(i; j) l = X i i l

Kl 1 X ul X X 2 k=1 i;j2Ik(l) i j yiyj = X

i i 1 X ul 2 l

Kl X( X k=1 i2Ik(l) iyi)2:

We search for the optimal solution using Sequential Minimal Optimization (SMO) method [ 24 ]. A point xi for which i > 0 is called support vector. The bias term b is determined by any support vector xi : b = yi P yi iH(xi; xi ): i

The decision for xj 2 Xtest is calculated using the found multipliers: f (xj ) = sign(P yi iH(xj ; xj ) + b):

i

One can see that there is no need to store the kernel matrix: the objective function is computed using the ensemble matrix M kept in memory. Therefore KCCE has linear storage complexity with respect to data size. The time complexity depends on the type of utilized clustering and kernel algorithms and is linear with respect to data matrix dimensionality in case of K-means and SVM-SMO.

In some classi cation tasks, test data are unavailable in the moment of classi er design. To nd the decision function f (x) for any new feature vector x, this observation should be attributed to clusters according to the obtained partition variants. It is possible to make this assignment using cluster centroid coordinates which can be stored in memory during the implementation of Step 1 in KCCE. The observation is assigned to the nearest centroid's label for each clustering variant.

On the Reliability of Ensemble Clustering

The suggested combined method includes two main phases: ensemble clustering and kernel classi er design. An important question is the reliability of the rst step: are the elements of the obtained similarity matrix H t true relationships between object pairs (e.g., belonging to same or di erent classes)? To study this problem, we use the methodology described in [ 12, 14, 13 ].

In the clustering process, true class labels are unavailable. Following a probabilistic approach, one may suppose that data sample is composed of a nite number of components. A latent groundtruth variable Y 0 de nes the class number to which an object belongs. Denote v(i; j) = I[ Y 0(ai) = Y 0(aj ) ]; (1)

P ul > P l:hl(i;j)=1 l:hl(i;j)=0 decision for ai and aj following weighted voting procedure.

For a pair (ai; aj ), their ensemble's margin is de ned as where ai and aj are arbitrary objects from input sample. This quantity determines the true status of the pair (i.e., if ai and aj indeed belong to the same class).

Function c(i; j) = I [ ul] will be called the ensemble mg(i; j) = f

X

ul l:hl(i;j)=v(i;j)

X l:hl(i;j)6=v(i;j) ulg and can be rewritten in the form: mg(i; j) =

L X ul fI[hl(i; j) = v(i; j)] l=1

I[hl(i; j) 6= v(i; j)]g : This value indicates to what extend the number of right decisions for (ai; aj ) exceed the number of wrong ones. Evidently, it equals: mg(i; j) =

L X ul(2v(i; j) l=1 1)(2hl(i; j) 1): (2) The margin can not be calculated if the true partition is unknown. However, it was shown in [ 12, 14 ] that some of margin's characteristics can be evaluated using a number of assumptions on the behavior of clustering algorithms: A1) Under the condition that input data matrix is xed, for any pair of objects (ai; aj ) their true status is a random value V (i; j) with values de ned in (1). A2) Algorithm is randomized, i.e. it depends on the vector chosen at random from the set of parameters . For xed input data, is running L times with i.i.d. parameters 1; : : : ; L being statistical copies of .

Conditional probabilities of correct decisions (partition or union of ai and aj under xed V (i; j)) are denoted as q0(i; j) = P [h(i; j; ) = 0jV (i; j) = 0]; q1(i; j) = P [h(i; j; ) = 1jV (i; j) = 1]; where h(i; j; ) is the decision for (ai; aj ) made by algorithm with random parameters . It should be noted that the work [ 14 ] makes use of more restrictive assumption: q0(i; j) = q1(i; j), i.e. it presumes that the conditional probabilities of correct assigning of both kinds coincide. This assumption could be used for the qualitative analysis of cluster ensemble's behavior; however, numerical results of [ 13 ] demonstrate that it can be violated.

The measure of clustering validity, estimated with algorithm , is represented as a random value (X; ). Because the quality criterion is determined on the whole data set, one may consider this value practically independent on V (i; j) and h(i; j; ).

The weights u1; : : : ; uL are random values following identical distribution de ned by the distribution of ( ) and its statistical copies 1( 1); : : : ; L( L). The weights are dependent on each other, and for any pair (ul1 ; ul2 ) the degree of their dependence is characterized with the covariance coe cient = cov[ul1 ; ul2 ]: From i.i.d. assumption, and because of P E[ul] = E l

P ul l = 1, it follows that E[ul] =

. Let us denote by s = V ar[ul] the variance of weights. From 0 = V ar "

# X ul = l

X V ar[ul] + l

X l1;l2 (l16=l2 ) cov[ul1 ; ul2 ]; one may conclude that LV ar[ul] + L(L 1)cov[ul1 ; ul2 ] = 0: Thus we get =

L s 1 : (3) Proposition 2. Given the assumptions A1), A2) be valid, conditional mathematical expectation of ensemble margin for (ai; aj ) under V (i; j) = v equals: E [mg(i; j) j V (i; j) = v] = 2Q(v; i; j) 1; where = ( 1; : : : ; L), Q(v; i; j) = (1 v) q0(i; j) + v q1(i; j); v 2 f0; 1g.

Proof. Let us denote by hl(i; j; l) = I[ (i; l) = (j; l)] the decision for (ai; aj ), where (i; l) is the cluster label assigned to object ai by algorithm in its lth run with usage of parameter vector l.

Until the proof end, arguments i; j are skipped for short: mg(i; j) = mg, V (i; j) = V , etc. From (2) we have:

E [mgjV = v] = P E [ul ( l)(2v 1)(2hl( l) 1)]:

l

Because l and are equally distributed and ul( l) is independent on hl( l), it holds true that E [mgjV = v] = P E[ul( )] (2v 1)(2E [h( )] 1) = (2v 1)(2E [h( )] 1): l

For v = 0 we have: (2v 1)(2E [h( )] 1) = (2P [h( ) = 1jV = 0] 1) = 2q0 1; and for v = 1: (2v 1)(2E [h( )] 1) = 2P [h( ) = 1jV = 1] 1 = 2q1 1: Therefore E [mgjV = v] = 2Q(v; i; j) 1: This completes the proof. Proposition 3. Given the assumptions A1), A2) be valid, conditional variance of ensemble margin for (ai; aj ) under V (i; j) = v equals:

V ar [mg(i; j) j V (i; j) = v] = 4Q(v; i; j)(1 Q(v; i; j)) (L s + Proof. Let us again skip indices i; j for simplicity; and also let hl denote hl( l), h = h( ), ul = ul( ). From the properties of variance, it follows that under condition V = v it holds true:

V ar [mg] = (2v 1)2V ar "

Now we consider the upper bound for the weight's variance.

Proposition 4. Under the validity of the assumptions A1) and A2), the vari1 ance s = V ar[ul] is upper bounded with the expression: s L2 (E[ ( ) 2] 1): (E[h])2 (E[ul1 ul2 ]

E[ul1 ]E[ul2 ]) = (E[h])2 L(L 1) : Using (3), (4) we see that V ar [mg] = 4Q(1

Q) L s +

Q(1

Q) + 4(E[h])2L s

4 (E[h])2 L s = The proof technically repeats the one for analogous statement in [ 14 ], p. 430.

Our main objective is nding dependencies between the observed ensemble characteristics and the probability of directly unobserved classi cation error for a pair ai; aj :

Perr(i; j) = P 1;:::; L;U(i;j)[ c(i; j) 6= V (i; j)]:

It is clear that the probability of error in ensemble classi cation of a pair equals Perr(i; j) = P [mg(i; j) < 0].

Now let us consider the conditional probability of error under given state of objects: Perr(v; i; j) = P 1;:::; L;V (i;j)[ c(i; j) 6= V (i; j) j V (i; j) = v]; v 2 f0; 1g: Proposition 5. Let the above introduced model assumptions A1), A2) be valid, and also let E [mg(i; j) j V (i; j) = v] > 0 for each (i; j). Then the conditional probability of error in classi cation of a given pair is upper bounded by the expression:

Perr(v; i; j) <

V ar [mg(i; j) j V (i; j) = v] (E [mg(i; j) j V (i; j) = v])2 ; where conditional mathematical expectation and variance of margin are given by Propositions 2,3.

This property directly follows from the Tchebychev's inequality. The proof is similar to one given in [ 14 ], p. 433, and skipped in this work for the sake of brevity.

From Proposition 2, it is clear that the margin expectation takes positive value if the following assumption is valid:

A3) 8i; j (i 6= j); 0:5 < q0(i; j) 1; 0:5 < q1(i; j) 1:

It means that the base clustering algorithm has at least slightly better classi cation quality than just random assignment of a pair to the same or di erent clusters. In machine learning theory, similar conditions are known as algorithm's weak learnability.

Let us formulate an important consequence of the obtained results. Proposition 6. Holding all other factors constant, under validity of assumptions A1), A2) and A3), conditional probability of error converges to zero as the ensemble size increases.

This property follows from Propositions 2-5 taking into account that the weight's variance s is of order O(L 2). 6

Numerical Experiments

This Section Describes Numerical Experiments with Kcce. In the First experiment, we used Monte Carlo statistical modeling technique to evaluate the quality of classi cation. We consider a simple case of two spherical Gaussian classes N (m1; ) and N (m2; ), each having diagonal covariance matrix = I, where > 0 is a parameter, m1 and m2 are population means (in our experiments, m1 = 0 and m2 = 1). The classes are of equal prior probabilities P1 = P2 = 0:5. In this simple case, it is possible to derive the Bayes probability of error PB = ( =2); where = (m1 m2)T 1(m1 m2) is the Machalanobis distance, is the standard Gaussian cumulative distribution function. Moreover, the expected generalization error for the optimal sample-based linear ! classi er [ 25 ] asymptotically equals PN =

In Monte Carlo modeling, we repeatedly generate data sets according to the given distributions. For each class, training sample size equals N . Each data set is analyzed in Matlab environment with SVM, KFD and KCCE. For SVM and jjx x0jj 2 KFD, radial basis function '(x; x0) = e 2 r with r = 5 is used as a kernel. The soft margin constant is C = 10. The cluster ensemble is generated for KCCE by random initialization of centroids in K-means (number of clusters equals 2). Ensemble size equals 10. The weights of partition variants are constant values.

The accuracy (probability of correct classi cation) of each algorithm is estimated by independent test sample of size Nt = 1000. To make the results more statistically sound, we averaged the accuracy estimates over 100 Monte Carlo repetitions. The 95% con dence intervals for the probability of correct classi cation are evaluated for each algorithm.

Figure 1 presents the results of modeling. The plots display the dependencies between algorithm's accuracy and standard deviation for di erent combinations of feature space dimensionality and training sample size.

The results show that there exist such examples of data distribution for which the proposed method demonstrates substantially more accurate classi cation than SVM or KFD, and approaches to the optimal Bayes classi er.

In the second experiment we consider a real hyperspectral satellite image \Indian Pines" taken from [ 26 ]. This scene was gathered by AVIRIS sensor over the Indian Pines test site in North-western Indiana. The image size is 145 145 pixels; each pixel is characterized by the vector of 224 spectral intensities in 4002500 nm range. The image includes 16 classes describing di erent vegetation types, as one can see in Figure 2. There are unlabeled pixels not assigned to any of the classes. These pixels are excluded from the analysis. To study the e ect of noise on the performance of the algorithms, randomly selected 100r% of the spectral intensity values have experienced a distorting e ect: the corresponding value x is replaced by the quantity generated from the interval [x(1 p); x(1+p)], where r; p are preset parameters. The dataset has been randomly divided on training and test sample in proportion 1:3.

We use multiclass SVM following \one-against-one" strategy. Cluster ensemble size is L = 200 . For the construction of each variant, three hyperspectral channels are randomly chosen. To obtain more diverse results of K-means, the number of its iterations is limited to 1, and the initial centroids are randomly sampled from data. In the ensemble generation, data matrix Xtest is not used. The number of clusters in each variant equals dpN e. The weights of clusterings are constant values.

We compare the proposed algorithm with conventional SVM using Euclidean metric, under similar conditions (the parameters are chosen as recommended default values in Matlab environment; RBF kernel with = 10 gives the best results). Table 1 shows the accuracy of classi cation (rate of correctly predicted class labels) on test sample for some of the noise parameters. The running time on a dual-core Intel Core i5 processor with a clock frequency of 2.8 GHz and 4 GB RAM is about 50 sec in average for KCCE and 14 sec for SVM (note that an unoptimized code is used in KCCE implementation, in contrast with e cient implementation of SVM). One can see that KCCE has revealed itself as more noise resistant than SVM, especially under large distortion rates. In this work, we have introduced a supervised classi cation algorithm using a combination of ensemble clustering and kernel based classi cation. In the clustering ensemble, we used a scheme of a single clustering algorithm that constructs base partitions with parameters taken at random. It was veri ed that the weighted co-association matrix obtained with a clustering ensemble is a valid kernel matrix. The proposed combined approach experimentally has been proven to be successful when comparing with Support Vector Machine and Kernel Fisher Discriminant. Monte-Carlo experiments demonstrated that there exist examples of data distribution for which the proposed method gets signi cantly more accurate predictions. The experiment with a real hyperspectral satellite image has shown that the suggested algorithm is more accurate than SVM under noise distortion.

In the future, we plan to continue working under improving the performance of the suggested approach. For example, it will be useful to lter out points with unstable clusterings before using the kernel classi er. We expect that applying cluster ensemble with optimized weights [ 12 ] will further improve the accuracy. It will be interesting to apply the introduced approach for the solution of other types of machine learning problems such as regression or transfer learning. Acknowledgement. The work was carried out according to the scienti c research program \Mathematical methods of pattern recognition and prediction" in the Sobolev Institute of mathematics SB RAS. The research was partly supported by RFBR grant 18-07-00600 and partly by the Russian Ministry of Science and Education under the 5-100 Excellence Programme.

References

1. Shawe-Taylor , J., Cristianini , N.: Kernel Methods for Pattern Analysis . Cambridge University Press ( 2004 )

2. Zhuravlev , Y.I. : Principles of construction of justi cation of algorithms for the solution of badly formalized problems . Mathematical Notes of the Academy of Sciences of the USSR . 23 ( 6 ), 493 { 501 ( 1978 )

3. Schapire , R. , Freund , Y. , Bartlett , P. , Lee , W. : Boosting the margin: a new explanation for the e ectiveness of voting methods . Annals of Statistics 26 ( 5 ), 1651 { 1686 ( 1998 )

4. Breiman , L. : Random forests . Machine Learning 45(1) , 5 { 32 ( 2001 )

5. Kuncheva , L. : Combining Pattern Classi ers . Methods and Algorithms . Wiley, NJ ( 2004 )

6. Ajdarkhanov , M.B. , Amirgaliev , E.N. , La , L.L. : Correctness of algebraic extensions of models of classi cation algorithms . Kibernetika i Sistemnyj Analiz 5 , 180 { 186 ( 2001 )

7. Jain , A.K. : Data clustering: 50 years beyond k-means . Pattern Recognition Letters 31 ( 8 ), 651 { 666 ( 2010 )

8. Ghosh , J. , Acharya , A. : Cluster ensembles . Wiley Interdisciplinary Reviews: Data Mining and Knowledge Discovery 1 ( 5 ), 305 { 315 ( 2011 )

9. Vega-Pons , S. Ruiz-Shulcloper , J.: A survey of clustering ensemble algorithms . IJPRAI 25 ( 3 ), 337 { 372 ( 2011 )

10. Fred , A. , Jain , A. : Combining multiple clusterings using evidence accumulation . IEEE Transaction on Pattern Analysis and Machine Intelligence 27 , 835 { 850 ( 2005 )

11. Gray , R.M.: Vector quantization . IEEE ASSP Magazine 1 ( 2 ), 4 { 29 ( 1984 )

12. Berikov , V.: Weighted ensemble of algorithms for complex data clustering . Pattern Recognition Letters 38 , 99 { 106 ( 2014 )

13. Berikov , V.: Cluster ensemble with averaged co-association matrix maximizing the expected margin . In: 9th International Conference on Discrete Optimization and Operations Research and Scienti c School (DOOR 2016 ). pp. 489 { 500 ( 2016 )

14. Berikov , V. , Pestunov , I. : Ensemble clustering based on weighted co-association matrices: Error bound and convergence properties . Pattern Recognition 63 , 427 { 436 ( 2017 )

15. Zhuravlev , Y.I. , Yunusov , R.: A method of improving the taxonomy algorithm by pattern recognition methods of the voting type . USSR Computational Mathematics and Mathematical Physics 11 ( 5 ), 327 { 333 ( 1971 )

16. Jaing , M. , Tseng , S. and Su , C. : Two-phase clustering process for outlier detection . Pattern Recognition Letters 22 ( 67 ), 691 { 700 ( 2001 )

17. Rahman , A. , Verma , B. : Cluster-based ensemble of classi ers . Expert Systems 30 , 270 { 282 ( 2013 )

18. Chapelle , O. , Zien , A. , Scholkopf , B . (Eds.): Semi-Supervised Learning . MIT Press ( 2006 )

19. Chapelle , O. , Weston , J. , Scholkopf , B. : Cluster kernels for semi-supervised learning . Adv. Neural Inf. Process. Syst . 15 , 601 - 608 ( 2002 )

20. Ng , A.Y. , Jordan , M.I. , Weiss , Y.: On spectral clustering: Analysis and an algorithm . In Advances in Neural Information Processing Systems 14 ( 2001 )

21. Balcan , M.F. , Blum , A. , Srebro , N.: A theory of learning with similarity functions . Machine Learning 72 , 89 { 11 ( 2008 )

22. Iam-On , N. , Boongoen , T. : Diversity-driven generation of link-based cluster ensemble and application to data classi cation . Expert Systems with Applications 42 ( 21 ), 8259 { 8273 ( 2015 )

23. Dietterich , T. , Bakiri , G.: Solving multiclass learning problems via error-correcting output codes . Journal of Arti cial Intelligence Research 2 , 263 - 282 ( 1995 )

24. Platt , J.: Sequential Minimal Optimization: A Fast Algorithm for Training Support Vector Machines . Advances In Kernel Methods - Support Vector Learning ( 1998 )

25. Raudys , S. : Statistical and Neural Classi ers: An integrated approach to design . London: Springer-Verlag ( 2001 )

26. Hyperspectral Remote Sensing Scenes: http://www.ehu.es/ccwintco/index.php/ HyperspectralRemote SensingScenes, [On-line; accessed 09-February-2018]