基于維度擴展重排的高維數據降維挖掘技術

鄧 慧，譚樂婷

(西南石油大學，四川 南充 637000)

1 引言

利用多變量構成向量，表示觀察目標的完整信息，將這些變量抽象出來就是高維數據。高維數據雖然可以提供與客觀事物相關的詳細信息，但表達形式復雜，為數據挖掘工作帶來困難。數據挖掘代表從海量數據中獲取隱含的、潛在有用的知識技術，任務可以分為預測與描述兩種。預測類任務目的是結合已知屬性預測未知屬性值；描述類任務是為得到數據隱藏的某種模式。無論是哪種任務最終目的都是實現數據到信息的轉換。如今，獲取數據已不再困難，從高維數據中挖掘有用信息則成為亟待解決的問題。

文獻[1]提出基于FFD(Full Functional Device)的大規模高維數據局部異常挖掘方法。將無線傳輸技術引入到挖掘過程中，并定義方法核心是對作業級與任務級的實現，改善數據抗干擾性能，通過FFD控制性能實現無線傳輸技術和挖掘進程數據互通的目標；并結合FIFO(First Input First Output)挖掘思想，設計挖掘過程與目標函數。所提方法可靠性較強，可完成任務量較大的數據挖掘；文獻[2]提出基于改進多層次模糊關聯規則的定量數據挖掘方法。利用高頻項目集合，對迭代方法進行深化構成自上而下的挖掘過程，將模糊集合理論、數據挖掘算法與多層次分類技術相結合，尋找模糊關聯矩陣，挖掘數據庫中的隱含知識。該方法可根據不同要求實現數據挖掘。

以上兩種方法雖然可以滿足高精度挖掘標準，但算法較為復雜，時間消耗較大，不能確保數據挖掘的完整性。為此，本文在維度擴展重排[3]基礎上對高維數據降維挖掘技術進行研究。通過數據預處理消除高維數據差異；對維度展開重排，優化高維數據集合中不同維度存在的關系；利用降維算法，在低維空間中簡化數據結構，并保持初始數據完整性，達到特征提取目的實現數據挖掘。

2 維度擴展重排下的高維數據降維處理

高維數據特征占用空間較大，導致其信息挖掘過程緩慢，準確度較低，為此需要對其進行降維處理。對高維數據預處理，采用Z-score方法將其變換為轉換函數形式，確定數據首維度，利用皮爾森相關系數絕對值計算維度相關性，利用得到的相似度矩陣對維度重新排列，將相似高維數據組合投影在低維空間中，通過特征值推理找出能夠體現初始高維數據結構的投影，實現高維數據的降維處理。以下將對此做出詳細分析。

2.1 高維對數據挖掘影響分析

高維對象數據轉換可以存儲在二維數組中，例如已知一個N維對象，利用N維向量x=(x1，x2，…，xn)對其描述，其中xj代表此目標第j個特性值。m個N維對象集合可通過數組(xij)i=1，..，m，j=1，…，n代表，其中xij指集合中第i個對象的第j個特性值。在低維空間內，經常利用Lp距離(若p=1，Lp距離稱為Manhattan 距離)當作數據之間存在的相似性度量，然而在高維空間中大多數的相似性概念是不存在的。

2.1.1 對聚類模型的影響

聚類最終目的是將完整的數據集合分割成多個數據簇，確保其類內相似程度達到最高，類間相似性最小。相似性屬于聚類的關鍵度量準則。在高維空間中一些距離度量會存在失效現象，使聚類概念失去本質意義。除此之外，索引結構失效以及網格數量隨維數提高的問題也會使聚類模型不再有效。

2.1.2 對關聯規則的影響

對關聯規則的挖掘也可理解為對頻繁項集的搜索(頻繁項集為經常同步出現的特征集合)。但多數頻繁項集挖掘方法均是在特征計數基礎上進行的，隨維數增長，特征組合也出現指數增長趨勢。因此在維數達到一定量級時不能在此空間中繼續搜索。

2.2 數據預處理

在維度擴展重排之前對數據做預處理是高維數據降維挖掘的關鍵步驟，本文通過數據標準化方法[4]對其進行預處理。此方法是將數據根據固定比例縮放，使數據變換在一個特定區間內。

該方法主要目的是去除數據之間差異，過濾冗余數據，方便不同單位和量級的指標進行對比。本文利用的標準化數據方法為Z-score。處理后的數據滿足標準正態分布，即均值是0，標準差是1，其轉換函數如下

(1)

式中，u表示全部樣本數據平均值，σ代表樣本數據標準差。利用上述轉換函數對數據做預處理，并將處理結果存入矩陣，便于數據挖掘。

2.3 維度擴展重排

對于維度擴展重排主要分為如下三個步驟，下述說明每步功能與實現方法。

2.3.1 確定首維度

首維度的選擇非常重要，在數據集合中首維度不僅僅表示全部維度中貢獻率最大的維度，而且還可以提供最有價值數據，確定正確的首維度對于分析高維數據有較大幫助。

本文通過奇異值分解方法[5]對維度擴展重排，它能夠適用于任意矩陣，其表現形式為

A=U∑VT

(2)

式中，A表示隨機矩陣形式，若A屬于一個N*M的矩陣，則可將其分解為N*N的方陣U，N*M的矩陣∑，以及M*M的矩陣VT，其中U代表左奇異矩陣，∑表示奇異值構成，V中矢量稱作右奇異值矢量。

奇異值大小體現出維度重要程度，因此可以表示維度貢獻率。在維度重排過程中，利用上述公式獲取的奇異值大小來確定首維度。

2.3.2 計算維度相關性

此步驟主要獲取高維數據集維度之間的相關程度，尋找高維數據集合最優維度排列順序。皮爾森方法屬于一種線性似度計算方式，此方法能夠較好體現兩個維度之間線性相關度。

若相關系數利用r描述，其代表兩個維度之間線性相關程度的強弱。如果r的絕對值越高，代表相關性越強。其取值范圍是[-1，1]，若r>0，則說明兩個變量為正相關，其中一個變量值隨另一個變量值增大而增大；若r<0說明兩個變量為負相關，這時，某個變量隨另一變量的增加而減小。本文中利用的相似性表示方法為皮爾森相關系數絕對值，其表達式如下

(3)

通過以上兩個步驟能夠得知數據集合維度之間相似性，最后結果可以描述為一個相似性矩陣。在此矩陣中，對角線上存在的值是經過奇異值分解獲取的，表示維度貢獻率，其余值為皮爾森有關系數絕對值大小，體現維度相似性。此矩陣屬于對稱矩陣，表達式如下。通過獲取的相似度矩陣R對維度重新排列，確保高維數據在下述降維處理時維度具有一定相似性。

(4)

維度擴展重排的具體過程為：在矩陣R的對角線中選取最大值，將其所在維度當做首維度；在矩陣R里尋找與首位度相關程度最大的維度當做第二維度，以此類推一直到全部維度均被確定，即可獲取最終高維數據維度順序。利用此種維度擴展重排方法不但能明確最具吸引力的屬性還可以減少平行坐標雜波[6]。

2.4 降維算法

F：X→Yxy=F(x)

(5)

其中，Y表示d空間集合中一個子集，將F稱為數據集X到Y的降維。

如果F是X的線性函數，則將F稱為線性降維；反之為非線性降維。

通過降維將高維數據根據某種組合投影在低維空間中，找出可以體現初始高維數據結構或特性的投影，在低維空間中對數據做簡化處理，將P個初始變量利用P′代替，確保數據完整性。此過程也可稱為特征提取[7]。

在分析數據過程中，一般將多元數據投影在二維平面中，采用散點圖研究變量之間具有的聯系。根據數據點與其在某個k維空間上投影的異差平方和比向其余空間投影時更低(1≤k≤P-1)為標準來挑選投影方向與數量。根本目的是捕獲數據最大變換性，降低數據維度。

Var(Xα)=(Xα)T(Xα)=αTXTXα=αTCα

(6)

式中，C=XTX表示數據的P×P協方差矩陣，X的平均值為0，因此將最大化的投影數據方差Var(Xα)描述為α與協方差矩陣的函數。

為取得唯一解，對權重C向量α進行標準化處理，使α每個元素的平方和均為1，即αTα=1，在此標準化約束基礎上，最大化問題能夠轉換為下述量的最大化：

μ=αTCα-λ(αTα-1)

(7)

式中，λ為拉格朗日乘子，對α求導且令其值等于0，則有

?μ/?α=2Cα-2λα=0

(8)

因此，獲得線性代數中特征值表達式

(C-λE)?=0

(9)

式中，E表示單位矩陣。能夠計算出協方差矩陣C與最大特征值相對的特征向量α1，α2，即為數據矩陣的第一主成分。

計算與α1正交的、C的第二大特性值所對的特征向量α2，α2屬于數據矩陣的第二大主成分，以此類推，獲得第K個主成分(1≤k≤P-1)。能夠看出，這是K個互不相關的線性排列，數據點在此組合中決定K維空間中投影差異與平方和最小。

高維數據集合中變量之間通常密切相關，利用較少的主成分捕捉數據最大變換性是有可能實現的，這樣既可降低數據維度。一些數據挖掘模型都會考慮數據變換壓縮，本文利用維度重排方法提取數據主成分，成功實現降維。

3 降維數據挖掘技術的實現

實現高維數據降維后對數據進行挖掘，在K-L變換特性與相空間重構基礎上建立挖掘模型。通過數據鏈距離做稀疏性融合[8]，再分析數據離群因子，獲取數據稀疏性公式

(10)

式中，ux與uy分別表示數據對象的二維幾何矩，C1為輸出數據不變矩。根據Radon尺度變換在低維項空間中運算最大Lyapunove指數

(11)

式中，r1代表數據尺度分解維數，r2為先驗點簇，σ1描述邊緣相關約束量，N1表示放射不變矩。

結合數據集合相似k距離序列尺度不變性原則[9]，實現數據聚類，聚類的目標函數表示為

(12)

式中，J(ω，e)表示數據分塊約束矢量，ai代表相空間全部對象的排序，φ(xi)屬于噪聲敏感系數[10]。

假設A∈Rn×m，獲得挖掘數據信息特性的K-L變化公式為

(13)

式中，誤差項e符合相似k距離分布，經過特征壓縮，將K-L轉換公式簡化為以下形式：

Y=Xβ+e

(14)

(15)

綜上所示，對高維數據降維挖掘的優化實現步驟為：

1)設定挖掘的原始迭代次數為I=0，參數初始化；

2)對所有物理機軌跡上的數據點做初始化處理與空間重構；

3)分配虛擬機，做測試樣本訓練；

4)完成全部虛擬機分配后，遍歷所有數據點，獲取數據點鏈距離，對局部信息更新；

5)通過式(13)對數據進行特征壓縮，在最佳分配方案下對數據聚類；

6)若當前挖掘次數I

7)挖掘結束，輸出最佳分配方案，獲取挖掘結果。

4 仿真分析

為驗證所提算法對高維數據降維挖掘的性能，設計仿真。實驗在MATLAB平臺上進行，具體參數如表1所示。

表1 實驗環境參數表

以CNNVD中國信息安全漏洞數據庫(http：∥www.cnnvd.org.cn)中的高維數據集為實驗對象，原始數據大小100 MB，共6000個高維數據樣本，屬性維數為36954個。

其它參數設計中，傳感器進行數據采集的節點通信半徑為R=30m，高維數據歸一化原始頻率f1=0.8，終止頻率f2=0.15，假設噪聲數據中混有頻率是450Hz高斯白噪聲，在信噪比為SNR=-5dB與SNR=-8dB環境下，實現自適應波束形成。在上述仿真條件下得到的初始高維數據時間序列波形如下圖所示：

圖1 高維數據采集時間序列波形圖

根據圖1給出的高維數據采集樣本作為測試目標，對其進行降維挖掘，并利用文獻[1]與文獻[2]方法對挖掘效果進行對比。

圖2 不同方法的挖掘準確度對比圖

圖3 不同方法的數據挖掘完整度對比圖

從圖2中可以看出，所提方法挖掘精準度始終保持在80%以上，高于其它方法。究其原因是因為通過標準化法處理高維數據，剔除了冗余干擾、提高精準度。隨著數據規模擴大，三種方法對高維數據低維挖掘的完整性都在逐漸降低，但是所提方法對維度擴展重排，明確數據屬性，較比其它方法數據挖掘完整程度高。

測試不同方法對100MB高維數據的降維挖掘時間，得到對比圖如圖4所示。

圖4 不同方法的挖掘時間對比圖

由圖4可知，所提方法整體挖掘過程耗時少，為0.36ms，相比文獻對比方法，所提方法沒有隨著樣本規模擴大急速增加耗時，穩定性更高，這一結果也表明所提方法的挖掘效率更高。

5 結論

為實現高維數據挖掘，提出基于維度擴展重排的高維數據降維挖掘技術，本文綜合考慮挖掘速度與完成比率的均衡性能，通過實驗測試證明該算法總體性能占優。雖然此種方法達到預期效果，但是在某些應用中還不夠完善，為將其推廣到更多領域中，在處理問題時適應性有待優化。