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

梁 偉

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

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

中圖分類號(hào):TP311.13 文獻(xiàn)標(biāo)識(shí)碼:A文章編號(hào):1006-8937(2009)20-0091-02

1發(fā)展歷史

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

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

2相關(guān)概念

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

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

對(duì)于一個(gè)事務(wù)集D,挖掘關(guān)聯(lián)規(guī)則的問題就是找出支持度和可信度分別大于用戶給定的最小支持度閥值(minsupp)和最小置信度(minconf)閥值的關(guān)聯(lián)規(guī)則,這種規(guī)則成為強(qiáng)關(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)生候選頻繁項(xiàng)集

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

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

①首先計(jì)算所有的C1;

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4.2算法描述

PS算法的主要步驟為:

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

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

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

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

5結(jié) 語

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

參考文獻(xiàn):

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

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

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

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

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