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

劉騁昊， 王靖亞

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

0 引言

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

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

1 傳統(tǒng)Apriori算法

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

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

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

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

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

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

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

挖掘步驟：

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

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

1.2 基本思想

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

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

輸出：D中的頻繁項(xiàng)集L。

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

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

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

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

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

}

(3)對(duì)L1到Lk取并集，最終得到頻繁項(xiàng)集L。

1.3 算法分析

該算法存在著兩個(gè)大問題：

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

K項(xiàng)事務(wù)集：事務(wù)集中的每個(gè)事務(wù)均含有K個(gè)項(xiàng)。

生成頻繁項(xiàng)集：頻繁項(xiàng)的所有非空子集的集合。

3.2 實(shí)現(xiàn)算法

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

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

輸出：D中頻繁項(xiàng)集L。

第一次掃描數(shù)據(jù)庫(kù)，生成多個(gè)事務(wù)集，最長(zhǎng)項(xiàng)K，每個(gè)數(shù)據(jù)集有mj個(gè)事務(wù)。

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

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

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

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

(1)掃描事務(wù)數(shù)據(jù)庫(kù)，對(duì)每個(gè)候選項(xiàng)計(jì)數(shù)得到候選1項(xiàng)集集合，如表2。

表2 候選1項(xiàng)集

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

表3 頻繁1項(xiàng)集

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

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

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

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

表4 候選2項(xiàng)集

表5 頻繁2項(xiàng)集

表6 頻繁3項(xiàng)集

4.2 從高維向低維掃描的Apriori算法計(jì)算過程

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

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

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

②選取下一個(gè)事務(wù)T4為候選項(xiàng)，因?yàn)門4包含于L31中，則跳過，選取下一個(gè)事務(wù)。以此類推，因?yàn)門8，T9支持度均小于最小支持度min_sup，舍去。

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

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

表8 2項(xiàng)事務(wù)集

4.3 算法效率比較分析

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

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

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

5 結(jié)語(yǔ)

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

［1］ 馬廷斌，徐芬.關(guān)聯(lián)規(guī)則挖掘中Apriori算法的研究與改進(jìn)［J］.蘭州工業(yè)高等專科學(xué)校學(xué)報(bào)，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è)計(jì)與實(shí)現(xiàn)［J］.電腦知識(shí)與技術(shù)，2008，13：684 －685.

［5］ 馬曉輝.一種基于關(guān)聯(lián)規(guī)則Apriori算法的改進(jìn)研究［J］.現(xiàn)代計(jì)算機(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］ 談麗，王建東.長(zhǎng)項(xiàng)優(yōu)先的產(chǎn)生算法——改進(jìn)的Apriori算法［J］.計(jì)算機(jī)與現(xiàn)代化，2007(8)：53－55.

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

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