引用本文

 

梁志贞, 张磊. 面向Kullback-Leibler散度不确定集的正则化线性判别分析. 自动化学报, 2022, 48(4): 1033−1047 doi: 10.16383/j.aas.c210434

Liang Zhi-Zhen, Zhang Lei. Regularized linear discriminant analysis based on uncertainty sets from Kullback-Leibler divergence. Acta Automatica Sinica, 2022, 48(4): 1033−1047 doi: 10.16383/j.aas.c210434    

http://www.aas.net.cn/cn/article/doi/10.16383/j.aas.c210434?viewType=HTML

文章简介

关键词

判别分析, KL散度, 不确定集, 正则化, 数据分类

摘   要

线性判别分析是一种统计学习方法. 针对线性判别分析的小样本奇异性问题和对污染样本敏感性问题, 目前许多线性判别分析的改进算法已被提出. 本文提出了基于Kullback-Leibler (KL)散度不确定集的判别分析方法. 提出的方法不仅利用了Ls范数定义类间距离和Lr范数定义类内距离, 而且对类内样本和各类中心的信息进行基于KL散度不确定集的概率建模. 首先通过优先考虑不利区分的样本提出了一种正则化对抗判别分析模型并利用广义Dinkelbach算法求解此模型. 这种算法的一个优点是在适当的条件下优化子问题不需要取得精确解. 投影(次)梯度法被用来求解优化子问题. 此外, 也提出了正则化乐观判别分析并采用交替优化技术求解广义Dinkelbach算法的优化子问题. 许多数据集上的实验表明了本文的模型优于现有的一些模型, 特别是在污染的数据集上, 正则化乐观判别分析由于优先考虑了类中心附近的样本点, 从而表现出良好的性能.

引   言

如今利用现代设备采集高维数据变得方便和容易, 但是获得的高维数据可能包含不相关和冗余的信息. 这不仅增加了学习模型的计算量和存储量, 而且可能导致学习模型的性能下降. 为了解决这些问题, 线性降维通常用于从数据中提取重要和有用的信息. 线性降维的目的是通过优化一些准则函数对原始特征空间进行适当的线性变换. 主成分分析(Principal component analysis, PCA)和线性判别分析(Linear discriminant analysis, LDA)是两种流行的线性降维方法. 由于PCA和LDA的简单性和有效性, 它们已经被广泛应用于许多领域, 如人脸识别、手写体字符识别和缺陷诊断等.

当样本的类别信息可用时, 通常情况下LDA在提取数据的鉴别特征方面比PCA更有效. 线性判别分析的目标是在变换空间中通过最大化类间距离和最小化类内距离来寻找投影矩阵. 从概率的观点来看, 假设每类样本服从高斯分布且具有不同的类中心以及相同的协方差, 则从Bayes最优准则可推导出LDA.

为了改善线性判别分析的特征提取性能, 各种LDA的改进算法已经被提出. 使用最优向量替换各类中心能提高LDA的类信息鉴别能力. 分数阶的LDA通过在一系列分数阶中引入加权函数来改善LDA, 但这增加了获得投影向量的代价. 与Bayes错误率相关的近似成对精度准则在原空间计算各类的权重, 从而改善LDA的性能. 几何平均, 调和平均以及加权调和平均被用来定义判别分析的准则函数. 最不利情况下的线性判别分析考虑了最近的两个类中心和具有最大方差的类来寻找投影方向. 基于最大−最小距离的目标函数探索了最近的数据对的性质来取得投影方向. Wasserstein判别分析利用正则化Wasserstein距离获取类之间的全局和局部信息并优化目标函数取得最佳投影方向.

线性判别分析存在小样本的奇异性以及非线性数据特征提取等问题. 为了克服LDA的小样本奇异性问题, 典型的方法包括PCA+LDA, 正则化LDA, 伪逆LDA 以及张量判别分析等. 为了有效地处理非线性数据, 各种线性判别分析已被拓宽到基于核函数的判别分析. 当训练集随着新数据的加入而变化时或处理的数据量大时, 各种增量学习或在线学习方式被用来获得鉴别分析的投影方向. 文献[24]提出了两种形式的增量LDA : 序列增量LDA和块增量LDA, 它们能有效地获取大数据流的特征空间.

数据在采集或传输过程中可能受到污染, 这使得处理的数据包含噪声或离群点. 但经典线性判别分析对噪声数据具有敏感性, 即获得的投影方向偏离真正的投影方向. 为了降低LDA对噪声数据的敏感性, 许多工作致力于用鲁棒的目标函数替换LDA的原有目标函数. 已有的诸多研究发现, 基于L_1范数的目标函数比基于L_2范数的目标函数在抑制异常点或噪声方面更有效. 因此基于L_1范数的判别分析方法近年来备受关注. L_1范数的LDA的类内距离和类间距离的定义依赖于L_1范数, 这在某种程度上能抑制噪声. L_1范数的核LDA不仅能抑制噪声, 而且能捕捉数据的非线性鉴别特征. L_1范数的两维LDA拓宽了L_1范数的LDA, 这种方法可直接处理图像数据, 而不需要把图像转化为向量形式. 通常L_1范数的判别分析通过贪婪算法获取多个投影方向, 而非贪婪迭代算法被用来直接获取L_1范数的LDA的多个投影向量. 广义弹性网通过L_p范数定义的目标函数来改善判别分析抑制噪声的能力, 而通过优化Bhattacharyya的L_1范数误差界可设计出新的鉴别分析模型. 最近提出的基于L_21范数的LDA方法通过同时优化类中心和投影方向从而在噪声数据方面表现出良好的性能.

在大多数判别分析中, 通常假定类内各个样本以相等的概率(均匀分布)取得的, 但是位于类中心附近的样本一般远远多于位于类边界附近的样本. 为了增加类内样本采样的多样性, 可令类内样本的采样概率在均匀分布的概率附近变化, 这种变化有利于区分类中心附近的样本或类边界附近的样本. 不确定优化中的不确定集能描述概率分布的变化范围. 因此本文借助KL散度定义的不确定集对类内样本信息进行概率建模. 此外, 为了更好描述各类中心的信息, 本文也利用KL散度定义的不确定集对其进行概率建模. 基于此, 本文提出了基于KL散度不确定集的线性判别分析方法, 从而进一步改善已有线性判别分析方法. 与以往的方法不同, 本文不仅考虑了一般范数的目标函数, 而且利用不确定集对训练样本信息进行了刻画. 本文采用的不确定集为围绕均匀分布的KL散度球且约束中的不确定集被转化为目标函数的正则化项. 本文的主要贡献表现为:

1) 提出了正则化对抗LDA和正则化乐观LDA. 正则化对抗LDA优先考虑了难以区分的样本, 而正则化乐观LDA优化考虑了易于区分的样本.

2) 采用了广义Dinkelbach算法求解正则化对抗LDA或正则化乐观LDA. 对正则化对抗LDA运用投影梯度法求解优化子问题, 而对正则化乐观LDA运用交替优化求解优化子问题.

3) 在数据集上表明了当数据没有被污染时, 两种判别分析模型取得可竞争的性能, 但在污染数据的情况下, 正则化乐观LDA取得更好的性能. 这也从另一方面说明了本文提供两种模型的目的, 即如果在某些验证数据集上正则化乐观LDA的最好性能明显优于正则化对抗LDA的最好性能, 那说明训练集包含离群点. 因此通过检查正则化对抗LDA和正则化乐观LDA的性能可判断训练集是否包含离群点.

图 1  L2RALDA, L1RALDA, L2ROLDA和L1ROLDA的收敛性分析

图 2  L2RALDA, L1RALDA, L2ROLDA和L1ROLDA的错误率与参数的关系

图 3  数据集上不同方法随维数变化的错误率

作者简介

梁志贞

中国矿业大学副教授. 2005年获得上海交通大学模式识别与智能系统专业博士学位. 主要研究方向为模式识别, 生物特征识别. 本文通信作者.

E-mail: liang@cumt.edu.cn

张   磊

中国矿业大学副教授. 主要研究方向为最优化方法和数据挖掘.

E-mail: zhanglei@cumt.edu.cn

相关文章

[1]   高云龙, 罗斯哲, 潘金艳, 陈柏华, 张逸松. 鲁棒自适应概率加权主成分分析.自动化学报, 2021, 47(4): 825-838 doi: 10.16383/j.aas.c180743

http://www.aas.net.cn/cn/article/doi/10.16383/j.aas.c180743?viewType=HTML

[2]   王前进, 杨春雨, 马小平, 张春富, 彭思敏. 基于随机配置网络的井下供给风量建模. 自动化学报, 2021, 47(8): 1963-1975. doi: 10.16383/j.aas.c190602

http://www.aas.net.cn/cn/article/doi/10.16383/j.aas.c190602?viewType=HTML

[3]   贾鹤鸣, 李瑶, 孙康健. 基于遗传乌燕鸥算法的同步优化特征选择. 自动化学报. doi: 10.16383/j.aas.c200322

http://www.aas.net.cn/cn/article/doi/10.16383/j.aas.c200322?viewType=HTML

[4]   张帆, 张新红. 基于位错理论的距离正则化水平集图像分割算法. 自动化学报, 2018, 44(5): 943-952. doi: 10.16383/j.aas.2017.c160383

http://www.aas.net.cn/cn/article/doi/10.16383/j.aas.2017.c160383?viewType=HTML

[5]   李慧, 马小平, 施珺, 李存华, 仲兆满, 蔡虹. 复杂网络环境下基于信任传递的推荐模型研究. 自动化学报, 2018, 44(2): 363-376. doi: 10.16383/j.aas.2018.c160395

http://www.aas.net.cn/cn/article/doi/10.16383/j.aas.2018.c160395?viewType=HTML

[6]   许夙晖, 慕晓冬, 柴栋, 罗畅. 基于极限学习机参数迁移的域适应算法. 自动化学报, 2018, 44(2): 311-317. doi: 10.16383/j.aas.2018.c160818

http://www.aas.net.cn/cn/article/doi/10.16383/j.aas.2018.c160818?viewType=HTML

[7]   陈斌, 张连海, 牛铜, 屈丹, 李弼程. 基于MCE准则的语音识别特征线性判别分析. 自动化学报, 2014, 40(6): 1208-1215. doi: 10.3724/SP.J.1004.2014.01208

http://www.aas.net.cn/cn/article/doi/10.3724/SP.J.1004.2014.01208?viewType=HTML

[8]   李娟, 王宇平. 考虑局部均值和类全局信息的快速近邻原型选择算法. 自动化学报, 2014, 40(6): 1116-1125. doi: 10.3724/SP.J.1004.2014.01116

http://www.aas.net.cn/cn/article/doi/10.3724/SP.J.1004.2014.01116?viewType=HTML

[9]  李伟, 焦松, 陆凌云, 杨明. 基于特征差异的仿真模型验证及选择方法. 自动化学报, 2014, 40(10): 2134-2144. doi: 10.3724/SP.J.1004.2014.02134

http://www.aas.net.cn/cn/article/doi/10.3724/SP.J.1004.2014.02134?viewType=HTML

[10]   韩敏, 任伟杰, 许美玲. 一种基于L1范数正则化的回声状态网络. 自动化学报, 2014, 40(11): 2428-2435. doi: 10.3724/SP.J.1004.2014.02428

http://www.aas.net.cn/cn/article/doi/10.3724/SP.J.1004.2014.02428?viewType=HTML

[11]   郑建炜, 王万良, 姚晓敏, 石海燕. 张量局部Fisher判别分析的人脸识别. 自动化学报, 2012, 38(9): 1485-1495. doi: 10.3724/SP.J.1004.2012.01485

http://www.aas.net.cn/cn/article/doi/10.3724/SP.J.1004.2012.01485?viewType=HTML

[12]   刘建伟, 李双成, 罗雄麟. p范数正则化支持向量机分类算法. 自动化学报, 2012, 38(1): 76-87. doi: 10.3724/SP.J.1004.2012.00076

http://www.aas.net.cn/cn/article/doi/10.3724/SP.J.1004.2012.00076?viewType=HTML

[13]   张文林, 张连海, 牛铜, 屈丹, 李弼程. 基于正则化的本征音说话人自适应方法. 自动化学报, 2012, 38(12): 1950-1957. doi: 10.3724/SP.J.1004.2012.01950

http://www.aas.net.cn/cn/article/doi/10.3724/SP.J.1004.2012.01950?viewType=HTML

[14]   武征鹏, 张学工. 弹性多核学习. 自动化学报, 2011, 37(6): 693-699. doi: 10.3724/SP.J.1004.2011.00693

http://www.aas.net.cn/cn/article/doi/10.3724/SP.J.1004.2011.00693?viewType=HTML

[15]   刘峤, 秦志光, 陈伟, 张凤荔. 基于零范数特征选择的支持向量机模型. 自动化学报, 2011, 37(2): 252-256. doi: 10.3724/SP.J.1004.2011.00252

http://www.aas.net.cn/cn/article/doi/10.3724/SP.J.1004.2011.00252?viewType=HTML

[16]   杨武夷, 梁伟, 辛乐, 张树武. 子空间半监督Fisher判别分析. 自动化学报, 2009, 35(12): 1513-1519. doi: 10.3724/SP.J.1004.2009.01513

http://www.aas.net.cn/cn/article/doi/10.3724/SP.J.1004.2009.01513?viewType=HTML

[17]   王卫东, 杨静宇. 采用虚拟训练样本的二次判别分析方法. 自动化学报, 2008, 34(4): 400-407. doi: 10.3724/SP.J.1004.2008.00400

http://www.aas.net.cn/cn/article/doi/10.3724/SP.J.1004.2008.00400?viewType=HTML

[18]   宋枫溪, 张大鹏, 杨静宇, 高秀梅. 基于最大散度差鉴别准则的自适应分类算法. 自动化学报, 2006, 32(4): 541-549.

http://www.aas.net.cn/cn/article/id/15811?viewType=HTML

[19]   许建化, 张学工, 李衍达. 最小平方误差算法的正则化核形式. 自动化学报, 2004, 30(1): 27-36.

http://www.aas.net.cn/cn/article/id/16345?viewType=HTML

[20]   张永平, 郑南宁, 赵荣椿. 基于变分的图像恢复算法及收敛性. 自动化学报, 2002, 28(5): 673-680.

http://www.aas.net.cn/cn/article/id/15567?viewType=HTML

[21]   李文彪, 潘士先. 弱正则化边缘检测. 自动化学报, 1996, 22(5): 545-553.

http://www.aas.net.cn/cn/article/id/17127?viewType=HTML