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

顧　瑋

（徐州高等師范學校　徐州　221116）

?

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

顧瑋

（徐州高等師范學校徐州221116）

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

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

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

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

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

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

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

1、增量式更新挖掘算法

這種算法包含兩種情況：

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

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

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

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

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

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

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

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

5、Apriori算法

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

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

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

Apriori算法的描述如下：

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

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

Aprior算法的偽代碼如下：

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

6、改進的Apriori算法

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

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

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

7、基于劃分的Apriori算法

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

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

第二部分，對這n個區(qū)段進行單獨計算，產(chǎn)生n個區(qū)域性的頻繁項目集（潛在的）。

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

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

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

8、DHP算法

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

9、FP-tree算法

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

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

參考文獻

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

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

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

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

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

［6］陳啟買，彭利寧等.基于關(guān)聯(lián)挖掘的課程相關(guān)性模式研究［J］華南師范大學學報（自然科學版）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

中圖分類號TP311.13

文獻標識碼A

文章編號160513-7274

作者簡介

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