基于矩陣和權重下的并行改進算法*

周 迎 王 芳 黃樹成

（江蘇科技大學計算機學院 鎮江 212001）

1 引言

當今網絡時代有著海量的信息，其中有很多隱藏的人們未知的相互關系，為了找到其中的關聯，人們采用了數據挖掘［1］。數據挖掘方法被廣泛使用，提起關聯分析，人們最先想到的的就是“購物籃”的例子，這主要針對的是超市的消費顧客，通過關聯規則挖掘算法，比如從海量的消費者購物數據中獲取關聯規則。

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

為解決上述問題，本篇論文提出了改進算法RTI_Apriori。主要改進有兩點：1）引入MapReduce，根據數據塊的數量對數據進行并行處理；2）改變存儲結構，使用布爾矩陣存儲事務信息，減少系統掃描數據庫的次數，并且通過刪除矩陣中全為零的行，合并事務相同的行等操作來對矩陣進行壓縮，由此提高算法效率［5］。

2 問題陳述

2.1 關聯規則

項集即表示項的集合，可用I=｛i1，i2，i3，…，in｝來表示數據庫中的項的集合，其中ik（k=1，2，3，…，n）為項集中n個數據項［6］。項集的長度等于項集中所包含的數據項數，K-項集就表示了項集中包含了K個項。用D來表示在數據挖掘過程中用到的數據集，D=｛t1，t2，t3，…，tm｝，D由數據構成，其中tk（k=1，2，3，…，m）稱為事務。每個事務都有其對應的獨有標識，通常用TID來表示，每個事務則由若干個項組成，由此可知T?I。例如，超市中的所有可購買商品的集合就是項集I，每一個完成的購物交易就是一個事務T，一次交易完成后購物清單上的商品就是項。

關聯規則可以形式化的描述為下列形式：若X，Y均為項集，X?I，Y?I且X∩Y=?，則形如X→Y的蘊含表達式就是關聯規則，它表示項X和項Y之間的關系，其中X和Y分別成為先導和后繼，或稱之為前件和后件。關聯規則最重要的是展示兩個事物之間的依賴關系，支持度與置信度是當中兩個最重要的參數［7］。

支持度指數據項｛X，Y｝出現的概率，即在所有的事務總和中，X，Y同時出現所占的比重，可寫為式（1）。置信度指包含X的事務中Y再出現的概率，即事務｛X，Y｝在事務X單獨發生的情況下所占的比重，可寫為式（2）。

在開始前我們會事先設定一個最小支持度閾值（min_sp），假使一個項集M的支持度大于等于設定的閾值，即sup（M）≥min_sp，那么這個項集M就可以稱作為頻繁項集，若此時的頻繁項集中包含了K個項，那么就稱這項集為為頻繁K-項集［12］。

2.2 Apriori算法

Apriori算法是一種廣度優先搜索算法，主要是利用與自身項集連接和剪枝的操作對數據庫中的數據進行迭代處理，預設的最小支持度（min_sp）是用來限制項集最少要出現的次數，通常根據具體的需求來設定。

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

Apriori算法的步驟如下：

Step1：掃描全部數據得到候選1-項集得到集合為C1；依照設定的min_sp進而得到頻繁1-項集的集合L1；設定n的初始值為1；

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

Step3：此時若Ln+1集合不為空，對n進行加1操作后返回上一步；否則算法繼續；

Step4：根據上述得步驟尋找隱藏其中的關聯規則，至此算法結束［8］。

2.3 Apriori算法的缺點

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

3 改進算法

3.1 改進算法思想

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

首先，使用Map和Reduce來查找頻繁1-項集，將數據分成N個數據塊分配給計算機的Map進程來進行計算。接著考慮用布爾映射矩陣來存儲事務項集。行表示事務，列表示項，分別用“0”和“1”來表示項Ii是否在事務Tj中出現，掃描數據庫，根據數據庫中的所有1-項集生成m*n階布爾矩陣，對這個布爾矩陣進行操作。

3.2 矩陣

設矩陣中第i行，第j列所在的元素為aij，矩陣的行和列的數量分別由事務和項的個數決定。設定a，由這個規則所生成的矩陣就是事務所對的布爾矩陣。

若DB有m條交易記錄和n個項，掃描并生成對應的布爾矩陣，則可得到一個m*n階矩陣。在得出的矩陣后添加一行，用來統計每列中相同項出現的次數記為CountCi，在矩陣后添加兩列，第一列為ConutRT，用來統計每一行中項的個數；第二列為Repetition，用來統計事務不同但包含的項相同的事務出現的次數，將這些事務壓縮，以此實現數據庫掃描次數減少的目標。

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

表1 樣本數據

設置最小支持度閾值min_sp=2，根據數據庫的掃描結果，事務T002和事務T010所含項集相同，則可對其進行壓縮，由此令事務T002的Repetition值為2，其余事務的值為1。根據結果降序排列，此得到矩陣D：

由上表可以看出，i6的支持數小于min_sp，則刪掉刪掉i6對應的矩陣所在列，由此得到矩陣D1：

得頻繁1-項集L1=｛i2，i3，i1，i4，i5｝。

對矩陣D1采取進一步壓縮，例如事務T005對應的事務數為1，小于2，所以在求頻繁2-項集時可以直接刪掉，重新計算等到矩陣D2：

對矩陣D2各列進行”與”計算，例如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。因為sp_count（i2，i3）＞min_sp。因為sp_count（i2，i3）=min_sp，所以｛i2，i3｝屬于頻繁2-項集，同理計算得出頻繁2-項集L2=｛｛i1，i2｝，｛i1，i3｝，｛i1，i5｝，｛i2，i3｝，｛i2，i5｝｝。

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

對矩陣D3各列進行“與”計算，例如i1，i2，i3，i1∧i2∧i3=1100，sup_count（i1，i2，i3）=1*1+1*1+0*1+0*1=2。因為sp_count（i1，i2，i3）＞min_sp，所以｛i1，i2，i3｝屬于頻繁3-項集，同理計算得出頻繁3-項集L3=｛｛i1，i2，i3｝，｛i1，i2，i5｝｝。

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

對矩陣D4各列進行”與”計算，i1∧i2∧i3∧i5=1，sup_count（i1，i2，i3，i5）=1*1=1。因為sp_count（i1，i2，i3，i5）＜min_sp，所以｛i1，i2，i3，i5｝不屬于頻繁4-項集，算法結束。

綜上頻繁項集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 算法性能驗證及結果分析

為驗證RTI_Apriori改進算法的有效性，將RTI_Apriori算法與原算法在相同的實驗環境下進行實驗結果比較測試。文中算法的實驗環境如表1所示。

表1 實驗軟硬件環境配置環境

第一組實驗主要測試方向是比較兩種算法在不同最小支持度條件下的執行時間。

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

圖1 不同最小支持度條件下的執行時間

第二組實驗主要測試了兩種算法在事務數量不同的情況下的執行時間。

從圖2的實驗結果看出，兩種算法的執行時間都隨著事務數量的增加而逐漸上升，而且RTI_Apriori算法的執行時間在事務數量相同的情況下更優［15］。當事務數量比較小時，RTI_Apriori算法和Apriori算法的執行時間差距并不大，但兩者的執行時間的差距隨著事務數量的增長而變大。

圖2 事務數量不同的情況下的執行時間

從上述的兩組實驗結果可以看出，改進后的RTI_Apriori算法的執行效率更高，花費的時間更短。RPI_Apriori算法避免了原算法多次掃描數據庫的缺陷，時間和空間效率都得到了提升。

5 結語

本文針對Apriori算法在挖掘頻繁項集時一些固有問題進行算法改進，引用了布爾矩陣，使得算法在執行過程中不需要對數據庫進行多次掃描，從而避免算法執行過程中出現的大量冗余候選集的問題。分析改進算法RTI_Apriori算法，并結合實際用例模擬了算法的執行過程。最后，兩組實驗數據的實驗結果也表明RTI_Apriori算法更優。