基于改進(jìn)Spark技術(shù)的高維數(shù)據(jù)增量式聚類算法

劉仁芬，楊鳳麗，王 霞

(石家莊鐵道大學(xué)四方學(xué)院，河北 石家莊051132)

1 引言

高維數(shù)據(jù)包含多種屬性，例如空間位置信息、多物理參量、多時(shí)次數(shù)據(jù)、醫(yī)療數(shù)據(jù)等，也可將其理解為維度超過2的數(shù)據(jù)。該類數(shù)據(jù)已經(jīng)稱為當(dāng)下生活中經(jīng)常使用的一種數(shù)據(jù)[1]，但是由于該類數(shù)據(jù)的樣本量極大，分析和處理的難度以及效果較差，甚至無法完成原始高維數(shù)據(jù)的加載；并且，即便在實(shí)現(xiàn)加載的情況下，也會(huì)導(dǎo)致計(jì)算機(jī)資源的超量占用，對算法的運(yùn)算效率造成較大影響[2，3]。

當(dāng)前，諸多學(xué)者針對高維數(shù)據(jù)的增量式聚類均展開相關(guān)研究，例如趙萌萌等人基于共享近鄰緊密度，研究高維數(shù)據(jù)的增量式聚類算法[4]，斯亞民基于嵌入式模糊集數(shù)據(jù)庫，研究高維數(shù)據(jù)的增量式聚類算法[5]。上述算法，可用于完成正常數(shù)據(jù)的聚類處理，但是當(dāng)數(shù)據(jù)信息流中存在異常數(shù)據(jù)時(shí)，上述方法的敏感性較強(qiáng)，則處理效果較差。

本文結(jié)合高維數(shù)據(jù)的特點(diǎn)，依據(jù)spark技術(shù)對高維數(shù)據(jù)的增量式聚類算法進(jìn)行改進(jìn)，提出基于改進(jìn)spark技術(shù)的高維數(shù)據(jù)增量式聚類算法，實(shí)現(xiàn)高維數(shù)據(jù)的有效聚類處理，且避免敏感性的發(fā)生，提升數(shù)據(jù)處理效率。spark技術(shù)是一種用于處理大數(shù)據(jù)的計(jì)算引擎，也可理解為一種通用的并行架構(gòu)，可實(shí)現(xiàn)交互式計(jì)算，可高效完成大數(shù)據(jù)的處理，并且通用性能較好，可適用于多種程序，實(shí)用性能較高，支持復(fù)雜算法的運(yùn)算。增量式聚類是一種以提升數(shù)據(jù)聚類效果以及效率為目的，在上一次聚類的基礎(chǔ)上，提升此次聚類效率的一種聚類算法。該算法也是用于實(shí)現(xiàn)高維數(shù)據(jù)處理的一種主要方法。

2 基于改進(jìn)spark技術(shù)的高維數(shù)據(jù)增量式聚類算法

2.1 高維數(shù)據(jù)結(jié)構(gòu)重組

高維數(shù)據(jù)中，含有大量模糊數(shù)據(jù)，對高維數(shù)據(jù)的處理造成一定影響。因此，為實(shí)現(xiàn)高維數(shù)據(jù)增量式聚類，需重組高維數(shù)據(jù)結(jié)構(gòu)，獲取數(shù)據(jù)中的模糊數(shù)據(jù)。本文采用基于混沌分區(qū)方法完成。依據(jù)獲取的模糊數(shù)據(jù)分析該數(shù)據(jù)的時(shí)間序列混沌序列，以此分析兩種結(jié)構(gòu)[6]，分別為重構(gòu)結(jié)構(gòu)及數(shù)據(jù)結(jié)構(gòu)，前者屬于模糊數(shù)據(jù)。

{x1，x2，…，xN}表示觀測時(shí)間序列，屬于高維數(shù)據(jù)流，且為待挖掘狀態(tài)；寬帶時(shí)間序列用x(n)表示，處于平穩(wěn)狀態(tài)；對模糊數(shù)據(jù)結(jié)構(gòu)映射，且在特征空間中完成，其維數(shù)用m表示，基于此可得重組結(jié)構(gòu)公式，且屬于高維數(shù)據(jù)

X(n)={x(n)，x(n+τ)，…，x(n+(m-1)τ)}

(1)

式中：n=1，2，…，N；τ表示時(shí)間延遲。

為獲取模糊信息的分布軌跡[7]，需在完成特征融合的基礎(chǔ)上，分析相軌跡演化情況，且處于高維空間內(nèi)完成，則公式為

X=[s1，s2，…，sK]

(2)

式中：K表示嵌入維數(shù)，K=N-(m-1)τ，屬于特征空間，且在搜索過程中；m表示層數(shù)，屬于數(shù)據(jù)的本體特征；特征矢量集用si表示，屬于相空間中，且si=(xi，xi+1，…，xi+(m-1)τ)T。

2.2 高維數(shù)據(jù)降維

由于獲取的模糊數(shù)據(jù)的分布軌跡呈不均勻分布狀態(tài)，并且數(shù)據(jù)的維數(shù)較高，因此，本文采用基于信息熵的高維稀疏降維算法，先該分布空間的高維數(shù)據(jù)進(jìn)行特征篩選后，減少特征的數(shù)量，然后完成數(shù)據(jù)降維[8]。

閾值用δ表示，屬于信息熵，通過減少數(shù)據(jù)特征數(shù)量，將無效的原始數(shù)據(jù)特征去除，其降維過程如下所述：

輸入：輸入X，X包含的樣本數(shù)量為m、特征數(shù)量為n；貢獻(xiàn)率為f。

輸出：降維結(jié)果Yk×m。

1)對數(shù)據(jù)的所有特征進(jìn)行求解，將求解結(jié)果與δ進(jìn)行對比，進(jìn)行特征選取，對X進(jìn)行相關(guān)操作，操作內(nèi)容為：求解特征ai的信息熵H(ai)；向集合A中引入ai。

2)為獲取矩陣Vn×m，中心化處理樣本矩陣

V=A-repmat(mean(A，2)，1，m)

(3)

3)為形成方差矩陣Cov，需求解其協(xié)方差，屬于差異性特征之間

Cov=(VVT)/(size(X，2)-1)

(4)

4)求解Cov的特征值和特征向量。

5)選擇并確定變換基：

為構(gòu)成特征向量矩陣Wn×k，選取最大的特征值的特征向量完成[9]，兩者的數(shù)量均為k。

6)降維結(jié)果求解，其公式為

Y=WTV

(5)

7)輸出結(jié)果

算法中f決定k值，f的計(jì)算公式為

(6)

式中：λi表示特征根。

2.3 并行化增量式高維數(shù)據(jù)聚類優(yōu)化

2.3.1 關(guān)聯(lián)數(shù)據(jù)檢測

檢測輸出Yk×m，獲取數(shù)據(jù)之間關(guān)聯(lián)性。設(shè)γBLCMV表示Yk×m的監(jiān)測統(tǒng)計(jì)特征值，其計(jì)算公式為

(7)

式中，檢索的模糊域用at(θ)表示；R表示優(yōu)化目標(biāo)函數(shù)；φ表示分塊匹配集，且φ=[φ1，φ2，…，φg]，其式(8)描述

(8)

(9)

式中：ASM表示加權(quán)幅值，且為輸出；ρSM表示自適應(yīng)調(diào)節(jié)參數(shù)；DSM表示約束條件，且為不等式；H表示特征分布系數(shù)。

設(shè)定時(shí)間窗口為Tφ，其屬于模糊類中心，計(jì)算公式為

Tφ=set(Tf/Nφ)

(10)

式中：Tf>φjTφ；Nφ表示φ的數(shù)量。

Yk×m的全局性最優(yōu)返回結(jié)果為

pi(l+1)=min(pmax，Ωi(l+1))

(11)

將式(11)結(jié)果輸入至緩沖器中，獲取鏈路增益值hi，且hi≠hmin(l)、Ωi(l)>0，基于此完成Yk×m中關(guān)聯(lián)數(shù)據(jù)檢測。

2.3.2 改進(jìn)spark融合聚類

為實(shí)現(xiàn)高維數(shù)據(jù)的增量式聚類，采用spark融合聚類方法[10]對提取的特征向量進(jìn)行并行聚類優(yōu)化，且在高維相空間中完成，獲取高維數(shù)據(jù)功率譜密度，且屬于傳輸信道，其計(jì)算公式為

(12)

設(shè)pi(l+1)=0，描述高維數(shù)據(jù)的輸出斜度和峰度，兩者的計(jì)算公式依次為

Sx=E[x3(t)]

(13)

Kx=E[x4(t)]-3E2[x2(t)]

(14)

并行化聚類的誤差計(jì)算公式為

(15)

式中：μ表示特征分量；d(n)表示期望距離，ω表示間距。

為獲取高維數(shù)據(jù)的均衡調(diào)度尺度特征，需提取高維數(shù)據(jù)的平均集對特征量，其屬于集對簇中[11]，并且位于信道的近場源中完成。

(16)

式中：E(i，j)表示均衡調(diào)度尺度特征；依據(jù)各個(gè)時(shí)幀A中的簇向量集ai，獲取高維數(shù)據(jù)并行化聚類的R，其計(jì)算公式為

R=ω1Ci+ω2Di+ω3Mi+ω4Ni

(17)

式中：ω表示間距，且在擾動(dòng)情況下，并屬于聚類類間；C、D分別表示頻率和尺度，兩者均屬于數(shù)據(jù)聚類過程中，且前者對應(yīng)子帶中心，后者對應(yīng)時(shí)間；M表示約束參量，且呈線性。則高維數(shù)據(jù)的spark融合[12]的高維數(shù)據(jù)增量式聚類集計(jì)算公式為

Qkc(-1)i+1det(Q′i1)))

(18)

K(xi，xj)=〈xi，xj〉

(19)

結(jié)合自適應(yīng)學(xué)習(xí)算法完成高維數(shù)據(jù)聚類中的自動(dòng)尋找，完成高維數(shù)據(jù)并行化聚類。

3 仿真測試與分析

為測試本文算法的聚類效果和性能，本文選擇兩種不同維度的數(shù)據(jù)集作為測試對象，數(shù)據(jù)集1包含樣本總數(shù)量為1799，其維度為256，類別數(shù)量為12；數(shù)據(jù)集2包含樣本總數(shù)量為400，其維度為1024，類別數(shù)量為400，測試時(shí)，測試過程中通過Visual C++完成算法編譯，并采用MATLAB仿真軟件完成測試。

為測試本文方法的高維數(shù)據(jù)的結(jié)構(gòu)重構(gòu)效果，需確定其最佳嵌入維數(shù)，測試在不同維數(shù)下，數(shù)據(jù)集的混沌重組結(jié)果，數(shù)據(jù)集1的重構(gòu)效果如圖1。

圖1 混沌重構(gòu)測試結(jié)果

根據(jù)圖1測試結(jié)果可得：嵌入維數(shù)為5時(shí)，混沌重構(gòu)分區(qū)后的數(shù)據(jù)分布存在尖峰位置，雖然整體呈現(xiàn)上下分布，但是中心線的上下兩部分存在一定不對稱現(xiàn)象；嵌入維數(shù)為7時(shí)，混沌重構(gòu)分區(qū)后的數(shù)據(jù)分布平滑、圓滿，不存在尖峰現(xiàn)象，并且中心線上下部分呈現(xiàn)較好的對稱分布；嵌入維數(shù)為9時(shí)，混沌重構(gòu)分區(qū)后的數(shù)據(jù)分布則出現(xiàn)較為明顯波動(dòng)，則波動(dòng)狀態(tài)不規(guī)則，導(dǎo)致縱向中心線和橫向中心線呈現(xiàn)差異變化。該結(jié)果表明，當(dāng)嵌入維數(shù)為7時(shí)，可獲取最佳的數(shù)據(jù)混沌重構(gòu)效果。

為測試本方法對高維數(shù)據(jù)的降維效果，采用本文方法對兩類數(shù)據(jù)集進(jìn)行降維處理，測試在不同貢獻(xiàn)率取值下，兩類數(shù)據(jù)集降維前后的對比結(jié)果，見表1。

表1 兩類數(shù)據(jù)集的降維測試結(jié)果

分析表1測試結(jié)果可知：本文算法具備良好的數(shù)據(jù)降維效果，針對維數(shù)相對較低和相對較高的兩種數(shù)據(jù)集的降維性能相差較小，不存在維數(shù)越高則降維效果較差現(xiàn)象。當(dāng)貢獻(xiàn)率達(dá)到1.0時(shí)，兩種數(shù)據(jù)集的維度分別下降120和118個(gè)維度，有效實(shí)現(xiàn)數(shù)據(jù)集的維度下降，以此降低存儲(chǔ)空間的占用率。

為測試本文算法的聚類效果，采用歸一化互信息和蘭德指數(shù)作為評價(jià)指標(biāo)，指標(biāo)的計(jì)算公式分別為：

(20)

(21)

式中：數(shù)據(jù)集的樣本總數(shù)量用N表示；第i類的樣本數(shù)量用Ai表示，且屬于本文方法聚類后；數(shù)據(jù)集中的真實(shí)數(shù)量用Bi表示，且屬于第j類樣本；ζ表示未知類別；以實(shí)際的樣本類別信息為參照，聚類后與其類別相同的樣本數(shù)量用a表示、不相同的數(shù)量用b表示。兩個(gè)評價(jià)指標(biāo)的取值范圍為[0，1]，本文方法的聚類效果隨著該取值的增加而越佳、該取值的降低而變差。

所提方法下兩類數(shù)據(jù)集的聚類的效果，結(jié)果見圖2、圖3。

圖2 歸一化互信息測試結(jié)果

依據(jù)圖2測試結(jié)果可知：當(dāng)樣本類別數(shù)量較少時(shí)，在不同的增益比例下，NMI呈現(xiàn)差異性波動(dòng)變化，但是當(dāng)期比例達(dá)到0.7時(shí)，NMI的結(jié)果較低，隨著樣本類別數(shù)量的增加，呈現(xiàn)顯著的下降趨勢；當(dāng)樣本中類別數(shù)量較多時(shí)，隨著樣本數(shù)量的增加，不同增益比例下的NMI值均呈現(xiàn)下降趨勢，但是，比例為0.1、0.3、0.5時(shí)，NMI的結(jié)果均在0.58以上，當(dāng)比例為0.7時(shí)，NMI的結(jié)果均低于0.55，并且樣本數(shù)量為12類時(shí)NMI的結(jié)果僅為0.15。

圖3 蘭德指數(shù)測試結(jié)果

依據(jù)圖3測試結(jié)果可知：增益比例為0.1、0.3、0.5時(shí)，數(shù)據(jù)集1和數(shù)據(jù)集2的RI結(jié)果均在0.60以上，且波動(dòng)范圍較小，當(dāng)增益比例為0.7時(shí)，數(shù)據(jù)集1的RI值，隨著樣本類別數(shù)量的增加，在0.3～0.45的范圍內(nèi)波動(dòng)；數(shù)據(jù)集2的RI值隨著樣本類別數(shù)量的增加，則呈現(xiàn)緩慢下降趨勢。

綜合圖2和圖3結(jié)果得出：增益比例對于NMI的結(jié)果存在直接影響，因此，算法在運(yùn)算過程中，比例值應(yīng)低于0.5，同時(shí)，在合理的比例取值下，樣本數(shù)量的增加，對于NMI的結(jié)果影響較小，可忽略不計(jì)。因此，在合理的增益比例下，本文算法的聚類效果良好，可完成高維數(shù)據(jù)的有效、可靠聚類。

4 結(jié)論

由于高維數(shù)據(jù)的利用率以及處理效果不理想，因此，本文以高維數(shù)據(jù)增量式聚類為目的，研究基于改進(jìn)spark技術(shù)的高維數(shù)據(jù)增量式聚類算法。通過高維數(shù)據(jù)結(jié)構(gòu)重構(gòu)、降維處理，并通過spark技術(shù)完成數(shù)據(jù)的并行聚類優(yōu)化，實(shí)現(xiàn)高維數(shù)據(jù)的高效處理，獲取有效數(shù)據(jù)，實(shí)現(xiàn)高維數(shù)據(jù)的增量式聚類。通過仿真測試得出：本文算法在最佳的嵌入維數(shù)下，可完成最佳的數(shù)據(jù)結(jié)構(gòu)重構(gòu)結(jié)果，并且能夠降低高維數(shù)據(jù)的維度，聚類效果良好。

在日后的研究中，將以進(jìn)一步提升算法的性能為主，對高維數(shù)據(jù)中的近似特征展開研究，分析是否可通過近似特征的結(jié)合，優(yōu)化算法的聚類性能。