顧　瑋

（徐州高等師范學(xué)校　徐州　221116）

?

關(guān)聯(lián)規(guī)則中幾種算法的研究

顧瑋

（徐州高等師范學(xué)校徐州221116）

摘要目前，研究人員投入了大量的精力和時(shí)間用來(lái)研究關(guān)聯(lián)規(guī)則挖掘算法，因?yàn)樗惴ㄊ顷P(guān)聯(lián)規(guī)則的核心，關(guān)聯(lián)規(guī)則中最著名最經(jīng)典的算法是Apriori算法。隨著研究的不斷投入，從時(shí)間、空間和成本上來(lái)考慮，算法的效率在不斷的提高，從寬度優(yōu)先挖掘算法到深度優(yōu)先挖掘算法，從只挖掘頻繁項(xiàng)集到改進(jìn)的頻集算法，關(guān)聯(lián)規(guī)則挖掘算法的效率在逐步提高。

關(guān)鍵詞數(shù)據(jù)挖掘關(guān)聯(lián)規(guī)則Apriori算法

所謂關(guān)聯(lián)，反映的是一個(gè)事件和其他事件之間依賴或關(guān)聯(lián)的知識(shí)。在提出了關(guān)聯(lián)規(guī)則的挖掘問(wèn)題之后，對(duì)該問(wèn)題的研究就開始著手，并取得了很大的發(fā)展。至目前為止主要的研究方向?yàn)椋?/p>

一、多循環(huán)方式挖掘算法

這種算法的核心是“層次算法”。算法的過(guò)程如下：先把整個(gè)挖掘過(guò)程分為若干個(gè)層，然后再各個(gè)層次進(jìn)行挖掘，每個(gè)層次都挖掘完成后，組合成最后的挖掘結(jié)果。典型算法包括Agrawai等人提出的Apriori、AIS算法，Park等人提出的DHP算法，Toivonen提出的FP-growth

二、并行/分布式關(guān)聯(lián)規(guī)則挖掘算法

一般在數(shù)據(jù)挖掘要處理的數(shù)據(jù)非常巨大的時(shí)候采用該算法，隨著網(wǎng)絡(luò)技術(shù)飛速發(fā)展，數(shù)據(jù)庫(kù)的存儲(chǔ)模式也逐漸向分布式存儲(chǔ)模式發(fā)展，因此分布式關(guān)聯(lián)規(guī)則算法變得更為重要。其主要算法包括CD、IDD、PDM、FPM和HPA等。

1、增量式更新挖掘算法

這種算法包含兩種情況：

（1）數(shù)據(jù)庫(kù)中的記錄發(fā)生變化時(shí)，例如進(jìn)行刪除、增加或修改等更新；

（2）在關(guān)聯(lián)規(guī)則的度量發(fā)生改變時(shí)的更新。度量包括支持度、置信度、興趣度等。例如馮玉才提出的IUAPIUA算法。

2、多層關(guān)聯(lián)規(guī)則挖掘算法

這種算法主要是根據(jù)概念層的每個(gè)抽象層上定義最小支持度聞值的特性，采用多種策略，挖掘多層關(guān)聯(lián)規(guī)則。區(qū)別于前面基于支持度——可信度的方法。典型的算法包括：Han等提出的ML_T2L1算法，R.Srikant等提出的Cumulate、Stratify算法等等。

3、基于概念格的關(guān)聯(lián)規(guī)則的挖掘算法

這種算法在數(shù)據(jù)挖掘中的應(yīng)用的非常廣泛，當(dāng)然也取得了非常豐碩的成績(jī)。典型的算法包括：Godin等提出的概念格模型提取蘊(yùn)含規(guī)則的方法；胡可云在Godin算法的基礎(chǔ)上，提出了更有效的購(gòu)物籃分析的關(guān)聯(lián)規(guī)則算法等。

4、多值關(guān)聯(lián)規(guī)則挖掘算法

將多值屬性的值劃分為多個(gè)區(qū)間，每個(gè)區(qū)間作為一個(gè)屬性，將類別屬性的每一個(gè)類別當(dāng)做一個(gè)屬性。這種算法是將多值關(guān)聯(lián)規(guī)則挖掘問(wèn)題轉(zhuǎn)化為布爾型關(guān)聯(lián)規(guī)則挖掘問(wèn)題。

5、Apriori算法

關(guān)聯(lián)規(guī)則的算法非常多，其中最為經(jīng)典的算法是Apriori算法，它是挖掘布爾關(guān)聯(lián)規(guī)則頻繁項(xiàng)目集的算法，這種算法本身有著很多缺陷，因此后來(lái)很多學(xué)者都對(duì)該算法提出了各種改進(jìn)算法。

Apriori算法是首先尋找給定數(shù)據(jù)集合中的頻繁項(xiàng)集，通過(guò)頻繁項(xiàng)集生成強(qiáng)關(guān)聯(lián)規(guī)則。尋找頻繁項(xiàng)集步驟的核心在于，用前一次掃描數(shù)據(jù)庫(kù)的結(jié)果產(chǎn)生本次掃描候選項(xiàng)目集，這樣可以減少候選數(shù)據(jù)項(xiàng)集的數(shù)量，提高搜索的效率。任何頻繁項(xiàng)集的所有子集一定是頻繁項(xiàng)集是Apriori算法的核心思想。

Apriori算法使用的是一種逐層搜索的迭代方法，即“K-1項(xiàng)集”用于搜索“K項(xiàng)集”；首先找出頻繁“1項(xiàng)集”的集合，該集合記作L1。L1用來(lái)去尋找頻繁“2項(xiàng)集”的集合L2，以此類推，L2又用來(lái)尋找頻繁“3項(xiàng)集”的集合L3，如此下去，直到不能找到“K項(xiàng)集”。需要注意的是，挖掘每個(gè)Lk都需要對(duì)整個(gè)數(shù)據(jù)庫(kù)進(jìn)行一次掃描。

Apriori算法的描述如下：

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

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

Aprior算法的偽代碼如下：

其中，Apriori-gen函數(shù)的參數(shù)為L(zhǎng)k-1，即所有長(zhǎng)度為k-1的頻繁項(xiàng)集，結(jié)果返回含有k個(gè)項(xiàng)目的候選項(xiàng)集Ck。

6、改進(jìn)的Apriori算法

Apriori算法利用其性質(zhì)來(lái)生成候選項(xiàng)集，大大壓縮了頻繁集的大小，取得了很好的性能，但還存在以下缺點(diǎn)：

（1）可能產(chǎn)生大量的候選集。迭代過(guò)程在內(nèi)存中產(chǎn)生、處理和保存候選頻繁項(xiàng)集，因此會(huì)產(chǎn)生非常大的數(shù)據(jù)，導(dǎo)致算法在廣度和深度上的適應(yīng)性很差。

（2）數(shù)據(jù)庫(kù)掃描的次數(shù)太多。A每次尋找k頻繁項(xiàng)目及時(shí)，都需要對(duì)數(shù)據(jù)庫(kù)進(jìn)行一次掃描，用來(lái)獲得候選項(xiàng)目集的支持度，一最大頻繁項(xiàng)集的長(zhǎng)度為N時(shí)，共需要掃描N次數(shù)據(jù)庫(kù)，耗費(fèi)的時(shí)間太長(zhǎng)，在實(shí)際應(yīng)用中經(jīng)常需要挖掘很長(zhǎng)的模式，多次掃描數(shù)據(jù)庫(kù)帶來(lái)巨大開銷。

7、基于劃分的Apriori算法

為了提高該算法的挖掘效果，本文提出了一種改進(jìn)的算法——基于劃分的Apriori改進(jìn)算法。共分為四個(gè)主要部分：

第一部分，對(duì)數(shù)據(jù)庫(kù)進(jìn)行劃分，劃分成n個(gè)規(guī)模大小相當(dāng)?shù)膮^(qū)段。

第二部分，對(duì)這n個(gè)區(qū)段進(jìn)行單獨(dú)計(jì)算，產(chǎn)生n個(gè)區(qū)域性的頻繁項(xiàng)目集（潛在的）。

第三部分，根據(jù)這些區(qū)域性頻繁項(xiàng)目集找出整個(gè)數(shù)據(jù)庫(kù)中真正的頻繁項(xiàng)集。

第四部分，在對(duì)整個(gè)數(shù)據(jù)庫(kù)做一次掃描，計(jì)算每個(gè)候選頻繁項(xiàng)目的實(shí)際支持度，最后得到所有的頻繁項(xiàng)目集。

這種基于劃分的Apriori算法在挖掘數(shù)據(jù)的過(guò)程中，只需要掃描兩次數(shù)據(jù)庫(kù)，在第一次完成數(shù)據(jù)庫(kù)掃描時(shí)會(huì)產(chǎn)生潛在的頻繁項(xiàng)集，確保了第二次掃描的實(shí)際支持度，而且不會(huì)受到數(shù)據(jù)量增加的影響，它的核心思想是劃分多個(gè)模塊，產(chǎn)生的項(xiàng)目集都是獨(dú)立的，之后再進(jìn)行項(xiàng)目集的合并，從而產(chǎn)生面向全局的候選頻繁項(xiàng)目集，所以這種基于劃分的Apriori算法對(duì)數(shù)據(jù)挖掘的效率有了很大的提高。

8、DHP算法

經(jīng)典的Apriori算法是一種逐層搜索的迭代方法，要產(chǎn)生頻繁項(xiàng)集必須對(duì)整個(gè)數(shù)據(jù)庫(kù)進(jìn)行一次掃描，結(jié)合產(chǎn)生的頻繁項(xiàng)集產(chǎn)生下一層候選集。而DHP算法是以Apriori算法為基礎(chǔ)，另外加入了哈希表架構(gòu)，通過(guò)利用Hash function過(guò)濾非頻繁候選集，在對(duì)數(shù)據(jù)庫(kù)進(jìn)行掃描，計(jì)算出沒(méi)有過(guò)濾的頻繁候選集，這樣可以減少候選集的數(shù)目，更加提高了搜索效率。

9、FP-tree算法

FP-tree算法其實(shí)和Apriori算法都是尋找頻繁項(xiàng)集的算法，但是FP-tree是不產(chǎn)生候選集而直接生成頻繁項(xiàng)集的算法，該算法直接將事務(wù)數(shù)據(jù)庫(kù)壓縮成一棵頻繁模式樹，通過(guò)這棵樹可以有效的產(chǎn)生關(guān)聯(lián)規(guī)則。其算法思想為：先設(shè)定最小支持度的閾值，再利用此閾值進(jìn)行篩選。假如事務(wù)數(shù)據(jù)庫(kù)比較龐大，也可以結(jié)合基于劃分的方法實(shí)現(xiàn)。這種算法與Apriori算法相比，只需要對(duì)事務(wù)數(shù)據(jù)庫(kù)進(jìn)行二次掃描，不會(huì)產(chǎn)生大量候選集，在效率上有很大的提高。

隨著關(guān)聯(lián)規(guī)則挖掘新的算法的提出，問(wèn)題的定義和問(wèn)題背景也不相同，關(guān)聯(lián)規(guī)則的應(yīng)用范圍，最主要是包括數(shù)據(jù)庫(kù)中對(duì)數(shù)據(jù)的判斷是不是有價(jià)值的，是不是存在可以相互依存的關(guān)系。目前的研究主要集中在基本關(guān)聯(lián)規(guī)則挖掘、復(fù)雜類型關(guān)聯(lián)規(guī)則挖掘、針對(duì)關(guān)聯(lián)規(guī)則評(píng)價(jià)的研究以及并行挖掘算法和增量挖掘算法等等。

參考文獻(xiàn)

［1］陳京民等著.數(shù)據(jù)倉(cāng)庫(kù)與數(shù)據(jù)挖掘技術(shù)［M］.電子工業(yè)出版社，2002.8：1-55.

［2］范明，孟小峰.數(shù)據(jù)挖掘概念與技術(shù)［M］.北京：機(jī)械工業(yè)出版社，2006：26-27，32.

［3］邵峰晶，于忠清.數(shù)據(jù)挖掘原理與算法［M］.北京：中國(guó)水利水電出版社，2003.

［4］曹露燕.葉書建.聚類分析在高校教務(wù)系統(tǒng)中的應(yīng)用研究［J］福建電腦2010（3）.

［5］劉建友.決策樹在高校教務(wù)管理中的應(yīng)用［J］中國(guó)高新技術(shù)企業(yè)2008（12）.

［6］陳啟買，彭利寧等.基于關(guān)聯(lián)挖掘的課程相關(guān)性模式研究［J］華南師范大學(xué)學(xué)報(bào)（自然科學(xué)版）2008（1）.

Research on Several Association Rules Algorithm

Gu Wei
（Xuzhou Higher Normal School Xuzhou 221116）

AbstractAt present，the researchers put a lot of effort and time to study the association rule mining algorithm，because the algorithm is the core of association rules，association rules，the most famous classical algorithm is the Apriori algorithm. With the continue to invest in research，from the time，space and cost up to consider，the efficiency of the algorithm in continuous improvement，from the width of the first mining algorithm to the depth first algorithm for mining，from mining frequent item sets to improve the frequency set algorithm，association rules mining algorithm efficiency in the step by step to improve.

keywordsData mining Association rules Apriori algorithm

中圖分類號(hào)TP311.13

文獻(xiàn)標(biāo)識(shí)碼A

文章編號(hào)160513-7274

作者簡(jiǎn)介

顧瑋，女，1981年生，漢族，徐州高等師范學(xué)校教師，碩士研究生，研究數(shù)據(jù)庫(kù)，數(shù)據(jù)挖掘，系統(tǒng)開發(fā)。