A new classification framework for high-dimensional data

It is well-known that the equality of the two multivariate distributions, $X\sim F$ and $Y\sim G$, can be characterized by the equality of three distributions: the distribution of the inter-point distance between two observations from $F_{X}$, the distribution of the inter-point distance between two observations from $G_{Y}$, and the distribution of the distance between one observation from $F_{X}$ and one from $G_{Y}$ (Maa et al., 1996). We utilize this fact as the basis for our approach.

We begin by examining the inter-point distances of observations in both settings shown in Table 1. Heatmaps of these distances in a typical simulation run are shown in the top panel of Figure 1, where the data is arranged in the order of $X_{1},X_{2},\dots,X_{50}$ and $Y_{1},Y_{2},\dots,Y_{50}$. To better visualize the patterns, we also include data with larger differences in the bottom panel of Figure 1: $\mu_{0}=15,a=1$ (left) and $\mu_{0}=0,a=1.15$ (right).

We denote the distance between two observations both from class $X$ as $D_{XX}$, the distance between one observation from class $X$ and the other from class $Y$ as $D_{XY}$, and the distance between two observations both from class $Y$ as $D_{YY}$. We see that, under the mean difference setting, the between-group distance ($D_{XY}$) tend to be larger than the within-group distance $(D_{XX},D_{YY})$ (left panel of Figure 1). However, under the variance difference setting where class Y has a larger variance difference, we see that $D_{XX}<D_{XY}<D_{YY}$ in general (right panel of Figure 1). This phenomenon is due to the curse of dimensionality, where the volume of the $d$-dimensional space increases exponentially in $d$, causing observations from a distribution with a larger variance to scatter farther apart compared to those from a distribution with a smaller variance. This behavior of high-dimensional data has been discussed in Chen and Friedman (2017).

Based on the observations above, we propose using $(D_{XX},D_{XY})$ and $(D_{XY},D_{YY})$ as summary statistics for class $X$ and $Y$, respectively. Specially, under the mean difference setting, the between-group distance ($D_{XY}$) tends to be larger than the within-group distance $(D_{XX},D_{YY})$. This creates differences in both dimensions: between $D_{XX}$ and $D_{XY}$, and between $D_{XY}$ and $D_{YY}$). Under the variance difference setting, we observe $D_{XX}<D_{XY}<D_{YY}$ (or $D_{XX}>D_{XY}>D_{YY}$ if class $X$ has a larger variance), so differences exist in both dimensions as well. In either scenario, the summary statistic is distinguishable between the two classes.

This idea can also be extended to $k$-class classification problems. For a $k$-class classification problem with class labels $1,2,\dots,k$, let $D_{ij}$ be the distance between one observation from the $i^{th}$ class and one from the $j^{th}$ class, and let $D_{ii}$ be the inter-point distance between two observations from the $i^{th}$ class. We can use $D_{i}=(D_{i1},D_{i2},\dots,D_{ik})$ as the summary statistic for the $i^{th}$ class. For two class $i$ and $j$ differ in distribution, $(D_{ii},D_{ij})$ and $(D_{ij},D_{jj})$ also differ in distribution. Hence, the summary statistic $D_{i}$ can distinguish class $i$ from other classes.

We provide two classification approaches. Approach 1 is based on the pairwise distances, while Approach 2 is based on the ranks of pairwise distances. The rank-based approach inherits the good properties of ranks and is more robust to outliers than the distance-based approach (see Section 3.4).

Let $S=\left\{(Z_{i},g_{i}),i=1,2,\dots,N\right\}$ be a training set consisting of $N$ observations, where $Z_{i}\in\mathbb{R}^{d}$ represents the $i$-th observation and $g_{i}\in\left\{1,2,\dots,k\right\}$ is its corresponding class label. We assume that all $Z_{i}$’s are independent and unique, and that if $g_{i}=j$, then $Z_{i}$ is drawn from the distribution $F_{j}$. Let $n_{j}=\sum_{i=1}^{N}\mathbbm{1}\left\{g_{i}=j\right\}$ denote the number of observations in the training set that belong to class $j$. The goal is to classify a new observation $W\in\mathbb{R}^{d}$ that is generated from one of the $k$ distributions $\left\{F_{j}\right\}_{j=1}^{k}$ to one of the $k$ classes.

The distance-based approach and rank-based approach are described in Algorithm 1 and Algorithm 2, respectively. In the distance-based approach, we first compute the pairwise distance matrix with the training set $S$ and the distance mean matrix $M^{(D)}$. Then, we compute a distance vector $D_{W}$, which contains all the pair-wise distance from the new observation $W$ to the training set, and the group distance mean vector $M_{W}^{(D)}$. The last step is to classify $W$ using the group distance mean vector $M_{W}^{(D)}$ and compare it with $M^{(D)}$. In the rank-based approach, we add steps to compute the rank matrix($R$) and vector($R_{W}$), along with the rank mean matrix($M^{(R)}$) and vector($M^{(R)}_{W}$), and classify the rank mean vector based on the rank mean vector in the last step.

To illustrate how the first three steps perform in separating the different classes, for the four datasets in Figure 1, we plot the distance mean vector $M^{(D)}(Z_{i}),i=1,2,\dots,100$ in Figure 2 and the rank mean vector $M^{(R)}(Z_{i}),i=1,2,\dots,100$ in Figure 3. As shown in Figures 2 and 3, the classes are well separated, indicating the effectiveness of the first three steps.

We applied Algorithms 1 and 2 to the two same settings as in Table 1, and the results are presented in Table 2. We see that under the mean difference setting, the new method performs similarly to PLSR, ELM, SVM and GLDA, which are the best performers in this setting. Under the variance difference setting, the new approaches outperform all other methods.

In each trial, we generate two independent samples, $X_{1},X_{2},\dots,X_{50}\stackrel{{\scriptstyle\text{ i.i.d }}}{{\sim}}F_{X}$ and $Y_{1},Y_{2},\dots,$ $Y_{50}$ $\stackrel{{\scriptstyle\text{ i.i.d }}}{{\sim}}F_{Y}$, with $X_{i}=\mathbf{A}(x_{i1},x_{i2},\dots,x_{id})^{\top}$, $x_{ik}\stackrel{{\scriptstyle\text{ i.i.d }}}{{\sim}}F_{x}$ and $Y_{j}=\mathbf{B}(y_{j1},y_{j2},\dots,y_{jd})^{\top}+\mu$, $y_{jk}\stackrel{{\scriptstyle\text{ i.i.d }}}{{\sim}}F_{y}$, to be the training set. We set $\mathbf{A}\mathbf{A}^{\top}=\Sigma$, with $\Sigma_{r,c}=0.1^{|r-c|}$, $d=1000$ , $\mathbf{B}=a\mathbf{A}$ and $\mu=\mu_{0}\frac{\mu^{\prime}}{\|\mu^{\prime}\|}$ with $\mu^{\prime}$ a random vector generated from $N_{d}(0,\mathbf{I}_{d})$. The testing samples are $W_{x_{1}},W_{x_{2}},\dots W_{x_{50}}\stackrel{{\scriptstyle\text{ i.i.d }}}{{\sim}}F_{X}$ and $W_{y_{1}},W_{y_{2}},\dots W_{y_{50}}\stackrel{{\scriptstyle\text{ i.i.d }}}{{\sim}}F_{Y}$. We consider a few different scenarios:

• •

  Scenario S1: $F_{x}=N(0,1)$, $F_{y}=N(0,1)$;

• •

  Scenario S2: $F_{x}=t_{5}$, $F_{y}=t_{5}$;

• •

  Scenario S3: $F_{x}=\chi^{2}_{5}-5$, $F_{y}=\chi^{2}_{5}-5$;

• •

  Scenario S4: $F_{x}=N(0,1)$, $F_{y}=t_{5}$.

Table 3 shows the average misclassification rate from $50$ trials. We see that when there is only a mean difference, the new methods (‘Dist’ and ‘Rank’) have a misclassfication rate close to the best method among all other methods. When there is only a variance difference, the new methods perform the best among all the methods. When there are both mean and variance differences, the new methods again have the lowest misclassification rate.

In each trial, we randomly generate $n=50$ observations from four distributions $Z_{ij}\stackrel{{\scriptstyle\text{ i.i.d }}}{{\sim}}F_{i},\ i=1,\dots,4$, $j=1,\dots,50$, to be the training set, with $Z_{ij}=a_{i}\mathbf{A}(z_{ij1},z_{ij2},\dots,z_{ijd})^{\top}+\mu_{i}$, $z_{ijk}\stackrel{{\scriptstyle\text{ i.i.d }}}{{\sim}}F_{z}$, $i=1,\dots,4$, $j=1,2,\dots,50$. We set $d=1000$, $\mathbf{A}\mathbf{A}^{\top}=\Sigma$, $\Sigma_{r,c}=0.1^{|r-c|}$ and $\mu=\mu_{0}\frac{\mu^{\prime}}{\|\mu^{\prime}\|}$, with $\mu^{\prime}$ a random vector generated from $N_{d}(0,\mathbf{I}_{d})$. The $a_{i}^{\prime}s$ and $\mu_{i}^{\prime}s$ are set as follow: $a_{1}=a_{3}=1$, $a_{2}=a_{4}=1.1$; $\mu_{1}=\mu_{2}=0$, $\mu_{3}=\mu_{4}=\mu$, $\mu_{0}=12$. Under those settings, the four distributions have two different means and two different variances. The testing samples are $W_{ij}\stackrel{{\scriptstyle\text{ i.i.d }}}{{\sim}}F_{i}$, $i=1,\dots,4$, $j=1,\dots,50$. We consider the following scenarios:

• •

  Scenario S5: $F_{z}=N(0,1)$;

• •

  Scenario S6: $F_{z}=t_{5}$;

• •

  Scenario S7: $F_{z}=\chi^{2}_{5}-5$.

The average misclassification rate of $50$ trials are shown in Table 4 (FAIR can only be applied to the two-class problem and is not included here). We see that, the new method has the lowest misclassification rate across all these scenarios.

We generate random graphs using the configuration model $G(v,\vec{k})$, where $v$ is the number of vertices and $\vec{k}$ is a vector containing the degrees of the $v$ vertices, with $k_{i}$ assigned to vertex $v_{i}$. In each trial, we generate two independent samples, $\left\{X_{1},X_{2},\dots,X_{30}\right\}$ and $\left\{Y_{1},Y_{2},\dots,Y_{30}\right\}$, with degree vectors $\vec{k}^{x}$ and $\vec{k}^{y}$, respectively. The testing samples are $W_{x_{1}},W_{x_{2}},\dots,W_{x_{20}}\stackrel{{\scriptstyle\text{ i.i.d }}}{{\sim}}G(v,\vec{k}^{x})$ and $W_{y_{1}},W_{y_{2}},\dots,W_{y_{20}}\stackrel{{\scriptstyle\text{ i.i.d }}}{{\sim}}G(v,\vec{k}^{y})$. We consider the following scenarios:

• •

  Scenario S8: $k^{x}_{1}=k^{x}_{2}=\dots=k^{x}_{20}=1$, $k^{x}_{21}=k^{x}_{22}=\dots=k^{x}_{40}=3$; $k^{y}_{1}=k^{y}_{2}=\dots=k^{y}_{20-a}=1$, $k^{y}_{21-a}=k^{y}_{22-a}=\dots=k^{y}_{20}=2$, $k^{y}_{21}=k^{y}_{22}=\dots=k^{y}_{20+a}=4$, $k^{y}_{21+a}=k^{y}_{22+a}=\dots=k^{y}_{40}=3$;

• •

  Scenario S9: $k^{x}_{1}=k^{x}_{2}=\dots=k^{x}_{40}=20$, $k^{y}_{1}=k^{y}_{2}=\dots=k^{y}_{40-a}=20$, $k^{y}_{41-a}=k^{y}_{42-a}=\dots=k^{y}_{40}=30$.

When comparing the performance of the methods, we convert the network data with 40 nodes into $40\times 40$ adjacency matrices, which are further converted into $1600$-dimensional vectors. We do this conversion so that all methods in the comparison can be applied. While for our approach, it can be applied to network data directly by using a distance on network data in step 1 of Algorithms 1 and 2.

The results are presented in Table 5. We see that the new method is among the best performers in all settings, while other good performers could work well under some settings but fail for others.

If there are outliers in the data, the distance-based approach is much less robust. Considering the simulation setting scenario S1 (multivariate normal distribution) in Section 3.1 but contaminated by outliers $X_{i}\sim(5(a-1)+1)\mathbf{A}(x_{i1},x_{i2},\dots,x_{id})^{\top}+5\mu$, $i=1,2,\dots,n_{o}$, where $n_{o}$ is the number of outliers, and all other observations are simulated in the same way as before. Table 6 shows the misclassification rate of the two approaches. We see that with outliers, the distance-based has a much higher misclassification rate than the rank-based approach. Therefore, the rank-based approach is recommended in practice for its robustness. However, under the ideal scenario of no outliers, the performance of the two approaches is similar, and we could study the distance-based approach to approximate the rank-based version as the former is much easier to analyze.