石正喜 葛科奇 曹財(cái)耀

（寧波城市職業(yè)技術(shù)學(xué)院信息學(xué)院浙江寧波315100）

1 引言

數(shù)據(jù)挖掘，又稱為數(shù)據(jù)庫中的知識(shí)發(fā)現(xiàn)(Know ledge Discovery in Database,KDD),是從大量的、不完全的、有噪聲的、模糊的、隨機(jī)的數(shù)據(jù)中，提取隱含在其中的、人們事先不知道的、但又是潛在有用的信息和知識(shí)的過程，它是知識(shí)發(fā)現(xiàn)的關(guān)鍵步驟。關(guān)聯(lián)規(guī)則挖掘是數(shù)據(jù)挖掘中應(yīng)用最廣的算法之一。關(guān)聯(lián)規(guī)則挖掘，是指從一個(gè)大型的數(shù)據(jù)集中發(fā)現(xiàn)有趣的關(guān)聯(lián)關(guān)系，即從數(shù)據(jù)集中識(shí)別出頻繁出現(xiàn)的屬性值集，也稱為頻繁項(xiàng)集，簡(jiǎn)稱頻繁集，然后利用所得的頻繁集創(chuàng)建描述關(guān)聯(lián)規(guī)則的過程。簡(jiǎn)言之，關(guān)聯(lián)規(guī)則挖掘就是通過給定的數(shù)據(jù)庫，根據(jù)最小支持度和最小置信度來尋找合適關(guān)聯(lián)規(guī)則的過程。

美國學(xué)者R.Agrawal等人從顧客交易數(shù)據(jù)庫中發(fā)現(xiàn)了用戶購買模式的相關(guān)性問題，于是提出Apriori關(guān)聯(lián)規(guī)則算法。目前，Apriori算法已廣泛應(yīng)用于數(shù)據(jù)分析、商業(yè)情報(bào)、高層決策等各個(gè)領(lǐng)域中。由于經(jīng)典的Apriori算法需要多次掃描原始數(shù)據(jù)庫，并生成大量的候選集，所以算法的挖掘性能一般，產(chǎn)生的冗余規(guī)則也較多。因此，在分析關(guān)聯(lián)規(guī)則挖掘算法的基礎(chǔ)上，提出一種改進(jìn)的Apriori關(guān)聯(lián)規(guī)則挖掘算法，并進(jìn)行了相關(guān)的檢驗(yàn)，結(jié)果表明該算法能較好地提取關(guān)聯(lián)規(guī)則[1]。

2 Apriori算法

Apriori算法的顯著特點(diǎn)是通過多次對(duì)數(shù)據(jù)庫D進(jìn)行掃描進(jìn)而發(fā)現(xiàn)所有的頻繁項(xiàng)目集[2]。設(shè)k為最長(zhǎng)頻繁項(xiàng)目集的長(zhǎng)度，則Apriori算法對(duì)數(shù)據(jù)庫D掃描次數(shù)為Sapriori=k。在第一趟掃描數(shù)據(jù)庫時(shí)，Apriori算法首先計(jì)算出數(shù)據(jù)庫D中所有的單個(gè)項(xiàng)目的支持度，并確定出滿足最小支持度的1-強(qiáng)項(xiàng)集的集合L1。然后利用L1來挖掘L2，也就是2-強(qiáng)項(xiàng)集；連續(xù)不斷的如此循環(huán)下去，在第n趟掃描中，首先以n-1趟掃描中所發(fā)現(xiàn)的含n-1個(gè)元素的強(qiáng)項(xiàng)集的集合Ln-1作為種子集，利用該種子集生成新的潛在的n-強(qiáng)項(xiàng)集的集合，即候選集Cn，計(jì)算這些候選集的支持度，最后從候選集Cn中確定出滿足最小支持度的n強(qiáng)項(xiàng)集的集合Ln。不斷重復(fù)以上過程，直至沒有新的強(qiáng)項(xiàng)集產(chǎn)生為止。

經(jīng)典的Apriori算法存在明顯的不足[3,4]：①需要多次掃描數(shù)據(jù)庫D，輸入/輸出系統(tǒng)消耗大量的計(jì)算機(jī)資源，如果最長(zhǎng)頻繁項(xiàng)目集的長(zhǎng)度為k，那么就需要掃描數(shù)據(jù)庫k遍；②產(chǎn)生的候選集是龐大的，由Lk-1產(chǎn)生k-候選集Ck是以指數(shù)增長(zhǎng)的?？傊?，Apriori算法比較適用于處理小數(shù)據(jù)量的數(shù)據(jù)庫，對(duì)于具有大量數(shù)據(jù)的數(shù)據(jù)庫或數(shù)據(jù)倉庫，執(zhí)行效率會(huì)很低。

3 改進(jìn)的Apriori算法

3.1 改進(jìn)Apriori算法的思路

改進(jìn)的Apriori算法為基于可拓理論的Apriori算法?？赏匦约词挛锿卣沟目赡苄?，事物的可拓性是事物本身固有的性質(zhì)，它包括發(fā)散性、相關(guān)性和蘊(yùn)含性，它從事物向外、平行、變通和組合分解的角度提供了多條變換的可能途徑。給定事物的名稱N,它關(guān)于特征c的量值v,以有序三元組R=(N,c,v)作為描述事物的基本元,簡(jiǎn)稱為物元。事物的名稱N、特征c和量值v稱為物元的三要素。如果物元三要素內(nèi)部結(jié)構(gòu)發(fā)生變化，那么物元也會(huì)產(chǎn)生變化。物元三要素是物元描述事物可變性的基本工具。物元把事物特征和量值放在一個(gè)統(tǒng)一體中考慮,使人們處理問題時(shí)，既要考慮事物的量,又要考慮事物的質(zhì)。

在基于可拓理論的數(shù)據(jù)挖掘中,關(guān)聯(lián)規(guī)則的定義為：對(duì)于一個(gè)征集X和一個(gè)概念描述Y,指定支持度閾值s0和置信度閾值c0,如果s(XyY)Es0并且c(XyY)Ec0,則規(guī)則XyY成立。其中,s(XyY)=card(XHY)/card(N),c(XyY)=card(XHY)/card(X)。運(yùn)算符card(#)是求數(shù)據(jù)記錄對(duì)象集中事物的個(gè)數(shù),即求事務(wù)集中的事務(wù)數(shù)的個(gè)數(shù)。card(XHY)表示的同時(shí)支持征集X與概念Y的事物的個(gè)數(shù),把它也稱為支持度計(jì)數(shù)[5]。

對(duì)于一個(gè)征集X,如果s(XyY)Es0,則征集X為大征集。一個(gè)大征集中的某一征集Xk,如果置信度大于置信度閾值,便可以挖掘出一個(gè)可拓關(guān)聯(lián)規(guī)則:XkyY,并將該征集Xk刪除,以避免冗余規(guī)則的產(chǎn)生。一個(gè)征集為大征集的必要條件是該征集所描述的所有子句確定的征集為大征集。由此,可以得到基于可拓理論的Apriori算法的2個(gè)關(guān)鍵步驟[6]：①大征集的交運(yùn)算：設(shè)X 1,X 2是2個(gè)大征集,進(jìn)行交運(yùn)算后生成征集的描述X是X 1,X 2中所有子句的合取范式；②征集的刪除運(yùn)算：對(duì)k元征集集合中的每一個(gè)征集Xk的所有k-1元子句進(jìn)行檢查,如果發(fā)現(xiàn)有某個(gè)k-1元子句所確定的征集Xk-1不是大征集,便將該征集從該k元集合中刪除。

3.2 改進(jìn)Apriori算法的描述

輸入:數(shù)據(jù)庫D，最小支持度閾值s0，最小置信度閾值c0輸出:關(guān)聯(lián)規(guī)則集R基于可拓理論的Apriori算法描述如下[7-9]:

①掃描整個(gè)數(shù)據(jù)庫D，統(tǒng)計(jì)每一條記錄的每一個(gè)元素，得到一個(gè)元素集合S；

②以S中每一個(gè)元素構(gòu)成一個(gè)集合，形成一元候選集H 1，設(shè)置一個(gè)元計(jì)數(shù)單位k，并令k=1；

③對(duì)于概念描述Y，依次計(jì)算Hk中每一個(gè)征集XkyY的支持度s和置信度c，如果Xk的支持度sE s0，則進(jìn)行如下判斷：

a對(duì)于給定的置信度閾值c0，如果Xk的置信度cEc0，則輸出一條規(guī)則XkyY；

b如果Xk的置信度cFc0，則將Xk存入大征集Lk中；

④若Lk中的元素的個(gè)數(shù)少于2個(gè)，則停止；否則，對(duì)于Lk中的每一個(gè)Xk，對(duì)Xk中的所有元素按字典順序排列；

⑤從Lk中取出2個(gè)不同的征集Xki，Xkj，對(duì)這2個(gè)征集的元素進(jìn)行逐一比較，如果滿足前k-1個(gè)元素相同，第k個(gè)元素不同，則以Xki所用元素和Xki的第k個(gè)元素構(gòu)成一個(gè)新的k+1元征集，并將其存入Hk+1。對(duì)Lk中的所有征集兩兩組合進(jìn)行此操作，生成k+1候選集；

⑥令k=k+1，返回到③。

4 改進(jìn)Apriori算法的性能驗(yàn)證

為進(jìn)一步驗(yàn)證改進(jìn)的Apriori算法性能，采用VC++實(shí)現(xiàn)上述算法，并利用SQLServer2005數(shù)據(jù)庫中的模擬實(shí)驗(yàn)數(shù)據(jù)對(duì)改進(jìn)的Apriori算法及經(jīng)典的Apriori算法進(jìn)行了驗(yàn)證。測(cè)試數(shù)據(jù)分別為600、900、1,200條記錄，最小支持度分別為0.05，0.07，0.09，0.11，0.13，0.15，0.17，0.19，0.21，實(shí)驗(yàn)結(jié)果表明，通過Apriori算法挖掘出的規(guī)則含有大量的冗余規(guī)則，采用改進(jìn)的Apriori算法得到的規(guī)則集既沒有冗余規(guī)則也沒有遺漏規(guī)則，但當(dāng)最小支持度增大或數(shù)據(jù)庫中的數(shù)據(jù)量增大時(shí)，改進(jìn)算法的運(yùn)行速度略低于Apriori算法。

5 結(jié)束語

分析了Apriori挖掘算法的特點(diǎn)及存在的問題，同時(shí)提出了Apriori挖掘算法的改進(jìn)方法，并對(duì)改進(jìn)前、后的算法進(jìn)行了實(shí)驗(yàn)數(shù)據(jù)的分析研究。分析結(jié)果表明，通過經(jīng)典的Apriori算法挖掘出的關(guān)聯(lián)規(guī)則包含大量的冗余規(guī)則，而改進(jìn)的Apriori算法沒有冗余規(guī)則的產(chǎn)生,并且產(chǎn)生的規(guī)則既沒有遺漏又簡(jiǎn)單明了，但改進(jìn)的Apriori算法的執(zhí)行效率略低于經(jīng)典的Apriori算法。

[1]毛國君,段立娟,王實(shí)等.數(shù)據(jù)挖掘原理與算法[M].清華大學(xué)出版社,2005.

[2]譚光明,馮圣中,孫凝暉.一種基于新型的數(shù)據(jù)挖掘算法研究[J].軟件學(xué)報(bào),2006,17(7)：1501- 1509.

[3]劉琦.基于關(guān)聯(lián)規(guī)則的數(shù)據(jù)挖掘算法研究[C].杭州:浙江大學(xué),2008.

[4]李新良,陳湘濤.數(shù)據(jù)挖掘中關(guān)聯(lián)規(guī)則算法的研究[J].計(jì)算機(jī)工程與應(yīng)用,2007,12(29):111.

[5]李立希,李鏵汶,楊春燕.可拓學(xué)在數(shù)據(jù)挖掘中的應(yīng)用初探[J].中國工程科學(xué),2004,6(7):53- 59.

[6]陳文偉,黃金才.可拓知識(shí)與可拓?cái)?shù)據(jù)挖掘[J].廣西師范大學(xué)學(xué)報(bào)(自然科學(xué)版),2006,24(4):159- 162.

[7]Jiawei Han,Hong Cheng,Dong Xin,Xifeng Yan.Frequent pattern mining:current status and future directions[J].Data M ining and Know ledge Discovery,2007(15):55- 86.

[8]Alain Deschenes,Kay C.W iese.Using different algorithms for improving the Accuracy of Data M ining Algorithm[J].Simon Fraser University,2004,598- 606.

[9]張玉林.一種無冗余的關(guān)聯(lián)規(guī)則算法.計(jì)算機(jī)工程與應(yīng)用,2007,43(3):26- 29.