區域分割局部主成分分析及其應用

張萍 朱衛坪 陳曉峰 郭靖 馬培勇

摘要：局部主成分分析計算本征數維需要遍歷樣本，時間成本較高。文章提出一種改進算法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—），女，研究生學歷，主要從事云計算、實時數據庫、大數據技術開發和應用研究。