基于維度擴(kuò)展重排的高維數(shù)據(jù)降維挖掘技術(shù)

鄧 慧，譚樂(lè)婷

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

1 引言

利用多變量構(gòu)成向量，表示觀察目標(biāo)的完整信息，將這些變量抽象出來(lái)就是高維數(shù)據(jù)。高維數(shù)據(jù)雖然可以提供與客觀事物相關(guān)的詳細(xì)信息，但表達(dá)形式復(fù)雜，為數(shù)據(jù)挖掘工作帶來(lái)困難。數(shù)據(jù)挖掘代表從海量數(shù)據(jù)中獲取隱含的、潛在有用的知識(shí)技術(shù)，任務(wù)可以分為預(yù)測(cè)與描述兩種。預(yù)測(cè)類任務(wù)目的是結(jié)合已知屬性預(yù)測(cè)未知屬性值；描述類任務(wù)是為得到數(shù)據(jù)隱藏的某種模式。無(wú)論是哪種任務(wù)最終目的都是實(shí)現(xiàn)數(shù)據(jù)到信息的轉(zhuǎn)換。如今，獲取數(shù)據(jù)已不再困難，從高維數(shù)據(jù)中挖掘有用信息則成為亟待解決的問(wèn)題。

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

以上兩種方法雖然可以滿足高精度挖掘標(biāo)準(zhǔn)，但算法較為復(fù)雜，時(shí)間消耗較大，不能確保數(shù)據(jù)挖掘的完整性。為此，本文在維度擴(kuò)展重排[3]基礎(chǔ)上對(duì)高維數(shù)據(jù)降維挖掘技術(shù)進(jìn)行研究。通過(guò)數(shù)據(jù)預(yù)處理消除高維數(shù)據(jù)差異；對(duì)維度展開(kāi)重排，優(yōu)化高維數(shù)據(jù)集合中不同維度存在的關(guān)系；利用降維算法，在低維空間中簡(jiǎn)化數(shù)據(jù)結(jié)構(gòu)，并保持初始數(shù)據(jù)完整性，達(dá)到特征提取目的實(shí)現(xiàn)數(shù)據(jù)挖掘。

2 維度擴(kuò)展重排下的高維數(shù)據(jù)降維處理

高維數(shù)據(jù)特征占用空間較大，導(dǎo)致其信息挖掘過(guò)程緩慢，準(zhǔn)確度較低，為此需要對(duì)其進(jìn)行降維處理。對(duì)高維數(shù)據(jù)預(yù)處理，采用Z-score方法將其變換為轉(zhuǎn)換函數(shù)形式，確定數(shù)據(jù)首維度，利用皮爾森相關(guān)系數(shù)絕對(duì)值計(jì)算維度相關(guān)性，利用得到的相似度矩陣對(duì)維度重新排列，將相似高維數(shù)據(jù)組合投影在低維空間中，通過(guò)特征值推理找出能夠體現(xiàn)初始高維數(shù)據(jù)結(jié)構(gòu)的投影，實(shí)現(xiàn)高維數(shù)據(jù)的降維處理。以下將對(duì)此做出詳細(xì)分析。

2.1 高維對(duì)數(shù)據(jù)挖掘影響分析

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

2.1.1 對(duì)聚類模型的影響

聚類最終目的是將完整的數(shù)據(jù)集合分割成多個(gè)數(shù)據(jù)簇，確保其類內(nèi)相似程度達(dá)到最高，類間相似性最小。相似性屬于聚類的關(guān)鍵度量準(zhǔn)則。在高維空間中一些距離度量會(huì)存在失效現(xiàn)象，使聚類概念失去本質(zhì)意義。除此之外，索引結(jié)構(gòu)失效以及網(wǎng)格數(shù)量隨維數(shù)提高的問(wèn)題也會(huì)使聚類模型不再有效。

2.1.2 對(duì)關(guān)聯(lián)規(guī)則的影響

對(duì)關(guān)聯(lián)規(guī)則的挖掘也可理解為對(duì)頻繁項(xiàng)集的搜索(頻繁項(xiàng)集為經(jīng)常同步出現(xiàn)的特征集合)。但多數(shù)頻繁項(xiàng)集挖掘方法均是在特征計(jì)數(shù)基礎(chǔ)上進(jìn)行的，隨維數(shù)增長(zhǎng)，特征組合也出現(xiàn)指數(shù)增長(zhǎng)趨勢(shì)。因此在維數(shù)達(dá)到一定量級(jí)時(shí)不能在此空間中繼續(xù)搜索。

2.2 數(shù)據(jù)預(yù)處理

在維度擴(kuò)展重排之前對(duì)數(shù)據(jù)做預(yù)處理是高維數(shù)據(jù)降維挖掘的關(guān)鍵步驟，本文通過(guò)數(shù)據(jù)標(biāo)準(zhǔn)化方法[4]對(duì)其進(jìn)行預(yù)處理。此方法是將數(shù)據(jù)根據(jù)固定比例縮放，使數(shù)據(jù)變換在一個(gè)特定區(qū)間內(nèi)。

該方法主要目的是去除數(shù)據(jù)之間差異，過(guò)濾冗余數(shù)據(jù)，方便不同單位和量級(jí)的指標(biāo)進(jìn)行對(duì)比。本文利用的標(biāo)準(zhǔn)化數(shù)據(jù)方法為Z-score。處理后的數(shù)據(jù)滿足標(biāo)準(zhǔn)正態(tài)分布，即均值是0，標(biāo)準(zhǔn)差是1，其轉(zhuǎn)換函數(shù)如下

(1)

式中，u表示全部樣本數(shù)據(jù)平均值，σ代表樣本數(shù)據(jù)標(biāo)準(zhǔn)差。利用上述轉(zhuǎn)換函數(shù)對(duì)數(shù)據(jù)做預(yù)處理，并將處理結(jié)果存入矩陣，便于數(shù)據(jù)挖掘。

2.3 維度擴(kuò)展重排

對(duì)于維度擴(kuò)展重排主要分為如下三個(gè)步驟，下述說(shuō)明每步功能與實(shí)現(xiàn)方法。

2.3.1 確定首維度

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

本文通過(guò)奇異值分解方法[5]對(duì)維度擴(kuò)展重排，它能夠適用于任意矩陣，其表現(xiàn)形式為

A=U∑VT

(2)

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

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

2.3.2 計(jì)算維度相關(guān)性

此步驟主要獲取高維數(shù)據(jù)集維度之間的相關(guān)程度，尋找高維數(shù)據(jù)集合最優(yōu)維度排列順序。皮爾森方法屬于一種線性似度計(jì)算方式，此方法能夠較好體現(xiàn)兩個(gè)維度之間線性相關(guān)度。

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

(3)

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

(4)

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

2.4 降維算法

F：X→Yxy=F(x)

(5)

其中，Y表示d空間集合中一個(gè)子集，將F稱為數(shù)據(jù)集X到Y(jié)的降維。

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

通過(guò)降維將高維數(shù)據(jù)根據(jù)某種組合投影在低維空間中，找出可以體現(xiàn)初始高維數(shù)據(jù)結(jié)構(gòu)或特性的投影，在低維空間中對(duì)數(shù)據(jù)做簡(jiǎn)化處理，將P個(gè)初始變量利用P′代替，確保數(shù)據(jù)完整性。此過(guò)程也可稱為特征提取[7]。

在分析數(shù)據(jù)過(guò)程中，一般將多元數(shù)據(jù)投影在二維平面中，采用散點(diǎn)圖研究變量之間具有的聯(lián)系。根據(jù)數(shù)據(jù)點(diǎn)與其在某個(gè)k維空間上投影的異差平方和比向其余空間投影時(shí)更低(1≤k≤P-1)為標(biāo)準(zhǔn)來(lái)挑選投影方向與數(shù)量。根本目的是捕獲數(shù)據(jù)最大變換性，降低數(shù)據(jù)維度。

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

(6)

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

為取得唯一解，對(duì)權(quán)重C向量α進(jìn)行標(biāo)準(zhǔn)化處理，使α每個(gè)元素的平方和均為1，即αTα=1，在此標(biāo)準(zhǔn)化約束基礎(chǔ)上，最大化問(wèn)題能夠轉(zhuǎn)換為下述量的最大化：

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

(7)

式中，λ為拉格朗日乘子，對(duì)α求導(dǎo)且令其值等于0，則有

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

(8)

因此，獲得線性代數(shù)中特征值表達(dá)式

(C-λE)?=0

(9)

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

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

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

3 降維數(shù)據(jù)挖掘技術(shù)的實(shí)現(xiàn)

實(shí)現(xiàn)高維數(shù)據(jù)降維后對(duì)數(shù)據(jù)進(jìn)行挖掘，在K-L變換特性與相空間重構(gòu)基礎(chǔ)上建立挖掘模型。通過(guò)數(shù)據(jù)鏈距離做稀疏性融合[8]，再分析數(shù)據(jù)離群因子，獲取數(shù)據(jù)稀疏性公式

(10)

式中，ux與uy分別表示數(shù)據(jù)對(duì)象的二維幾何矩，C1為輸出數(shù)據(jù)不變矩。根據(jù)Radon尺度變換在低維項(xiàng)空間中運(yùn)算最大Lyapunove指數(shù)

(11)

式中，r1代表數(shù)據(jù)尺度分解維數(shù)，r2為先驗(yàn)點(diǎn)簇，σ1描述邊緣相關(guān)約束量，N1表示放射不變矩。

結(jié)合數(shù)據(jù)集合相似k距離序列尺度不變性原則[9]，實(shí)現(xiàn)數(shù)據(jù)聚類，聚類的目標(biāo)函數(shù)表示為

(12)

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

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

(13)

式中，誤差項(xiàng)e符合相似k距離分布，經(jīng)過(guò)特征壓縮，將K-L轉(zhuǎn)換公式簡(jiǎn)化為以下形式：

Y=Xβ+e

(14)

(15)

綜上所示，對(duì)高維數(shù)據(jù)降維挖掘的優(yōu)化實(shí)現(xiàn)步驟為：

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

2)對(duì)所有物理機(jī)軌跡上的數(shù)據(jù)點(diǎn)做初始化處理與空間重構(gòu)；

3)分配虛擬機(jī)，做測(cè)試樣本訓(xùn)練；

4)完成全部虛擬機(jī)分配后，遍歷所有數(shù)據(jù)點(diǎn)，獲取數(shù)據(jù)點(diǎn)鏈距離，對(duì)局部信息更新；

5)通過(guò)式(13)對(duì)數(shù)據(jù)進(jìn)行特征壓縮，在最佳分配方案下對(duì)數(shù)據(jù)聚類；

6)若當(dāng)前挖掘次數(shù)I

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

4 仿真分析

為驗(yàn)證所提算法對(duì)高維數(shù)據(jù)降維挖掘的性能，設(shè)計(jì)仿真。實(shí)驗(yàn)在MATLAB平臺(tái)上進(jìn)行，具體參數(shù)如表1所示。

表1 實(shí)驗(yàn)環(huán)境參數(shù)表

以CNNVD中國(guó)信息安全漏洞數(shù)據(jù)庫(kù)(http：∥www.cnnvd.org.cn)中的高維數(shù)據(jù)集為實(shí)驗(yàn)對(duì)象，原始數(shù)據(jù)大小100 MB，共6000個(gè)高維數(shù)據(jù)樣本，屬性維數(shù)為36954個(gè)。

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

圖1 高維數(shù)據(jù)采集時(shí)間序列波形圖

根據(jù)圖1給出的高維數(shù)據(jù)采集樣本作為測(cè)試目標(biāo)，對(duì)其進(jìn)行降維挖掘，并利用文獻(xiàn)[1]與文獻(xiàn)[2]方法對(duì)挖掘效果進(jìn)行對(duì)比。

圖2 不同方法的挖掘準(zhǔn)確度對(duì)比圖

圖3 不同方法的數(shù)據(jù)挖掘完整度對(duì)比圖

從圖2中可以看出，所提方法挖掘精準(zhǔn)度始終保持在80%以上，高于其它方法。究其原因是因?yàn)橥ㄟ^(guò)標(biāo)準(zhǔn)化法處理高維數(shù)據(jù)，剔除了冗余干擾、提高精準(zhǔn)度。隨著數(shù)據(jù)規(guī)模擴(kuò)大，三種方法對(duì)高維數(shù)據(jù)低維挖掘的完整性都在逐漸降低，但是所提方法對(duì)維度擴(kuò)展重排，明確數(shù)據(jù)屬性，較比其它方法數(shù)據(jù)挖掘完整程度高。

測(cè)試不同方法對(duì)100MB高維數(shù)據(jù)的降維挖掘時(shí)間，得到對(duì)比圖如圖4所示。

圖4 不同方法的挖掘時(shí)間對(duì)比圖

由圖4可知，所提方法整體挖掘過(guò)程耗時(shí)少，為0.36ms，相比文獻(xiàn)對(duì)比方法，所提方法沒(méi)有隨著樣本規(guī)模擴(kuò)大急速增加耗時(shí)，穩(wěn)定性更高，這一結(jié)果也表明所提方法的挖掘效率更高。

5 結(jié)論

為實(shí)現(xiàn)高維數(shù)據(jù)挖掘，提出基于維度擴(kuò)展重排的高維數(shù)據(jù)降維挖掘技術(shù)，本文綜合考慮挖掘速度與完成比率的均衡性能，通過(guò)實(shí)驗(yàn)測(cè)試證明該算法總體性能占優(yōu)。雖然此種方法達(dá)到預(yù)期效果，但是在某些應(yīng)用中還不夠完善，為將其推廣到更多領(lǐng)域中，在處理問(wèn)題時(shí)適應(yīng)性有待優(yōu)化。