王 銳，曹振強

WANG Rui1, CAO Zheng-qiang2

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

1 多層次關(guān)聯(lián)規(guī)則描述

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

以郵政報刊發(fā)行為例：

圖1 報刊概念層次樹

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

2 挖掘多層次關(guān)聯(lián)規(guī)則的方法

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

多層次挖掘關(guān)聯(lián)規(guī)則算法的闕值取值分析：

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

圖2 利用統(tǒng)一最小支持闕值的多層次挖掘

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

但是利用統(tǒng)一的最小支持闕值也存在一些問題。由于低層次項不可能比相應(yīng)高層次項出現(xiàn)的次數(shù)更多。如果最小支持闕值設(shè)置過高，那就可能忽略了一些低層次中有意義的關(guān)聯(lián)關(guān)系。若闕值設(shè)置過小，則可能產(chǎn)生過多的高層次無意義的關(guān)聯(lián)關(guān)系。因此產(chǎn)生了第二種算法。

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

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

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

利用遞減闡值挖掘多層次關(guān)聯(lián)知識，可以選擇若干搜索策略：

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

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

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

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

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

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

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

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

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

如果要挖掘?qū)哟蝘和層次j（i＜j）之間的層次關(guān)聯(lián)規(guī)則，那么就應(yīng)該整個使用層次j的遞減支持闕值，所以使得層次j中的項能夠被分析挖掘出來。

3 基于概念層次樹的多層次關(guān)聯(lián)規(guī)則算法

基本思路：

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

輸出：符合最小支持度Smin和最小可信度Cmin的多層次關(guān)聯(lián)規(guī)則。

步驟：

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

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

3）do；

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

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

6）根據(jù)頻繁項集，測試ptree中的節(jié)點是否能組成頻繁規(guī)則，能組成的加入ptree'；

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

8）ptree’中的節(jié)點及根節(jié)點組成新的ptree；

9）while DB'＜DB；

10）對ptree'中的節(jié)點，計算后選規(guī)則集c_rules；

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

12）凈化規(guī)則集rules；刪除冗余規(guī)則，刪除誤導(dǎo)規(guī)則和無效規(guī)則；

13）輸出 rules；

4 基于語義劃分的多層次關(guān)聯(lián)規(guī)則冗余處理

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

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

4.1 構(gòu)建前綴樹

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

4.2 結(jié)合語義本體遍歷前綴樹

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

輸入：前綴樹節(jié)點pfnode，本體ontology，關(guān)聯(lián)類型relType，weight關(guān)聯(lián)權(quán)值，premises 存儲的前綴樹從根節(jié)點到其他節(jié)點的路徑集合，表示已經(jīng)發(fā)現(xiàn)的所有規(guī)則前項輸出：冗余規(guī)則候選集合candreds

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

4.3 對冗余規(guī)則候選集合進行冗余處理

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

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

5 結(jié)論

數(shù)據(jù)倉庫和數(shù)據(jù)挖掘技術(shù)是當(dāng)今信息技術(shù)領(lǐng)域研究和應(yīng)用的熱點技術(shù)。本文從數(shù)據(jù)挖掘的概念和特點入手，以郵政報刊發(fā)行數(shù)據(jù)庫為例，討論了數(shù)據(jù)挖掘技術(shù)的有關(guān)概念、挖掘的過程和方法，并詳細論述了關(guān)聯(lián)規(guī)則挖掘算法的思想和實現(xiàn)。

[1] 張維明,等.數(shù)據(jù)倉庫原理與應(yīng)用[M].北京：電子工業(yè)出版社,2002.

[2] 彭木根.數(shù)據(jù)倉庫技術(shù)與實現(xiàn)[M].北京：電子工業(yè)出版社,2002.

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