---
abstract: 'Spectral dimensionality reduction methods enable linear separations of complex data with high-dimensional features in a reduced space. However, these methods do not always give the desired results due to irregularities or uncertainties of the data. Thus, we consider aggressively modifying the scales of the features to obtain the desired classification. Using prior knowledge on the labels of partial samples to specify the Fiedler vector, we formulate an eigenvalue problem of a linear matrix pencil whose eigenvector has the feature scaling factors. The resulting factors can modify the features of entire samples to form clusters in the reduced space, according to the known labels. In this study, we propose new dimensionality reduction methods supervised using the feature scaling associated with the spectral clustering. Numerical experiments show that the proposed methods outperform well-established supervised methods for toy problems with more samples than features, and are more robust regarding clustering than existing methods. Also, the proposed methods outperform existing methods regarding classification for real-world problems with more features than samples of gene expression profiles of cancer diseases. Furthermore, the feature scaling tends to improve the clustering and classification accuracies of existing unsupervised methods, as the proportion of training data increases.'
author:
- |
    Momo Matsuda$^1$, Keiichi Morikuni$^1$, Tetsuya Sakurai$^{1,2}$\
    $^1$ University of Tsukuba\
    $^2$ JST/CREST\
    matsuda@mma.cs.tsukuba.ac.jp
bibliography:
- 'arXiv.bib'
title: |
    Spectral Feature Scaling Method\
    for Supervised Dimensionality Reduction
---

Introduction
============

Consider clustering a set of data samples with high-dimensional 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 [@gene], the analysis of chemical sensor data [@sensor], the community detection in social networks [@network], the analyses of neural spike sorting [@spike], and so on [@detection]. 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 [@super1; @super2]. The proposed classification method can be considered a supervised method, incorporated with the kernel version of the locality preserving projections (LPP) [@lpp]. LPP is comparable with the linear discriminant analyisis (LDA) [@lda], the local Fisher discriminant analysis (LFDA) [@lfda], and the locality adaptive discriminant analysis (LADA) [@lada]. Kernel versions of LDA, LPP and LFDA aim at nonlinear dimensionality reduction. These methods have semi-supervised variants [@uni; @semisuper; @Cui].

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 $w_{i,j}$ of the edge between nodes $i$ and $j$ represents the similarity between samples $i$ and $j$ for $i, j = 1, 2, \ldots, 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 $$\begin{aligned}
  W&=\lbrace w_{i,j}\rbrace\in{\mathbb{R}}^{n\times n}, \\
  D&=\mathrm{diag}\left(d_1,d_2,\ldots,d_n\right)\in{\mathbb{R}}^{n\times n} \quad \mbox{ with } \quad d_i = \sum_{i=1}^n w_{i,j},  \end{aligned}$$ $\bm{e}\in{\mathbb{R}}^n$ be a vector with all elements $1$, and $\bm{t}$ be an indicator vector with the $i$th entry $t_i = 1$ if sample $i$ is in a cluster, and $t_i = -1$ if sample $i$ is in another cluster. Then, the constrained minimization of the Ncut function [@sc] $$\min_{\bm{v}} \frac{\bm{v}^{\mathsf{T}} (D - W) \bm{v}}{\bm{v}^{\mathsf{T}}D\bm{v}}, \quad \mbox{subject to} \quad \bm{e}^{\mathsf{T}}D\bm{v} = 0
  \label{eq:j}$$ over $v_i \in \{ 1, -b \}$ with $b = \sum_{t_i > 0}d_i \slash \sum_{t_i<0}d_i$, is relaxed to finding the Fiedler vector $\bm{v} \in {\mathbb{R}}^n \setminus \{ \bm{0} \}$ [@fiedler] associated with the smallest eigenvalue of the constrained generalized eigenvalue problem $$L\bm{v} = \lambda D \bm{v}, \quad \mbox{subject to} \quad \bm{e}^{\mathsf{T}}D\bm{v} = 0,
  \label{eq:lap}$$ where $L = D - W$ is a Laplacian matrix and $\lambda \in {\mathbb{R}}$. The latter problem (\[eq:lap\]) is tractable, while the former (\[eq:j\]) is NP-hard. Moreover, a few eigenvectors of (\[eq:lap\]) form clusters that are separable using hyperplanes if the samples form well-separated clusters. A sophisticated algorithm for (\[eq:lap\]) is nearly linear time [@time].

Proposed Method
===============

Irregular scales and uncertainty of features prevent well-established 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 = \left[\bm{x}_1, \bm{x}_2, \ldots, \bm{x}_n\right]^{\mathsf{T}}, \bm{x}_i\in{\mathbb{R}}^m$ with $m$ features. If the classes of partial samples are known, we can estimate the entries of the Fiedler vector $\bm{v}\in{\mathbb{R}}^n\backslash\lbrace\bm{0}\rbrace$ of the Laplacian eigenvalue problem $$L_s \bm{v} = \lambda_s D_s \bm{v}, \quad \bm{e}^{\mathsf{T}}D_s \bm{v} = \bm{0}, \quad \lambda_s \in {\mathbb{R}},
  \label{eq:LS}$$ where $L_s = D_s - W_s$, and $W_s = \lbrace w_{i,j}^{(s)} \rbrace \in {\mathbb{R}}^{n\times n}$ depends on the feature scaling factors $\bm{s}\in{\mathbb{R}}^m$. We obtain the scaling factors $\bm{s}\in{\mathbb{R}}^m$ in (\[eq:LS\]) by solving an eigenproblem of a linear matrix pencil. Then, applying the obtained scaling factors to the features of the entire data $Y = \left[X^{{\mathsf{T}}}, R^{\mathsf{T}}\right]^{\mathsf{T}}\in{\mathbb{R}}^{N \times m}$ with $N$ samples, we can extend the prior knowledge on the partial samples to overall samples, where $R\in{\mathbb{R}}^{(N-n)\times m}$ denotes the remaining data. In statistical terms, the scaling changes the mean $\bar{y}_j = \frac{1}{n}\sum_{i=1}^n y_{i,j}$ and the variance $\sigma_j^2 = \frac{1}{n} \sum_{i=1}^n (y_{i,j} - \bar{y}_j)^2$ of the $j$th feature to $s_j^{1/2}\bar{y}_j$ and $|s_j|\sigma_j^2$, respectively, for $j = 1, 2, \ldots, m$. Note that we allow the scaling factors to have negative values. See [@negative]. Finding appropriate scaling factors is also considered metric learning [@metric]. Recall that the center of a cluster associated with a Bregman divergence is equal to the centroid of the samples of the cluster [@diver].

Now, we reformulate (\[eq:LS\]) as another eigenproblem to extract the scaling factors $s_i\in{\mathbb{R}},i = 1, 2, \ldots, m$ as an eigenvector. Denote the scaling matrix by $S^{\frac{1}{2}}=\mathrm{diag}\left(s_1, s_2, \ldots, s_m\right)^{\frac{1}{2}}\in~{\mathbb{R}}^{m \times m}$ and denote the $(i,j)$ entry of the similarity matrix $W_s$ for the scaled data $XS^{1/2}$ by $$\begin{aligned}
  w_{i,j}^{(s)} = \begin{cases}
    1 - \frac{\left( \bm{x}_i - \bm{x}_j \right)^{{\mathsf{T}}} S \left( \bm{x}_i - \bm{x}_j \right)}{2\sigma^2}  = 1 - \frac{\bm{s}^{\mathsf{T}} \bm{x}_{i,j}}{2\sigma^2}, \\
    \quad \simeq \exp\left(- \frac{\left( \bm{x}_i - \bm{x}_j \right)^{{\mathsf{T}}} S \left( \bm{x}_i - \bm{x}_j \right)}{2\sigma^2}\right),& i \neq j,\\
    & \\
    0, & i = j,
  \end{cases}
         \label{eq:weight}\end{aligned}$$ where $\bm{s} = \left[ s_1, s_2, \ldots, s_m\right]^{\mathsf{T}}\in{\mathbb{R}}^m$ and the $k$th entry of $\bm{x}_{i,j}\in{\mathbb{R}}^m$ is $\left(x_{i,k} - x_{j,k}\right)^2$. Here, we used the first-order approximation of the exponential function $\exp\left(-x\right) \approx 1 - x \quad\mbox{for}\quad0<x<1.$ Then, the $i$th row of $W_s$ is $$\begin{split}
    \bm{w}_i^{(s){\mathsf{T}}}& = \left[1,\ldots,1,0,1,\ldots,1\right]-\frac{\bm{s}^{\mathsf{T}}}{2\sigma^2}\left[\bm{x}_{i,1},\bm{x}_{i,2},\ldots,\bm{x}_{i,n}\right]\\
    & = \tilde{\bm{e}}_i^{\mathsf{T}}-\bm{s}^{\mathsf{T}}X_i,
  \end{split}$$ where $\tilde{\bm{e}}_i$ is the $n$-dimensional vector with the $i$th entry equal to zero and the remaining entries ones, and $X_i = \frac{1}{2\sigma^2}\left[\bm{x}_{i,1},\bm{x}_{i,2},\ldots,\bm{x}_{i,n}\right] \in{\mathbb{R}}^{m\times n}.$ Hence, we have $$W_s\bm{v} = \left[\tilde{\bm{e}}_1^{\mathsf{T}}, \tilde{\bm{e}}_2^{\mathsf{T}}, \ldots, \tilde{\bm{e}}_n^{\mathsf{T}}\right]^{\mathsf{T}}\bm{v} - \left[X_1\bm{v}, X_2\bm{v}, \ldots, X_n\bm{v}\right]^{\mathsf{T}}\bm{s}.$$ Let $\hat{\bm{x}}_i = \frac{1}{2\sigma^2}\left(\bm{x}_{i,1} + \bm{x}_{i,2} + \cdots + \bm{x}_{i,n}\right).$ Then, the $i$th diagonal entry $d_i^{(s)}$ of $D_s$ is $$d_i^{(s)} = \sum_{j=1}^nw_{i,j}^{(s)} = (n-1) - \bm{s}^{\mathsf{T}}\hat{\bm{x}}_i.$$ Hence, denoting the Fiedler vector by $\bm{v} = \left[ v_1, v_2, \ldots, v_n \right]^{\mathsf{T}}$, we have $$\begin{aligned}
  D_s\bm{v} = (n-1)\bm{v} - \left[v_1\hat{\bm{x}}_1, v_2\hat{\bm{x}}_2, \ldots, v_n\hat{\bm{x}}_n\right]^{\mathsf{T}}\bm{s}.\end{aligned}$$ Thus, (\[eq:LS\]) is written as $$\begin{aligned}
  L_s\bm{v} = \lambda_sD_s\bm{v} &\Leftrightarrow& W_s\bm{v} = (1 - \lambda_s)D_s\bm{v}\\
                                 &\Leftrightarrow&
                                                   \begin{bmatrix}
                                                     A & \bm{\alpha}\\
                                                   \end{bmatrix}
  \begin{bmatrix}
    \bm{s}\\
    -1\\    
  \end{bmatrix} = \mu
  \begin{bmatrix}
    B & \bm{\beta}
  \end{bmatrix}
        \begin{bmatrix}
          \bm{s}\\
          -1
        \end{bmatrix},\end{aligned}$$ where $\mu = 1 - \lambda_s$, $$\begin{aligned}
  A =
  \begin{bmatrix}
    \left(X_1\bm{v}\right)^{\mathsf{T}}\\
    \left(X_2\bm{v}\right)^{\mathsf{T}}\\
    \vdots\\
    \left(X_n\bm{v}\right)^{\mathsf{T}}\\
  \end{bmatrix}, \quad B =
  \begin{bmatrix}
    v_1\hat{\bm{x}}_1^{\mathsf{T}}\\
    v_2\hat{\bm{x}}_2^{\mathsf{T}}\\
    \vdots\\
    v_n\hat{\bm{x}}_n^{\mathsf{T}}\\
  \end{bmatrix}\in{\mathbb{R}}^{n\times m},
  \label{eq:AB}\end{aligned}$$ $$\begin{aligned}
  \bm{\alpha} = \left[\tilde{\bm{e}}_1, \tilde{\bm{e}}_2, \ldots, \tilde{\bm{e}}_n\right]^{\mathsf{T}}\bm{v}\in{\mathbb{R}}^n,\quad \bm{\beta} = (n-1)\bm{v}\in{\mathbb{R}}^n.
  \label{eq:so}\end{aligned}$$ Furthermore, the feature scaling factors $\bm{s}$ have the constraint $$\begin{aligned}
  &&\bm{e}^{\mathsf{T}}D_s\bm{v} = \sum_{i=1}^n\left((n-1)v_i - v_i\bm{s}^{\mathsf{T}}\hat{\bm{x}}_i\right) = 0\\
  &\Leftrightarrow& \left(\sum_{i=1}^nv_i\hat{\bm{x}}_i^{\mathsf{T}}\right)\bm{s} - (n-1)\sum_{i=1}^n v_i = 0.\end{aligned}$$ Therefore, we can obtain the scaling factors $\bm{s}$ by solving the generalized eigenproblem of a linear matrix pencil $$\begin{aligned}
  \begin{bmatrix}
    A & \bm{\alpha}\\
    \bm{\gamma}^{\mathsf{T}}& \rho
  \end{bmatrix}
                     \begin{bmatrix}
                       \bm{s}\\
                       -1
                     \end{bmatrix} = \mu
  \begin{bmatrix}
    B & \bm{\beta}\\
    \bm{0}^{\mathsf{T}}& 0    
  \end{bmatrix}
                \begin{bmatrix}
                  \bm{s}\\
                  -1
                \end{bmatrix}, \quad \bm{s}\in{\mathbb{R}}^m, \quad \mu\in{\mathbb{R}},
  \label{eq:rec}\end{aligned}$$ where $$\begin{aligned}
  \bm{\gamma} = \sum_{i=1}^nv_i\hat{\bm{x}}_i\in{\mathbb{R}}^m, \quad \rho = (n-1)\sum_{i=1}^nv_i\in{\mathbb{R}}.
  \label{eq:gammarho}\end{aligned}$$ It follows from the equality $\left( A - B \right)^{\mathsf{T}}\bm{e} = \bm{0}$ that there exists a real number $\mu$ that satisfies (\[eq:rec\]). To solve (\[eq:rec\]), we can use the contour integral method [@ss] for $n < m$; otherwise, we can also use the minimal perturbation approach [@svd]. When $\bm{s}$ is obtained as a complex vector, its real and imaginary parts are also eigenvectors of (\[eq:rec\]). We took the real part in the experiments given in section \[expe\]. For $\mu = 1 - \lambda$, we adopt the eigenvector of (\[eq:rec\]) associated with the eigenvalue $\mu$ closest to one as the scaling factors. Then, we apply the squared feature scaling factors $\bm{s}^{1/2}$ to the entire data $Y$, such that $Z = YS^{1/2}$. Finally, we perform the spectral clustering or classification on the scaled data $Z \in{\mathbb{R}}^{N\times m}$ by solving the Laplacian eigenvalue problem $$L' \bm{u} = \lambda' D' \bm{u}, \quad \bm{e}^{{\mathsf{T}}}\!D'\bm{u} = 0, \quad \bm{u}\in\mathbb{R}^N\setminus\lbrace\bm{0}\rbrace, \quad \lambda' \in \mathbb{R}$$ for a few eigenvectors corresponding to the smallest eigenvalues, where $L'=D'-W'\in{\mathbb{R}}^{N \times N}, W' = \lbrace w'_{i,j} \rbrace \in {\mathbb{R}}^{N \times N}$, $$w'_{i,j} = \exp\left(-\frac{{\| \bm{z}_i - \bm{z}_j \|_2}^2 }{2 \sigma^2}\right),\quad  i, j = 1, 2 \ldots, N,
  \label{eq:w}$$ $\bm{z}_i \in {\mathbb{R}}^m$ is the $i$th row of $Z$, $d'_i=\sum_{j=1}^n w'_{i,j}$, and $D'=\mathrm{diag} \left(d'_1, d'_2, \ldots, d'_N\right)$. We summarize the procedures of the proposed methods in Algorithm \[alg1\].

Training data $X \in \mathbb{R}^{n \times m}$, entire data $Y \in \mathbb{R}^{N \times m}$, estimated Fiedler vector $\bm{v}$, dimension of the reduced space $\ell$. Compute $A, B, \bm{\alpha}, \bm{\beta}, \bm{\gamma}, \rho$ in (\[eq:AB\]), (\[eq:so\]), (\[eq:gammarho\]). Solve (\[eq:rec\]) for an eigenvector $\bm{s} = [s_1, s_2, \ldots, s_m]^{\mathsf{T}}$. Set the scaling matrix $S^{1/2} = \mathrm{diag}(s_1, s_2, \ldots, s_m)^{1/2}$. Compute the scaled data matrix $Z = YS^{1/2}$. Compute the similarity matrix $W' \in \mathbb{R}^{N \times N}$ (\[eq:w\]) and $D'$, using the $k$-nearest neighbors, and set $L' = D' - W'$. Solve $L'\bm{u} = \lambda' D' \bm{u}$ for the eigenvectors $\bm{u}_1,\bm{u}_2 \ldots \bm{u}_\ell$ corresponding to the $\ell$ nonzero smallest eigenvalues. Cluster/classify the reduced data samples $\left[\bm{u}_1,\bm{u}_2,\ldots,\bm{u}_\ell\right]\in{\mathbb{R}}^{N \times\ell}$ rowwise by using the $k$-means algorithm/the one-nearest neighborhood method, respectively.

Numerical experiments {#expe}
=====================

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) [@sc], LPP, its kernel version (KLPP) [@lpp], and two supervised methods, LFDA and its kernel version (KLFDA) [@lfda]. 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. 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 $\sigma$ among $1, 10^{\pm1}$, and $10^{\pm2}$ to achieve the best accuracy. We formed the similarity matrix in (\[eq:w\]) by using the seven-nearest 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 [@theroy]. The reduced data samples to a low-dimension were clustered using the $k$-means algorithm, and classified using the one-nearest neighborhood method.

The performance measures we used were the normalized mutual information (NMI) [@nmi] and the Rand index (RI) [@randindex] for evaluating the clustering methods, and RI for evaluating the classification methods. Let $n_i$ be the number of samples in cluster/class $i$, $\hat{n}_i$ be the number of samples clustered/classified by a method to cluster/class $i$, and $n_{i,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 $$\mbox{NMI} = \frac{\sum_{i=1}^2 \sum_{j=1}^{2} n_{i,j} \log\left(n \cdot n_{i,j} / \left(n_i \cdot n'_j\right)\right)}{\sqrt{\left(\sum_{i=1}^2 n_i \log\left(n_i / n\right)\right)\left(\sum_{j=1}^{2} n'_j \log\left(n'_j / n\right)\right)}}.$$ 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 $${\rm RI} = \frac{{\rm TP} + {\rm TN}}{{\rm TP} + {\rm TN} + {\rm FP} + {\rm FN}}.$$ As the obtained clustering and classification become more accurate, the values of NMI and RI become large.

Artificial Data
---------------

In this subsection, we use toy problems of data sets consisting of 800 samples with 10 features. Figure \[fig:arti\] shows three of the 10 features, where the symbols $\circ$ and + denote the data samples in different classes, and the remaining seven features were given uniformly distributed random numbers in the interval $\left[0, 1 \right]$. The original data were normalized to have a mean of zero and variance one. We set the entries of the Fiedler vector $\bm{v}$ to $v_i = 1$ if sample $i$ is in a cluster, and $v_i = -0.2$ if sample $i$ is in another cluster (see (\[eq:j\])). 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 \[fig:ACC\] and \[fig:NMI\] 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 \[fig:KNN\] shows the means and standard deviations of RI for the classification problems, where the reduced dimensions are $\ell = 1,2, \mbox{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 \[fig:sf\] 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 \[fig:onespace\] shows the data samples reduced to a one-dimensional 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 \[tb:arti\] gives the means and standard deviations of RI through the leave-one-out cross validation for the classification problems for reduced dimensions $\ell = 1,2,$ and $3$. Table \[tb:arti\] shows that SC-S was immune from an overfitting in the learning process.

![Proportion of training data vs. RI for classification of artificia.l data for reduced dimensions $\ell = 1, 2,$ and $3$[]{data-label="fig:KNN"}](arti.pdf)

![Proportion of training data vs. RI for classification of artificia.l data for reduced dimensions $\ell = 1, 2,$ and $3$[]{data-label="fig:KNN"}](rebuttal_1eigKNN.pdf "fig:")\
(a) One dimension

![Proportion of training data vs. RI for classification of artificia.l data for reduced dimensions $\ell = 1, 2,$ and $3$[]{data-label="fig:KNN"}](rebuttal_2eigKNN.pdf "fig:")\
(b) Two dimensions

![Proportion of training data vs. RI for classification of artificia.l data for reduced dimensions $\ell = 1, 2,$ and $3$[]{data-label="fig:KNN"}](rebuttal_3eigKNN.pdf "fig:")\
(c) Three dimensions

![Values of the scaling factors[]{data-label="fig:sf"}](sf.pdf)

\
(a) SC-S\

\
(b) SC\

\
(c) KLFDA

  $\quad \ell$           1                 2                 3
  -------------- ----------------- ----------------- -----------------
  SC-S            \*100.0$\pm$0.0   \*100.0$\pm$0.0   \*100.0$\pm$0.0
  LPP              77.0$\pm$40.1     89.6$\pm$30.5     99.9$\pm$3.5
  KLPP             52.4$\pm$49.9     52.4$\pm$50.0     52.4$\pm$49.9
  LFDA             78.4$\pm$41.2     83.9$\pm$36.8     81.4$\pm$38.9
  KLFDA            86.8$\pm$33.9     86.9$\pm$33.8     87.0$\pm$33.6

  : RI (mean% $\pm$ std) for classification of artificial data sets[]{data-label="tb:arti"}

GEO Data 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 \[tb:geo\] 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 $\bm{v}$ were set to $v_i = 1$ if sample $i$ is in a cluster, and $v_i = -1$ if sample $i$ is in another cluster (see (\[eq:j\])).

Tables \[tb:accresult\] and \[tb:nmiresult\] give the means and standard deviations of RI and NMI, respectively, for each data set for the clustering problems. The symbol $\ast$ 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 \[tb:error\] gives the means and standard deviations of RI for the classification problems for the reduced dimensions $\ell = 1, 2,$ and $3$. SC-S was best in average in terms of accuracy for three data sets, except for Ovarian with $\ell = 1$. LFDA was best in terms of accuracy for Ovarian with $\ell = 1$, and for IPF with $\ell = 3$. KLFDA was best in terms of accuracy for IPF. SC-S became more accurate, as the number of eigenvectors $\ell$ used increased for Ovarian.

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

  ------------------- ---- ---- -------
                                
  \[2pt\]                       
  \[-10pt\] Ovarian    11   22   54675
  Pancreatic           12   24   54675
  IPF                  12   23   54613
  Colorectral          11   22   54675
  ------------------- ---- ---- -------

  : NMI (mean $\pm$ std) for clustering GEO data sets[]{data-label="tb:nmiresult"}

  Data set         Ovarian           Pancreatic         
  ---------- ------------------- ------------------- -- --
  SC           52.6 $\pm$ 0.05     54.2 $\pm$ 0.00      
  SC-S        \*60.2 $\pm$ 1.11    56.0 $\pm$ 1.22      
  LPP          57.0 $\pm$ 1.47    \*59.5 $\pm$ 1.20     
  KLPP         54.6 $\pm$ 0.00     54.2 $\pm$ 0.00      
  LFDA         57.9 $\pm$ 1.77     55.1 $\pm$ 1.57      
  KLFDA        56.4 $\pm$ 0.05     51.0 $\pm$ 0.08      

  : NMI (mean $\pm$ std) for clustering GEO data sets[]{data-label="tb:nmiresult"}

  Data set           IPF             Colorectal
  ---------- ------------------- -------------------
  SC           69.6 $\pm$ 0.00     50.0 $\pm$ 0.00
  SC-S         76.1 $\pm$ 0.00    \*74.1 $\pm$ 1.10
  LPP          76.7 $\pm$ 2.12     57.8 $\pm$ 1.33
  KLPP         71.3 $\pm$ 0.00     53.2 $\pm$ 0.00
  LFDA         70.0 $\pm$ 4.34     54.3 $\pm$ 2.01
  KLFDA       \*79.9 $\pm$ 0.12    63.4 $\pm$ 0.25

  : NMI (mean $\pm$ std) for clustering GEO data sets[]{data-label="tb:nmiresult"}

  Data set          Ovarian             Pancreatic          
  ---------- --------------------- --------------------- -- --
  SC           0.004 $\pm$ 0.000     0.043 $\pm$ 0.000      
  SC-S        \*0.082 $\pm$ 0.019    0.042 $\pm$ 0.010      
  LPP          0.044 $\pm$ 0.024    \*0.053 $\pm$ 0.022     
  KLPP         0.006 $\pm$ 0.000     0.039 $\pm$ 0.000      
  LFDA         0.057 $\pm$ 0.021     0.040 $\pm$ 0.021      
  KLFDA        0.067 $\pm$ 0.001     0.005 $\pm$ 0.000      

  : NMI (mean $\pm$ std) for clustering GEO data sets[]{data-label="tb:nmiresult"}

  Data set            IPF               Colorectal
  ---------- --------------------- ---------------------
  SC           0.024 $\pm$ 0.000     0.041 $\pm$ 0.000
  SC-S         0.093 $\pm$ 0.000    \*0.323 $\pm$ 0.016
  LPP          0.040 $\pm$ 0.014     0.048 $\pm$ 0.024
  KLPP         0.040 $\pm$ 0.000     0.052 $\pm$ 0.000
  LFDA         0.077 $\pm$ 0.041     0.030 $\pm$ 0.013
  KLFDA       \*0.148 $\pm$ 0.005    0.109 $\pm$ 0.003

  : NMI (mean $\pm$ std) for clustering GEO data sets[]{data-label="tb:nmiresult"}

Conclusions
===========

We considered the dimensionality reduction of high-dimensional 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 {#acknowledgements .unnumbered}
================

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.

[^1]: <https://lvdmaaten.github.io/drtoolbox/>

[^2]: <http://www.ms.k.u-tokyo.ac.jp/software.html>

[^3]: https://www.ncbi.nlm.nih.gov/
