王 銳，曹振強(qiáng)

WANG Rui1, CAO Zheng-qiang2

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

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

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

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

圖1 報(bào)刊概念層次樹

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

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

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

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

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

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

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

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

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

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

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

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

1）層與層獨(dú)立。這是一個(gè)完全寬度搜索。沒有利用任何頻繁項(xiàng)集的有關(guān)知識(shí)來(lái)幫助進(jìn)行項(xiàng)集的修剪。無(wú)論該節(jié)點(diǎn)的父節(jié)點(diǎn)是否為頻繁的，均要對(duì)每一個(gè)節(jié)點(diǎn)進(jìn)行檢查。

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

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

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

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

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

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

圖4 利用受控單項(xiàng)跨層次過濾多層次挖掘

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

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

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

基本思路：

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

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

步驟：

1）對(duì)概念層次樹的每個(gè)節(jié)點(diǎn)進(jìn)行編碼；

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

3）do；

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

5）在概念層次樹ptree’中計(jì)算頻繁項(xiàng)集；

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

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

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

9）while DB'＜DB；

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

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

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

13）輸出 rules；

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

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

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

4.1 構(gòu)建前綴樹

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

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

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

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

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

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

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

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

5 結(jié)論

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

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

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

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