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

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

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

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

1 Apriori 算法流程

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

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

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

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

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

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

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

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

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

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

定義2 k-path 問(wèn)題。當(dāng)規(guī)定長(zhǎng)度或步長(zhǎng)時(shí)，找出一條長(zhǎng)度為k 的簡(jiǎn)單路徑， 或是在固定步長(zhǎng)時(shí)，找到一條長(zhǎng)度最長(zhǎng)的簡(jiǎn)單路徑。

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

2.1 改進(jìn)的算法

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

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

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

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

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

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

3 算法分析與實(shí)驗(yàn)結(jié)果

3.1 實(shí)例分析

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

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

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

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

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

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

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

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

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

同時(shí)可得到頻繁2-項(xiàng)集：L2={{ab}，{ac}，{ae}，{af}，{bc}，{bf}，{ce}，{cf}，{ef}}。

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

圖2 頻繁k-項(xiàng)集的生成過(guò)程Fig.2 The process of generating frequent k-itemsets

最終可得頻繁3-項(xiàng)集L3={{abc}，{ace}，{abf}，{aef}，{bcf}，{cef}}。 當(dāng)步長(zhǎng)等于max|T|時(shí)，停止搜索。

3.2 實(shí)驗(yàn)結(jié)果分析

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

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

圖3 改進(jìn)的算法與Apriori 算法Fig.3 Improved algorithm and Apriori algorithm

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

4 結(jié)論

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

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

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