多層次分布式數據挖掘關聯規則的研究

王 銳，曹振強

WANG Rui1, CAO Zheng-qiang2

（1.鄭州廣播電視大學，鄭州 450003；2.河南省圖書館，鄭州 450052）

1 多層次關聯規則描述

對于許多應用來講，由于數據在多維空間中存在多樣性，因此要想從基本或低層次概念上發現強關聯規則可能是較為困難的，而在過高抽象層次的概念上所挖掘出的強關聯規則或許表達了一些普通的常識。但是對一個用戶來講是常識性知識，可能對于另外一個用戶就是新奇的知識。因此數據挖掘希望應該能夠提供在多個不同層次挖掘相應關聯規則知識的能力，并能夠較為容易對不同抽象空間的內容進行瀏覽與選擇。

以郵政報刊發行為例：

圖1 報刊概念層次樹

一個典型的報刊目錄的層次結構，如圖1所示。在這個層次樹中描寫了郵政報刊的一種分類方法，該層次樹描述了從低層次概念到高層次概念的相互關系。在概念層次樹中，利用高層次概念替換低層次概念可以是數據的泛化。如概念層次樹共分為四層，分別為層次0，1，2，3；層次自頂而下從零開始。樹的根節點標記為all。層次1包括：雜志，報紙；層次2包括：技術，生活，娛樂等分類。層次3則包括：計算機應用，計算機工程，女友，家庭生活，新周刊，娛樂前線等雜志報紙。概念層次結構可以由熟悉報刊數據組織結構的用戶在報刊目錄表中定義。[1]

2 挖掘多層次關聯規則的方法

首先就給予支持度和信任度的挖掘方法作進一步討論。一般而言，利用自上而下的策略從最高層次向低層次方向進行挖掘時，對頻繁項集出現次數進行累積以便發現每一個層次的頻繁項集指導無法獲得新頻繁項集為止。也就是在獲得所有層次概念1的頻繁項集后，再挖掘層次2的頻繁項集，如此下去。對于每一個概念層次（挖掘），可以利用任何發現頻繁項集的算法，如：Apriori或者FP-tree，FP-growth算法。

多層次挖掘關聯規則算法的闕值取值分析：

1）對所有層次均使用統一的最小支持闕值，即對（所有）不同層次頻繁項集的挖掘均使用相同的最小支持闕值，例如圖2所示整個挖掘均使用最小支持闕值5%（從“技術”到“計算機應用”）；“計算機工程”不是頻繁的，但是“計算機技術”和“計算機應用”卻是頻繁的。

圖2 利用統一最小支持闕值的多層次挖掘

利用統一最小支持闕值，可以簡化搜索過程。由于用戶只需要設置一個最小支持闕值，因此整個挖掘方法變得比較簡單?；谝粋€祖先節點是其子節點的超集，可以采用一個優化技術，即可避免搜索其祖先節點包含不滿足最小支持闕值的項集。

但是利用統一的最小支持闕值也存在一些問題。由于低層次項不可能比相應高層次項出現的次數更多。如果最小支持闕值設置過高，那就可能忽略了一些低層次中有意義的關聯關系。若闕值設置過小，則可能產生過多的高層次無意義的關聯關系。因此產生了第二種算法。

2）在低層次里用減少的闕值（又稱為遞減支持闕值）。所謂遞減支持闕值，每一個抽象層次均有相應的最小支持闕值。抽象層次越低，相應的最小支持闕值就越小。例如圖3

所示，層次1和層次2的支持度分別為5%和3%這樣：“計算機工程”、“計算機技術”和“計算機應用”都是頻繁的。[2]

圖3 利用遞減闕值的多層次挖掘

利用遞減闡值挖掘多層次關聯知識，可以選擇若干搜索策略：

1）層與層獨立。這是一個完全寬度搜索。沒有利用任何頻繁項集的有關知識來幫助進行項集的修剪。無論該節點的父節點是否為頻繁的，均要對每一個節點進行檢查。

2）利用單項進行跨層次過濾。當且僅當相應父節點在（i-1）層次是頻繁的，方才檢查在i層次的單項。也就是說，根據一個更普遍的來確定檢查一個更具體的。

3）利用k-項集進行跨層次過濾。當且僅當相應的父k-項集（i-1）層次是頻繁的。方才檢查在i層次的k-項集。

層與層獨立策略由于它過于寬松而導致其會要檢查無數低層次概念的頻繁項，并會發現許多沒有太大意義的關聯知識。例如：如果“生活類”雜志很少被訂閱，那么在去討論其子節點“家庭生活”和“女友”雜志之間是否存在關聯就沒有任何意義。但是如果“計算機技術”經常被訂閱，那么檢查其子節點“計算機應用”與“計算機工程”之間是否存在關聯就很有必要。[3]

利用k-項集進行跨層次過濾策略，容許挖掘系統僅僅檢查頻繁k-項集的子節點。由于通常并沒有許多k-項集（特別是當k＞2時）在進行合并后仍是頻繁項集，但是利用這種策略可能會過濾掉一些有價值的模式。

利用單項進行跨層次過濾策略，就是上述兩個極端的綜合。但是這種方法或許會遺漏掉有關低層次項之間的關聯只是。這些項在使用遞減支持闕值時是頻繁項集；即使它們的祖先結點不是頻繁的。例如：若根據相應測光那次的最小支持闕值，在概念層次i中的“新周刊”是頻繁的，但是根據i-1層次的最小支持闕值，它的父結點“娛樂”卻不是頻繁的。這樣會遺漏掉諸如“家庭生活→新周刊”這樣的頻繁關聯隊則。

利用單項進行跨層次過濾策略的一個改進版本，稱為受控利用單項進行跨層次過濾策略。它的具體做法是：設置一個闕值稱為“層次通過闕值”（level passage threshold ），它將容許相對頻繁的項“傳送”到較低層次。換句話說，這種方法容許對那些不滿足最小支持闕值項的后代進行檢查，只要它們滿足“層次通過闕值”。每一個概念層次均有自己相應的“層次通過闕值”。給定一個層次，它的“層次通過闕值”取值，通常在本層次最小支持闕值和下一層最小支持闕值之間值。用戶或許會在高概念層次降低“層次通過闕值”以使相對頻繁的后代能夠得到檢查；而在低概念層次降低“層次通過闕值”，也將會使所有項的后代均能得到檢查。在圖4中，設置層次1的“層次通過闕值”為8%，將使層次2結點“計算機應用”和“計算機工程”得到檢查，并發現是頻繁的；即使它們的父結點“計算機技術”是非頻繁的。建立這一方法，將使得用戶能夠更加靈活的控制在多概念層次上的數據挖掘以減少無效關聯規則的搜索與產生。

圖4 利用受控單項跨層次過濾多層次挖掘

到現在為止，我們討論的頻繁項集挖掘所涉及的項集，都是一個項集中的所有項均屬于同一個概念層次，從而發現諸如“計算機技術幼生活”（計算機技術和生活都屬于層次2）得關聯規則。若要發現跨概念層次的關聯規則，如：“計算機技術→家庭生活”（其中兩個項分屬于層次2和層次3），這樣規則也稱為跨層次關聯規則（cross-level association rules ）。

如果要挖掘層次i和層次j（i＜j）之間的層次關聯規則，那么就應該整個使用層次j的遞減支持闕值，所以使得層次j中的項能夠被分析挖掘出來。

3 基于概念層次樹的多層次關聯規則算法

基本思路：

輸入：交易數據庫TDB，概念層次樹tree，最小支持度Smin和最小可信度Cmin。

輸出：符合最小支持度Smin和最小可信度Cmin的多層次關聯規則。

步驟：

1）對概念層次樹的每個節點進行編碼；

2）ptree：= tree；/*ptree中存放上一次挖掘中能組成頻繁規則的節點，即組成選驗估計的節點/

3）do；

4）抽樣（按TID ），另存為DB'；

5）在概念層次樹ptree’中計算頻繁項集；

6）根據頻繁項集，測試ptree中的節點是否能組成頻繁規則，能組成的加入ptree'；

7）對ptree葉子節點x，如出現在ptree'中，擴展x的子節點x1，x2,…,xn，測試x1，x2,…,xn能否組成頻繁規則。如xi可以，加入ptree'，并擴展xi,循環向下；

8）ptree’中的節點及根節點組成新的ptree；

9）while DB'＜DB；

10）對ptree'中的節點，計算后選規則集c_rules；

11）檢查c_rules中的規則的支持度和可信度，刪除支持度和可信度小于給定值的規則，得規則集rules；

12）凈化規則集rules；刪除冗余規則，刪除誤導規則和無效規則；

13）輸出 rules；

4 基于語義劃分的多層次關聯規則冗余處理

關聯規則挖掘會產生大量的規則，有時候甚至多達數十萬條，要想從如此巨大的規則集合中結合語義信息搜索冗余規則無疑需要很大的運算量，為能更快速準確地對規則進行冗余處理，文中提出前綴樹掃描方法來減少冗余處理過程的運算復雜度，提高處理結果的準確度。

方法主要分為3 部分：1）按照規則前項對規則進行預處理，用規則前項中的項為節點構建前綴樹。這步完成后，把所有規則都壓縮到規則前綴樹集合中。2）結合語義本體遍歷每棵前綴樹，從前綴樹根節點到的其它節點的所有路徑都有可能是一條規則的前項，從根節點開始遍歷前綴樹的每個節點同時查找本體，找出這個節點的關聯節點，組成項目列表，如果該項目列表能構成規則前項，則把它加入冗余規則候選集合中。這步完成后每條規則都被加入相應的冗余規則候選集合，3）掃描每個冗余規則候選集合，進行相應的冗余處理。

4.1 構建前綴樹

使用規則前項中的項為節點構造規則前綴樹。首先，對每條規則的前項進行排序預處理，把第一個項目相同的規則放在一個集合中；對于每個集合，用集合中每條規則前項都含有的相同第一個項目作為前綴樹的根節點，依次掃描集合中的每條規則前項，構造前綴樹， 使得前綴樹從根節點到樹中其它節點的路徑都對應著規則前項。這步需要遍歷規則集合中所有的規則，完成后所有的規則都被包含在前綴樹集合中。

4.2 結合語義本體遍歷前綴樹

scanPrefixTree( pfnode，ontology ，r elType，weig ht，premises）

輸入：前綴樹節點pfnode，本體ontology，關聯類型relType，weight關聯權值，premises 存儲的前綴樹從根節點到其他節點的路徑集合，表示已經發現的所有規則前項輸出：冗余規則候選集合candreds

結合語義本體遍歷規則前綴樹，這步是冗余處理的核心。輸入前綴樹根節點root，本體ontology，關聯類型relType，關聯權值weight，采用深度優先方式遍歷。從前綴樹根節點開始，記錄從根節點到其它節點路徑上的所有節點，如果這些節點能夠成一條規則前項，則建立冗余候選集合。同時遍歷本體，返回與當前節點有指定關聯類型relType且權值大于weight 的關聯節點，如果關聯節點能夠與當前節點對應的路徑上除當前節點的所有節點構成規則前項，則把這條規則加入到相應的冗余候選集合，遞歸地遍歷當前節點的每個子節點。這個過程總的時間代價大約為O（n2）。如此，遍歷完前綴樹后，所有的規則都被加入到相應的冗余候選集合中。

4.3 對冗余規則候選集合進行冗余處理

對每個冗余候選集合進行處理。冗余候選集合中每條規則的前項都是具有前面定義的某一類關系的項集，這時只需要考察候選中每條規則的后項。如果某兩個候選的后項也符合這類關系，那么這條規則被認為是這類型的冗余規則，進行相應的處理。

最后用某手機訂閱服務數據集作為實驗數據進行試驗。實驗表明，使用本文提出的冗余處理方法能有效消除多層關聯規則冗余，使得挖掘出的規則更加符合實際情況，在實際應用更加具有指導意義；同時通過處理冗余和不處理冗余挖掘時間耗費的對比，表明文中提出的方法在時間耗費上也是可以接受的。

5 結論

數據倉庫和數據挖掘技術是當今信息技術領域研究和應用的熱點技術。本文從數據挖掘的概念和特點入手，以郵政報刊發行數據庫為例，討論了數據挖掘技術的有關概念、挖掘的過程和方法，并詳細論述了關聯規則挖掘算法的思想和實現。

[1] 張維明,等.數據倉庫原理與應用[M].北京：電子工業出版社,2002.

[2] 彭木根.數據倉庫技術與實現[M].北京：電子工業出版社,2002.

[3] Claude Seidman.SQL Server2000數據挖掘技術指南.北京：機械工業出版社,2002.