經(jīng)典關(guān)聯(lián)算法分析和Weka數(shù)據(jù)挖掘應(yīng)用

中南林業(yè)科技大學(xué)計(jì)算機(jī)與信息工程學(xué)院 歐陽林 譚駿珊 唐 笑

1.關(guān)聯(lián)規(guī)則

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

關(guān)聯(lián)規(guī)則挖掘的經(jīng)典應(yīng)用是購物籃數(shù)據(jù)分析，該過程通過發(fā)現(xiàn)顧客放入其購物籃中不同商品之間的聯(lián)系，分析顧客的購買習(xí)慣，得出哪些商品頻繁的被顧客同時(shí)購買，可以優(yōu)化商品的分類陳列、改善商店的布局。以下是一個(gè)關(guān)聯(lián)規(guī)則的簡單例子：

計(jì)算機(jī)=＞財(cái)務(wù)管理軟件

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

這個(gè)規(guī)則表明12%的顧客同時(shí)購買電腦和財(cái)務(wù)管理軟件，而在所有購買了電腦的顧客中有60%顧客也購買了財(cái)務(wù)管理軟件。

2.關(guān)聯(lián)規(guī)則相關(guān)概念

項(xiàng)目集合：I={i1，i2，i3，…，im}。

k-項(xiàng)集：項(xiàng)集中項(xiàng)目個(gè)數(shù)為k的項(xiàng)集。

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

關(guān)聯(lián)規(guī)則表達(dá)模型：

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

這是一個(gè)蘊(yùn)涵關(guān)系表達(dá)式，X稱前件，Y稱后件。

X覆蓋ti：項(xiàng)集X是事務(wù)ti∈T的一個(gè)子集，則稱ti包含X，也稱X覆蓋ti。

支持計(jì)數(shù)：是T中包含X的事務(wù)的數(shù)目，記做X.count。

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

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

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

頻繁項(xiàng)目集：一個(gè)支持度高于minsup的項(xiàng)集。

可信關(guān)聯(lián)規(guī)則：置信度大于minconf的規(guī)則。

3.Apriori算法思想

Apriori算法是基于關(guān)聯(lián)規(guī)則的經(jīng)典挖掘算法，是一種最有影響的挖掘布爾關(guān)聯(lián)規(guī)則頻繁項(xiàng)集的算法。Apriori算法分兩步進(jìn)行：

（1）生成所有頻繁項(xiàng)目集。

（2）從頻繁項(xiàng)目集中生成所有可信關(guān)聯(lián)規(guī)則。

3.1 頻繁項(xiàng)目集生成部分的算法

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

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

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

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

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

算法最后輸出的是所有頻繁項(xiàng)目集的集合F。

3.2 候選項(xiàng)集集合Ck的生成函數(shù)

該函數(shù)分為兩部分：合并和剪枝。

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

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

3.3 關(guān)聯(lián)規(guī)則生成算法

給定一個(gè)頻繁項(xiàng)目集f，如果一條關(guān)聯(lián)規(guī)則的后件為a，那么所有以a的任意一個(gè)非空子集為后件的候選規(guī)則都是關(guān)聯(lián)規(guī)則?；诖耍贸隽艘粋€(gè)類似于頻繁項(xiàng)目集生成的關(guān)聯(lián)規(guī)則生成算法。首先，從頻繁項(xiàng)目集f中生成只有一項(xiàng)的關(guān)聯(lián)規(guī)則，然后利用所得到的關(guān)聯(lián)規(guī)則和candidate-gen函數(shù)生成所有2-后件候選關(guān)聯(lián)規(guī)則，依此類推。

3.4 缺點(diǎn)

在實(shí)踐中，關(guān)聯(lián)規(guī)則可能不像人們期望的那么有用。一個(gè)主要缺點(diǎn)是支持度、置信度框架常常產(chǎn)生過多的規(guī)則。另一個(gè)缺點(diǎn)是其中大部分規(guī)則是顯而易見的。關(guān)聯(lián)分析需要技巧，用嚴(yán)格的統(tǒng)計(jì)學(xué)知識(shí)處理規(guī)則增值將是有益的[4]。

3.5 提高Apriori的有效性

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

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

事務(wù)壓縮：減少用于未來掃描的事務(wù)集的大小。一個(gè)基本的原理就是不包含任何k-項(xiàng)集的事務(wù)不可能包含任何（k+1）-項(xiàng)集。從而就可以將這些事務(wù)在其后的考慮時(shí)加上標(biāo)記或刪除，因?yàn)闉楫a(chǎn)生j-項(xiàng)集（j＞k），掃描數(shù)據(jù)庫時(shí)不再需要它們，這樣在下一遍的掃描中就可以減少要進(jìn)行掃描的事務(wù)集的個(gè)數(shù)。

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

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

動(dòng)態(tài)項(xiàng)集計(jì)數(shù)：動(dòng)態(tài)項(xiàng)集計(jì)數(shù)技術(shù)將數(shù)據(jù)庫劃分為標(biāo)記開始點(diǎn)的塊在掃描的不同點(diǎn)添加候選項(xiàng)集，不像Apriori僅在每次完整的數(shù)據(jù)庫掃描之前確定新的候選，在這種方法中，可以在任何開始點(diǎn)添加新的候選項(xiàng)集。該技術(shù)動(dòng)態(tài)地評估已被計(jì)數(shù)的所有項(xiàng)集的支持度，如果一個(gè)項(xiàng)集的所有子集已被確定為頻繁的，則添加它作為新的候選。結(jié)果算法需要的數(shù)據(jù)庫掃描比Apriori少。

4.weka實(shí)現(xiàn)數(shù)據(jù)挖掘

Weka是一個(gè)功能全面的機(jī)器學(xué)習(xí)和數(shù)據(jù)挖掘應(yīng)用程序平臺(tái)[4]。Weka用Java編程，其中提供了優(yōu)秀的學(xué)習(xí)算法，現(xiàn)在我們使用上面已經(jīng)分析了的Apriori算法做一些機(jī)器學(xué)習(xí)工作。本文中，我們在windows xp下，使用的是weka3.6版以及Mysql5.0版本數(shù)據(jù)庫，對深海油氣田的數(shù)據(jù)庫中的oilField表中的FieldLife和Total用Apriori進(jìn)行分析。

4.1 weka連接數(shù)據(jù)庫

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

（1）驅(qū)動(dòng)加載項(xiàng)

將jdbcDriver=后的內(nèi)容mysqlconnector-java-3.1.14-bin.jar里面的驅(qū)動(dòng)，配置如下：

（2）類型轉(zhuǎn)換

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

（3）將weka重新打包

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

（4）覆蓋原文件，運(yùn)行weka

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

（5）點(diǎn)擊Explorer-Open DB

在url欄的最后面修改要連接的數(shù)據(jù)庫名，點(diǎn)擊user輸入用戶名與密碼，點(diǎn)擊connect連接數(shù)據(jù)庫。

4.2 weka進(jìn)行關(guān)聯(lián)規(guī)則挖掘

（1）導(dǎo)入數(shù)據(jù)

在Query欄輸入sql語句，點(diǎn)execute執(zhí)行，點(diǎn)ok將結(jié)果集導(dǎo)入weka。本文導(dǎo)入了深海油氣田數(shù)據(jù)庫中的oilField表中的FieldLife和Total：

FieldLife：油田壽命

Total：油田儲(chǔ)量

（2）數(shù)據(jù)離散化

在weka的preprocess的filter中選擇unsupervised/attribute/discretize。在choose右側(cè)點(diǎn)擊顯示輸入?yún)?shù)界面，將bin改成5。然后點(diǎn)擊apply，這樣就將fieldlife和total離散成了5類數(shù)據(jù)。

（3）度量標(biāo)準(zhǔn)

Weka中有幾個(gè)類似的度量代替置信度來衡量規(guī)則的關(guān)聯(lián)程度，它們分別是：

Lift：P(L，R)/(P(L)P(R))。Lift=1時(shí)表示L和R獨(dú)立。這個(gè)數(shù)越大，越表明L和R存在在一個(gè)購物籃中不是偶然現(xiàn)象。

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

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

值得注意的是，用Lift和Leverage作標(biāo)準(zhǔn)時(shí)，L和R是對稱的，Confidence和Conviction則不然。

（4）參數(shù)設(shè)置

現(xiàn)在計(jì)劃挖掘出支持度在10%到100%之間，并且lift值超過1.5且lift值排在前10位的那些關(guān)聯(lián)規(guī)則。我們把"lowerBoundMinSupport"和"upperBoundMinSupport"分別設(shè)為0.1和1，"metricType"設(shè)為lift，"minMetric"設(shè)為1.5，"numRules"設(shè)為10。其他選項(xiàng)保持默認(rèn)即可。"OK"之后在"Explorer"中點(diǎn)擊"Start"開始運(yùn)行算法，在右邊窗口顯示數(shù)據(jù)集摘要和挖掘結(jié)果。

（5）結(jié)果及分析

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

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

[2]韓家煒.數(shù)據(jù)挖掘:概念與技術(shù)[M].機(jī)械工業(yè)出版社.

[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.數(shù)據(jù)挖掘基礎(chǔ)教程[M].范明,牛常勇,譯.機(jī)械工業(yè)出版社.