基于頻繁項集的多源異構數據并行聚類算法

趙春霞， 趙營穎， 宋學坤

(河南中醫藥大學信息技術學院， 河南鄭州 450046)

網絡技術的不斷發展促使多源異構數據迅速生成，挖掘處理復雜的多源異構數據，能夠有效獲取數據潛在信息和規律[1]。聚類分析屬于機器學習、數據挖掘以及統計學等領域的交叉性學科，不僅能夠起到有效演示的作用，即確定事物的分類標準或類別準則，而且聚類的作用就是歸納，不需要確定分類的標準、分析數據對象[2]，因此對于有效地挖掘和分析復雜的多源異構數據具有重要意義。

相關領域學者對數據并行聚類進行了研究。 文獻[3]中提出基于MapReduce并行化計算框架的大數據聚類算法(簡稱文獻[3]算法)。 采用Canopy算法對聚類中心進行初始化劃分， 獲取粗精度聚類中心點， 利用基于MapReduce框架的并行化計算方法， 細化聚類或合并Canopy中心， 實現大數據準確聚類分析。 該算法的并行聚類處理精度較高， 但并行計算效率較低。 文獻[4]中提出基于Spark框架優化的大規模數據集譜聚類并行算法(簡稱文獻[4]算法)。 采用單向循環迭代， 對相似矩陣構建進行優化， 利用位置變換和標量乘法替換， 對Laplacian矩陣構建與正規化進行優化， 運用近似特征向量進一步計算， 實現大規模數據集譜聚類并行分析。 該算法能夠有效提高運行效率， 但存在聚類處理精度低的問題。

本文中提出一種基于頻繁項集的多源異構數據并行聚類算法(簡稱本文算法)，采用極大元法挖掘最大頻繁項集，構建相異度數據結構矩陣，利用時間窗口和頻繁項集挖掘出多源異構數據特征，提高多源異構數據并行聚類處理精度。運用時間反轉處理以及高維相空間重構方法，實現多源異構數據并行聚類，從而縮短多源異構數據并行聚類處理時間。

1 多源異構數據頻繁項集挖掘

假設事務數據庫D={d1,d2, …,dn, …}(n為正整數)的項目全集為非空有限集I，其中事務dn為I的子集，即dn?I，由此可知，dn存在線程控制標識符(TID)，主要用來表示事務編號。I的任意子集X稱為D的項集(itemset)。若dn?X，則稱事務dn屬于項集X。

D的項集X出現的頻數記為Sc(X)，為了簡化計算，采用支持度S(X)表示項集X出現的頻率，則有

(1)

式中|D|為D中的事務個數。

當項集X的支持度S(X)大于用戶設置的支持度的閾值Smin(X)時， 項集X為頻繁項集； 反之， 當S(X)小于Smin(X)時，項集X為非頻繁項集[5]。

當頻繁項集生成時，對頻繁項集進行候選剪枝，具體方法如下。

在一般的關聯規則挖掘過程中，支持度的閾值Smin(X)是通過用戶或相關領域專家確定的，而最小支持度為Cmin(X)=Smin(X)|D|。利用D、Smin(X)，結合挖掘得到的頻繁項集，可以獲取全部頻繁項集。

假設X?Y為關聯規則，項集為規則前件，項集Y為規則后件，在關聯規則中，X、Y為不相交的項集，即X∩Y=○/。同時，X、Y都具有比閾值頻繁項集更大的支持度。使用置信度和支持度測量規則的興趣度，支持度用于確定數據集的頻繁度，而置信度用于確定Y包含X中的頻繁度。

利用支持度閾值以及置信度閾值滿足關聯規則的需求，那么該關聯規則定義為有趣的，即

(2)

(3)

式中：Cmin(X?Y)為最小支持度下的關聯規則；q為記錄的數據條數。

假設I的任意一個子集X都能表示為m維特征向量(χX,1,χX,2,…,χX,m)，則I的全部子集都能形成冪集格P(I)的同構位置格{0, 1}m。根據頻繁項集的性質和定義，如果X為頻繁項集，則X的任意子集都為頻繁項集，通過頻繁項集所獲取的集合可以作為I的冪集格[6]。

冪集格P(I)的極大元為最大頻繁項集，利用I全部子集所形成的冪集格P(I)和同構位置格{0, 1}m，利用類同挖掘的極大元方法，實現多源異構數據最大頻繁項集挖掘。

2 本文算法

2.1 構建相異度數據結構矩陣

通過機器學習方法對聚類分析進行觀察，不需要事先了解數據集的分布，然后結合物理或抽象的集合，計算集合的相似性進行聚類。

一個簇的實體情況是作為相似性而存在的， 因此可以得到實體之間不相似的不同的簇。 對空間內的類簇聚類情況進行測試， 由于同樣的類簇中任意2個點之間的距離小于不同類簇中2個點之間的距離， 因此聚類可以具體描述[7]如下： 在給定的數據集V={vi|i=1,2,…,n}中， 通過對象之間的類似程度劃分數據集， 簇Ci、Cj?V， 其中j=1,2,…,n，i+j=n,且滿足

Ci∪Cj=○/,i≠j

，

(4)

Ci∪Cj=V

。

(5)

相異度矩陣δ的存儲方式是通過在n個對象中有可能出現2個對象之間的相異性實現的，具體表現形式為n×n型矩陣，所有元素d(w1,w2)即為對象w1、w2之間的相異性，即

(6)

d(w1,w2)一般為非負數，當對象w1、w2十分接近時，d(w1,w2)接近于0；d(w1,w2)越大，則對象w1、w2之間的差距越大，由此獲得相異度矩陣[8]。

2.2 提取多源異構數據特征

通過構建的相異度結構矩陣，提取統計序列的特征量，實現多源異構數據并行聚類。多源異構數據的數據庫檢測統計特征值矩陣Φ為

Φ=δ(a,J)-1

，

(7)

式中：a為檢索模糊域；J為數據的分塊匹配集。

融合數據庫內多源異構復合，計算聚類中心，從而獲取多源異構數據的特征分布域敘述Ism，

(8)

式中：Asm為多源異構數據的并行規劃聚類加權輸出幅值；ρsm為多源異構數據的并行規劃聚類自適應調節參數；Dsm為不等式的約束條件。

利用平均加權的方法，通過在模糊聚類中心[9]敘述數據庫中多源異構數據時間窗口T,

T=Ism(T1/T2)

，

(9)

式中：T1為事件時間；T2為處理時間。

通過式(9)可以獲取數據庫內多源異構數據信息融合全局性的尋優返回值，把數據輸入緩沖器中，得到多源異構數據鏈路的增益值，以此完成多源異構數據特征的提取。

2.3 融合并行聚類算法

通過在高維空間內實現多源異構數據檢測，利用頻繁項集挖掘[10]的多源異構數據特征進行并行聚類，從而獲取數據庫內多源異構數據信道的傳輸功率譜密度Ω，

(10)

式中：σ為信號序列；h為采樣頻率；G為互功率譜估計；N為時間帶寬積。

利用時間反轉處理以及高維相空間的重構方法，實現多源異構數據時空結構加權處理，表達式為

(11)

式中：e(n)為多源異構數據時空結構加權處理結果；y(n)為空間樣點個數；x(n)為回歸參數。

通過在較大規模的多重輸入-多重輸出(multiple input-multiple output，MIMO)信道內，對多源異構的數據平均值特征量進行提取，獲取多源異構數據的并行聚類目標函數R，即

(12)

式中：f為聚類擾動的間距；κ為子帶中心的頻率；Wi為不同聚類中心的時間尺度；M為線性約束的參量。

多源異構數據融合聚類集為

(13)

式中w為最大聚類數。

在信息匯集的區域，只要分別滿足項集數據庫的壓縮xi以及事務數據庫的壓縮xj，就能夠假設多源異構數據并行融合聚類的中心ci,i-1≤minci+1,i，從而獲取關聯的規則集K(xi,xj)，即

K(xi,xj)=exp[(xi-xj)2/(2γ2)]

，

(14)

式中γ為采集因子。

通過上式搜索到數據聚類中心，實現多源異構數據并行聚類。

3 實驗仿真分析

為了驗證本文算法的有效性，選擇實驗環境如下：中央處理器(CPU)為Intel雙核2.7 GB，內存為4 GB，硬盤容量為500 GB，操作系統為Window10，采用Visual C++編程。

3.1 多源異構數據并行聚類處理精度

實驗所用的基礎數據集選擇某公司內部二維多源異構數據，數量為16 575條，二維多源異構數據流量的平均大小為1 474 KB，并且確保每一條多源異構數據都處于獨立的狀態。然后選擇10臺處理器，分別采用文獻[3]算法、文獻[4]算法和本文算法，以并行化聚類的方式對總體多源異構數據條數進行并行聚類處理，對比不同算法的多源異構數據條數并行聚類處理效果。具體對比結果如表1所示。由表可以看出， 本文算法的多源異構數據條數并行聚類處理結果與實際多源異構數據條數相差較小， 而文獻[3]算法和文獻[4]算法的多源異構數據條數并行聚類處理結果與實際多源異構數據條數相差較大， 由此可知， 本文算法的多源異構數據條數并行聚類處理精度較高。 由于本文算法采用極大元法挖掘最大頻繁項集， 構建相異度矩陣， 利用時間窗口和頻繁項集挖掘出多源異構數據特征， 因此提高了多源異構數據并行聚類處理精度。

表1 不同算法的多源異構數據并行聚類處理結果

3.2 多源異構數據并行聚類處理時間

由于多源異構數據并行聚類處理精度實驗中的基礎數據較少，因此很難清晰地反映不同算法在多源異構數據并行聚類處理時間的差異。將多源異構數據條數增至50 000、 100 000、 150 000、 200 000、 250 000，分別采用文獻[3]算法、文獻[4]算法和本文算法進行并行聚類處理，不同算法的處理時間結果如圖1所示。由圖可知， 隨著多源異構數據條數的增加， 不同算法的多源異構數據并行聚類處理時間呈線性增長。 當多源異構數據條數為250 000時， 文獻[3]算法的并行聚類處理時間為45 s， 文獻[4]算法的處理時間為28 s， 而本文算法的處理時間僅為18 s。 本文算法通過引入頻繁項挖掘技術， 能夠找出各數據之間的關聯規則并進行劃分， 利用平均加權方法在模糊聚類中心敘述數據庫內多源異構數據時間窗口， 因此大幅縮短了多源異構數據并行聚類處理時間。

注： 本文算法—基于頻繁項集的多源異構數據并行聚類算法； 文獻[3]算法—基于MapReduce并行化計算框架的大數據聚 類算法； 文獻[4]算法—基于Spark框架優化的大規模數據 集譜聚類并行算法。圖1 不同算法的多源異構數據并行聚類處理時間

4 結語

為了有效提高多源異構數據并行聚類處理精度， 縮短多源異構數據并行聚類處理時間， 本文中提出一種基于頻繁項集的多源異構數據并行聚類算法。 通過構建相異度矩陣， 使用時間窗口和頻繁項集挖掘， 提取多源異構數據特征， 利用時間反轉處理以及高維相空間重構方法， 高效實現多源異構數據并行聚類。 本文算法能夠有效提高多源異構數據并行聚類處理精度， 減少處理時間。 隨著科學技術的發展對聚類的準確度以及運行速度要求越來越高， 未來還要進一步研究優化多源異構數據并行聚類處理精度和時間的方法。