分布式數據庫中關系數據正負關聯規則挖掘

吳愛華，陳出新

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

1 引言

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

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

基于上述方法中存在的問題，提出了一種新的分布式數據庫中關系數據正負關聯規則挖掘方法。通過對生成的正關聯規則和負關聯規則，實現分布式數據庫中關系數據正負關聯規則挖掘。與傳統挖掘方法具有一定優勢。

2 關聯規則的基本概念和性質

2.1 關聯規則的定義

為了實現分布式數據庫中關系數據正負關聯規則挖掘，首先分析關聯規則的定義。

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

定義1：關聯規則是形如K→H的蘊涵式，則K?I，H?I，且K∩H=Φ。

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

(1)

其中，|D|用以描述事務數據庫的個數。

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

(2)

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

2.2 關聯規則的性質

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

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

3 關系數據正負關聯規則挖掘實現

3.1 挖掘過程分析

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

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

步驟2：生成可信關聯規則。通過對比置信度，將高于最小置信度規則定位可信關聯規則。

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

表1 關聯規則數據庫信息

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

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

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

置信度為：

根據設定的最小支持度為0.5，酸奶?芒果的關聯規則認定為興趣項，表示購買酸奶和芒果之間存在關聯關系。

3.2 負關聯規則分析

假設任務相關數據D為項集K和Y，關聯規則K?Y，K?Y，K?Y表示負關聯規則。

負關聯規則與正關聯規則的支持度和置信度定義接近，區別在于正關聯規則中的K和Y在負關聯規則中表示為K和Y。支持度的計算方法為

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

(3)

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

(4)

置信度計算方法為

(5)

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

(6)

(7)

尋找支持度和置信度大于指定的最小支持度和最小置信度的三種形式規則為負關聯規則[11]。

3.3 相關系數分析

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

(8)

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

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

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

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

通過對相關系數的確定，以及分析三種具有影響程度的相關系數情形，實現關聯規則相關系數的確定。

3.4 權重相關系數確定

1)關聯規則的權重確定

假設關聯規則{k1，k2，…kn}表示總規則集中的具體關聯規則，子數據庫的關聯規則為{G1，G2，…Gn}，Gi的權重為：

(9)

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

2)數據庫權重確定

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

(10)

3)權重合成

若數據庫中有規則K?Y存在，則支持度為

(11)

此時獲取的數據關聯規則的置信度為

(12)

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

(13)

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

將corrKY與最小相關系數進行比較，若corrKY大于最小相關系數使K?Y或則Y?K為強關聯規則，反之則為負關聯規則或弱關聯規則。

在上述分析中，通過對權重相關系數的獲取，完成置信度和支持度的確定，實現關系數據正負關聯規則挖掘。

4 實驗分析

4.1 實驗環境

實驗對某電信事務分布式數據庫中關系數據進行測試挖掘，該數據庫中共包含Q1、Q2、Q3三個數據庫，分別為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);(S，H)}。實驗操作系統為Windows2000，CPU為Pentium Ⅲ—733MHz。

4.2 實驗參數

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

(14)

4.3 結果分析

為了驗證所提方法的有效性，實驗采用本文方法對樣本數據進行相關系數和權重系數的確定，實驗結果如表2、3和表4 所示。

表2 相關系數確定分析

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

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

表3 A、S和D的支持度和權重系數統計表

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

表4 A、S和D的支持度和置信度統計

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

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

圖1 三種算法的挖掘執行時間對比結果

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

5 結論

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