基于Apriori 算法的關(guān)聯(lián)規(guī)則分析應(yīng)用

殷麗鳳，李明狀

（大連交通大學(xué)軟件學(xué)院，遼寧 大連 116028）

目前，隨著整個(gè)社會(huì)進(jìn)入到信息化時(shí)代，大量的信息和數(shù)據(jù)成為了當(dāng)前時(shí)代的特征。在大數(shù)據(jù)時(shí)代下，數(shù)據(jù)就是人類的無形財(cái)富和資產(chǎn)。在不斷產(chǎn)生海量數(shù)據(jù)的情況下，必須利用新的技術(shù)手段和工具來處理海量的數(shù)據(jù)集，從而更加智慧地提取數(shù)據(jù)中有用的信息。關(guān)聯(lián)規(guī)則挖掘技術(shù)是數(shù)據(jù)挖掘最重要的方法之一，凡是涉及從數(shù)據(jù)中獲取知識(shí)的問題，關(guān)聯(lián)規(guī)則挖掘都可能成為有力的工具。現(xiàn)如今關(guān)聯(lián)規(guī)則挖掘已經(jīng)應(yīng)用到各行各業(yè)，例如銷售行業(yè)、金融、教育等。文中利用關(guān)聯(lián)規(guī)則挖掘中最經(jīng)典的Apriori 算法，使用公共數(shù)據(jù)集MovieLens進(jìn)行電影標(biāo)簽推薦的研究。

1 數(shù)據(jù)挖掘和關(guān)聯(lián)規(guī)則

1.1 數(shù)據(jù)挖掘

數(shù)據(jù)挖掘技術(shù)是數(shù)據(jù)分析方法，它從大量的、模糊的、有噪音的數(shù)據(jù)中挖掘出具有潛在價(jià)值的、隱藏的、未知的概念、規(guī)則和模式。

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

關(guān)聯(lián)規(guī)則挖掘是一種處理大量數(shù)據(jù)集中各項(xiàng)之間隱藏的屬性關(guān)系的方法。假設(shè)兩項(xiàng)或者多項(xiàng)屬性之間存在一定關(guān)聯(lián)，則一項(xiàng)屬性就能按照其他屬性進(jìn)行判定[1]。下面給出項(xiàng)、項(xiàng)集、項(xiàng)集的頻數(shù)、支持度、置信度、作用度、最小支持度和最小置信度等關(guān)聯(lián)規(guī)則的相關(guān)概念。

1）項(xiàng)與項(xiàng)集

設(shè)I={i1,i2,…,im}，i1,i2,…,im稱為項(xiàng)，集合I稱為項(xiàng)集。

2）項(xiàng)集的頻數(shù)

包括項(xiàng)集的事務(wù)數(shù)稱為項(xiàng)集的頻數(shù)，事務(wù)數(shù)代表數(shù)據(jù)集中的記錄數(shù)，數(shù)據(jù)庫中的一條記錄稱為事務(wù)，頻數(shù)被用于支持度的計(jì)數(shù)[3]。

3）支持度（Support）

關(guān)聯(lián)規(guī)則X→Y的支持度反映了所有事務(wù)集中{X,Y}出現(xiàn)的可能性[2],公式如下所示。

式中，D表示整個(gè)事務(wù)集，| |D表示D中事務(wù)的總數(shù)，NUM(X∪Y)表示數(shù)據(jù)集中X與Y同時(shí)出現(xiàn)在一條事務(wù)記錄中的次數(shù)[3]。

4）置信度（Confidence）

關(guān)聯(lián)規(guī)則X→Y的置信度反映了事務(wù){(diào)X,Y}在事務(wù)X單獨(dú)發(fā)生的情況下所占的比重，公式如下所示。

5）作用度（Lift）

關(guān)聯(lián)規(guī)則X→Y的作用度反映了事務(wù)Y發(fā)生的條件下，同時(shí)含有事務(wù)X的概率與僅關(guān)注事務(wù)X發(fā)生概率的之比，實(shí)質(zhì)上就是置信度和期望置信度的比值[4]，公式如下所示。

6）確信度（Conviction）

關(guān)聯(lián)規(guī)則X→Y的確信度反映了事務(wù)X出現(xiàn)而事務(wù)Y不出現(xiàn)的概率，公式如下所示。

7）最小支持度與最小置信度

最小支持度（min_Sup）與最小置信度（min_Conf）是根據(jù)實(shí)際情況人為設(shè)定的，通過比較事務(wù)集的支持度與最小支持度，進(jìn)行剪枝操作。最小支持度反映了關(guān)聯(lián)規(guī)則的最低重要程度，最小置信度規(guī)定了關(guān)聯(lián)規(guī)則必須滿足的最低可靠性[3]。

8）頻繁項(xiàng)集

頻繁項(xiàng)集即支持度大于min_Sup 的事務(wù)集。

9）強(qiáng)關(guān)聯(lián)規(guī)則

在頻繁項(xiàng)集中，置信度大于或等于最小置信度的關(guān)聯(lián)規(guī)則稱為強(qiáng)關(guān)聯(lián)規(guī)則[5]。

2 Apriori算法原理

Apriori 算法是關(guān)聯(lián)規(guī)則挖掘頻繁項(xiàng)集的經(jīng)典算法之一[6]，基本思想就是利用層層迭代的方式逐層獲取頻繁項(xiàng)集[7]。頻繁k-項(xiàng)集Lk用于搜索頻繁(k+1)-項(xiàng)集Lk+1，反復(fù)循環(huán)，直到不能找到新的頻繁項(xiàng)集為止，然后通過頻繁項(xiàng)集挖掘出強(qiáng)關(guān)聯(lián)規(guī)則[8]。為了提高頻繁項(xiàng)集產(chǎn)生的效率，Apriori 算法有如下兩個(gè)性質(zhì)：

性質(zhì)1：事務(wù)數(shù)據(jù)庫D中有兩個(gè)項(xiàng)集分別為X與Y，假設(shè)滿足X?Y，且Y是一個(gè)頻繁項(xiàng)集，X≠?，則推出X是頻繁項(xiàng)集[9]。

性質(zhì)2：事務(wù)數(shù)據(jù)庫D中有兩個(gè)項(xiàng)集分別為X與Y，假設(shè)滿足X?Y，且當(dāng)X是一個(gè)非頻繁項(xiàng)集時(shí)，則Y也是非頻繁項(xiàng)集。

Apriori 算 法步驟 如下[9]：

Step1：設(shè)定最小支持度及最小置信度。

Step2：通過掃描事務(wù)數(shù)據(jù)庫后，計(jì)算每一個(gè)事務(wù)集的支持度。將其與最小支持度進(jìn)行對比，所有支持度大于或等于最小支持度的事務(wù)集被稱為頻繁1-項(xiàng)集，該集合記為L1[10]。

Step3：掃描L1，將L1中的事務(wù)集進(jìn)行自連接，形成頻繁2-項(xiàng)集的候選集C2。

Step4：遍歷C2中所有的事務(wù)項(xiàng)，計(jì)算每個(gè)事務(wù)項(xiàng)的支持度，支持度不低于最小支持度的項(xiàng)集則為頻繁2-項(xiàng)集[10]，該集合記為L2。

Step5：重復(fù)Step3，Step4 過程，直到不能再找到頻繁k-項(xiàng)集。

Step6：計(jì)算頻繁k-項(xiàng)集中元素之間的置信度，根據(jù)min_Conf 篩選產(chǎn)生關(guān)聯(lián)規(guī)則[11]。

算法流程圖如圖1 所示。

圖1 Apriori算法流程圖

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

3.1 獲取數(shù)據(jù)集

MovieLens 數(shù)據(jù)集是推薦系統(tǒng)領(lǐng)域最為經(jīng)典的數(shù)據(jù)集之一[12]。文中采用MovieLens 數(shù)據(jù)集中的movie.csv 文件，該文件包括movieId（電影編號）、title（電影名稱）、genres（電影標(biāo)簽）三個(gè)屬性參數(shù)[13]。

3.2 用One-hot編碼進(jìn)行數(shù)據(jù)預(yù)處理

One-hot 編碼也稱“獨(dú)熱編碼”，又稱一位有效編碼，使用One-hot 編碼，主要是采用N位狀態(tài)寄存器來對N個(gè)狀態(tài)進(jìn)行編碼，每個(gè)狀態(tài)都有獨(dú)立的寄存器位，并且在任意時(shí)候只有一位有效[14]。在數(shù)據(jù)處理任務(wù)中，為了加快速度，通常需要對數(shù)據(jù)進(jìn)行特征數(shù)字化，三個(gè)特征屬性的例子如下：

性別：[“male”，“female”]

地區(qū)：[“China”，“US”，“Asia”]

瀏覽器：[“Firefox”，“Chrome”，“Safari”，“Microsoft Edge”]

對于某一個(gè)樣本，如[“female”，“ China”，“Safari”]，在進(jìn)行數(shù)據(jù)預(yù)處理之前，要將這個(gè)樣本值的特征采用序列化的方式進(jìn)行數(shù)字化。如性別的兩個(gè)特征屬性值“male”和“female”對應(yīng)的數(shù)值分別為0和1；地區(qū)的三個(gè)特征屬性值“China”“US”“Asia”對應(yīng)的數(shù)值為0、1、2，瀏覽器四個(gè)特征屬性值對應(yīng)的數(shù)值分別為0、1、2、3。樣本[“female”，“China”，“Safari”]序列化的結(jié)果為[1,0,2]。但序列化特征處理并不能直接放入算法中，為了解決此問題，可以采用Onehot 編碼處理。在One-hot 編碼中，樣本值中有多少特征屬性值，就用多少維來表示這個(gè)特征[15]。采取One-Hot 編碼處理方式對樣本“[“female”，“China”，“Safari”]”進(jìn)行編碼，“female”對應(yīng)[0,1]，“China”對應(yīng)[1,0,0]，“Safari”對應(yīng)[0,0,1,0]。則完整的編碼結(jié)果為[0,1,1,0,0,0,0,1,0]。

文中采用的MovieLens 數(shù)據(jù)集非常規(guī)則，對于數(shù)據(jù)預(yù)處理分為如下步驟：

Step1:查看genres 數(shù)據(jù)列的類型；

Step2:將genres 列數(shù)據(jù)進(jìn)行One-hot 編碼；

Step3:電影類型之間使用“|”分隔符隔開；

Step4:把genres 列去掉，分割之后再拼接上；

Step5:把genres 轉(zhuǎn)換為字符串類型，然后按豎線進(jìn)行分割。

用One-hot 編碼處理MovieLens 數(shù)據(jù)集得到的部分結(jié)果如圖2 所示。

圖2 用One-hot編碼處理數(shù)據(jù)后的部分?jǐn)?shù)據(jù)集

3.3 實(shí)驗(yàn)過程

利用Apriori 算法生成頻繁項(xiàng)集，通過與最小置信度比較生成關(guān)聯(lián)規(guī)則[8]。例如關(guān)聯(lián)規(guī)則X→Y，用戶喜歡X類型標(biāo)簽電影，則該用戶很可能喜歡Y類型標(biāo)簽的電影。文中設(shè)定最小作用度，只返回高于最小作用度的關(guān)聯(lián)規(guī)則。作用度反映了在用戶給電影標(biāo)簽為X時(shí)，推薦用戶標(biāo)簽Y的電影出現(xiàn)概率發(fā)生了多大的變化[16]。整個(gè)實(shí)驗(yàn)的過程如下：

1）掃描事務(wù)數(shù)據(jù)集，累計(jì)每個(gè)事務(wù)出現(xiàn)的次數(shù)，設(shè)置最小支持度為0.02；

2）按照支持度大小輸出頻繁項(xiàng)集；

3）根據(jù)所產(chǎn)生的頻繁項(xiàng)集計(jì)算關(guān)聯(lián)規(guī)則，設(shè)定最小作用度為2；

4）按照作用度從大到小排序，得到的關(guān)聯(lián)規(guī)則本地保存。

3.4 結(jié)果分析

根據(jù)實(shí)驗(yàn)過程中步驟2，通過Apriori 算法遍歷每條電影數(shù)據(jù)，大于最小支持度0.02 的項(xiàng)集則為頻繁項(xiàng)集，共計(jì)頻繁項(xiàng)集38 條，輸出的部分頻繁項(xiàng)集如表1 所示。

表1 部分頻繁項(xiàng)集

根據(jù)實(shí)驗(yàn)過程步驟3，設(shè)置最小作用度為2，得到部分關(guān)聯(lián)規(guī)則為表2 所示。

表2 部分關(guān)聯(lián)規(guī)則結(jié)果

查看表2 中列出的六條數(shù)據(jù)，可以得出實(shí)驗(yàn)結(jié)果如下：從表中的關(guān)聯(lián)規(guī)則可以看出，關(guān)聯(lián)規(guī)則(Thriller)→(Mystery)的作用度為3.428 351 5，這個(gè)作用度大于設(shè)置的最小作用度2 時(shí)，代表事務(wù){(diào)′Thriller′}的出現(xiàn)對于事務(wù){(diào)′Mystery′}的出現(xiàn)有很大的影響，則可以說明事務(wù){(diào)′Thriller′}與事務(wù){(diào)′Mystery′}之間具有很強(qiáng)的關(guān)聯(lián)關(guān)系，同時(shí)數(shù)據(jù)確信度的數(shù)值越高也代表兩者關(guān)聯(lián)性越高。則當(dāng)用戶給電影打{′Thriller′}標(biāo)簽后，通過得到的關(guān)聯(lián)規(guī)則結(jié)果可以得出，程序會(huì)有很大概率給用戶推薦標(biāo)簽為{′Mystery′}的電影，從而提升電影推薦的準(zhǔn)確度。

從表2 實(shí)驗(yàn)數(shù)據(jù)來看，幾條規(guī)則在數(shù)據(jù)集上的作用度、確信度很高，所以表明當(dāng)用戶給自己喜歡的電影標(biāo)注標(biāo)簽時(shí)，使用Apriori 算法進(jìn)行的電影推薦效果很好，從而提升了用戶體驗(yàn)。

4 結(jié)束語

文中首先利用機(jī)器學(xué)習(xí)中的One-hot 編碼原理對電影評分?jǐn)?shù)據(jù)集MovieLens 進(jìn)行數(shù)據(jù)處理，利用Apriori 算法找出數(shù)據(jù)集中的頻繁項(xiàng)集，根據(jù)頻繁項(xiàng)集找出關(guān)聯(lián)規(guī)則完成電影的推薦，實(shí)例分析表明，用Apriori 算法進(jìn)行電影推薦效果很好，能很好提升用戶體驗(yàn)。但由于Ariori 算法的自身缺陷會(huì)產(chǎn)生大量的候選集，以及需要重復(fù)掃描數(shù)據(jù)庫，而會(huì)加大加劇計(jì)算機(jī)系統(tǒng)的I/O 開銷，所以進(jìn)一步的研究方向?qū)?huì)放在如何優(yōu)化Apriori 算法減少計(jì)算機(jī)系統(tǒng)I/O 開銷和優(yōu)化算法精度上。