陳萬(wàn)敏

中國(guó)人民銀行蘭州中心支行 甘肅 蘭州 730000

引言

數(shù)據(jù)挖掘是從實(shí)際應(yīng)用產(chǎn)生的數(shù)據(jù)中，發(fā)現(xiàn)隱含在其中且人們之前未掌握的、但對(duì)社會(huì)和行業(yè)發(fā)展有價(jià)值的信息和知識(shí)的過程。通常這些數(shù)據(jù)有規(guī)模龐大、種類繁多、增長(zhǎng)速度快等特點(diǎn)[1]。關(guān)聯(lián)規(guī)則對(duì)發(fā)現(xiàn)大數(shù)據(jù)之間的隱藏信息具有重要意義，可以視為數(shù)據(jù)挖掘的重點(diǎn)研究對(duì)象之一。為了探索大數(shù)據(jù)內(nèi)隱含的信息，Agrawal等[2]首次提出關(guān)聯(lián)規(guī)則算法Apriori，該算法的基本思想是對(duì)數(shù)據(jù)庫(kù)進(jìn)行重復(fù)掃描[3]，依據(jù)反單調(diào)性將給定的維生成所需要的k維頻繁項(xiàng)集。首先需要找到頻繁項(xiàng)中的項(xiàng)集L1，通過L1挖掘L2，L2挖掘L3，逐層進(jìn)行挖掘，直到挖掘不到更為頻繁的k項(xiàng)集，每次只能找到一個(gè)Li，下一頻次挖掘須再次掃描數(shù)據(jù)庫(kù)。Apriori算法雖實(shí)現(xiàn)了較好的效果，但存在一些問題：一是該算法會(huì)對(duì)數(shù)據(jù)庫(kù)進(jìn)行多次掃描，候選項(xiàng)集中的每項(xiàng)都需要掃描一次數(shù)據(jù)庫(kù)，以判定是否可以加入頻繁項(xiàng)集，導(dǎo)致輸入/輸出的負(fù)擔(dān)過重；二是由于會(huì)產(chǎn)生大量的頻繁項(xiàng)集候選項(xiàng)，因此要耗費(fèi)大量主存空間和相應(yīng)的計(jì)算時(shí)間。針對(duì)此問題，本文提出了一種基于矩陣優(yōu)化的高效頻繁項(xiàng)挖掘算法（Matrix Weight Sort Apriori,MWS_Apriori）。該算法對(duì)數(shù)據(jù)庫(kù)僅掃描一次，將事務(wù)數(shù)據(jù)轉(zhuǎn)換為0-1事務(wù)矩陣形式，并且會(huì)對(duì)頻繁項(xiàng)集的項(xiàng)賦予相應(yīng)的權(quán)重，使用基數(shù)排序?qū)︻l繁項(xiàng)集重新排序，減少判斷的次數(shù)，以此來(lái)降低產(chǎn)生候選項(xiàng)集時(shí)所需的計(jì)算量。該算法能夠相對(duì)有效地減輕I/O負(fù)擔(dān)，并減少運(yùn)算次數(shù)，不僅能有效提高內(nèi)存利用率，且在一定程度上能大大縮短規(guī)則產(chǎn)生的時(shí)間。

1 Apriori算法的相關(guān)研究

Apriori算法原理是利用逐層搜索的方式來(lái)尋找相應(yīng)的頻繁項(xiàng)集，主要步驟為：第一步將k項(xiàng)集自連接生成項(xiàng)集，第二步將不滿足最小支持度的項(xiàng)進(jìn)行剪枝。Yu等[4]使用帶標(biāo)簽的算法，減少了針對(duì)候選2項(xiàng)集進(jìn)行冗余修剪的操作；Bhandari等[5]將聚類和并行算法進(jìn)行結(jié)合，減少對(duì)存儲(chǔ)空間的需求，相比之下，該方法在生成候選支持度時(shí)，時(shí)間消耗減少了67.87%；Bera等[6]以較小的空間作為代價(jià)提出一種隨機(jī)算法技術(shù)，該技術(shù)盡可能多地輸出頻繁項(xiàng)集，并降低時(shí)間開銷。Vaithiyanathan等基于壓縮數(shù)據(jù)庫(kù)的想法提出了一種改進(jìn)的先驗(yàn)算法，并通過實(shí)驗(yàn)證明了該技術(shù)的有用性；Slimani等采用一種二進(jìn)制數(shù)據(jù)集結(jié)構(gòu)，將三個(gè)數(shù)據(jù)集用于算法進(jìn)行比較；Yu等根據(jù)哈希表可快速進(jìn)行查找，提出了一種基于前綴項(xiàng)集的候選存儲(chǔ)結(jié)構(gòu)的辦法，能極大限度地提高傳統(tǒng)算法在進(jìn)行連接、剪枝中的效率，當(dāng)支持度的數(shù)值越小時(shí)所提升的效率越大。

2 MWS_Apriori算法

2.1 MWS_Apriori算法

MWS_Apriori算法思路如下：

2.1.1 掃描源數(shù)據(jù)，以項(xiàng)為行，事務(wù)為列，轉(zhuǎn)化生成事務(wù)矩陣，矩陣W中的值初始化為1。

2.1.2 若矩陣中有相同的事務(wù)，則該列在W中對(duì)應(yīng)的值加1，刪除重復(fù)的事務(wù)列。矩陣N為每項(xiàng)對(duì)應(yīng)的行按位與W中的值相乘的和，即項(xiàng)的支持度計(jì)數(shù)。矩陣M為每個(gè)事務(wù)所包含的項(xiàng)數(shù)。若N中的值小于min_sup，則將該元素在矩陣中所在的行進(jìn)行刪除，余下的即為頻繁項(xiàng)集。更新矩陣M，當(dāng)矩陣M中某個(gè)元素值為0時(shí)，將該元素所在的列進(jìn)行刪除，由此得到矩陣D1。

2.1.3 將所有頻繁1-項(xiàng)集對(duì)應(yīng)的行進(jìn)行兩兩結(jié)合并進(jìn)行對(duì)應(yīng)項(xiàng)的邏輯與操作，生成2-事務(wù)矩陣，重新計(jì)算并生成矩陣N，刪除N中值小于min_sup的元素在矩陣中對(duì)應(yīng)的行，重新計(jì)算矩陣M，若M中的某值小于2，則刪除該元素在矩陣中對(duì)應(yīng)的列，得到壓縮后的矩陣D2。

2.1.4 對(duì)頻繁項(xiàng)集中單項(xiàng)所出現(xiàn)次數(shù)進(jìn)行統(tǒng)計(jì)，根據(jù)統(tǒng)計(jì)的結(jié)果按照基數(shù)排序法中的遞增順序?qū)㈩l繁項(xiàng)集進(jìn)行重新排序。

2.1.5 依據(jù)(k -1)-候選項(xiàng)，將所有(k-1)-項(xiàng)頻繁項(xiàng)集中滿足前(k-2)個(gè)項(xiàng)相同的行進(jìn)行兩兩結(jié)合，并將結(jié)合后所得的項(xiàng)與對(duì)應(yīng)項(xiàng)進(jìn)行邏輯與操作，重新計(jì)算并生成矩陣N，刪除N中值小于min_sup的元素在矩陣中對(duì)應(yīng)的行，重新計(jì)算矩陣M，若M中的某值小于k，則將該元素所對(duì)應(yīng)的整列進(jìn)行刪除，即對(duì)矩陣進(jìn)行壓縮，壓縮后所得矩陣Dk(k≥3)。

2.1.6 對(duì)于壓縮后的矩陣Dk(k≥3)，包含的是對(duì)應(yīng)的k-項(xiàng)頻繁項(xiàng)集，其相對(duì)應(yīng)的矩陣N保存了每一項(xiàng)頻繁項(xiàng)集的支持度計(jì)數(shù)。

2.1.7 判斷頻繁項(xiàng)k-集的個(gè)數(shù)是否小于k+1或生成頻繁項(xiàng)目的集合是否為空，若是則停止搜索；反之，則重復(fù)步驟(5)～(7)。

2.2 MWS_Apriori算法的實(shí)現(xiàn)

本文從兩個(gè)方面對(duì)Apriori算法進(jìn)行優(yōu)化改進(jìn)：一是轉(zhuǎn)換成0-1事務(wù)矩陣；二是對(duì)頻繁項(xiàng)集的項(xiàng)排序，對(duì)滿足前(k-2)個(gè)項(xiàng)相同的項(xiàng)進(jìn)行連接。該算法的具體實(shí)現(xiàn)過程如下：

2.2.1 對(duì)事務(wù)數(shù)據(jù)庫(kù)進(jìn)行掃描，從而生成0-1矩陣D及矩陣W。事務(wù)T3和T6、T5和T7含有相同項(xiàng)目，所以第3、5列的權(quán)值設(shè)置為2，其余的權(quán)值均為1。

2.2.2 1-項(xiàng)頻繁項(xiàng)集，第一步對(duì)矩陣D中列元素為1進(jìn)行逐個(gè)累加求和得到矩陣M。第二步刪除M中數(shù)值≤1所對(duì)應(yīng)的列，將矩陣D中每行與所對(duì)應(yīng)的權(quán)值進(jìn)行相乘，將相乘之后每行的數(shù)值進(jìn)行相加并按行拼接在一起形成矩陣N。第三步假設(shè)Ii=[1001111]，通過support_count(Ii)=Ii×WT=6得到其他項(xiàng)的支持度計(jì)數(shù)，刪除N中≤min_sup的行，重新計(jì)算得到M，直到矩陣無(wú)變化為止。由此可得I1，I2，I3，I4，I5，為1-頻繁項(xiàng)集。

2.2.3 2-項(xiàng)頻繁項(xiàng)集，第一步將所有1-頻繁項(xiàng)集中每行進(jìn)行求與運(yùn)算形成矩陣D1。第二步將列中數(shù)值為1的元素進(jìn)行累加得到矩陣M。第三步對(duì)每行的項(xiàng)集求支持度得到矩陣N。第四步將M中數(shù)值≤1的所對(duì)應(yīng)的列刪除，將N中數(shù)值≤min_sup的所對(duì)應(yīng)的行刪除，直到矩陣無(wú)任何變化，得到矩陣D2。

2.2.4 3-項(xiàng)頻繁項(xiàng)集，第一步將2-項(xiàng)頻繁項(xiàng)集中的各項(xiàng)，按照單項(xiàng)出現(xiàn)的次數(shù)進(jìn)行遞增排序。第二步將排序后的2-項(xiàng)頻繁項(xiàng)集中滿足條件的項(xiàng)集兩兩結(jié)合，進(jìn)行對(duì)應(yīng)項(xiàng)的邏輯與操作后生成矩陣。第三步將列中所有數(shù)值為1的元素累加得到矩陣M。第四步對(duì)每行的項(xiàng)集求支持度得到矩陣N。第五步將M中數(shù)值≤1的列刪除，把N中≤min_sup所對(duì)應(yīng)的行刪除，直到矩陣無(wú)變化為止，得到矩陣D3。

2.2.5 3-項(xiàng)頻繁項(xiàng)集的個(gè)數(shù)求解為2，小于4，則終止求4-項(xiàng)頻繁項(xiàng)集，那么最大頻繁項(xiàng)集為頻繁3項(xiàng)集，結(jié)束算法。其中，D={T1，T2…T9}表示數(shù)據(jù)庫(kù)中存有9個(gè)事務(wù)；I={I1，I2，I3，I4，I5}表示對(duì)應(yīng)的項(xiàng)目集；min_sup=2。

MWS_Apriori算法能在掃描次數(shù)最少的前提下，減少候選項(xiàng)集的冗余項(xiàng)，提升算法執(zhí)行效率。

3 實(shí)驗(yàn)及算法性能分析

3.1 實(shí)驗(yàn)平臺(tái)與數(shù)據(jù)集

為了驗(yàn)證本文改進(jìn)MWS_Apriori算法的有效性和高效性，對(duì)Apriori、FP-Growth和MWS_Apriori算法在4個(gè)公共數(shù)據(jù)集上進(jìn)行對(duì)比實(shí)驗(yàn)，并根據(jù)試驗(yàn)結(jié)果進(jìn)行統(tǒng)計(jì)分析。

3.2 運(yùn)行時(shí)間比較分析

為驗(yàn)證在不同最小支持度和不同事務(wù)數(shù)量情況下算法的執(zhí)行時(shí)間，本文采用了多次取平均的方式消除多次實(shí)驗(yàn)帶來(lái)誤差的影響，并將以上3種算法在4個(gè)數(shù)據(jù)集上的不同最小支持度執(zhí)行時(shí)間做了對(duì)比。通過結(jié)果對(duì)比可以發(fā)現(xiàn)，MWS_Apriori算法在效率上好于其他的算法，并且隨著最小支持度增加，3種算法運(yùn)行時(shí)間都呈下降的趨勢(shì)。從musroom和connect這兩個(gè)數(shù)據(jù)集中挖掘出頻繁項(xiàng)集的數(shù)量遠(yuǎn)遠(yuǎn)超過所挖掘的事務(wù)數(shù)量，因此比較耗時(shí)，3種算法的運(yùn)行時(shí)間都隨最小支持度增加而趨于平緩，3種算法在處理accidents和T10I4D100K數(shù)據(jù)集時(shí)，運(yùn)算時(shí)間下降幅度都較大。

圖1顯示了包含MWS_Apriori算法在內(nèi)的3種算法在4種不同公共數(shù)據(jù)集上的具體表現(xiàn)，可以看出當(dāng)每個(gè)數(shù)據(jù)集所持有的支持度相同，事務(wù)的數(shù)量不同時(shí)，3種算法的運(yùn)行時(shí)間都隨著事務(wù)的數(shù)量增加而增加，但MWS_Apriori算法在效率上優(yōu)于剩下的兩種算法。在數(shù)據(jù)集T10I4D100K中，F(xiàn)P-Growth算法的運(yùn)行時(shí)間隨著事務(wù)數(shù)量增加逐漸接近Apriori算法所用的時(shí)間。從上述結(jié)果可以看出，改進(jìn)之后的MWS_Apriori算法運(yùn)行時(shí)間的波動(dòng)幅度明顯小于其他兩種算法，并且隨著測(cè)試數(shù)據(jù)集的增加，時(shí)間幅度波動(dòng)會(huì)越發(fā)的穩(wěn)定，表明MWS_Apriori算法相較于對(duì)比算法Apriori算法和FP-Growth算法更加具有魯棒性。

圖1 不同事務(wù)數(shù)的運(yùn)行效率對(duì)比圖

4 結(jié)束語(yǔ)

本文針對(duì)Apriori算法的頻繁掃描數(shù)據(jù)庫(kù)和產(chǎn)生候選集效率低等問題，結(jié)合前人的研究，提出了一種新的改進(jìn)算法，該算法對(duì)事件數(shù)據(jù)庫(kù)僅掃描一次，將事務(wù)數(shù)據(jù)庫(kù)轉(zhuǎn)換為二進(jìn)制數(shù)據(jù)中顯示的事務(wù)矩陣，并挖掘矩陣庫(kù)，同時(shí)依據(jù)同一事務(wù)出現(xiàn)的次數(shù)來(lái)賦予權(quán)重后根據(jù)基數(shù)排序法進(jìn)行重新排序，能減少冗余的候選項(xiàng)集及內(nèi)存的消耗，實(shí)驗(yàn)表明基于矩陣的MWS_Apriori算法的挖掘時(shí)間效率較高，算法更具魯棒性。