關(guān)聯(lián)規(guī)則算法探討

梁 偉

摘要:文章對關(guān)聯(lián)規(guī)則的發(fā)展進行了簡單的介紹,分析了關(guān)聯(lián)規(guī)則的經(jīng)典算法,介紹進了一種新的關(guān)聯(lián)規(guī)則算法,并對這三種算法在挖掘關(guān)聯(lián)規(guī)則的特點進行了對比分析,最后對關(guān)聯(lián)規(guī)則以后的發(fā)展進行了總結(jié)。

關(guān)鍵詞:數(shù)據(jù)挖掘;關(guān)聯(lián)規(guī)則;算法;探討

中圖分類號:TP311.13 文獻標識碼:A文章編號:1006-8937(2009)20-0091-02

1發(fā)展歷史

隨著信息技術(shù)的迅猛發(fā)展,許多領(lǐng)域搜集、積累了大量的數(shù)據(jù),迫切需要一種新技術(shù)從海量的數(shù)據(jù)中自動、高效地提取所需的有用知識。對這些海量數(shù)據(jù)進行研究的過程中,數(shù)據(jù)挖掘技術(shù)受到越來越多的關(guān)注。我們可以使用數(shù)據(jù)挖掘技術(shù)從海量數(shù)據(jù)中發(fā)掘其中存在的潛在規(guī)律。并將這些規(guī)律進行總結(jié),用于今后的決策。采用關(guān)聯(lián)規(guī)則在大型事務(wù)數(shù)據(jù)庫中進行數(shù)據(jù)挖掘是數(shù)據(jù)挖掘領(lǐng)域的一個重要研究內(nèi)容。從大量數(shù)據(jù)中發(fā)現(xiàn)項之間有趣的、隱藏的關(guān)聯(lián)和相關(guān)聯(lián)系正是關(guān)聯(lián)規(guī)則目的。

關(guān)聯(lián)規(guī)則技術(shù)在不斷成熟和發(fā)展,應(yīng)用范圍不斷擴大,由最初的購物籃分析發(fā)展到計算機入侵檢測、搜索引擎、警務(wù)預(yù)警、交通事故、保險業(yè)、金融業(yè)、農(nóng)業(yè)專家系統(tǒng)、教學(xué)評估、股票分析等領(lǐng)域。在理論研究方面,由最簡單的單維、單層、布爾關(guān)聯(lián)規(guī)則逐漸向復(fù)雜形式擴展,由頻繁模式挖掘不斷擴展到閉合模式挖掘、擴展型關(guān)聯(lián)規(guī)則、最大模式挖掘、衍生型關(guān)聯(lián)規(guī)則、關(guān)聯(lián)規(guī)則隱私保護、挖掘后處理、增量挖掘、規(guī)則主觀興趣度度量、相關(guān)模式、數(shù)據(jù)流等多種類型數(shù)據(jù)上的關(guān)聯(lián)規(guī)則挖掘等。

2相關(guān)概念

設(shè)項的集合I = { i l ,i 2 ,…,i m },D為數(shù)據(jù)庫事務(wù)集合,每個事務(wù)T是一個項目子集,似的TI。每個事務(wù)由事務(wù)標識符TID標識。若有XI, XT,則稱T包含X;如果X有k個元素,稱X為k-項集。

關(guān)聯(lián)規(guī)則的邏輯蘊含式為:X Y[s,c] ,其中XI ,YI 且 XY=。規(guī)則XY在事務(wù)集D中成立,并且具有支s和置信度c。支持s是指事務(wù)集XY含的百分比:support(XY)=P(XY),置信度c是指D中包含X的事務(wù)同時也包含Y的百分比confidence(XY)=P(Y|X)。

對于一個事務(wù)集D,挖掘關(guān)聯(lián)規(guī)則的問題就是找出支持度和可信度分別大于用戶給定的最小支持度閥值(minsupp)和最小置信度(minconf)閥值的關(guān)聯(lián)規(guī)則,這種規(guī)則成為強關(guān)聯(lián)規(guī)則。

3經(jīng)典算法

基于頻繁集的方法是關(guān)聯(lián)規(guī)則挖掘的主要方法,Aproiri算法是基于頻繁集的算法最主要算法之一,在數(shù)據(jù)挖掘中具有里程碑的作用,但是Apriori算法本身存在著一些固有的無法克服的缺陷,而后出現(xiàn)的基于頻繁集的另外一種算法FP-gorwth算法能較好地解決APriori算法存在的一些問題。下面分別介紹兩種經(jīng)典的算法。

3.1產(chǎn)生候選頻繁項集

Apriori算法是Rabesh Agrawal等人在1994年提出的,該算法采用了一種寬度優(yōu)先、逐層搜索的迭代方法:首先產(chǎn)生所有的頻繁1-項集,然后在此基礎(chǔ)上依次產(chǎn)生頻繁2-項集、頻繁3-項集……,直到頻繁k-項集為空集。在此過程中,產(chǎn)生每個頻繁項集都需要掃描一次數(shù)據(jù)庫,通過對數(shù)據(jù)庫D的多趟掃描來發(fā)現(xiàn)所有的頻繁項目集。

設(shè)Ck表示候選k-項集,Lk表示Ck中出現(xiàn)頻率大于或等于最小支持數(shù)的k-項集,即k-頻繁集或者是k-大項集。該算法的基本過程如下。

①首先計算所有的C1;

②掃描數(shù)據(jù)庫,刪除其中的非頻繁子集,生成L1(1-頻繁項集);

③將L1與自己連接生成C2(候選2-項集);

④掃描數(shù)據(jù)庫,刪除C2中的非頻繁子集,生成L2(2-頻繁項集);

⑤依此類推,通過Lk-1((k-1)-頻繁項集)與自己連接生成Ck(候選k-項集),然后掃描數(shù)據(jù)庫,生成Lk(頻繁k-項集),直到不再有產(chǎn)生頻繁項集為止。

Apriori算法雖然能較有效地產(chǎn)生關(guān)聯(lián)規(guī)則,同時也存在著不少缺點:

①數(shù)據(jù)庫太大時對候選項集的支持度計算非常繁瑣,當支持度、置信度閥值設(shè)置太低會產(chǎn)生過多的規(guī)則,致使用戶難易人為地對這些規(guī)則進行出區(qū)分和判斷。

②要對數(shù)據(jù)進行多次掃描,需要很大的I/O負載,算法的效率不高。

③當數(shù)據(jù)庫D很大時,會產(chǎn)生龐大的候選集,導(dǎo)致算法的耗時太大。

3.2不產(chǎn)生候選頻繁項集

FP-Tree算法由 Jiawei Han提出。它的基本思路是將數(shù)據(jù)集中的重要信息壓縮在一個稱為頻繁模式樹(FP-Tree)的數(shù)據(jù)結(jié)構(gòu)中, 然后基于FP-Tree生成數(shù)據(jù)集中所有的頻繁項集。該算法對所有頻繁項集的挖掘分為以下兩步:構(gòu)造頻繁模式樹FP-Tree。在 FP-Tree中,每個結(jié)點有4個域組成結(jié)點名稱、結(jié)點計數(shù)、結(jié)點鏈及父結(jié)點指針。另外,為方便樹遍歷,創(chuàng)建一個頻繁項頭表,它由兩個域組成:項目名稱及結(jié)點鏈頭,其中結(jié)點鏈頭指向 FP-Tree中與之名稱相同的第一個結(jié)點;調(diào)用FP-Growth挖掘出所有頻繁項集,具體算法描述如下。

①生成頻繁模式樹,首先,掃描事務(wù)數(shù)據(jù)庫 D一次,產(chǎn)生頻繁1-項集,并把它們按降序排列,放入L表中。其次,創(chuàng)建 FP-Tree的根結(jié)點,以“null”標記。再一次掃描D,對于D中的每個事務(wù)按 L中的次序排序,并對每個事務(wù)創(chuàng)建一個分枝。

②挖掘頻繁項集,首先,從FP-tree的頭表開始, 按照每個頻繁項集的鏈接遍歷,列出能夠到達此項的所有前綴路徑,得到條件模式基。其次,用條件模式基構(gòu)造對應(yīng)的條件FP-tree。第三,遞歸挖掘條件FP-tree,直到結(jié)果FP-tree為空,或者只含有唯一的一個路徑(此路徑上的每個子路徑對應(yīng)的項集都是頻繁項集)。

FP-Growth算法是一種基于模式增長的頻繁模式挖掘算法,采用了“分而治之”策略,它能夠在不產(chǎn)生候選頻繁項集的情況下挖掘全部頻繁項集,直接將數(shù)據(jù)庫壓縮成一個頻繁模式樹FP-tree,只需要兩次掃描數(shù)據(jù)庫,相對于Apriori算法效率快一個數(shù)量級。該算法雖然可以避免產(chǎn)生候選項目集,但在挖掘過程,當存在大量大項集,并且如果得到的頻繁模式樹FP-tree分支很多、分支長度很長時,該算法將需要構(gòu)造出太多的條件FP-tree,這不僅費時且要占用大量存儲空間,導(dǎo)致挖掘效率不高。另外構(gòu)造FP-tree是自頂而下構(gòu)造的,而生成條件模式基是自底而上生成的,在挖掘時需要反復(fù)地進行搜索FP-tree,存儲結(jié)構(gòu)采用雙向鏈表,則會進一步增加內(nèi)存的開銷。

4一種新的關(guān)聯(lián)規(guī)則算法

目前有許多新的關(guān)聯(lián)規(guī)則算法出現(xiàn),但大都是根據(jù)Apriori算法的框架結(jié)構(gòu)來改進的。文章將介紹一種新的基于冪集的挖掘算法PS (Power Set),該算法將完全脫離Apriori算法的框架結(jié)構(gòu)。

4.1算法的相關(guān)概念

①冪集合PS(A)定義:對于任意一個非空集合A,它的冪集合PS( A) 就是由A的全部子集組成的集合。例如非空集合A:{a,b,c},則它的冪集合PS(A)={{},{a},,{c},{a,b},{a,c},{b,c},{a,b,c}}。

②對事務(wù)數(shù)據(jù)庫D,I={il,i2……im},XI,在D中包含X的事務(wù)數(shù)就稱為D中的頻度,也可簡稱為X的頻度。

③集合A={a1,a2,a3,……,ai}中元素的個數(shù)稱為該集合A的長度Length(A)。

4.2算法描述

PS算法的主要步驟為:

①首先掃描事務(wù)數(shù)據(jù)庫D,并對每一條事務(wù)記錄本身進行拆解,例如,XYZ為一事務(wù)記錄,可以拆分為XY、XZ、YZ、X、Y、Z、XYZ七個子集。

②接著得到子集依據(jù)集合長度Length(A)存放在不同的結(jié)果表中,并做頻度計數(shù),如果結(jié)果表已存在對應(yīng)的子集,則將該集合的計數(shù)值加1,如果不存在,則將該集合加入其中,并設(shè)置初始值為1。這樣此事務(wù)記錄的拆解才算結(jié)束。當事務(wù)數(shù)據(jù)庫被掃描一次以后,所有的事務(wù)記錄都拆解完畢。

③最后根據(jù)用戶輸入的最小支持度和最小置信度閥值來產(chǎn)生頻繁項目集和關(guān)聯(lián)規(guī)則。

該算法通過對數(shù)據(jù)庫的一次掃描就能挖掘所有的頻繁集,大大降低了I/O存取的時間;而且算法運算簡單且速度較快,用戶可以任意改變最小支持度閥值使算法彈性增大,執(zhí)行的效率穩(wěn)定,不受支持度的變動的影響,在增量式挖掘中可以運用該算法而不需要對數(shù)據(jù)庫進行前期的處理。算法在新增記錄時比Apriori算法節(jié)省許多重復(fù)搜索記錄的時間,但是該算法在存儲的空間上會花費比Apriori算法大上數(shù)倍的存儲空間,所以PS算法是一種以存儲空間換取挖掘時間的方式。

5結(jié) 語

文章對關(guān)聯(lián)規(guī)則的發(fā)展做了簡單的介紹,對關(guān)聯(lián)規(guī)則的兩個經(jīng)典算法進行了分析并介紹了一種完全脫離Apriori算法的框架結(jié)構(gòu)的新算法。重點分析了三種算法的特點,得出對于將來的挖掘關(guān)聯(lián)規(guī)則的改進和研究重點仍會在減少I/O操作、減少存儲空間、產(chǎn)生更少的候選項集和如何更有效地挖掘數(shù)據(jù)中更實用的關(guān)聯(lián)規(guī)則上。

參考文獻:

[1] 王琳莎,林國龍,楊斌.新的關(guān)聯(lián)規(guī)則算法在物流行業(yè)中的應(yīng)用[J].物流工程與管理,2009,(3):41-43.

[2] 方風波.關(guān)聯(lián)規(guī)則挖掘技術(shù)發(fā)展及應(yīng)用[J].中小企業(yè)科技,2007,(6):108-109.

[3] 朱紹文,王泉德等.關(guān)聯(lián)規(guī)則挖掘技術(shù)及發(fā)展動向[J].計算機工程,2000,(9):4-6.

[4] 白利果,喬鋼柱,曾建潮.關(guān)聯(lián)規(guī)則挖掘在農(nóng)業(yè)產(chǎn)值分析中的應(yīng)用[J].太原科技大學(xué)學(xué)報,2008,(10):335-338.

[5] 李新仕.基于FP-tree的關(guān)聯(lián)規(guī)則挖掘算法的研究[D].南寧:廣西大學(xué)碩士學(xué)位論文.2006.