經典關聯算法分析和Weka數據挖掘應用

中南林業科技大學計算機與信息工程學院 歐陽林 譚駿珊 唐 笑

1.關聯規則

關聯規則是數據中蘊含的一類重要規律，對關聯規則進行挖掘是數據挖掘中的一項根本任務，甚至可以說是數據庫和數據挖掘領域中所發明并被廣泛研究的最為重要的模型[1]。簡言之，關聯規則挖掘是發現大量數據中項集之間的關系或相關聯系[2]。這些關系往往是隱藏的，從大量商務數據中發些這些有趣的關系對交叉銷售、配送服務、賤賣分析等是有價值的，這樣也有利于商務決策的制定。

關聯規則挖掘的經典應用是購物籃數據分析，該過程通過發現顧客放入其購物籃中不同商品之間的聯系，分析顧客的購買習慣，得出哪些商品頻繁的被顧客同時購買，可以優化商品的分類陳列、改善商店的布局。以下是一個關聯規則的簡單例子：

計算機=＞財務管理軟件

[支持度=12%，置信度=60%]

這個規則表明12%的顧客同時購買電腦和財務管理軟件，而在所有購買了電腦的顧客中有60%顧客也購買了財務管理軟件。

2.關聯規則相關概念

項目集合：I={i1，i2，i3，…，im}。

k-項集：項集中項目個數為k的項集。

事務集合：T=(t1，t2，t3，...，tm)。

關聯規則表達模型：

XàY，其中X∈I，Y∈I，且X∩Y=?。

這是一個蘊涵關系表達式，X稱前件，Y稱后件。

X覆蓋ti：項集X是事務ti∈T的一個子集，則稱ti包含X，也稱X覆蓋ti。

支持計數：是T中包含X的事務的數目，記做X.count。

支持度：規則XàY的支持度是T中包含X∪Y的事務的百分比，也可以看做是概率P(XUY)。支持度表示規則在事務集合T中使用的頻繁程度。如果支持度的值太小，則表明這個規則可能是偶然發生的，研究它可能沒什么價值。

置信度：規則XàY的置信度是既包含了X又包含了Y的事務的數量占所有包含了X的事務的百分比，也可看做是條件概率P(Y|X)。置信度決定了規則的可預測度，如果一條規則的置信度太低，那么從X就很難可靠地推斷出Y。研究置信度太低的規則在實際應用中也不會有太大價值。

目標：關聯規則挖掘就是要找出一個給定的事務T中所有滿足用戶指定的最小支持度(minsup)和最小置信度(mincof)的關聯規則。如果一個關聯規則滿足最小支持度和最小置信度，那么就認為該關聯規則是有意義的。

頻繁項目集：一個支持度高于minsup的項集。

可信關聯規則：置信度大于minconf的規則。

3.Apriori算法思想

Apriori算法是基于關聯規則的經典挖掘算法，是一種最有影響的挖掘布爾關聯規則頻繁項集的算法。Apriori算法分兩步進行：

（1）生成所有頻繁項目集。

（2）從頻繁項目集中生成所有可信關聯規則。

3.1 頻繁項目集生成部分的算法

Apriori算法基于演繹原理（向下封閉屬性）來高校的產生所有頻繁項目集，其中向下封閉屬性是指如果一個項集滿足某個最小支持度要求，那么這個項集的任何非空子集必須都滿足這個最小支持度。

Apriori使用一種逐層搜索的思想來生成頻繁項目集。它采用多輪搜索的方法，每一輪搜索一遍整個數據集，并最終生成所有的頻繁項目集。在第一輪搜索中，算法計算出所有只包含一個項目集的項集在事務集合中的支持度，并據此得到初始的單項目集（即1-頻繁項目集）F1。隨后的每一輪所搜都分為三步：

(1)將算法第(k-1)輪搜索生成的頻繁項目集集合Fk-1作為種子集合產生候選的項集集合Ck，而Ck中的這些候選項集都是可能的頻繁項目集，這個過程由candidate-gen()函數完成。

(2)隨后算法對整個事務數據庫進行掃描，計算Ck中的每個候選項集c的支持度，注意，在整個計算過程中并不需要將整個數據集加載入內存，事實上，在任何時候我們都只要在內存中保留一條事務記錄，因此Apriori算法可以用于處理非常巨大的數據集。

(3)在本論搜索的最后，算法計算Ck中每個候選項集的支持度，并將符合最小支持度要求的候選項集加入Fk中。

算法最后輸出的是所有頻繁項目集的集合F。

3.2 候選項集集合Ck的生成函數

該函數分為兩部分：合并和剪枝。

合并：將兩個(k-1)-頻繁項目集合并來產生一個可能的k-候選項集c。兩個頻繁項目集f1和f2的前k-2個項目都是相同的，只有最一個項目是不同的，隨后，c被加入到候選項集集合Ck中。

剪枝：從合并步中得到的候選項集并不是最終的Ck。有一部分候選項集可以被剪枝。這一步判斷c的所有(k-1)-子集是否都在Fk-1中。如果其中任何一個子集不在Fk-1中，則根據向下封閉原理，c必然不可能是頻繁項目集，于是可將c從候選項集Ck中刪除。

3.3 關聯規則生成算法

給定一個頻繁項目集f，如果一條關聯規則的后件為a，那么所有以a的任意一個非空子集為后件的候選規則都是關聯規則。基于此，得出了一個類似于頻繁項目集生成的關聯規則生成算法。首先，從頻繁項目集f中生成只有一項的關聯規則，然后利用所得到的關聯規則和candidate-gen函數生成所有2-后件候選關聯規則，依此類推。

3.4 缺點

在實踐中，關聯規則可能不像人們期望的那么有用。一個主要缺點是支持度、置信度框架常常產生過多的規則。另一個缺點是其中大部分規則是顯而易見的。關聯分析需要技巧，用嚴格的統計學知識處理規則增值將是有益的[4]。

3.5 提高Apriori的有效性

為提高Apriori算法的有效性，我們可以從以下幾個方面考慮：

基于散列的方法：通過實驗可以發現尋找頻繁項集主要的計算是在生成頻繁2-項集上，一種基于散列的技術可以用于壓縮候選k-項集Ck(k＞1)。例如，當掃描數據庫中每個事務，由C1中的候選1-項集產生頻繁1-項集L1時，可以對每個事務產生所有的2-項集，將它們散列（即映射）到散列表結構的不同桶中，并增加對應的桶計數，在散列表中對應的桶計數低于支持度閾值的2-項集不可能是頻繁2-項集，因而應當由候選集中刪除。這種基于散列的技術可以大大壓縮要考察的k-項集，特別是利用這一技術來改進產生頻繁2-項集。

事務壓縮：減少用于未來掃描的事務集的大小。一個基本的原理就是不包含任何k-項集的事務不可能包含任何（k+1）-項集。從而就可以將這些事務在其后的考慮時加上標記或刪除，因為為產生j-項集（j＞k），掃描數據庫時不再需要它們，這樣在下一遍的掃描中就可以減少要進行掃描的事務集的個數。

基于劃分的方法：為了降低算法對內存的需求同時提高并行性，基于劃分的方法把數據庫從邏輯上分成幾個互不相交的塊，每次單獨考慮一個塊并對它生成所有的頻繁項集，然后把產生的頻繁項集合并，用來生成所有可能的頻繁項集，最后計算這些頻繁項集的支持度，這里每一個部分的大小和劃分的數目確定，使得每一部分能夠放入內存，這樣每個階段只需要被掃描一次，而算法的正確性是由每一個可能的頻繁項集至少在某一個分塊中是頻繁項集保證的。此算法可以使高度并行的，可以把每一部分分配給某一個處理器生成頻繁項集。

基于選樣的方法：在給定數據的一個子集挖掘。選樣的方法的基本思想是：選取給定數據庫D的隨機樣本S，然后，在S而不是在D中搜索頻繁項集，得到一些在整個數據庫中可能成立的規則，然后對數據庫剩余部分驗證這個結果。用這種方法，犧牲了一些精度換取了有效性。樣本S的大小這樣選取，使得可以在內存搜索S中頻繁項集；這樣，總共只需要掃描一次S中的事務。由于搜索S中而不是D中的頻繁項集，可能丟失一些全局頻繁項集。為減少這種可能性，使用比最小支持度低的支持度閾值來找出局部于S的頻繁項集（記作LS）。然后，數據庫的其余部分用于計算LS中每個項集的實際頻繁度。采用下列方法來確定是否所有的頻繁項集都包含在LS中：如果LS實際包含了D中的所有頻繁項集，只需要掃描一次D；否則，可以做第二次掃描，以找出在第一次掃描時遺漏的頻繁項集。當效率最為重要時，如計算密集的應用必須在頻繁度不同的數據上運行時，選擇方法特別合適。

動態項集計數：動態項集計數技術將數據庫劃分為標記開始點的塊在掃描的不同點添加候選項集，不像Apriori僅在每次完整的數據庫掃描之前確定新的候選，在這種方法中，可以在任何開始點添加新的候選項集。該技術動態地評估已被計數的所有項集的支持度，如果一個項集的所有子集已被確定為頻繁的，則添加它作為新的候選。結果算法需要的數據庫掃描比Apriori少。

4.weka實現數據挖掘

Weka是一個功能全面的機器學習和數據挖掘應用程序平臺[4]。Weka用Java編程，其中提供了優秀的學習算法，現在我們使用上面已經分析了的Apriori算法做一些機器學習工作。本文中，我們在windows xp下，使用的是weka3.6版以及Mysql5.0版本數據庫，對深海油氣田的數據庫中的oilField表中的FieldLife和Total用Apriori進行分析。

4.1 weka連接數據庫

在連接數據庫之前我們需要下載安裝了mysql-connector-java-3.1.14和Java的jdk，并將mysql-connectorjava-3.1.14-bin.jar的路徑配置到環境變量classpath中。接著打開weka的安裝路徑，例如：我的路徑為：G:Program FilesWeka-3-6，找到weka.jar文件，將其解壓到當前文件夾下。在解壓后的文件夾中找到wekaexperiment這個目錄下的DatabaseUtils.props與DatabaseUtils.props.mysql。然后使用UltraEdit打開這兩個文件。在DatabaseUtils.props.mysql文件中，我們能看到以下配置項：

（1）驅動加載項

將jdbcDriver=后的內容mysqlconnector-java-3.1.14-bin.jar里面的驅動，配置如下：

（2）類型轉換

找到# specific data types部分，在其下配置mysql中各種類型對應轉換成weka的數據類型，我們使用從DatabaseUtils.props中的#mysqlconversion下的配置項。其余部分的配置不需要更改，保存文件。此時我們再將DatabaseUtils.props重命名為任意名字，將DatabaseUtils.props.mysql改成DatabaseUtils.props。

（3）將weka重新打包

在命令提示符下我們進入到剛解壓的文件夾下，運行jar –cvf weka.jar *.*，此命令將當前目錄下的任意文件壓縮到weka.jar里，并且weka.jar文件就生成在當前目錄下。

（4）覆蓋原文件，運行weka

我們將重新打包的weka.jar拷貝到安裝目錄下（建議將原文件重命名），然后運行weka。

（5）點擊Explorer-Open DB

在url欄的最后面修改要連接的數據庫名，點擊user輸入用戶名與密碼，點擊connect連接數據庫。

4.2 weka進行關聯規則挖掘

（1）導入數據

在Query欄輸入sql語句，點execute執行，點ok將結果集導入weka。本文導入了深海油氣田數據庫中的oilField表中的FieldLife和Total：

FieldLife：油田壽命

Total：油田儲量

（2）數據離散化

在weka的preprocess的filter中選擇unsupervised/attribute/discretize。在choose右側點擊顯示輸入參數界面，將bin改成5。然后點擊apply，這樣就將fieldlife和total離散成了5類數據。

（3）度量標準

Weka中有幾個類似的度量代替置信度來衡量規則的關聯程度，它們分別是：

Lift：P(L，R)/(P(L)P(R))。Lift=1時表示L和R獨立。這個數越大，越表明L和R存在在一個購物籃中不是偶然現象。

Leverage：P(L,R)-P(L)P(R)。它和Lift的含義相近。Leverage=0時L和R獨立，Leverage越大L和R的關系越密切。

Conviction：P(L)P(!R)/P(L,!R)（!R表示R沒有發生）。Conviction也是用來衡量L和R的獨立性。從它和lift的關系（對R取反，代入Lift公式后求倒數）可以看出，我們也希望這個值越大越好。

值得注意的是，用Lift和Leverage作標準時，L和R是對稱的，Confidence和Conviction則不然。

（4）參數設置

現在計劃挖掘出支持度在10%到100%之間，并且lift值超過1.5且lift值排在前10位的那些關聯規則。我們把"lowerBoundMinSupport"和"upperBoundMinSupport"分別設為0.1和1，"metricType"設為lift，"minMetric"設為1.5，"numRules"設為10。其他選項保持默認即可。"OK"之后在"Explorer"中點擊"Start"開始運行算法，在右邊窗口顯示數據集摘要和挖掘結果。

（5）結果及分析

雖然設置的numRules為10，但是相關的關聯項只有四項。對于挖掘出的每條規則，WEKA列出了它們關聯程度的四項指標。第一條規則的意思是油田壽命在5.797968868E17-7.693786214E17范圍內的油田的儲量大于7.87367106E17的可信度為55%。第二條規則是說油田儲量大于7.87367106E17的油田的壽命在5.797968868E17-7.693786214E17范圍內的可信度為43%，依此類推。所以，總的來說油田壽命較長的油田，其儲量最高的可能性最大。

[1]Bing Lin.Web數據挖掘俞勇[M].薛貴榮,韓定一,譯.北京:清華大學出版社.

[2]韓家煒.數據挖掘:概念與技術[M].機械工業出版社.

[3]Data Minng:Concepts and Techniques J.Han and M.Kamber Morgan Kaufman 2006 China Machine Press.

[4][印]K.P. Soman Shyam Diwakar V.Ajay.數據挖掘基礎教程[M].范明,牛常勇,譯.機械工業出版社.