Spectral Feature Scaling Method for Supervised Dimensionality Reduction

1 Introduction

Consider clustering a set of data samples with highdimensional features into mutually exclusive subsets, called clusters, and classifying these clusters when given prior knowledge on the class labels of partial samples. These kinds of problems arise in pathological diagnoses using gene expression data [Tarca et al., 2006], the analysis of chemical sensor data [Jurs et al., 2000], the community detection in social networks [Tichy et al., 1979], the analyses of neural spike sorting [Bar-Hillel et al., 2006], and so on [Sogh, 2006]. Spectral clustering is an unsupervised technique that projects the data samples to the eigenspace of the Laplacian matrix, in which the data samples are linearly separated if they are well clustered. This technique is more effective in complicated clustering than existing methods. For example, the k-means algorithm induces partitions using hyperplanes, but may fail to give satisfactory results due to irregularities and uncertainties of the features.

Here, we consider aggressively modifying the scales of the features to improve the separation in the reduced space, and obtain the desired classification. We derive the factors for scaling the features (scaling factors) using a learning machine based on spectral dimensionality reduction; namely, the inputs are unscaled and labeled samples, and the outputs are the scaling factors. To this end, by exploiting the prior knowledge on the labels of partial samples, we specify the Fiedler vector and reformulate the Laplacian eigenproblem as an eigenproblem of a linear matrix pencil whose eigenvector has the scaling factors. The obtained factors can modify the features of the entire samples to form clusters in the reduced dimensionality space according to the known labels. Thus, we use the prior knowledge to implicitly specify the phenomenon of interest, and supervise dimensionality reduction methods for the scaling factors. These approaches yield the desired clusters, incorporated with unsupervised spectral clustering, for test data scaled by the obtained factors for training data. Numerical experiments on artificial data and real-world data from gene expression profiles show that the feature scaling improves the accuracy of the spectral clustering. In addition, the spectral dimensionality reduction methods supervised using the feature scaling outperform existing methods in some cases, and are more robust than existing methods.

We review related work on supervised spectral dimensionality reduction methods. Learning a similarity matrix from training data is effective in spectral clustering [Bach and Jordan, 2003; Kamvar et al., 2003]. The proposed classification method can be considered a supervised method, incorporated with the kernel version of the locality preserving projections (LPP) [He and Niyogi, 2003]. LPP is comparable with the linear discriminant analyisis (LDA) [Belhumeur et al., 1997], the local Fisher discriminant analysis (LFDA) [Sugiyama, 2007], and the locality adaptive discriminant analysis (LADA) [Li et al., 2017]. Kernel versions of LDA, LPP and LFDA aim at nonlinear dimensionality reduction. These methods have semi-supervised variants [Song et al., 2008; Kulis et al., 2005; Cui and Fan, 2012].

1.1 Spectral Clustering

The underlying idea of the proposed methods follows from spectral clustering, which is induced by graph partitioning, where the graph is weighted and undirected. The weight wi,j of the edge between nodes i and j represents the similarity between samples i and j for i, j = 1, 2, . . . , n, where n is the number of samples. By dividing the graph into mutually exclusive subgraphs, the corresponding samples form clusters. This discrete problem can be continuously relaxed to a matrix eigenvalue problem. Let

e ∈ Rn be a vector with all elements 1, and t be an indicator vector with the ith entry ti = 1 if sample i is in a cluster, and ti = -1 if sample i is in another cluster. Then, the constrained minimization of the Ncut function [Shi and Malik, 2000]

over vi ∈ {1,-b} with b = ∑ti>0 di/ ∑ti<0 di, is relaxed to finding the Fiedler vector v ∈ Rn \ {0} [Fiedler, 1973] associated with the smallest eigenvalue of the constrained generalized eigenvalue problem

where L = D-W is a Laplacian matrix and λ ∈ R. The latter problem (2) is tractable, while the former (1) is NP-hard. Moreover, a few eigenvectors of (2) form clusters that are separable using hyperplanes if the samples form well-separated clusters. A sophisticated algorithm for (2) is nearly linear time [Spielman and Teng, 2014].

2 ProposedMethod

Irregular scales and uncertainty of features prevent wellestablished dimensionality reduction methods from clustering data samples into the desired disjoint subsets. In spectral clustering, the Ncut function is popular by virtue of the nonlinear separability, but is not versatile. To cope with these issues, we propose a remedy to aggressively modify the scales of the features in the eigenspace where a linear separation works, based on prior knowledge of the partial n samples X = [x1, x2, . . . , xn]T , xi ∈ Rm with m features. If the classes of partial samples are known, we can estimate the entries of the Fiedler vector v ∈ Rn \{0} of the Laplacian eigenvalue problem

where Ls = Ds -Ws, and Ws = {w(s) i,j } ∈ Rn×n depends on the feature scaling factors s ∈ Rm. We obtain the scaling factors s ∈ Rm in (3) by solving an eigenproblem of a linear matrix pencil. Then, applying the obtained scaling factors to the features of the entire data Y = [XT,RT]T ∈ RN×m with N samples, we can extend the prior knowledge on the partial samples to overall samples, where R ∈ R(N-n)×m denotes the remaining data. In statistical terms, the scaling changes the mean ¯ yj = 1n ∑ni=1 yi,j and the variance σ2 j = 1n ∑ni=1 (yi,j - ¯ yj)2 of the jth feature to s1/2 j ¯ yj and |sj |σ2 j , respectively, for j = 1, 2, . . . ,m. Note that we allow the scaling factors to have negative values. See [Schleif and Tino, 2015]. Finding appropriate scaling factors is also considered metric learning [Yang, 2006]. Recall that the center of a cluster associated with a Bregman divergence is equal to the centroid of the samples of the cluster [Banerjee et al., 2005].

Now, we reformulate (3) as another eigenproblem to extract the scaling factors si ∈ R, i = 1, 2, . . . ,m as an eigenvector. Denote the scaling matrix by S 1 2 = diag (s1, s2, . . . , sm) 1 2 ∈ Rm×m and denote the (i, j) entry of the similarity matrix Ws for the scaled data XS1/2 by

where s = [s1, s2, . . . , sm]T ∈ Rm and the kth entry of xi,j ∈ Rm is (xi,k -xj,k)2 . Here, we used the first-order approximation of the exponential function exp (-x) ≈ 1 - x for 0 < x < 1. Then, the ith row of Ws is

where ˜ ei is the n-dimensional vector with the ith entry equal to zero and the remaining entries ones, and Xi = 1 2σ2 [xi,1, xi,2, . . . , xi,n] ∈ Rm×n . Hence, we have

Let ˆxi = 1 2σ2 (xi,1 +xi,2 + · · · +xi,n) . Then, the ith diagonal entry d(s) i of Ds is

Hence, denoting the Fiedler vector by v = [v1, v2, . . . , vn]T , we have

Furthermore, the feature scaling factors s have the constraint

Therefore, we can obtain the scaling factors s by solving the generalized eigenproblem of a linear matrix pencil

where

It follows from the equality (A - B)T e = 0 that there exists a real number µ that satisfies (7). To solve (7), we can use the contour integral method [Morikuni, 2016] for n < m; otherwise, we can also use the minimal perturbation approach [Ito and Murota, 2016]. When s is obtained as a complex vector, its real and imaginary parts are also eigenvectors of (7). We took the real part in the experiments given in section 3. For µ = 1 - λ, we adopt the eigenvector of (7) associated with the eigenvalue µ closest to one as the scaling factors. Then, we apply the squared feature scaling factors s1/2 to the entire data Y , such that Z = Y S1/2 . Finally, we perform the spectral clustering or classification on the scaled data Z ∈ RN×m by solving the Laplacian eigenvalue problem

for a few eigenvectors corresponding to the smallest eigenvalues, where L′ = D′ -W ′ ∈ RN×N ,W ′ = {w′i,j } ∈ RN×N ,

zi ∈ Rm is the ith row of Z, d′i = ∑nj=1 w′i,j , and D′ = diag (d′1 , d′2 , . . . , d′N ). We summarize the procedures of the proposed methods in Algorithm 1.

3 Numerical Experiments

Numerical experiments on test problems were performed to compare the proposed methods with existing methods in terms of accuracy. For clustering problems, we compared the proposed method (spectral clustering method supervised using the feature scaling, SC-S) with the unsupervised spectral clustering method (SC) [Shi and Malik, 2000], LPP, its kernel version (KLPP) [He and Niyogi, 2003], and two supervised methods, LFDA and its kernel version (KLFDA) [Sugiyama, 2007]. For classification problems, we compared the proposed method (spectral classification method supervised using the feature scaling, SC-S) with LPP, KLPP, LFDA, and KLFDA. All programs were coded and run in Matlab 2016b.

Algorithm 1 Spectral clustering/classification methods supervised using the feature scaling

Input: Training data X ∈ Rn×m, entire data Y ∈ RN×m, estimated Fiedler vector v, dimension of the reduced space ℓ.

• 1: Compute A,B,α, β, γ, ρ in (5), (6), (8).
• 2: Solve (7) for an eigenvector s = [s1, s2, . . . , sm]T .
• 3: Set the scaling matrix S1/2 = diag(s1, s2, . . . , sm)1/2 .
• 4: Compute the scaled data matrix Z = Y S1/2 .
• 5: Compute the similarity matrix W ′ ∈ RN×N (9) and D′ , using the k-nearest neighbors, and set L′ = D′ - W ′ .
• 6: Solve L′u = λ′D′u for the eigenvectors u1,u2 . . . uℓ corresponding to the ℓ nonzero smallest eigenvalues.
• 7: Cluster/classify the reduced data samples [u1,u2, . . . , uℓ] ∈ RN×ℓ rowwise by using the kmeans algorithm/the one-nearest neighborhood method, respectively.

We employed the LPP code in the Matlab Toolbox for Dimensionality Reduction 1 and the LFDA and KLFDA codes in the Sugiyama-Sato-Honda Lab site 2 . In the compared methods except for LFDA, we chose the optimal value of the parameter σ among 1, 10±1 , and 10±2 to achieve the best accuracy. We formed the similarity matrix in (9) by using the sevennearest neighbor and taking the symmetric part. We set the dimensions of the reduced space to one for clustering problems, and one, two and three for classification problems. It is known that using one eigenvector is sufficient for binary clustering if the clusters are well-separated [Chung, 1996]. The reduced data samples to a low-dimension were clustered using the k-means algorithm, and classified using the onenearest neighborhood method.

The performance measures we used were the normalized mutual information (NMI) [Strehl and Ghosh, 2002] and the Rand index (RI) [Rand, 1971] for evaluating the clustering methods, and RI for evaluating the classification methods. Let ni be the number of samples in cluster/class i, ˆni be the number of samples clustered/classified by a method to cluster/class i, and ni,j be the number of samples in cluster/class i clustered/classified by a method to cluster/class j. Then, the NMI measure for binary clustering is defined by

Next, let TP (true positive) denote the number of samples which are correctly identified as class 1, FP (false positive) denote the number of samples which are incorrectly identified as class 1, TN (true negative) denote the number of samples which are correctly identified as class 2, FN (false negative) denote the number of samples which are incorrectly identified as class 2. Then, the RI measure is defined by

1 https://lvdmaaten.github.io/drtoolbox/

2 http://www.ms.k.u-tokyo.ac.jp/software.html

As the obtained clustering and classification become more accurate, the values of NMI and RI become large.

3.1 Artificial Data

In this subsection, we use toy problems of data sets consisting of 800 samples with 10 features. Figure 1 shows three of the 10 features, where the symbols ◦ and + denote the data samples in different classes, and the remaining seven features were given uniformly distributed random numbers in the interval [0, 1]. The original data were normalized to have a mean of zero and variance one. We set the entries of the Fiedler vector v to vi = 1 if sample i is in a cluster, and vi = -0.2 if sample i is in another cluster (see (1)). We repeated clustering the same reduced data samples 20 times using the k-means algorithm and the one-nearest neighborhood method, starting with different random initial guesses. Moreover, we tested on different proportions of training data from 5% to 50%, and repeated each test 10 times with different random choices of training data. Thus, we report the average performance by taking the arithmetic mean of RI and NMI.

Figures 2 and 3 show the means and standard deviations of RI and NMI, respectively, for the clustering problems. SC-S performed the best in terms of accuracy among the compared methods. The value of RI for SC-S, LFDA, and KLFDA tended to increase with the proportion of training data used. On the other hand, the accuracies of clustering using SC, LPP, and KLPP were similar for different proportions of training data.

Figure 4 shows the means and standard deviations of RI for the classification problems, where the reduced dimensions are ℓ = 1, 2, and, 3. SC-S performed the best in terms of accuracy for proportions of training data of 5-50% with few exceptions among the compared methods. As the proportion of training data increased, the accuracy of the compared methods tended to increase.

Figure 5 shows the values of the scaling factors for each feature when using 50% of the entire data for training. Since the fourth to tenth features given by random numbers were not involved in the classification, the values of the scaling factors of these seven features were small. Thus, the values of the scaling factors indicated which features were effective for the desired classification.

Figure 6 shows the data samples reduced to a onedimensional space for each method when using 50% of all data for training. SC-S reduced all data to one dimension, and made it linearly separable to the true clusters. KLFDA failed to reduce the data samples to be linearly separable to the true clusters.

Table 1 gives the means and standard deviations of RI through the leave-one-out cross-validation for the classification problems for reduced dimensions ℓ = 1, 2, and 3. Table 1 shows that SC-S was immune from an overfitting in the learning process.

3.2 GEOData Sets

In this subsection, we use four data sets in the Gene Expression Omunibus 3 from real-world problems with more features than samples. Table 2 gives the specifications of the data sets, where IPF denotes Idiopathic Pulmonary Fibrosis. Each data set has two binary classes: diseased patients and healthy peoples. We chose 50% of the entire data for training and repeated each test 10 times with different choices of the training data. The entries of the Fiedler vector v were set to vi = 1 if sample i is in a cluster, and vi = -1 if sample i is in another cluster (see (1)).

3 https://www.ncbi.nlm.nih.gov/

Tables 3 and 4 give the means and standard deviations of RI and NMI, respectively, for each data set for the clustering problems. The symbol ∗ denotes the largest values of RI and NMI for each data set. SC-S performed the best in terms of accuracy for two data sets, and second best for two data sets among the compared methods. LFDA performed the best in terms of accuracy for one data set, second best for one data set but worst for one data set among the compared methods. These results showed that SC-S was more robust than other methods.

Table 5 gives the means and standard deviations of RI for the classification problems for the reduced dimensions ℓ = 1, 2, and 3. SC-S was best in average in terms of accuracy for Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence (IJCAI-18)

three data sets, except for Ovarian with ℓ = 1. LFDA was best in terms of accuracy for Ovarian with ℓ = 1, and for IPF with ℓ = 3. KLFDA was best in terms of accuracy for IPF. SC-S became more accurate, as the number of eigenvectors ℓ used increased for Ovarian.

It is known that the cross-validation is unreliable in small sample classification [Isaksson et al., 2008]. Indeed, we observed significantly large values of the standard deviation for the compared methods for the data sets.

4 Conclusions

We considered the dimensionality reduction of highdimensional data. To deal with irregularity or uncertainty in features, we proposed supervised dimensionality reduction methods that exploit knowledge on the labels of partial samples. With the supervision, we modify the features' variances and means. Moreover, the feature scaling can reduce those features that prevent us from obtaining the desired clusters. To obtain the factors used to scale the features, we formulated an eigenproblem of a linear matrix pencil whose eigenvector has the feature scaling factors, and described the procedures for the proposed methods. Numerical experiments showed that the feature scaling is effective when combined with spectral clustering and classification methods. For toy problems with more samples than features, the feature scaling improved the accuracy of the unsupervised spectral clustering, and the proposed methods outperformed several existing methods. For real-world problems with more features than samples from gene expression profiles, the proposed method was more robust in terms of clustering than well-established methods, and outperformed existing methods in some cases.

Acknowledgements

We would like to thank Doctor Akira Imakura for his valuable comments. The second author was supported in part by JSPS KAKENHI Grant Number 15K04768 and the Hattori Hokokai Foundation. The third author was supported by JST/CREST, Japan.