基于關(guān)聯(lián)規(guī)則的數(shù)據(jù)挖掘Apriori算法的兩種優(yōu)化分析

張 超

（亳州學(xué)院 電子與信息工程系，安徽 亳州236800）

Apriori算法是關(guān)聯(lián)規(guī)則挖掘技術(shù)的最基本算法［1］.目前關(guān)聯(lián)規(guī)則的并行數(shù)據(jù)挖掘算法大都以Apriori算法為基礎(chǔ)，它具有無可替代的獨特地位，其效率的優(yōu)化研究已成為廣大學(xué)者關(guān)注的熱點.Apriori算法本質(zhì)主要包含兩個方面問題，第一個是找出事務(wù)數(shù)據(jù)庫中所有的頻繁數(shù)據(jù)項集.第二個是如何生成強關(guān)聯(lián)規(guī)則.兩個方面相比較，第一方面的問題是算法的核心［2］.基于此，對算法進行優(yōu)化，就應(yīng)把重點放在找出頻繁數(shù)據(jù)項集方面.

1 Apriori算法概述

1.1 原理

Apriori算法的核心思想是基于頻繁項集理論的遞歸方法，采用逐層搜索的迭代方法挖掘出在目標(biāo)事務(wù)數(shù)據(jù)庫中所有頻繁項集，直至找到最高階頻繁項集即止，最后通過對獲得的頻繁項集進行計算得到強關(guān)聯(lián)規(guī)則［3-5］.其中，現(xiàn)設(shè)候選k-項集集合表示為Ck，頻繁k-項集集合表示為Lk.經(jīng)過一次掃描后，即可快捷得出L1.執(zhí)行第k（k＞1）次掃描時，由Lk-1生成Ck.然后根據(jù)Ck繼續(xù)進行掃描，對照每個元素的支持度，刪減不符合者，最后即可求得Lk.依據(jù)此思路可依次求得Lk+1，Lk+2，Lk+3…….若某次計算Ck為空時，算法自然結(jié)束.

1.2 生成頻繁項集的過程

Apriori算法的基本思想是基于頻繁項集生成過程，使用遞推方式推演出頻繁項集，使用頻繁項集Lk-1產(chǎn)生頻繁項集Lk，其過程分為連接和剪枝兩步［6］.Apriori算法生成頻繁相集的第一步驟為連接步，即計算Lk由 Lk-1自身作連接得到 Ck.假若 Lk-1中含有項集 l1及 l2，li為（k-1）項集，規(guī)定 li［j］為 li的項，j為項的序號.對于 li，使得 li［1］＜li［2］＜…＜.對于 l1和 l2，假設(shè) l1和 l2是可連接的，那么它們從第 1 個到第（k-2）個的項都應(yīng)當(dāng)分別對應(yīng)相等.即（l1［1］=l2［1］）∩（l1［2］=l2［2］）∩…∩（l1［k-2］=l2［k-2］）∩（=l1［k-1］＜l2［k-1］）.其中 l1［k-1］＜l2［k-1］限定不產(chǎn)生重復(fù)現(xiàn)象，最后的結(jié)果項集可記作：（l1［1］，l1［2］，…，l1［k-1］，l1［k-2］）.

第二步驟為剪枝步，按照在給定的事務(wù)數(shù)據(jù)庫D中，任意大項集的子集都是大項集，任意弱項集的超集都是弱項集［7］的性質(zhì)，可以刪除Ck中對應(yīng)的支持度不滿足的某個子集.

1.3 主要步驟

設(shè)min-sup表示最小支持度，則有以下步驟：（1）掃描數(shù)據(jù)，并生成C1；（2）根據(jù)min-sup的要求，由C1推導(dǎo)出 L1；（3）k＞1 時，按照（4）、（5）、（6）的次序重復(fù)執(zhí)行；（4）對 Lk-1執(zhí)行連接和剪枝操作，并得出 Ck；若Ck=Φ，執(zhí)行（7），不然，執(zhí)行（5）；（5）按照 min-sup 的要求，由候選 Ck推導(dǎo)出 Lk；（6）如 L≠Φ，k=k+1，執(zhí)行（4）；否則執(zhí)行（7）；（7）由min-sup的具體要求，基于頻繁項集進一步推導(dǎo)出強關(guān)聯(lián)規(guī)則.

2 Apriori算法的應(yīng)用求解過程

一個大型購物中心的數(shù)據(jù)庫事務(wù)包括T1、T2……T9，|D|=9.基于Apriori算法求D中頻繁項集，Ti表示事務(wù)名，Pi表示商品名，Ci表示候選 i—項集集合，Li表示頻繁項集， 規(guī)定 min-sup=2，T1={P1P2P5}、T2={P2P4}、T3={P2P3}、T4={P1P2P4}、T5={P1P3}、T6={P2P3}、T7={P1P3}、T8={P1P2P3P5}、T9={P1P2P3}.

具體求解過程如下：第一次C1→L1，按照min-sup=2的要求，對原數(shù)據(jù)庫D進行掃描C1={{P1}{P2}{P3}{P4}{P5}}各項集的支持度分別為6、7、6、2、2.繼而對C1掃描，不需要刪除任何項目，求得L1=C1且支持度不變。

第二次求解C2→L2，在第一次求解出L1結(jié)果的基礎(chǔ)上，進一步求得C2=L1∞L1。C2={{P1P2}{P1P3}{P1P4}{P1P5}{P2，P3}{P2，P4}{P2，P5}{P3，P4}{P3，P5}{P4，P5}}，在剪枝步中 C2無須刪除.對其掃描后可求得 C2的各項支持度分別為 4、4、1、2、4、2、2、0、1、0. 結(jié)合支持度 min-sup=2 的要求， 刪除不滿足后三項要求者即可得到 L2。L2={{P1P2}{P1P3}{P1P4}{P1P5}{P2，P3}{P2，P4}{P2，P5}}，其中各項的支持度分別為 4、4、1、2、4、2、2.

第三次求解C3→L3，在第二次的結(jié)果的基礎(chǔ)上，對L2進行自身連接得到C3，再由其對應(yīng)的支持度數(shù)即可求得L3.步驟如下：

（1） 執(zhí)行連接操作：C3=L2∞L2={{P1，P2}，{P1，P3}，{P1，P5}，{P2，P3}，{P2，P4}，{P2，P5}} ∞ {{P1，P2}，{P1，P3}，{P1，P5}，{P2，P3}，{P2，P4}，{P2，P5}}={{P1，P2，P3}，{P1，P2，P5}，{P1，P3，P5}，{P2，P3，P4}，{P2，P3，P5}，{P2，P4，P5}}.

（2）執(zhí)行剪枝操作：根據(jù)有關(guān)性質(zhì)，上步結(jié)果中的后4個均要刪除.以{P1，P3，P5}為例，其對應(yīng)的2項子集分別包括{P1，P3}、{P1，P5}、{P3，P5}.L2中存在{P1，P3}、{P1，P5}但不包括{P3，P5}，因而不是頻繁的.剪枝后得到 C3={{P1，P2，P3}，{P1，P2，P5}}.

（3）結(jié)合統(tǒng)計支持度，C3的各元素均符合.即 L3={{P1，P2，P3}，{P1，P2，P5}}.

第四次掃描：求解 C4=L3∞L3，L3∞L3={{P1，P2，P3，P5}}，但其子集{P2，P3，P5}不屬于 L3范疇，因此它不是頻繁的，理應(yīng)刪除.至此求解全過程結(jié)束.

3 Apriori算法效率的優(yōu)化

綜上分析，進行推導(dǎo)Ck的連接操作通常要做大量繁雜的比較.但即便如此，卻并不保證得到的一定為候選項集.這樣一來，連接操作的有效性就比較差，往往在許多時候都是無效的.若能夠去除無效的連接比較，簡化剪枝步驟，而使執(zhí)行連接之后得到的都歸屬于候選項集，那么算法效率將得到真正的優(yōu)化提升.基于這種思路，筆者提出一種優(yōu)化后的Apriori-A算法.

3.1 Apriori-A算法思想

首先，執(zhí)行對 Lk-1掃描，并記錄項集：{l1［1］}，{l1［1］，l1［2］}，…，{l1［1］，l1［2］，…，l1［k-2］，l1［k-1］}，{l2［1］}，{l2［1］，l2［2］}，…，{l2［1］，l2［2］，…，l2［k-2］，l2［k-1］}，{l3［1］}，….基于描述方便，令 li是一個 k 項集，li={li［1］，li［2］，…，li［k-1］，li［k］}，由算法性質(zhì)可知，若 li歸屬于 Ck，那么 Lk-1應(yīng)包含其以下的 k-1 個 k-1 項集.綜上分析，進而得到規(guī)律：在掃描中，設(shè)項集{li［1］}，{li［1］，li［2］}的出現(xiàn)機會分別為 Q1和 Q2，那么必有 Q1≥k-1，Q2≥k-2.以此類推，項集{li［1］，li［2］，…，li［k-1］］}出現(xiàn)機會 Qk-1≥1.假定 Q1、Q2分別是{li［1］}，{li［1］，li［2］}的掃描次數(shù)，若 k-1＞Q1，則執(zhí)行刪除操作，即將 Lk-1中凡是以 li［1］開始的 k-1項集一律刪除.假若 k-1≤Q1，則將 Q2與 k-2 進行比較.依此類推分析，假若 k-2＞Q2，把 Lk-1中凡是以項集{li［1］，li［2］}起頭的全部刪除，如果k-2≤Q2，就接著與后面的項集掃描次數(shù)繼續(xù)比較.

這種優(yōu)化的策略，實際上是以數(shù)字比較和刪除操作為手段，進而實現(xiàn)了刪除Lk-1中大量的無效項集.此優(yōu)化算法的優(yōu)點在于事先大大減少了冗余的連接，最后以連接操作生成k項集，只要通過一次比較操作即得出是否歸屬于Ck.該優(yōu)化思想基于先刪除后連接，以減少冗余的連接為前提條件，進而實現(xiàn)減少剪枝步中的判斷量，最終實現(xiàn)提升數(shù)據(jù)挖掘效率的目的.

3.2 Apriori-A算法應(yīng)用分析

例 1： L3={{O，P，Q}，{O，P，T}，{P，Q，R}，{P，Q，S}，{P，R，S}，{Q，R，S}，{Q，S，T}，{R，S，T}}.

基于Apriori-A算法，其刪減操作過程見表1.執(zhí)行得到結(jié)果={{P，Q，R}，{P，Q，S}}，然后執(zhí)行它的自連接操作，最終得到{P，Q，R，S}的四項集.由于子集{Q，R，S}∈L3，所以 C4={P，Q，R，S}，通過驗證，得出結(jié)論是完全正確.

表1 刪減L3中項集的過程

本例中，如執(zhí)行經(jīng)典 Apriori算法，則首先執(zhí)行連接操作，求得{O，P，Q，T}、{P，Q，R，S}兩個項集.然后執(zhí)行剪枝步驟，若在最壞的極端情況下，則要對{O，P，Q}、{O，P，T}、{O，Q，T}、{P，Q，T}、{P，Q，R}、{P，Q，S}、{P，R，S}、{Q，R，S}等8個項集都要判斷其是否在L3范圍之內(nèi).綜上分析，在本優(yōu)化算法中，只需執(zhí)行連接操作求得相應(yīng)的四項集，在后面的剪枝步驟中，再判斷其子項集{Q，R，S}同L3有無歸屬關(guān)系成立即可.相比而言，優(yōu)化后的Apriori-A算法效率明顯地提升.

3.3 Apriori-B算法思想

通過深入分析和研究后，還可得知另一結(jié)論：判別一個項集是否歸屬于Lk，對Ck中的所有對象還需進一步明確其支持度計數(shù).一般來說，用于關(guān)聯(lián)規(guī)則挖掘的數(shù)據(jù)庫的數(shù)據(jù)量都是非常龐大的.從先前分析來看，繁瑣冗余的掃描則在很大程度上使得算法的效率大幅降低.試想，假如能夠應(yīng)用某種策略使得掃描次數(shù)大幅簡略，則算法的優(yōu)化就自然輕松實現(xiàn).這樣一來，問題的根源在于運用何種恰當(dāng)?shù)牟呗阅軌蚴沟脭?shù)據(jù)庫的掃描大幅精簡.

按照上述思路，現(xiàn)提出另一種優(yōu)化策略.具體如下：引入一個C’K，在此集合中的任一對象標(biāo)記成＜TID，{XK}＞，XK表示為潛在的頻繁K—項集.C’K作如下特性的定義，數(shù)據(jù)庫表示為D，事務(wù)表示為T，若k=l，C’K和D是一致的，其本質(zhì)上可看作是用{I}代替了項目i.若K＞1，C’K中包含的對象同T保持完全相同，即可表示為：＜t.TID，{C∈C’K∣C?t}＞.歸結(jié)到實際，就是先得到頻繁 1-項集，并同步生成了 C’1.

從第二步起始，諸如此類，即可往復(fù)循環(huán)，直至不再有頻繁項目集的生成.現(xiàn)假定第k步出現(xiàn)了循環(huán)，基于描述方便，分為兩步說明.其一，先由第K-1步中得到LK-1，對其連接生成候選頻繁K-項目集CK，并同步生成集合C’K，繼續(xù)在C’K中搜索，即可統(tǒng)計出對應(yīng)CK的支持度.究其根源是基于這一理論：如果一個事務(wù)不包含任何候選K-項集，則C’K中將沒有這個事務(wù)的目錄，所以C’K的目錄數(shù)據(jù)必然小于數(shù)據(jù)庫中事務(wù)的數(shù)據(jù)，特別是當(dāng)k值很大時［8-10］.并且這種情況，極有可能因k值的增長，而呈現(xiàn)愈來明顯的趨勢.進而可以推知，當(dāng)K值較大時，由于事務(wù)T基本上沒什么候選項，所以任一目錄同對應(yīng)事務(wù)T相比，均要小于.同理，若當(dāng)K值較小時，對于任一個T的候選K-項目集，C’K的一個目錄就可以完全涵概，所以任一目錄同對應(yīng)事務(wù)T相比，均較大.

3.4 實例算法應(yīng)用分析

例 2：有一數(shù)據(jù)庫 D，包含 4 個事務(wù)表示為 T10、T20、T30、T40，support表示其支持度，T10={P1，P3，P4}，T20={P2，P3，P5}，T30={P1，P2，P3，P5}，T40={P2， P5}，最小支持度 min-sup=2.

按照經(jīng)典的Aprior算法對數(shù)據(jù)庫D進行掃描后得到C1，其中TSD分別包括{P1}、{P2}、{P3}、{P4}、{P5}五項，求解得到各自的support分別對應(yīng)為2、3、3、1、3.由min-sup=2，在C1中繼續(xù)掃描則需要刪除{P4}，即求得L1的 4 項分別包括{P1}、{P2}、{P3}、{P5}.對 L1掃描后，可得到上述 4 項各自的 support分別對應(yīng)為 2、3、3、3.繼續(xù)求 C2=L1∞L1，其分別包括{P1P2}、{P1P3}、{P1P5}、{P2P3}、{P2P5}、{P3P5}等 6 項，對其掃描得到各自的 support分別對應(yīng)為 1、2、1、2、3、2.由 min-sup=2，在 C2中繼續(xù)掃描后需要刪除{P1P2}、{P1P5}，剩余的即構(gòu)成了 L2，其內(nèi)在四項分別為{P1P3}、{P2P3}、{P2P5}、{P3P5}等 ，掃描后得到對應(yīng)的支持度分別為 2、2、3、2.繼續(xù)求解 C3=L2∞L2，求其結(jié)果僅包括{P2P3P5}，掃描后其支持度為2，符合min-sup要求，因此L3=C3，其結(jié)果也僅包括{P2P3P5}且支持度為2.

若執(zhí)行優(yōu)化的Apriori-B算法，其步驟可分為三步.第一步求解L1，對數(shù)據(jù)庫D掃描得到C’1，其四個事務(wù)的構(gòu)成分別為{P1}，{P3}，{P4}；{P2}，{P3}，{P5}；{P1}，{P2}，{P3}，{P5}；{P2}， {P5}等四項.對 C’1繼續(xù)掃描可得到 L1，其四個事務(wù)的構(gòu)成分別為{P1}、{P2}、{P3}、{P5}四項，對應(yīng) support分別為 2、3、3、3.

第二步求解 L2，先計算 C2=L1∞L1，其構(gòu)成包括{P1P2}、{P1P3}、{P1P5}、{P2P3}、{P2P5}、{P3P5}等六項.對 C2掃描后可以得到C’2，其內(nèi)在的四個事務(wù)的值分別為 {{P1P3}}、{{P2P3}{P2P5}{P3P5}}、{{P1P2}{P1P3}{P1P5}{P2P3}{P2P5}{P3P5}}、{{P2P5}}等四項.繼續(xù)對C’2掃描，結(jié)合最小支持度min-sup=2的要求，即可求得L2的四項其分別為{P1P3}、{P2P3}、{P2P5}、{P3P5}，對應(yīng)支持度分別是 2、2、3、2.

第三步求解 L3，首先計算 C3=L2∞L2，求得 C3僅包含一項{P2P3P5}，繼續(xù)對 C3掃描可得到 C’3.C’3包含兩個事務(wù)T20、T30，對應(yīng)的構(gòu)成值分別為{{P2P3P5}}、{{P2P3P5}}.以此類推，繼續(xù)掃描 C’3即可求出 L3，只含有一個對象{P2P3P5}，且其支持度為2.

經(jīng)對比分析后不難看出，應(yīng)用Apriori-B算法僅僅是在第一步掃描對象是原數(shù)據(jù)庫D，而在后續(xù)的第二和第三步中，掃描對象均為前一次所得到的候選數(shù)據(jù)庫C’k.并且可知，若k值不斷增大，同原數(shù)據(jù)庫D相比而言，前者要遠遠小于后者.如此來看，采用Apriori-B算法，確實可減少I/O時間，可以大幅提升算法效率.

3.5 算法效率實驗驗證

以亳州學(xué)院教學(xué)評價系統(tǒng)數(shù)據(jù)進行挖掘為例，實驗環(huán)境：Win7，eclipse，Java編程語言，計算機配置酷睿i5 3.0 GHz，內(nèi)存4 G，硬盤1 T.算法運行時長對比分析見圖1.經(jīng)典Apriori如①，Apriori-A如②，Apriori-B如③.從圖1的情況可觀測到①的線條始終位于②、③之上.運用改進后的Apriori-A算法、Apriori-B算法在事務(wù)數(shù)相等的情況下運行時間較經(jīng)典Apriori算法更短，效率更高.從事務(wù)數(shù)規(guī)模不斷增大的趨勢來看，算法效率改善的愈加明顯，算法優(yōu)化具有較強的應(yīng)用意義.

圖1 算法運行對比分析

4 結(jié)語

頻繁數(shù)據(jù)項集的生成是關(guān)聯(lián)規(guī)則挖掘的核心問題.Apriori—A算法思想是從刪除無效連接，以減少冗余的連接為前提條件，進而實現(xiàn)了減少剪枝步中的判斷量；Apriori—B算法則以候選事務(wù)數(shù)據(jù)庫替代原數(shù)據(jù)庫D，實現(xiàn)了大幅減少掃描次數(shù).經(jīng)定性分析和定量驗證，兩種優(yōu)化策略均在特定案例可以使之效率有效提升.但兩種優(yōu)化算法依然存在較為繁瑣的數(shù)據(jù)庫掃描操作，算法效率仍有較大的提升空間.