王程锦，王秀友，林玉娥

(1.安徽理工大学 计算机科学与工程学院，安徽 淮南 232000；2.阜阳师范学院 计算机与信息工程学院，安徽 阜阳 236037)

关键字：最大边界准则；类内子空间；局部线性嵌入

模式识别技术是当前热门的研究方向，拥有广阔的应用前景[1-2]。目前已有许多经典算法，如主成分分析方法(principal components analysis,PCA)[3]、线性判别分析方法(linear discriminant analysis,LDA)[4]等。由于LDA算法能充分利用样本的判别信息，使它成为模式识别领域应用最广泛的方法之一[5-6]。然而LDA算法处理高维数据时会产生小样本问题[7-8]，为此研究人员提出了许多改进的 LDA 算法，如 PCA+LDA[9]、2D-LDA[10]、D-LDA[11]等。其中Li[12]等人提出了最大边界准则算法(maximum margin critrrion,MMC)，这种算法以类间散布矩阵与类内散布矩阵的迹之差作为鉴别准则，算法从理论上避免了LDA的小样本问题，并取得了较好的识别效果。目前许多研究人员基于MMC进行了研究[13-14]。但MMC的算法特性决定了它依旧很难处理非线性数据的缺陷。为了解决这个问题，流形学习算法开始兴起。He[15]等人提出了一种局部保留投影(locality preserving projections,LPP)算法；何力[16]等人提出基于放大因子和延伸方向研究流形学习算法；Roweis[17]等人提出了局部线性嵌入方法(locally linear embedding,LLE)。LLE能使降维后的高维数据尽可能地保持局部线性的拓扑结构，从而减小降维带来的误差[18-19]。但LLE不能获取样本的全局信息，故仍难以取得较理想的识别结果。

通过对上述算法的分析可知，MMC算法可以有效避免小样本问题但难以处理非线性数据；LLE算法能获取样本中的流形数据但不能充分利用类内信息。因此，本文提出一种基于类内子空间学习的局部线性嵌入算法(local linear embedding algorithm based on intra-class subspace learnning，ISL/LLE)。该方法使用最大边界准则的结构解决小样本问题，通过对类内离散度进行充分学习[20]，得到由类内子空间构成的类间离散度矩阵。同时，为弥补MMC不能处理非线性数据的不足，本文采用LLE找出样本数据中的流形结构，以获取样本数据中的非线性信息。

1 相关算法

假设X={x1,x2,…,xN}是初始数据的数据集合，且xi∈Rn,1≤i≤N。其中N为样本数，样本数据共有K类，1≤i≤K。通过对目标函数的运算，得到一个投影矩阵V以使高维度的原始数据投射到一个低维数据空间Y上，Y⊂Rd,d＜＜n，即Y=VTX。

1.1 最大间距准则函数

MMC算法以类间散布矩阵与类内散布矩阵之差作为目标函数运算准则，将高维的样本数据压缩至低维数据，并能保证投影之后的样本具很好的可分性。

令Sw、Sb分别表示类内、类间散布矩阵，其定义分别如下：

1.2 局部线性嵌入

LLE算法的基本思想是在极小的局部邻域内，用局部的线性值代替全局的非线性值，每个样本点都可根据其局部邻域点线性重构。使用互相重叠的局部邻域结构得到整体的完整信息，从而使降维的数据保有原有拓扑结构。算法步骤：

Step 1：基于欧氏距离公式，算出每一个样本点的K近邻。

Step 2：算出各个样本点的局部重构系数。

若Xj不是Xi的近邻，Wij=0；且（Wij是Xij所对应的重构权值）。

空调系统冷、热源机房是整个空调系统的心脏部位，其内部系统一般由以下几部分构成：①冷、热源主机；②各种辅助设备；③各种管道；④各种管道配件；⑤电气设备；⑥检控仪表。其中，涉及的管道配件种类及数量繁多，而各种新技术、新产品又层出不穷，因此在选用管道配件时，无论是设计人员还是现场的施工技术人员，往往都会有这样或者那样的困惑。在近些年的工程实践中，我们也发现过很多由于管道配件选用不当而影响系统正常工作的案例。为此，本文对选用管道配件的一些方法予以归纳，供参考。

Step 3：依据Step 2中的局部重构矩阵计算低维的嵌入空间的值。

式中，M=(I-W)T(I-W)。使式(6)中的优化问题的解为矩阵XTMXT的前d个最小特征值所对应的d个特征向量构成的矩阵。

2 基于类内子空间学习的局部线性嵌入

2.1 算法基本思想

ISL/LLE算法首先对类内散布矩阵进行深入学习，得到类内散布矩阵的子矩阵，再对所得的类内子矩阵进行学习，从而获取具有类内信息的类间散布矩阵；进一步给出了结合MMC与LLE的目标函数，从而充分挖掘出样本的非线性数据信息。一方面，ISL/LLE算法利用样本类内子空间，获取数据信息；另一方面，利用LLE算法的局部线性嵌入解决MMC算法不能获取非线性数据的问题。

首先，要对类内散布矩阵进行充分学习，设有第i类离散度定义如下

根据公式(7)，可对每类的类内离散度进行特征分解，即求得矩阵的前m个最小特征值对应的特征向量Ui={ui1,ui2,…,uim}。利用所得的子空间Ui，定义拥有类内信息的类间散布矩阵S′b

为保证计算的稳定性，令Sb=(S′b+(S′b)T)∕2 。同时，为了避免小样本问题，使用MMC的迹差形式有如下目标函数：

式(9)仅能获取样本的线性信息，然而人脸样本分布是复杂的、非线性的，为了进一步获取样本的非线性信息，故此本文综合式(6)和式(9)得到如式(10)的目标函数，即ISL/LLE的目标函数：

式(11)中，α(0≤α≤1)为平衡参数，则其最小化函数问题可以使用拉格朗日乘数法来解决

所以，当V={v1,v2,…,vd}是由前d个最小特征向量组成时，所求目标函数值最小。

2.2 算法描述

ISL/LLE算法如下：

输入:原始样本数据X。

输出:降维后的低维子空间Y。

Step 1：求取初始类内离散度矩阵Sw。

Step 3：利用Ui计算具有类内信息的类间离散度。

Step 4：根据式(6)计算LLE中相似矩阵M。

Step 6：通过Y=VT求得高维样本数据对应的低维空间Y。

3 实验

为了验证本文算法的识别性能，在ORL、AR和YALE三种人脸库上进行实验，并对比其他几种算法LLE、MMC和ISL的算法性能。每种算法都使用PCA进行预处理，且采用统一的最近邻分类器进行分类。

3.1 参数选择

α值的选择会对实验的结果产生直接的影响，所以，此次实验将在ORL、AR和YALE等数据库中进行实验，以选择各个数据库适合的α值。

由图1可以得出，在ORL、AR和YALE数据库中，使SIL/LLE取得最大平均识别率α的值分别为0.3、0.1和0.6。为提高算法的高效性，后续实验中使用每个数据库中对应的最优α值。

3.2 以样本数为自变量时的实验

分别随机选取三种人脸库的4/5/6幅图像作为训练样本，其余的作为测试样本进行实验。将ISL/LLE算法与其他几种算法的平均识别率进行对比，如表1～3所示。

图1 三种人脸库上不同α值下的平均识别率

表1 ORL人脸库上不同样本数下的平均识别率

表2 AR人脸库上不同样本数下的平均识别率

表3 YALE人脸库上不同样本数下的平均识别率

3.3 以维数为自变量时的实验

在取相同的训练样本数的情况下，以投影矩阵的维数作为自变量，如此对每种算法进行实验。实验结果如图2～4。

由表1～3可看出随着测试样本数目改变，ISL/LLE算法的识别率始终高于其他算法。这说明通过对类内信息的再学习，可以获取有利于分类的信息从而提高算法的识别性能。由图2～4可以看出ISL/LLE总体识别效果优于其他三种算法，这是由于ISL/LLE采用了既能获取样本的局部信息又能获得样本的全局信息，从而在识别过程中获得了更为有效的判别特征。

图2 ORL人脸库上不同维数下的平均识别率

图3 AR人脸库上不同维数下的平均识别率

图4 YALE人脸库上不同维数下的平均识别率

4 小结

本文在LLE和MMC的算法基础上，提出一种ISL/LLE算法。该算法首先对类内散布矩阵进行充分学习，获得由类内子空间构成的类间散布矩阵；同时利用LLE对非线性数据进行学习，从而有效地解决了LLE算法不能有效地利用判别信息及MMC算法不能获取非线性数据的问题。在ORL、AR和YALE等数据库上的实验也表明，ISL/LLE算法具有更好的识别率。但对于ISL/LLE识别的时间效率问题没有进行深入探讨，这将是笔者之后研究的方向。