劉騁昊， 王靖亞

(中國人民公安大學(xué)，北京 100038)

0 引言

數(shù)據(jù)挖掘的目的是從數(shù)據(jù)倉庫或數(shù)據(jù)集中存放的大量原始數(shù)據(jù)中提取人們感興趣的、隱含的、具有潛在應(yīng)用價值的信息和知識。數(shù)據(jù)挖掘算法可分為三大類—關(guān)聯(lián)規(guī)則算法、分類算法和聚類算法。其中關(guān)聯(lián)規(guī)則算法可支持間接數(shù)據(jù)挖掘，易處理變長的數(shù)據(jù)，且算法的性能可以提前預(yù)測，更為重要的是關(guān)聯(lián)規(guī)則算法的挖掘結(jié)果直觀易懂，所以，基于關(guān)聯(lián)規(guī)則的挖掘一直以來都受到眾多行業(yè)和業(yè)內(nèi)人士的青睞。

Apriori算法是最經(jīng)典的關(guān)聯(lián)規(guī)則的挖掘算法之一，1993年由R.Agrawal和R.Srikant針對購物籃問題而提出。Apriori算法的基本思想是重復(fù)掃描數(shù)據(jù)庫，找出頻繁項集，然后通過最小支持度和最小置信度進(jìn)行剪枝，最終得到關(guān)聯(lián)規(guī)則。該算法簡單易懂且挖掘結(jié)果能很好地表示數(shù)據(jù)庫中不同項集之間的關(guān)聯(lián)關(guān)系，但該算法在性能上存在著一定的缺陷。本文提出了一種對Apriori算法的改進(jìn)方法，并且證明了該算法可以有效提高傳統(tǒng)的Apriori算法的運算效率。

1 傳統(tǒng)Apriori算法

1.1 關(guān)聯(lián)規(guī)則挖掘的相關(guān)概念和步驟

設(shè)任務(wù)相關(guān)的數(shù)據(jù)D是數(shù)據(jù)庫事務(wù)的集合，其中每個事務(wù)T是項的集合，使得T包含于I。每一個事務(wù)有一個標(biāo)識符，稱作TID(Thing Identifier)。

項集：項的集合，包含k個項的項集稱為k—項集，設(shè)項集 I={i1，i2，…，ik}［1］。

項集的頻率：項集的出現(xiàn)頻率是包含項集的事務(wù)數(shù)，簡稱為項集的頻率、支持計數(shù)或計數(shù)。

支持度：support(X=＞Y)=P(X∪Y)，即X和Y這兩個項集在事務(wù)集D中同時出現(xiàn)的概率。

頻繁項集：如果項集的出現(xiàn)頻率大于或等于最小支持度，則稱為頻繁項集頻繁k—項集的集合通常記作Lk。

關(guān)聯(lián)規(guī)則：形如X=＞Y的蘊(yùn)涵式，其中設(shè)X是一個項集，即事務(wù)T包含X;X、Y中的項均包含于D，且 X∩Y=Φ。

挖掘步驟：

(1)找出所有頻率項集。即要求找出的項目集出現(xiàn)頻繁度必須大于或等于用戶自定義的最小支持度。

(2)由頻繁項集產(chǎn)生強(qiáng)關(guān)聯(lián)規(guī)則。即根據(jù)用戶規(guī)定的最小置信度來確定產(chǎn)生頻繁項集的取舍，從而確定強(qiáng)關(guān)聯(lián)規(guī)則。

1.2 基本思想

發(fā)現(xiàn)關(guān)聯(lián)規(guī)則的關(guān)鍵是頻繁項集的發(fā)現(xiàn)。Apriori算法推導(dǎo)頻繁項集的過程如下：

輸入：事務(wù)數(shù)據(jù)庫D，最小支持度min_sup。

輸出：D中的頻繁項集L。

(1)第一次掃描數(shù)據(jù)庫，找出滿足最小支持度的頻繁1—項集L1。

(2)For(k=2;Lk－1≠;k++)

{由Lk－1中所含的項自連接，產(chǎn)生候選k項集Ck;

掃描數(shù)據(jù)庫，計算這些候選集的支持度;

對候選K項集Ck進(jìn)行剪枝，刪除支持度小于最小支持度min_sup的項目，K項集Lk。

}

(3)對L1到Lk取并集，最終得到頻繁項集L。

1.3 算法分析

該算法存在著兩個大問題：

(1)算法運算過程中，通過頻繁項集自連接產(chǎn)生了大量的候選集，即由K頻繁項集自連接生成K+1候選集，使候選集的數(shù)量呈指數(shù)倍增長，如果頻繁項集中的項數(shù)過多，則產(chǎn)生候選集所帶來的時間和空間上的開銷是非常驚人的;

(2)該算法要求多次掃描數(shù)據(jù)庫，每得到一個頻繁項集就要掃描一次數(shù)據(jù)庫，由此可知，最大頻繁項集中有多少項就需要對事物數(shù)據(jù)庫掃描多少次，對一些大型數(shù)據(jù)庫而言，掃描數(shù)據(jù)庫所帶來的時間開銷和I/O負(fù)載過大。

2 已有的Apriori算法改進(jìn)及其分析

針對Apriori算法的以上缺點和不足，引發(fā)了許多學(xué)者對Apriori算法進(jìn)行改進(jìn)。改進(jìn)的兩個主要方向是：

(1)減少候選集的生成數(shù)量，提高空間效率;

(2)減少數(shù)據(jù)庫掃描次數(shù)或每次掃描的事務(wù)個數(shù)，提高時間效率。其中具有代表性的方法：

①基于散列的方法：1995年，由Park等人提出［2］。該方法通過引入hash技術(shù)來提高生成頻繁2項集的效率并在循環(huán)過程中對事務(wù)進(jìn)行消減，從而改善算法的運行效率，但對2階候選集沒有作用。

②基于劃分的方法：1995年，由Savasere等人提出［3］。該方法把數(shù)據(jù)庫從邏輯上劃分成幾個互不相交的塊，算法分別對每個分塊進(jìn)行頻繁項集的搜索，然后把產(chǎn)生的頻繁項集合并生成所有可能的頻繁項集，再對生成的頻繁項集進(jìn)行剪枝。該方法的優(yōu)點在于只需兩次掃描整個事務(wù)數(shù)據(jù)庫，但對數(shù)據(jù)庫劃分時要求過高。

③基于抽樣的方法：1996年，由 Toivonen提出［4］，該方法首先對數(shù)據(jù)庫進(jìn)行采樣，其次對樣本數(shù)據(jù)庫進(jìn)行挖掘從中得到所需的規(guī)則，然后再將其帶入數(shù)據(jù)庫中進(jìn)行驗證。該方法顯著提高了算法的運行效率，但有時生成的結(jié)果誤差較大。

④0－1矩陣的方法［5］：該方法通過建立0－1 矩陣將項集和事務(wù)號聯(lián)系起來，得到所有項目的關(guān)聯(lián)組合，然后產(chǎn)生頻繁項集。該方法只需掃描一次數(shù)據(jù)庫，減少了數(shù)據(jù)庫的掃描次數(shù)。但在挖掘具有大量頻繁項集和長頻繁項集或低支持度的數(shù)據(jù)集時，由于生成的0－1矩陣過多，會使其性能下降。

⑤基于頻繁模式樹的方法：2000年，由J.Han等提出［6］，該方法是對數(shù)據(jù)庫做第一遍掃描后，將頻繁項目集壓縮為一棵頻繁模式樹，然后對生成的頻繁樹分化成多個條件庫，對每一個條件庫逐一進(jìn)行挖掘，產(chǎn)生關(guān)聯(lián)規(guī)則。該方法不使用候選集，且數(shù)據(jù)庫只需掃描2次，顯著提高了算法的運行效率，但頻繁樹生成和遍歷，也將消耗大量的時間和空間。

3 一種從高維向低維掃描的Apriori改進(jìn)算法

3.1 算法原理及相關(guān)定義

最長項優(yōu)先原則［7］：所含項目數(shù)最多的事務(wù)擁有優(yōu)先被處理權(quán)。

Apriori性質(zhì)［8］：頻繁項集的所有非空子集也都必須是頻繁的。由這個性質(zhì)可知［9］，如果項集I不滿足最小支持度min_sup，則I不是頻繁的，即P(A)＜min_sup;如果向項集I添加項A，其合并項集A∪I不會比項集I的出現(xiàn)頻率大，所以項集A∪I也不是頻繁的，即P(A∪I)＜min_sup。

K項事務(wù)集：事務(wù)集中的每個事務(wù)均含有K個項。

生成頻繁項集：頻繁項的所有非空子集的集合。

3.2 實現(xiàn)算法

該改進(jìn)算法根據(jù)最長項優(yōu)先原則和Apriori性質(zhì)，從高維向低維逐層掃描過程。

輸入：事務(wù)數(shù)據(jù)庫D，最小支持度閾值min_sup。

輸出：D中頻繁項集L。

第一次掃描數(shù)據(jù)庫，生成多個事務(wù)集，最長項K，每個數(shù)據(jù)集有mj個事務(wù)。

4 傳統(tǒng)的Apriori算法與改進(jìn)算法的示例比較

下面給出的信息表中i1到i5共5個屬性，最小支持度 min_sup=2，事件集 T={T1，T2，…，T9}共 9個事件。我們現(xiàn)在對這個樣本數(shù)據(jù)庫采用本文中提供的改進(jìn)Apriori算法進(jìn)行演算。樣本數(shù)據(jù)庫如表1所示。

表1 事務(wù)數(shù)據(jù)集T

4.1 傳統(tǒng)Apriori算法計算過程

(1)掃描事務(wù)數(shù)據(jù)庫，對每個候選項計數(shù)得到候選1項集集合，如表2。

表2 候選1項集

(2)將支持度計數(shù)結(jié)果與最小支持度進(jìn)行比較，保留滿足最小支持度的項，得到頻繁1項集，如表3所示。

表3 頻繁1項集

(3)自連接頻繁1項集，得到候選2項集，如表4。

(4)將支持度計數(shù)結(jié)果與最小支持度進(jìn)行比較，保留滿足最小支持度的項，得到頻繁2項集，如表5。

(5)依次，連續(xù)剪枝，得到頻繁3項式集合，如表6。

(6)對表3，表5，表6取并集，得到最終的頻繁項集L。

表4 候選2項集

表5 頻繁2項集

表6 頻繁3項集

4.2 從高維向低維掃描的Apriori算法計算過程

(1)預(yù)處理事務(wù)數(shù)據(jù)庫，根據(jù)每個事務(wù)所含項數(shù)不同，劃分為不同的數(shù)據(jù)集。生成3項事務(wù)集如表7和2項事務(wù)集如表8。

(2)由最長項優(yōu)先原則，先處理3項事務(wù)集，所含事務(wù)個數(shù)=4，從TID號小的開始處理。

① 選取事務(wù)T1中所含項{i1，i2，i5}作為候選3項式，掃描該事務(wù)數(shù)據(jù)集得其支持度為2。由最小支持度min_sup=2，可知該候選集為頻繁3項式，生成該頻繁項的所有非空子集，取其并集，得到生成頻繁項集 L31={{i1，i2，i5}，{i1，i2}，{i2，i5}，{i1，i5}，{i1}，{i2}，{i5}}。

②選取下一個事務(wù)T4為候選項，因為T4包含于L31中，則跳過，選取下一個事務(wù)。以此類推，因為T8，T9支持度均小于最小支持度min_sup，舍去。

③合并所有3項事務(wù)集的生成頻繁項集，得到3項事務(wù)集的頻繁項集：

(3)處理2項事務(wù)集，所含事務(wù)個數(shù)=5，選取T2中所含的項為候選項，判斷該候選項是否是L3中元素，如果是，跳過，選取下一事務(wù);如果不是，掃描2項事務(wù)集，支持度為1，舍去。以此類推，得生成頻繁項集 L22={{i2，i3}，{i2}，{i3}}，L23={{i1，i3}，{i1}，{i3}}。取并集，則2項集頻繁項集 L2={{i2，i3}，{i1，i3}，{i1}，{i2}，{i3}}。

(4)取L2和L3的并集，得到最終的頻繁集L={{i1，i2，i5}，{i1，i2}，{i2，i5}，{i2，i3}，{i1，i3}，{i1}，{i2}，{i3}，{i5}}。

表7 3項事務(wù)集

表8 2項事務(wù)集

4.3 算法效率比較分析

通過上述實例比較，我們可以發(fā)現(xiàn)從高維向低維Apriori算法有著顯著的優(yōu)點。

(1)空間效率角度分析：從高維向低維逐層掃描，剔除了傳統(tǒng)Apriori算法中最終的頻繁項集中不會出現(xiàn)的候選項，減少了額外空間的占用量;且算法的預(yù)處理階段，將原有的數(shù)據(jù)庫劃分為不同的數(shù)據(jù)集，再對每個數(shù)據(jù)集分別進(jìn)行處理，使算法的額外空間占用量只等于原始數(shù)據(jù)庫的大小，與傳統(tǒng)Apriori算法中候選集呈指數(shù)倍增長，使額外空間占有量的快速增長相比，提高了算法的空間效率。

(2)時間效率角度分析：該算法中只有首次是對整個事務(wù)數(shù)據(jù)庫進(jìn)行掃描，除此之外每次掃描的都是含有相同項數(shù)的事務(wù)數(shù)據(jù)集，這大大減少了掃描的事務(wù)個數(shù)，縮短了掃描時間;再次，對于已存在頻繁集中的項目集，則可以直接跳過，不必再重復(fù)掃描事務(wù)集，從而減少掃描次數(shù)，最終達(dá)到提高算法時間效率的目的。

5 結(jié)語

本文在傳統(tǒng)的Apriori算法的基礎(chǔ)上，提出了一種新的改進(jìn)算法，該算法將原始的事務(wù)數(shù)據(jù)庫劃分為具有相同數(shù)量項的事務(wù)集，減少了對數(shù)據(jù)庫的掃描次數(shù)和每次掃描事務(wù)的個數(shù);快速查找到頻繁項集，剔除頻繁項集不包含的候選項，減少中間項的生成數(shù)量，因此該算法在時間效率和空間效率上都得到了一定的提高。

［1］ 馬廷斌，徐芬.關(guān)聯(lián)規(guī)則挖掘中Apriori算法的研究與改進(jìn)［J］.蘭州工業(yè)高等專科學(xué)校學(xué)報，2010，17(1)：13－15.

［2］ Sing Li.Making P2P interoperable：The JXTA command shell［M］.Bimaingham：Wrox Press，2001.

［3］ Jameela A J，Nader M，Hong Jiang.Agent-based parallel computing in java proof of concept［R］.Technical Report TR-UNL-CSE-2001-1004，Slimmer，2001：5 －12.

［4］ 包林玉，袁平，彭春燕，等.基于JMS和XML的異構(gòu)數(shù)據(jù)集成技術(shù)的設(shè)計與實現(xiàn)［J］.電腦知識與技術(shù)，2008，13：684 －685.

［5］ 馬曉輝.一種基于關(guān)聯(lián)規(guī)則Apriori算法的改進(jìn)研究［J］.現(xiàn)代計算機(jī)，2011，3(6).

［6］ Han J，Pei J，Yin Y.Mining frequent patterns without candidate generation［C］∥Proceedings of the Special Interest Group on Management of Data，2000：1－12.

［7］ 談麗，王建東.長項優(yōu)先的產(chǎn)生算法——改進(jìn)的Apriori算法［J］.計算機(jī)與現(xiàn)代化，2007(8)：53－55.

［8］ 綦孝姬，于紅，劉溪婧，等.基于候選項目集特性的改進(jìn)Apriori算法研究［J］.鄭州大學(xué)學(xué)報，2009，41(1)：36－39.

［9］ 錢雪忠，孔芳.關(guān)聯(lián)規(guī)則挖掘中對Apriori算法的研究［J］.計算機(jī)工程與應(yīng)用，2008，44(17)：138 －140.