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

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

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

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

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

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

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

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

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

2.1 基本概念

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

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

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

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

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

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

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

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

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

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

2.2.2 FP－tree算法

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

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

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

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

2.2.3 FPL算法

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

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

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

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

3.總結(jié)

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

參考文獻：

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

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

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

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

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