分布式數(shù)據(jù)庫中關(guān)系數(shù)據(jù)正負關(guān)聯(lián)規(guī)則挖掘

吳愛華，陳出新

(廣州大學華軟軟件學院，廣東廣州 510990)

1 引言

關(guān)聯(lián)規(guī)則挖掘是指從海量數(shù)據(jù)中得到數(shù)據(jù)間有價值、互相聯(lián)系的相關(guān)內(nèi)容[1]。關(guān)聯(lián)規(guī)則挖掘是目前數(shù)據(jù)挖掘領域的研究重點，在數(shù)據(jù)庫中存在重要易被發(fā)現(xiàn)的知識即為數(shù)據(jù)關(guān)聯(lián)，關(guān)聯(lián)是在兩個及以上變量的取值之間存在一定的規(guī)律性，關(guān)聯(lián)規(guī)則能夠表明諸多事務中之間的潛在聯(lián)系[2-4]。近年來，隨著信息技術(shù)的不斷發(fā)展，分布式數(shù)據(jù)庫越來越多，通過挖掘數(shù)據(jù)庫中數(shù)據(jù)進行企業(yè)戰(zhàn)略抉擇和企業(yè)管理服務，這些數(shù)據(jù)之間的關(guān)系錯綜復雜，且存在很多重復冗余數(shù)據(jù)，對這些數(shù)據(jù)關(guān)系確定和有關(guān)數(shù)據(jù)的挖掘成為當前研究的熱點問題。

吳瓊等人[5]提出基于多目標煙花算法的關(guān)聯(lián)規(guī)則挖掘方法。該方法首先分析了關(guān)聯(lián)規(guī)則的量化特征，引入多目標煙花算法，來降低反向?qū)W習陷入局部最優(yōu)的幾率，在數(shù)據(jù)庫中設計冗余數(shù)據(jù)淘汰原則，且在保證數(shù)據(jù)多樣化的基礎上，設計關(guān)聯(lián)規(guī)則集合，該方法通過多目標煙花算法進行整體搜索關(guān)聯(lián)規(guī)則，有效提升算法收斂速度，具有較好的穩(wěn)定性、可靠性及性能之間的均衡性，但該方法在關(guān)聯(lián)數(shù)據(jù)挖掘中對其正負關(guān)系考慮甚少，存在數(shù)據(jù)挖掘準確度較低等問題。丁勇等人[6]研究了一種基于Hadoop的關(guān)聯(lián)規(guī)則挖掘算法。該方法通過設置關(guān)聯(lián)規(guī)則挖掘的層次，通過在每一個分布式節(jié)點數(shù)據(jù)中設置前綴共享樹，通過對設置的共享樹進行全局搜索，逐層對每一個數(shù)據(jù)進行函數(shù)輸入，最后通過調(diào)用reduce函數(shù)匯總挖掘后的關(guān)聯(lián)規(guī)則數(shù)據(jù)。該方法通過分治策略和遞歸調(diào)用的方式，得到能夠滿足最小支持度閾值的頻繁項集，有效提升算法的運行效率。該方法對數(shù)據(jù)的挖掘效率較高，但由于數(shù)據(jù)庫中其它數(shù)據(jù)的干擾，導致挖掘過程中抗干擾能力較低。

基于上述方法中存在的問題，提出了一種新的分布式數(shù)據(jù)庫中關(guān)系數(shù)據(jù)正負關(guān)聯(lián)規(guī)則挖掘方法。通過對生成的正關(guān)聯(lián)規(guī)則和負關(guān)聯(lián)規(guī)則，實現(xiàn)分布式數(shù)據(jù)庫中關(guān)系數(shù)據(jù)正負關(guān)聯(lián)規(guī)則挖掘。與傳統(tǒng)挖掘方法具有一定優(yōu)勢。

2 關(guān)聯(lián)規(guī)則的基本概念和性質(zhì)

2.1 關(guān)聯(lián)規(guī)則的定義

為了實現(xiàn)分布式數(shù)據(jù)庫中關(guān)系數(shù)據(jù)正負關(guān)聯(lián)規(guī)則挖掘，首先分析關(guān)聯(lián)規(guī)則的定義。

假設項的集合為I={i1，i2，…in}，D用以描述任務相關(guān)數(shù)據(jù)，表示數(shù)據(jù)庫事務的集合，T用以描述每個事務，表示項的集合，令T?I，每個事務各有唯一的標識符，表示為TID，K為一個項集，事務T涵蓋K當且僅當K?T。

定義1：關(guān)聯(lián)規(guī)則是形如K→H的蘊涵式，則K?I，H?I，且K∩H=Φ。

定義2：置信度和支持度[7]。規(guī)則K→H的支持度S，表示支持度是任務相關(guān)數(shù)據(jù)中事務包含K∪H的百分比，表示概率p(K∪H)，即

(1)

其中，|D|用以描述事務數(shù)據(jù)庫的個數(shù)。

規(guī)則K→H的可信度為C，表示同時包含K項集和H項集，可表示為條件概率P(H|K)，即：

(2)

其中，|A|用以描述K項集的事務個數(shù)。

2.2 關(guān)聯(lián)規(guī)則的性質(zhì)

性質(zhì)1：假設{Y1，Y2，…Yn}表示項集，且Y?I，Y≠Φ，Ω?Y，若Y表示頻繁項集，在數(shù)據(jù)庫事務集和最小支持度為固定值的條件下[8]，則Ω可表示頻繁項集。

性質(zhì)2：假設{Y1，Y2，…Yn}表示項集，且Y?Γ?I，Y≠Φ，若Y表示非頻繁項集，在數(shù)據(jù)庫事務集和最小支持度為固定值的條件下，則Γ同樣表示非頻繁項集。

3 關(guān)系數(shù)據(jù)正負關(guān)聯(lián)規(guī)則挖掘?qū)崿F(xiàn)

3.1 挖掘過程分析

關(guān)聯(lián)規(guī)則挖掘過程是針對具有抉擇性和決策性的關(guān)聯(lián)規(guī)則進行發(fā)掘，挖掘感興趣的相關(guān)項目，滿足專家設定的最小置信度和支持度閾值[9-10]，挖掘步驟為：

步驟1：生成頻繁項目集。通過比對支持度將高于最小支持度的項集組合成頻繁項目集。

步驟2：生成可信關(guān)聯(lián)規(guī)則。通過對比置信度，將高于最小置信度規(guī)則定位可信關(guān)聯(lián)規(guī)則。

假設數(shù)據(jù)庫D為顧客購買信息，分為6個事務，如表1所示。

表1 關(guān)聯(lián)規(guī)則數(shù)據(jù)庫信息

設項目集A={酸奶，芒果，薯片，面包}，最小支持度為0.5，由表1可知興趣項為事務1、2、3、4、5和6中包含酸奶=100%，事務2、4、5和6包含芒果=66.66%，薯片和面包均包含33.33%，將其視為不感興趣項，關(guān)聯(lián)規(guī)則為酸奶?芒果，支持度分別為

supp(酸奶)=6/6=100%=1

supp(酸奶?芒果)=4/6=66.66%=0.67

置信度為：

根據(jù)設定的最小支持度為0.5，酸奶?芒果的關(guān)聯(lián)規(guī)則認定為興趣項，表示購買酸奶和芒果之間存在關(guān)聯(lián)關(guān)系。

3.2 負關(guān)聯(lián)規(guī)則分析

假設任務相關(guān)數(shù)據(jù)D為項集K和Y，關(guān)聯(lián)規(guī)則K?Y，K?Y，K?Y表示負關(guān)聯(lián)規(guī)則。

負關(guān)聯(lián)規(guī)則與正關(guān)聯(lián)規(guī)則的支持度和置信度定義接近，區(qū)別在于正關(guān)聯(lián)規(guī)則中的K和Y在負關(guān)聯(lián)規(guī)則中表示為K和Y。支持度的計算方法為

supp(K∪Y)=supp(K)-supp(K∪Y)

(3)

supp(K∪Y)=supp(Y)-supp(K∪Y))

(4)

置信度計算方法為

(5)

教學查房是臨床實踐教學的一個重要環(huán)節(jié)，是醫(yī)學生培養(yǎng)的必經(jīng)過程。通過教學查房，留學生開始進入醫(yī)生角色，深入臨床實踐。在腫瘤學教學查房中，教師應不斷提升自身教學水平，應用適應于留學生特點的方式進行教學活動，鼓勵學生積極參與、主動思考，培養(yǎng)學生綜合能力，促進師生協(xié)作交流，完善教學中的不足，最終提高留學生教學質(zhì)量。

(6)

(7)

尋找支持度和置信度大于指定的最小支持度和最小置信度的三種形式規(guī)則為負關(guān)聯(lián)規(guī)則[11]。

3.3 相關(guān)系數(shù)分析

在正負關(guān)聯(lián)規(guī)則進行挖掘時，包含多個負關(guān)聯(lián)規(guī)則和一個正關(guān)聯(lián)規(guī)則等待挖掘。為了對挖掘的關(guān)聯(lián)規(guī)則類型進行判斷，若有項目集K和項目集Y，利用相關(guān)系數(shù)(corrK，Y)尋找兩者之間的關(guān)聯(lián)，即

(8)

其中，相關(guān)系數(shù)的取值范圍為(-∞，+∞)，但存在三種可能影響相關(guān)系數(shù)的具體取值，即：

1)當corrK，Y>1時，表示項目集K和項目集Y正相關(guān)，表明在某個事務中包含的項目集K數(shù)量與項目集Y數(shù)量成正比，即正關(guān)聯(lián)關(guān)系。

2)當corrK，Y=1時，表示項目集K和項目集Y沒有關(guān)系，表明某事務中包含的項目集Y與是否有項目集K不存在關(guān)聯(lián)。

3)當corrK，Y<1時，表示項目集K和項目集Y負相關(guān)，表明在某個事務中包含的項目集K數(shù)量與項目集Y數(shù)量成反比，即負關(guān)聯(lián)關(guān)系。

通過對相關(guān)系數(shù)的確定，以及分析三種具有影響程度的相關(guān)系數(shù)情形，實現(xiàn)關(guān)聯(lián)規(guī)則相關(guān)系數(shù)的確定。

3.4 權(quán)重相關(guān)系數(shù)確定

1)關(guān)聯(lián)規(guī)則的權(quán)重確定

假設關(guān)聯(lián)規(guī)則{k1，k2，…kn}表示總規(guī)則集中的具體關(guān)聯(lián)規(guī)則，子數(shù)據(jù)庫的關(guān)聯(lián)規(guī)則為{G1，G2，…Gn}，Gi的權(quán)重為：

(9)

其中，i=1，2，…，n，Num(G)用以描述涵蓋r規(guī)則的數(shù)據(jù)庫數(shù)量。

2)數(shù)據(jù)庫權(quán)重確定

假設子數(shù)據(jù)庫為{f1，f2，…fm}，ki和f表示總關(guān)聯(lián)規(guī)則集，Gi(i=1，2，…，n)表示關(guān)聯(lián)規(guī)則集中具體的關(guān)聯(lián)規(guī)則，則數(shù)據(jù)庫的權(quán)重為

(10)

3)權(quán)重合成

若數(shù)據(jù)庫中有規(guī)則K?Y存在，則支持度為

(11)

此時獲取的數(shù)據(jù)關(guān)聯(lián)規(guī)則的置信度為

(12)

在上述分析基礎上，假設最小支持度和最小置信度一定時，則

(13)

其中，a表示項目集K和項目集Y之間關(guān)聯(lián)的置信度，x2(1)用以表示K和Y之間是否互相獨立的值。通過Apriori算法可產(chǎn)生頻繁相集M。

將corrKY與最小相關(guān)系數(shù)進行比較，若corrKY大于最小相關(guān)系數(shù)使K?Y或則Y?K為強關(guān)聯(lián)規(guī)則，反之則為負關(guān)聯(lián)規(guī)則或弱關(guān)聯(lián)規(guī)則。

在上述分析中，通過對權(quán)重相關(guān)系數(shù)的獲取，完成置信度和支持度的確定，實現(xiàn)關(guān)系數(shù)據(jù)正負關(guān)聯(lián)規(guī)則挖掘。

4 實驗分析

4.1 實驗環(huán)境

實驗對某電信事務分布式數(shù)據(jù)庫中關(guān)系數(shù)據(jù)進行測試挖掘，該數(shù)據(jù)庫中共包含Q1、Q2、Q3三個數(shù)據(jù)庫，分別為Q1={(A，D，G);(S，D)}；Q2={(A，D，H);(A，D);(A，D，G)}；Q3={(A，S，G);(G);(S，D，H);(A，F(xiàn));(S，H)}。實驗操作系統(tǒng)為Windows2000，CPU為Pentium Ⅲ—733MHz。

4.2 實驗參數(shù)

設最小支持度為0.3，最小置信度為0.3，不同最小支持度為0.4，不同最小置信度為0.6，a為0.05。則生成規(guī)則為A?G，S?D，S?G，G?SD，S?FG，F(xiàn)?SG，D?F，D?G，F(xiàn)?G，則

(14)

4.3 結(jié)果分析

為了驗證所提方法的有效性，實驗采用本文方法對樣本數(shù)據(jù)進行相關(guān)系數(shù)和權(quán)重系數(shù)的確定，實驗結(jié)果如表2、3和表4 所示。

表2 相關(guān)系數(shù)確定分析

分析表2中數(shù)據(jù)可知，采用本文方法后生成的9個規(guī)則中，其中生成了3個為負規(guī)則和1個弱規(guī)則，負規(guī)則分別為A?G、D?G和F?G，弱規(guī)則為D?F，其余5個均為強關(guān)聯(lián)規(guī)則，表明本文算法可有效識別結(jié)果規(guī)則集中的負關(guān)聯(lián)規(guī)則和弱關(guān)聯(lián)規(guī)則，確保數(shù)據(jù)庫中關(guān)聯(lián)數(shù)據(jù)挖掘更加準確，驗證了本文方法的有效性。

實驗中，計算Q1、Q2和Q3三個數(shù)據(jù)庫的權(quán)重系數(shù)：corr1、corr2和corr3分別為0.212、0.301和0.498。通過各數(shù)據(jù)庫的權(quán)重系數(shù)合成得到頻繁項集FS={A，S，D，F(xiàn)，H}，得到FS={A，S，D}，獲得的A、S和D的支持度和權(quán)重系數(shù)結(jié)果如表3 所示：

表3 A、S和D的支持度和權(quán)重系數(shù)統(tǒng)計表

由表3可知，A?D之間不存在關(guān)聯(lián)關(guān)系，其中，A?S，S?D之間存在負關(guān)聯(lián)關(guān)系。由于不同最小支持度和不同最小置信度為0.4和0.6，通過A、S和D的計算支持度和置信度如表4所示。

表4 A、S和D的支持度和置信度統(tǒng)計

由表4可知，置信度都能滿足最小值的要求，但是支持度只有A﹁ S滿足，說明只有A﹁ S有意義，通過采用本文方法確定的支持度符合數(shù)據(jù)挖掘的規(guī)則，得到的結(jié)果均在符合要求之內(nèi)，表明本文算法具有一定效用。

為了進一步驗證本文方法的有效性，實驗通過對比的方法，實驗對比本文方法、文獻[5]基于多目標煙花算法的關(guān)聯(lián)規(guī)則挖掘算法和文獻[6]一種基于Hadoop的關(guān)聯(lián)規(guī)則挖掘算法，在不同最小支持度和不同事物數(shù)條件下，三種算法的挖掘的執(zhí)行時間，結(jié)果如圖的測試結(jié)果如圖1所示。

圖1 三種算法的挖掘執(zhí)行時間對比結(jié)果

分析圖1(a)中結(jié)果可以發(fā)現(xiàn)，隨著最小支持度的變化，本文挖掘方法在求取頻繁項集的時間明顯少于兩種挖掘方法，當最小支持度超過10%后，三種挖掘方法的所需時間逐漸接近，趨近于定值。圖1(b)中隨著事務集數(shù)量的逐漸增多，三種挖掘方法所需時間都在隨之增多，但是本文挖掘方法的執(zhí)行時間增長的趨勢相對平緩，而另外兩種挖掘方法的執(zhí)行時間增長較快，尤其是基于多目標煙花算法的關(guān)聯(lián)規(guī)則挖掘算法，其增長速度最快。相比之下，所提方法的挖掘方法執(zhí)行需要的時間較短，這是由于所提挖掘方法利用多級支持度從頻繁項集中生成正關(guān)聯(lián)規(guī)則，結(jié)合根據(jù)頻繁項集和非頻繁項集生成負關(guān)聯(lián)規(guī)則，通過最小支持度合理設置相關(guān)置信度，引入不同權(quán)重值于各數(shù)據(jù)庫中，實現(xiàn)分布式數(shù)據(jù)庫中關(guān)系數(shù)據(jù)正負關(guān)聯(lián)規(guī)則的挖掘，進而縮短了任務執(zhí)行的挖掘時間。表明本文挖掘方法在數(shù)據(jù)挖掘過程中性能優(yōu)勢明顯較好，具有更好的效果和適用性。

5 結(jié)論

隨著經(jīng)濟的發(fā)展，企業(yè)全球化進程不斷加深，分布式數(shù)據(jù)庫成為眾多企業(yè)的首選。企業(yè)為了戰(zhàn)略抉擇和服務，同家企業(yè)各分布式數(shù)據(jù)庫之間的業(yè)務信息數(shù)據(jù)需要進行必要的關(guān)聯(lián)。本文研究的分布式數(shù)據(jù)庫中關(guān)系數(shù)據(jù)正負關(guān)聯(lián)規(guī)則挖掘算法，該方法能夠有效、快速地對所有數(shù)據(jù)進行挖掘分析，對于不需要的數(shù)據(jù)也可進行精準篩選，并通過實驗結(jié)果表明了本文算法的有效性和適用性。在后續(xù)的研究中，將提升信息檢索查詢和跨語言信息檢索等能力，以期能夠更好地完善挖掘方法的性能。