Apriori關(guān)聯(lián)挖掘的研究與應(yīng)用

羅冬梅

（ 武夷學(xué)院 計算機公共教研室，福建 武夷山 354300 ）

1．引言

近些年來，隨著數(shù)據(jù)的大量積累以及市場競爭對信息與知識的迫切需求，數(shù)據(jù)挖掘已成為一個非常活躍的研究課題，它在各領(lǐng)域中得到了大力推廣及應(yīng)用。數(shù)據(jù)挖掘[1]（Data Mining）就是從大量的、不完全的、有噪聲的、模糊的、隨機的數(shù)據(jù)中，提取隱含在其中的、人們事先不知道的、但又是潛在有用的信息和知識的過程。簡單地說, 數(shù)據(jù)挖掘是從大量數(shù)據(jù)中提取或挖掘知識。數(shù)據(jù)挖掘的方法有很多，其中應(yīng)用最廣泛的方法之一就是關(guān)聯(lián)規(guī)則挖掘算法。

數(shù)據(jù)關(guān)聯(lián)是數(shù)據(jù)庫中存在的一類重要的、可被發(fā)現(xiàn)的知識。若兩個或多個變量的取值之間存在某種規(guī)律性，就稱為關(guān)聯(lián)。關(guān)聯(lián)可分為簡單關(guān)聯(lián)、時序關(guān)聯(lián)和因果關(guān)聯(lián)。關(guān)聯(lián)分析的目的是找出數(shù)據(jù)庫中隱藏的關(guān)聯(lián)網(wǎng)。有時并不知道數(shù)據(jù)庫中數(shù)據(jù)的關(guān)聯(lián)函數(shù)，即使知道也是不確定的，因此關(guān)聯(lián)分析生成的規(guī)則帶有可信度。關(guān)聯(lián)規(guī)則挖掘發(fā)現(xiàn)大量數(shù)據(jù)中項集之間有趣的關(guān)聯(lián)關(guān)系或相關(guān)聯(lián)系[2]。

2．關(guān)聯(lián)規(guī)則挖掘Apriori算法

關(guān)聯(lián)規(guī)則挖掘是數(shù)據(jù)挖掘領(lǐng)域一個非常重要的技術(shù)，它是由 Agrawal、Imielinski、Swami 等人首先提出以解決事務(wù)數(shù)據(jù)庫分析等問題，是一種簡單但很實用的數(shù)據(jù)挖掘方法。它是從大量數(shù)據(jù)中的項集之間發(fā)現(xiàn)有趣的關(guān)聯(lián)或相關(guān)，從而達(dá)到認(rèn)識事物客觀規(guī)律的技術(shù)方法。隨著對大量數(shù)據(jù)的不停收集與存儲，數(shù)據(jù)庫中挖掘關(guān)聯(lián)規(guī)則顯得越來越重要。

2．1． 算法思想

Apriori算法是一種最有影響的挖掘布爾關(guān)聯(lián)規(guī)則頻繁項集的算法。Apriori算法利用幾次迭代來計算數(shù)據(jù)庫中所有滿足最小支持度的所有頻繁項集，它的主要工作就是尋找k-項集。第i次迭代計算出所有頻繁i項集（包含i個元素的項集）。首先，找出頻繁1-項集的集合，記作L1。L1用于找頻繁2-項集的集合 L2，而 L2用于找 L3，如此下去，直到不能找到頻繁k-項集。找每個Lk需要一次數(shù)據(jù)庫掃描。

2．2． 算法描述

Apriori 算法的具體實現(xiàn)過程：

（1）通過第一趟掃描事務(wù)數(shù)據(jù)庫D計算出所有1-項集的支持度，從而得到滿足最小支持度 s%的頻繁1-項集構(gòu)成的集合L1。

（2）為了產(chǎn)生頻繁k-項集構(gòu)成的集合Lk，預(yù)先生成一個候選頻繁k-項集的集合Ck。若P，Q∈Lk-1，P={p1，p2，……pk-2，pk-1}，Q={q1，q2，……qk-2，qk-1}，并且當(dāng)1≤i＜k-1時，pi=qi；當(dāng)i=k-1時，pk-1≠qk-1，則 P∪Q={p1，p2，……pk-2，pk-1，qk-1}是候選頻繁k-項集的集合Ck的子集。

（3）由于Ck是Lk的超集，可能有些元素不是頻繁的，當(dāng)Ck很龐大時會帶來巨大的計算量。為了減少Ck的規(guī)模，Apriori算法遵從下列性質(zhì)：任何非頻繁的（k-1）項集不是頻繁k-項集的子集。所以，當(dāng)候選k-項集的某個（k-1）子集不是Lk-1中的成員時，則該候選頻繁項集不可能是頻繁的，可以從 Ck中移去，這就是Apriori剪枝思想。

（4）通過單趟掃描事務(wù)數(shù)據(jù)庫D，計算Ck中各個項集的支持度，將Ck中不滿足最小支持度s%的項集剔除，形成由頻繁k項集構(gòu)成的集合Lk。

通過迭代循環(huán)，重復(fù)上述步驟（1）～（4），直到不能產(chǎn)生新的頻繁項集的集合為止。

2．3． 算法應(yīng)用

抽取“福建省工商行政管理查處經(jīng)濟違法違章案件管理系統(tǒng)”中截止至2010年6月30日前的已辦結(jié)案件數(shù)據(jù)共7667條，并選取部分相關(guān)字段如表1所示，進(jìn)行數(shù)據(jù)的關(guān)聯(lián)規(guī)則挖掘?qū)嶒灐?/p>

表1 案件基本數(shù)據(jù)

本實驗?zāi)康氖菣z驗案件管理系統(tǒng)的數(shù)據(jù)中，適用程序、辦案單位、案件來源、案值、立案日期、主辦人、協(xié)辦人、案件類型這 8個數(shù)據(jù)項間是否存在關(guān)聯(lián)規(guī)則，若存在，關(guān)聯(lián)規(guī)則是怎樣的。

數(shù)據(jù)挖掘?qū)嶒灢襟E如下：

第一步 準(zhǔn)備數(shù)據(jù)

（1）選擇需分析的數(shù)據(jù)項目，將對應(yīng)數(shù)據(jù)記錄存放到挖掘?qū)嶒灡碇小Ｈ〕鲞m用程序、辦案單位、案件來源、案值、立案日期、主辦人、協(xié)辦人、案件類型數(shù)據(jù)，存放到實驗表中。

（2）將實驗表內(nèi)數(shù)據(jù)按關(guān)聯(lián)規(guī)則挖掘要求進(jìn)行規(guī)范化處理；將案值（數(shù)值型的數(shù)據(jù)類型）進(jìn)行離散化處理；將立案日期（日期型）的數(shù)據(jù)處理成枚舉型。具體而言，把案值分成 30個 bin；將立案日期數(shù)據(jù)由日期型轉(zhuǎn)換成枚舉型{200611，200612，200701，200702，200703，200704…}

第二步 選擇算法進(jìn)行數(shù)據(jù)挖掘

本實驗中，選擇Apriori算法，使用逐層迭代找出頻繁項集。設(shè)置度量標(biāo)準(zhǔn)為置信度，選擇顯示100條關(guān)聯(lián)規(guī)則中，共出現(xiàn)39條最優(yōu)關(guān)聯(lián)規(guī)則，關(guān)聯(lián)規(guī)則按降序排列，置信度區(qū)間為1至0.9，抽取其中的規(guī)則1、5、8、11、33進(jìn)行說明。

實驗結(jié)果如下：

規(guī)則 1 案件來源=檢查 案件類型=廣告違法1000 ==> 案值='(-inf-5]' 998 conf:(1)；

……

規(guī)則 5 辦案單位=沙縣工商行政管理局 820==> 適用程序=一般程序 809 conf:(0.99)；

……

規(guī)則 8 案件來源=檢查 案件類型=合同違法811 ==> 案值='(-inf-5]' 791 conf:(0.98)；

……

規(guī)則 11 案件來源=檢查 5732 ==> 案值='(-inf-5]' 5573 conf:(0.97)

……

規(guī)則 33 案值='(-inf-5]' 案件類型=無照經(jīng)營2488 ==> 適用程序=一般程序 2268 conf:(0.91)

……

規(guī)則1：為最優(yōu)規(guī)則，可以從中看出案件來源為檢查，案件類型為廣告違法的案件有1000件，其中案值在5萬元及5萬元以下的有998件，置信度為1。說明全市已結(jié)案的案件中有近15%為廣告違法案件，案件來源為檢查，案值基本在5萬元及5萬元以下。

規(guī)則5：辦案單位為沙縣工商行政管理局的案件有820件，其中適用程序為一般程序的有809件，置信度為 0.99。說明沙縣工商行政管理局已結(jié)案的案件適用程序基本為一般程序。

規(guī)則8：案件來源為檢查，案件類型為合同違法的案件有811件，其中案值在5萬元及5萬元以下的有 791件，置信度為 0.98。說明合同違法案件來源為檢查，案件基本在5萬元及5萬元以下。

規(guī)則11：案件來源為檢查的案件有5732件，其中案值在5萬元及5萬元以下的有5573件，置信度為 0.97。說明我市已結(jié)案的案件中，大多數(shù)案件來源為檢查，并且案件在5萬元及5萬元以下。

規(guī)則33：案值在5萬元及5萬元以下、類型為無照經(jīng)營的案件有2488件，其中適用程序為一般程序的有2268件，置信度為0.91。說明我市已辦結(jié)的案件中近41%的案件為案值在5萬元及5萬元以下的無照經(jīng)營案件，其中適用一般程序的占所有無照經(jīng)營案件的80%左右。

通過以上分析結(jié)果，可以看出三明市工商系統(tǒng)查處的案件中，案件規(guī)模都比較小，案值基本在 5萬元及 5萬元以下，其中，無照經(jīng)營案件、廣告違法案件、合同違法案件所占比例較大。沙縣工商行政管理局、永安市工商行政管理局所辦理的案件適用一般程序比例占已辦理案件的90%以上。

3．結(jié)束語

關(guān)聯(lián)規(guī)則挖掘用于尋找給定數(shù)據(jù)集中項之間的有趣的關(guān)聯(lián)或相關(guān)關(guān)系，揭示數(shù)據(jù)項間的未知的依賴關(guān)系，根據(jù)所挖掘的關(guān)聯(lián)關(guān)系，可以從一個數(shù)據(jù)對象信息來推斷另一個數(shù)據(jù)對象的信息。Apriori算法是一種找頻繁項集的基本算法，它存在兩大缺點：可能產(chǎn)生大量的候選集，以及可能需要重復(fù)掃描數(shù)據(jù)庫。針對Apriori算法存在的缺點，人們對Apriori算法進(jìn)行了多方面的改進(jìn)，這些算法大多是以Apriori為核心，或是其變形，或是其擴展，如增量更新算法[3][4]、并行算法等[5][6]。

[1] 彭儀普，熊擁軍．關(guān)聯(lián)挖掘在文獻(xiàn)借閱歷史數(shù)據(jù)分析中的應(yīng)用[J]．情報技術(shù)，2005，（8）：40-44．

[2] Jiawei Han, Micheline Kamber．?dāng)?shù)據(jù)挖掘概念與技術(shù)[M]．范明，孟小峰，譯．北京：機械工業(yè)出版社，2002：149-178．

[3] 孫浩，趙霽．一種關(guān)聯(lián)規(guī)則增量更新算法[J]．系統(tǒng)工程與電子技術(shù)，2004，（5）．

[4] 李銘蔡，慶生．一個高效的關(guān)聯(lián)規(guī)則增量式更新算法[J]．計算機工程與應(yīng)用，2005，（5）．

[5] 王運峰，張蕾，韓紀(jì)富，等．?dāng)?shù)據(jù)庫中關(guān)聯(lián)規(guī)則的并行挖掘算法[J]．計算機工程與應(yīng)用，2001，（16）．

[6] 林偉偉，張志立，齊德昱．基于網(wǎng)格的分布并行計算策略[J]．計算機工程， 2006，（9）．