數(shù)據(jù)挖掘關(guān)聯(lián)規(guī)則的研究

【摘 要】關(guān)聯(lián)規(guī)則作為數(shù)據(jù)挖掘的一個(gè)重要研究分支，其主要的研究目的是從大型數(shù)據(jù)集中發(fā)現(xiàn)隱藏的、有趣的、屬性間存在的規(guī)律。本文就數(shù)據(jù)挖掘中的關(guān)聯(lián)規(guī)則做了簡(jiǎn)要論述。

【關(guān)鍵詞】數(shù)據(jù)挖掘；關(guān)聯(lián)規(guī)則

1.數(shù)據(jù)挖掘

從信息處理的角度，人們更希望計(jì)算機(jī)幫助我們分析數(shù)據(jù)、理解數(shù)據(jù)，幫助我們基于豐富的數(shù)據(jù)作出決策，做人力所不能及的事情。于是，數(shù)據(jù)挖掘——從大量數(shù)據(jù)中用非平凡的方法發(fā)現(xiàn)有用的知識(shí)——就成了一種自然的需求，它的主要目的便是從龐大的數(shù)據(jù)庫(kù)中尋找出有價(jià)值的隱藏事件，找出其中的知識(shí)，并根據(jù)不同的問(wèn)題建立不同的模型，以提供決策時(shí)的依據(jù)，數(shù)據(jù)挖掘?qū)M織及決策行為將有相當(dāng)大的幫助。

數(shù)據(jù)挖掘又稱數(shù)據(jù)庫(kù)中的知識(shí)發(fā)現(xiàn)（Knowledge Discovery in Databases），知識(shí)發(fā)現(xiàn)的一般步驟為：數(shù)據(jù)抽取，數(shù)據(jù)清理，數(shù)據(jù)設(shè)計(jì)，算法設(shè)計(jì)，算法運(yùn)行，結(jié)果分析。

數(shù)據(jù)挖掘的核心步驟是算法的設(shè)計(jì)階段，一個(gè)好的算法（速度快、伸縮性好、結(jié)果容易使用且符合用戶的特定需求）是影響數(shù)據(jù)挖掘效率的最重要因素。數(shù)據(jù)挖掘是一個(gè)循環(huán)過(guò)程，如果用戶對(duì)結(jié)果不滿意，可對(duì)數(shù)據(jù)庫(kù)進(jìn)行重新挖掘。

從數(shù)據(jù)庫(kù)中發(fā)掘的規(guī)則可以有以下幾種：特征規(guī)則、區(qū)分規(guī)則、聚類規(guī)則、關(guān)聯(lián)規(guī)則和進(jìn)化規(guī)則等。關(guān)聯(lián)規(guī)則是比較新的一種，它的形式簡(jiǎn)潔，易于解釋和理解并可有效捕捉數(shù)據(jù)間的重要關(guān)系。

2.關(guān)聯(lián)規(guī)則

關(guān)聯(lián)規(guī)則挖掘最相關(guān)的三個(gè)重要的研究領(lǐng)域是：統(tǒng)計(jì)學(xué)（Statistics），機(jī)器學(xué)習(xí)(Machine Learning)（或稱人工智能，Artificial Intelligent）及數(shù)據(jù)庫(kù)（Database）。關(guān)聯(lián)規(guī)則挖掘與統(tǒng)計(jì)學(xué)和機(jī)器學(xué)習(xí)的共同特點(diǎn)是：都是從數(shù)據(jù)集中發(fā)現(xiàn)知識(shí)。

2.1 基本概念

Agrawal等人于1993年首先提出了挖掘顧客交易數(shù)據(jù)庫(kù)中項(xiàng)集間的關(guān)聯(lián)規(guī)則問(wèn)題，是數(shù)據(jù)挖掘的一個(gè)重要研究領(lǐng)域。它反映出一個(gè)事物與其它事物之間的相互依存性和關(guān)聯(lián)性。如果兩個(gè)或者多個(gè)事物之間存在一定的關(guān)聯(lián)關(guān)系，那么，其中一個(gè)事物就能夠通過(guò)其它事物預(yù)測(cè)到。具體描述為：

設(shè)I={i1，i2，…，im}是二進(jìn)制文字的集合，其中的元素稱為項(xiàng)(item)。記任務(wù)相關(guān)的數(shù)據(jù)D為交易T(transaction)的集合，這里交易T是項(xiàng)的集合，并且T#8838;I。每個(gè)交易都有一個(gè)唯一的標(biāo)識(shí)，如交易號(hào)，記作TID。設(shè)X是一個(gè)I中項(xiàng)的集合，如果X#8838;T，那么稱交易T包含X。

2.2 關(guān)聯(lián)規(guī)則挖掘的算法

Agrawal等人在1993年設(shè)計(jì)了一個(gè)基本算法，提出了挖掘關(guān)聯(lián)規(guī)則的一個(gè)重要方法—這是一個(gè)基于兩階段頻繁項(xiàng)集思想的方法，將關(guān)聯(lián)規(guī)則挖掘算法的設(shè)計(jì)可以分解為兩個(gè)子問(wèn)題：

1)找到所有支持度大于最小支持度的項(xiàng)集（Itemset），這些項(xiàng)集稱為頻繁項(xiàng)集（Frequent Itemset)。

2)使用第1步找到的頻繁項(xiàng)集產(chǎn)生期望的規(guī)則。

第一個(gè)問(wèn)題是算法設(shè)計(jì)的核心問(wèn)題，它的效率高低是影響算法的關(guān)鍵，從龐大的數(shù)據(jù)庫(kù)中找出所有符合大于或等于最小支持度的頻繁項(xiàng)集，往往是相當(dāng)艱巨且耗時(shí)的過(guò)程，但頻繁項(xiàng)集被確定以后，要產(chǎn)生相對(duì)應(yīng)的關(guān)聯(lián)規(guī)則就容易且直接了，第2步只在生成的頻繁項(xiàng)集中創(chuàng)建相應(yīng)規(guī)則的枚舉過(guò)程，無(wú)需復(fù)雜的計(jì)算，目前所謂的算法設(shè)計(jì)問(wèn)題主要是圍繞如何生成頻繁集展開的。

2.2.1 經(jīng)典頻集方法

為了生成所有頻繁項(xiàng)集，Agrawal等人在1993年設(shè)計(jì)了Apriori算法，使用了遞推的方法。

首先產(chǎn)生頻繁1-項(xiàng)集L1，然后是頻繁2-項(xiàng)集L2，直到有某個(gè)r值使得Lr為空，這時(shí)算法停止。這里在第k次循環(huán)中，過(guò)程先產(chǎn)生候選k-項(xiàng)集的集合Ck，Ck中的每一個(gè)項(xiàng)集是對(duì)兩個(gè)只有一個(gè)項(xiàng)不同的屬于Lk-1的頻繁項(xiàng)集做一個(gè)(k-2)-連接來(lái)產(chǎn)生的。Ck中的項(xiàng)集是用來(lái)產(chǎn)生頻繁項(xiàng)集的候選集，最后的頻繁項(xiàng)集Lk必須是Ck的一個(gè)子集。Ck中的每個(gè)元素需在交易數(shù)據(jù)庫(kù)中進(jìn)行驗(yàn)證來(lái)決定其是否加入Lk，這里的驗(yàn)證過(guò)程是算法性能的一個(gè)瓶頸。這個(gè)方法要求多次掃描可能很大的交易數(shù)據(jù)庫(kù)，即如果頻繁項(xiàng)集最多包含10個(gè)項(xiàng)，那么就需要掃描交易數(shù)據(jù)庫(kù)10遍，這需要很大的I/O負(fù)載。

2.2.2 FP－tree算法

Han等人提出FP－tree算法[32]，此算法是不產(chǎn)生候選項(xiàng)集作法的代表，因?yàn)椴挥卯a(chǎn)生候選項(xiàng)集，只需掃描數(shù)據(jù)庫(kù)兩次，因此節(jié)省了大量I／O的時(shí)間，整體的效能大幅提升，而且已運(yùn)用在實(shí)際的產(chǎn)品中。

FP－tree算法和上述算法最主要的差別在于：FP－tree算法不用產(chǎn)生候選項(xiàng)集，且將數(shù)據(jù)庫(kù)壓縮在FP－tree的結(jié)構(gòu)中，改進(jìn)了掃描多次數(shù)據(jù)庫(kù)的高成本。我們利用表2-1中的例子來(lái)說(shuō)明FP－tree算法。它的最小支持度設(shè)為2，其作法可分為兩個(gè)階段。

第一個(gè)階段為構(gòu)建FP－tree結(jié)構(gòu)，需掃描數(shù)據(jù)庫(kù)兩次，第一次掃描數(shù)據(jù)庫(kù)將每個(gè)支持度大于或等于最小支持度的項(xiàng)目（頻繁1-項(xiàng)集）找出，并根據(jù)其支持度值大小和在數(shù)據(jù)庫(kù)出現(xiàn)的先后次序作排序。并使得每一項(xiàng)通過(guò)一個(gè)節(jié)點(diǎn)鏈指向它在樹中的出現(xiàn)。第二次掃描過(guò)濾掉數(shù)據(jù)庫(kù)中不足最小支持度的項(xiàng)目并依據(jù)排序表的頻繁1-項(xiàng)集的次序得到每筆記錄中包含頻繁項(xiàng)的模式，同時(shí)構(gòu)建FP－tree結(jié)構(gòu)。

FP－tree構(gòu)造如下：首先，創(chuàng)建樹的根節(jié)點(diǎn)，用“root”標(biāo)記，讀入經(jīng)過(guò)排序處理的每筆記錄的第一個(gè)項(xiàng)時(shí)，檢查root下的子樹是否存在此項(xiàng)目節(jié)點(diǎn)，若此項(xiàng)目不存在，則在root下新增此項(xiàng)目節(jié)點(diǎn)（Ni）；如果此項(xiàng)目存在，則將此節(jié)Nj支持度加l。之后的項(xiàng)目讀入時(shí)，檢查Nk（Nk為Ni或Nj）下的子樹是否存在此項(xiàng)目節(jié)點(diǎn)，如果不存在，就在Nk下新增一個(gè)項(xiàng)目節(jié)點(diǎn)，如果存在，則將此節(jié)點(diǎn)支持度加1，以此類推做完每筆頻繁項(xiàng)集中的所有項(xiàng)目。

2.2.3 FPL算法

E C.Tseng及Hsu Tseng提出FPL（Frequent Pattern List）算法以改進(jìn)FP-tree算法，F(xiàn)PL主要是將數(shù)據(jù)庫(kù)中的交易數(shù)據(jù)做適當(dāng)?shù)奶幚砗髢?chǔ)存在一線性串行數(shù)據(jù)結(jié)構(gòu)中，并在此線性串行結(jié)構(gòu)上執(zhí)行簡(jiǎn)單的運(yùn)算，即可有效找出所有頻繁項(xiàng)集模式，因?yàn)镕PL算法利用簡(jiǎn)單的線性串行數(shù)據(jù)結(jié)構(gòu)，不需產(chǎn)生候選項(xiàng)集，只需掃描數(shù)據(jù)庫(kù)兩次，且不管是稀疏數(shù)據(jù)庫(kù)或是密集數(shù)據(jù)庫(kù)均能有效找出所有的頻繁項(xiàng)集模式，因此克服了FP-tree的缺點(diǎn)。

FPL算法掃描數(shù)據(jù)庫(kù)兩次，第一次掃描數(shù)據(jù)庫(kù)將每個(gè)支持度值大于或等于最小支持度的頻繁1-項(xiàng)集找出，并依照支持度大小和在數(shù)據(jù)庫(kù)出現(xiàn)的先后次序作排序，第二次掃描以過(guò)濾掉記錄中不足最小支持度的項(xiàng)目并根據(jù)己排序好的項(xiàng)目次序得到每筆記錄的包含頻繁項(xiàng)的模式，這一步與FP-tree算法一致。

此后FPL執(zhí)行以下兩個(gè)階段。第一個(gè)階段是構(gòu)建頻繁項(xiàng)目線性串行。根據(jù)表2-5將頻繁項(xiàng)依支持大小建立成FPL串行，并將表2-3中的每筆記錄建構(gòu)成0、1二元數(shù)據(jù)表（DB-BIT），作法是根據(jù)FPL串行節(jié)點(diǎn)順序與表2-3的數(shù)據(jù)做比較即可得到每筆記錄，記錄Ti之某位數(shù)據(jù)若為0（1）表示相對(duì)的頻繁數(shù)據(jù)項(xiàng)目未出現(xiàn)（出現(xiàn)）在此記錄中，最后將DB-BIT中的所有記錄掛至適當(dāng)?shù)腇PL串行節(jié)點(diǎn)上。

第二個(gè)階段是從此串行結(jié)構(gòu)中挖掘所有的頻繁項(xiàng)集模式。首先檢查串行最右邊節(jié)點(diǎn)（Ni），這也與FP-tree算法相似，從支持度最小的項(xiàng)開始挖掘。在此要找出所有包含Ni項(xiàng)目的頻繁項(xiàng)集模式，計(jì)算出現(xiàn)在Ni節(jié)點(diǎn)上的其它各項(xiàng)出現(xiàn)次數(shù)(Bit count)，接著忽略Ni以及所有Bit count小于最小支持度的項(xiàng)產(chǎn)生Ni項(xiàng)目的頻繁1-項(xiàng)集模式：I5：2（代表項(xiàng)目I5在數(shù)據(jù)庫(kù)中出現(xiàn)二次），接下來(lái)處理Bit count值大于或等于最小支持度的節(jié)點(diǎn)(Nb(b=l，2，…n))，產(chǎn)生頻繁模式為Nb和Ni組合，其出現(xiàn)次數(shù)皆為Nb支持度值（I2，I5：2），（I1，I5：2），再將Nb重新建立一子串行，并且將Ni所屬的所有記錄掛至適當(dāng)?shù)墓?jié)點(diǎn)上，依據(jù)上面的方法，再挖掘新的頻繁模式：（I2，I1，I5：2），直到串行中只剩下一個(gè)節(jié)點(diǎn)I2。接著考慮移走Ni所屬的記錄及DB-BIT最后一位，找出下一個(gè)Ni=1的所有記錄并掛至此串行下。重復(fù)上述方法尋找頻繁項(xiàng)集模式，直至串形結(jié)構(gòu)上只有一個(gè)最大節(jié)點(diǎn)存在為止。

3.總結(jié)

總之，Apriori、FP-tree等現(xiàn)有關(guān)聯(lián)規(guī)則挖掘算法都是在單維、單層、布爾關(guān)聯(lián)規(guī)則下討論的，是最簡(jiǎn)單形式的關(guān)聯(lián)規(guī)則，它是解決其它問(wèn)題的基礎(chǔ)。

參考文獻(xiàn)：

[1]朱揚(yáng)勇，周欣，施伯樂(lè).規(guī)則型數(shù)據(jù)采掘工具集AMINER[J].高技術(shù)通訊，2000，10.

[2]胡侃，夏紹偉.基于大型數(shù)據(jù)庫(kù)的數(shù)據(jù)采掘:研究綜述[J].軟件學(xué)報(bào)，1998，3.

[3]王曙光，施英.一種改進(jìn)的相聯(lián)規(guī)則提取算法.計(jì)算機(jī)工程與應(yīng)用[J].2002，15.

[4]顏雪松，蔡之華.一種基于Apriori的高效關(guān)聯(lián)規(guī)則的挖掘[J].計(jì)算機(jī)工程與應(yīng)用，2002，10.

作者簡(jiǎn)介：趙超（1983—），陜西西安人，碩士研究生，渭南師范學(xué)院教師，研究方向：計(jì)算機(jī)技術(shù)與應(yīng)用。