基于頻繁項集的多源異構數(shù)據(jù)并行聚類算法

趙春霞， 趙營穎， 宋學坤

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

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

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

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

1 多源異構數(shù)據(jù)頻繁項集挖掘

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

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

(1)

式中|D|為D中的事務個數(shù)。

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

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

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

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

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

(2)

(3)

式中：Cmin(X?Y)為最小支持度下的關聯(lián)規(guī)則；q為記錄的數(shù)據(jù)條數(shù)。

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

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

2 本文算法

2.1 構建相異度數(shù)據(jù)結構矩陣

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

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

Ci∪Cj=○/,i≠j

，

(4)

Ci∪Cj=V

。

(5)

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

(6)

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

2.2 提取多源異構數(shù)據(jù)特征

通過構建的相異度結構矩陣，提取統(tǒng)計序列的特征量，實現(xiàn)多源異構數(shù)據(jù)并行聚類。多源異構數(shù)據(jù)的數(shù)據(jù)庫檢測統(tǒng)計特征值矩陣Φ為

Φ=δ(a,J)-1

，

(7)

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

融合數(shù)據(jù)庫內(nèi)多源異構復合，計算聚類中心，從而獲取多源異構數(shù)據(jù)的特征分布域敘述Ism，

(8)

式中：Asm為多源異構數(shù)據(jù)的并行規(guī)劃聚類加權輸出幅值；ρsm為多源異構數(shù)據(jù)的并行規(guī)劃聚類自適應調(diào)節(jié)參數(shù)；Dsm為不等式的約束條件。

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

T=Ism(T1/T2)

，

(9)

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

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

2.3 融合并行聚類算法

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

(10)

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

利用時間反轉(zhuǎn)處理以及高維相空間的重構方法，實現(xiàn)多源異構數(shù)據(jù)時空結構加權處理，表達式為

(11)

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

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

(12)

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

多源異構數(shù)據(jù)融合聚類集為

(13)

式中w為最大聚類數(shù)。

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

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

，

(14)

式中γ為采集因子。

通過上式搜索到數(shù)據(jù)聚類中心，實現(xiàn)多源異構數(shù)據(jù)并行聚類。

3 實驗仿真分析

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

3.1 多源異構數(shù)據(jù)并行聚類處理精度

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

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

3.2 多源異構數(shù)據(jù)并行聚類處理時間

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

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

4 結語

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