区域分割局部主成分分析及其应用

张萍 朱卫坪 陈晓峰 郭靖 马培勇

摘要：局部主成分分析计算本征数维需要遍历样本，时间成本较高。文章提出一种改进算法ADLPCA，将样本空间分割为多个区域，通过计算分割区域的主元维数得到本征维数。在UCI数据集和流程工业能耗数据集上的试验表明，ADLPCA在计算效果与LPCA相媲美的情况下，可以显著地降低计算耗时。

关键词：区域分割;本征维数;局部主成分分析

中图分类号：TP18      文献标识码：A

文章编号：1009-3044（2022）17-0078-03

流程工业在智能制造和工业4.0的推动下不断向智能化、数字化、网络化发展[1]。工业的信息化，集散控制系统使用，实时数据采集，为流程工业提供了高维数，多尺度基础数据。从数据挖掘信息，实现对生产过程的智能监控、分析、优化，成为流程工业的关键任务之一。流程工业大数据的维度比较高，比如一套常规化工生产线数据采集点从几千到十几万不等。数据维数超过20，就会引起“维数灾难”问题[2]。降维技术，是解决维数灾难的主要方向，研究人员提出了多种降维算法，如主成分分析、非负矩阵分解、因子分析、 奇异值分解、独立成分分析等[3]。

降维算法把高维数据投影到低维空间，必然会造成信息损失，因此降维研究的难点是寻找高维数据的本征维数，以减少信息损失，同时又避免保留过多维数导致冗余计算[4]。最早的本征维数算法是局部主成分分析LPCA（Local Principle Analysis）[5]，该算法原理简洁、实现方便，成为目前使用最多的本征维数估算方法。研究人员基于局部主成分分析改进出更多的算法，如从数据集均值中心进行局部区域搜索[6]，引入折棒分布（Broken Stick Distribution）维数估算准则[7]，拓展到非线性场景[8]等，以解决更多细化场景的应用。

局部主成分分析存在一个突出问题：计算本征维数的过程需要遍历全部样本，这导致其存在缺点：在数据集上耗时较久，且样本密集区域对计算结果影响较大。一些研究结果表明，将样本划分成若干区域，用区域数据进行训练，可以得到更快的训练性能。比如，先用K-means聚类算法将样本集划分为多个区域，在子区域训练KNN分类器[9]，用固定半径超球分割样本集，再用超球区域训练KNN分类器[10-11]，基于网格样本密度进行区域划分实现流式数据聚类[12]，根据划分的子区域特征数量阈值提高特征提取效率[13]。

本文提出一种基于区域分割的局部主成分分析算法ADLPCA（Area Division Local Principal Component Analysis），具体地，将数据集划分为若干子区域，然后计算每个子区域的局部主成分分析，最后加权计算本征维数，由此提升本征维数的计算效率，并降低数据密集区的权重影响。

1 局部主成分分析

主成分分析把高维数据投影到低维空间：给定一个数据集，先对数据集进行中心化，再计算数据集的协方差阵及其特征值，保留最大的若干特征值，并计算这些特征值对应的单位特征向量，把数据集投影到这些单位特征向量，即得到数据集在低维空间的坐标。

局部主成分分析，对每个样本的局部临域做主成分分析，获取局部邻域的主元维数，然后根据主元维数计算数据集的本征维数[14]。

设数据集[S={Xi}]，其中[i∈{1，...，N}]，[Xi∈Rc]。局部主成分分析算法步骤如下：

步骤1：设定主成分阈值比率[t]，设定邻域参数[δ]（如果是球形邻域，[δ]为球半径，如果是K近邻邻域，[δ]为样本近邻数）。

步骤2：[Xi]为样本，令[i=1]，根据[δ]查找[Xi]的局部邻域内样本，设有[Ni]个样本，记为[Si={Xi1，...，XiNi}]。

步骤3：对[Si]进行中心化，计算其协方差阵以及所有特征值，把特征值从大到小排列，第一个特征值是最大的，设其为[λmax]，然后用这些特征值除以最大特征值[λmax]，转化成归一特征值：[λi1，...，λij，...，λiNi]，其中[λi1=λmaxλmax=1]。

步骤4：求级差[Δλij=λij-λij+1]，其中[j∈{1，...，Ni-1}]，遍历[Δλij]，把第一个大于阈值[λmaxt]的[Δλij]对应的[j]记为[di]，是该样本局部邻域的主成分维数。

步骤5：令[i=i+1]，如[i

步骤6：令[dδ=1Ndi]表示邻域参数为[δ]时的本征维数。

步骤7：减少[δ]值，返回步骤3，继续执行算法，直到[dδ]收敛到一个稳定数值，记为[d]，为数据集的本征维数。

2 区域分割局部主成分分析

提出一种区域分割局部主成分分析算法Area Division Local Principle Analysis（ADLPCA）：给定样本集，对每一个样本，查找其K个近邻样本;选择一个样本，把它和它的K个近邻样本组成一个子区域，然后将加入这个子区域的所有样本从样本集中删除;其他的样本也按照上述过程进行处理，直到形成所有的子区域;对所有的子区域做局部主元分析，计算主元维数;根据所有子区域的主元维数计算本征维数。算法详细步骤如下：

步骤1：设定近邻数K，主成分阈值比率[t]，子区域样本数比率[r]

步骤2：设数据集[S={Xi}]，其中[i∈{1，...，N}]，[Xi∈Rc]。

步骤3：[i=1]

步骤4：在样本集[S]查找[Xi]的K个近邻样本，记这些近邻样本组成样本集[Bi]

步骤5：[i=i+1]

步骤6：如果[i

步骤7：[i=1]

步骤8：将[Xi]和[Bi]组成样本集[Ci]，计算[Ci]和[S]交集[Di=Ci∩S]，如果[Di]包含的样本数大于等于[rK]，则[Di]记为一个有效的子区域，同时从[S]删除[Di]包含的全部样本。

步骤9：[i=i+1]

步骤10：如果[i

步骤11：记所有的子区域为[D={Di}，i∈{1，M}]，其中[M]为有效子区域的数量。

步骤12：i=1

步骤13：对子区域[Di]，进行中心化，设子区域的样本数为[Ni]，计算其协方差阵以及归一特征值[λi1，...，λij，...，λiNi]，其中[λi1=1]，记最大值为[λmax]。

步骤14：求归一特征值级差[Δλij=λij-λij+1]，其中[j∈{1，...，Ni-1}]，遍历[Δλij]，把第一个大于阈值[λmaxt]的[Δλij]对应的[j]记为[di]，是子区域的主成分维数[di]。

步骤15：[i=i+1]

步骤16：如果[i

步骤17：记[d={di}]，[i∈{1，M}]，计算[dK=1Mdi]是近邻数为K时的主成分维数。

步骤18：减少近邻数K，返回步骤4，继续执行算法。多次循环。直到[dK]收敛到一个数值记为[d]，为数据集的本征维数。

3 实验数据与分析

试验数据来源于UCI[15]的4个数据集，分别是Banknote Authentication（Banknote），Breast Cancer Wisconsin Diagnostic（Wdbc），Iris，Page Blocks Classification（Pageblocks）。这些数据集的属性都是数值型。研究本征维数不需要使用类别信息，去除类别信息后，Iris为150个样本4个属性，Wdbc为569个样本30个属性，Banknote为1372个样本4个属性，Pageblocks为5473个样本11个属性。4个数据集的所有属性值均做归一化处理，以消除属性数值的不同取值范围对试验的影响，归一化方式如下：

数据预处理后，配置ADLPCA算法的参数。ADLPCA有三个参数：区域分割近邻参数K;主成分阈值比例[t];子区域样本数比率[r]。为充分研究K参数的影响，对所有数据集，按照样本总数的30%，29%，...，1%的比例递减取值，如果遇到K不为正整数的情况，则根据四舍五入的原则将其调整为正整数。主成分阈值比例[t]按照经验取0.05，也就是说，计算时，按照最大特征值的0.05倍为阈值。子区域样本数比率[r]按照经验值取0.6，进行区域分割的时候，[K]为当前轮次的近邻参数，如果候选区域的样本数小于[rK]，则放弃该区域，选择下一个样本进行区域分割。用LPCA算法与ADLPCA做对比试验。LPCA有两个参数，近邻参数K;主成分阈值比率[t]。这两个参数的设定方式与ADLPCA是相同的。

实验采用计算机配置：CPU：Intel i7双核 2.80GHz;内存：16G;操作系统：Windows 10（64位）。

表1给出ADLPCA和LPCA的运行时间。从运行时间而言，ADLPCA耗时大约为LPCA的十分之一，说明ADLPCA在效率上具有明显的优势，其原因在于ADLPCA只需要计算分割区域的局部主成分维数，LPCA需要遍历全部样本计算每个样本所在邻域的主成分维数。如Pagelocks数据集，在参数[K=129]时，分割区域数量是76个，只需计算76个分割区域的PCA，而LPCA需要计算5473个样本近邻区域PCA。

图1～图4分别给出了ADLPCA和LPCA的本征维数试验结果。横坐标为参数K从大到小的递减迭代序号，纵坐标为这些K值计算出来的局部主成分维数。从图中可以看出，ADLPCA的计算结果与LPCA的计算结果具有一致的趋势，可以得到几乎一致的本征维数。LPCA的曲线更为平滑，原因在于其计算是通过对全部样本的邻域主成分维数取均值实现的，样本数量比ADLPCA的分割区域数量大得多，因此其曲线必然更为平滑。高维数据集的本征维数显著更低，比如Wdbc数据集样本维数为30维，本征维数约为10.3维，Pageblocks数据集样本维数为11维，本征维数约为3.4维，表明高维数据嵌入在低维子空间上。低维数据集的本征维数跟样本维数较为接近，Iris数据集和Banknote数据集的样本维数均为4，本征维数也几乎接近4。

4 流程工业能耗数据降维分析

流程工业生产环节多、工艺复杂，智能制造和工业4.0为流程工业提供的基础数据。按照传统方式进行数据分析，会面临较高的成本。比如，对若干个环节进行组合分析，需要根据工艺以人工统计每个测点的工艺特性，又比如对电、燃气等能耗进行分析，需要确认不同计量仪表之间的总量和分量关系，然后再进行综合处理。实践表明，灵活组合测试数据，计算其本征维数，然后再根据本征维数进行降维，再做后续机器学习分析，是一种高性价比的方案。

以某化工厂的有功功率能耗分析为例，研究其本征数维问题。对该化工厂进行数据收集，统计到304个测点，测点形如“TLHG5C010100401ACP，I段进线有功功率”，“TLG3B020100601ACP，3P-24A贫甲醇泵有功功率”等。每个测点记录不同工艺环节的有功功率，所有测点每五秒记录一次读值，选取5000个数值，时长共计约7个小时，覆盖典型的工艺工况。对数据进行归一化预处理，生成304維数据集，每维有5000个数值。按照第4节的参数，用ADLPCA和LPCA对该数据集进行本征维数计算，计算结果如图5所示。ADLPCA运行时间7.63秒，LPCA运行时间68.40秒，ADLPCA具有较大的节时优势，在较短的时间内得到与LPCA近似的结果。有功功率数据集的本征维数约在2.3维左右，表明大部分测点记录的是彼此独立工艺环节的有功功率，然后再汇集到少数功率总表。

5 结论

针对局部主成分分析LPCA遍历样本导致的效率问题，提出一种基于区域分割的改进算法ADLPCA。试验结果以及在化工能耗数据处理上表明，ADLPCA在计算效果与LPCA相媲美的情况下，可以显著地降低计算耗时，同时也说明区域分割策略在本征维数计算上的有效性。

参考文献：

[1] 柴天佑，刘强，丁进良，等.工业互联网驱动的流程工业智能优化制造新模式研究展望[J].中國科学：技术科学，2022，52（1）：14-25.

[2] 薄树奎，李盛阳，朱重光.基于统计学的最近邻查询中维数灾难的研究[J].计算机工程，2006，32（21）：6-8.

[3] 张煜东，霍元铠，吴乐南，等.降维技术与方法综述[J].四川兵工学报，2010，31（10）：1-7.

[4] 宋怀波，何东健.面向精细农业的高维数据本征维数估计方法研究进展[J].中国科学：信息科学，2010，40（S1）：104-110.

[5] Bennett R.The intrinsic dimensionality of signal collections[J].IEEE Transactions on Information Theory，1969，15（5）：517-525.

[6] Fukunaga K，Olsen D R.An algorithm for finding intrinsic dimensionality of data[J].IEEE Transactions on Computers，1971，C-20（2）：176-183.

[7] Cangelosi R，Goriely A.Component retention in principal component analysis with application to cDNA microarray data[J].Biology Direct，2007，2：2.

[8] Chen C K，Andrews H C.Nonlinear intrinsic dimensionality computations[J].IEEE Transactions on Computers，1974，C-23（2）：178-184.

[9] 胡元，石冰.基于区域划分的kNN文本快速分类算法研究[J].计算机科学，2012，39（10）：182-186.

[10] 赵忠帅，张公敬.改进的KNN快速分类算法[J].青岛大学学报（自然科学版），2014，27（4）：39-43.

[11] 郝卫杰，王艳飞，胡敬伟，等.基于超球区域划分的改进KNN算法[J].青岛大学学报（自然科学版），2017，30（1）：85-90.

[12] 于翔，印桂生，许宪东，等.一种基于区域划分的数据流子空间聚类方法[J].计算机研究与发展，2014，51（1）：88-95.

[13] 孙浩，王朋.一种基于区域划分的改进ORB算法[J].北京航空航天大学学报，2020，46（9）：1763-1769.

[14] 刘建.高维数据的本征维数估计方法研究[D].长沙：国防科学技术大学，2005.

[15]UCI Machine Learning Rpository[DB] https：//archive-beta.ics.uci.edu/ml/datasets.

收稿日期：2022-02-10

作者简介：张萍（1981—），女，研究生学历，主要从事云计算、实时数据库、大数据技术开发和应用研究。