Multiclass spectral feature scaling method for dimensionality reduction

Abstract

Irregular features disrupt the desired classification. In this paper, we consider aggressively modifying scales of features in the original space according to the label information to form well-separated clusters in low-dimensional space. The proposed method exploits spectral clustering to derive scaling factors that are used to modify the features. Specifically, we reformulate the Laplacian eigenproblem of the spectral clustering as an eigenproblem of a linear matrix pencil whose eigenvector has the scaling factors. Numerical experiments show that the proposed method outperforms well-established supervised dimensionality reduction methods for toy problems with more samples than features and real-world problems with more features than samples.

Keywords

Dimensionality reduction spectral clustering feature scaling machine learning

1. Introduction

Dimensionality reduction is a technique for reducing the number of variables of data samples and has been successfully applied in many fields to make machine learning algorithms faster and more accurate, including the pathological diagnoses of gene expression data [28], the analysis of chemical sensor data [17], the community detection in social networks [29], the analyses of neural spike sorting [1], and others [24]. Due to their dependence on label information, dimensionality reduction methods can be divided into supervised and unsupervised methods. Typical unsupervised dimensionality reduction methods are the principal component analysis (PCA) [13, 16], the classical multidimensional scaling (MDS) [4], the locality preserving projections (LPP) [12], and the t-distributed stochastic neighbor embedding (t-SNE) [30].

To make use of prior knowledge on the labels, we focus on supervised dimensionality reduction methods. Supervised dimensionality reduction methods map data samples into an optimal low-dimensional space for satisfactory classification while incorporating the label information. One of the most popular supervised dimensionality reduction methods is the linear discriminant analysis (LDA) [3], which maximizes the between-class scatter and reduces the within-class scatter in a low-dimensional space. However, LDA is based on the assumption that the input data obeys a Gaussian distribution and may fail to capture the underlying local data structure. To overcome its drawback, variants of LDA have been proposed. Bressan and Vitrià [5] proposed a variant that preserves the local data structure by redefining the between-class scatter and within-class scatter matrices based on the $k$ -nearest neighbors of each data sample. Weinberger and Saul [32] considered penalizing large distances among data samples with the same label and the $k$ -nearest neighbors and small distances among data samples with different labels according to a cost function. Sugiyama proposed the local Fisher discriminant analysis (LFDA) [26], which maximizes the between-class separability and preserves the within-class local structure, incorporating LPP for supervised dimensionality reduction. Cai et al. [7] proposed another variant, which captures the local geometrical data structure to map $k$ -nearest neighbors in the same classes and those in different classes to a low-dimensional space as close and as distant as possible, respectively. Instead of preserving the local data structure based on the distances among data samples in the original data space, Li et al. [18] introduced a weight between a pair of samples in the same class and exploited the local manifold structure of data samples in a low-dimensional space. In the context of recent metric learning, Mu [21] proposed supervised low-rank metric learning for an optional Mahalanobis distance (fixed-rank metric learning (FRML)), and Harandi et al. [10] proposed joint learning for dimensionality reduction mapping and metric in the reduced space (dimensionality reduction metric learning (DRML)).

In addition to capturing the local structure, as in LDA and its variants, we consider aggressively modifying the scales of the features in the original space before mapping the data samples to a low-dimensional space. This results in reducing the effect of features that interfere in the desirable classification as well as enhancing the separations of different clusters. For these purposes, we derive quantities called feature scaling factors, which are used to scale features based on spectral clustering (SC) for dimensionality reduction [19]. SC projects given data samples to a low-dimensional space formed by eigenvectors of a similarity or Laplacian matrix. In [35, 34], it was reported that SC is effective in detecting cluster structures, and in [33], it was reported that SC preserves the local data structure for feature selection. These reports motivated us to also use SC to learn local cluster structures.

Our purpose is to scale features of given data samples and form (well-separated) clusters in a lower dimensional space. Previous spectral feature scaling methods aimed at binary classification [19]: in this paper, we extend the scope of classification problems to handle multiclassing. Multiclass classification problems with more than two classes have typically been solved by combining independently produced binary classification problems [14]. We take an approach different from [14] to enable a multiclass classification. The contributions of this study can be summarized as follows:

Extension to multiclass classification

We extend the scope of problems that the spectral feature scaling method can handle to multiclass classification. Previous formulations allow only binary classification and require repeated applications of the method for multiclass classification.

Automatic parameter tuning

We propose an automatic tuning technique to determine the values of parameters that specify entries of the (Fielder) eigenvectors according to the labels of training data samples. The extension of the spectral feature scaling method to multiclass classification naively increases the number of hyperparameters and the computational cost. Our technique can save this cost in the multiclass case.

The remainder of this paper is organized as follows. In Section 2, we present preliminaries. In Section 3, we present the proposed spectral feature scaling method. In Section 4, we describe the difference between the proposed method and previous methods. In Section 5, we present experimental results comparing the proposed method with previous methods. In Section 6, we conclude the paper. Throughout the paper, we use italic bold characters to represent column vectors.

2. Preliminaries

Conventional spectral clustering nonlinearly reduces the dimensionality of data samples but may not form the desired data sample clusters due to irregularity of the data features. To improve the classification of reduced data samples, we may modify the scales of features. Simple feature scaling techniques, such as centering, standardization, and normalization, serve as preprocessing for the support vector machine and $k$ -means algorithm. This motivated us to propose supervised feature scaling that enhances the separation of reduced data samples based on prior knowledge from training data.

The spectral clustering partitions a weighted undirected graph in which the edge weight $w_{i,j}$ between nodes $i$ and $j$ is defined according to the similarity between data samples $\bm{x}_{i}$ and $\bm{x}_{j}$ , where $i,j=1,2,\ldots,n$ and $n$ is the number of data samples. We use the locally scaled Gaussian kernel function [36] to define the similarity between data samples $\bm{x}_{i}$ and $\bm{x}_{j}$ as follows:

$\displaystyle w_{i,j}=\exp\left(-\frac{(\bm{x}_{i}-\bm{x}_{j})^{\mathsf{T}}S(% \bm{x}_{i}-\bm{x}_{j})}{\sigma^{\prime}_{i}\sigma^{\prime}_{j}}\right),$ (1)

where $S=\text{diag}(s_{1},s_{2},\ldots,s_{m})\in\mathbb{R}^{m\times m}$ , and $\sigma^{\prime}_{i}$ denotes the local scaling of data samples around $\bm{x}_{i}$ . Thus, we convert a given set of data samples to a graph according to similarities or distances among data samples. A similarity graph is given by a model of the local relationship between data samples. We set $\sigma^{\prime}_{i}=(\bm{x}_{i}-\bm{x}_{i}^{(k)})^{\mathsf{T}}S(\bm{x}_{i}-\bm% {x}_{i}^{(k)})$ , where $\bm{x}_{i}^{(k)}$ is the $k$ th nearest neighbor of $\bm{x}_{i}$ . Zelnik-Manor and Perona [36] recommended the value $k=7$ for $S=I$ in spectral clustering in practice, and we adopted this choice.

Spectral clustering partitions a graph into subgraphs that are contradictory to each other and forms clusters from the corresponding data samples. Let $W_{s}=(w_{i,j})\in\mathbb{R}^{n\times n}$ be the similarity matrix,

$\displaystyle D_{s}=\text{diag}(d_{1},d_{2},\ldots,d_{n})\in\mathbb{R}^{n% \times n}\quad\text{ with }\quad d_{i}=\sum_{j=1}^{n}w_{i,j},$ (2)

$\bm{e}$ be a vector of all ones, and $t_{i}\in\{\pm 1\}$ be an indicator such that $t_{i}=1$ when data sample $i$ belongs to a cluster and $t_{i}=-1$ when data sample $i$ belongs to another cluster. Then, the graph partitioning is given by the constrained minimization problem of the normalized cut (Ncut) function [23]:

$\displaystyle\min_{\bm{v}}\frac{\bm{v}^{\mathsf{T}}(D_{s}-W_{s})\bm{v}}{\bm{v}% ^{\mathsf{T}}D_{s}\bm{v}},$ (3) $\displaystyle\text{subject to}\quad\bm{e}^{\mathsf{T}}D_{s}^{(p)}\bm{v}=0,% \quad v_{i}\in\{1,-b\},\quad b=\frac{\sum_{i:t_{i}>0}d_{i}}{\sum_{i:t_{i}<0}d_% {i}}.$

The entry $v_{i}\in\{1,-b\}$ takes two discrete values to devide the set of data samples into two clusters. By the continuous relaxation $v_{i}\in\{1,-b\}$ to $v_{i}\in\mathbb{R}$ , Eq. (2) is reduced to finding the Fiedler vector $\bm{v}\in\mathbb{R}^{n}\setminus\{\bm{0}\}$ [9] corresponding to the minimum eigenvalue of the constrained generalized eigenvalue problem

$\displaystyle L_{s}\bm{v}=\lambda_{s}D_{s}\bm{v},\quad\lambda_{s}\in\mathbb{R}% ,\quad\text{subject to}\quad\bm{e}^{\mathsf{T}}D_{s}\bm{v}=0,$ (4)

if the minimum eigenvalue has multiplicity one, where $L_{s}=D_{s}-W_{s}$ is the Laplacian matrix. The entries of the Fiedler vector are referred to as the coordinates of the data samples in the reduced space. In practice, we use more eigenvectors corresponding to the minimum eigenvalues of Eq. (4) to form a larger space for accurate classification. When clustering well-separated data samples, we will find hyperplanes that separate the data samples with reduced dimensions formed by a few eigenvectors in Eq. (4). Here, if $S=I$ in Eq. (1), i.e., $S$ is the identity matrix, Eq. (4) is reduced to a conventional spectral clustering method with relaxed Ncut [23]. If $S\neq I$ , Eq. (4) is a generalization of the method [23] and we can calculate the diagonal entries $s_{i}(i=1,2,\ldots,m)$ of $S$ , which are called the scaling factors, for each data feature for binary classification problems [19].

3. Proposed method

In this section, we formulate the spectral feature scaling method (SFS) for dimensionality reduction. The method was originally proposed for binary clustering and classification, but it is here extended to multiclass classification. The proposed method does not use typical means of extension to multiclass classification, such as multiclass support vector machines [14]. The new formulation of SFS computes $r$ scaling factors for each feature and merges them into a single scaling factor. Here, the parameter $r$ is the number of combinations that divide the set of data samples into two classes: we will discuss the selection of $r$ in Section 3.3.

If the labels of the training data samples are known, we use discrete variable $v_{i}\in\{1,-b\}$ in Eq. (2) to prescribe the entries of the $r$ eigenvectors $\bm{v}^{(p)}\in\mathbb{R}^{n}\setminus\{\bm{0}\}(p=1,2,\ldots,r)$ of the Laplacian eigenvalue problem

$\displaystyle L_{s}^{(p)}\bm{v}^{(p)}=\lambda_{s}^{(p)}D_{s}^{(p)}\bm{v}^{(p)}% ,\quad\bm{e}^{\mathsf{T}}D_{s}\bm{v}^{(p)}=0,\quad\lambda_{s}^{(p)}\in\mathbb{% R},$ (5)

where $\bm{v}^{(p)}\in\{1$ , $-b^{(p)}\}$ , $L_{s}^{(p)}=D_{s}^{(p)}-W_{s}^{(p)}$ , $D_{s}^{(p)}=\text{diag}(d_{1}^{(p)},d_{2}^{(p)},\ldots,d_{n}^{(p)})$ , and $W_{s}^{(p)}=(w_{i,j}^{(p)})\in\mathbb{R}^{n\times n}$ depend on the feature scaling factors $s_{i}^{(p)}\in\mathbb{R},i=1,2,\ldots,m$ , and $b^{(p)}$ is a parameter: we will discuss how to estimate the values of $b^{(p)}$ in Section 3.3. The entries $w_{i,j}^{(p)}$ and $d_{i}^{(p)}$ are analogously defined as Eq. (2). We form the scaling matrix $S$ from $s_{i}^{(p)}$ and will discuss the detail in Section 3.2. Then, we apply $S^{1/2}$ to data $[X^{\mathsf{T}},T^{\mathsf{T}}]^{\mathsf{T}}$ , which consists of the training data $X=[\bm{x}_{1},\bm{x}_{2},\ldots,\bm{x}_{n}]^{\mathsf{T}}\in\mathbb{R}^{n\times m}$ and the test data $Y\in\mathbb{R}^{N\times m}$ as follows:

$\displaystyle Z=\left[\begin{array}[]{c}X\\ Y\\ \end{array}\right]S^{1/2}.$ (6)

With the feature scaling $S$ , we enhance the separation of the reduced data samples as desired in the low-dimensional space formed by spectral clustering. This will improve the classification results. Finally, we classify the scaled data $Z\in\mathbb{R}^{(N+n)\times m}$ using $\ell$ eigenvectors corresponding to the positive minimum eigenvalue of the Laplacian eigenvalue problem

$\displaystyle L^{\prime}\bm{u}=\lambda^{\prime}D^{\prime}\bm{u},\quad\bm{e}^{% \mathsf{T}}D^{\prime}\bm{u}=0,\quad\bm{u}\in\mathbb{R}^{N}\setminus\{\bm{0}\},% \quad\lambda^{\prime}\in\mathbb{R},$

where $L^{\prime}=D^{\prime}-W^{\prime}\in\mathbb{R}^{N\times N}$ , $W^{\prime}=(w^{\prime}_{i,j})\in\mathbb{R}^{N\times N}$ ,

$\displaystyle w^{\prime}_{i,j}=\exp\left(-\frac{{\|\bm{z}_{i}-\bm{z}_{j}\|_{2}% }^{2}}{\sigma_{i}\sigma_{j}}\right),\quad i,j=1,2\ldots,N,$ (7)

$\bm{z}_{i}\in\mathbb{R}^{m}$ is the $i$ th column of $Z^{\mathsf{T}}$ , $d^{\prime}_{i}=\sum_{j=1}^{n}w^{\prime}_{i,j}$ , $D^{\prime}=\text{diag}(d^{\prime}_{1},d^{\prime}_{2},\ldots,d^{\prime}_{N})$ , and $\sigma_{i}=\|\bm{z}_{i}-\bm{z}_{i}^{(k)}\|_{2}$ . The values of parameters $\ell$ and $r$ can be determined by cross-validation.

3.1 Formulation

Now, we reformulate Eq. (5) as another eigenvalue problem to extract the scaling factors $\sqrt{s_{i}^{(p)}}(i=1,2,\ldots,m)$ as an eigenvector. Denote the scaling matrix by

$\displaystyle S^{(p)^{1/2}}=\text{diag}\left(\sqrt{s_{1}^{(p)}},\sqrt{s_{2}^{(% p)}},\ldots,\sqrt{s_{m}^{(p)}}\right)\in\mathbb{R}^{m\times m}$

and the $(i,j)$ entry of the similarity matrix $W_{s}^{(p)}$ of scaled data $XS^{(p)^{1/2}}$ by

$\displaystyle w_{i,j}^{(p)}=\left\{\begin{array}[]{ll}1-\frac{(\bm{x}_{i}-\bm{% x}_{j})^{\mathsf{T}}S^{(p)}(\bm{x}_{i}-\bm{x}_{j})}{\sigma_{i}\sigma_{j}}\\ =1-\frac{\bm{s}^{(p)\mathsf{T}}\bm{x}_{i,j}}{\sigma_{i}\sigma_{j}}\simeq\exp(-% \frac{(\bm{x}_{i}-\bm{x}_{j})^{\mathsf{T}}S^{(p)}(\bm{x}_{i}-\bm{x}_{j})}{% \sigma^{\prime}_{i}\sigma^{\prime}_{j}}),&\quad i\neq j,\\ 0,&\quad i=j,\\ \end{array}\right.$ (8)

where $\sigma_{i}=\|\bm{x}_{i}-\bm{x}_{i}^{(k)}\|_{2}$ , $\bm{s}^{(p)}=[s_{1}^{(p)},s_{2}^{(p)},\ldots,s_{m}^{(p)}]^{\mathsf{T}}\in% \mathbb{R}^{m}$ , and the $k$ th entry of $\bm{x}_{i,j}\in\mathbb{R}^{m}$ is $(x_{i,k}-x_{j,k})^{2}$ [22]. Here, we used the first-order approximation of the exponential function $\exp(-x)\simeq∼{}1-x$ for $0<x\ll 1$ . Then, the $i$ th row of $W_{s}^{(p)}$ is

$\displaystyle\bm{w}_{i}^{(p)\mathsf{T}}=[1,\ldots,1,0,1,\ldots,1]-\bm{s}^{(p)% \mathsf{T}}\left[\frac{\bm{x}_{i,1}}{\sigma_{i}\sigma_{1}},\frac{\bm{x}_{i,2}}% {\sigma_{i}\sigma_{2}},\ldots,\frac{\bm{x}_{i,n}}{\sigma_{i}\sigma_{n}}\right]% =\tilde{\bm{e}}_{i}^{\mathsf{T}}-\bm{s}^{(p)\mathsf{T}}X_{i},$

where $\tilde{\bm{e}}_{i}$ is an $n$ -dimensional vector with zero in the $i$ th entry and ones in all other entries, and

$\displaystyle X_{i}=\left[\frac{\bm{x}_{i,1}}{\sigma_{i}\sigma_{1}},\frac{\bm{% x}_{i,2}}{\sigma_{i}\sigma_{2}},\ldots,\frac{\bm{x}_{i,n}}{\sigma_{i}\sigma_{n% }}\right]\in\mathbb{R}^{m\times n}.$

Hence, we have

$\displaystyle W_{s}^{(p)}\bm{v}^{(p)}=[\tilde{\bm{e}}_{1}^{\mathsf{T}},\tilde{% \bm{e}}_{2}^{\mathsf{T}},\ldots,\tilde{\bm{e}}_{n}^{\mathsf{T}}]\bm{v}^{(p)}-[% X_{1}\bm{v}^{(p)},X_{2}\bm{v}^{(p)},\ldots,X_{n}\bm{v}^{(p)}]^{\mathsf{T}}\bm{% s}^{(p)}.$

Let $\hat{\bm{x}}_{i}=\sum_{j=1}^{n}\frac{\bm{x}_{i,j}}{\sigma_{i}\sigma_{j}}$ . Then, the $i$ th diagonal entry of $D_{s}^{(p)}$ is

$\displaystyle d_{i}^{(p)}=\sum_{j=1}^{n}w_{i,j}^{(s)}=(n-1)-\bm{s}^{(p)\mathsf% {T}}\hat{\bm{x}}_{i}.$

Hence, denoting the eigenvector by $\bm{v}^{(p)}=[v_{1}^{(p)},v_{2}^{(p)},\ldots,v_{n}^{(p)}]^{\mathsf{T}}$ , we have

$\displaystyle D_{s}^{(p)}\bm{v}^{(p)}=(n-1)\bm{v}^{(p)}-[v_{1}^{(p)}\hat{\bm{x% }}_{1},v_{2}^{(p)}\hat{\bm{x}}_{2},\ldots,v_{n}^{(p)}\hat{\bm{x}}_{n}]^{% \mathsf{T}}\bm{s}^{(p)}.$

Thus, Eq. (5) can be written as

$\displaystyle L_{s}^{(p)}\bm{v}^{(p)}=\lambda_{s}^{(p)}D_{s}^{(p)}\bm{v}^{(p)}% \Leftrightarrow W_{s}^{(p)}\bm{v}^{(p)}=(1-\lambda_{s}^{(p)})D_{s}^{(p)}\bm{v}% ^{(p)}\Leftrightarrow\left[\begin{array}[]{c}A^{(p)}\quad\bm{\alpha}^{(p)}\\ \end{array}\right]\left[\begin{array}[]{c}\bm{s}^{(p)}\\ -1\\ \end{array}\right]=\mu^{(p)}\left[\begin{array}[]{c}B^{(p)}\quad\bm{\beta}^{(p% )}\\ \end{array}\right]\left[\begin{array}[]{c}\bm{s}^{(p)}\\ -1\\ \end{array}\right]$ (9)

where $\mu^{(p)}=1-\lambda_{s}^{(p)}$ ,

$\displaystyle A^{(p)}=\left[\begin{array}[]{c}(X_{1}\bm{v}^{(p)})^{\mathsf{T}}% \\ (X_{2}\bm{v}^{(p)})^{\mathsf{T}}\\ \vdots\\ (X_{n}\bm{v}^{(p)})^{\mathsf{T}}\\ \end{array}\right]\in\mathbb{R}^{n\times m},\quad B^{(p)}=\left[\begin{array}[% ]{c}v_{1}^{(p)}\hat{\bm{x}}_{1}^{\mathsf{T}}\\ v_{2}^{(p)}\hat{\bm{x}}_{2}^{\mathsf{T}}\\ \vdots\\ v_{n}^{(p)}\hat{\bm{x}}_{n}^{\mathsf{T}}\\ \end{array}\right]\in\mathbb{R}^{n\times m},$ (10) $\displaystyle\bm{\alpha}^{(p)}=[\tilde{\bm{e}}_{1},\tilde{\bm{e}}_{2},\ldots,% \tilde{\bm{e}}_{n}]^{\mathsf{T}}\bm{v}^{(p)}\in\mathbb{R}^{n},\quad\bm{\beta}^% {(p)}=(n-1)\bm{v}^{(p)}\in\mathbb{R}^{n}.$ (11)

Furthermore, the feature scaling factors have the constraint

$\displaystyle\bm{e}^{\mathsf{T}}D_{s}^{(p)}\bm{v}^{(p)}=\sum_{i=1}^{n}((n-1)v_% {i}^{(p)}-v_{i}^{(p)}\bm{s}^{(p)}\hat{\bm{x}}_{i})=0$ (12) $\displaystyle\Leftrightarrow\left(\sum_{i=1}^{n}v_{i}^{(p)}\hat{\bm{x}}_{i}^{% \mathsf{T}}\right)\bm{s}^{(p)}-(n-1)\sum_{i=1}^{n}v_{i}^{(p)}=0.$

Combining Eqs (9)–(3.1), we can obtain the generalized eigenvalue problem of a linear matrix pencil

$\displaystyle\mathcal{A}^{(p)}\left[\begin{array}[]{c}\bm{s}^{(p)}\\ -1\\ \end{array}\right]=\mu^{(p)}\mathcal{B}^{(p)}\left[\begin{array}[]{c}\bm{s}^{(% p)}\\ -1\\ \end{array}\right],\quad\bm{s}^{(p)}\in\mathbb{R}^{m},\quad\mu^{(p)}\in\mathbb% {R},$ (13)

where

$\displaystyle\mathcal{A}^{(p)}=\left[\begin{array}[]{cc}A^{(p)}&\bm{\alpha}^{(% p)}\\ \bm{\gamma}^{(p)\mathsf{T}}&\rho^{(p)}\\ \end{array}\right]\in\mathbb{R}^{(n+1)\times(m+1)},$ (14) $\displaystyle\mathcal{B}^{(p)}=\left[\begin{array}[]{cc}B^{(p)}&\bm{\beta}^{(p% )}\\ \bm{0}^{\mathsf{T}}&0\\ \end{array}\right]\in\mathbb{R}^{(n+1)\times(m+1)},$ (15) $\displaystyle\bm{\gamma}^{(p)}=\sum_{i=1}^{n}v_{i}^{(p)}\hat{\bm{x}}_{i}\in% \mathbb{R}^{m},\quad\rho^{(p)}=(n-1)\sum_{i=1}^{n}v_{i}^{(p)}\in\mathbb{R},$ (16)

and we solve Eq. (13) for the scaling factors $\bm{s}^{(p)}$ for each $p=1,2,\ldots,r$ . If the $r$ eigenproblems Eq. (13) have a common eigenpair, they can be combined as

$\displaystyle\left[\begin{array}[]{c}\mathcal{A}^{(1)}\\ \mathcal{A}^{(2)}\\ \vdots\\ \mathcal{A}^{(r)}\\ \end{array}\right]\left[\begin{array}[]{c}\bm{s}\\ -1\\ \end{array}\right]=\mu_{s}\left[\begin{array}[]{c}\mathcal{B}^{(1)}\\ \mathcal{B}^{(2)}\\ \vdots\\ \mathcal{B}^{(r)}\\ \end{array}\right]\left[\begin{array}[]{c}\bm{s}\\ -1\\ \end{array}\right],\quad\bm{s}\in\mathbb{R}^{m},\quad\mu_{s}\in\mathbb{R},$ (17)

where $\mu_{s}=1-\lambda_{s}$ . The existence of an eigenvalue $\mu^{(p)}$ of Eq. (13) is assured by the equality $[\bm{e}^{\mathsf{T}}0](\mathcal{A}-\mathcal{B})^{\mathsf{T}}=\bm{0}^{\mathsf{T}}$ . Because the Fiedler vector is associated with the smallest eigenvalue, we adopt the eigenvector of Eqs (13) and (17) associated with the eigenvalues $\mu^{(p)}=1-\lambda_{s}^{(p)}$ and $\mu_{s}$ closest to but less than one as a candidate feature scaling factors, respectively. Here, the $r$ eigenproblem Eq. (17) may not have the same eigenpair, so we find an eigenpair $(\lambda,[\bm{s}^{\mathsf{T}},-1]^{\mathsf{T}})$ of Eqs (14) and (15) as close as possible in the $r$ eigenproblems. To solve Eqs (13) or (17), we can use the contour integral method [20] for $n<m$ ; otherwise, we can also use the minimal perturbation approach [15].

3.2 Integrating candidates of feature scaling factors

Here, we describe how to determine the scaling factors from the candidates in the multiclass case. The scaling factors $\sqrt{s_{i}^{(p)}}$ given by solving Eq. (13) are used to form a single feature scaling matrix $S^{1/2}=\text{diag}(s_{1},s_{2},\ldots,s_{m})^{1/2}$ . We have the following five approaches to computing the diagonal elements $s_{i}^{1/2}(i=1,2,\ldots,m)$ of $S^{1/2}$ :

•
Principal component analysis (PCA) [13, 16]

We can obtain $s_{i}^{1/2}$ by using the principal component, i.e., the eigenvector $\bm{\phi}\in\mathbb{R}^{r}$ associated with the maximum eigenvalue $\tau\in\mathbb{R}$ of the eigenproblem

$\displaystyle M\bm{\phi}=\tau\bm{\phi},\quad M=\sum_{i=1}^{m}(\bm{\hat{s}}_{i}% -\hat{\bm{\mu}})(\bm{\hat{s}}_{i}-\hat{\bm{\mu}})^{\mathsf{T}},$

where $\bm{\hat{s}}_{i}^{\mathsf{T}}\in\mathbb{R}^{r}$ is $i$ th row of the matrix

$\displaystyle\left[\begin{array}[]{cccc}\sqrt{s_{1}^{(1)}}&\sqrt{s_{1}^{(2)}}&% \ldots&\sqrt{s_{1}^{(r)}}\\ \sqrt{s_{2}^{(1)}}&\sqrt{s_{2}^{(2)}}&\ldots&\sqrt{s_{2}^{(r)}}\\ \vdots&\vdots&\ddots&\vdots\\ \sqrt{s_{m}^{(1)}}&\sqrt{s_{m}^{(2)}}&\ldots&\sqrt{s_{m}^{(r)}}\\ \end{array}\right]\in\mathbb{R}^{m\times r},$

and $\hat{\bm{\mu}}=\frac{1}{m}\sum_{i=1}^{m}\bm{\hat{s}}_{i}$ . Thus, $s_{i}^{1/2}=\bm{\hat{s}}_{i}^{\mathsf{T}}\bm{\phi}$ is obtained.
•
Arithmetic mean $s_{i}^{1/2}=\frac{1}{r}\sum_{p=1}^{r}\sqrt{s_{i}^{(p)}}$ .
•
Geometric mean $s_{i}^{1/2}=\left(\prod_{p=1}^{r}\sqrt{s_{i}^{(p)}}\right)^{1/r}$ .
•
Root mean square $s_{i}^{1/2}=\sqrt{\frac{1}{r}\sum_{p=1}^{r}s_{i}^{(p)}}$ .
•
Harmonic mean $s_{i}^{1/2}=r\left/\sum_{p=1}^{r}\left(1/\sqrt{s_{i}^{(p)}}\right)\right.$ .

We will compare the classification accuracy of each approach for integrating scaling factors in the numerical experiments.
3.3 Number of prescribed eigenvectors and prescription of the entries

Consider determining a reasonable number $r$ of prescribed eigenvectors $\bm{v}^{(p)}$ to prevent solving many eigenvalue problems Eq. (13) or a large eigenvalue problem Eq. (17). Let $K$ be the number of classes. In particular, if $K=2$ , we prescribe only one eigenvector $\bm{v}^{(p)},p=1,r=1$ in Eq. (5), as in [19]. This is because one eigenvector is sufficient for binary classification if the clusters are well-separated [8]. If $K>2$ , we split the set of training data samples into $r$ combinations of binary classes with two options: take $r=K$ or take at least $r=\lceil\log_{2}K\rceil$ and determine the entries of the eigenvector $\bm{v}^{(p)}$ as

$\displaystyle v_{i}^{(p)}=\left\{\begin{array}[]{ll}1&\text{if sample }i\text{% is in class }c,\quad c=1,2,\ldots,K,\\ -b^{(p)}&\text{otherwise}\\ \end{array}\right.$ (18)

for $p=1,2,\dots,r$ according to the label information of the training data, where $b^{(p)}$ is a parameter we discuss how to determine later in this section. Remark that the $r$ -dimensional indicator vector $[v_{i}^{(1)},v_{i}^{(2)},\ldots,v_{i}^{(r)}]$ for sample $i$ is uniquely chosen to a label. This is a solution of discrete optimization for a binary clustering Eq. (2) reduced from multiclass classification. That is, one cluster consists of data samples belonging to several classes, and the other clusters consist of data samples belonging to other classes. The classification accuracy varies depending on the combination of such binary classifications. By setting $r=K$ , the computational cost for solving Eqs (13) or (17) is large, while the classification accuracy tends to be less sensitive to the choice of combinations. When setting $r$ as small, the classification accuracy tends to be sensitive and the computational cost for solving Eqs (13) or (17) is small. Hence, there is a trade-off between the cost and sensitivity of classification accuracy for these approaches.

In the previous SFS with $r=1$ in Eq. (18), we empirically determined the value of $b$ [19]. In this study, we found that the values of $b^{(p)}$ in Eq. (18) determined by

$\displaystyle b^{(p)}=\frac{\sum_{i:t_{i}>0}d_{i}^{(p)}}{\sum_{i:t_{i}<0}d_{i}% ^{(p)}},\quad p=1,2,\ldots,r$ (19)

according to the label information of training data $X$ give favorable results, where $t_{i}=1$ indicates that data sample $i$ belongs to a cluster, and $t_{i}=-1$ indicates that data sample $i$ belongs to another cluster. The choice of $t_{i}=1$ or $t_{i}=-1$ is flexible in Eq. (19) and can be fixed by cross-validation in practice (see Section 5). Note that the ideal Fiedler vector does not necessarily take such an entry and is not necessarily unique.

We summarize the procedures of the proposed method in Algorithm 3.3.

[!h] Supervised dimensionality reduction method with spectral features scaling[1] Training data $X\in\mathbb{R}^{n\times m}$ with $n$ samples and $m$ features, test data $Y\in\mathbb{R}^{N\times m}$ , number of reduced dimensions $\ell$ . Low-dimensional data samples $U=[\bm{u}_{1},\bm{u}_{2},\dots,\bm{u}_{\ell}]^{\mathsf{T}}\in\mathbb{R}^{\ell% \times(N+n)}$ . Decide the number of eigenvectors to prescribe $r$ . Compute the parameter $b^{(p)}$ using $X$ and set the eigenvectors $\bm{v}^{(p)},(p=1,2,\ldots,r)$ . Compute $A^{(p)},B^{(p)},\bm{\alpha}^{(p)},\bm{\beta}^{(p)},\bm{\gamma}^{(p)}$ , and $\rho^{(p)}$ using Eqs (10), (11), and (16). Solve Eq. (13) for an eigenvector $\bm{s}^{(p)}$ . Compute the scaling matrix $S^{1/2}$ from the scaling factors $\bm{s}^{(p)}$ (Section 3.3). Compute the scaled data matrix $Z$ Eq. (6). Compute the similarity matrix $W^{\prime}\in\mathbb{R}^{(N+n)\times(N+n)}$ Eq. (7) and $D^{\prime}$ . Compute the Laplacian matrix $L^{\prime}=D^{\prime}-W^{\prime}$ . Solve $L^{\prime}\bm{u}=\lambda^{\prime}D^{\prime}\bm{u}$ for the eigenvectors $\bm{u}_{1},\bm{u}_{2}\ldots\bm{u}_{\ell}$ corresponding to the $\ell$ smallest nonzero eigenvalues.

4. Related methods

In this section, we discuss the difference between the proposed method and previous methods. Many supervised dimensionality reduction methods, such as LDA and its variants, utilize knowledge from labels and map given data samples to an optimal low-dimensional space. The objective of these methods is to find a transformation matrix $T$ to map given data samples $X$ to low-dimensional data samples $U$

$\displaystyle U=TX^{\mathsf{T}},$

whereas the objective of our method is to generate a scaling matrix $S^{1/2}$ and modify the scales of the features of given data samples $X$ as $XS^{1/2}$ and then map them to low-dimensional data samples $U^{\prime}$ using a transformation matrix $T^{\prime}$ :

$\displaystyle U^{\prime}=T^{\prime}\phi(S^{1/2}X^{\mathsf{T}}),$

where $\phi:\mathbb{R}^{m\times n}\rightarrow\mathbb{R}^{m\times n}$ is a transformation with a nonlinear kernel function. The methods in [18, 31] modify the weights among data samples, whereas the proposed method modifies the scales of features in the original space and uses the same feature scaling factors for all data samples.

5. Numerical experiments

We compare the proposed method (SFS) with previous supervised dimensionality reduction methods and metric learning method in terms of accuracy by numerical experiments on artificial data and practical datasets. We show that the proposed method outperforms previous methods in some cases, and is more robust than the previous methods. The previous methods were kernel versions of LDA (KDA) [2, 6] and LFDA (KLFDA) [27], LADA [18] and FRML [21]. The performance measures used for comparisons were overall accuracy (OA), average accuracy (AA), and normalized mutual information (NMI) [%] [25]. Here, OA and AA are definedas

$\displaystyle\text{OA}=\frac{\sum_{i=1}^{K}\hat{n}_{i}}{\sum_{i=1}^{K}n_{i}},% \quad\text{AA}=\frac{1}{K}\sum_{i=1}^{K}\frac{\hat{n}_{i}}{n_{i}},$

where $n_{i}$ is the number of samples in class $i$ , $\hat{n}_{i}$ is the number of samples classified by a method to class $i$ , and $K$ is the number of classes. We performed five-fold cross-validation and show the mean and standard deviation of each performance measure. The reduced dimension $\ell$ and the constraint rank for FRML were chosen by four-fold cross-validation regarding OA between one to the number of features when the number of features is smaller than the number of training data samples and between one to the number of training data samples, otherwise. In SFS, we used the seven nearest neighbors to sparsify the matrix $W^{\prime}$ . We chose optional values of the regularization parameters of FRML among 1, 10 ${}^{-1}$ , 10 ${}^{-2}$ , 10 ${}^{-3}$ , and 10 ${}^{-4}$ according to cross-validation and, $\lambda$ and $\gamma$ of LADA [31] among 1, 10 ${}^{1}$ , 10 ${}^{2}$ , and 10 ${}^{3}$ according to cross-validation. In SFS, we chose the value of $t_{i}=1$ or $t_{i}=-1$ to which class $i$ is set when using the number of classes as the number of reduced dimensions (Section 3.3), chose the number of reduced dimension $\ell$ , and chose the value of $t_{i}$ again. We used the KLFDA code from the Sugiyama-Sato-Honda Lab site1

¹
http://www.ms.k.u-tokyo.ac.jp/.

and programmed the LADA and KDA codes. All programs were coded and run in MATLAB 2018a.

Figure 1.

Visualization of the artificial data in three dimensions.

Figure 2.

Mean of each performance measure vs. variance $\sigma^{2}$ .

5.1 Artificial datasets

In this subsection, we report results on a toy problem consisting of 600 data samples with ten features. The data samples had three classes, and each class had 200 samples. Figure 1 shows three of the ten features, where the symbols $\circ$ , $\vartriangle$ , and $\square$ represent data samples in classes 1, 2, and 3, respectively, and the data samples in each class are normally distributed along a ring. The rings of classes 1 and 2, and those of classes 2 and 3 intersect, respectively. The variances of the first to third features are 0.35, 2.01, and 0.19, respectively. The remaining seven features are normally distributed with center zero and variance $\sigma^{2}$ . We changed the variance $\sigma^{2}$ from 1 to 25 in increments of 1. These seven features interfere with data sample classification according to the first three features. The classification of data samples with the reduced dimension was done by logistic regression. Results for other classifiers are given in the Appendix. In SFS, the number of prescribed eigenvectors $\bm{v}^{(p)}$ was set to the number of classes.

Figure 3.

Test data samples for $\sigma^{2}=1$ in the original and reduced two-dimensional space.

Figure 4.

Test data samples for $\sigma^{2}=25$ in the original and reduced two-dimensional space.

Figure 5.

Values of the scaling factors for (a) $\sigma^{2}=1$ and (b) $\sigma^{2}=25$ when using the root mean square.

Table 1

Specifications of datasets

	# of samples	# of features	# of classes
(a) Colon	62	2000	2
(b) CLL_SUB_111	111	11340	3
(c) Lung	203	3312	5
(d) Lymphoma	96	4026	9
(e) WarpPIE10P	210	2420	10

Table 2

Performance rates (mean% $\pm$ std) for real-world datasets

	OA	AA	NMI
(a) Colon
SFS (RMS)	81.7 ${}_{6.2}$	81.3 ${}_{8.8}$	35.1 ${}_{19.2}$
LADA	63.3 ${}_{6.7}$	57.5 ${}_{8.3}$	12.5 ${}_{8.0}$
KLFDA	83.3 ${}_{7.5}$	78.8 ${}_{8.5}$	36.7 ${}_{22.2}$
KDA	66.7 ${}_{0.0}$	50.0 ${}_{0.0}$	NaN
FRML	71.7 ${}_{10.0}$	65.0 ${}_{11.6}$	15.3 ${}_{23.7}$
(b) CLL_SUB_111
SFS (RMS)	68.2 ${}_{5.0}$	72.7 ${}_{8.8}$	37.3 ${}_{2.2}$
LADA	53.6 ${}_{7.3}$	38.0 ${}_{6.5}$	11.2 ${}_{8.3}$
KLFDA	67.3 ${}_{7.8}$	70.7 ${}_{9.3}$	34.2 ${}_{7.9}$
KDA	50.0 ${}_{5.0}$	35.3 ${}_{4.0}$	15.9 ${}_{13.3}$
FRML	45.5 ${}_{5.8}$	57.3 ${}_{5.3}$	31.2 ${}_{9.1}$
(c) Lung
SFS (RMS)	94.5 ${}_{1.9}$	85.4 ${}_{11.1}$	85.7 ${}_{6.3}$
LADA	93.5 ${}_{3.4}$	79.4 ${}_{13.1}$	79.8 ${}_{10.2}$
KLFDA	93.0 ${}_{2.9}$	82.0 ${}_{10.7}$	78.7 ${}_{8.3}$
KDA	64.5 ${}_{8.7}$	20.4 ${}_{4.4}$	8.5 ${}_{10.0}$
FRML	91.0 ${}_{2.0}$	76.3 ${}_{7.7}$	75.3 ${}_{8.7}$
(d) Lymphoma
SFS (RMS)	94.8 ${}_{9.2}$	94.8 ${}_{9.2}$	94.6 ${}_{5.2}$
LADA	60.0 ${}_{7.8}$	42.8 ${}_{15.4}$	62.7 ${}_{7.4}$
KLFDA	90.5 ${}_{2.1}$	80.0 ${}_{4.4}$	90.7 ${}_{2.2}$
KDA	47.4 ${}_{0.0}$	11.1 ${}_{0.0}$	NaN
FRML	62.1 ${}_{14.7}$	49.8 ${}_{23.7}$	67.2 ${}_{7.6}$
(e) WarpPIE10P
SFS (RMS)	88.6 ${}_{2.8}$	88.9 ${}_{2.6}$	90.3 ${}_{2.4}$
LADA	82.9 ${}_{2.8}$	82.6 ${}_{3.2}$	83.7 ${}_{3.0}$
KLFDA	99.5 ${}_{1.0}$	99.5 ${}_{1.0}$	99.5 ${}_{1.0}$
KDA	23.3 ${}_{7.6}$	8.7 ${}_{2.5}$	24.1 ${}_{14.1}$
FRML	34.8 ${}_{20.1}$	35.2 ${}_{20.3}$	54.1 ${}_{11.0}$

Figure 2 shows the performance measures for variances $\sigma^{2}=1,2,\ldots,25$ where SFS (one-versus-all) represents the “one-vs-all” approach [11, p. 658] for the previous SFS for a binary classification problem. Regarding the performance measures, some of the proposed methods were more accurate than the previous methods, and KDA was the worst regardless of the variance. SFS (PCA) was the best when the variance was small, while SFS(arithmetic) and SFS (RMS) were the best when the variance was large. SFS (RMS), SFS (arithmetic), and LADA tended to be robust against interfering features. SFS (one-vs-all) was almost as accurate as KDA and FRML, and the line overlaps with the KDA line and FRML line. LADA was more accurate than KLFDA, though LADA is not kernelized. Among the compared SFS methods, the RMS approach was most accurate for many values of $\sigma^{2}$ . The proposed SFS methods were more accurate than the conventional “one-vs-all” approach for the multiclass classification problem.

Figures 3 and 4 show the first and second features of the original data in parts (a) and the two-dimensional data samples reduced by each method in parts (b)–(d) for $\sigma^{2}=1$ and 25, respectively. LADA and KLFDA failed to enhance the separations of clusters, while the proposed method separated clusters well.

Figure 5 shows the absolute values of the obtained scaling factors of SFS (RMS) for $\sigma^{2}=1$ and $\sigma^{2}=25$ . Because the fourth to tenth features given by random numbers are not involved in the classification, the values of the scaling factors of these seven features were small. Thus, the values of the scaling factors indicate which features are effective in the desired classification.

5.2 Real-world datasets

In this section, we report results for five datasets with more features than samples in the real world from a public repository.2

²
http://featureselection.asu.edu/datasets.php.

Table 1 gives the numbers of samples, features, and classes of the datasets. Datasets (a)–(d) are of gene expressions, and dataset (e) is of face images. In SFS, the number of prescribed eigenvectors was set to the number of classes, and we used RMS to generate the feature scaling matrix. The classification was done by KNN for

k=1

since it was the best in the experiment in Section 5.1.

Table 2 gives the mean and standard deviation of the performance measures for each method. For the colon and lymphoma, the NMI of KDA was Not-a-Number (NaN) because KDA gave the same label to all test data samples. In all performance measures, SFS (RMS) was the best or second best for all datasets. KLFDA was the best for warpPIE10P.

6. Conclusions

In this paper, to deal with irregularity or uncertainty in features, we extended previously proposed feature scaling methods to multiclass classification and proposed a supervised dimensionality reduction method that exploits knowledge of labels of training data samples. The proposed method aggressively modifies the scales of features, and feature scaling can reduce the effects of features that prevent us from obtaining the desired clusters. To obtain the factors for scaling the features based on spectral clustering, we derived matrix eigenproblems whose eigenvectors have the feature scaling factors and described the procedures for the proposed method. The multiclass extension asks for more hyperparameters and computational cost. To reduce the number of hyperparameters, we proposed an automatic tuning technique based on the formula for discrete optimization to determine the entries of prescribed eigenvectors. The demanding combinations of entries of prescribed vectors are related to the number of eigenproblems to solve and can be reduced with a trade-off between accuracy and computational cost. Numerical experiments showed that feature scaling is effective when combined with the proposed classification method. For toy problems with more samples than features, feature scaling improved accuracy and was more robust to interfering features. In terms of flexibility in merging candidates of scaling factors for each feature, our experimental results indicate that the RMS approach is preferable in practice. For real-world problems with more features than samples, the proposed method was more robust than previous methods and outperformed previous methods in some cases.

Footnotes

Acknowledgments

The second author was supported in part by JSPS KAKENHI Grant Number 16K17639 and the Hattori Hokokai Foundation. The third author was supported in part by the Japan Science and Technology Agency, ACT-I (No. JPMJPR16U6), New Energy and Industrial Technology Development Organization, and JSPS KAKENHI Grant Numbers 17K12690, 18H03250.

Appendix A. Comparison of classifiers

In Section 5.1, we used logistic regression to classify data samples with reduced dimensions. In fact, the proposed method is not specialized to a particular classifier, which means we can choose an arbitrary classifier after the dimensionality reduction. In this appendix, we observe the dependence of the accuracy on classifiers and compare four classifiers: logistic regression (LR), $k$ -nearest neighbor algorithm (KNN), support vector machine (SVM), and naive Bayes classifier (NB). Among the proposed methods, we used SFS (RMS) because it performed the best in many cases.

Figure 6 shows the mean OA for each method and each classifier. SFS (RMS) was more accurate than other methods for every classifier. SFS (RMS) with KNN was more accurate than the other classifiers. The relative positions of the compared methods are the same for all performance measures.

Figure 6.

Mean performance measure (OA) vs. classifier.

Figure 7 shows the OA of each method for $k=1,2,\ldots,50$ in the KNN. For $k=1$ , SFS (RMS) was the best and its OA was 93.7%. The accuracies of the compared methods did not largely depend on the value of $k$ . The relative positions of the compared methods are also the same for all $k$ in the KNN.

Figure 7.

Mean of performance measure (OA) vs. $k$ in the $k$ -NN classifier.

References

Bar-Hillel

Spiro

and Stark

, Spike sorting: Bayesian clustering of non-stationary data, Journal of Neuroscience Methods 157(2) (2006), 303–316.

Baudat

and Anouar

, Generalized discriminant analysis using a kernel approach, Journal of Neural Computation 12(10) (2000), 2385–2404.

Belhumeur

P.N.

Hespanha

J.P.

and Kriegman

D.J.

, Eigenfaces vs. Fisherfaces: Recognition using class specific linear projection, IEEE Transactions on Pattern Analysis and Machine Intelligence 19(7) (1997), 711–720.

Borg

and Groenen

P.J.F.

, Modern Multidimensional Scaling: Theory and Applications, Springer, New York, 1997.

Bressan

and Vitrià

, Nonparametric discriminant analysis and nearest neighbor classification, Pattern Recognition Letters 24(15) (2003), 2743–2749.

Cai

and Han

, Efficient kernel discriminant analysis via spectral regression, in: Seventh IEEE International Conference on Data Mining (ICDM 2007), 2007, pp. 427–432.

Cai

Zhou

Han

and Bao

, Locality sensitive discriminant analysis, in: Proceedings of the 20th International Joint Conference on Artificial Intelligence (IJCAI 2011), 2007, pp. 708–713.

Chung

F.R.K.

, Spectral Graph Theory, American Mathematical Society, Providence, RI, 1996.

Fiedler

, Algebraic connectivity of graphs, Czechoslovak Mathematical Journal 23(2) (1973), 298–305.

10.

Harandi

Salzmann

and Hartley

, Joint dimensionality reduction and metric learning: A geometric take, in: Proceedings of the 34th International Conference on Machine Learning, 2017, pp. 1404–1413.

11.

Hastie

Tibshirani

and Friedman

, The Elements of Statistical Learning, Springer, 2nd edition, New York, 2009.

12.

and Niyogi

, Locality preserving projections, in: Proceedings of the 16th International Conference on Neural Information Processing Systems, 2003, pp. 153–160.

13.

Hotelling

, Analysis of a complex of statistical variables into principal components, Journal of Educational Psychology 24(6) (1933), 417–441.

14.

Hsu

C.W.

and Lin

C.-J.

, A comparison of methods for multiclass support vector machines, IEEE Transactions on Neural Networks 13(2) (2002), 415–425.

15.

Ito

and Murota

, An algorithm for the generalized eigenvalue problem for nonsquare matrix pencils by minimal perturbation approach, SIAM Journal on Matrix Analysis and Applications 37(1) (2016), 409–419.

16.

Jolliffe

I.T.

, Principal component analysis and factor analysis, Principal Component Analysis, 1986, 115–128.

17.

Jurs

P.C.

Bakken

G.A.

and McClelland

H.E.

, Computational methods for the analysis of chemical sensor array data from volatile analytes, Chemical Reviews 100(7) (2000), 2649–2678.

18.

Chen

Nie

and Wang

, Locality adaptive discriminant analysis, in: Proceedings of the 26th International Joint Conference on Artificial Intelligence (IJCAI 2017), 2017, pp. 2201–2207.

19.

Matsuda

Morikuni

and Sakurai

, Spectral feature scaling method for supervised dimensionality reduction, in: Proceedings of the 27th International Joint Conference on Artificial Intelligence (IJCAI 2018), 2018, pp. 2560–2566.

20.

Morikuni

, Contour integral-type method for eigenproblems of rectangular matrix pencils, in: Book of Abstracts, Annual Meeting 2016 of the Japan Society for Industrial and Applied Mathematics, Kitakyushu, Japan, 2016, pp. 352–353.

21.

, Fixed-rank supervised metric learning on riemannian manifold, in: Proceedings of the Thirtieth AAAI Conference on Artificial Intelligence (AAAI-16), 2016, pp. 1941–1947.

22.

A.Y.

Jordan

M.I.

and Yair

, On spectral clustering: Analysis and an algorithm, in: Advances in Neural Information Processing Systems 14, 2002, pp. 849–856.

23.

Shi

and Malik

, Normalized cuts and image segmentation, IEEE Transactions on Pattern Analysis and Machine Intelligence 22(8) (2000), 888–905.

24.

Sogh

T.S.

, Wired and wireless intrusion detection system: Classifications, good characteristics and state-of-the-art, Computer Standards & Interfaces 28(6) (2006), 670–694.

25.

Strehl

and Ghosh

, Cluster ensembles – a knowledge reuse framework for combining multiple partitions, Journal of Machine Learning Research 3 (2002), 583–617.

26.

Sugiyama

, Local Fisher discriminant analysis for supervised dimensionality reduction, in: Proceedings of the 23rd International Conference on Machine Learning, 2006, pp. 905–912.

27.

Sugiyama

, Dimensionality reduction of multimodal labeled data by local Fisher discriminant analysis, Journal of Machine Learning Research 8 (2007), 1027–1061.

28.

Tarca

A.L.

Romero

and Draghici

, Analysis of microarray experiments of gene expression profiling, American Journal of Obstetrics and Gynecology 195(2) (2006), 373–388.

29.

Tichy

N.M.

Tushman

M.L.

and Fombrun

, Social network analysis for organizations, Academy of Management Review 4(4) (1979), 507–519.

30.

van der Maaten

and Hinton

, Visualizing high-dimensional data using t-SNE, Journal of Machine Learning Research 9 (2008), 2579–2605.

31.

Wang

Meng

and Li

, Locality adaptive discriminant analysis for spectral-spatial classification of hyperspectral images, IEEE Geoscience and Remote Sensing Letters 14(11) (2017), 2077–2081.

32.

Weinberger

K.Q.

and Saul

L.K.

, Distance metric learning for large margin nearest neighbor classification, Journal of Machine Learning Research 10 (2009), 207–244.

33.

and Sakurai

, Spectral clustering and discriminant analysis for unsupervised feature selection, in: Proceedings of the European Symposium on Artificial Neural Networks, Computational Intelligence and Machine Learning, 2016, pp. 563–568.

34.

Sakurai

and Liu

, Large scale spectral clustering using sparse representation based on hubness, in: Proceeding of the IEEE International Conference on Cloud and Big Data Computing, 2018, pp. 1731–1737.

35.

and Sakurai

, Spectral clustering with adaptive similarity measure in Kernel space, Intelligent Data Analysis 22(4) (2018), 751–765.

36.

Zelnik-Manor

and Perona

, Self-tuning spectral clustering, in: Proceedings of Advances in Neural Information Processing Systems 17, 2005, pp. 1601–1608.

Multiclass spectral feature scaling method for dimensionality reduction

Abstract

Keywords

1. Introduction

2. Preliminaries

5. Numerical experiments

1 http://www.ms.k.u-tokyo.ac.jp/.

2 http://featureselection.asu.edu/datasets.php.

Footnotes

Acknowledgments

Appendix A. Comparison of classifiers

References

¹
http://www.ms.k.u-tokyo.ac.jp/.

²
http://featureselection.asu.edu/datasets.php.