基于關聯規則的數據挖掘算法研究

石正喜 葛科奇 曹財耀

（寧波城市職業技術學院信息學院浙江寧波315100）

1 引言

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

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

2 Apriori算法

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

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

3 改進的Apriori算法

3.1 改進Apriori算法的思路

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

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

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

3.2 改進Apriori算法的描述

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

①掃描整個數據庫D，統計每一條記錄的每一個元素，得到一個元素集合S；

②以S中每一個元素構成一個集合，形成一元候選集H 1，設置一個元計數單位k，并令k=1；

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

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

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

④若Lk中的元素的個數少于2個，則停止；否則，對于Lk中的每一個Xk，對Xk中的所有元素按字典順序排列；

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

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

4 改進Apriori算法的性能驗證

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

5 結束語

分析了Apriori挖掘算法的特點及存在的問題，同時提出了Apriori挖掘算法的改進方法，并對改進前、后的算法進行了實驗數據的分析研究。分析結果表明，通過經典的Apriori算法挖掘出的關聯規則包含大量的冗余規則，而改進的Apriori算法沒有冗余規則的產生,并且產生的規則既沒有遺漏又簡單明了，但改進的Apriori算法的執行效率略低于經典的Apriori算法。

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

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

[3]劉琦.基于關聯規則的數據挖掘算法研究[C].杭州:浙江大學,2008.

[4]李新良,陳湘濤.數據挖掘中關聯規則算法的研究[J].計算機工程與應用,2007,12(29):111.

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

[6]陳文偉,黃金才.可拓知識與可拓數據挖掘[J].廣西師范大學學報(自然科學版),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]張玉林.一種無冗余的關聯規則算法.計算機工程與應用,2007,43(3):26- 29.