王 梅，張四平

(湖南信息職業(yè)技術(shù)學(xué)院 計算機工程學(xué)院，湖南 長沙 410200)

?

基于SOA的改進型Apriori算法

王 梅，張四平

(湖南信息職業(yè)技術(shù)學(xué)院 計算機工程學(xué)院，湖南 長沙 410200)

針對傳統(tǒng)的粗糙集挖掘方法易受到頻繁項集中干擾項的影響，導(dǎo)致挖掘精度低的問題，提出基于面向服務(wù)構(gòu)架和時頻特征提取的頻繁項集關(guān)聯(lián)規(guī)則挖掘Apriori算法.通過頻繁模式樹下的面向服務(wù)構(gòu)架SOA模型，建立頻繁項挖掘的頻繁模式樹，并進行信息融合預(yù)處理，構(gòu)建頻繁項集關(guān)聯(lián)規(guī)則概念格，并提取數(shù)據(jù)時頻特征，實現(xiàn)Apriori算法改進.仿真結(jié)果表明，采用改進Apriori算法進行關(guān)聯(lián)規(guī)則的頻繁項集挖掘時，數(shù)據(jù)特征提取精度較高，所需時間少，挖掘精度及指標(biāo)性能均優(yōu)于傳統(tǒng)方法．

面向服務(wù)構(gòu)架；關(guān)聯(lián)規(guī)則；頻繁項集；Apriori算法

0 引 言

Apriori算法是一種挖掘關(guān)聯(lián)規(guī)則的頻繁項集算法，采用面向服務(wù)構(gòu)架(Service-Oriented Architecture，SOA)體系作為信息加工的概念格，用計算機模式識別方法生成頻繁項集，使用XML Schema實現(xiàn)頻繁項集挖掘.隨著Apriori 算法的改進，被廣泛應(yīng)用在并行計算機模式識別、機械故障診斷、決策制定和審計跟蹤等領(lǐng)域，經(jīng)典Apriori挖掘算法采用多處理器進行關(guān)聯(lián)規(guī)則特征檢測，結(jié)合面向服務(wù)架構(gòu)SOA技術(shù)尋找頻繁項集[1-3]，獲得用戶行為特征信息.面向服務(wù)構(gòu)架SOA技術(shù)是采用分布式傳感器節(jié)點進行數(shù)據(jù)感知和通信，根據(jù)需求通過網(wǎng)絡(luò)將應(yīng)用程序的耦合服務(wù)構(gòu)架進行特征配準(zhǔn)和分布式部署[4]，實現(xiàn)更迅速、更可靠的數(shù)據(jù)傳輸.在面向服務(wù)構(gòu)架網(wǎng)絡(luò)模型中，通過頻繁項集關(guān)聯(lián)規(guī)則挖掘，可提高信息提取和數(shù)據(jù)分析能力，因此，研究基于面向服務(wù)構(gòu)架SOA的Apriori算法具有重要意義[5]．文獻(xiàn)[6]提出基于關(guān)聯(lián)規(guī)則的頻繁項集挖掘算法，采用證據(jù)理論進行關(guān)聯(lián)規(guī)則的特征融合和線性特征分解，通過后綴項表的構(gòu)建，保留面向服務(wù)構(gòu)架頻繁項集的完整信息，提高數(shù)據(jù)挖掘精度，但是該算法在進行關(guān)聯(lián)規(guī)則特征空間重構(gòu)中受到噪聲干擾導(dǎo)致挖掘精度低，且計算開銷較大，實時性不好；文獻(xiàn)[7]提出基于關(guān)聯(lián)規(guī)則置信度約束控制的Apriori算法，在支持度大于給定最小支持度下，進行閾值模型的構(gòu)建，通過判決函數(shù)實現(xiàn)對頻繁項集規(guī)則提取與概念格構(gòu)建，提高關(guān)聯(lián)規(guī)則的目標(biāo)匹配性能，數(shù)據(jù)挖掘細(xì)節(jié)特征分解性能較高，置信度區(qū)間內(nèi)目標(biāo)信息挖掘特征較為明顯，但是該算法隨著干擾數(shù)據(jù)的增大，挖掘環(huán)境的信噪比降低，導(dǎo)致頻繁項集挖掘的可靠性和收斂性不好；文獻(xiàn)[8]提出基于FP-Growth的粗糙集挖掘方法，該算法會隨著頻繁項集中干擾項的增多，關(guān)聯(lián)規(guī)則挖掘精度下降，不適合大范圍使用．

因此，提出基于面向服務(wù)構(gòu)架和時頻特征提取的改進Apriori算法，首先給出頻繁模式樹下的面向服務(wù)構(gòu)架模型，并進行頻繁項集關(guān)聯(lián)規(guī)則概念格構(gòu)建和數(shù)據(jù)特征分析，采用時頻特征提取方法進行數(shù)據(jù)特征提取及Apriori算法的改進，最后通過仿真實驗進行性能測試.

1 頻繁模式樹下的面向服務(wù)構(gòu)架模型及預(yù)處理

1.1 SOA模型

為了實現(xiàn)對關(guān)聯(lián)規(guī)則頻繁項集的挖掘，本文在面向服務(wù)構(gòu)架SOA模型下進行Apriori算法的改進設(shè)計，結(jié)合候選挖掘頻繁項集的時頻特征，進行頻繁模式樹的先驗概率密度信息提取和數(shù)據(jù)挖掘，假設(shè)X和G為屬性集合，M為D和I之間的三元組，頻繁項集產(chǎn)生格結(jié)構(gòu)代替每個結(jié)點的特征參量β，進行頻繁模式樹構(gòu)建．

定義1 (頻繁模式樹)定義概念格上的規(guī)則子集在時頻空間上1×k維最小支持度minsup向量為D，在關(guān)聯(lián)規(guī)則提取格結(jié)構(gòu)下，通過SOA構(gòu)架，進行數(shù)據(jù)項x的相空間重構(gòu)，在重構(gòu)的相空間中，構(gòu)建頻繁模式樹Vx，其中，重構(gòu)的特征軌跡滿足V(1，i)=p，且頻繁模式樹的分岔樹A，B同時滿足以下兩個條件：

(1)

(2)

根據(jù)上述約束條件，構(gòu)建頻繁模式樹下面向服務(wù)構(gòu)架SOA模型，抽取高密度區(qū)域置信度因素的條件概率P(A|B)，得到置信度為

(3)

由上述定義，可以得到m維屬性分類下，頻繁結(jié)點屬性值的集合階數(shù)為p,全部規(guī)則為ai(t),則全部規(guī)則屬性約束下，頻繁項挖掘的干擾項n(t)可表示為

(4)

在頻繁項挖掘的樣本事務(wù)數(shù)據(jù)庫D中，通過候選概念格結(jié)點得到事件d的先驗概率P(d)，掃描分枝概念樹的候選特征參量a1(t)和a2(t)由下式確定：

(5)

依次類推，當(dāng)m(t)與θ(t)互質(zhì)，相關(guān)結(jié)點的最小計數(shù)值滿足N≤Mm(t)θ(t)，且M>4τ，頻繁項挖掘的相位信息為θ1，θ2，...，θq，此時頻繁模式樹下的面向服務(wù)構(gòu)架SOA模型屬性集為S={n1}，所有候選結(jié)點組合滿足，表明對任意1≤i≤L時間復(fù)雜度ni(1≤i≤L)存在唯一解[9-15]．

定義2 候選概念格設(shè)置.給定頻繁模式樹下，面向服務(wù)構(gòu)架SOA模型的冗余規(guī)則S=(U，A，V，f)，其中，U為冗余規(guī)則論域，A為相關(guān)冗余結(jié)點的屬性集，設(shè)Θ為頻繁概念格規(guī)則提取函數(shù)m:2Θ→[0，1]，保留項集對應(yīng)的父結(jié)點滿足下列條件：

(6)

(7)

(8)

(9)

在C4.5決策樹模型下，進行頻繁項目列表的減枝處理，剔除相關(guān)冗余結(jié)點，此時滿足時間復(fù)雜度，U在等價關(guān)系C下可劃分為E=U/RC={Ei|i=1，2，…，n}，頻繁概念格規(guī)則提取的事務(wù)TID為S=(U，C∪D，V，f)，其中，C和D分別為條件屬性和決策屬性.

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

根據(jù)F1構(gòu)造頻繁項挖掘的頻繁模式樹(FP-tree)，設(shè)置FP-tree上的結(jié)點計數(shù)為count，任意分枝Ti(i=1，2…，m，m為分枝個數(shù))的子集為Ni(Ni≥1)，相關(guān)結(jié)點最小計數(shù)分枝長度的序貫采樣為O(Ni)，頻繁項目列表簇間數(shù)據(jù)傳輸?shù)淖疃搪窂酵ㄟ^調(diào)節(jié)因子λ(k)進行自適應(yīng)修正，在重建的特征子空間中得到頻繁項目列表調(diào)節(jié)因子為

(10)

其中，c(k)=tr[N(k)]/tr[C(k)]，表示頻繁項集關(guān)聯(lián)規(guī)則解析特征模型，滿足

(11)

其中

(12)

(13)

(14)

其中，Bi(k)為量化初始狀態(tài)x(0)的均值Dij(k)為量化測量值方差，當(dāng)w(k)和ui(k)，i=1，2，…，N相對獨立時，頻繁項集關(guān)聯(lián)規(guī)則到達(dá)融合中心的矢量特征為xiri(x).則得到頻繁項集關(guān)聯(lián)規(guī)則挖掘的信息融合動態(tài)方程為

(15)

式中，rj(x)為融合誤差，xi為幅值.采用后綴項表構(gòu)造map，進行數(shù)據(jù)融合模型的構(gòu)建，提取一組頻繁項集，確定在某一時刻的頻率分量，得到數(shù)據(jù)傳送量為

(16)

其中，后綴項表函數(shù)g(Ij)定義為

(17)

綜上所述可知，進行后綴項表構(gòu)造及信息融合預(yù)處理，為實現(xiàn)基于SOA的關(guān)聯(lián)規(guī)則頻繁項集挖掘提供準(zhǔn)確的數(shù)據(jù)基礎(chǔ)．

2 頻繁項集挖掘算法

2.1 頻繁項集時頻特征提取

在上述進行數(shù)據(jù)結(jié)構(gòu)分析和信息融合預(yù)處理的基礎(chǔ)上，進行算法改進設(shè)計，通過研究基于面向服務(wù)構(gòu)架SOA的Apriori算法，實現(xiàn)頻繁項集關(guān)聯(lián)規(guī)則挖掘，提高信息提取和數(shù)據(jù)分析能力.傳統(tǒng)方法采用基于FP-Growth的粗糙集挖掘方法，當(dāng)頻繁項集中干擾項的增加時，挖掘精度會降低[16-20].因此，提出基于面向服務(wù)構(gòu)架和時頻特征提取的頻繁項集關(guān)聯(lián)規(guī)則挖掘Apriori算法.根據(jù)時頻分辨率正則訓(xùn)練遷移法則，建立頻繁項集關(guān)聯(lián)規(guī)則數(shù)據(jù)集局域化矢量模型。假設(shè)當(dāng)數(shù)據(jù)集局域化先驗數(shù)據(jù)xm+1的決策屬性取值為dm+1=d1，引入相關(guān)系數(shù)法進行虛假分量識別，由此計算出粗糙集虛假分量為

(18)

(19)

若時頻特征提取過程是一個對規(guī)則項進行局部正交分解的過程，則通過特征空間重構(gòu)，得到基于SOA的關(guān)聯(lián)規(guī)則頻繁項集挖掘時的時頻特征，即

(20)

(21)

其中，虛假分量L與原規(guī)則項頻繁集T的相關(guān)系數(shù)為

(22)

在此基礎(chǔ)上，采用固有模態(tài)函數(shù)分解變換，對關(guān)聯(lián)規(guī)則頻繁項集挖掘目標(biāo)函數(shù)進行求導(dǎo)，得到優(yōu)化頻繁項集挖掘的目標(biāo)函數(shù)滿足

(23)

根據(jù)上述時頻特征提取結(jié)果可知，虛假分量L與原頻繁項集T的相關(guān)性很小，采用數(shù)據(jù)結(jié)構(gòu)子空間進行重建，結(jié)合時頻特征提取結(jié)果，能較好地實現(xiàn)Apriori算法改進．

2.2 頻繁項集關(guān)聯(lián)規(guī)則挖掘Apriori算法

假設(shè)，頻繁項集關(guān)聯(lián)規(guī)則的訓(xùn)練集為{xi，yi}，分解得到IMF分量線性函數(shù)為

(24)

其中：w為各分量的權(quán)值向量；b為頻繁項集關(guān)聯(lián)規(guī)則挖掘的偏置量.將ei與設(shè)定門限e進行比較，得到閉頻繁項挖掘?qū)傩訶的增益函數(shù)，且滿足約束優(yōu)化問題

(25)

式中，C為基核函數(shù)；wi為粗糙集支持度.將上述約束優(yōu)化問題轉(zhuǎn)化為計算最小支持度問題，得到基于時頻特征提取的閉頻繁項挖掘一致性集成模型：

(26)

上式為一個Lagrange函數(shù)；αi為反饋均衡串?dāng)_抑制算子.基于線性均衡模型進行數(shù)據(jù)挖掘傳輸隨機序列迭代，迭代函數(shù)為

(27)

其中

(28)

當(dāng)數(shù)據(jù)碼元速率一定的情況下，用擴展后的序列去調(diào)制載波，在迭代步長足夠的情況下，采用判決反饋均衡實現(xiàn)時間窗口重排，得到頻繁項集關(guān)聯(lián)規(guī)則挖掘的傳遞函數(shù)為

(29)

(30)

沿著中心路由遍歷每條事務(wù)模式路由T，得到Apriori算法的特征空間協(xié)方差矩陣為

(31)

在m維屬性分類中構(gòu)造閉頻繁模式的鄰居簇頭，得到特征挖掘的相關(guān)性函數(shù)滿足為

(32)

3 實驗分析與性能測試

為了測試改進Apriori算法的性能，進行仿真實驗對比分析，實驗建立在面向服務(wù)構(gòu)架SOA的Hadoop平臺上，硬件環(huán)境為：CPU Inter Pentium 4，內(nèi)存為2G.實驗數(shù)據(jù)集采用breast cancer關(guān)聯(lián)規(guī)則閉頻繁項數(shù)據(jù)集，頻繁項集關(guān)聯(lián)規(guī)則的采樣樣本時間間隔為0.25 s，時長T=0.1 s，采樣點數(shù)為100.采用時頻特征提取方法合成數(shù)據(jù)集testdata(DC15000TB8000RT100)，得到測試數(shù)據(jù)集合.根據(jù)上述仿真環(huán)境和參數(shù)設(shè)定，進行仿真實驗分析.首先進行數(shù)據(jù)信息采樣，構(gòu)造頻繁項挖掘的FP-tree，得到原始的關(guān)聯(lián)規(guī)則頻繁項集特征分布，如圖1所示．

圖 1 關(guān)聯(lián)規(guī)則頻繁項集特征分布 圖 2 兩種算法下閉頻繁項數(shù)據(jù)集 的Apriori分枝結(jié)果Fig.1 Characteristics of frequent itemsets distributed association rules Fig.2 Closed frequent items under two kinds of algorithm Apriori branch of data sets

以上述采集關(guān)聯(lián)規(guī)則頻繁項集為測試對象，進行Apriori分離處理，分別采用本文方法和傳統(tǒng)基于關(guān)聯(lián)規(guī)則置信度約束控制的Apriori方法，得到對閉頻繁項數(shù)據(jù)集的Apriori分離結(jié)果，如圖2所示．

圖 3 不同算法的挖掘時間對比Fig.3 Different algorithms of mining time

從圖2可見，采用本文方法進行關(guān)聯(lián)規(guī)則頻繁項集挖掘，相比傳統(tǒng)方法，對數(shù)據(jù)的分簇挖掘性能較好，受到的干擾較小，性能較高.為了定量對比算法性能，分別采用本文方法(PFP-P)和傳統(tǒng)方法(文獻(xiàn)[4]給出的PFP算法，文獻(xiàn)[8]對文獻(xiàn)[4]改進的PFP-C算法)進行對比，以挖掘時間為測試指標(biāo)，得到仿真結(jié)果，如圖3所示．

從圖3可見，采用本文改進的Apriori算法進行關(guān)聯(lián)規(guī)則的頻繁項集挖掘，消耗時間最少，挖掘加速比較高，相反，PFP算法及PFP-C算法的挖掘加速比和挖掘時間均較差，性能低于改進方法，由此說明，改進方法性能較好，具有一定的優(yōu)勢．

4 結(jié)束語

針對傳統(tǒng)Apriori算法挖掘效率低，誤差大的問題,提出基于面向服務(wù)構(gòu)架和時頻特征提取的頻繁項集關(guān)聯(lián)規(guī)則挖掘Apriori算法，通過頻繁模式樹下的面向服務(wù)構(gòu)架SOA模型，建立頻繁項挖掘的FP-tree，并進行信息融合預(yù)處理，構(gòu)建頻繁項集關(guān)聯(lián)規(guī)則概念格和數(shù)據(jù)時頻特征提取，實現(xiàn)Apriori算法改進.研究結(jié)果表明，采用改進方法時其挖掘性能較好，耗時等測試指標(biāo)均優(yōu)于傳統(tǒng)方法，展示了較好的應(yīng)用價值．

[1] 尚朝軒，王品，韓壯志，等. 基于類決策樹分類的特征層融合識別算法[J]. 控制與決策，2016，31(6):1009-1014．

SHANG Chaoxuan，WANG Pin，HAN Zhuangzhi，et al. Feature-level fusion recognition algorithm based on analogy decision tree classification[J]. Control and Decision，2016，31(6):1009-1014．

[2] IHSNA A Kareem，MEHDI G Duaimi. Improved accuracy for decision tree algorithm based on unsupervised discretization[J]. International Journal of Computer Science and Mobile Computing，2014，3(6):176-183．

[3] PEI Jian，HAN Jiawei，MAO Runying. CLOSET：An efficient algorithm for mining frequent closed itemsets[J]. Acm Sigmod Workshop on Research Issues in Data Mining and Knowledge Discovery，2000，4(2):21-30．

[4] CHONG F T，HECK M J R，RANGANATHAN P，et al. Data center energy efficiency：improving energy efficiency in data centers beyond technology scaling[J]. IEEE Design & Test，2014，31(1):93-104．

[5] 郎振紅. 基于云計算自主學(xué)習(xí)平臺的設(shè)計[J]. 電子設(shè)計工程，2016，24(1):35-39．

LANG Zhenhong. A design of self-study’s platform system based on cloud computing[J]. Electronic Design Engineering,2016，24(1):35-39．

[6] MORENO Salinas D，PASCOAL A M，ARANDA J. Optimal sensor placement for multiple target positioning with range-only measurements in two-dimensional scenarios[J]. Sensors，2013，13(8):10674-10710．

[7] LEE W，BANG H，LEEGHIM H. Cooperative localization between small UAVs using a combination of heterogeneous sensors[J]. Aerospace Science and Technology，2013，27(1):105-111．

[8] KARLSSON J，ROWE W，XU L，et al. Fast missing-data IAA with application to notched spectrum SAR[J]. IEEE Transactions on Aerospace Electronic Systems，2014，50(2):959-971．

[9] PARK H R，LI Jie. Sparse covariance-based high resolution time delay estimation for spread spectrum signals[J]. Electronics Letters，2015，51(2):155-157．

[10] WANG Lin，ZHANG Fa，ARJONA Aroca J，et al. Green DCN：A general framework for achieving energy efficiency in data center networks[J]. IEEE Journal on Selected Areas in Communications，2014，32(1):4-15．

[11] 虞飛，陶建武，陳誠，等.基于稀疏協(xié)方差矩陣迭代的單快拍氣流速度估計算法[J].電子與信息學(xué)報，2015，37(3):574-579．

YU Fei,TAO Jianwu，CHEN Cheng,et al.Single snapshot airspeed estimation based on sparse covariance matrix iteration[J].Journal of Electronics & Information Technology,2015，37(3):574-579．

[12] 周鐳，單鋒，劉鵬，等. 基于供應(yīng)鏈的企業(yè)信息化評價模型的建立[J]. 西安工程大學(xué)學(xué)報，2015，29(6):772-779．

ZHOU Lei，SHAN Feng，LIU Peng，et al. The establishment of the enterprise informatization evaluation model based on supply chain[J]. Journal of Xi’an Polytechnic University，2015，29(6):772-779．

[13] KALEVA J，TOLLI A，JUNTTI M. Weighted sum rate maximization for interfering broadcast channel via successive convex approximation[C]//IEEE Global Communications Conference， Anaheim，2012：3838-3843．

[14] LIU Heng，DING Zhiguo ，F(xiàn)AN Pingzhi，et al. Precoding design for interference suppression in multi-cell multi-user networks[J]. IET Communications，2014，8(9):1534-1540．

[15] RATHEESH M，DAVID M J. System-level performance of interference alignment[J]. IEEE Transactions on Wireless Communications，2015，14(2):1060-1070．

[16] GENG Zhe，DENG Hai，HIMED B. Adaptive radar beamforming for interference mitigation in radar-wireless spectrum sharing[J]. IEEE Signal Processing Letters，2015，22(4):484-488．

[17] YANG Yunchuan，SUN Cong，ZHAO Hui，et al. Algorithms for secrecy guarantee with null space beamforming in two-way relay networks[J]. IEEE Transactions on Signal Processing，2014，62(8):2111-2126．

[18] 吳鴻華，穆勇，屈忠鋒，等. 基于面板數(shù)據(jù)的接近性和相似性關(guān)聯(lián)度模型[J]. 控制與決策，2016，31(3):555-558．

WU Honghua，MU Yong，QU Zhongfeng，et al. Similarity and nearness relational degree based on panel data[J]. Control and Decision，2016，31(3):555-558．

[19] 閻芳，李元章，張全新，等. 基于對象的OpenXML復(fù)合文件去重方法研究[J]. 計算機研究與發(fā)展，2015，52(7):1546-1557

YAN Fang，LI Yuanzhang，ZHANG Quanxin，et al. Object based data de-duplication method for open XML compound files[J]. Journal of Computer Research and Development，2015，52(7):1546-1557．

編輯、校對：師 瑯

Improved Apriori algorithm based on SOA

WANG Mei， ZHANG Siping

(School of Computer Engineering， Hunan College of Information， Changsha 410200， China)

In the view of the traditional method of rough set mining method easily affected by frequent items focused distractions， leading to the problem of low digging precision, based on service oriented architecture and time-frequency feature extraction,Apriori algorithm for mining association rules is proposed.Through frequent pattern tree of service-oriented architecture SOA model， the FP-tree of frequent items mining is set up， information fusion is preprocessed， concept lattice and association rule are built and data frequent item sets time-frequency feature is extracted， achieving improved Apriori algorithm. The simulation results show that with the improved algorithm the data feature extraction has high precision， less time required; mining precision and performance indicators are better than those of traditional methods．

service oriented architecture; association rule; frequent item set; apriori algorithm

1674-649X(2016)04-0487-07

10.13338/j.issn.1674-649x.2016.04.014

2016-03-16

湖南省教育廳高校研究基金資助項目(15C0980)

王梅(1978—)，女，湖南省長沙市人，湖南信息技術(shù)學(xué)院講師，研究方向為大數(shù)據(jù)、數(shù)據(jù)處理.

E-mail:siping_zhang@sina.com

王梅，張四平.基于SOA的改進型Apriori算法[J].西安工程大學(xué)學(xué)報，2016，30(4)：487-493.

WANGMei，ZHANGSiping.ImprovedApriorialgorithmbasedonSOA[J].JournalofXi′anPolytechnicUniversity,2016，30(4)：487-493.

TP

A