一种无参数的局部线性判别分析方法

A Parameter-Free Local Linear Discriminant Analysis Method

摘要: 为了解决因引入局部化思想的线性判别分析(Linear Discriminant Analysis, LDA)方法需要人工设置邻居个数而无法以自适应的方式挖掘数据的局部结构问题，提出了一种无参数的局部线性判别分析(Parameter-free Local Linear Discriminant Analysis, Pf-LLDA)方法。该方法首先建立了一个关于权重矩阵和变换矩阵的统一优化模型。然后，通过使用交替方向的方法迭代求解出了与数据局部结构相关的权重矩阵和与判别分析相关的变换矩阵。从而使得Pf-LLDA在无需人为设定邻居个数的情况下，自适应地挖掘出了数据的局部结构并最终实现了局部线性判别分析的能力。在仿真数据集和手写体真实数据集上的实验结果表明，Pf-LLDA挖掘出数据局部结构的同时实现了更优的判别分析结果。

Abstract: For the Linear Discriminant Analysis (LDA) method which utilized the idea of localization and setting the number of neighbors by hand, it cannot mine the local structure embedded in the data adaptively. In order to solve this problem, this paper proposes a Parameter-free Local Linear Discriminant Analysis (Pf-LLDA) method. This method first establishes a unified optimization model about the weight matrix and the transformation matrix. Then, by using the alternating direction method, the solution of the weight matrix, which is associated with the local structure embedded in the data, and the transformation matrix, which is associated with the discriminant analysis are iteratively well found. Thus, Pf-LLDA adaptively mines the local structure of the data and finally achieves the capability of local linear discriminant analysis without artificially setting the number of neighbors. Experimental results on both synthetic and handwritten real datasets show that Pf-LLDA achieves better discriminant analysis results while mining the local structure of the data.

1. 引言

维度约简在解决维度灾难问题上具有很重要的作用。降维作为维度约简中最为直观的一种方法在模式识别和机器学习领域具有很重要的研究意义 [1]。

通常来讲，根据是否使用了数据标签信息，降维方法可以被简单的分为有监督的降维方法和无监督的降维方法 [2]。相对于无监督的降维方法，有监督的降维方法因为利用了已知的数据标签信息而被更广泛的采用。线性判别分析(Linear Discriminant Analysis, LDA) [1] [2] 便是一个典例。LDA通过最大化类间距离的同时并最小化类内距离的方式找到了具有判别性的线性变换。但由于LDA用样本均值代表整体样本的方式构造类内散度矩阵和整体散度矩阵，当同类样本不满足高斯分布假设(即多模态现象)时 [3]，LDA将失去判别能力。为了使LDA能有效地应对多模态现象，国内外众多学者在传统LDA中引入了数据的局部结构。比较典型的有：非参数¹判别分析(Nonparametric Discriminant Analysis, NDA) [4]，局部Fisher判别分析(Local Fisher Discriminant Analysis, LFDA) [3] 和局部敏感判别分析 [5] (Locality Sensitive Discriminant Analysis, LSDA)等。更为具体地，NDA通过将每个样本替换表示成其近邻样本加权的形式引入了数据的局部结构。LFDA首先将LDA中的类内和整体散度矩阵重新表示成样本间距离平方和的形式，然后再引入局部保留投影的思想使样本在降维前后保持着一致的邻居关系，从而达到局部结构的引入。不同于LFDA，LSDA从谱图理论出发，通过将图表示成拉普拉斯矩阵的形式引入了数据的局部结构。此外，还有许多在LFDA和LSDA模型基础上的变体 [6] [7] [8]，这些变体本质上都是通过改变样本间相似关系的权重值或者图节点间边值的大小得到对数据结构更准确的近邻表达。不幸的是，这些方法在引入数据局部结构时都必须人为设定样本的近邻个数。该近邻个数参数决定性地影响着数据降维后的可分性，且其具体值的确定需要科研人员对数据的先验知识具有很全面的认识，这很大程度上限制了局部线性判别分析方法的广泛应用 [9]。因此，仅根据已有的数据样本，自动对数据进行局部线性判别分析是一个非常值得研究的问题 [10]，同时在图像检索 [4] 和人脸识别 [11] 等方面具有很重要的应用价值。

受自权重自适应局部判别分析(Self-weighted Adaptive Locality Discriminant Analysis, SALDA) [9] 的启发，本文提出了一种无参数的局部判别分析(Parameter-free Local Linear Discriminant Analysis, Pf-LLDA)方法。Pf-LLDA首先建立一个与LDA类似的模型。但不同于LDA模型只需要求解与降维相关的变换矩阵，Pf-LLDA不仅需要求解与降维相关的变换矩阵还需要求解与数据局部结构相关的权重矩阵。通过运用交替方向的优化求解思路 [12]，Pf-LLDA模型在无需设置近邻个数的前提下得到了反映数据结构图的权重矩阵和考虑了数据局部结构性质的变换矩阵。最后，根据变换矩阵得到了测试样本的低维表示，并将其输入到k近邻分类器中进行验证。在仿真和真实数据集上的实验结果表明，Pf-LLDA不仅在多模态问题上实现了无参数的局部判别分析性能，而且在手写字体识别问题上相比其他方法得到了更优的结果。

2. 算法描述

本章从已有的工作出发，引出了无参数的局部判别分析(Parameter-free Local Linear Discriminant Analysis, Pf-LLDA)模型，并给出了具体的求解方法与伪代码。更具体地，2.1节、2.2节和2.3节分别概述了线性判别分析(Linear Discriminant Analysis, LDA)、局部Fisher判别分析(Local Fisher Discriminant Analysis, LFDA)和自权重自适应局部判别分析(Self-weighted Adaptive Locality Discriminant Analysis, SALDA)模型；2.4节详细阐述了Pf-LLDA模型与求解方案。

2.1. 线性判别分析(LDA)

给定n个m维的数据样本 $X=\left[x_1,\cdots ,x_n\right]\in {ℝ}^{m\times n}$，并且已知这些样本来自c个不同的类别，LDA可以通过以下固定整体分散度的同时最小化类内分散度的方式得到具有判别性的变换矩阵 $A\in {ℝ}^{m\times d}$。

$\begin{array}{l}\underset{A}{\min }\text{Tr}\left(A^{\text{T}}{S}_{w}A\right)\\ s.t.A^{\text{T}}{S}_{t}A=I_d\end{array}$ (1)

这里，d表示低维目标空间的维数； $\text{Tr}\left(X\right)$ 表示对矩阵X的求迹运算； $X^{\text{T}}$ 表示对矩阵X转置； $I_d$ 表示 $d\times d$ 维的单位阵。 $S_w$ 和 $S_t$ 分别表示数据的类内散度矩阵和整体散度矩阵，并分别由以下公式计算 [3] [7]：

$\begin{array}{c}{S}_w={\displaystyle {\sum }_{i=1}^c{\displaystyle {\sum }_{j=1}^{n_i}\left(x_j^i-{\mu }^i\right){\left(x_j^i-{\mu }^i\right)}^{\text{T}}}}\\ =\frac{1}{2}{\displaystyle {\sum }_{i=1}^c\frac{1}{n_i}{\displaystyle {\sum }_{j=1}^{n_i}{\displaystyle {\sum }_{k=1}^{n_i}\left(x_j^i-x_k^i\right){\left(x_j^i-x_k^i\right)}^{\text{T}}}}},\end{array}$ (2)

$\begin{array}{c}{S}_t={\displaystyle {\sum }_{j=1}^n\left(x_i-\mu \right){\left(x_i-\mu \right)}^{\text{T}}}\\ =\frac{1}{2n}{\displaystyle {\sum }_{j=1}^n{\displaystyle {\sum }_{k=1}^n\left(x_j-x_k\right){\left(x_j-x_k\right)}^{\text{T}}}}.\end{array}$ (3)

其中， $x_j^i$ 表示属于类别i的样本 $x_j$ ； $n_i$ 表示属于类别i的样本个数； $\mu$ 和 ${\mu }^i$ 分别表示所有样本的均值和属于类别i的样本均值。最终，LDA的变换矩阵A可以通过求解如下广义特征值问题的最小的特征值所对应的特征向量得到 [1] [2]：

$S_{w}A=\lambda S_{t}A.$ (4)

2.2. 局部Fisher判别分析(LFDA)

局部Fisher判别分析通过将样本的近邻结构引入到构建类内散度矩阵和整体散度矩阵中，使得模型具有局部判别能力并能很好地对多模态分布下的数据进行有效降维。具体地，LFDA首先以如下方式重新定义了LDA的类内散度矩阵(2)和整体散度矩阵(3)：

$\begin{array}{c}{\hat{S}}_w=\frac{1}{2}{\displaystyle {\sum }_{j=1}^n{\displaystyle {\sum }_{k=1}^n{W}_{jk}^{\left(w\right)}\left(x_j-x_k\right){\left(x_j-x_k\right)}^{\text{T}}}}\\ ={\displaystyle {\sum }_{j=1}^n\left({\displaystyle {\sum }_{k=1}^n{W}_{jk}^{\left(w\right)}}\right)x_j{x}_k^{\text{T}}}-{\displaystyle {\sum }_{j=1}^n{\displaystyle {\sum }_{k=1}^n{W}_{jk}^{\left(w\right)}{x}_j{x}_k^{\mathrm{T}}}}\\ =X{D}^{\left(w\right)}{X}^{\text{T}}-X{W}^{\left(w\right)}{X}^{\text{T}}=X{L}^{\left(w\right)}{X}^{\text{T}},\end{array}$ (5)

$\begin{array}{c}{\hat{S}}_t=\frac{1}{2}{\displaystyle {\sum }_{j=1}^n{\displaystyle {\sum }_{k=1}^n{W}_{jk}^{\left(w\right)}\left(x_j-x_k\right){\left(x_j-x_k\right)}^{\text{T}}}}\\ =X{D}^{\left(t\right)}{X}^{\text{T}}-X{W}^{\left(t\right)}{X}^{\text{T}}=X{L}^{\left(t\right)}{X}^{\text{T}}.\end{array}$ (6)

其中， $D^{\left(i\right)}\in {ℝ}^{n\times n},i=\left\{w,t\right\}$ 表示以对称矩阵 $W^{\left(i\right)}\in {ℝ}^{n\times n},i=\left\{w,t\right\}$ 的行和为对角元素构造的对角矩阵；而权重矩阵 $W^{\left(i\right)}\in {ℝ}^{n\times n},i=\left\{w,t\right\}$ 以如下形式定义：

$W_{jk}^{\left(w\right)}=\{\begin{array}{l}{W}_{ij}/n_i,\text{if}{y}_j=y_k=i\\ 0,\text{otherwise}\end{array}$ (7)

$W_{jk}^{\left(t\right)}=\{\begin{array}{l}{W}_{ij}/n,\text{if}{y}_j=y_k\\ 1/n,\text{otherwise}\end{array}$ (8)

这里， $y_j$ 表示样本 $x_j$ 的类别标签；W表示与样本近邻相关的仿射矩阵。一种简单的定义方式是：当样本 $x_j$ 与样本 $x_k$ 互为近邻时， $W_{ij}=1$，否则 $W_{ij}=0$。更多关于W的定义方式可以参考文献 [3]，需要强调的是，无论哪种定义方式，样本近邻点的个数都是需要人为指定的。最后LFDA使用改进的类内散度矩阵 ${\hat{S}}_w$ 和整体散度矩阵 ${\hat{S}}_t$ 对应地替换LDA中的 $S_w$ 和 $S_t$，得到与LDA类似的模型：

$\begin{array}{l}\underset{A}{\min }\text{Tr}\left(A^{\text{T}}{\hat{S}}_{w}A\right)\\ s.t.A^{\text{T}}{\hat{S}}_{t}A=I_d\end{array}$ (9)

从而以类似于公式(4)的方式求得最终的变换矩阵。

2.3. 自权重自适应局部判别分析(SALDA)

不同于LFDA使用人为指定样本近邻个数的方式来挖掘数据的局部结构，SALDA尝试根据数据自身信息自适应地挖掘数据的局部流型结构来达到局部判别分析的目的。具体而言，首先根据矩阵的迹运算和矩阵元素形式的F-范数等价的性质，即对于方阵 $X\in {ℝ}^{m\times n}$， $\text{Tr}\left(X^{\text{T}}X\right)={\Vert X\Vert }_F^2={\displaystyle {\sum }_{i=1}^m{\displaystyle {\sum }_{j=1}^n{X}_{ij}^2}}$，以及公式(2)，易得：

$\text{Tr}\left(A^{\text{T}}{S}_{w}A\right)=\frac{1}{2}{\displaystyle {\sum }_{i=1}^c\frac{1}{n_i}{\displaystyle {\sum }_{j=1}^{n_i}{\displaystyle {\sum }_{k=1}^{n_i}{\Vert A^{\text{T}}\left(x_j^i-x_k^i\right)\Vert }_F^2},}}$ (10)

这里 ${\Vert X\Vert }_F$ 表示矩阵X元素形式的F-范数。因此，单独将控制样本间差异的权重W提出来并控制其为正数，则由公式(10)与传统LDA模型(1)便可得到SALDA模型 [9]：

$\begin{array}{l}\underset{A}{\min }{\displaystyle {\sum }_{i=1}^c{\displaystyle {\sum }_{j=1}^{n_i}{\displaystyle {\sum }_{k=1}^{n_i}{W}_{jk}^i{\Vert A^{\text{T}}\left(x_j^i-x_k^i\right)\Vert }_F^2}}}\\ s.t.A^{\text{T}}{S}_{t}A=I_d,W_{jk}^i\ge 0,\end{array}$ (11)

需要注意的是，这里的权重W只是作为常数值单独进行表示而非模型的求解变量。参考LFDA中定义近邻结构的仿射矩阵发现，其内部的每一个元素表示样本相关性的大小。换句话说，当样本距离越近时，对应在仿射矩阵中的值就越大。因此，根据F-范数与欧拉距离的相似性定义，SALDA通过以下对同类别 内的样本对 $x_j$ 和 $x_k$ 的求欧拉距离的倒数形式定义W中的每一个元素值 [13] [14]：

$W_{jk}^i=\frac{1}{2{\Vert A^{\text{T}}\left(x_j^i-x_k^i\right)\Vert }_F},$ (12)

当得到W时，模型就可以重新表示成：

$\begin{array}{l}\underset{A}{\min }\text{Tr}\left(A^{\text{T}}XL{X}^{\text{T}}A\right)\\ s.t.A^{\text{T}}{S}_{t}A=I_d\end{array}$ (13)

这里，拉普拉斯矩阵 $L=D-W$，D是由权重矩阵W得到的对角矩阵，其对角线上的元素为W对应行中所有元素值之和，即 $D_{ii}={\displaystyle {\sum }_{j=1}^n{W}_{ij}}$。显然，若记 ${\tilde{S}}_w=XL{X}^{\text{T}}$，模型(13)与模型(1)具有类似的结构，所以同样可以通过广义特征值分解的方法进行求解。

值得强调的是，SALDA为了运用近邻思想并避开近邻个数的设置来挖掘数据的局部结构，采用构建具有仿射矩阵性质的方式固定计算权重矩阵W。这种方式虽然在构建仿射矩阵方面似乎是有效的，但是在整体模型上却不是很合理。一方面，模型(11)中的待求解变量只有变换矩阵A，但模型却是以迭代计算(12)和求解子模型(13)的方式进行求解；另一方面，W并不是模型要求解的参数，但又参与模型的更新求解，这不仅模糊了模型的可解释性也导致模型的求解并不一定收敛。

2.4. 无参数的局部判别分析(Pf-LLDA)

受SALDA启发，我们将权重矩阵 假定为一个需要求解的未知量，得到如下Pf-LLDA模型：

$\begin{array}{l}\underset{\left(A,W\right)}{\min }{\displaystyle {\sum }_{i=1}^c{n}_i}{\displaystyle {\sum }_{j=1}^{n_i}{\displaystyle {\sum }_{k=1}^{n_i}{W}_{ij}^i{}^2{\Vert A^{\text{T}}\left(x_j^i-x_k^i\right)\Vert }_F^2}}\\ s.t.A^{\text{T}}{S}_{t}A=I_d,W_{jk}^i\ge 0,{\displaystyle {\sum }_{k=1}^{n_i}{W}_{jk}^i=\frac{n_i}{n}}.\end{array}$ (14)

相比于SALDA模型(11)，Pf-LLDA主要有以下几方面的不同：

• Pf-LLDA模型将变换矩阵A与权重矩阵W共同作为模型待求解的未知量进行建模，而SALDA只对变换矩阵A进行了建模；

• Pf-LLDA通过控制同类别样本的权重和为定值，理论地给出了W的自适应更新公式。相比于SALDA直接设定而无法保证收敛的方式，Pf-LLDA关于W的更新不仅具有可解释性而且保证模型收敛；

• Pf-LLDA通过设定不同类样本的权重和为 $n^i/n$ 的方式对不同类别进行了区分使得模型适用于类别失衡问题从而更好地提升降维性能。

模型(14)可以通过交替方向的优化求解思路 [12] 迭代进行求解。下面具体给出了针对W和A的求解方式。

2.4.1. 固定W，更新A

当权重矩阵固定，即W为已知数时，模型(14)转换成：

$\begin{array}{l}\underset{A}{\min }{\displaystyle {\sum }_{i=1}^c{n}_i}{\displaystyle {\sum }_{j=1}^{n_i}{\displaystyle {\sum }_{k=1}^{n_i}{W}_{ij}^i{}^2{\Vert A^{\text{T}}\left(x_j^i-x_k^i\right)\Vert }_F^2}}\\ s.t.A^{\text{T}}{S}_{t}A=I_d\end{array}$ (15)

与公式(10)的推导类似，模型(15)可进一步转换成模型(13)的形式。因此以上问题(15)可以通过广义特征值的方法进行求解。

2.4.2. 固定A，更新W

当变换矩阵固定，即A为已知数时，模型(14)转换成：

$\begin{array}{l}\underset{W}{\min }{\displaystyle {\sum }_{i=1}^c{n}_i{\displaystyle {\sum }_{j=1}^{n_i}{\displaystyle {\sum }_{k=1}^{n_i}{W}_{ij}^i{}^2{\Vert A^{\text{T}}\left(x_j^i-x_k^i\right)\Vert }_F^2}}}\\ s.t.W_{jk}^i\ge 0,{\displaystyle {\sum }_{k=1}^{n_i}{W}_{jk}^i}=\frac{n_i}{n}.\end{array}$ (16)

模型(16)可以通过分别求解它的一般化子模型来得到最终的W。具体而言，对于任意确定的i和j，令向量 $u=W_{j\cdot }^i\in {ℝ}^{n_i\times 1}$，其中 $W_{j\cdot }^i={\left[W_{j1}^i,\cdots ,W_{j{n}_i}^i\right]}^{\text{T}}$。同时令对角矩阵 $V=diag\left({\Vert A^{\text{T}}\left(x_j^i-x_k^i\right)\Vert }_F^2\right),k=1,\cdots ,n_i$，即V的对角线元素为 $V_{kk}={\Vert A^{\text{T}}\left(x_j^i-x_k^i\right)\Vert }_F^2$。所以模型(16)在固定i和j时，可得到通用子模型：

$\begin{array}{l}\underset{u}{\min }{u}^{\text{T}}Vu\\ s.t.u\ge 0,u^{\text{T}}1=\frac{n_i}{n}.\end{array}$ (17)

这里 $1\in {ℝ}^{n_i\times 1}$ 表示长度为 $n_i$ 的全1列向量。模型(17)可以通过拉格朗日乘子法 [1] 计算得出u的每一个元素，具体如下：

$u_k=\frac{n_i}{n\cdot V_{kk}}{\left({\displaystyle {\sum }_{t=1}^{n_i}\frac{1}{V_{tt}}}\right)}^{-1},k=1,\cdots ,n_i.$ (18)

所以，模型(16)的最优解 $W^{*}$ 满足：

$W_{jk}^i{}^{*}=\frac{n_i}{n\cdot {\Vert A^{\text{T}}\left(x_j^i-x_k^i\right)\Vert }_F^2}{\left({\displaystyle {\sum }_{t=1}^{n_i}\frac{1}{{\Vert A^{\text{T}}\left(x_j^i-x_k^i\right)\Vert }_F^2}}\right)}^{-1},i=1,\cdots ,c;j=1,\cdots ,n_i;k=1,\cdots ,n_i.$ (19)

有趣的是，Pf-LLDA通过设置W为模型变量的方式求解出来的结果与SALDA分析仿射矩阵性质的方式固定W的结果具有类似的结构。但由于SALDA缺乏理论的推导，同时更新公式(12)与(19)并非完全一样，导致SALDA模型求解时并不一定收敛。最终求解模型(14)的算法流程如算法1所示，其中初始化目标函数值 $o_0=+\infty ,o_1=1$ 保证了算法能正常进行循环迭代求解过程。当目标函数值在迭代更新前后的变化量小于精度误差 $\epsilon ={10}^{-6}$ 时，循环终止，并返回最终的变换矩阵A。

Algorithm 1. The algorithm of parameter-free local linear discriminant analysis

算法1. 无参数的局部判别分析算法

3. 实验与分析

为了系统检验算法的有效性，我们分别对比了本文提出的算法与其它相关算法在两个仿真数据集与一个真实数据集上的表现。

3.1. 仿真数据集上的实验

如图1所示，每个数据集中有两个类，每类包含200个二维的数据点。图1a中两个类别的数据由均值为[−1, 0]和[1, 0]，方差同为[0.1, 0; 0, 1]的二维高斯分布函数生成。图1b中类别I的数据由均值为[−3, 0]和[3, 0]，方差同为[0.5, 0; 0, 0.5]的两个二维高斯分布函数生成；类别II的数据由均值为[0, 0]，方差为[0.1, 0; 0, 1]的二维高斯分布函数生成。显然，图1a中的不同类别的数据点只由一个高斯分布产生，即只存在单模态现象；而图1b中的类别I的数据集是由两个高斯分布的数据点构成，所以存在多模态现象。

(a) 单模态(b) 多模态

Figure 1. The projection of different method on simulation datasets

图1. 不同方法在仿真数据集的投影方向

我们在这两个仿真数据上对比了线性判别分析(Linear Discriminant Analysis, LDA) [4]、局部Fisher判别分析(Local Fisher Discriminant Analysis, LFDA) [3]、自权重自适应局部判别分析(Self-weighted Adaptive Locality Discriminant Analysis, SALDA) [9] 和我们提出的无参数的局部判别分析(Parameter-free Local Linear Discriminant Analysis, Pf-LLDA)方法。如图1所示，每种方法的一维投影线已经被描绘出来。不难发现，在单模态数据集上(图1a)，LDA、LFDA和Pf-LLDA都能找到合理的投影方向。但在多模态数据集上(图1b)，LDA却失败了。另一方面，SALDA无论在哪种模态的数据集上似乎都不具备判别能力。其主要的原因有：1) 由2.4节的分析和2.3节中权重更新公式(12)可知，SALDA通过简单对样本距离求倒数的方式很难保证模型收敛；2) 分析SALDA的代码²实现发现，SALDA主要是因为迭代了超过所设置的最大次数(1000次)而跳出模型求解。这就导致了SALDA得到的投影结果更倾向于陷入随机的一个局部最优值。相比之下，我们不仅通过理论证明了Pf-LLDA权重的更新方式实现了如LFDA的局部判别性分析，同时在这两个仿真数据集上以算法1的实现方式都能保证在100次迭代内完成收敛。

3.2. 真实数据集上的实验

²https://github.com/guomuhan/salda2/blob/master/ADLDA.m

USUP³是一个手写数字图像数据集。它是模式识别领域研究所广泛使用的数据集之一，扫描于美国邮局的邮件中，具有很好的普适性。我们随机取了其中5500张手写数字图像作为我们的实验数据，每张图像是由16 × 16像素点的灰度图组成。图2显示了该数据集中的部分样本。

需要说明的是，为了避免降维算法中存在的过度降维 [11] 和小样本 [15] 问题，与文献 [13] 类似，我们首先对所有数据进行主成分分析 [1] [2] 处理，将每个样本表示成79维的向量。然后，将训练样本输入到LDA相关的算法中得到变换矩阵和低维表示的训练样本。接着，根据变换矩阵对测试样本进行降维，得到低维表示的测试样本。最后，将低维表示的测试样本和训练样本作为1近邻算法 [1] [9] 的输入，得到关于测试样本的分类准确率。需要说明的是，为了结果的准确性，每组实验都会独立重复30次并将最终准确率的平均值记录下来。

Figure 2. Part of samples in USUP dataset

图2. USUP数据集中的部分样本

我们在真实数据集对比了LDA、NDA、FLDA、SALDA和局部敏感判别分析 [5] (Locality Sensitive Discriminant Analysis, LSDA)方法。并用控制变量法从训练样本个数、所降的维度、近邻个数和类别个数四个角度进行实验验证。每个实验角度的参数由表1给出。具体而言，表1中关于“训练样本个数”角度的实验参数由第二列给出。此时，样本最终的维度为60；通过引入近邻个数实现的局部线性判别分析算法的近邻个数参数为5；数据的类别个数为5；而来自每类的训练样本个数为*：表示它是这组实验所要研究的变量。其他三个角度的实验参数设置同理。

Table 1. The detailed parameters for each experiment

表1. 各个实验的具体参数

表2对比了当每类训练样本为5、10、20、40、80、160和320时，各种方法在USUP数据集上的分类准确率。不难发现，当所降维度、近邻个数和类别个数相同时，所有方法的分类准确率会随着训练样本的增加而有所提升。相比之下，Pf-LLDA总体上得到了更好的分类效果。特别是在训练样本数较少的情况下，Pf-LLDA的优势更为明显。

Table 2. The classification accuracy with different number of training samples (%)

表2. 不同训练样本个数下的分类准确率(%)

表3对比了当训练样本数、近邻个数和类别个数相同时，不同方法将样本从高维降到不同低维度时的准确率。需要注意的是，每个样本经过主成分分析表示成79维的向量，所以所降的维度最高被设置为78。对比发现，在所降的维度较低时，Pf-LLDA相比于其他方法还是可以接受的。并且随着所降的维度的升高，Pf-LLDA实现了更高的准确率上限。

Table 3. The classification accuracy with different reduced dimensions (%)

表3. 不同所降维度下的分类准确率(%)

图3描绘了对于不同的局部判别分析方法，近邻个数对分类准确率的影响。这里我们只展示了近邻个数从1到39时的结果。可以看到，不同的近邻个数对NDA、LFDA和LSDA的分类效果影响很大。特别地，LSDA的分类准确率由近邻个数为3时的73.73%降到近邻个数为37时的60.07%。相比之下，SALDA通过自权重的方式避开了对近邻个数的依赖从而实现了稳定的结果输出。但与2.4节中的分析一致，SALDA陷入随机的一个局部最优值导致其分类准确率并不理想。Pf-LLDA克服了SALDA的缺点，不仅实现了稳定的结果，同时也得到了较高的准确率。

Figure 3. The influence of the number of nearest neighbors on classification accuracy

图3. 近邻个数对分类准确率的影响

最后，我们验证了当类别个数从4增加到10时，不同方法的分类结果。如表4所示，相比于其他四种局部判别分析方法和作为基线的LDA方法，Pf-LLDA得到了显著的提升。这不仅依赖于Pf-LLDA利用了数据的局部结构，也依赖于我们所引入的无参方式自适应地挖掘出数据局部几何结构的差异性。

Table 4. The classification accuracy with different number of classes (%)

表4. 不同类别个数下的分类准确率(%)

4. 总结

本文提出了一种无参数的局部判别分析方法。该方法通过利用已知的数据信息，自适应地学习到了数据的低维局部结构。系统的实验结果表明，该方法在无需人为设置近邻个数的情况下，不仅挖掘出了数据的局部结构还有效的提高了分类准确率。未来将在模型中引入非线性或张量的思想，使模型适用于挖掘更复杂数据的数据结构。

NOTES

³https://www.kaggle.com/bistaumanga/usps-dataset