# Combining Dissimilarities in a Hyper Reproducing Kernel Hilbert Space for Complex Human Cancer Prediction

Authors: Manuel Martín-Merino; Ángela Blanco; Javier De Las Rivas
Journal: Journal of Biomedicine and Biotechnology
 (2009)

---

## Abstract

DNA microarrays provide rich profiles that are used in
cancer prediction considering the gene expression levels
across a collection of related samples. Support Vector Machines
(SVM) have been applied to the classification of cancer
samples with encouraging results. However, they rely on
Euclidean distances that fail to reflect accurately the proximities
among sample profiles. Then, non-Euclidean dissimilarities
provide additional information that should be considered
to reduce the misclassification errors.
In this paper, we incorporate in theν-SVM algorithm a
linear combination of non-Euclidean dissimilarities. The
weights of the combination are learnt in a (Hyper
Reproducing Kernel Hilbert Space) HRKHS using a Semidefinite
Programming algorithm. This approach allows us to incorporate
a smoothing term that penalizes the complexity of the
family of distances and avoids overfitting. The experimental results suggest that the method proposed
helps to reduce the misclassification errors in several
human cancer problems.


---

## Body

## 1. Introduction

DNA Microarray technology provides us a way to monitor the expression levels of thousands of genes simultaneously across a collection of related samples. This technology has been applied particularly to the prediction of different types of human cancer with encouraging results [1].Support Vector Machines (SVM) [2] are powerful machine learning techniques that have been applied to the classification of cancer samples [3]. However, the categorization of different cancer types remains a difficult problem for classical SVM algorithms. In particular, the SVM is based on Euclidean distances that fail to reflect accurately the proximities among the sample profiles [4]. Non-Euclidean dissimilarities misclassify frequently different subsets of patterns because each one reflects complementary features of the data. Therefore, they should be integrated in order to reduce the fraction of patterns misclassified by the base dissimilarities.In this paper, we introduce a framework to learn a linear combination of non-Euclidean dissimilarities that reflect better the proximities among the sample profiles. Each dissimilarity is embedded in a feature space using the Empirical Kernel Map [5, 6]. After that, learning the dissimilarity is equivalent to optimize the weights of the linear combination of kernels. Several approaches have been proposed to this aim. In [7, 8] the kernel is learnt optimizing an error function that maximizes the alignment between the input kernel and an idealized kernel. However, this error function is not related to the misclassification error and is prone to overfitting. To avoid this problem, [9] learns the kernel by optimizing an error function derived from the Statistical Learning Theory. This approach includes a term to penalize the complexity of the family of kernels considered. This algorithm is not able to incorporate infinite families of kernels and does not overcome the overfitting of the data.In this paper, the combination of distances is learnt in a (Hyper Reproducing Kernel Hilbert Space) HRKHS following the approach of hyperkernels proposed in [10]. This formalism exhibits a strong theoretical foundation and is less sensitive to overfitting. Moreover, it allow us to work with infinite families of distances. The algorithm has been applied to the prediction of different kinds of human cancer. The experimental results suggest that the combination of dissimilarities in a Hyper Reproducing Kernel Hilbert Space improves the accuracy of classifiers based on a single distance, particularly for nonlinear problems. Besides, our approach outperforms the Lanckriet formalism specially for multicategory problems and is more robust to overfitting.This paper is organized as follows. Section2 introduces the algorithm proposed, the material and the methods employed. Section 3 illustrates the performance of the algorithm in the challenging problem of gene expression data analysis. Finally, Section 4 gets conclusions and outlines future research trends.


## 2. Material and Methods

### 2.1. Distances for Gene Expression Data Analysis

An important step in the design of a classifier is the choice of a proper dissimilarity that reflects the proximities among the objects. However, the choice of a good dissimilarity is not an easy task. Each measure reflects different features of the data and the classifiers induced by the dissimilarities misclassify frequently a different set of patterns. In this section, we comment shortly the main differences among several dissimilarities proposed to evaluate the proximity between biological samples considering their gene expression profiles. For a deeper description and definitions see [11].Letx=[x1,…,xd] be the vectorial representation of a sample where xi is the expression level of gene i. The Euclidean distance  evaluates if the gene expression levels differ significantly across different samples:
(1)deuclid(x,y)=∑i=1d‍(xi-yi)2.An interesting alternative is thecosine dissimilarity. This measure will become small when the ratio between the gene expression levels is similar for the two samples considered. It differs significantly from the Euclidean distance when the data is not normalized by the L2 norm:
(2)dcosine(x,y)=1-xTy∥x∥∥y∥.
The correlation measure  evaluates if the expression level of genes change similarly in both samples. Correlation-based measures tend to group together samples whose expression levels are linearly related. The correlation differs significantly from the cosine if the means of the sample profiles are not zero. This measure is more sensitive to outliers:
(3)dcor(x,y)=1-∑i=1d(xi-x̅)(yi-y̅)∑i=1d(xi-x̅)2∑j=1d(yj-y̅)2,
where x̅ and y̅ are the means of the gene expression profiles.TheSpearman rank dissimilarity is less sensitive to outliers because it computes a correlation between the ranks of the gene expression levels:
(4)dspeam(x′,y′)=1-∑i=1d(xi′-x′̅)(yi′-y′̅)∑i=1d(xi′-x′̅)2∑i=1d(yi′-y′̅)2,
where xi'=rank(xi) and yj'=rank(yj).An alternative measure that helps to overcome the problem of outliers is theKendall-τ  index  which is related to the Mutual Information probabilistic measure [11]:
(5)dkendall(x,y)=1-∑i=1d∑j=1dCxij-Cyijd(d-1),
where Cxij=sign(xi-xj) and Cyij=sign(yi-yj).Finally, the dissimilarities have been transformed using the inverse multiquadratic kernel because this transformation helps to discover certain properties of the underlying structure of the data [12, 13]. The inverse multiquadratic transformation is based on the inverse multiquadratic kernel defined as follows:
(6)k(x,y)=1∥x-y∥2+c2,
where c is a smoothing parameter. Considering that ∥x-y∥ is the Euclidean distance, (6) can be rewritten in terms of a dissimilarity as follows:
(7)k(x,y)=1dij2+c2.
The above nonlinear transformation gives more weight to small dissimilarities, particularly when c becomes small.


### 2.2.ν-Support Vector Machines

Support Vector Machines [2] are powerful classifiers that are able to deal with high dimensional and noisy data keeping a high generalization ability. They have been widely applied in cancer classification using gene expression profiles [1, 14]. In this paper, we will focus on the ν-Support Vector Machines (SVM). The ν-SVM is a reparametrization of the classical C-SVM [2] that allows to interpret the regularization parameter in terms of the number of support vectors and margin errors. This property helps to control the complexity of the approximating functions in an intuitive way. This feature is desirable for the application we are dealing with because the sample size is frequently small and the resulting classifiers are prone to overfitting.Let{(xi,yi)}i=1n be the training set codified in ℝd. We assume that each xi belongs to one of the two classes labeled by yi∈{-1,1}. The SVM algorithm looks for the linear hyperplane f(x;w)=wTx+b that maximizes the margin γ=2/∥w∥2. γ determines the generalization ability of the SVM. The slack variables ξi allow to consider classification errors and are defined as ξi=max{0,1-yif(xi)}.For theν-SVM, the hyperplane that minimizes the prediction error is obtained solving the following optimization problem [2]:
(8)minw,{ξi},ρ12∥w∥2-νρ+1m∑i‍ξis.t.yi(〈w,xi〉+b)≥ρ-ξi,i=1,…,m,ξi≥0,ρ≥0i=1,…,m,
where ν is an upper bound on the fraction of margin errors and a lower bound on the number of support vectors. Therefore, this parameter controls the complexity of the approximating functions.The optimization problem can be solved efficiently in the dual space and the discriminant function can be expressed exclusively in terms of scalar products:(9)f(x)=∑αi>0‍αiyi〈x,xi〉+b,
where αi are the Lagrange multipliers in the dual optimization problem. The ν-SVM algorithm can be easily extended to the nonlinear case substituting the scalar products by a Mercer kernel [2]. Besides, non-Euclidean dissimilarities can be incorporated into the ν-SVM via the kernel of dissimilarities [5].Finally, several approaches have been proposed in the literature to extend the SVM to deal with multiple classes. In this paper, we have followed the one-against-one (OVO) strategy. Letk be the number of classes, in this approach k(k-1)/2 binary classifiers are trained and the appropriate class is found by a voting scheme. This strategy compares favorably with more sophisticated methods and it is more efficient computationally than the one-against-rest (OVR) approach [15].


### 2.3. Empirical Kernel Map

The Empirical Kernel Map allows us to incorporate non-Euclidean dissimilarities into the SVM algorithm using the kernel trick [5, 13].Letd:𝒳×𝒳→ℝ be a dissimilarity and R={p1,…,pn} a subset of representatives drawn from the training set. Define the mapping ϕ:ℱ→ℝn as
(10)ϕ(z)=D(z,R)=[d(z,p1),d(z,p2),…,d(z,pn)].
This mapping defines a dissimilarity space where feature i is given by d(·,pi).The set of representativesR determines the dimensionality of the feature space. The choice of R is equivalent to select a subset of features in the dissimilarity space. Due to the small number of samples in our application, we have considered the whole training set as representatives. Notice that it has been suggested in literature [13] that for small samples reducing the set of representatives does not help to improve the classifier performance.


### 2.4. Learning a Linear Combination of Dissimilarities in an HRKHS

In order to learn a linear combination of non-Euclidean dissimilarities, we follow the  approach of Hyperkernels developed by [10]. To this aim, each distance is embedded in an RKHS via the Empirical Kernel Map presented in Section 2.3. Next, a regularized quality functional is introduced that incorporates an l2-penalty over the complexity of the family of distances considered. The solution to this regularized quality functional is searched in a Hyper Reproducing Kernel Hilbert Space. This allows to minimize the quality functional using an SDP approach.LetXtrain={x1,x2,…,xm} and Ytrain={y1,y2,…,yn} be a finite sample of training patterns where yi∈{-1,+1}. Let 𝒦 be a family of semidefinite positive kernels. Our goal is to learn a kernel of dissimilarities k∈𝒦 that represents the combination of dissimilarities and minimizes the following empirical quality functional:
(11)Qemp(f,Xtrain,Ytrain)=1m∑i=1m‍l(xi,yi,f(xi))+λ2∥f∥ℋ2,
where l is a loss function, ∥∥ℋ is the L2 norm defined in a reproducing kernel Hilbert space, and λ is a regularization parameter that controls the balance between training error and the generalization ability.By virtue of the representer theorem [2], we know that (11) can be written as a kernel expansion:
(12)Qemp=minα,k[1m∑i=1m‍l(xi,yi,[Kα]i)+λ2αTKα].
However, if the family of kernels 𝒦 is complex enough it is possible to find a kernel that achieves zero error overfitting the data. To avoid this problem, we introduce a term that penalizes the kernel complexity in an HRKHS. A rigorous definition of the HRKHS is provided in the appendix:
(13)Qreg(k,X,Y)=Qemp(k,X,Y)+λQ2∥k∥H̲2,
where ∥∥ℋ̲ is the L2 norm defined in the Hyper Reproducing Kernel Hilbert space generated by the hyperkernel k̲. λQ is a regularization parameter that controls the complexity of the resulting kernel.The following theorem allows us to write the solution to the minimization of this regularized quality functional as a linear combination of hyperkernels in an HRKHS.Theorem 1 (Representer theorem for Hyper-RKHS [10]).
Let X, Y be the combined training and test set, then each minimizerk∈ℋ̲ of the regularized quality functional Qreg(k,X,Y) admits a representation of the form
(14)k(x,x′)=∑i,j=1m‍βijk̲((xi,xj),(x,x′)),
for all x,x′∈X, where βij∈ℝ, for each 1≤i,j≤m.However, we are only interested in solutions that give rise to positive semidefinite kernels. The following condition over the hyperkernels [10] allows us to guarantee that the solution is a positive semidefinite kernel.Property 1.
Given a hyperkernelk̲  with elements such that for any fixed x̲∈X̲, the function k(xp,xq)=k̲(x̲,(xp,xq)), with xp,xq∈𝒳, is a positive semidefinite kernel, and βij≥0 for all i,j=1,…,m, then the kernel
(15)k(xp,xq)=∑i,j=1m‍βijk̲(xi,xj,xp,xq)
is positive semidefinite.Now, we address the problem of combining a finite set of dissimilarities. As we mentioned in Section2.3, each dissimilarity can be represented by a kernel using the Empirical Kernel Map. Next, the hyperkernel is defined as
(16)k̲(x̲,x′̲)=∑i=1n‍ciki(x̲)ki(x′̲),
where each ki is a positive semidefinite kernel of dissimilarities and ci is a constant ≥0.Now, we show thatk̲ is a valid hyperkernel. First, k̲ is a kernel because it can be written as a dot product 〈Φ̲(x̲),Φ̲(x′̲)〉 where
(17)Φ̲(x̲)=(c1k1(x̲),c2k2(x̲),…,cnkn(x̲)).
Next, the resulting kernel (15) is positive semidefinite because for all x̲,k̲(x̲,(xp,xq)) is a positive semidefinite kernel and βij can be constrained to be ≥0. Besides, the linear combination of kernels is a kernel and therefore is positive semidefinite. Notice that k̲(x̲,(xp,xq)) is positive semidefinite if ci≥0 and ki are pointwise positive for training data. Both RBF and multiquadratic kernels verify this condition.Finally, we show that the resulting kernel is a linear combination of the originalki. Substituting the expression of the hyperkernel (16) in (15), the kernel is written as
(18)k(xp,xq)=∑i,j=1m‍βij∑l=1n‍clkl(xi,xj)kl(xp,xq).
Now the kernel can be written as a linear combination of base kernels:
(19)k(xp,xq)=∑l=1n‍[cl∑i,j=1m‍βijkl(xi,xj)]kl(xp,xq).
Therefore, the above kernel introduces into the ν-SVM a linear combination of base dissimilarities represented by kl with coefficients γl=cl∑i,j=1m‍βijkl(xi,xj).The previous approach can be extended to an infinite family of distances. In this case, the space that generates the kernel is infinite dimensional. Therefore, in order to work in this space, it is necessary to define a hyperkernel and to optimize it using an HRKHS. Letk be a kernel of dissimilarities. The hyperkernel is defined as follows [10]:
(20)k̲(x̲,x′̲)=∑i=0∞‍ci(k(x̲)k(x′̲))i,
where ci≥0 and i=0,…,∞. In this case, the nonlinear transformation to feature space is infinite dimensional. Particularly, we are considering all powers of the original kernels which is equivalent to transform nonlinearly the original dissimilarities:
(21)Φ̲(x̲)=((c1)k(x̲),(c2)k2(x̲),…,(cn)kn(x̲)),
where n is the dimensionality of the space which is infinite in this case. As we mentioned in Section 2.1, nonlinear transformations of a given dissimilarity provide additional information that may help to improve the classifier performance.As for the finite family, it can be easily shown thatk̲ is a valid hyperkernel provided that the kernels considered are pointwise positive. The Inverse Multiquadratic kernel satisfies this condition. Next, we derive the hyperkernel expression for the multiquadratic kernel.Proposition 1 (see [Harmonic Hyperkernel]).
Suppose k is a kernel with range[0,1] and ci=(1-λh)λhi, i∈ℕ, 0<λh<1. Then, computing the infinite sum in (20), one has the following expression for the harmonic hyperkernel:
(22)k̲(x̲,x′̲)=(1-λh)∑i=0∞‍(λhk(x̲)k(x′̲))i=1-λh1-λhk(x̲)k(x′̲),λh is a regularization term that controls the complexity of the resulting kernel. Particularly, larger values for λh give more weight to strongly nonlinear kernels while smaller values give coverage for wider kernels.
In this paper one has considered the inverse multiquadratic kernel defined in (6). Substituting in (22), one gets the inverse multiquadratic hyperkernel:
(23)k̲(x̲,x̲′)=1-λh1-λh((∥x-x′∥2+c2)(∥x′′-x′′′∥2+c2))-1/2,
where x̲=(x,x′) and x′̲=(x′′,x′′′).


### 2.5.ν-SVM in an HRKHS

In this section, we detail how to learn the kernel for aν-Support Vector Machine in an HRKHS. First, we will introduce the optimization problem and next, we will explain shortly how to solve it using an SDP approach.We start some notation that is used in theν-SVM algorithm. For p,q,r∈ℝn, n∈ℕ let r=p∘q be defined as element by element  multiplication, ri=pi×qi. The pseudoinverse of a matrix K is denoted by K†. Define the hyperkernel Gram  matrix K̲ by K̲ijpq=k̲((xi,xj),(xp,xq)), the kernel matrix K=reshape(K̲β) (reshaping an m2 by 1 vector, K̲β, to an m×m matrix), Y=diag(y) (a matrix with y on the diagonal and zero otherwise), G(β)=YKY (the dependence on β is made explicit), and 1 is a vector of ones.Theν-SVM considered in this paper uses an l1 soft margin, where l(xi,yi,f(xi))=max(0,1-yif(xi)). This error is less sensitive to outliers which are convenient features for microarray datasets. Let ξi be the slack variables that allow for errors in the training set. Substituting in (13) Qemp by the one optimized by ν-SVM (8) the regularized quality functional in an HRKHS can be written as
(24)mink∈H̲minw∈ℋk1m∑i=1m‍ξi+12∥w∥ℋ2-νρ+λQ2∥k∥H̲2s.t.yif(xi)≥ρ-ξi,i=1,…,m,ξi≥0i=1,…,m,
where ν is the regularization parameter that achieves a balance between training error and the complexity of the approximating functions and λQ is a parameter that penalizes the complexity of the family of kernels considered.  The minimization of the previous equation leads to the following SDP optimization problem [10].
(25)minβ,γ,η,ξ,χ12t1-χν+1mξT1+λQ2t2(26)s.t.χ≥0,η≥0,ξ≥0,β≥0,(27)∥K̲1/2β∥≤t2,1Tβ=1,(28)[G(β)zzTt1]≽0,
where z=γy+χ1+η-ξThe value ofα which optimizes the corresponding Lagrange function is G(β)†z, and the classification function, f=sign(K(α∘y)-boffset), is given by
(29)f=sign(KG(β)†(y∘z)-γ),K̲ is the hyperkernel defined in Section 2.4 which represents the combination of dissimilarities considered. Finally, the algorithm proposed can be easily extended to deal with multiple classes via a one-against-one approach (OVO). This strategy is simple, more efficient computationally than the OVR, and compares well with more sophisticated multicategory SVM methods [15].


### 2.6. Implementation

The optimization problem (25) were solved using SeDuMi 1.1R3 [16] and YALMIP [17] SDP optimization packages running under MATLAB.As in the SDP problem there arem2 coefficients βij, the computational complexity is high. However, it can be significantly reduced if the Hyperkernel {k̲((xi,xj),·)∣1≤i,j≤m2} is approximated by a small fraction of terms, p≪m2 for a given error. In particular, we have chosen an m×p truncated lower triangular matrix G which approximate the hyperkernel matrix to an error δ=10-6 using the incomplete Cholesky factorization method [18].


### 2.7. Datasets and Preprocessing

The gene expression datasets considered in this paper correspond to several human cancer problems and exhibit different features as shown in Table1. We have considered both, binary and multi-category problems with a broad range of signal to noise ratio (Var/Samp.), different number of samples, and varying priors for the larger category. All the datasets are available from the Broad Institute of MIT and Harvard http://www.broad.mit.edu/cgi-bin/cancer/datasets.cgi/. Next we detail the features and preprocessing applied to each dataset.Table 1
Features of the different cancer datasets
ClasesSamplesGenesVar/Samp.Priors%Lymphoma DLBCL27768178875.3Lymphoma MLBCL/DLBCL22104492821384Breast cancer LN249712914551Medulloblastoma260712911965Breast cancer B349121324.752DLBCL survival C458379565.427DLBCL survival D4129379529.438The first dataset was obtained from77 patients with (diffuse large B-cell lymphoma) DLBCL (58 samples) or FL (follicular lymphoma) (19 samples) and they were subjected to transcriptional profiling using oligonucleotide Affymetrix gene chip  hu68000  containing probes for 6817 genes [19]. The second dataset consists of frozen tumors specimens from newly diagnosed, previously untreated MLBCL patients (34 samples) and DLBCL patients (176 samples). They were hybridized to Affymetrix hgu133b  gene chip containing probes for 44000 genes [20]. In both cases the raw intensities have been normalized using the rma algorithm [21] available from Bioconductor package [11]. The third problem we address concerns the clinically important issue of metastatic spread of the tumor. The determination of the extent of lymph node involvement in primary breast cancer is the single most important risk factor in disease outcome and here the analysis compares primary cancers that have not spread beyond the breast to ones that have metastasized to axillary lymph nodes at the time of diagnosis. We identified tumors as “reported negative’’ (24) when no positive lymph nodes were discovered and “reported positive’’ (25) for tumors with at least three identifiably positive nodes [22]. All assays used the human HuGeneFL Genechip microarray containing probes for 7129 genes. The fourth dataset [23] address the clinical challenge concerning medulloblastoma due to the variable response of patients to therapy. Whereas some patients are cured by chemotherapy and radiation, others have progressive disease. The dataset consists of 60 samples containing 39 medulloblastoma survivors and 21 treatment failures. Samples were hybridized to Affymetrix HuGeneFL arrays containing 5920 known genes and 897 expressed sequence tags.All the datasets have been standarized subtracting the median and dividing by the Inter-quantile range. The rescaling were performed based only on the training set to avoid bias.Regarding the identification of multiple classes of cancer we have considered three different datasets. The first one consists of49 samples of Breast Cancer generated using 1-channel oligonucleotide Affymetrix HuGeneFl [1]. The second and third datasets consist of 58 and a129 samples from Diffuse large B-cell lymphoma with survival data. Fourth different subclasses can be identified. Data preparatory steps have been performed by the authors of the primary study [1]. The 10% oligonucleotides with smaller Interquantile Range were filtered to remove genes with expression level constant across samples.


### 2.8. Performance Evaluation

In order to assure an honest evaluation of all the classifiers we have performed a double loop of crossvalidation [15]. The outer loop is based on stratified tenfold cross-validation that iteratively splits the data in ten sets, one for testing and the others for training. The inner loop perform stratified ninefold cross-validation over the training set and is used to estimate the optimal parameters avoiding overfitting. The stratified variant of cross-validation keeps the same proportion of patterns for each class in training and test sets. This is necessary in our problem because the class proportions are not equal. Finally, the error measure considered to evaluate the classifiers has been accuracy. This metric computes the proportion of samples misclassified. The accuracy is easy to interpret and allows us to compare with the results obtained by previously published studies.


### 2.9. Parameters for the Classification Algorithm

The parameters for theν-SVM and for the classifiers based on a linear combination of dissimilarities have been set up by a nested stratified tenfold crossvalidation procedure [15]. This method avoids the overfitting as is described in Section 2.8 and takes into account the asymmetric distribution of class priors.For theν-SVM we have considered both, linear and inverse multiquadratic kernels. The optimal parameters have been obtained by a grid search strategy over the following set of values: ν={0.1,0.2,0.3,0.4,0.5} and σ={d/2,d,2d}, where d denotes the dimensionality of the input space.Additionally, for the finite family of distancesci=1/M where M is the number of dissimilarities considered, and λQ=1 because the misclassification errors are hardly sensitive to the regularization parameter that controls the kernel complexity. Finally, for the infinite family of dissimilarities, the regularization parameter λh in the Harmonic hyperkernel (22) has been set up to 0.6 which gives an adequate coverage of various kernel widths. Smaller values emphasizes only wide kernels. All the base kernel of dissimilarities have been normalized so that all ones have the same scale.Regarding the Lanckriet [9] formalism that allows to combine a finite set of dissimilarities, several values for the regularization parameter C have been tried, C={0.1,1,10,100,1000}. A grid search strategy has been applied to determine the best values for both, the kernel parameters and the regularization parameter. The kernel matrices have been normalized by the trace as recommended in the original paper.


### 2.10. Gene Selection

Gene selection can improve significantly the classifier performance [24]. Therefore, we have evaluated the classifiers for the following subsets of genes {280,146,101,56,34}. The ν-SVM is robust against noise and is able to deal with high dimensional data. However, the empirical evidence suggests that considering a larger subset of genes or even the whole set of genes increases the misclassification errors.The genes are ranked according to the ratio of between-group to within-group sums of squares defined in [25]:
(30)BW(j)=∑i∑kI(yi=k)(x̅·j(k)-x̅·j)2∑i∑kI(yi=k)(xij-x̅·j(k))2,
where x̅·j(k) and x̅·j denote “respectively’’ the average expression level of gene j for class k and the overall average expression level of gene j across all samples, yi denotes the class of sample i, and I(·) is the indicator function. Next, the top ranked genes are chosen. This feature selection method is simple but compares well with more sophisticated methods [24]. Finally, the ranking of genes has been carried out considering only the training set to avoid bias. Therefore, feature selection is repeated in each iteration of cross-validation.


## 2.1. Distances for Gene Expression Data Analysis

An important step in the design of a classifier is the choice of a proper dissimilarity that reflects the proximities among the objects. However, the choice of a good dissimilarity is not an easy task. Each measure reflects different features of the data and the classifiers induced by the dissimilarities misclassify frequently a different set of patterns. In this section, we comment shortly the main differences among several dissimilarities proposed to evaluate the proximity between biological samples considering their gene expression profiles. For a deeper description and definitions see [11].Letx=[x1,…,xd] be the vectorial representation of a sample where xi is the expression level of gene i. The Euclidean distance  evaluates if the gene expression levels differ significantly across different samples:
(1)deuclid(x,y)=∑i=1d‍(xi-yi)2.An interesting alternative is thecosine dissimilarity. This measure will become small when the ratio between the gene expression levels is similar for the two samples considered. It differs significantly from the Euclidean distance when the data is not normalized by the L2 norm:
(2)dcosine(x,y)=1-xTy∥x∥∥y∥.
The correlation measure  evaluates if the expression level of genes change similarly in both samples. Correlation-based measures tend to group together samples whose expression levels are linearly related. The correlation differs significantly from the cosine if the means of the sample profiles are not zero. This measure is more sensitive to outliers:
(3)dcor(x,y)=1-∑i=1d(xi-x̅)(yi-y̅)∑i=1d(xi-x̅)2∑j=1d(yj-y̅)2,
where x̅ and y̅ are the means of the gene expression profiles.TheSpearman rank dissimilarity is less sensitive to outliers because it computes a correlation between the ranks of the gene expression levels:
(4)dspeam(x′,y′)=1-∑i=1d(xi′-x′̅)(yi′-y′̅)∑i=1d(xi′-x′̅)2∑i=1d(yi′-y′̅)2,
where xi'=rank(xi) and yj'=rank(yj).An alternative measure that helps to overcome the problem of outliers is theKendall-τ  index  which is related to the Mutual Information probabilistic measure [11]:
(5)dkendall(x,y)=1-∑i=1d∑j=1dCxij-Cyijd(d-1),
where Cxij=sign(xi-xj) and Cyij=sign(yi-yj).Finally, the dissimilarities have been transformed using the inverse multiquadratic kernel because this transformation helps to discover certain properties of the underlying structure of the data [12, 13]. The inverse multiquadratic transformation is based on the inverse multiquadratic kernel defined as follows:
(6)k(x,y)=1∥x-y∥2+c2,
where c is a smoothing parameter. Considering that ∥x-y∥ is the Euclidean distance, (6) can be rewritten in terms of a dissimilarity as follows:
(7)k(x,y)=1dij2+c2.
The above nonlinear transformation gives more weight to small dissimilarities, particularly when c becomes small.


## 2.2.ν-Support Vector Machines

Support Vector Machines [2] are powerful classifiers that are able to deal with high dimensional and noisy data keeping a high generalization ability. They have been widely applied in cancer classification using gene expression profiles [1, 14]. In this paper, we will focus on the ν-Support Vector Machines (SVM). The ν-SVM is a reparametrization of the classical C-SVM [2] that allows to interpret the regularization parameter in terms of the number of support vectors and margin errors. This property helps to control the complexity of the approximating functions in an intuitive way. This feature is desirable for the application we are dealing with because the sample size is frequently small and the resulting classifiers are prone to overfitting.Let{(xi,yi)}i=1n be the training set codified in ℝd. We assume that each xi belongs to one of the two classes labeled by yi∈{-1,1}. The SVM algorithm looks for the linear hyperplane f(x;w)=wTx+b that maximizes the margin γ=2/∥w∥2. γ determines the generalization ability of the SVM. The slack variables ξi allow to consider classification errors and are defined as ξi=max{0,1-yif(xi)}.For theν-SVM, the hyperplane that minimizes the prediction error is obtained solving the following optimization problem [2]:
(8)minw,{ξi},ρ12∥w∥2-νρ+1m∑i‍ξis.t.yi(〈w,xi〉+b)≥ρ-ξi,i=1,…,m,ξi≥0,ρ≥0i=1,…,m,
where ν is an upper bound on the fraction of margin errors and a lower bound on the number of support vectors. Therefore, this parameter controls the complexity of the approximating functions.The optimization problem can be solved efficiently in the dual space and the discriminant function can be expressed exclusively in terms of scalar products:(9)f(x)=∑αi>0‍αiyi〈x,xi〉+b,
where αi are the Lagrange multipliers in the dual optimization problem. The ν-SVM algorithm can be easily extended to the nonlinear case substituting the scalar products by a Mercer kernel [2]. Besides, non-Euclidean dissimilarities can be incorporated into the ν-SVM via the kernel of dissimilarities [5].Finally, several approaches have been proposed in the literature to extend the SVM to deal with multiple classes. In this paper, we have followed the one-against-one (OVO) strategy. Letk be the number of classes, in this approach k(k-1)/2 binary classifiers are trained and the appropriate class is found by a voting scheme. This strategy compares favorably with more sophisticated methods and it is more efficient computationally than the one-against-rest (OVR) approach [15].


## 2.3. Empirical Kernel Map

The Empirical Kernel Map allows us to incorporate non-Euclidean dissimilarities into the SVM algorithm using the kernel trick [5, 13].Letd:𝒳×𝒳→ℝ be a dissimilarity and R={p1,…,pn} a subset of representatives drawn from the training set. Define the mapping ϕ:ℱ→ℝn as
(10)ϕ(z)=D(z,R)=[d(z,p1),d(z,p2),…,d(z,pn)].
This mapping defines a dissimilarity space where feature i is given by d(·,pi).The set of representativesR determines the dimensionality of the feature space. The choice of R is equivalent to select a subset of features in the dissimilarity space. Due to the small number of samples in our application, we have considered the whole training set as representatives. Notice that it has been suggested in literature [13] that for small samples reducing the set of representatives does not help to improve the classifier performance.


## 2.4. Learning a Linear Combination of Dissimilarities in an HRKHS

In order to learn a linear combination of non-Euclidean dissimilarities, we follow the  approach of Hyperkernels developed by [10]. To this aim, each distance is embedded in an RKHS via the Empirical Kernel Map presented in Section 2.3. Next, a regularized quality functional is introduced that incorporates an l2-penalty over the complexity of the family of distances considered. The solution to this regularized quality functional is searched in a Hyper Reproducing Kernel Hilbert Space. This allows to minimize the quality functional using an SDP approach.LetXtrain={x1,x2,…,xm} and Ytrain={y1,y2,…,yn} be a finite sample of training patterns where yi∈{-1,+1}. Let 𝒦 be a family of semidefinite positive kernels. Our goal is to learn a kernel of dissimilarities k∈𝒦 that represents the combination of dissimilarities and minimizes the following empirical quality functional:
(11)Qemp(f,Xtrain,Ytrain)=1m∑i=1m‍l(xi,yi,f(xi))+λ2∥f∥ℋ2,
where l is a loss function, ∥∥ℋ is the L2 norm defined in a reproducing kernel Hilbert space, and λ is a regularization parameter that controls the balance between training error and the generalization ability.By virtue of the representer theorem [2], we know that (11) can be written as a kernel expansion:
(12)Qemp=minα,k[1m∑i=1m‍l(xi,yi,[Kα]i)+λ2αTKα].
However, if the family of kernels 𝒦 is complex enough it is possible to find a kernel that achieves zero error overfitting the data. To avoid this problem, we introduce a term that penalizes the kernel complexity in an HRKHS. A rigorous definition of the HRKHS is provided in the appendix:
(13)Qreg(k,X,Y)=Qemp(k,X,Y)+λQ2∥k∥H̲2,
where ∥∥ℋ̲ is the L2 norm defined in the Hyper Reproducing Kernel Hilbert space generated by the hyperkernel k̲. λQ is a regularization parameter that controls the complexity of the resulting kernel.The following theorem allows us to write the solution to the minimization of this regularized quality functional as a linear combination of hyperkernels in an HRKHS.Theorem 1 (Representer theorem for Hyper-RKHS [10]).
Let X, Y be the combined training and test set, then each minimizerk∈ℋ̲ of the regularized quality functional Qreg(k,X,Y) admits a representation of the form
(14)k(x,x′)=∑i,j=1m‍βijk̲((xi,xj),(x,x′)),
for all x,x′∈X, where βij∈ℝ, for each 1≤i,j≤m.However, we are only interested in solutions that give rise to positive semidefinite kernels. The following condition over the hyperkernels [10] allows us to guarantee that the solution is a positive semidefinite kernel.Property 1.
Given a hyperkernelk̲  with elements such that for any fixed x̲∈X̲, the function k(xp,xq)=k̲(x̲,(xp,xq)), with xp,xq∈𝒳, is a positive semidefinite kernel, and βij≥0 for all i,j=1,…,m, then the kernel
(15)k(xp,xq)=∑i,j=1m‍βijk̲(xi,xj,xp,xq)
is positive semidefinite.Now, we address the problem of combining a finite set of dissimilarities. As we mentioned in Section2.3, each dissimilarity can be represented by a kernel using the Empirical Kernel Map. Next, the hyperkernel is defined as
(16)k̲(x̲,x′̲)=∑i=1n‍ciki(x̲)ki(x′̲),
where each ki is a positive semidefinite kernel of dissimilarities and ci is a constant ≥0.Now, we show thatk̲ is a valid hyperkernel. First, k̲ is a kernel because it can be written as a dot product 〈Φ̲(x̲),Φ̲(x′̲)〉 where
(17)Φ̲(x̲)=(c1k1(x̲),c2k2(x̲),…,cnkn(x̲)).
Next, the resulting kernel (15) is positive semidefinite because for all x̲,k̲(x̲,(xp,xq)) is a positive semidefinite kernel and βij can be constrained to be ≥0. Besides, the linear combination of kernels is a kernel and therefore is positive semidefinite. Notice that k̲(x̲,(xp,xq)) is positive semidefinite if ci≥0 and ki are pointwise positive for training data. Both RBF and multiquadratic kernels verify this condition.Finally, we show that the resulting kernel is a linear combination of the originalki. Substituting the expression of the hyperkernel (16) in (15), the kernel is written as
(18)k(xp,xq)=∑i,j=1m‍βij∑l=1n‍clkl(xi,xj)kl(xp,xq).
Now the kernel can be written as a linear combination of base kernels:
(19)k(xp,xq)=∑l=1n‍[cl∑i,j=1m‍βijkl(xi,xj)]kl(xp,xq).
Therefore, the above kernel introduces into the ν-SVM a linear combination of base dissimilarities represented by kl with coefficients γl=cl∑i,j=1m‍βijkl(xi,xj).The previous approach can be extended to an infinite family of distances. In this case, the space that generates the kernel is infinite dimensional. Therefore, in order to work in this space, it is necessary to define a hyperkernel and to optimize it using an HRKHS. Letk be a kernel of dissimilarities. The hyperkernel is defined as follows [10]:
(20)k̲(x̲,x′̲)=∑i=0∞‍ci(k(x̲)k(x′̲))i,
where ci≥0 and i=0,…,∞. In this case, the nonlinear transformation to feature space is infinite dimensional. Particularly, we are considering all powers of the original kernels which is equivalent to transform nonlinearly the original dissimilarities:
(21)Φ̲(x̲)=((c1)k(x̲),(c2)k2(x̲),…,(cn)kn(x̲)),
where n is the dimensionality of the space which is infinite in this case. As we mentioned in Section 2.1, nonlinear transformations of a given dissimilarity provide additional information that may help to improve the classifier performance.As for the finite family, it can be easily shown thatk̲ is a valid hyperkernel provided that the kernels considered are pointwise positive. The Inverse Multiquadratic kernel satisfies this condition. Next, we derive the hyperkernel expression for the multiquadratic kernel.Proposition 1 (see [Harmonic Hyperkernel]).
Suppose k is a kernel with range[0,1] and ci=(1-λh)λhi, i∈ℕ, 0<λh<1. Then, computing the infinite sum in (20), one has the following expression for the harmonic hyperkernel:
(22)k̲(x̲,x′̲)=(1-λh)∑i=0∞‍(λhk(x̲)k(x′̲))i=1-λh1-λhk(x̲)k(x′̲),λh is a regularization term that controls the complexity of the resulting kernel. Particularly, larger values for λh give more weight to strongly nonlinear kernels while smaller values give coverage for wider kernels.
In this paper one has considered the inverse multiquadratic kernel defined in (6). Substituting in (22), one gets the inverse multiquadratic hyperkernel:
(23)k̲(x̲,x̲′)=1-λh1-λh((∥x-x′∥2+c2)(∥x′′-x′′′∥2+c2))-1/2,
where x̲=(x,x′) and x′̲=(x′′,x′′′).


## 2.5.ν-SVM in an HRKHS

In this section, we detail how to learn the kernel for aν-Support Vector Machine in an HRKHS. First, we will introduce the optimization problem and next, we will explain shortly how to solve it using an SDP approach.We start some notation that is used in theν-SVM algorithm. For p,q,r∈ℝn, n∈ℕ let r=p∘q be defined as element by element  multiplication, ri=pi×qi. The pseudoinverse of a matrix K is denoted by K†. Define the hyperkernel Gram  matrix K̲ by K̲ijpq=k̲((xi,xj),(xp,xq)), the kernel matrix K=reshape(K̲β) (reshaping an m2 by 1 vector, K̲β, to an m×m matrix), Y=diag(y) (a matrix with y on the diagonal and zero otherwise), G(β)=YKY (the dependence on β is made explicit), and 1 is a vector of ones.Theν-SVM considered in this paper uses an l1 soft margin, where l(xi,yi,f(xi))=max(0,1-yif(xi)). This error is less sensitive to outliers which are convenient features for microarray datasets. Let ξi be the slack variables that allow for errors in the training set. Substituting in (13) Qemp by the one optimized by ν-SVM (8) the regularized quality functional in an HRKHS can be written as
(24)mink∈H̲minw∈ℋk1m∑i=1m‍ξi+12∥w∥ℋ2-νρ+λQ2∥k∥H̲2s.t.yif(xi)≥ρ-ξi,i=1,…,m,ξi≥0i=1,…,m,
where ν is the regularization parameter that achieves a balance between training error and the complexity of the approximating functions and λQ is a parameter that penalizes the complexity of the family of kernels considered.  The minimization of the previous equation leads to the following SDP optimization problem [10].
(25)minβ,γ,η,ξ,χ12t1-χν+1mξT1+λQ2t2(26)s.t.χ≥0,η≥0,ξ≥0,β≥0,(27)∥K̲1/2β∥≤t2,1Tβ=1,(28)[G(β)zzTt1]≽0,
where z=γy+χ1+η-ξThe value ofα which optimizes the corresponding Lagrange function is G(β)†z, and the classification function, f=sign(K(α∘y)-boffset), is given by
(29)f=sign(KG(β)†(y∘z)-γ),K̲ is the hyperkernel defined in Section 2.4 which represents the combination of dissimilarities considered. Finally, the algorithm proposed can be easily extended to deal with multiple classes via a one-against-one approach (OVO). This strategy is simple, more efficient computationally than the OVR, and compares well with more sophisticated multicategory SVM methods [15].


## 2.6. Implementation

The optimization problem (25) were solved using SeDuMi 1.1R3 [16] and YALMIP [17] SDP optimization packages running under MATLAB.As in the SDP problem there arem2 coefficients βij, the computational complexity is high. However, it can be significantly reduced if the Hyperkernel {k̲((xi,xj),·)∣1≤i,j≤m2} is approximated by a small fraction of terms, p≪m2 for a given error. In particular, we have chosen an m×p truncated lower triangular matrix G which approximate the hyperkernel matrix to an error δ=10-6 using the incomplete Cholesky factorization method [18].


## 2.7. Datasets and Preprocessing

The gene expression datasets considered in this paper correspond to several human cancer problems and exhibit different features as shown in Table1. We have considered both, binary and multi-category problems with a broad range of signal to noise ratio (Var/Samp.), different number of samples, and varying priors for the larger category. All the datasets are available from the Broad Institute of MIT and Harvard http://www.broad.mit.edu/cgi-bin/cancer/datasets.cgi/. Next we detail the features and preprocessing applied to each dataset.Table 1
Features of the different cancer datasets
ClasesSamplesGenesVar/Samp.Priors%Lymphoma DLBCL27768178875.3Lymphoma MLBCL/DLBCL22104492821384Breast cancer LN249712914551Medulloblastoma260712911965Breast cancer B349121324.752DLBCL survival C458379565.427DLBCL survival D4129379529.438The first dataset was obtained from77 patients with (diffuse large B-cell lymphoma) DLBCL (58 samples) or FL (follicular lymphoma) (19 samples) and they were subjected to transcriptional profiling using oligonucleotide Affymetrix gene chip  hu68000  containing probes for 6817 genes [19]. The second dataset consists of frozen tumors specimens from newly diagnosed, previously untreated MLBCL patients (34 samples) and DLBCL patients (176 samples). They were hybridized to Affymetrix hgu133b  gene chip containing probes for 44000 genes [20]. In both cases the raw intensities have been normalized using the rma algorithm [21] available from Bioconductor package [11]. The third problem we address concerns the clinically important issue of metastatic spread of the tumor. The determination of the extent of lymph node involvement in primary breast cancer is the single most important risk factor in disease outcome and here the analysis compares primary cancers that have not spread beyond the breast to ones that have metastasized to axillary lymph nodes at the time of diagnosis. We identified tumors as “reported negative’’ (24) when no positive lymph nodes were discovered and “reported positive’’ (25) for tumors with at least three identifiably positive nodes [22]. All assays used the human HuGeneFL Genechip microarray containing probes for 7129 genes. The fourth dataset [23] address the clinical challenge concerning medulloblastoma due to the variable response of patients to therapy. Whereas some patients are cured by chemotherapy and radiation, others have progressive disease. The dataset consists of 60 samples containing 39 medulloblastoma survivors and 21 treatment failures. Samples were hybridized to Affymetrix HuGeneFL arrays containing 5920 known genes and 897 expressed sequence tags.All the datasets have been standarized subtracting the median and dividing by the Inter-quantile range. The rescaling were performed based only on the training set to avoid bias.Regarding the identification of multiple classes of cancer we have considered three different datasets. The first one consists of49 samples of Breast Cancer generated using 1-channel oligonucleotide Affymetrix HuGeneFl [1]. The second and third datasets consist of 58 and a129 samples from Diffuse large B-cell lymphoma with survival data. Fourth different subclasses can be identified. Data preparatory steps have been performed by the authors of the primary study [1]. The 10% oligonucleotides with smaller Interquantile Range were filtered to remove genes with expression level constant across samples.


## 2.8. Performance Evaluation

In order to assure an honest evaluation of all the classifiers we have performed a double loop of crossvalidation [15]. The outer loop is based on stratified tenfold cross-validation that iteratively splits the data in ten sets, one for testing and the others for training. The inner loop perform stratified ninefold cross-validation over the training set and is used to estimate the optimal parameters avoiding overfitting. The stratified variant of cross-validation keeps the same proportion of patterns for each class in training and test sets. This is necessary in our problem because the class proportions are not equal. Finally, the error measure considered to evaluate the classifiers has been accuracy. This metric computes the proportion of samples misclassified. The accuracy is easy to interpret and allows us to compare with the results obtained by previously published studies.


## 2.9. Parameters for the Classification Algorithm

The parameters for theν-SVM and for the classifiers based on a linear combination of dissimilarities have been set up by a nested stratified tenfold crossvalidation procedure [15]. This method avoids the overfitting as is described in Section 2.8 and takes into account the asymmetric distribution of class priors.For theν-SVM we have considered both, linear and inverse multiquadratic kernels. The optimal parameters have been obtained by a grid search strategy over the following set of values: ν={0.1,0.2,0.3,0.4,0.5} and σ={d/2,d,2d}, where d denotes the dimensionality of the input space.Additionally, for the finite family of distancesci=1/M where M is the number of dissimilarities considered, and λQ=1 because the misclassification errors are hardly sensitive to the regularization parameter that controls the kernel complexity. Finally, for the infinite family of dissimilarities, the regularization parameter λh in the Harmonic hyperkernel (22) has been set up to 0.6 which gives an adequate coverage of various kernel widths. Smaller values emphasizes only wide kernels. All the base kernel of dissimilarities have been normalized so that all ones have the same scale.Regarding the Lanckriet [9] formalism that allows to combine a finite set of dissimilarities, several values for the regularization parameter C have been tried, C={0.1,1,10,100,1000}. A grid search strategy has been applied to determine the best values for both, the kernel parameters and the regularization parameter. The kernel matrices have been normalized by the trace as recommended in the original paper.


## 2.10. Gene Selection

Gene selection can improve significantly the classifier performance [24]. Therefore, we have evaluated the classifiers for the following subsets of genes {280,146,101,56,34}. The ν-SVM is robust against noise and is able to deal with high dimensional data. However, the empirical evidence suggests that considering a larger subset of genes or even the whole set of genes increases the misclassification errors.The genes are ranked according to the ratio of between-group to within-group sums of squares defined in [25]:
(30)BW(j)=∑i∑kI(yi=k)(x̅·j(k)-x̅·j)2∑i∑kI(yi=k)(xij-x̅·j(k))2,
where x̅·j(k) and x̅·j denote “respectively’’ the average expression level of gene j for class k and the overall average expression level of gene j across all samples, yi denotes the class of sample i, and I(·) is the indicator function. Next, the top ranked genes are chosen. This feature selection method is simple but compares well with more sophisticated methods [24]. Finally, the ranking of genes has been carried out considering only the training set to avoid bias. Therefore, feature selection is repeated in each iteration of cross-validation.


## 3. Results and Analysis

The algorithms proposed have been applied to the identification of several cancer human samples using microarray gene expression data.First, we address several binary categorization problems.Table2 reports the accuracy for the two combination approaches proposed in this paper. The first one considers the finite set of dissimilarities introduced in Section 2.1. The second one considers an infinite family of distances obtained by transforming nonlinearly the base dissimilarities to feature space. We have compared with the ν-SVM based on the best distance (linear and nonlinear kernel) and the classical ν-SVM. The performance for the Lanckriet formalism [9] that allow us to incorporate a finite linear combination of dissimilarities is also reported.Table 2
Accuracy for theν-SVM using a linear combination of non-Euclidean dissimilarities in an HRKHS. The ν-SVM based on the best distance and coordinates and the Lanckriet formalism have been taken as a reference.
TechniqueLimphomaLimphoma cell BBreast LNBrainν-SVM (coordinates)6.66%7.14%8.16%16.6%ν-SVM (best distance)6.66%5.71%8.16%13.3%ν-SVM (nonlinear kernel)6.25%5.71%8.16%11.6%Lanckriet (finite family)5%7.62%8.16%11.67%Finite family of distances5%7.14%10%10%Infinite family of distances5%5.71%8%8.33%Before computing the kernel of dissimilarities, all the distances have been transformed using the multiquadratic kernel introduced in Section2.1. This nonlinear transformation helps to improve the accuracy for all the techniques evaluated. From the analysis of Table 2, the following conclusions can be drawn.(i)
Theν-SVM based on a finite set of distances improves the ν-SVM based on the best dissimilarity for brain prognosis and Lymphoma datasets. The error is not reduced for Lymphoma cell B and Breast LN. This may be explained because the ratio (var/samp.) in Table 1 suggests that both datasets are quite noisy and nonlinear. The combination of a finite set of dissimilarities is not able to improve the separation between classes and increases slightly the overfitting of the data. Similarly, our algorithm helps to improve the SVM based on coordinates, particularly for the previous problems. We also report that working directly from a dissimilarity matrix may help to reduce the misclassification errors.(ii)
The infinite family of distances outperforms theν-SVM based on the best distance disregarding the kernel considered for all the datasets. The improvement is more relevant in brain cancer prognosis. Brain cancer prognosis is a complex problem according to the original study [23] and the nonlinear transformations of the dissimilarities help to reduce the misclassification errors. Besides, the infinite family improves the accuracy of the finite family of distances particularly for lymphoma cell B and Breast LN. This suggests that both datasets are nonlinear.(iii)
The Lanckriet formalism and the finite family of dissimilarities perform similarly. However, the infinite family of distances outperforms the Lanckriet formalism particularly for brain and Lymphoma cell B which are more complex problems.(iv)
The best distance depends on the dataset considered.Next we move to the categorization of multiple cancer types.Table3 compares the proposed algorithms with ν-SVM based on the best distance (linear and nonlinear kernel) and the classical ν-SVM. The accuracy for the Lanckriet formalism has also been reported. Our approach considers an infinite family of distances obtained by transforming nonlinearly the base dissimilarities to feature space.Table 3
Accuracy for theν-SVM using a linear combination of non-Euclidean dissimilarities in an HRKHS. The ν-SVM based on the best distance, the classical -SVM, and the Lanckriet formalism have been taken as a reference.
TechniqueBreast BDLBCL CDLBCL Dν-SVM (Coordinates)10.20%6.89%12.96%ν-SVM (Best Distance)8.6%6.89%14.81%ν-SVM (Nonlinear kernel)8.16%6.89%12.96%Lanckriet (finite family)8%10.3%25.2%Infinite family of distances6%5.33%16%Before computing the kernel of dissimilarities, all the distances have been transformed using the multiquadratic kernel introduced in Section2.1. From the analysis of Table 3, the following conclusions can be drawn.(i)
The combination of non-Euclidean dissimilarities helps to improve the SVM based on the best dissimilarity disregarding the kernel considered for the two first datasets. The error is slightly larger for the third dataset which may suggest that the problem is linear.(ii)
Our algorithm improves the SVM based on coordinates. The experimental results suggest that the nonlinear transformations of the dissimilarities help to increase the separation among classes.(iii)
The Hyperkernel classifier outperforms the Lanckriet formalism for multicategory problems. As the number of classes growths the number of samples per class comes down and the Lanckriet formalism seems to be less robust to overfitting.Finally, notice that our algorithm allow us to work with applications in with only a dissimilarity is defined. Moreover, we avoid the complex task of choosing a dissimilarity that reflects properly the proximities among the sample profiles.


## 4. Conclusions

In this paper, we propose two methods to incorporate in theν-SVM algorithm a linear combination of non-Euclidean dissimilarities. The family of distances is learnt in a (Hyper Reproducing Kernel Hilbert Space) HRKHS using a Semidefinite Programming approach. A penalty term has been added to avoid the overfitting of the data. The algorithm has been applied to the classification of complex cancer human samples.  The experimental results suggest that the combination of dissimilarities in a Hyper Reproducing Kernel Hilbert Space improves the accuracy of classifiers based on a single distance particularly for nonlinear problems. Besides, this approach outperforms the Lanckriet formalism specially for multi-category problems and is more robust to overfitting. Future research trends will focus on learning the combination of dissimilarities for other classifiers such as k-NN.



---

*Source: 906865-2009-06-21.xml*