基于矩陣和權(quán)重下的并行改進(jìn)算法*

周 迎 王 芳 黃樹(shù)成

（江蘇科技大學(xué)計(jì)算機(jī)學(xué)院 鎮(zhèn)江 212001）

1 引言

當(dāng)今網(wǎng)絡(luò)時(shí)代有著海量的信息，其中有很多隱藏的人們未知的相互關(guān)系，為了找到其中的關(guān)聯(lián)，人們采用了數(shù)據(jù)挖掘［1］。數(shù)據(jù)挖掘方法被廣泛使用，提起關(guān)聯(lián)分析，人們最先想到的的就是“購(gòu)物籃”的例子，這主要針對(duì)的是超市的消費(fèi)顧客，通過(guò)關(guān)聯(lián)規(guī)則挖掘算法，比如從海量的消費(fèi)者購(gòu)物數(shù)據(jù)中獲取關(guān)聯(lián)規(guī)則。

提取頻繁項(xiàng)集的算法很多，最廣為人知的一定有Apriori算法［2］。Apriori算法使用是一種先驗(yàn)性質(zhì)，從下至上迭代。根據(jù)算法的性質(zhì)，如果給定的項(xiàng)集是頻繁項(xiàng)集，那么它所包含的非空子集也必是頻繁項(xiàng)集。Apriori算法的步驟最關(guān)鍵一是尋找頻繁項(xiàng)集，二是生成強(qiáng)關(guān)聯(lián)規(guī)則［3］。然而，在挖掘過(guò)程中，算法最大的不足就是對(duì)數(shù)據(jù)庫(kù)掃描多次，由此它將導(dǎo)致系統(tǒng)的輸入輸出開(kāi)銷(xiāo)增加，進(jìn)一步使得算法的效率降低［4］。

為解決上述問(wèn)題，本篇論文提出了改進(jìn)算法RTI_Apriori。主要改進(jìn)有兩點(diǎn)：1）引入MapReduce，根據(jù)數(shù)據(jù)塊的數(shù)量對(duì)數(shù)據(jù)進(jìn)行并行處理；2）改變存儲(chǔ)結(jié)構(gòu)，使用布爾矩陣存儲(chǔ)事務(wù)信息，減少系統(tǒng)掃描數(shù)據(jù)庫(kù)的次數(shù)，并且通過(guò)刪除矩陣中全為零的行，合并事務(wù)相同的行等操作來(lái)對(duì)矩陣進(jìn)行壓縮，由此提高算法效率［5］。

2 問(wèn)題陳述

2.1 關(guān)聯(lián)規(guī)則

項(xiàng)集即表示項(xiàng)的集合，可用I=｛i1，i2，i3，…，in｝來(lái)表示數(shù)據(jù)庫(kù)中的項(xiàng)的集合，其中ik（k=1，2，3，…，n）為項(xiàng)集中n個(gè)數(shù)據(jù)項(xiàng)［6］。項(xiàng)集的長(zhǎng)度等于項(xiàng)集中所包含的數(shù)據(jù)項(xiàng)數(shù)，K-項(xiàng)集就表示了項(xiàng)集中包含了K個(gè)項(xiàng)。用D來(lái)表示在數(shù)據(jù)挖掘過(guò)程中用到的數(shù)據(jù)集，D=｛t1，t2，t3，…，tm｝，D由數(shù)據(jù)構(gòu)成，其中tk（k=1，2，3，…，m）稱(chēng)為事務(wù)。每個(gè)事務(wù)都有其對(duì)應(yīng)的獨(dú)有標(biāo)識(shí)，通常用TID來(lái)表示，每個(gè)事務(wù)則由若干個(gè)項(xiàng)組成，由此可知T?I。例如，超市中的所有可購(gòu)買(mǎi)商品的集合就是項(xiàng)集I，每一個(gè)完成的購(gòu)物交易就是一個(gè)事務(wù)T，一次交易完成后購(gòu)物清單上的商品就是項(xiàng)。

關(guān)聯(lián)規(guī)則可以形式化的描述為下列形式：若X，Y均為項(xiàng)集，X?I，Y?I且X∩Y=?，則形如X→Y的蘊(yùn)含表達(dá)式就是關(guān)聯(lián)規(guī)則，它表示項(xiàng)X和項(xiàng)Y之間的關(guān)系，其中X和Y分別成為先導(dǎo)和后繼，或稱(chēng)之為前件和后件。關(guān)聯(lián)規(guī)則最重要的是展示兩個(gè)事物之間的依賴(lài)關(guān)系，支持度與置信度是當(dāng)中兩個(gè)最重要的參數(shù)［7］。

支持度指數(shù)據(jù)項(xiàng)｛X，Y｝出現(xiàn)的概率，即在所有的事務(wù)總和中，X，Y同時(shí)出現(xiàn)所占的比重，可寫(xiě)為式（1）。置信度指包含X的事務(wù)中Y再出現(xiàn)的概率，即事務(wù)｛X，Y｝在事務(wù)X單獨(dú)發(fā)生的情況下所占的比重，可寫(xiě)為式（2）。

在開(kāi)始前我們會(huì)事先設(shè)定一個(gè)最小支持度閾值（min_sp），假使一個(gè)項(xiàng)集M的支持度大于等于設(shè)定的閾值，即sup（M）≥min_sp，那么這個(gè)項(xiàng)集M就可以稱(chēng)作為頻繁項(xiàng)集，若此時(shí)的頻繁項(xiàng)集中包含了K個(gè)項(xiàng)，那么就稱(chēng)這項(xiàng)集為為頻繁K-項(xiàng)集［12］。

2.2 Apriori算法

Apriori算法是一種廣度優(yōu)先搜索算法，主要是利用與自身項(xiàng)集連接和剪枝的操作對(duì)數(shù)據(jù)庫(kù)中的數(shù)據(jù)進(jìn)行迭代處理，預(yù)設(shè)的最小支持度（min_sp）是用來(lái)限制項(xiàng)集最少要出現(xiàn)的次數(shù)，通常根據(jù)具體的需求來(lái)設(shè)定。

最小置信度（min_conf）則是衡量最小可靠程度 的 數(shù) 值。如 果 能 夠 有Sup（X?Y）/P（X）≥min_conf條件成立，那么就可以得到”X→Y”的規(guī)則［13］。

Apriori算法的步驟如下：

Step1：掃描全部數(shù)據(jù)得到候選1-項(xiàng)集得到集合為C1；依照設(shè)定的min_sp進(jìn)而得到頻繁1-項(xiàng)集的集合L1；設(shè)定n的初始值為1；

Step2：對(duì)Ln與本身連接生成的集合執(zhí)行剪枝操作從而得到候選（n+1）-項(xiàng)集的集合Cn+1；根據(jù)算法性質(zhì)，進(jìn)而得到頻繁（n+1）-項(xiàng)集的集合Ln+1；

Step3：此時(shí)若Ln+1集合不為空，對(duì)n進(jìn)行加1操作后返回上一步；否則算法繼續(xù)；

Step4：根據(jù)上述得步驟尋找隱藏其中的關(guān)聯(lián)規(guī)則，至此算法結(jié)束［8］。

2.3 Apriori算法的缺點(diǎn)

如上所示，候選集的規(guī)模越大，所產(chǎn)生的消耗越多，呈現(xiàn)指數(shù)型增長(zhǎng)，盡管在連接后進(jìn)行了剪枝操作，但仍存在許多不必要的候選項(xiàng)集。若有104個(gè)頻繁單項(xiàng)集，經(jīng)過(guò)連接就將產(chǎn)生候選2-項(xiàng)集的數(shù)據(jù)為108個(gè)候選集對(duì)，從生成的大量候選集對(duì)里找到所需的候選集是算法中時(shí)間需求最大的階段。計(jì)算支持度時(shí)算法要將集合Ck中記錄的所有候選項(xiàng)集都計(jì)算一遍進(jìn)行對(duì)比，造成不必要的資源浪費(fèi)。

3 改進(jìn)算法

3.1 改進(jìn)算法思想

從最小化事務(wù)數(shù)據(jù)庫(kù)掃描次數(shù)以及降低候選集數(shù)量方面著手改進(jìn)，進(jìn)而提高挖掘的效率。

首先，使用Map和Reduce來(lái)查找頻繁1-項(xiàng)集，將數(shù)據(jù)分成N個(gè)數(shù)據(jù)塊分配給計(jì)算機(jī)的Map進(jìn)程來(lái)進(jìn)行計(jì)算。接著考慮用布爾映射矩陣來(lái)存儲(chǔ)事務(wù)項(xiàng)集。行表示事務(wù)，列表示項(xiàng)，分別用“0”和“1”來(lái)表示項(xiàng)Ii是否在事務(wù)Tj中出現(xiàn)，掃描數(shù)據(jù)庫(kù)，根據(jù)數(shù)據(jù)庫(kù)中的所有1-項(xiàng)集生成m*n階布爾矩陣，對(duì)這個(gè)布爾矩陣進(jìn)行操作。

3.2 矩陣

設(shè)矩陣中第i行，第j列所在的元素為aij，矩陣的行和列的數(shù)量分別由事務(wù)和項(xiàng)的個(gè)數(shù)決定。設(shè)定a，由這個(gè)規(guī)則所生成的矩陣就是事務(wù)所對(duì)的布爾矩陣。

若DB有m條交易記錄和n個(gè)項(xiàng)，掃描并生成對(duì)應(yīng)的布爾矩陣，則可得到一個(gè)m*n階矩陣。在得出的矩陣后添加一行，用來(lái)統(tǒng)計(jì)每列中相同項(xiàng)出現(xiàn)的次數(shù)記為CountCi，在矩陣后添加兩列，第一列為ConutRT，用來(lái)統(tǒng)計(jì)每一行中項(xiàng)的個(gè)數(shù)；第二列為Repetition，用來(lái)統(tǒng)計(jì)事務(wù)不同但包含的項(xiàng)相同的事務(wù)出現(xiàn)的次數(shù)，將這些事務(wù)壓縮，以此實(shí)現(xiàn)數(shù)據(jù)庫(kù)掃描次數(shù)減少的目標(biāo)。

矩陣中每一列值為“1”的元素個(gè)數(shù)總和就是候選1-項(xiàng)集C1的支持度，根據(jù)CountCi和CountRT降序排列，將小于最小設(shè)定的最小支持度的項(xiàng)從矩陣中刪除，從而得到頻繁1-項(xiàng)集。數(shù)據(jù)子集的列與列之間進(jìn)行“與”運(yùn)算操作后，比對(duì)其“1”的個(gè)數(shù)和與最小支持度的大小關(guān)系，符合條件保留不符合刪除，以此循環(huán)直到項(xiàng)集空則終止［9］。

表1 樣本數(shù)據(jù)

設(shè)置最小支持度閾值min_sp=2，根據(jù)數(shù)據(jù)庫(kù)的掃描結(jié)果，事務(wù)T002和事務(wù)T010所含項(xiàng)集相同，則可對(duì)其進(jìn)行壓縮，由此令事務(wù)T002的Repetition值為2，其余事務(wù)的值為1。根據(jù)結(jié)果降序排列，此得到矩陣D：

由上表可以看出，i6的支持?jǐn)?shù)小于min_sp，則刪掉刪掉i6對(duì)應(yīng)的矩陣所在列，由此得到矩陣D1：

得頻繁1-項(xiàng)集L1=｛i2，i3，i1，i4，i5｝。

對(duì)矩陣D1采取進(jìn)一步壓縮，例如事務(wù)T005對(duì)應(yīng)的事務(wù)數(shù)為1，小于2，所以在求頻繁2-項(xiàng)集時(shí)可以直接刪掉，重新計(jì)算等到矩陣D2：

對(duì)矩陣D2各列進(jìn)行”與”計(jì)算，例如i2和i3，i2∧i3=11010100，sup_count（i2，i3）=1*1+1*1+0*1+1*1+0*1+1*1+0*2+0*1=4。因?yàn)閟p_count（i2，i3）＞min_sp。因?yàn)閟p_count（i2，i3）=min_sp，所以｛i2，i3｝屬于頻繁2-項(xiàng)集，同理計(jì)算得出頻繁2-項(xiàng)集L2=｛｛i1，i2｝，｛i1，i3｝，｛i1，i5｝，｛i2，i3｝，｛i2，i5｝｝。

對(duì)矩陣D2采取進(jìn)一步壓縮，下一步求頻繁3-項(xiàng)集，所以項(xiàng)集小于3的行向量可以刪除，重新計(jì)算等到矩陣D3：

對(duì)矩陣D3各列進(jìn)行“與”計(jì)算，例如i1，i2，i3，i1∧i2∧i3=1100，sup_count（i1，i2，i3）=1*1+1*1+0*1+0*1=2。因?yàn)閟p_count（i1，i2，i3）＞min_sp，所以｛i1，i2，i3｝屬于頻繁3-項(xiàng)集，同理計(jì)算得出頻繁3-項(xiàng)集L3=｛｛i1，i2，i3｝，｛i1，i2，i5｝｝。

對(duì)矩陣D4進(jìn)行進(jìn)一步壓縮，下一步求頻繁4-項(xiàng)集，所以項(xiàng)集小于4的行向量可以刪除，重新計(jì)算等到矩陣D4：

對(duì)矩陣D4各列進(jìn)行”與”計(jì)算，i1∧i2∧i3∧i5=1，sup_count（i1，i2，i3，i5）=1*1=1。因?yàn)閟p_count（i1，i2，i3，i5）＜min_sp，所以｛i1，i2，i3，i5｝不屬于頻繁4-項(xiàng)集，算法結(jié)束。

綜上頻繁項(xiàng)集L=L1∪L2∪L3=｛｛i2｝，｛i3｝，｛i1｝，｛i4｝，｛i5｝｝，｛i1，i2｝，｛i1，i3｝，｛i1，i5｝，｛i2，i3｝，｛i2，i4｝，｛i2，i5｝，｛i1，i2，i3｝，｛i1，i2，i5｝

4 算法性能驗(yàn)證及結(jié)果分析

為驗(yàn)證RTI_Apriori改進(jìn)算法的有效性，將RTI_Apriori算法與原算法在相同的實(shí)驗(yàn)環(huán)境下進(jìn)行實(shí)驗(yàn)結(jié)果比較測(cè)試。文中算法的實(shí)驗(yàn)環(huán)境如表1所示。

表1 實(shí)驗(yàn)軟硬件環(huán)境配置環(huán)境

第一組實(shí)驗(yàn)主要測(cè)試方向是比較兩種算法在不同最小支持度條件下的執(zhí)行時(shí)間。

從圖1的實(shí)驗(yàn)結(jié)果橫向來(lái)看，兩種算法的執(zhí)行時(shí)間都隨著最小支持度數(shù)值的增加而逐漸下降，縱向的看，在支持度數(shù)值一致的情況下，RTI_Apriori算法的執(zhí)行時(shí)間明顯更小，主要原因是RTI_Apriori算法在尋找頻繁項(xiàng)集的過(guò)程中只需要掃描一次數(shù)據(jù)庫(kù)，從而算法的執(zhí)行時(shí)間減少了，效率提高了［14］。

圖1 不同最小支持度條件下的執(zhí)行時(shí)間

第二組實(shí)驗(yàn)主要測(cè)試了兩種算法在事務(wù)數(shù)量不同的情況下的執(zhí)行時(shí)間。

從圖2的實(shí)驗(yàn)結(jié)果看出，兩種算法的執(zhí)行時(shí)間都隨著事務(wù)數(shù)量的增加而逐漸上升，而且RTI_Apriori算法的執(zhí)行時(shí)間在事務(wù)數(shù)量相同的情況下更優(yōu)［15］。當(dāng)事務(wù)數(shù)量比較小時(shí)，RTI_Apriori算法和Apriori算法的執(zhí)行時(shí)間差距并不大，但兩者的執(zhí)行時(shí)間的差距隨著事務(wù)數(shù)量的增長(zhǎng)而變大。

圖2 事務(wù)數(shù)量不同的情況下的執(zhí)行時(shí)間

從上述的兩組實(shí)驗(yàn)結(jié)果可以看出，改進(jìn)后的RTI_Apriori算法的執(zhí)行效率更高，花費(fèi)的時(shí)間更短。RPI_Apriori算法避免了原算法多次掃描數(shù)據(jù)庫(kù)的缺陷，時(shí)間和空間效率都得到了提升。

5 結(jié)語(yǔ)

本文針對(duì)Apriori算法在挖掘頻繁項(xiàng)集時(shí)一些固有問(wèn)題進(jìn)行算法改進(jìn)，引用了布爾矩陣，使得算法在執(zhí)行過(guò)程中不需要對(duì)數(shù)據(jù)庫(kù)進(jìn)行多次掃描，從而避免算法執(zhí)行過(guò)程中出現(xiàn)的大量冗余候選集的問(wèn)題。分析改進(jìn)算法RTI_Apriori算法，并結(jié)合實(shí)際用例模擬了算法的執(zhí)行過(guò)程。最后，兩組實(shí)驗(yàn)數(shù)據(jù)的實(shí)驗(yàn)結(jié)果也表明RTI_Apriori算法更優(yōu)。