基于多數據庫的模糊元關聯規則挖掘方法

劉小燕 王 健

1(河南理工大學計算機科學與技術學院 河南 焦作 454000)2(河南理工大學安全科學與工程學院 河南 焦作 454000)

0 引 言

關聯規則挖掘算法是數據挖掘算法的一種，對于分布式數據，主要考慮算法的效率。不同站點的數據，事務分布在不同的站點，而垂直分布中，項集在站點之間被分割。基于Apriori的FDM算法(快速分布式挖掘)，主要致力于減少計算項目支持度時的通信交換[1]。CDA(計數分布算法)提出，對于每個可用的處理器，將分區挖掘過程并行化，從分布式數據中提取規則[3]。ODAM算法主要針對地理上分布的數據集，盡量減少交換信息的數量[4]。并行關聯規則挖掘算法在不同的站點之間劃分數據，而分布式關聯規則挖掘算法每個站點單獨執行任務但需要訪問整個數據集。分布式關聯規則挖掘主要目的是減少通信成本。

元規則是一個模板，用于指導關聯規則提取過程[5]。臨時元規則指的是第2次推理過程中發現的臨時規則(一階規則)[2]，表示形式為(A→B)。有些工作是從關聯規則中挖掘模糊規則，在不同的時間段為每個關聯規則賦一系列支持度和置信度值[6]。模糊元規則用于捕獲隨著時間的推移關聯規則的變化，從而得到模糊元規則的類型：t1時段支持度變化=相對降低→下一時段支持度變化=高度降低，使用模糊集手工定義適當的語言標簽。

傳統的挖掘算法，對規模較大的數據進行整體決策時較困難，因此，本文提出了一種二階挖掘方法，兩步使用關聯規則來獲取元關聯規則。元規則的前件或后件是關聯規則，不考慮支持度/置信度值序列。和先前工作相比，本文提出的方法有如下好處：由于能從多個數據集中提取規則，并進行二次挖掘，使元規則能表達新的普通規則不能表達的相關信息；該算法產生一組更易于人工檢查管理的規則集；允許將上下文信息以更人性化的方式合并到挖掘過程。

1 基于層次理論的模糊關聯規則

模糊集應用于關聯分析有兩種方法：(1) 從清晰關系數據庫或量化數據集提取模糊關聯；(2) 分析模糊事務。一般來說，方法1中模糊集允許通過語言標簽定義屬性值的軟區間邊界，這種方法可用不同的粒度級別表示規則。方法2中，數據以模糊事務數據庫的形式提供，即事務項目在一定程度上滿足。本文主要考慮方法2，數據以模糊事務數據庫的形式表示，即事務中的項目在一定程度上滿足。

層次理論模型[6]認為，項i∈I，項目集A?I，基于模糊數據庫的層次理論表示(∧A,ρA)。其中，∧A={α1,α2,…,αm},1=α1>α2>…>αm>0，是預先定義的層次集，ρA(α)={τ∈：τ(A)≥α}是一個將每個層次應用于清晰的實現中的函數。

MαiB┐BAaibi┐Acidi

其中，ai,bi,ci和di為非負整數，ai=|ρA∧B(αi)|，bi=|ρA∧┐B(αi)|，ci和di類似。為了評價模糊關聯規則的有效性，可以使用基本的概率分布概括每一個興趣度度量，基本的概率分布定義如下：

Y必須是至少一個a∈∧的原象。支持度、置信度和確定性因素分別都是方程。∧等于1可以得到清晰方法的值。

FCF(A→B)=

當|ρA(αi)|=0時，置信度的計算可能有不確定的形式“0/0”，若不存在滿足前件的事務時這種情況便會發生。為保持模糊規則的定義，給不確定性賦值。對于確定性因素FCF，層次理論的項目集都需要標準化，即A或B必須滿足在層次a=1至少有一個事務，如果不，它們的滿足程度應當用A或B達到的最大值來標準化。

2 基于元關聯規則挖掘信息

使用元關聯規則的目的是將地理上分布或者因為存儲、安全或其他原因而水平分區的數據庫中的信息進行融合。在這兩種情況下，我們想要發現從單個主要的數據集中提取的關聯規則之間的關聯。當數據集非常大、復雜且異質的情況下這非常有用。比如，數據集類型，數據庫收集不同來源的傳感器數據(如燈光、移動傳感器、視頻)，數據被劃分在不同的采集或存儲區。為了得到有意義的相同類型項目的元規則，主要的數據集必須有相似的結構和語義，但它們的結構不需要完全相同。

下面舉例說明這個問題。假設有一個多分支組織，如銀行，全國有幾個分行。數據存儲在各自的分行，這些分行有相似的結構。組織感興趣的是根據客戶的數據分析其利潤。有兩種選擇：(1) 對數據進行全局分析，即合并所有的局部數據，編譯成一個大的數據集，分析整個數據；(2) 對從各個分部的數據獲取的局部模式進行分析獲取相關信息。若用第2種方法，檢查的規則數量將會非常多。為此，本文提出了元規則以便于第2種情況下進行分析。通過元規則進行挖掘有以下優點：不需要處理整個數據集，可以提高效率；可以使用從單個數據庫獲取的模式，減少規則挖掘過程的時間，在多數情況下，可以獲取一個較小的、便于檢查的規則集；所有數據源不需要有完全一致的結構；元規則便于在更加抽象的層次上分析，因為我們研究的是規則之間的不同而不是數據之間的不同；元規則便于將上下文知識合并到挖掘過程，例如部門選址時關于地方的人口結構或經濟數據。但是，因為元規則分析是基于已有的摘要數據(關聯規則形式)進行的，所以難免會丟失一些信息。

2.1 元關聯規則挖掘過程

圖1 原始數據集到最終的元關聯規則挖掘過程

Step1{D1,D2,…,Dk}是數據庫集，共享部分屬性。將規則提取過程應用到每個數據庫后，可以獲取每個數據庫Di的關聯規則Ri。然后，在關聯規則R1,R2,…,Rk中就可以得到信息和它們的評價值。R1,R2,…,Rk規則的數量可以不同，每個規則的前件或后件中的項目數也可以不同。值得注意的是，Ri可能會有共同的規則。不失一般性，假定處理每個數據集時，使用相同的最小支持度和確定性因素值。

2.2 清晰元關聯規則

表1 布爾數據庫的例子

得到3種類型的元關聯規則：(1)ari=>arj,ari和arj是規則的合取(或一個規則，當ar只涉及一個規則時)。例如，若ari=r1∧r3，arj=r2，則r1∧r3=>r2是個元關聯規則。(2)atsi=>atsj,atsi和atsj是屬性的合取(或一個屬性，當ats只包含一個屬性時)。(3)ari=>atsj∧ark或者atsj∧ark=>ari，ari和ark是規則的合取，atsj是屬性的合取，它們可以混合。例如，我們可以發現一個形式為r1∧at2=>r3∧at4的元關聯規則。

此過程有一定的局限性，因為不收集所有可用信息(即規則的支持度和有效性)，只考慮規則先前是否從數據庫中挖掘，這意味著不同強度的普通規則(CF(ri)>>CF(rj))在布爾元數據庫中重要性相同。為了解決這個問題，可使用區間將評估測試合并到元數據庫，得到的項目形式為。例如，若使用CF，區間為[minCF,1]的子集，項目形式為，其中CFj∈[minCF, 1]，j=1，2。然而，由于清晰的區間邊界，這種方法是有問題的。例如，若CF(ri)=0.75，CF(rj)=0.76，區間為(0.5,0.75]和(0.75,1]，則CF值將落在不同的區間盡管它們非常接近。為此，我們考慮將模糊事務作為元規則提取過程的輸入，使用層次理論框架管理。

2.3 使用層次理論的模糊元關聯規則

模糊事務包括項目的模糊子集，每個項目的度被解釋為其對事務的隸屬度[8]。在模糊元數據庫中，事務是初始數據庫Di，項目是發現的規則rj∈Ri。這樣，一致使用評價值，確定性因素作為數據集中規則的可滿足度。表2描述了模糊元數據庫的一般形式。(i,j)處的值，即第Di行第rj列為數據庫Di中規則rj的確定性因素。與清晰情況相比，模糊元數據庫的取值在單位區間，更具體地說，在區間[minCF, 1]。清晰和模糊屬性可提供額外的信息，描述原始數據庫的一些特征信息。模糊集適合表示不精確的性質。

表2 模糊數據庫的例子

模糊元數據庫一旦建立，就可以使用模糊關聯規則挖掘算法獲取模糊元規則。本文使用層次理論框架，考慮支持度(FSupp)和確定性因素(FCF)措施。與清晰情況相似，模糊元規則也分為3種不同的類型：只與規則或規則的合取相關的模糊元規則；只與屬性或屬性的合取相關的模糊元規則；與規則和屬性的合取相關的模糊元規則。

模糊元規則和清晰元規則相比，它們的發現方式不同，采用了不同的信息(數據庫的規則評價度)和合適的評價措施(FSupp、FCF)。需要注意的是，提取的模糊元規則表示的關聯在原始數據庫中具有很高的可信度，而使用清晰方法只表示該規則存在[9]。

3 算 法

文獻[10]中可以找到一些方法發現清晰或模糊關聯規則。大多數算法分為兩步：第1步，計算頻繁項集或候選項集。第2步，提取超過用戶定義的精度閾值的規則。第1步計算代價太高，已經提出了很多不同的策略和啟發法來減少挖掘過程中的時間消耗。有些文獻使用二進制形式表示項目來加速合取的計算。使用二進制表示，內存占用不高，減少了系統的內存需求。

圖2 元關聯規則挖掘算法的盒圖表示

圖3 基于層次理論的模糊關聯規則挖掘算法

4 實 驗

實驗環境為：奔騰雙核處理器2.5 GHz，3 GB內存，Windows 7，Java 8。為了獲得可讀的規則，在第1步中限制前件有一個項，后件有一個項。對于元關聯規則，允許前件和后件最多有兩個項。本文所用實驗數據為：(1) 合成數據集：規模小，包含人工數據，劃分為8個數據庫，每個數據庫包含15個事務和6個屬性，每個屬性有6個不同的可能取值，從而可以得到36個形式為<屬性，值>的項。這主要用來區分傳統關聯規則挖掘算法和本文提出的元關聯規則挖掘算法的不同。(2) 真實數據集：包含南京市警區2010年的犯罪記錄以及犯罪事件發生時附近街坊的社交經濟數據。選擇了6個屬性：季度、日期、犯罪描述、位置、逮捕、家庭犯罪。數據集由23個數據庫組成，每個數據庫包含一個警區的事務。元數據庫增加了警區范圍內學校的一些屬性，如學生數、違紀數、安全系數(見表3)。(3)合成數據集用于可擴展：從南京市數據集(見表4)隨機生成10個合成數據庫，命名為1X-合成、2X-合成、3X-合成、4X-合成、5X-合成、6X-合成、7X-合成、8X-合成、9X-合成、10X-合成。2X-合成數據庫包含的事務數是1X-合成數據庫的兩倍，3X-合成數據庫包含的事務數是1X-合成數據庫的3倍，其他合成數據庫包含的事務數以此遞推。

表3 增加的額外屬性描述

表4 南京市數據集

通過實驗發現，實驗1發現的某些規則和單獨從8個數據集中的每2個數據集發現的規則相同，它們也在實驗2發現的某些元關聯規則中出現。如，規則r1(i1->i2)為實驗1發現的規則，r1有可能出現在實驗2發現的元關聯規則的前件或后件中，如r1∧at1=>r2。這種現象很容易理解，因為一個規則若在大多數數據庫中被發現，那么在合成數據庫中也很容易被發現。

然而，從實驗1中獲取的許多規則沒有出現在實驗2的任何元規則中。原因是在合成數據庫中，總的支持度和確定值較高超過了閾值，而在分離的數據集中，事務只在某些分離的數據集中滿足規則，所以它們沒有出現在實驗2的任何元規則中。此外，有許多規則出現在實驗2的元規則中但是并未出現在實驗1中，這也是合理的，因為不同的數據集中獲取的規則其支持度和確定值可能低于合成數據庫規定的閾值。

2) 真實數據結果 通過合并所有分區數據，構建了幾個實驗。問題是如何合并表3中的額外屬性信息，這些信息已經被分區數據合并，若把它們作為新事務添加到合成數據庫中沒有多大意義，因此可以作為新項目添加。由于每個區只有一個值，所以相同分區的所有事務重復相同值。比較了合并額外屬性和不合并額外屬性兩種情形下合成數據庫中獲取的規則。圖4顯示了支持度和確定值取不同閾值時的結果，從圖中可以發現，添加額外屬性可以發現更多的關聯規則。

圖4 minCF不同時合成數據庫獲取的規則數

第二組實驗主要分析清晰和模糊元規則挖掘方法的性能。將支持度閾值分別設為0.1和0.05，圖5和圖6顯示了當確定性因素的閾值取為{0.2,0.3，…，0.9}時發現的元規則數。圖5中，清晰方法獲取的元規則數大于模糊方法獲取的元規則數，尤其是當確定性因素閾值較小時區別非常明顯。此外，清晰方法和模糊方法兩者最大的不同是，當確定性因素閾值緩慢變大時，清晰元規則數急速下降，而模糊元規則數緩慢下降。由此可見，模糊元規則比清晰元規則更加合適，因為規則數量變化小而且便于觀察。圖6顯示了執行時間和支持度閾值有很大關系，支持度閾值決定了獲取的普通關聯規則的數量。從圖中可以發現，清晰方法受元規則數的影響，而模糊方法有相同的曲線不受元規則數的影響。

圖5 支持度閾值取不同值時發現的 清晰和模糊元關聯規則

圖6 支持度閾值取不同值時挖掘清晰和 模糊元關聯規則所耗時間

5 結 語

本文闡述了元關聯規則的概念，將從不同的數據集中挖掘的關聯規則進行融合。分別基于生成的清晰和模糊元數據庫，提出了兩個不同的過程以挖掘元關聯規則。模糊方法對第一階段獲取的精度措施適當地處理，可以更友好地表示額外的模糊屬性；獲得了一套簡化的元規則，可以方便用戶更快的檢索。

未來工作需要解決的問題有：很多情況下，屬性描述不完全適合于所有數據集，盡管它們含義相似。研究如何在元關聯規則挖掘過程中融合信息，一個可能的解決方案是利用知識庫，通過匹配類似項目協助挖掘元規則。此外，對于使用大數據集的大數據庫，需要進一步驗證本文算法的適用性。

參 考 文 獻

[1] Cheung D W,Ng V T,Fu A W,et al.Efficient Mining of Association Rules in Distributed Databases[J].Knowledge & Data Engineering IEEE Transactions on,1996,8(6):911-922.

[2] Delado M,Ruiz M D,Sánchez D.New Approaches for Discovering Exception and Anomalous Rules[J].International Journal of Uncertainty,Fuzziness and Knowledge-Based Systems,2011,19(2):361-399.

[3] 李其軒,路艷麗.直覺模糊信息系統的規則提取方法[J].計算機應用與軟件,2015,32(1):251-254.

[4] Saxena N,Arora R,Sikarwar R,et al.An Efficient Approach of Association Rule Mining on Distributed Database Algorithm[J].International Journal of Computer Applications,2014,81(3):12-16.

[5] 翟悅,秦放.基于概念格的無冗余關聯規則提取算法[J].計算機應用與軟件,2015,32(4):46-49,66.[6]劉玉龍,吳衛榮,王燕.多維信息融合方法及技術研究[J].計算機應用與軟件,2017,34(6):101-105.

[7] 周越.多域分布式網絡中告警模糊關聯規則挖掘的研究[D].成都:電子科技大學,2016.

[8] 丁三軍,薛宇,王朝霞,等.基于模糊數據挖掘的虛擬環境主機故障預測[J].計算機工程,2015,41(11):202-206.

[9] 丁建立,王曼.基于關聯規則挖掘的航班協同保障數據知識發現研究[J].計算機應用與軟件,2016,33(11):21-23,61.

[10] 段功豪.基于多結構數據挖掘的滑坡災害預測模型研究[D].武漢:中國地質大學,2016.