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

羅冬梅

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

1．引言

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

數(shù)據(jù)關(guān)聯(lián)是數(shù)據(jù)庫(kù)中存在的一類重要的、可被發(fā)現(xiàn)的知識(shí)。若兩個(gè)或多個(gè)變量的取值之間存在某種規(guī)律性，就稱為關(guān)聯(lián)。關(guān)聯(lián)可分為簡(jiǎn)單關(guān)聯(lián)、時(shí)序關(guān)聯(lián)和因果關(guān)聯(lián)。關(guān)聯(lián)分析的目的是找出數(shù)據(jù)庫(kù)中隱藏的關(guān)聯(lián)網(wǎng)。有時(shí)并不知道數(shù)據(jù)庫(kù)中數(shù)據(jù)的關(guān)聯(lián)函數(shù)，即使知道也是不確定的，因此關(guān)聯(lián)分析生成的規(guī)則帶有可信度。關(guān)聯(lián)規(guī)則挖掘發(fā)現(xiàn)大量數(shù)據(jù)中項(xiàng)集之間有趣的關(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)域一個(gè)非常重要的技術(shù)，它是由 Agrawal、Imielinski、Swami 等人首先提出以解決事務(wù)數(shù)據(jù)庫(kù)分析等問題，是一種簡(jiǎn)單但很實(shí)用的數(shù)據(jù)挖掘方法。它是從大量數(shù)據(jù)中的項(xiàng)集之間發(fā)現(xiàn)有趣的關(guān)聯(lián)或相關(guān)，從而達(dá)到認(rèn)識(shí)事物客觀規(guī)律的技術(shù)方法。隨著對(duì)大量數(shù)據(jù)的不停收集與存儲(chǔ)，數(shù)據(jù)庫(kù)中挖掘關(guān)聯(lián)規(guī)則顯得越來(lái)越重要。

2．1． 算法思想

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

2．2． 算法描述

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

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

（2）為了產(chǎn)生頻繁k-項(xiàng)集構(gòu)成的集合Lk，預(yù)先生成一個(gè)候選頻繁k-項(xiàng)集的集合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時(shí)，pi=qi；當(dāng)i=k-1時(shí)，pk-1≠qk-1，則 P∪Q={p1，p2，……pk-2，pk-1，qk-1}是候選頻繁k-項(xiàng)集的集合Ck的子集。

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

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

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

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

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

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

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

數(shù)據(jù)挖掘?qū)嶒?yàn)步驟如下：

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

（1）選擇需分析的數(shù)據(jù)項(xiàng)目，將對(duì)應(yīng)數(shù)據(jù)記錄存放到挖掘?qū)嶒?yàn)表中。取出適用程序、辦案單位、案件來(lái)源、案值、立案日期、主辦人、協(xié)辦人、案件類型數(shù)據(jù)，存放到實(shí)驗(yàn)表中。

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

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

本實(shí)驗(yàn)中，選擇Apriori算法，使用逐層迭代找出頻繁項(xiàng)集。設(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)行說(shuō)明。

實(shí)驗(yàn)結(jié)果如下：

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

……

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

……

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

……

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

……

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

……

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

規(guī)則5：辦案單位為沙縣工商行政管理局的案件有820件，其中適用程序?yàn)橐话愠绦虻挠?09件，置信度為 0.99。說(shuō)明沙縣工商行政管理局已結(jié)案的案件適用程序基本為一般程序。

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

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

規(guī)則33：案值在5萬(wàn)元及5萬(wàn)元以下、類型為無(wú)照經(jīng)營(yíng)的案件有2488件，其中適用程序?yàn)橐话愠绦虻挠?268件，置信度為0.91。說(shuō)明我市已辦結(jié)的案件中近41%的案件為案值在5萬(wàn)元及5萬(wàn)元以下的無(wú)照經(jīng)營(yíng)案件，其中適用一般程序的占所有無(wú)照經(jīng)營(yíng)案件的80%左右。

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

3．結(jié)束語(yǔ)

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

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

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

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

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

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

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