張萍 朱衛(wèi)坪 陳曉峰 郭靖 馬培勇

摘要：局部主成分分析計算本征數(shù)維需要遍歷樣本，時間成本較高。文章提出一種改進算法ADLPCA，將樣本空間分割為多個區(qū)域，通過計算分割區(qū)域的主元維數(shù)得到本征維數(shù)。在UCI數(shù)據(jù)集和流程工業(yè)能耗數(shù)據(jù)集上的試驗表明，ADLPCA在計算效果與LPCA相媲美的情況下，可以顯著地降低計算耗時。

關鍵詞：區(qū)域分割;本征維數(shù);局部主成分分析

中圖分類號：TP18? ? ? 文獻標識碼：A

文章編號：1009-3044（2022）17-0078-03

流程工業(yè)在智能制造和工業(yè)4.0的推動下不斷向智能化、數(shù)字化、網(wǎng)絡化發(fā)展[1]。工業(yè)的信息化，集散控制系統(tǒng)使用，實時數(shù)據(jù)采集，為流程工業(yè)提供了高維數(shù)，多尺度基礎數(shù)據(jù)。從數(shù)據(jù)挖掘信息，實現(xiàn)對生產(chǎn)過程的智能監(jiān)控、分析、優(yōu)化，成為流程工業(yè)的關鍵任務之一。流程工業(yè)大數(shù)據(jù)的維度比較高，比如一套常規(guī)化工生產(chǎn)線數(shù)據(jù)采集點從幾千到十幾萬不等。數(shù)據(jù)維數(shù)超過20，就會引起“維數(shù)災難”問題[2]。降維技術，是解決維數(shù)災難的主要方向，研究人員提出了多種降維算法，如主成分分析、非負矩陣分解、因子分析、 奇異值分解、獨立成分分析等[3]。

降維算法把高維數(shù)據(jù)投影到低維空間，必然會造成信息損失，因此降維研究的難點是尋找高維數(shù)據(jù)的本征維數(shù)，以減少信息損失，同時又避免保留過多維數(shù)導致冗余計算[4]。最早的本征維數(shù)算法是局部主成分分析LPCA（Local Principle Analysis）[5]，該算法原理簡潔、實現(xiàn)方便，成為目前使用最多的本征維數(shù)估算方法。研究人員基于局部主成分分析改進出更多的算法，如從數(shù)據(jù)集均值中心進行局部區(qū)域搜索[6]，引入折棒分布（Broken Stick Distribution）維數(shù)估算準則[7]，拓展到非線性場景[8]等，以解決更多細化場景的應用。

局部主成分分析存在一個突出問題：計算本征維數(shù)的過程需要遍歷全部樣本，這導致其存在缺點：在數(shù)據(jù)集上耗時較久，且樣本密集區(qū)域對計算結果影響較大。一些研究結果表明，將樣本劃分成若干區(qū)域，用區(qū)域數(shù)據(jù)進行訓練，可以得到更快的訓練性能。比如，先用K-means聚類算法將樣本集劃分為多個區(qū)域，在子區(qū)域訓練KNN分類器[9]，用固定半徑超球分割樣本集，再用超球區(qū)域訓練KNN分類器[10-11]，基于網(wǎng)格樣本密度進行區(qū)域劃分實現(xiàn)流式數(shù)據(jù)聚類[12]，根據(jù)劃分的子區(qū)域特征數(shù)量閾值提高特征提取效率[13]。

本文提出一種基于區(qū)域分割的局部主成分分析算法ADLPCA（Area Division Local Principal Component Analysis），具體地，將數(shù)據(jù)集劃分為若干子區(qū)域，然后計算每個子區(qū)域的局部主成分分析，最后加權計算本征維數(shù)，由此提升本征維數(shù)的計算效率，并降低數(shù)據(jù)密集區(qū)的權重影響。

1 局部主成分分析

主成分分析把高維數(shù)據(jù)投影到低維空間：給定一個數(shù)據(jù)集，先對數(shù)據(jù)集進行中心化，再計算數(shù)據(jù)集的協(xié)方差陣及其特征值，保留最大的若干特征值，并計算這些特征值對應的單位特征向量，把數(shù)據(jù)集投影到這些單位特征向量，即得到數(shù)據(jù)集在低維空間的坐標。

局部主成分分析，對每個樣本的局部臨域做主成分分析，獲取局部鄰域的主元維數(shù)，然后根據(jù)主元維數(shù)計算數(shù)據(jù)集的本征維數(shù)[14]。

設數(shù)據(jù)集[S={Xi}]，其中[i∈{1，...，N}]，[Xi∈Rc]。局部主成分分析算法步驟如下：

步驟1：設定主成分閾值比率[t]，設定鄰域參數(shù)[δ]（如果是球形鄰域，[δ]為球半徑，如果是K近鄰鄰域，[δ]為樣本近鄰數(shù)）。

步驟2：[Xi]為樣本，令[i=1]，根據(jù)[δ]查找[Xi]的局部鄰域內(nèi)樣本，設有[Ni]個樣本，記為[Si={Xi1，...，XiNi}]。

步驟3：對[Si]進行中心化，計算其協(xié)方差陣以及所有特征值，把特征值從大到小排列，第一個特征值是最大的，設其為[λmax]，然后用這些特征值除以最大特征值[λmax]，轉化成歸一特征值：[λi1，...，λij，...，λiNi]，其中[λi1=λmaxλmax=1]。

步驟4：求級差[Δλij=λij-λij+1]，其中[j∈{1，...，Ni-1}]，遍歷[Δλij]，把第一個大于閾值[λmaxt]的[Δλij]對應的[j]記為[di]，是該樣本局部鄰域的主成分維數(shù)。

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

步驟6：令[dδ=1Ndi]表示鄰域參數(shù)為[δ]時的本征維數(shù)。

步驟7：減少[δ]值，返回步驟3，繼續(xù)執(zhí)行算法，直到[dδ]收斂到一個穩(wěn)定數(shù)值，記為[d]，為數(shù)據(jù)集的本征維數(shù)。

2 區(qū)域分割局部主成分分析

提出一種區(qū)域分割局部主成分分析算法Area Division Local Principle Analysis（ADLPCA）：給定樣本集，對每一個樣本，查找其K個近鄰樣本;選擇一個樣本，把它和它的K個近鄰樣本組成一個子區(qū)域，然后將加入這個子區(qū)域的所有樣本從樣本集中刪除;其他的樣本也按照上述過程進行處理，直到形成所有的子區(qū)域;對所有的子區(qū)域做局部主元分析，計算主元維數(shù);根據(jù)所有子區(qū)域的主元維數(shù)計算本征維數(shù)。算法詳細步驟如下：

步驟1：設定近鄰數(shù)K，主成分閾值比率[t]，子區(qū)域樣本數(shù)比率[r]

步驟2：設數(shù)據(jù)集[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]包含的樣本數(shù)大于等于[rK]，則[Di]記為一個有效的子區(qū)域，同時從[S]刪除[Di]包含的全部樣本。

步驟9：[i=i+1]

步驟10：如果[i

步驟11：記所有的子區(qū)域為[D={Di}，i∈{1，M}]，其中[M]為有效子區(qū)域的數(shù)量。

步驟12：i=1

步驟13：對子區(qū)域[Di]，進行中心化，設子區(qū)域的樣本數(shù)為[Ni]，計算其協(xié)方差陣以及歸一特征值[λi1，...，λij，...，λiNi]，其中[λi1=1]，記最大值為[λmax]。

步驟14：求歸一特征值級差[Δλij=λij-λij+1]，其中[j∈{1，...，Ni-1}]，遍歷[Δλij]，把第一個大于閾值[λmaxt]的[Δλij]對應的[j]記為[di]，是子區(qū)域的主成分維數(shù)[di]。

步驟15：[i=i+1]

步驟16：如果[i

步驟17：記[d={di}]，[i∈{1，M}]，計算[dK=1Mdi]是近鄰數(shù)為K時的主成分維數(shù)。

步驟18：減少近鄰數(shù)K，返回步驟4，繼續(xù)執(zhí)行算法。多次循環(huán)。直到[dK]收斂到一個數(shù)值記為[d]，為數(shù)據(jù)集的本征維數(shù)。

3 實驗數(shù)據(jù)與分析

試驗數(shù)據(jù)來源于UCI[15]的4個數(shù)據(jù)集，分別是Banknote Authentication（Banknote），Breast Cancer Wisconsin Diagnostic（Wdbc），Iris，Page Blocks Classification（Pageblocks）。這些數(shù)據(jù)集的屬性都是數(shù)值型。研究本征維數(shù)不需要使用類別信息，去除類別信息后，Iris為150個樣本4個屬性，Wdbc為569個樣本30個屬性，Banknote為1372個樣本4個屬性，Pageblocks為5473個樣本11個屬性。4個數(shù)據(jù)集的所有屬性值均做歸一化處理，以消除屬性數(shù)值的不同取值范圍對試驗的影響，歸一化方式如下：

數(shù)據(jù)預處理后，配置ADLPCA算法的參數(shù)。ADLPCA有三個參數(shù)：區(qū)域分割近鄰參數(shù)K;主成分閾值比例[t];子區(qū)域樣本數(shù)比率[r]。為充分研究K參數(shù)的影響，對所有數(shù)據(jù)集，按照樣本總數(shù)的30%，29%，...，1%的比例遞減取值，如果遇到K不為正整數(shù)的情況，則根據(jù)四舍五入的原則將其調(diào)整為正整數(shù)。主成分閾值比例[t]按照經(jīng)驗取0.05，也就是說，計算時，按照最大特征值的0.05倍為閾值。子區(qū)域樣本數(shù)比率[r]按照經(jīng)驗值取0.6，進行區(qū)域分割的時候，[K]為當前輪次的近鄰參數(shù)，如果候選區(qū)域的樣本數(shù)小于[rK]，則放棄該區(qū)域，選擇下一個樣本進行區(qū)域分割。用LPCA算法與ADLPCA做對比試驗。LPCA有兩個參數(shù)，近鄰參數(shù)K;主成分閾值比率[t]。這兩個參數(shù)的設定方式與ADLPCA是相同的。

實驗采用計算機配置：CPU：Intel i7雙核 2.80GHz;內(nèi)存：16G;操作系統(tǒng)：Windows 10（64位）。

表1給出ADLPCA和LPCA的運行時間。從運行時間而言，ADLPCA耗時大約為LPCA的十分之一，說明ADLPCA在效率上具有明顯的優(yōu)勢，其原因在于ADLPCA只需要計算分割區(qū)域的局部主成分維數(shù)，LPCA需要遍歷全部樣本計算每個樣本所在鄰域的主成分維數(shù)。如Pagelocks數(shù)據(jù)集，在參數(shù)[K=129]時，分割區(qū)域數(shù)量是76個，只需計算76個分割區(qū)域的PCA，而LPCA需要計算5473個樣本近鄰區(qū)域PCA。

圖1～圖4分別給出了ADLPCA和LPCA的本征維數(shù)試驗結果。橫坐標為參數(shù)K從大到小的遞減迭代序號，縱坐標為這些K值計算出來的局部主成分維數(shù)。從圖中可以看出，ADLPCA的計算結果與LPCA的計算結果具有一致的趨勢，可以得到幾乎一致的本征維數(shù)。LPCA的曲線更為平滑，原因在于其計算是通過對全部樣本的鄰域主成分維數(shù)取均值實現(xiàn)的，樣本數(shù)量比ADLPCA的分割區(qū)域數(shù)量大得多，因此其曲線必然更為平滑。高維數(shù)據(jù)集的本征維數(shù)顯著更低，比如Wdbc數(shù)據(jù)集樣本維數(shù)為30維，本征維數(shù)約為10.3維，Pageblocks數(shù)據(jù)集樣本維數(shù)為11維，本征維數(shù)約為3.4維，表明高維數(shù)據(jù)嵌入在低維子空間上。低維數(shù)據(jù)集的本征維數(shù)跟樣本維數(shù)較為接近，Iris數(shù)據(jù)集和Banknote數(shù)據(jù)集的樣本維數(shù)均為4，本征維數(shù)也幾乎接近4。

4 流程工業(yè)能耗數(shù)據(jù)降維分析

流程工業(yè)生產(chǎn)環(huán)節(jié)多、工藝復雜，智能制造和工業(yè)4.0為流程工業(yè)提供的基礎數(shù)據(jù)。按照傳統(tǒng)方式進行數(shù)據(jù)分析，會面臨較高的成本。比如，對若干個環(huán)節(jié)進行組合分析，需要根據(jù)工藝以人工統(tǒng)計每個測點的工藝特性，又比如對電、燃氣等能耗進行分析，需要確認不同計量儀表之間的總量和分量關系，然后再進行綜合處理。實踐表明，靈活組合測試數(shù)據(jù)，計算其本征維數(shù)，然后再根據(jù)本征維數(shù)進行降維，再做后續(xù)機器學習分析，是一種高性價比的方案。

以某化工廠的有功功率能耗分析為例，研究其本征數(shù)維問題。對該化工廠進行數(shù)據(jù)收集，統(tǒng)計到304個測點，測點形如“TLHG5C010100401ACP，I段進線有功功率”，“TLG3B020100601ACP，3P-24A貧甲醇泵有功功率”等。每個測點記錄不同工藝環(huán)節(jié)的有功功率，所有測點每五秒記錄一次讀值，選取5000個數(shù)值，時長共計約7個小時，覆蓋典型的工藝工況。對數(shù)據(jù)進行歸一化預處理，生成304維數(shù)據(jù)集，每維有5000個數(shù)值。按照第4節(jié)的參數(shù)，用ADLPCA和LPCA對該數(shù)據(jù)集進行本征維數(shù)計算，計算結果如圖5所示。ADLPCA運行時間7.63秒，LPCA運行時間68.40秒，ADLPCA具有較大的節(jié)時優(yōu)勢，在較短的時間內(nèi)得到與LPCA近似的結果。有功功率數(shù)據(jù)集的本征維數(shù)約在2.3維左右，表明大部分測點記錄的是彼此獨立工藝環(huán)節(jié)的有功功率，然后再匯集到少數(shù)功率總表。

5 結論

針對局部主成分分析LPCA遍歷樣本導致的效率問題，提出一種基于區(qū)域分割的改進算法ADLPCA。試驗結果以及在化工能耗數(shù)據(jù)處理上表明，ADLPCA在計算效果與LPCA相媲美的情況下，可以顯著地降低計算耗時，同時也說明區(qū)域分割策略在本征維數(shù)計算上的有效性。

參考文獻：

[1] 柴天佑，劉強，丁進良，等.工業(yè)互聯(lián)網(wǎng)驅動的流程工業(yè)智能優(yōu)化制造新模式研究展望[J].中國科學：技術科學，2022，52（1）：14-25.

[2] 薄樹奎，李盛陽，朱重光.基于統(tǒng)計學的最近鄰查詢中維數(shù)災難的研究[J].計算機工程，2006，32（21）：6-8.

[3] 張煜東，霍元鎧，吳樂南，等.降維技術與方法綜述[J].四川兵工學報，2010，31（10）：1-7.

[4] 宋懷波，何東健.面向精細農(nóng)業(yè)的高維數(shù)據(jù)本征維數(shù)估計方法研究進展[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] 胡元，石冰.基于區(qū)域劃分的kNN文本快速分類算法研究[J].計算機科學，2012，39（10）：182-186.

[10] 趙忠?guī)?，張公?改進的KNN快速分類算法[J].青島大學學報（自然科學版），2014，27（4）：39-43.

[11] 郝衛(wèi)杰，王艷飛，胡敬偉，等.基于超球區(qū)域劃分的改進KNN算法[J].青島大學學報（自然科學版），2017，30（1）：85-90.

[12] 于翔，印桂生，許憲東，等.一種基于區(qū)域劃分的數(shù)據(jù)流子空間聚類方法[J].計算機研究與發(fā)展，2014，51（1）：88-95.

[13] 孫浩，王朋.一種基于區(qū)域劃分的改進ORB算法[J].北京航空航天大學學報，2020，46（9）：1763-1769.

[14] 劉建.高維數(shù)據(jù)的本征維數(shù)估計方法研究[D].長沙：國防科學技術大學，2005.

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

收稿日期：2022-02-10

作者簡介：張萍（1981—），女，研究生學歷，主要從事云計算、實時數(shù)據(jù)庫、大數(shù)據(jù)技術開發(fā)和應用研究。