一種基于圖論與最大路徑的關聯(lián)規(guī)則挖掘算法

涂曉斌，郭 力，劉晨寧，周 婷，左黎明

（華東交通大學理學院，江西 南昌 330013）

最初提出關聯(lián)規(guī)則的動機是針對購物籃分析問題，除了應用于顧客模式的挖掘，在其它領域也得到了應用，包括工程、醫(yī)療保健、金融證券分析、電信和保險業(yè)的錯誤校驗等。Agrawal[1]首先在1993 年提出了關聯(lián)規(guī)則概念， 隨后在1994 年提出了經(jīng)典的Apriori 算法，該算法第一次實現(xiàn)了在大數(shù)據(jù)集上的關聯(lián)規(guī)則提取，利用逐層搜索的迭代方法找出數(shù)據(jù)庫中項集的關系，形成規(guī)則。 汪曦曦[2]根據(jù)事務數(shù)據(jù)集生成一個布爾矩陣，并得到關聯(lián)規(guī)則圖， 通過判斷節(jié)點之間是否存在通路，產(chǎn)生頻繁項集，該過程需刪除無用的通路。 羅丹等[3]在基于矩陣的改進算法中，刪除了不能連接的項集和非頻繁項集，使矩陣更加簡化，但計算過程避免不了新矩陣的生成。 宋文慧等[4]利用一個上三角矩陣表示事務之間的關系，但在挖掘頻繁項集的過程中生成大量的候選項集。 邊根慶等[5]掃描一次數(shù)據(jù)庫，生成布爾矩陣，賦予項和事務權(quán)重，定義了一個權(quán)重支持度，通過大量計算得到頻繁項集。 楊秋翔等[6]在布爾矩陣的下方添加一行，用于計算項目支持數(shù)，刪除統(tǒng)計值等于0的事務在矩陣中所對應的行，挖掘過程需要反復進行排序和計算操作。 廖紀勇等[7]在生成關聯(lián)規(guī)則的布爾矩陣后，將各列按照支持度計數(shù)進行排序，但每生成一組頻繁k-項集，需要重新排序得到新的矩陣。 田建勇等[8]利用矩陣表示事務間的關系，但在生成頻繁項集的過程中仍然產(chǎn)生候選項集。

這些算法基于矩陣挖掘頻繁項集[9-10]，在一定程度上有效減少了對數(shù)據(jù)集掃描的次數(shù)，但在挖掘過程中出現(xiàn)了候選項集或新的矩陣，占用大量內(nèi)存。在超大數(shù)據(jù)集下，規(guī)則生成的效率較低。本文以布爾矩陣為基礎，將圖論與最大路徑問題[11-13]相結(jié)合，通過增加步長搜索頻繁項集，能有效提高算法效率。

1 Apriori 算法流程

Apriori 算法的主要思想是找出存在于事務數(shù)據(jù)集中最大的頻繁項集，再利用得到的最大頻繁項集與預先設定的最小置信度閾值生成強關聯(lián)規(guī)則。Apriori 算法的步驟如下。

1） 掃描全部數(shù)據(jù)集，產(chǎn)生候選1-項集的集合；

2） 根據(jù)最小支持度， 由候選1-項集的集合產(chǎn)生頻繁1-項集；

3） 當k＞1，重復執(zhí)行步驟（4）（5）（6）；

4） 由Lk執(zhí)行連接和剪枝操作，產(chǎn)生候選k+1-項集的集合Ck+1；

5） 根據(jù)最小支持度， 由候選k+1-項集的集合Ck+1，產(chǎn)生頻繁k+1-項集的集合Lk+1；

6） 若L 不等于空，則k=k+1，跳往步驟（4）；否則，跳往步驟（7）；

7） 根據(jù)最小置信度，由頻繁項集產(chǎn)生強關聯(lián)規(guī)則，結(jié)束。

2 基于圖和最大路徑的優(yōu)化算法

定義1 最長路徑問題。 指給定圖中找到一條最長長度的簡單路徑問題。 路徑的長度可以通過其邊數(shù)來測量，而在加權(quán)圖中通過各邊的權(quán)重之和來測量。

定義2 k-path 問題。當規(guī)定長度或步長時，找出一條長度為k 的簡單路徑， 或是在固定步長時，找到一條長度最長的簡單路徑。

這種問題應用在關聯(lián)規(guī)則中，可以將事務作為結(jié)點，當兩個事務同時出現(xiàn)時就會相連接而產(chǎn)生一條邊，二者同時出現(xiàn)的頻率作為邊的權(quán)值，從而構(gòu)成一張無向帶權(quán)圖。 當規(guī)定步數(shù)為k 且k＞2 時，所經(jīng)過的結(jié)點數(shù)為k+1，此時，挖掘頻繁k+2-項集的任務即可轉(zhuǎn)變成尋找一條最大權(quán)值的k-path。

2.1 改進的算法

假設數(shù)據(jù)集D 中包含m 個事務T 和n 個項目t，即D={T1，T2，…，Tm}，其 中I={i1，i2，…，ik}為k-項集，設置一個最小支持度min_support。

Step1 構(gòu)造關聯(lián)規(guī)則矩陣。將事務集看作列向量，項目集看作行向量，則按以下規(guī)則可生成一個m 行n 列的事務集布爾矩陣R。

Step2 矩陣的清理。 對于矩陣R 按列求和，得出各個項目在整個數(shù)據(jù)庫的支持度計數(shù)，刪去列和小于最小支持度計數(shù)的列，剩下的列所對應的項目名即頻繁1-項集L1，整理后的矩陣記作R′。

Step3 構(gòu)造關聯(lián)規(guī)則圖。 根據(jù)矩陣R′創(chuàng)建一個簡單無向圖G=（V，E）， 頂點為頻繁1-項集中的所有項目，即V=L1＝{i1，i2，…，ip}，p≤n。 對于L1中的項目，兩兩組合，在矩陣R′中進行按位與運算計數(shù)，記的數(shù)為W（isit），即有isit＝W（isit），其中s，t=1，2，…，p 且s≠t。 對圖G，連接isit＝W（isit）≠0 的頂點，則邊isit的權(quán)重為W（isit），關聯(lián)規(guī)則圖構(gòu)建完畢。

Step4 構(gòu)造待挖掘矩陣。將關聯(lián)規(guī)則圖轉(zhuǎn)換成鄰接矩陣Mp×p， 此處的圖為無向帶權(quán)圖， 鄰接矩陣Mp×p的主對角線一定為0。 在遍歷過程中，為避免元素被重復計算，對矩陣Mp×p進行約簡，將其下三角區(qū)域元素用0 替換，對于小于最小支持度計數(shù)的元素也以0 替換，得到待挖掘的矩陣M′p×p。

Step5 頻繁k-項集的生成。對于頻繁2-項集，篩選圖G 中大于min_support 的邊即可。 去除待挖掘矩陣的全0 行，全0 列。 以矩陣的左上角非0 元素為起點，頻繁k-項集（k＞2）所對應的步長為k-2，因該矩陣為上三角矩陣， 在列方向上向下移動，行方向上左右移動，找出權(quán)值最大的一條路徑。 連接該路徑中元素所對應的項目，生成頻繁k-項集。 當步長等于max|T|時，停止搜索。

3 算法分析與實驗結(jié)果

3.1 實例分析

為了進一步說明算法，給出一個簡單的算例。 已知數(shù)據(jù)庫D 中包含10 個事務，D={T1，T2，T3，…，T10}，項目集合為I={a，b，c，d，e，f}， 最小支持度為0.2，事務數(shù)據(jù)集如表1。

表1 事務數(shù)據(jù)集Tab.1 Transactional datasets

1） 掃描數(shù)據(jù)庫D，可構(gòu)造一個10 行6 列的0-1 事務矩陣R。 根據(jù)所給條件計算出最小支持度計數(shù)：min sup_count=min_support×|D|=0.2×10=2。 計算矩陣各列的列和， 刪去小于最小支持度計數(shù)的列，得到一個新的矩陣R′， 也就是頻繁1-項集所對應的矩陣。

由此得到頻繁1-項集L1={{a}，，{c}，{e}，{f}}。

2） 根據(jù)矩陣R′構(gòu)造一個關聯(lián)規(guī)則圖G=（V，E）， 其中V={a，b，c，e，f}； 對矩陣R′各列按位采用“與運算”， 得出邊集為E={ab，ac，ae，af，bc，be，bf，ce，cf，ef}，對應的權(quán)重如表2。

表2 邊與權(quán)重Tab.2 Edges and weight

畫出關聯(lián)規(guī)則圖如圖1。

圖1 關聯(lián)規(guī)則圖Fig.1 Association rule graph

3） 根據(jù)關聯(lián)圖生成鄰接矩陣M，并將小于最小支持度計數(shù)的元素用0 替換。

同時可得到頻繁2-項集：L2={{ab}，{ac}，{ae}，{af}，{bc}，{bf}，{ce}，{cf}，{ef}}。

4） 頻繁k-項集的生成k＞2。搜尋頻繁3-項集，取步長為1。 在去除全0 行、全0 列后，從第1 行開始遍歷，選擇非0 出發(fā)點ab，向矩陣的右下角搜索最大路徑，移至點ac，該路徑所對應的行、列索引名組合成頻繁項集，即{abc}。同理對于下一個點ac，有兩種移動情況，都得到頻繁項集{abc}。 如圖2（A），最終得頻繁項集：{abc}，{ace}，{abf}，{aef}； 遍歷第2 行，出發(fā)點為bc，無法移動，對下一個點進行操作，如圖2（B），得到頻繁項集：{bcf}；遍歷第3 行，如圖2（C），得到頻繁項集：{cef}。

圖2 頻繁k-項集的生成過程Fig.2 The process of generating frequent k-itemsets

最終可得頻繁3-項集L3={{abc}，{ace}，{abf}，{aef}，{bcf}，{cef}}。 當步長等于max|T|時，停止搜索。

3.2 實驗結(jié)果分析

為測試改進后的算法性能， 將本文算法與Apriori 算法進行關聯(lián)規(guī)則挖掘?qū)嶒灐?硬件環(huán)境為Intel（R）Core（TM）i7-10 750 Hz@2.60 GHz，軟件環(huán)境為Windows10 操作系統(tǒng)，使用Python 編程實現(xiàn)。本實驗選擇了某商品零售企業(yè)提供的購物籃數(shù)據(jù)集(https://download.csdn.net/download/qq_42878458/16601884?spm=1001.2014.3001.5503)，該數(shù)據(jù)包含9 835個購物籃數(shù)據(jù)，169 個商品類別。

考慮當事務數(shù)增加時，將改進的算法與傳統(tǒng)的Apriori 算法進行時間的對比，所得實驗結(jié)果見圖3。

圖3 改進的算法與Apriori 算法Fig.3 Improved algorithm and Apriori algorithm

由圖3 可知，與Apriori 算法相比，隨著數(shù)據(jù)規(guī)模的增大，改進的算法挖掘頻繁項集的時間在不斷減少，有效改進了傳統(tǒng)算法挖掘效率低的問題。

4 結(jié)論

1） Apriori 算法基于多次掃描事務數(shù)據(jù)集來執(zhí)行，在改進的算法中，把事務集看作列向量，項目集看作行向量，只掃描一次數(shù)據(jù)集，并構(gòu)造出0-1 關聯(lián)規(guī)則矩陣，減少了時間和空間消耗。

2） 對關聯(lián)規(guī)則矩陣進行約簡，刪去列和小于最小支持度計數(shù)的列；對待挖掘矩陣進行約簡，將下三角區(qū)域和小于最小支持度計數(shù)的元素以0 替換，避免重復計算。

3） 結(jié)合最大路徑問題，以待挖掘矩陣的左上角非0 元素為起點， 結(jié)合圖論中的最大路徑問題，向右下角搜索權(quán)值最大的一條路徑，并根據(jù)步長確定頻繁項集， 在時間復雜度上要優(yōu)于傳統(tǒng)的算法，在海量數(shù)據(jù)的處理方面有一定優(yōu)勢。