孫金鑫

文章編號： 2095-2163（2018）03-0132-04中圖分類號： 文獻標志碼： A

摘要： 關鍵詞： （School of Computer Science and Technology， Donghua University， Shanghai 201620， China）

Abstract： In the last century， the rise of data mining technology helped the researchers to extract valuable information from a large amount of data. Agrawal et al. proposed association rule mining techniques in the 1990s to find relevant information in a large amount of data. After these two decades of development， association rules have become a very important and relatively mature method in data mining. This article outlines the application of association rules in data mining， discusses the existing classical algorithms in association rules， and summarizes the advantages and disadvantages of these algorithms. Based on the above， the paper further optimizes the FP-Growth algorithm.

Key words：

作者簡介：

收稿日期： 引言

互聯(lián)網(wǎng)時代，在查詢某個記錄時經(jīng)常使用數(shù)據(jù)庫管理系統(tǒng)，用網(wǎng)絡搜索引擎來檢索特定的網(wǎng)頁。在這個過程中，大量使用了計算機科學技術(shù)中的數(shù)據(jù)結(jié)構(gòu)和邏輯精深的算法來創(chuàng)建索引結(jié)構(gòu)，用以管控信息的組織與查詢，而這類方法只能在特定環(huán)境之下得以實現(xiàn)。隨著社會的不斷進步，計算機信息技術(shù)的飛速發(fā)展，數(shù)據(jù)量呈現(xiàn)指數(shù)級的增長，就使得數(shù)據(jù)庫的規(guī)模也處于持續(xù)的攀升中。在此基礎上，則需要研發(fā)更加復雜和更有效率的算法來將這些數(shù)據(jù)轉(zhuǎn)換成有價值的信息，而這也將耗費數(shù)目可觀的計算成本。為應對這一需求，數(shù)據(jù)挖掘技術(shù)也得到了迅速發(fā)展，目前已廣泛地應用于數(shù)據(jù)分析領域中，其目的是從大量的數(shù)據(jù)中挖掘隱藏的、潛在的、有價值的模式或規(guī)則以對企業(yè)工程的決策提供有效依據(jù)。從信息技術(shù)的角度來看，數(shù)據(jù)挖掘技術(shù)及其相應算法是伴隨著數(shù)據(jù)倉庫技術(shù)的日趨成熟而逐步完善起來的。正是數(shù)據(jù)挖掘技術(shù)的滲透作用，增強了信息檢索系統(tǒng)的能力[1]，具有廣闊前景。因而，本文將對這一內(nèi)容展開深入探索研究。

1數(shù)據(jù)挖掘簡述

數(shù)據(jù)挖掘（Data Mining，DM），又可稱為數(shù)據(jù)庫知識發(fā)現(xiàn)（Knowledge Discover in Database，KDD），是一種新型的數(shù)據(jù)處理技術(shù)，綜合涵蓋了諸如數(shù)據(jù)庫技術(shù)、統(tǒng)計學、機器學習、分布式和并行計算等眾多學科領域內(nèi)容[2]。這是從研究數(shù)據(jù)庫的大量的、不完全的、模糊的、隨機的、有噪音的（包括錯誤或偏離期望的異常值）數(shù)據(jù)中，運算得出人們感興趣的有用信息及模式。例如預測作用，能夠高度自動化分析原有的數(shù)據(jù)，并發(fā)現(xiàn)數(shù)據(jù)之間的潛在聯(lián)系，再以此為基礎，歸納挖掘得到未來可能會發(fā)生的行為。研究者們在知識發(fā)現(xiàn)的模式中，透過微觀看宏觀，會揭示大量數(shù)據(jù)項集存在的有價值的關聯(lián)關系。這些知識蘊含著普遍意義上的更高層次的價值。正是數(shù)據(jù)挖掘的長足發(fā)展，使得數(shù)據(jù)庫技術(shù)向更高層次推進，即對現(xiàn)實科研產(chǎn)生了價值高端、且意義深遠的作用與影響。

2關聯(lián)規(guī)則算法研究

關聯(lián)規(guī)則挖掘研究成為數(shù)據(jù)挖掘中的一個探討熱點，并已陸續(xù)應用于市場營銷、事務分析等重要領域[3]。關聯(lián)規(guī)則中的算法研究就是當前的目標核心方向，而且也相繼提出了許多高效的關聯(lián)規(guī)則挖掘算法。大量的研究表明，關聯(lián)規(guī)則的主要任務就是找出滿足預先指定的頻率和精度標準的所有規(guī)則，但是由于頻繁集數(shù)量與變量數(shù)、以及數(shù)據(jù)多少是指數(shù)型的關系，這就在無形中增加了研究難度。但是在實際的數(shù)據(jù)集下，頻繁集數(shù)量都會較小，這就又顯著提升了研究的可行性。關聯(lián)規(guī)則的典型算法主要包括：Apriori算法、AprioriTid算法、DLG算法和FP-Growth算法。下面將逐一闡釋論述各算法的研究工作。

2.1Apriori算法

Apriori算法是一種基于關聯(lián)規(guī)則頻繁項集的算法，最早提出，同時也占據(jù)了標志性地位。后續(xù)的眾多挖掘算法都是在 Apriori 算法基礎上引入改進，并將其作為基準來對比評估算法自身性能。Apriori算法是一種逐層搜索的迭代方法，k項集用于搜索（k+1）項集。首先，通過掃描事務集，找出所有的頻繁一項集，該集合記做L1，然后利用L1找頻繁二項集的集合 L2，L2用于找L3，如此循環(huán)下去，直至不能再找到任何頻繁k項集，最后在所有的頻繁集中推出強規(guī)則。在此算法中常出現(xiàn)頻繁項集的概念。項集是項目的集合，包括k個項目的集合記為： k-項集。研究中，包含項集的事務數(shù)可稱為項集的頻率、支持計數(shù)或計數(shù)。如果項集滿足最小支持度，則稱為頻繁項集。Apriori的算法流程如圖1所示。

但是Apriori算法在執(zhí)行的過程中，需要對數(shù)據(jù)庫設計部署頻繁的掃描，如果設置了最小支持度和置信度之后，所生成的頻繁項集最大限度是K，那么就要對數(shù)據(jù)庫展開K次掃描，這樣就會增加掃描時間，從而影響工作效率。對于這些問題，迄今已發(fā)表了許多優(yōu)化的方法，諸如：數(shù)據(jù)庫邏輯分割的優(yōu)化、哈希表技術(shù)的優(yōu)化、基于事務壓縮技術(shù)的優(yōu)化和采樣技術(shù)的優(yōu)化等。但是如何將這些方法進行有效融合以提高算法效率卻仍有待進一步的研究。

2.2AprioriTid算法

AprioriTid是一種寬度優(yōu)先搜索算法，這是建立在前期研發(fā)算法Apriori的基礎上，對Apriori算法的改進在于：Apriori算法每次迭代都是掃描原始數(shù)據(jù)集來計算支持度，而AprioriTid是通過以k階生成的Tid表來達到這一目的。Tid表沒有直接存儲事務，存儲的是每個事務中包含的k維候選項目集，其作用是用來判斷k維候選項目集能否成為k維頻繁項目集，如此循環(huán)下去。簡單說來，AprioriTid算法和Apriori算法的根本性差別就表現(xiàn)在，算法中用于產(chǎn)生候選項目集支持度計數(shù)的數(shù)據(jù)結(jié)構(gòu)不同，從而導致了該算法的性能也得到了顯著提升。但是AprioriTid 算法卻也暴露出一定程度上的不足之處。當數(shù)據(jù)量龐大時，此算法也將會帶來巨大的時間和空間復雜度。

2.3DLG算法

DLG（Direct Large Itemset Generation） 算法是Yen等人研發(fā)提出的基于圖的關聯(lián)規(guī)則挖掘算法[4]。該算法的實現(xiàn)步驟是：先掃描數(shù)據(jù)事務庫，生成一階的頻繁項目集和圖的位向量，然后再生成二階頻繁項目集并生成關聯(lián)圖，最后通過擴展生成k-1階頻繁項集。該算法的缺點是生成的候選頻繁項目集比較大，且會造成計算時間的嚴重浪費。

2.4FP-Growth算法

FP-Growth算法是一種基于頻繁項目集的挖掘算法[5]。算法原理是事務數(shù)據(jù)庫壓縮到構(gòu)建的FP-Tree模式樹中。該算法需要對數(shù)據(jù)事務庫進行2次掃描，這也是和Apriori算法呈現(xiàn)重點區(qū)別的地方。整個挖掘過程都不會產(chǎn)生候選項目集，都是以FP-Tree的方式在內(nèi)存中設定表示。也因如此，目前已可見到許多優(yōu)化的改進算法，相對優(yōu)化的是文獻[6]給出了基于事務項矩陣的FP-Growth改進算法MFP-Growth。這一算法主要是利用矩陣來存儲事務庫中的事務，過程中只需要掃描一次事務庫，再通過構(gòu)造頻繁項集的條件矩陣來實現(xiàn)頻繁項集的挖掘。該算法減少了算法的內(nèi)存空間，從而大幅提高了運行效率。

3FP-Growth算法的優(yōu)化

3.1優(yōu)化算法研究

在FP-tree構(gòu)建生成后，可以著手挖掘FP-tree以找到完整的頻繁項集合。算法中，F(xiàn)P-Growth函數(shù)的輸入數(shù)據(jù)：在第一次調(diào)用時，Tree是指原始的FP-tree，遞歸調(diào)用時便是某個模式的條件FP-tree；在第一次調(diào)用函數(shù)時，a是null，此后遞歸調(diào)用時，a代表模式的后綴。FP-Growth函數(shù)的輸出結(jié)果：輸出所有的模式和支持度。這里，研究將給出FP-Growth算法的執(zhí)行偽代碼可見如下。

輸入由表4（見后文）構(gòu)造的FP-tree表示的數(shù)據(jù)和后綴模式a。

輸出所有的頻繁項集

方法調(diào)用FP-Growth（FP-tree，null）

FP-Growth（tree，a）{

If tree含單個路徑P{

For（路徑P中結(jié)點的每個組合（記作b））{{

產(chǎn)生模式b∪a，其支持度support=b中結(jié)點的最小支持度；

}

}else{

for（每個ai在tree的頭部（按照支持度由低到高順序進行掃描））{

產(chǎn)生一個模式b=ai∪a，其支持度support=ai.support；

構(gòu)造b的條件模式基，然后構(gòu)造b的條件FP-tree b；

If（tree b不為空）調(diào)用FP-Growth（tree b，b）；

}

}}}

綜合上述分析可知，F(xiàn)P-Growth算法是在整個事務數(shù)據(jù)庫基礎上構(gòu)建模式樹，占用內(nèi)存較大，當亟待挖掘的數(shù)據(jù)量較大、或約束條件嚴格時，算法運行效率偏低，嚴重影響了數(shù)據(jù)挖掘的時效性。為此在延承 FP-Growth 算法長足優(yōu)勢的前提下，本文提出了優(yōu)化方法。本次設計方法中，首先對事務數(shù)據(jù)庫進行遍歷，得到所有事務項中項的支持度計數(shù)，根據(jù)最小支持度的預設條件可將支持度計數(shù)不滿足預設條件的項刪除，得到頻繁 1-項集。依照頻繁1-項集中各項支持度計數(shù)重新排列事務數(shù)據(jù)庫中的項，并刪除支持度不符合條件的事務項；然后，利用頻繁1-項集研發(fā)構(gòu)造各項的數(shù)據(jù)庫子集，再對各子集運用FP-Growth 算法進行頻繁項集的挖掘，得到各項的頻繁項集，最后將所有得到的頻繁項集予以合并，即為整個事物數(shù)據(jù)庫的頻繁項集。

3.2算法設計實例

假如現(xiàn)有事務數(shù)據(jù)庫，庫中事項可見表1。

3.3算法優(yōu)化設計

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

輸出事務數(shù)據(jù)庫 T 的頻繁項集

算法優(yōu)化過程可詳述如下：

（1）遍歷事務數(shù)據(jù)庫T，找出所有候選1-項集，計算各項的支持度計數(shù)，將支持度計數(shù)小于預設條件最小支持度的項刪除，得到頻繁1-項集的集合 H。設 H={J1，J2，…，Jn}。其中， J1是支持度最大的，Jn是支持度最小的。

（2）再次遍歷事務數(shù)據(jù)庫 T ，將支持度計數(shù)小于最小支持度的項從各事務數(shù)據(jù)庫中刪除，對事務數(shù)據(jù)庫中的項按照支持度計數(shù)從大到小進行重新排列，得到新的事務數(shù)據(jù)庫為 T'。

（3）遍歷事務數(shù)據(jù)庫T'，找出包含項 Ji的所有事務項，將支持度小于該事務項支持度的項刪除，得到的事務項集合就是項 Ji的數(shù)據(jù)庫子集 Ti。

（4）再利用FP-Growth 算法對數(shù)據(jù)庫子集Ti進行頻繁項集挖掘。

以某年某月的銷售數(shù)據(jù)預處理后1 000條數(shù)據(jù)為例。假設最小支持度為40%，在相同的硬件和軟件環(huán)境下，采用FP- Growth算法得到頻繁1-項集34項、頻繁2-項集26項、頻繁3-項集18項、頻繁4-項集12項、無頻繁5-項集。采用優(yōu)化FP- Growth算法得到頻繁1-項集34項、頻繁2-項集26項、頻繁3-項集18項、頻繁4-項集12項、無頻繁5-項集。2種方法得到的頻繁項集的內(nèi)容相同。改變樣本數(shù)據(jù)的數(shù)據(jù)量，2種算法在時間上的對比結(jié)果如圖3所示。

進一步研究可知，隨著數(shù)據(jù)庫中屬性項數(shù)和記錄數(shù)的不斷增加，優(yōu)化FP-Growth算法在時間及空間上運行效果將更加突出，算法優(yōu)越性也越發(fā)明顯。

4結(jié)束語

本文首先對關聯(lián)規(guī)則挖掘進行了研究，主要包括關聯(lián)規(guī)則挖掘的相關概念定義以及挖掘過程，對現(xiàn)有的數(shù)據(jù)分析方法給出了技術(shù)進展的研究成果綜述，而且又著重于對關聯(lián)規(guī)則挖掘的4種經(jīng)典算法展開了詳盡的闡釋研究，通過對關聯(lián)規(guī)則現(xiàn)有主流算法的深入探討剖析，總結(jié)出每種算法的優(yōu)勢與劣勢，進而設計提出一種FP-Growth的優(yōu)化方式。

參考文獻

[1] 楊澤民. 數(shù)據(jù)挖掘中關聯(lián)規(guī)則算法的研究 [J]. 軟件，2013，34（11）：71-72.

[2] 段玉琴. 數(shù)據(jù)挖掘中關聯(lián)規(guī)則算法的研究 [D]. 西安：西安電子科技大學，2011.

[3] 高杰，李紹軍，錢峰. 挖掘關聯(lián)規(guī)則中AprioriTid 算法的改進[J]. 計算機工程與應用，2007， 43（7）：188-190，197.

[4] 陳明，史忠植，王文杰. 一種有效的基于圖的關聯(lián)規(guī)則挖掘算法[J]. 計算機應用，2006， 26（11）：2654-2656.

[5] HAN Jiawei， PEI Jian， YIN Yiwen. Mining frequent patterns without candidate generation[C]//Proceedings of the ACM SIGMOD International Conference on Management of Data. Dallas， Texas， USA：ACM Press， 2000：1-12.

[6] 段西強，喬賽. 一種基于事務-項矩陣的改進FP-Growth算法[J]. 泰山學院學報，2012， 34（6）：50-52.

[7] 俞燕燕，李紹滋. 基于散列的關聯(lián)規(guī)則AprioriTid改進算法[J]. 計算機工程，2008， 34（5）： 60-62.

[8] 袁玉波，楊傳勝，黃廷祝，等. 數(shù)據(jù)挖掘與最優(yōu)化技術(shù)及其應用 [M]. 北京：科學出版社，2007.

[9] 陳耿，朱玉全，楊鶴標，等. 關聯(lián)規(guī)則挖掘中若干關鍵技術(shù)的研究[J]. 計算機研究與發(fā)展，2005， 42（10）：1785-1789.