Hans Journal of Data Mining
Vol. 09  No. 02 ( 2019 ), Article ID: 29848 , 10 pages
10.12677/HJDM.2019.92006

Enhanced Linear Discriminant Projections with Global plus Local Information

Weiqi Mai

School of Mathematics, South China University of Technology, Guangzhou Guangdong

Received: Apr. 4th, 2019; accepted: Apr. 17th, 2019; published: Apr. 24th, 2019

ABSTRACT

Linear Discriminant Projection (LDP) is a supervised feature extraction method, which makes good results in image processing and other areas. However, the LDP only considers global information, ignoring information contained in local neighboring points. The problem of ignoring local information also exists in Linear Discriminant Analysis (LDA). At present, in the research of LDA, some scholars have sorted out a complete algorithm framework combining global and local aspects to solve this problem. Since the structure of the objective function of LDP and LDA is similar, this paper considers to apply the algorithm framework of LDA’s global and local combination to LDP on the basis of LDP algorithm, so as to realize the complete combination of global and local information of LDP, and obtain the new algorithm: Enhanced Within-class Linear Discriminant Projection (EWLDP) and Complete Global-local Linear Discriminant Projection (CGLDP). Finally, this paper uses Iris data set to prove that the dimensionality reduction effect of CGLDP and EWLDP algorithm is better than LDP, and CGLDP integrates local information more completely, and the performance is also better than EWLDP.

Keywords:LDP, Global Information, Local Information, LDA

全局加局部的线性判别投影

麦炜琪

华南理工大学数学学院,广东 广州

收稿日期:2019年4月4日;录用日期:2019年4月17日;发布日期:2019年4月24日

摘 要

线性判别投影(Linear Discriminant Projection, LDP)是一种有监督的特征提取方法,在图像处理等邻域得到了很好的效果。然而LDP只考虑全局信息,忽略了局部邻近点中包含的信息。忽略局部信息的问题也出现在线性判别分析(Linear Discriminant Analysis, LDA)中。目前在LDA的研究中,针对这个问题已经有学者整理出了一个完整的全局结合局部的算法框架。由于LDP和LDA的目标函数结构相似,本文考虑在LDP的算法基础上,将LDA全局结合局部的算法框架沿用到LDP中,使LDP实现全局信息和局部信息的完整结合,得到新算法:增强组间线性判别投影(Enhanced Within-class Linear Discriminant Projection, EWLDP)、完全线性判别投影(Complete Global-local Linear Discriminant Projection, CGLDP)。最后本文利用鸢尾花数据集(Iris),证实CGLDP、EWLDP算法的降维效果比LDP更优,并且CGLDP更完整地结合了局部信息,效果也比EWLDP更优。

关键词 :LDP,全局信息,局部信息,LDA

Copyright © 2019 by author(s) and Hans Publishers Inc.

This work is licensed under the Creative Commons Attribution International License (CC BY).

http://creativecommons.org/licenses/by/4.0/

1. 绪论

1.1. 引言

在模式识别和数据预处理的机器学习任务中,我们常常面临“维度灾难”的问题。提取特征维度过高或者提取错误特征,都会给后续的判别分类带来负面影响,如计算复杂性过高、分类器不稳定。为了克服维度灾难和提取正确的特征,降维成为了一个热门的研究方向。

1.2. 研究背景

降维主要分为两个方向:有监督学习和无监督学习。在监督学习方向,主要代表有线性判别分析(LDA)、线性判别投影(LDP) [1] ,LDA和LDP的基本思想都是通过投影,使得投影后不同类别的数据点尽可能分开,而相同类别的数据点尽可能靠近;在无监督学习方向,主要代表有主成分分析(PCA),PCA选取样本协方差矩阵特征值较大的特征方向作为新坐标系,以最大程度保留数据点的原始信息。由于有监督学习考虑了样本数据的标签,因此有监督学习的分类效果自然比无监督学习更好。然而,LDA、LDP算法只考虑了样本数据的全局信息,却忽略了局部样本点之间隐含的信息,而局部信息对判别分类存在不可忽略的影响。

目前关于结合局部信息进行线性判别或线性投影的研究已经取得了比较好的结果 [2] - [10] ,其中局部信息结合性最强的算法代表有 [2] :enhanced within-class LDA (EWLDA)、complete global-local LDA (CGLDA)。其中CGLDA完整地结合了三种局部信息:局部相似信息、局部组间模式多样性、局部组内模式多样性。这两个算法在实证中都比原始LDA算法和其他改进的LDA算法(HLDA、LocLDA、LFDA、EFDC、GbFA、UDP)表现更好。

然而相较于LDA算法,目前结合局部信息的LDP算法的文献相对较少,进展也相对落后于LDA算法。这在实际应用场景中,导致了LDP算法的局限性和弱表现性。

1.3. 研究意义

目前来说,尚未有研究将LDP算法完整地结合三种局部信息,本文将沿用LDA的研究成果,在LDP上实现全局信息和局部信息的完整结合,得到一种新的特征提取的算法。本文通过在实际场景中将改良的LDP算法和其他特征提取算法作比较,证实了LDP算法的在实际场景中的表现优良性。因此,也证实了全局信息结合局部信息这一思想的可延拓性。对特征选取方法具有重要的理论意义和广阔的应用前景。

1.4. 论文结构

本文分为四章。其中第一章简述了LDP、LDA算法的研究现状,提出了全局结合局部的算法思想。第二章节简述了LDP、LDA算法的基础知识。第三章介绍全局结合局部的LDP算法的原理。第四章是鸢尾花实验的结果与分析。

2. 基础知识

2.1. 线性判别投影(LDP)

LDP的基本思想是投影 [1] :将样本点投影到某一个方向,使得投影后组与组之间尽可能地分开,同一组的尽可能靠近。LDP的判别函数是线性的,在实际应用中也比较方便。

在判别分类问题中,设从总体 G t ( t = 1 , , k ) 中共抽取出n个d维样本 x 1 , x 2 , , x n ,LDP算法的目标是找到投影方向v,在该方向上组间距离和组内距离的比值最大化:

arg max v v C D v v C S v (2-1)

其中,组间离散矩阵:

C D = ( i , j ) D ( x i x j ) ( x i x j ) (2-2)

组内离散矩阵:

C S = ( i , j ) S ( x i x j ) ( x i x j ) (2-3)

D代表不同类别标签的样本点集,S代表相同类别标签的样本点集。 C S 记录了不同类别标签的样本点之间的距离, C S 记录了相同类别标签的样本点之间的距离。

事实上,LDP目标是由两个子目标组成的:

arg max v v C D v (2-4)

arg min v v C S v (2-5)

其中目标(2-4)使不同类别标签的数据点投影后距离最大化,目标(2-5)使相同类别标签的数据点投影后距离最小化。显然,LDP忽略了局部邻近点中的信息,后面针对这一问题对LDP作进一步的改进。

2.2. 线性判别分析(LDA)

LDA的基本思想和LDP一致,其判别准则利用方差分析的思想,将问题化为求投影方向 v ,使FISHER判别准则达到最大值:

arg max v v S B v v S W v (2-6)

其中,组间离差矩阵:

S B = t = 1 k n t ( μ t μ ) ( μ t μ ) (2-7)

组内离差矩阵:

S W = t = 1 k j = 1 n t ( x j t μ t ) ( x j t μ t ) (2-8)

其中 μ 为总样本均值, μ t 为第t类总体 G t 的样本均值, n t 为第t类总体 G t 的样本数, x j t 为第t类总体 G t 的第j个样本。

事实上,目标是由两个子目标组成的:

arg max v v S B v (2-9)

arg min v v S W v (2-10)

其中目标(2-9)使不同类别标签的数据点投影后样本内方差最大化,目标(2-10)使相同类别标签的数据点投影后样本内方差最小化。LDA算法是基于总体服从正态分布的假设,其目标函数只考虑总体的方差,而忽略局部样本之间隐含的信息。

3. 全局加局部的线性判别投影

3.1. 增强组间线性判别投影(EWLDP)

3.1.1. 局部相似性

局部相似性指的是近邻且同类的样本点之间的相似性 [11] ,当样本点的距离越近,相似性越强。前面提到,LDP算法只考虑样本中的全局信息而忽略了局部样本间的信息,然而在实际场景中,局部信息对判别分类更具有意义。在本章节,首先提出一种新算法增强组间线性判别投影(EWLDP),将局部相似信息融合到LDP目标函数中。

局部相似信息在局部保留投影(LPP)中有很好的定义,EWLDP沿用LPP算法中保留局部相似信息的技巧,并结合监督学习的分类标签,将局部相似矩阵整合到LDP目标函数中。

LPP的基本思想是保留样本点的局部相似信息进行投影降维,目标函数为:

1 2 arg min v i , j v x i v x j 2 S i j (3-1)

其中权重矩阵S为一个相似矩阵, S i j 表示样本 x i , x j 的相似性。S一共有两种定义方式:

S i j = { exp ( x i x j 2 / t ) , x i x j 2 < δ 0 , else (3-2)

S i j = { exp ( x i x j 2 / t ) , x i N k ( x j ) or x j N k ( x i ) 0 , else (3-3)

其中 δ 表示局部领域的半径,通常 δ 取值较小且 δ > 0 x i N k ( x j ) 表示样本点 x i 属于样本点 x j 的k近邻点, x j N k ( x i ) 同理。从以上两种定义可以看出,当样本点距离越小,相似性越强,则权重越大。近邻点投影后的在一维空间中的距离变大,会给目标函数带来更大的惩罚。LPP算法就是通过增强近邻点之间的在惩罚函数中的权重系数,从而达到保留局部相似信息的目的。

然而上述两种定义的矩阵S都没有考虑样本标签,即认为近邻点属于相同类别,非近邻点属于不同类别。在实际场景中,近邻点往往包含异类样本点。为了提高分类准确度,需要考虑样本标签,重新定义相似矩阵S:

S i j = { exp ( x i x j 2 / t ) , x i x j 2 < δ and y i = y j 0 , else (3-4)

S i j = { exp ( x i x j 2 / t ) , x i N k ( x j ) or x j N k ( x i ) and y i = y j 0 , else (3-5)

其中 y i , y j 分别代表样本 x i , x j 的类别标签。从以上两个定义可以看出,新的权重系数只考虑邻近且同类的样本点,其余为零。

下面对目标函数(3-1)进行代数运算,使目标函数的形式与子目标(2-5)的形式一致,从而更方便融合到LDP的目标函数中:

1 2 min i , j v x i v x j 2 S i j = 1 2 min i , j ( v x i v x j ) ( v x i v x j ) S i j = 1 2 min i , j v ( x i x j ) S i j ( x i x j ) v = 1 2 min { v [ i , j ( x i x j ) S i j ( x i x j ) ] v } = 1 2 min [ v ( 2 i , j x i S i j x i 2 i , j x i S i j x j ) v ] = min v ( X D X X S X ) v = min v S L W v (3-6)

其中 D = d i a g ( D 11 , , D n n ) D i i = j = 1 n S i j ( i = 1 , , n ) 。称 S L W = X ( D S ) X 为局部组内离散矩阵。

3.1.2. 算法原理

根据前面提到的三个目标函数(2-4)、(2-5)、(3-6),其中组间离散矩阵 C D 、组内离散矩阵 C S 保留了全局信息,局部组内离散矩阵 S L W 保留了局部相似信息,下面提出EWLDP的目标函数:

arg max v v C D v v [ α C S + ( 1 α ) S L W ] v (3-7)

其中参数 α ( 0 , 1 ) 权衡了组内离散矩阵 C S 和局部组内离散矩阵 S L W

结合以上两个组内信息矩阵,得到一个完全的组内离散矩阵:

C T W = α C S + ( 1 α ) S L W (3-8)

于是EWLDP的目标函数(3-7)可以记为:

arg max v v C D v v C T W v (3-9)

α = 1 时,即为LDP算法。

和LDA类似,求解式(3-9)的问题,对应求解广义特征问题:

C D v = λ C T W v (3-10)

所以最优投影方向 为 C T W 1 C D 的最大特征值对应的特征向量。

3.2. 完全线性判别投影(CGLDP)

3.2.1. 局部模式差异性

模式差异性表示了样本点的分布特性,当一个总体的样本点分布较分散,则其模式差异性越大;当该总体的样本点分布较集中,则其模式差异性越小。局部模式差异性指的是近邻样本点之间的模式差异性,当样本点距离越大,则模式差异性越大 [11] 。局部模式差异性分为局部组间模式差异性以及局部组内模式差异性,分别指近邻异类样本点之间的模式差异性和近邻同类样本点之间的模式差异性。

上一节提出了考虑局部相似信息的EWLDP算法,然而没有考虑所有的局部信息。局部信息一共分为三种:局部相似性、局部组间模式差异性以及局部组内模式差异性。为了投影后仍然保留局部模式差异性,建立目标函数:

1 2 arg max v i , j v x i v x j 2 W i j (3-11)

其中权重矩阵W表示样本点之间的模式差异性,当样本点 x i , x j 之间距离越大,则权重 W i j 越大。

首先为了保留局部组内模式差异性,定义权重矩阵W:

W i j = { exp ( t / x i x j 2 ) , x i N k ( x j ) or x j N k ( x i ) and y i = y j 0 , else (3-12)

从而最大化目标函数(3-11),使得局部组内模式差异性在新的降维特征空间中得到很好的保留。然而定义(3-12)只保留了局部组内模式差异性,而忽略了局部组间模式差异性。在实际场景中,局部组间模式差异性对选择投影方向起着决定性作用,模式差异性越大的近邻样本点更能决定投影方向。同时从另一个方面,处于决策边界的异类样本点往往存在异常点,保留局部组间模式差异性可以提升新特征空间的泛化能力。

通过最大化投影后的局部组内模式差异性和局部组间模式差异性,重新定义权重矩阵W:

W i j = { exp ( t / x i x j 2 ) ( 1 + exp ( x i x j 2 / t ) ) , x i N k ( x j ) or x j N k ( x i ) and y i = y j exp ( t / x i x j 2 ) ( 1 exp ( x i x j 2 / t ) ) , x i N k ( x j ) or x j N k ( x i ) and y i y j 0 , else (3-13)

结合权重矩阵(3-13)最大化目标函数(3-11),即若近邻样本点(包括同类和异类)距离较大,则投影后距离也应该较大,从而保留样本的局部模式差异性。

下面对目标函数(3-11)进行代数运算,使目标函数的形式与子目标(2-4)的形式一致,从而更方便融合到EWLDP的目标函数中:

1 2 max i , j v x i v x j 2 W i j = 1 2 max i , j ( v x i v x j ) ( v x i v x j ) W i j = 1 2 max i , j v ( x i x j ) W i j ( x i x j ) v = 1 2 max { v [ i , j ( x i x j ) W i j ( x i x j ) ] v } = 1 2 max [ v ( 2 i , j x i W i j x i 2 i , j x i W i j x j ) v ] = max v ( X P X X W X ) v = max v S L P v (3-14)

其中 P = d i a g ( P 11 , , P n n ) , P i i = j = 1 n W i j ( i = 1 , , n ) 。称 S L P = X ( P W ) X 为局部模式差异矩阵。

3.2.2. 算法原理

根据前面提到的四个目标函数(2-4)、(2-5)、(3-6)、(3-14),其中组间离散矩阵 C D 、组内离散矩阵 C S 保留了全局信息,局部组内离散矩阵 S L W 保留了局部相似信息,局部模式差异矩阵 S L P 保留了局部相似信息。下面提出CGLDP的目标函数:

arg max v v [ β C D + ( 1 β ) S L P ] v v [ α C S + ( 1 α ) S L W ] v (3-15)

其中参数 β ( 0 , 1 ) 权衡了组间离散矩阵 C D 和局部模式差异矩阵 S L P

结合以上两个矩阵,得到一个完全的差异矩阵:

C T D = β C D + ( 1 β ) S L P (3-16)

于是CGLDP的目标函数(3-7)可以记为:

arg max v v C T D v v C T W v (3-17)

β = 1 时,即为EWLDP算法;当 α , β = 1 时,即为LDP算法。

和LDA类似,求解式(3-17)的问题,对应求解广义特征问题:

C T D v = λ C T W v (3-18)

所以最优投影方向v为 C T W 1 C T D 的最大特征值对应的特征向量的问题,对应求解广义特征问题:

C T D v = λ C T W v (3-18)

所以最优投影方向v为 C T W 1 C T D 的最大特征值对应的特征向量。

4. 实验过程及其结果

4.1. 样本简介

鸢尾花(Iris)数据集是常用的分类实验数据集,由Fisher, 1936收集整理。Iris也称鸢尾花卉数据集,是一类多重变量分析的数据集。数据集包含150个数据集,分为3类,每类50个数据,每个数据包含4个属性。可通过花萼长度,花萼宽度,花瓣长度,花瓣宽度4个属性预测鸢尾花卉属于{Setosa,Versicolour,Virginica}三个种类中的哪一类。

4.2. 实验内容

本次实验主要目的是比较LDP、EWLDP、CGLDP三个算法在iris数据集上的降维效果,从而证明局部信息对特征选取的重要性。本文使用MATLAB工具编写算法。实验过程中,需要调试的参数包括近邻点的界定值 δ ,权重矩阵中的参数t,权衡组间离散矩阵 C D 和局部模式差异矩阵 S L P 的参数 β ,权衡组内离散矩阵 C S 和局部组内离散矩阵 S L W 的参数 α

以下表1为三个算法模型涉及的参数。根据三个算法的目标函数定义(3-1)、(3-9)、(3-17),LDP算法模型的超参数 α , β 统一取默认值为1;EWLDP算法模型的参数 β 取默认值为1,剩余三个参数 δ , t , α 待调试;CGLDP算法模型的参数 δ , t , α , β 待调试。

Table 1. Parameters of the experiment

表1. 实验调试参数

4.3. 实验结果分析

经过对以上参数调试,得到三个算法的参数最佳取值(见表2),以及各自的投影降维的散点分布图(默认降到两维)。

Table 2. The values of the parameters

表2. 参数调试结果

图1中的三个二维图,分别显示了Iris数据集通过算法LDP、EWLDP、CGLDP降维后,得到的二维数据的分布情况,其中黄色、绿色、紫色散点分别代表了原始样本集中三种类别的数据。图1(a)展示了在原始LDP算法下,Iris数据集在二维空间的分布情况,可以看出经过LDP降维,三种类别的数据在二维空间中没有明显的分离,故认为没有达到降维分类的根本目的。图1(b)、图1(c)展示了Iris数据集分别经过算法EWLDP、CGLDP降维后,三种类别的数据有明显的分离,说明算法EWLDP、CGLDP的降维效果均优于LDP。另外对比图1(b)与图1(c)中三种类别散点的分离情况,图1(c)中同一类别的数据较为集中,而不同类别的数据较为分散,故认为算法CGLDP的降维效果优于EWLDP。

从以上三个散点图可以看出,EWLDP和CGLDP的分类效果明显比原始LDP算法要好,从而说明了局部信息对投影降维的重要性,以及在LDP算法上增加局部信息的可行性、进步性。EWLDP各类的分布比较散,即组内平方和较大,不符合投影后组内点尽可能集中的目的。而CGLDP各类的分布比较集中,比EWLDP的投影效果更好,从而说明了完整的局部信息的重要性、优异性。

Figure 1. The scatter distribution diagram after dimensionality reduction of the three algorithms

图1. 三个算法降维后的散点分布图

5. 结论

本文展示了三种局部信息:局部相似性、局部组间模式差异性以及局部组内模式差异性,并将这三种局部信息添入LDP算法中,得到两个算法EWLDP、CGLDP。为了将这三种局部信息结合进LDP算法中,本文首先将局部相似信息结合LDP算法,得到EWLDP算法。然后将局部组间模式差异性以及局部组内模式差异性结合EWLDP算法,得到CGLDP算法。最后本文利用iris数据集进行实验,得出投影后散点分布图,从而给出判别分类的依据,结果证实了CGLDP、EWLDP算法的进步性。

本文后续的研究工作主要为拓展算法CGLDP、EWLDP在其他领域数据集上的应用验证,并与其他相关算法进行比较(如LDA、EWLDA、CGLDA等)。

文章引用

麦炜琪. 全局加局部的线性判别投影
Enhanced Linear Discriminant Projections with Global plus Local Information[J]. 数据挖掘, 2019, 09(02): 42-51. https://doi.org/10.12677/HJDM.2019.92006

参考文献

  1. 1. Cai, H.-P., Mikolajczyk, K. and Matas, J. (2011) Learning Linear Discriminant Projections for Dimensionality Reduction of Image Descriptors. IEEE Transactions on Pattern Analysis and Machine Intelligence, 33, 338-352. https://doi.org/10.1109/TPAMI.2010.89

  2. 2. Zhang, D., He, J.Z. and Zhao, Y. (2014) Global plus Local: A Complete Framework for Feature Extraction and Recognition. Pattern Recognition, 47, 1433-1442. https://doi.org/10.1016/j.patcog.2013.10.005

  3. 3. He, X. and Niyogi, P. (2003) Locality Preserving Projections. Ad-vances in Neural Information Processing Systems.

  4. 4. Gao, Q., Liu, J., Zhang, H., et al. (2012) Enhanced Fisher Discri-minant Criterion for Image Recognition. Pattern Recognition, 45. https://doi.org/10.1016/j.patcog.2012.03.024

  5. 5. Huang, P. and Chen, C.K. (2010) Feature Extraction by Locality-Based Linear Discriminant Analysis. CCCM.

  6. 6. Gao, Q.X., Liu, J.J., Zhang, H.J., Hou, J. and Yang, X.J. (2012) Enhanced Fisher Discriminant Criterion for Image. Pattern Recognition, 45, 3717-3724. https://doi.org/10.1016/j.patcog.2012.03.024

  7. 7. Zhang, D. and Zhao, Y. A New Supervised Dimensionality Reduction Algorithm Using Linear Discriminant Analysis and Locality Preserving Projection.

  8. 8. Hua, G., Brown, M. and Winder, S. Discriminant Embedding for Local Image Descriptors.

  9. 9. Mikolajczyk, K. and Matas, J. Improving Descriptors for Fast Tree Matching by Optimal Linear Projection.

  10. 10. 庞成. 人脸识别中子空间降维方法研究[D]: [硕士学位论文]. 扬州: 扬州大学, 2013.

  11. 11. 徐伟. 基于多信息融合的流形学习方法研究[D]: [硕士学位论文]. 扬州: 扬州大学, 2013.

期刊菜单