趙春霞， 趙營(yíng)穎， 宋學(xué)坤

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

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

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

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

1 多源異構(gòu)數(shù)據(jù)頻繁項(xiàng)集挖掘

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

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

(1)

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

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

當(dāng)頻繁項(xiàng)集生成時(shí)，對(duì)頻繁項(xiàng)集進(jìn)行候選剪枝，具體方法如下。

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

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

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

(2)

(3)

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

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

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

2 本文算法

2.1 構(gòu)建相異度數(shù)據(jù)結(jié)構(gòu)矩陣

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

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

Ci∪Cj=○/,i≠j

，

(4)

Ci∪Cj=V

。

(5)

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

(6)

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

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

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

Φ=δ(a,J)-1

，

(7)

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

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

(8)

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

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

T=Ism(T1/T2)

，

(9)

式中：T1為事件時(shí)間；T2為處理時(shí)間。

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

2.3 融合并行聚類算法

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

(10)

式中：σ為信號(hào)序列；h為采樣頻率；G為互功率譜估計(jì)；N為時(shí)間帶寬積。

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

(11)

式中：e(n)為多源異構(gòu)數(shù)據(jù)時(shí)空結(jié)構(gòu)加權(quán)處理結(jié)果；y(n)為空間樣點(diǎn)個(gè)數(shù)；x(n)為回歸參數(shù)。

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

(12)

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

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

(13)

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

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

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

，

(14)

式中γ為采集因子。

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

3 實(shí)驗(yàn)仿真分析

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

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

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

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

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

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

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

4 結(jié)語

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