一种核化的逆近邻判别分析方法

1.本发明属于逆近邻判别分析领域，尤其涉及一种核化的逆近邻判别分析方法。


背景技术：

2.线性判别分析法(lda)是一种有监督的经典的线性学习方法，它源于fisher判别式，它不仅可以用于特征降维，还可以有效解决有监督的分类问题。它的原理是在给定的训练样本中，试图找到能使类间散度矩阵最大化和类内散度矩阵最小化的投影矩阵，并利用该投影矩阵对测试样本进行降维，进而可以使用最近邻或其它分类器进行分类。作为一种有监督的特征提取方法，lda已经在模式识别分类任务中，证明了它的可行性和有效性，并且被广泛应用于数据降维、信号分析、图像分类等领域。特别在手写数字识别、人脸识别、目标分类等视觉分类任务上有较显著的研究成果。
3.在lda算法中，需要假设样本服从独立同分布(i.i.d.)，才能获得较好的分类结果。但当同一个类的样本来自几个不同的集群，有不同的方差时，使得上述假设不成立，则lda难以得到很好的分类效果。混合判别分析(mda)是解决该问题的一种重要方法，其使用高斯模型对不同的集群进行建模。另外一种解决方案是流形或者图论的方法对局部结构进行建模，还有一类方法是使用k近邻等非参数方法对局部邻域进行建模，其中基于逆近邻的线性判别分析(nlda)是最近提出的其中一种解决多模态问题的有效方法。nlda通过逆近邻算法构建散度矩阵，而逆近邻算法是一种有效的无监督离群点检测方法，它可以排除训练集中的“孤立点”，具有更优的分类能力。nlda是一种直接将散度矩阵定义在邻域上的方法，是一种新的局部判别器。它的最小子类可以看作是一个邻域，这样就解决了原来lda算法必须要样本服从独立和同分布(i.i.d.)的问题。由于nlda是lda的一种延伸，因此nlda也是一种线性方法，当遇到非线性数据时得到的结果并不理想，以人脸识别为例，通常人脸的表情、姿态或光照的变化常会造成非线性的结果。解决非线性问题的一种常用的解决方案是将原始输入数据的点映射到一个更高维的欧氏空间，然后在该高维空间上学习分类器，进行判别学习。因此本发明为了提高nlda在处理非线性数据上的性能，提出了一种核化的逆近邻判别分析方法(krnda)，该方法将原始数据首先利用高斯核映射函数映射至高维希尔伯特空间，然后在高维空间中进行逆近邻的判别分析。然而由于高斯核映射的空间是非显式的，即其隐射函数不能进行显式的表达。


技术实现要素：

4.本发明的目的在于提供一种核化的逆近邻判别分析方法，将原始数据首先利用高斯核映射函数映射至高维希尔伯特空间，然后在高维空间中进行逆近邻的判别分析，同时利用核技巧对逆近邻线性判别分析进行了核化的推导。并且在求样本逆近邻的过程中采用高维空间上的距离，得到高维逆近邻，进一步有效排除离群点。
5.为了达到上述目的，在本发明提供如下的技术方案：
6.一种核化的逆近邻判别分析方法，其包括如下步骤：
7.s1、获得训练图像样本，所述训练图像样本为x＝[x1,x2,
…
,xn]；
[0008]
s2、利用高斯核函数将输入数据映射到高维空间，所述输入数据为训练图像样本；
[0009]
s3、利用核技巧以及逆近邻算法得到训练图像样本在高维空间中的类内散度矩阵和类间散度矩阵表达；
[0010]
s4、通过特征分解学习最大化类间散度矩阵和最小化类内散度矩阵的投影矩阵；
[0011]
s5、利用投影矩阵训练和所述测试图像样本进行特征提取；
[0012]
s6、使用最近邻算法对测试样本进行分类。
[0013]
进一步地，所述利用高斯核函数将输入数据映射到高维空间具体为：定义一种映射使每个样本从原始特征空间rd映射到高维特征空间f，将其表示为：rd→
f,其目的是使特征空间中的线性子空间可以通过映射向量来张成，其中表示将样本x从原始特征空间映射到高维特征空间，是样本在高维特征空间中的表示。将训练样本中的第i个图像向量xi和第j个图像向量xj的内积表示为以下的核函数形式：
[0014][0015]
其中，《
·
》为高维特征空间中两个向量的内积；选择典型而有效的高斯核函数kg，并且进行内积计算，将其表示如下：
[0016][0017]
其中，σ是高斯核函数中的一个可调参数。
[0018]
进一步地，所述利用核技巧以及逆近邻算法得到训练图像样本在高维空间中的类内散度矩阵和类间散度矩阵表达，具体为：
[0019]
s301、在高维核空间中去确定样本的逆近邻，高维空间中样本点在n个映射后的图像样本集合中的k阶逆近邻表达为:
[0020][0021]
其中，表示高维样本点的k阶近邻；
[0022]
得到高维空间中的一个最优投影矩阵ω＝[ω1,ω2,
…
,ωi,
…
,ωh],h表示最后特征保留的维度,使得类间散度最大化同时类内散度最小化,即最大化下面式子:
[0023][0024]
在高维空间f中的h个投影向量ω＝[ω1,ω2,
…
,ωi,
…
,ωh],则投影向量在原始高维数据张成的f空间中线性表示：
[0025][0026]
其中，α
ij
和n分别指的是线性组合的系数和训练样本的总数。
[0027]
s302、得到了最优投影矩ω，通过对映射后的高维样本进行投影，即可获得降维后的判别特征则
[0028][0029]
使用上面的线性表达式以及核技巧,上式中的表达成：
[0030][0031]
其中αi＝[α
i1
,α
i2
,
…
,α
in
]
t
,由于则km表示所有训练的高维样本和第m个高维样本之间的内积向量；
[0032]
s303、使用高斯核函数计算核函数k(xi,xm)，计算出低维投影特征gm，对降维后的判别特征进行优化，其中低维投影特征gm表达为:
[0033][0034]
其中α＝[α1,α2,
…
,αh]
t
。
[0035]
进一步地，所述通过特征分解学习最大化类间散度矩阵和最小化类内散度矩阵的投影矩阵的具体步骤为：将所述学习能够最大化类间散度矩阵和最小化类内散度矩阵的问题转化为经典的特征分解问题：
[0036]
bα＝λwα
[0037]
其中b和w分别为映射后类间散度矩阵和类内散度矩阵。
[0038]
进一步地，所述经典的特征分解问题为：求解过程中,通过对(w)-1
b进行特征分解，取最大的h个特征值所对应的特征向量α＝[α1,α2,
…
,αh]并且得到最终的解。
[0039]
进一步地，所述利用投影矩阵训练图像样本进行特征提取具体为：
[0040]
s501、对所有的训练图像样本x＝[x1,x2,
…
,xn]提取特征；
[0041]
s502、按照高维映射得到训练图像样本集合
[0042]
s503、对n个高维训练样本利用公式求取同类样本的k阶逆近邻，并且当逆近邻个数不小于t个的时候，求取逆近邻样本的均值，即对该高维均值向量进行投影得到判别特征根据s3判别特征低维投影特征进gm和线性组合系数α的推导关系，可以得到
[0043]
最后得到所有训练样本判别特征g＝α
t
k,其中
[0044]
g＝[g1,g2,
…
,gm](m≤n),k＝[k1,k2,
…
,km]，k为核矩阵。
[0045]
s504、对于一个测试样本x
t
，按照高维映射得到对该高维样本进行投影得到判别特征得到g
t
＝α
tkt
。
[0046]
进一步地，所述使用最近邻算法对所述测试图像样本进行分类具体为：根据s5中的g
t
与g＝[g1,g2,
…
,gm]的m个原始样本在高维空间的逆近邻均值用欧氏距离求最近邻距离,所述g
t
的类别,即为g＝[g1,g2,
…
,gm]中最近邻的那个判别特征的类标号。
[0047]
本发明的有益技术效果至少在于以下几点：
[0048]
本发明所提出的核化的逆近邻判别分析方法(krnda)有效解决了逆近邻线性判别分析方法(nlda)在处理非线性数据(例如手写数字、人脸和多视角目标识别问题)时出现的识别性能下降问题。在usps和mnist手写数据集上实现识别奇偶数的二分类问题中核化的逆近邻判别分析方法优于lda、lfda、cclda、l
2,1-rlda和nlda等基于lda的改进算法。在orl人脸数据集和coil-20目标识别数据集上分别达到97.50％和99.30％的最高识别率。
附图说明
[0049]
利用附图对本发明作进一步说明，但附图中的实施例不构成对本发明的任何限制，对于本领域的普通技术人员，在不付出创造性劳动的前提下，还可以根据以下附图获得其它的附图。
[0050]
图1为本发明实施例的核化的逆近邻判别分析方法流程图。
[0051]
图2为本发明实施例二usps和mnist中的数字样本示意图。
[0052]
图3为本发明实施例二coil-20数据集部分图片示意图。
[0053]
图4为本发明实施例二orl人脸数据集部分图片示意图。
具体实施方式
[0054]
下面详细描述本发明的实施例，所述实施例的示例在附图中示出，其中自始至终相同或类似的标号表示相同或类似的元件或具有相同或类似功能的元件。下面通过参考附图描述的实施例是示例性的，仅用于解释本发明，而不能理解为对本发明的限制。
[0055]
具体实施方式一：
[0056]
如图1所示，本发明实施例提供的调平系统的平均值控制方法，是一种核化的逆近邻判别分析方法，其包括如下步骤：
[0057]
s1：获得训练图像样本x＝[x1,x2,
…
,xn]。
[0058]
s2：利用高斯核函数将输入数据映射到高维空间，要求每个样本从原始特征空间映射到高维特征空间映射到高维特征空间其目的是使特征空间中的线性子空间可以通过映射向量来张成。将两个图像向量xi,xj的内积表示为以下的核函数形式：
[0059][0060]
其中《
·
》为高维特征空间中两个向量的内积。许多映射函数并没有显式的表达，但其内积可以通过公式的表达。选择合适的核函数隐式计算高维特征空间中两个向量的内积是所有核方法的重要步骤。本发明选择典型而有效的高斯核函数进行内积计算，将其表示如下：
[0061][0062]
σ是高斯核函数中的一个可调参数。由此高维空间中的两个样本内积可以进行显式的表达。
[0063]
s3：利用核技巧以及逆近邻算法得到训练样本在高维空间中的类内散度矩阵和类间散度矩阵表达。首先在高维核空间中去确定样本的逆近邻。那么高维空间中样本点在n个映射后的图像样本集合中的k阶逆近邻可以表达成:
[0064][0065]
其中表示高维样本点的k阶近邻。
[0066]
算法的目的是求取高维空间中的一个最优投影矩阵ω＝[ω1,ω2,
…
,ωh],h是最大的h个特征值所对应的特征向量,使得类间散度矩阵最大化，同时类内散度矩阵最小化,即优化下面式子:
[0067][0068]
在高维空间f中的h个投影向量ω＝[ω1,ω2,
…
,ωh],可以在原始高维数据张成的f空间中线性表示：
[0069][0070]
其中α
ij
和n分别指的是线性组合的系数和训练样本的总数。假设我们得到了最优投影矩阵ω，通过对映射后的高维样本进行投影，即可获得降维后的判别特征那么有
[0071]
[0072]
使用上面的线性表达式以及核技巧,上式中的可以表达成：
[0073][0074]
其中αi＝[α
i1
,α
i2
,
…
,α
in
]
t
,由于则用km表示所有训练的高维样本和第m个高维样本之间的内积向量，核函数k(xi,xm)的计算方法使用高斯核函数进行。
[0075]
计算出低维投影特征gm，对降维后的判别特征进行优化，其中低维投影特征gm可以表达为:
[0076][0077]jkrnda
(ω)
[0078]
其中α＝[α1,α2,
…
,αh]
t
,利用上述关系,可以将优化公式中的改写为:
[0079][0080]
其中
[0081][0082]
是逆近邻得到的局部样本个数,
[0083]
中t是逆近邻样本个数阈值,即当中的逆邻个数要达到t个才构建局部邻域,并使用该局部邻域计算高维样本的均值是指标签和样本xj一样的图像样本集合.
[0084]
将优化公式j
krnda
(ω)中的改写为:
[0085][0086]
其中
[0087][0088]
综上所述，
[0089][0090]
s4：通过特征分解学习能够最大化类间散度矩阵和最小化类内散度矩阵的投影矩阵，最大化上述公式的优化问题可以转化成经典的特征分解问题，即
[0091]
bα＝λwα
[0092]
求解过程中,通过对(w)-1
b进行特征分解，取最大的h个特征值所对应的特征向量α＝[α1,α2,
…
,αh],得到最终的解。
[0093]
s5：利用投影矩阵对样本进行特征提取，首先对所有的训练样本x＝[x1,x2,
…
,xn]提取特征,按照高维映射得到对n个高维训练样本利用公式求取同类样本的k阶逆近邻,并且当逆近邻个数不小于t个的时候,求取逆近邻样本的均值,即对该高维均值向量进行投影得到判别特征根据s3判别特征低维投影特征gm和线性组合系数α的推导关系,可以得到最后得到所有训练样本判别特征g＝α
t
k,其中g＝[g1,g2,
…
,gm](m≤n),k＝[k1,k2,
…
,km]，k为核矩阵；对于一个测试样本x
t
，按照高维映射得到对该高维样本进行投影得到判别特征得到g
t
＝α
tkt
。
[0094]
s6：使用最近邻算法对所述测试样本进行分类具体为：取步骤s5中的g
t
与g＝[g1,g2,
…
,gm]的m个原始样本在高维空间中的逆近邻均值用欧氏距离求最近邻距离,那么g
t
的类别,即为g＝[g1,g2,
…
,gm]中最近邻的那个判别特征的类标号。
[0095]
具体实施方式二：
[0096]
为了说明本发明算法的有效性，本实施例在手写数据集的识别、人脸识别和目标识别中实施本发明提出的算法，所用的数据集包括在mnist和usps手写数据集、orl人脸数据集和coil-20目标识别数据集。本发明在上述数据集上与没有核化的nlda算法进行比较,以突出本发明的有效性。除此之外，还实施了相关线性判别算法：lda，lfda，l
2,1-rlda和cclda进行比较。其中lfda是一种利用局部信息构建的线性判别器，l
2,1-rlda是一种利用
l
1-范数正则化的线性判别器。在cclda中，利用线性判别分析中的簇内和簇间散度矩阵对类内和类间散点矩阵进行归一化处理，解决lda中由小样本量引起的过拟合问题。
[0097]
图2中展示了一些关于mnist和usps数据集中手写字体图像，左边是奇数，右边是偶数。
[0098]
在手写数据集上，本实施例将分类问题划分为二分类问题，即判别数字是奇数还是偶数。奇数类是1，3，5，7和9。偶数类分别是2、4、6、8和10。显然，根据字体的形状的相似性，奇数和偶数都实际包含了5个子类，基于逆近邻的线性判别分析(nlda)方法对这种多子类的图像分类任务有较好的识别性能。随机选择不同数量的样本进行实验，如mnist1000，mnist6000，mnist10000和mnist15000，这表示我们从mnist数据集的60000个训练样本中随机选择1000、6000、10000和15000个样本进行训练,在10000个测试样本中,大概以训练数据和测试数据6:1的比率随机挑选测试集进行测试。usps数据集总共有9298张手写图片,本实施中训练集包含7291张图片,测试集包含2007张图片。识别结果如表1所示，在表格中最好的结果用加粗表示。不难发现本发明所提出的核化的逆近邻判别分析方法(krnda)算法具有更好的识别结果，体现了其对非线性图像的处理能力。
[0099]
表1 usps和mnist数字识别问题的准确率比较(单位：％)
[0100]
数据集ldalfdaccldal
2,1-rldanldakrndausps89.8394.4789.9396.7196.6697.65mnist100087.3578.9176.5087.9587.9592.17mnist600081.9086.6081.0096.4096.3096.60mnist1000082.2986.3182.1197.0595.7397.60mnist1500082.1687.9682.6897.0896.3698.04
[0101]
根据表1，我们可以知道krnda在usps和mnist1000，mnist6000、mnist10000和mnist15000上的识别率，分别达到97.65％、92.17％、96.60％、97.60％和98.04％。在所有在usps和mnist1000，mnist6000、mnist10000和mnist15000上，krnda都明显优于lda、lfda、cclda、l
2,1-rlda和nlda。随着mnist训练数据的增加，我们的识别率也越来越高，同样其性能也优于其他线性分类器。
[0102]
接下来本发明使用coil-20(哥伦比亚目标图像库)数据集和orl数据集来评估本发明的方法。coil-20由20个不同类别的物体组成，每个物体都有72张不同视点的图像，如汽车、猫、杯子、橡皮擦等。这些图像被手动调整大小并归一化到20
×
20像素。每类随机选择50％的图像进行训练，其余的图像进行测试。如图3所示，展示了该数据集的部分图片示例。
[0103]
orl人脸数据集包含40个人的400张图像。一些图像是在不同的时间拍摄的，有不同的变化，包括表情(睁开或闭上眼睛，微笑或不微笑)和面部细节(戴眼镜或没有眼镜)。从orl数据集中提取的人脸图像被调整大小并归一化到20
×
20像素。同样每个类随机选择50％的图像进行训练，其余的图像进行测试。如图4所示，展示了该数据集的部分图片示例。
[0104]
如表2所示，所提出的krnda优于原始nlda算法，在orl数据集和coil-20数据集上的识别率分别达到97.50％和99.30％。同时，相比其它线性判别算法，本发明也有明显的性能优势。以上实施例说明了本发明的有效性。
[0105]
表2.orl和coil-20数据集上的识别率比较(单位：％)
[0106]
数据集ldafldaccldal
2,1-rldanldakrnda
orl94.0092.0090.0095.0095.0097.50coil-2093.8896.6691.5097.9295.1499.30
[0107]
本发明上述实施例，首次将逆近邻线性判别分析(nlda)方法推广到高维空间，以解决非线性数据的分类问题，提出使用高斯核函数进行高维映射，对nlda算法进行核化，利用核技巧进行非显式映射的推导，在高斯函数映射后的空间中建立高维逆近邻进而求取散度矩阵，其中利用核技巧实现高维空间中的距离表达。
[0108]
尽管已经示出和描述了本发明的实施例，本领域技术人员可以理解：在不脱离本发明的原理和宗旨的情况下可以对这些实施例进行多种变化、修改、替换和变形，本发明的范围由权利要求及其等同物限定。

技术特征：
1.一种核化的逆近邻判别分析方法，其特征在于，包括如下步骤：s1、获得训练图像样本，所述训练图像样本为x＝[x1,x2,...,x
n
]；s2、利用高斯核函数将输入数据映射到高维空间，所述输入数据为训练图像样本；s3、利用核技巧以及逆近邻算法得到训练图像样本在高维空间中的类内散度矩阵和类间散度矩阵表达；s4、通过特征分解学习最大化类间散度矩阵和最小化类内散矩阵的投影矩阵；s5、利用投影矩阵训练和所述测试图像样本进行特征提取；s6、使用最近邻算法对所述测试图像样本进行分类。2.根据权利要求1所述的核化的逆近邻判别分析方法，其特征在于，所述利用高斯核函数将输入数据映射到高维空间具体为：定义一种映射使每个样本从原始特征空间r
d
映射到高维特征空间f，将其表示为：到高维特征空间f，将其表示为：其目的是使特征空间中的线性子空间可以通过映射向量来张成，其中表示将样本x从原始特征空间映射到高维特征空间中，是样本x在高维特征空间中的表示；将训练样本中的第i个图像向量x
i
和第j个图像向量x
j
的内积表示为以下的核函数形式：其中，<
·
>为高维特征空间中两个向量的内积；选择典型而有效的高斯核函数k
g
，并且进行内积计算，将其表示如下：其中，σ是高斯核函数中的一个可调参数。3.根据权利要求1所述的核化的逆近邻判别分析方法，其特征在于，所述利用核技巧以及逆近邻算法得到训练图像样本在高维空间中的类内散度矩阵和类间散度矩阵表达，具体为：s301、在高维核空间中去确定样本的逆近邻，高维空间中样本点在n个映射后的图像样本集合中的k阶逆近邻表达为:其中，表示高维样本点的k阶近邻；得到高维空间中的一个最优投影矩阵ω＝[ω1,ω2,...,ω
i
,...,ω
h
],h表示最后特征保留的维度,使得类间散度矩阵最大化和类内散度矩阵最小化,即最大化j
krnda
(ω)，用下面式子表示:在高维空间f中的h个投影向量ω＝[ω1,ω2,...,ω
i
,...,ω
h
],则投影向量在原始高维数据张成的f空间中线性表示：
其中，α
ij
和n分别指的是线性组合系数和训练样本总数；s302、得到了最优投影矩ω，通过对映射后的高维样本进行投影，即可获得降维后的判别特征则使用上面的线性表达式以及核技巧,上式中的表达成：其中α
i
＝[α
i1
,α
i2
,...,α
in
]
t
,由于则k
m
表示所有训练的高维样本和第m个高维样本之间的内积向量；s303、使用高斯核函数计算核函数k(x
i
,x
m
)，计算出低维投影特征g
m
，对降维后的判别特征进行优化，其中低维投影特征g
m
表达为:其中α＝[α1,α2,...,α
h
]
t
。4.根据权利要求3所述的核化的逆近邻判别分析方法，其特征在于，所述通过特征分解学习最大化类间散度矩阵和最小化类内散度矩阵的投影矩阵的具体步骤为：将所述学习能够最大化类间散度矩阵和最小化类内散矩阵的投影矩阵的问题转化为经典的特征分解问题：bα＝λwα其中b和w分别为映射后类间散度矩阵和类内散度矩阵。5.根据权利要求4所述的核化的逆近邻判别分析方法，其特征在于，所述经典的特征分
解问题为：求解过程中,通过对(w)-1
b进行特征分解，取最大的h个特征值所对应的特征向量α＝[α1,α2,...,α
h
]并且得到最终的解。6.根据权利要求5所述的核化的逆近邻判别分析方法，其特征在于，所述利用投影矩阵训练图像样本进行特征提取具体为：s501、对所有的训练图像样本x＝[x1,x2,...,x
n
]提取特征；s502、按照高维映射得到训练图像样本集合s503、对n个高维训练样本利用公式求取同类样本的k阶逆近邻,并且当逆近邻个数不小于t个的时候,求取逆近邻样本的均值,即对该高维均值向量进行投影得到判别特征根据s3判别特征低维投影特征g
m
和线性组合系数α的推导关系,可以得到最后得到所有训练样本判别特征g＝α
t
k,其中g＝[g1,g2,...,g
m
](m≤n),k＝[k1,k2,...,k
m
]，k为核矩阵；504、对于一个测试样本x
t
，按照高维映射得到对该高维样本进行投影得到判别特征得到g
t
＝α
t
k
t
。7.根据权利要求6所述的核化的逆近邻判别分析方法，其特征在于，所述使用最近邻算法对所述测试图像样本进行分类具体为：根据s5中的g
t
与g＝[g1,g2,...,g
m
]的m个原始样本在高维空间的逆近邻均值用欧氏距离求最近邻距离,所述g
t
的类别,即为g＝[g1,g2,...,g
m
]中最近邻的那个判别特征的类标号。

技术总结
本发明公开了一种核化的逆近邻判别分析方法，包括如下步骤：获得训练图像样本；利用高斯核函数将输入数据映射到高维空间；利用核技巧以及逆近邻算法得到训练图像样本在高维空间中的类内散度矩阵和类间散度矩阵的表达；通过特征分解学习最大化类间散度矩阵和最小化类内散度矩阵的投影矩阵；利用投影矩阵对训练和测试图像样本进行特征提取；使用最近邻算法对测试样本进行分类。本发明首次将逆近邻线性判别分析方法推广到高维空间，以解决非线性数据的分类问题，提出使用高斯核函数进行高维映射，对该算法进行核化，利用核技巧进行非显式映射的推导，在高斯函数映射后的空间中建立高维逆近邻进而求取散度矩阵，其中利用核技巧实现高维空间中的距离表达。现高维空间中的距离表达。现高维空间中的距离表达。


技术研发人员：谭恒良 李旺旺 谢铭 冯健维 杜娇 杨朔 颜国风
受保护的技术使用者：广州大学
技术研发日：2023.03.10
技术公布日：2023/7/19