李 旭, 董爭鳴, 吳洪森

(浙江警察學院,浙江杭州 310053)

0 引言

隨著網(wǎng)絡(luò)的飛速發(fā)展,傳統(tǒng) Web在信息顯示和處理上的不足之處也更加顯著,而語義網(wǎng)作為一種新型的網(wǎng)絡(luò)結(jié)構(gòu),較好地克服了這些問題。正如Tim Berners-Lee所描繪,語義網(wǎng)代表著網(wǎng)絡(luò)的未來,必將成為下一代互聯(lián)網(wǎng)的神經(jīng),而基于語義的 Web挖掘作為與這一趨勢相適應的技術(shù),也必將成為Web挖掘研究的新熱點。

Web挖掘通常分為:Web內(nèi)容挖掘(Web contentmining),Web結(jié)構(gòu)挖掘(Web structure mining)和 Web使用記錄挖掘(Web usagemining)三類。本文從 Web結(jié)構(gòu)挖掘的典型 Apriori算法入手進行分析。Web內(nèi)容挖掘是對 Web頁面上的數(shù)據(jù)內(nèi)容進行挖掘,它是從 WWW的組織結(jié)構(gòu)和鏈接關(guān)系中推導知識。Web內(nèi)容挖掘通過分析一個網(wǎng)頁上的內(nèi)容建立數(shù)據(jù)庫,通過不同的數(shù)據(jù)庫之間的元記錄之間的關(guān)聯(lián)性即查找頻率性建立關(guān)聯(lián)挖掘規(guī)則,并由此獲得有關(guān)不同頁面間相似度和關(guān)聯(lián)度的信息規(guī)則,從而實現(xiàn)對 Web網(wǎng)頁上語義內(nèi)容的挖掘。

1 語義 Web挖掘的相關(guān)基本理論

1.1 語義的 Web挖掘

WEB挖掘是一個極其復雜的過程,它不同于傳統(tǒng)的數(shù)據(jù)倉庫技術(shù)和簡單的知識發(fā)現(xiàn)(KDD),它面對的海量信息不全是簡單的結(jié)構(gòu)化數(shù)據(jù),而常常為半結(jié)構(gòu)化的數(shù)據(jù),如文本、圖形、圖像數(shù)據(jù),甚至是異構(gòu)型數(shù)據(jù)。發(fā)現(xiàn)知識的方法可以是數(shù)學的,也可以是非數(shù)學的;可以是演繹的,也可以是歸納的。

語義 Web以本體形式所描述的清楚語義知識可以應用于不同目的的 Web挖掘。在 Web內(nèi)容挖掘中可以利用本體知識來選擇最相關(guān)的源數(shù)據(jù)、預處理輸入的數(shù)據(jù)和評價所發(fā)現(xiàn)的模式。由于目前的Web主要是用來顯示信息,Web上的數(shù)據(jù)不包含語義信息,因此常常使所選擇進行 Web內(nèi)容挖掘的數(shù)據(jù)中一方面包含大量的冗余數(shù)據(jù),另一方面也可能使許多需要的數(shù)據(jù)卻沒選擇到。相反,當用語義Web數(shù)據(jù)進行數(shù)據(jù)挖掘時,由于數(shù)據(jù)中已經(jīng)包含了清楚的語義信息,使我們在選擇源數(shù)據(jù)時可以利用這些語義信息,選擇最相關(guān)的數(shù)據(jù),去除那些冗余的數(shù)據(jù);另外,也可以利用語義知識對 Web挖掘中用到的源數(shù)據(jù)進行預處理,可以大大減少算法的運算量,提高算法的效率。

1.2 關(guān)聯(lián)規(guī)則的挖掘結(jié)構(gòu)

關(guān)聯(lián)規(guī)則挖掘方法是以數(shù)據(jù)立方體的數(shù)據(jù)結(jié)構(gòu)為基礎(chǔ),它是把關(guān)聯(lián)規(guī)則挖掘和挖掘算法、OLAP關(guān)聯(lián)技術(shù)合成起來的方法。這里重點討論 OLAP關(guān)聯(lián)規(guī)則挖掘的結(jié)構(gòu)。OLAP關(guān)聯(lián)規(guī)則挖掘結(jié)構(gòu)由數(shù)據(jù)倉庫,OLAP引擎和關(guān)聯(lián)規(guī)則挖掘引擎三部分組成。

(1)數(shù)據(jù)倉庫

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

(2)OLAP引擎

一旦把工作數(shù)據(jù)立方體建好,在挖掘過程中所需要的完整信息就保存在數(shù)據(jù)立方體中。這樣,數(shù)據(jù)立方體就可以作為挖掘的數(shù)據(jù)源,也可作為原始數(shù)據(jù)和挖掘任務(wù)之間的接口。因為數(shù)據(jù)立方體含有的數(shù)據(jù)量非常大,所以有必要對數(shù)據(jù)立方體建立豐富的運算函數(shù)。OLAP引擎的主要任務(wù)就是計算用戶的 OLAP指令,最后把結(jié)果返回給用戶界面層?？梢钥闯?OLAP引擎在OLAP關(guān)聯(lián)規(guī)則挖掘的結(jié)構(gòu)中具有非常重要的作用。

(3)關(guān)聯(lián)規(guī)則挖掘引擎

關(guān)聯(lián)規(guī)則挖掘引擎是關(guān)聯(lián)規(guī)則挖掘系統(tǒng)中非常重要的組成部分。一般情況下,在產(chǎn)生工作數(shù)據(jù)立方體后,發(fā)現(xiàn)關(guān)聯(lián)規(guī)則的任務(wù)可以分為兩步。第一步是找出所有符合支持度的經(jīng)常項目集。在此階段,輸入的是與任務(wù)相關(guān)的工作數(shù)據(jù)立方體,支持度的最小值和用戶的限制條件。輸出的是滿足條件的經(jīng)常項目集。根據(jù)關(guān)聯(lián)規(guī)則的類型,輸出的經(jīng)常項目集可以是單維經(jīng)常項目集,多維經(jīng)常項目集或合成項目集。第二步是利用經(jīng)常項目集產(chǎn)生期望的關(guān)聯(lián)規(guī)則。在此階段,輸入的是上一階段輸出的經(jīng)常項目集,置信度的最小值和用戶的限制條件。輸出的是滿足置信度和用戶限制條件的關(guān)聯(lián)規(guī)則。

2 面向語義化的 Web數(shù)據(jù)挖掘算法

本研究課題提出的改進算法是通過數(shù)據(jù)庫和Web日志構(gòu)建概念層次樹,在繼承 Apriori算法思想的基礎(chǔ)上,根據(jù)概念層次樹來挖掘多層包括交叉層次的關(guān)聯(lián)規(guī)則。

該改進算法輸入的是 log表和支持度閾值,輸出的是多層頻繁項集 L。在對 Apriori算法進行改進、進行 OLAP關(guān)聯(lián)規(guī)則挖掘時,可以分為三個步驟:

①預處理。從 log表過濾出相關(guān)的信息,然后根據(jù)概念層次樹,自頂向下,對數(shù)據(jù)庫中的項進行編碼,得到編碼后的數(shù)據(jù)庫 D。

②執(zhí)行改進的 Apriori算法,分別找出各個層次的頻繁項集。

③找出交叉層次的關(guān)聯(lián)規(guī)則。

2.1 預處理

輸入:log表和支持度閾值;

輸出:編碼后的數(shù)據(jù)庫 D。

由于 Apriori算法會產(chǎn)生大量的候選集以及需要重復掃描數(shù)據(jù)庫,因此對數(shù)據(jù)庫 log表進行相關(guān)信息的過濾預處理,具體按照以下步驟執(zhí)行:

①從 log表過濾出相關(guān)的信息,得出經(jīng)過數(shù)據(jù)清洗后的 log表 d。

②根據(jù)概念層次樹,自頂向下,對數(shù)據(jù)庫中的項進行編碼,得到編碼后的數(shù)據(jù)庫 D。概念層次樹可以由專家給出,也可以從數(shù)據(jù)庫和 Web日志生成。經(jīng)過 log表清洗后的表 d,刪除了大量無關(guān)的候選集,從而大大減少了掃描數(shù)據(jù)庫的次數(shù),同時也可以為后面的執(zhí)行步驟中刪去冗余的多層(后代)頻繁項集。

2.2 執(zhí)行算法

輸入:編碼后的 D及各個層次的支持度閾值;

輸出:分別找出各個層次的頻繁項集。

當計算多層次事務(wù)數(shù)據(jù)庫中項集的支持度時,普通的算法是按普通組合的方法計算交叉層次的支持度,這樣數(shù)據(jù)挖掘的開銷巨大;而改進算法在計算某項集的支持度時,按該項集所在的層次分開計算,含交叉層次的項集,采用區(qū)間支持度的方法來表示其支持度。

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

對于每層(設(shè)層號為 i)尋找頻繁項集,均執(zhí)行下面步驟。

(1)找出頻繁 l項集

掃描編碼后的數(shù)據(jù)庫 D,收集每項的支持度。按支持度降序排列,刪去不滿足對應第 i層的最小支持度的項,結(jié)果為頻繁 l項集,存入頻繁項表 L[i];同時,刪去冗余的多層(后代)頻繁 l項集。

(2)構(gòu)建 Apriori算法樹

1)根節(jié)點標記為 null,它的子節(jié)點為一個項前綴子樹的集合,還有一個頻繁項組成的頭表。

2)每個項前綴子樹的節(jié)點有 3個域:itemname,count,node-link。item-name記錄該節(jié)點所代表的項的名字,count記錄所在路徑代表的交易中達到此節(jié)點的交易個數(shù),node_link指向下一個具有同樣的 item-name域的節(jié)點,如果沒有這樣一個節(jié)點,就為 null。

3)頻繁項頭表的每個表項由兩個域組成:itemname和 node-link。 node-link指向 Apriori-tree中具有與該表項相同 item-name域的第1個節(jié)點。

4)創(chuàng)建 Apriori算法樹根節(jié)點,記為 T,并標記為 null。對于 D中每個會話 session,執(zhí)行:選擇 session中的頻繁項,并按 L[i]中的次序排序。設(shè)排序后的頻繁項表為[p|P],其中 p是第1個元素,P是剩余元素的表。調(diào)用 insert-tree([p|P],T)。

函數(shù) insert-tree([p|P],T)的運行如下:如果 T有一個子結(jié)點 N,其中 N.item-name=p。itemname,則將 N的 count域值增加 1;否則,創(chuàng)建一個新節(jié)點 N,使它的 count為 1,使它的父節(jié)點為 T,并且使它的 node-link和那些具有相同 item-name域串起來。如果 P非空,則遞歸調(diào)用 insert-tree(P,N)。

(3)遞歸挖掘 Apriori算法樹

Apriori算法樹的挖掘通過調(diào)用預先設(shè)計好的子函數(shù)來實現(xiàn)。

執(zhí)行了改進后的算法,一方面能夠在有效地找出各個層次的頻繁項集的同時,保證算法的效率性;另一方面,在最低層或原始層的數(shù)據(jù)項之間,由于在計算某項集的支持度時,按該項集所在的層次分開計算,含交叉層次的項集,采用區(qū)間支持度的方法來表示其支持度,因此能夠比較容易地找出強關(guān)聯(lián)規(guī)則及多層次的挖掘規(guī)則。

2.3 找出交叉層次的關(guān)聯(lián)規(guī)則

輸入:各個層次的頻繁項集;

輸出:交叉層次的頻繁項集 L。

從各個層次的頻繁項集中計算出交叉層次的頻繁項集 L,避免了在最低層或原始層的數(shù)據(jù)項之間尋找關(guān)聯(lián)規(guī)則。在較高的概念層尋找關(guān)聯(lián)規(guī)則不僅具有相對較高的執(zhí)行效率,而且發(fā)現(xiàn)的強關(guān)聯(lián)規(guī)則也相對更加容易,其可能提供知識也更具有普遍意義。

尋找交叉層次的關(guān)聯(lián)規(guī)則的基本思想:自底向上,從最低層的頻繁項集開始,計算交叉層次的頻繁項集。對交叉層次的頻繁項集,根據(jù)滿足最小支持度閾值的概率來篩選出合適的頻繁項集,刪去不滿足概率的項集。

在 OLAP關(guān)聯(lián)規(guī)則挖掘時,把要挖掘的維稱為項目維,而把與此維相關(guān)的另外的維稱為事務(wù)處理維,產(chǎn)生經(jīng)常項目集的算法和 Apriori算法類似,只是在判斷是否滿足支持度時,Apriori算法掃描的是交易數(shù)據(jù)表,而該方法掃描的是部分數(shù)據(jù)立方體。由于維之內(nèi)關(guān)聯(lián)規(guī)則挖掘的經(jīng)常項目集產(chǎn)生方法和Apriori算法一樣,而合成關(guān)聯(lián)規(guī)則挖掘的經(jīng)常項目集產(chǎn)生方法是維之內(nèi)關(guān)聯(lián)規(guī)則挖掘和維之間關(guān)聯(lián)規(guī)則挖掘經(jīng)常項目集產(chǎn)生方法的綜合,本文介紹維之間關(guān)聯(lián)規(guī)則挖掘的經(jīng)常項目集產(chǎn)生方法。

維之間關(guān)聯(lián)規(guī)則就是存在于一組維之內(nèi)的相關(guān)規(guī)則。算法的整個過程也是以 Apriori算法為基礎(chǔ)。因為項目存在于不同的維中,這里通過利用數(shù)據(jù)立方體的概念分層結(jié)構(gòu)來直接獲取每個項目集的置信度。這個算法的輸入條件是 n維的數(shù)據(jù)立方體 CB[d1,d2,……dn]和所要求的最低支持度。

按某項集所在的層次分開計算頻繁項集,含交叉層次的項集,采用區(qū)間支持度的方法來表示其支持度,實現(xiàn)了交叉層次的頻繁項集 L的快速計算。同時,對于強關(guān)聯(lián)規(guī)則的挖掘也提供了更加有效的挖掘算法,在多個概念層的項之間找有趣的關(guān)聯(lián)比僅在原始層數(shù)據(jù)之間更容易,在較高的概念層發(fā)現(xiàn)的強關(guān)聯(lián)規(guī)則更具普遍意義。

2.4 算法性能仿真

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

測試了算法的隨記錄的增加時間的變化(時間復雜性),將測試數(shù)據(jù)庫的元組數(shù)從 1 000開始,逐漸遞增到 5 000。兩算法的時間復雜性數(shù)據(jù)曲線如圖1所示,從圖中可以發(fā)現(xiàn),兩個算法的時間復雜性均較好,不過隨數(shù)據(jù)庫規(guī)模的增大,針對 Apriori算法的改進,OLAP結(jié)構(gòu)算法在執(zhí)行時間更為迅速,而且在時間的增長上更為平緩一些,所以本論文提出的改進算法是可行的。

圖1 算法仿真實驗結(jié)果比較圖

3 結(jié)語

語義 Web研究的主要目的就是擴展當前的Web,使得 Web中所有信息都具有語義,是計算機能夠理解和處理的,便于人和計算機之間的交互與合作,因而其研究的側(cè)重點就是如何把信息表示為計算機能夠理解和處理的形式,即帶有語義,這是語義 Web挖掘研究的主要內(nèi)容。

語義 Web上的數(shù)據(jù)挖掘算法可以應用于各種領(lǐng)域。如當前 Web上的搜索引擎主要是使用基于關(guān)鍵詞的查找策略,這使查找效率非常低下,本研究課題通過對傳統(tǒng)的挖掘算法 Apriori算法的改進,通過運用對語義化的內(nèi)容建立關(guān)聯(lián)層次數(shù)據(jù)倉庫的方法,實現(xiàn)了語義化的 Web快速挖掘,從而大大提高了 Web搜索的工作效率。在 Web服務(wù)中利用挖掘算法將大大改進 Web服務(wù)的能力和范圍,下一步的研究重點是在 Web挖掘中利用語義 Web上的本體知識,同挖掘算法結(jié)合起來,從而從本質(zhì)上大大改進 Web挖掘的結(jié)果和提高 Web挖掘的效率。

[1] ChakrabartiS.Automatic resource compilation by analyzing hyperlink structure and assciated text[J].In:Proc.of the 7th Worldwide Web con f.(WWW 7),1998,30(7):239-244.

[2] Wang J C,Huang Y,Wu G S,et al.Web mining:knowledge discovery on the Web Systems[C].Man,and Cybernetics,1999.IEEE SMC'99 Conference Proceedings,1999:116-121.

[3] Ng R,Lakshmanan L V S,Han J,et al.Exp loratory mining and pruning optimizations of constrained associations ru les[C].Proceedings of ACM SIGMOD International Con ference on Managementof Data,13～24,June 1998.

[4] Gruber T R.Towards Principles for the Design of Ontologies used for Knowledge Sharing[J].International Journalof Human-Computer Studies,43:907-928,1995.

[5] Ying Ding＆Dieter Fensel.Ontology Library Systems:The Key to sueeessful Ontology Reuse.In The First Semantie Web Working SymPosium[C].Stan ford University,California,USA,July30-August,(l),2001,104-111.

[6] Chen JP,Bian F L,Fu ZL,etal.An Imp roved Algorithm of Apriori[J].Geomatics and Inform ation Science of Wuhan University,2003,(1):94-99.