基于ＦＰ－Ｇｒｏｗｔｈ算法改進的多層次關聯規則挖掘算法

摘要：針對FP算法的缺陷，將OLAP技術和Apriori關聯規則相結合，提出了一種針對FP算法的改進的多層次關聯規則數據挖掘算法，在分析了關聯規則數據挖掘結構的基礎上，給出了該算法的思想與執行步驟，對于關聯規則數據挖掘的研究具有一定的理論意義。

關鍵詞：算法改進；多層次；關聯規則；數據挖掘

中圖分類號：TP312文獻標識碼：A文章編號：1009-3044(34)-1994-03

Multi-level Association Rules with Data Mining Based on FP Arithmetic Improvement

WANG Juan

(Cizhou College， Computer Center， Cizhou 247000， China)

Abstract: Aiming at the problems of FP arithmetic， the OLAP technology was combined with Apriori association rules， and the new arithmetic that aimed the problems of FP arithmetic was given out， which was the FP arithmetic improvement， and on the basis of analyzing the structure of data rules with data mining， the new arithmetic’s theory and its implementation steps were also developed. All of these work was significative for researching data rules with data mining.

Key words: arithmetic improvement; multi-level; association rules; data mining

1 引言

眾所周知，在實際進行空間數據庫和屬性數據庫設計時，為優化設計，將空間數據庫按照地物的類型分成不同的數據層，如道路層，建筑物層等；對屬性數據庫常常依據范式理論，將其分解為若干通過關鍵字、外關鍵字或其他屬性相互關聯的若干張表的有機組合，這導致了許多空間數據被分別存放在不同層中，而其屬性被分別放在不同的表中。挖掘這些表中蘊藏的知識和信息，顯然有重要的理論和實踐意義。在許多應用場合，空間關聯規則的挖掘要求在多個數據層和表中進行。

對于關聯規則算法，傳統經典的關聯規則Apriori算法有許多不同的改進方法。可能產生大量的候選集以及可能需要重復掃描數據庫，是Apriori算法的兩大缺點。針對Apriori 算法的固有缺陷，國外有學者提出了不產生候選挖掘頻繁項集的方法—FP 算法。FP對不同長度的規則都有很好的適應性，同時在效率上較Apriori算法有巨大的提高。許多應用，特別是電子商務的應用中，在最低層或原始層的數據項之間，可能很難找出強關聯規則和有趣的購買模式。在多個概念層的項之間找有趣的關聯比僅在原始層數據之間更容易，在較高的概念層發現的強關聯規則可能提供普遍意義的知識。因此，我們需要挖掘多層次的關聯規則。

2 基本理論

筆者研究了一種有效的多層次關聯規則挖掘方法，這種方法把FP算法、OLAP技術和Apriori關聯規則挖掘算法結合起來。由于在方法中要涉及到數據倉庫、OLAP、關聯規則挖掘等概念，所以下面先對這些概念進行簡要的介紹。

數據倉庫是面向主題的、穩定的、完整的、時變性的數據集合，數據倉庫為決策支持提供支持。為了進行有效的數據處理，數據倉庫中的一部分必須預先計算，筆者把數據倉庫中預先計算的那部分稱為數據立方體。

OLAP是由數據倉庫提供的，用于以多層次，多維的形式來操作數據。OLAP的基本操作包括：向上綜合，向下考察，局部分析，旋轉等。因此，聯機分析處理的過程就是根據數據分析的要求，從原始數據中構造各種數據立方體，并對立方體執行有關的操作，把結果返回給用戶的過程。

關聯規則是數據間依賴關系的描述，是知識發現研究的重要內容。信息系統S 定義為四元組：(U，A，V，f)，U是對象集合，A={a1，a2，…，ap}是屬性集合，V=V1∪V2…∪Vp是屬性的值域集合，f：U×A→V 定義對象的屬性值。通常，屬性是可分類的，數據的分類層次(hierarchies) 表示了自底向上的概括(generalization) 和自頂向下的特殊化(specification)。基于分類層次的關聯規則挖掘算法主要包括：算法Cumulate 和Stratify，算法ML-T2L1，以及Srikant提出的利用布爾表達限定規則中項目的出現（指定關聯規則的形式）提高挖掘針對性的算法。基于分類的方法僅適用于單個屬性有清晰分類層次的應用。

3 關聯規則挖掘的結構

此關聯規則挖掘方法是以數據立方體的數據結構為基礎，它是把關聯規則挖掘和FP算法、OLAP技術合成起來的方法。下面重點討論OLAP關聯規則挖掘的結構。OLAP關聯規則挖掘的結構由三部分組成：數據倉庫，OLAP引擎和關聯規則挖掘引擎。下面分別討論這三部分。

1) 數據倉庫：

數據倉庫在語義上是用來存儲數據，為決策支持提供服務，但也存儲一些企業決策時需要的信息。它包括的數據主要有三部分：第一部分是完整的歷史數據，這就允許挖掘器能夠輕易而快捷地獲取整個歷史數據；第二部分是已物化的數據立方體，由于物化的數據立方體已存儲在數據倉庫中，這就為挖掘器節省了好多工作；第三部分是元數據，對挖掘器起來說，元數據可以被看作是路標。元數據不僅用來描述數據的內容而且用來描述信息的上下文環境。一種非常重要的元數據就是概念層次結構。概念層次結構是數據倉庫和OLAP的基本要素，它嵌入在維的規范說明中。

2) OLAP引擎：

一旦把工作數據立方體建好，在挖掘過程中所需要的完整信息就保存在數據立方體中。這樣，數據立方體就可以作為挖掘的數據源，也可作為原始數據和挖掘任務之間的接口。因為數據立方體含有的數據量非常大，所以有必要對數據立方體建立豐富的運算函數。這樣OLAP引擎的主要任務就是計算用戶的OLAP指令，最后把結果返回給用戶界面層。可以看出OLAP引擎在OLAP關聯規則挖掘的結構中具有非常重要的作用。

3) 關聯規則挖掘引擎：

關聯規則挖掘引擎是關聯規則挖掘系統的一個非常重要組成部分，下面先介紹關聯規則的類型，其次討論關聯規則挖掘引擎的框架。

該論文將提到三種類型的關聯規則：維之間的關聯規則，維之內的關聯規則，合成關聯規則。

維之間的關聯規則，規則的主體和頭都在不同的維中，如，Location(X，South)，Profit(X，Bad)→Product(X，tent)。可以看出，在這個關聯規則中所有的項目都在不同的維中，且沒有重復。

維之內的關聯規則，所有的項目都在同一維內，因此也稱為單維關聯規則。如，Product(X，clothes)→Product(X，tent)。

合成關聯規則是上兩種關聯規則的合成，因此也稱為多維相關規則。如，Location(X，South)，Product(X，clothes)→Product(X，tent)。

一般情況下，在產生工作數據立方體后，發現關聯規則的任務可以分為兩步。第一步是找出所有符合支持度的經常項目集。在此階段，輸入的是與任務相關的工作數據立方體，支持度的最小值和用戶的限制條件，輸出的是滿足條件的經常項目集。根據關聯規則的類型，輸出的經常項目集可以是單維經常項目集，多維經常項目集或合成項目集。第二步是利用經常項目集產生期望的關聯規則。在此階段，輸入的是上一階段輸出的經常項目集，置信度的最小值和用戶的限制條件。輸出的是滿足置信度和用戶限制條件的關聯規則。

4 關聯規則數據挖掘算法描述

從上面的討論得知，在對FP算法進行改進、進行OLAP關聯規則挖掘時，可以分為三個步驟：

1) 預處理：從log 表過濾出相關的信息，然后根據概念層次樹，自頂向下，對數據庫中的項進行編碼，得到編碼后的數據庫D。

2) 執行改進的FP算法，分別找出各個層次的頻繁項集。

3) 找出交叉層次的關聯規則。

下面逐一進行說明設計。

4.1 預處理

1) 從log表過濾出相關的信息，得出經過數據清洗后的log表d。

2) 根據概念層次樹，自頂向下，對數據庫中的項進行編碼，得到編碼后的數據庫D。

概念層次樹可以由專家給出，也可以從數據庫和Web 日志生成。

4.2 執行改進的FP算法

基本思想：自頂向下，逐層尋找每層的頻繁項集。刪去不滿足閾值的項集。如果其祖先不滿足最小支持度閾值，則不需要再計算它的支持度，直接刪去即可。

對于每層(設層號為i)尋找頻繁項集，均執行下面步驟：

1) 找出頻繁1項集

掃描編碼后的數據庫D，收集每項的支持度。按支持度降序排列，刪去不滿足對應第i 層的最小支持度的項，結果為頻繁1項集，存入頻繁項表L[i]；同時，刪去冗余的多層（后代）頻繁1項集。

2) 構建FP樹

① 根節點標記為1，它的子節點為一個項前綴子樹的集合，還有一個頻繁項組成的頭表。

② 每個項前綴子樹的節點有3個域：item-name，count，node_link。item-name 記錄該節點所代表的項的名字，count記錄所在路徑代表的交易中達到此節點的交易個數，node_link 指向下一個具有同樣的item-name 域的節點，如果沒有這樣一個節點，就為1。

③ 頻繁項頭表的每個表項由兩個域組成： item-name 和node_link。node_link 指向FP-tree 中具有與該表項相同item-name域的第1個節點。

創建FP-tree 根節點，記為T，并標記為1。對于D 中每個會話session，執行：選擇session 中的頻繁項，并按L[i]中的次序排序。設排序后的頻繁項表為[p|P]，其中p 是第1個元素，P是剩余元素的表。調用insert_tree([p|P]，T)。

函數insert_tree([p|P]，T)的運行如下：如果T有一個子結點N，其中N.item-name=p.item-name，則將N 的count域值增加1；否則，創建一個新節點N，使它的count 為1，使它的父節點為T， 并且使它的node_link 和那些具有相同item_name 域串起來。如果P 非空， 則遞歸調用insert_tree(P，N)。

3) 遞歸挖掘FP樹：FP-樹的挖掘通過調用FP-growth(FP_tree，1)實現

4.3 找出交叉層次的關聯規則

基本思想：自底向上，從最低層的頻繁項集開始，計算交叉層次的頻繁項集。對交叉層次的頻繁項集，根據滿足最小支持度閾值的概率來篩選出合適的頻繁項集，刪去不滿足概率的項集。

在OLAP關聯規則挖掘時，把要挖掘的維稱為項目維，而把與這個維相關的另外的維稱為事務處理維，產生經常項目集的算法和Apriori算法類似，只是在判斷是否滿足支持度時，Apriori算法掃描的是交易數據表，而該方法掃描的是部分數據立方體。由于維之內關聯規則挖掘的經常項目集產生方法和Apriori算法的一樣，而合成關聯規則挖掘的經常項目集產生方法是維之內關聯規則挖掘和維之間關聯規則挖掘經常項目集產生方法的綜合，由于篇幅的關系這里只對維之間關聯規則挖掘的經常項目集產生方法做一具體介紹。

維之間關聯規則就是存在于一組維之內的相關規則。算法的整個過程也是以Apriori算法為基礎。因為項目存在于不同的維中，這里通過利用數據立方體的概念分層結構來直接獲取每個項目集的置信度。這個算法的輸入條件是n 維的數據立方體CB[d1，d2，……dn]和所要求的最低支持度。

4.4 算法實驗結果對比分析

為了比較上述多層空間關聯規則挖掘算法的效率，用Visual C++在內存為512MB的C4 1.7G計算機上實現了FP算法與本改進算法的性能比較。測試數據集共包括2個數據層各含有5個屬性，每個屬性泛化后有2~10個屬性值，采用的元模式形如 P(t，x)∧Q(t，y)→R(t，z)，而各層的最低支持度均為6%，最低信任均為75%。

測試了算法的隨記錄的增加時間的變化(時間復雜性)，將測試數據庫的元組數從1000開始，逐漸遞增到5000。兩算法的時間復雜性數據曲線如圖1所示，從圖中礦業發現，兩個算法的時間復雜性均較好，不過隨數據庫規模的增大，針對FP算法的改進OLAP結構算法在執行時間更為迅速，而且在時間的增長上更為平緩一些，所以本論文提出的改進算法是可行的。

5 結語

該文中首先對數據倉庫、OLAP、相關規則的挖掘進行了總體的介紹，其次全面討論了OLAP相關規則挖掘的結構，最后討論了基于FP算法改進，利用OLAP 關聯規則挖掘結構實現的多層次關聯挖掘算法。

根據用戶及網站的訪問使用，為用戶提供動態個性化推薦，是電子商務中極為重要的功能。本文提出的挖掘多層關聯規則算法，通過數據庫和Web 日志構建概念層次樹，在繼承FP 算法思想的基礎上，利用OLAP關聯規則的結構，由概念層次樹挖掘多層包括交叉層次的關聯規則算法。本算法是對數據挖掘算法的必要補充，具有一定的理論意義，不僅能有效地應用于電子商務的個性化推薦，而且能方便地推廣到其他有關的應用中。

參考文獻：

[1] 高峰，謝劍英.多值屬性關聯規則的理論基礎[J].計算機工程，2000，26(11):47-49.

[2] 王文清，喬雪峰.帶有時態約束的多層次關聯規則的挖掘[J].北京理工大學學報，2003，23(1):87-90.

[3] Chen J P， Bian F L， Fu Z L， et al. An Improved Algorithm of Apriori[J].Geomatics and Inform ation Science of Wuhan University，2003(1):94-99.

[4] 許兆新，周雙娥，郝燕玲.最優關聯規則的形式和挖掘思想的研究[J].計算機工程與應用，2000(20):118-119.

[5] 張玉林，仲偉俊，梅姝娥.一類表內多概念間多層次關聯規則挖掘算法及應用[J].計算機工程與應用，2001(14):91-92，102.