程險(xiǎn)峰

（長(zhǎng)春市公安局交通警察支隊(duì)，長(zhǎng)春 130000）

數(shù)據(jù)關(guān)聯(lián)是數(shù)據(jù)庫(kù)中存在的一類重要的可被發(fā)現(xiàn)的知識(shí)。若兩個(gè)或多個(gè)變量的取值之間存在某種規(guī)律性，則稱之為關(guān)聯(lián)，關(guān)聯(lián)可以分為簡(jiǎn)單關(guān)聯(lián)、時(shí)序關(guān)聯(lián)、因果關(guān)聯(lián)。關(guān)聯(lián)分析的目的是從大型數(shù)據(jù)中找出隱藏的屬性之間存在的關(guān)聯(lián)和規(guī)律。有時(shí)并不知道數(shù)據(jù)庫(kù)中數(shù)據(jù)的關(guān)聯(lián)函數(shù)，即使知道也是不確定的，因此關(guān)聯(lián)分析生成的規(guī)則帶有可信度。

自Agrawal等人首次提出了挖掘顧客交易數(shù)據(jù)庫(kù)中項(xiàng)集間的關(guān)聯(lián)規(guī)則問(wèn)題以來(lái)，研究人員對(duì)原有的算法進(jìn)行了大量研究和進(jìn)一步優(yōu)化，例如，提出了隨機(jī)采樣、并行等思想，使得挖掘規(guī)則算法的效率和伸縮性都有了提高，并且推廣了關(guān)聯(lián)規(guī)則的應(yīng)用范圍。

1 傳統(tǒng)的關(guān)聯(lián)規(guī)則挖掘算法

1.1 Apriori算法

Apriori算法最初是由 Agrawal等人提出的，Apriori算法是一種經(jīng)典的規(guī)則挖掘算法，通過(guò)挖掘布爾關(guān)聯(lián)規(guī)則頻繁項(xiàng)集挖掘數(shù)據(jù)。其基本原理如下：

（1）通過(guò)事物數(shù)據(jù)庫(kù)得到大一項(xiàng)集L1。若L1為非空的，則由L1產(chǎn)生長(zhǎng)度為2的候選項(xiàng)集合C2；

（2）對(duì)事務(wù)數(shù)據(jù)庫(kù)中的每一個(gè)事務(wù) t，求出 t在C2中的全部子集Ct，對(duì)于Ct中的每一個(gè)長(zhǎng)度為2的候選項(xiàng)集c進(jìn)行加1操作。

（3）完成一次事務(wù)數(shù)據(jù)庫(kù)的掃描，篩選出C2中滿足最小支持度的項(xiàng)集組成了長(zhǎng)度為2的頻繁項(xiàng)集合。

（4）重復(fù)以上步驟，處理新得到的頻繁項(xiàng)集合，直到不再產(chǎn)生頻繁項(xiàng)集合為止。Apriori算法的缺點(diǎn)是掃描事務(wù)數(shù)據(jù)庫(kù)次數(shù)過(guò)多、在頻繁項(xiàng)長(zhǎng)度變大的情況下，運(yùn)算時(shí)間顯著增加、不能直接用于關(guān)系數(shù)據(jù)庫(kù)的關(guān)聯(lián)規(guī)則挖掘、不適于海量數(shù)據(jù)環(huán)境下的關(guān)聯(lián)規(guī)則挖掘。

1.2 基于劃分的算法

A.Savasere等人提出的Partition算法和S.Brin等人提出的DIC算法均屬于基于劃分的算法。這些算法為了節(jié)省訪問(wèn)外部存儲(chǔ)器I/O的開(kāi)銷，將整個(gè)數(shù)據(jù)集劃分為數(shù)據(jù)塊，然后將這些數(shù)據(jù)塊存放在內(nèi)存中進(jìn)行處理。與 Apriori算法相比，數(shù)據(jù)集劃分算法高度并行并且候選項(xiàng)目集數(shù)量比較大，是各種并行關(guān)聯(lián)規(guī)則和分布式關(guān)聯(lián)規(guī)則挖掘算法的基礎(chǔ)。該算法先把每個(gè)分塊數(shù)據(jù)分別分配給某一個(gè)處理器生成頻集，產(chǎn)生頻集的每個(gè)循環(huán)結(jié)束以后，處理器之間通過(guò)通信產(chǎn)生全局的候選k-項(xiàng)集，算法的執(zhí)行時(shí)間主要取決于該通信過(guò)程，這也是算法的主要瓶頸；另一個(gè)瓶頸即每個(gè)獨(dú)立的處理器生成頻集所消耗的時(shí)間。

1.3 FP-樹(shù)頻集算法

頻繁項(xiàng)集挖掘算法 FP-樹(shù)算法的基本原理是通過(guò)兩次掃描數(shù)據(jù)庫(kù)，將數(shù)據(jù)信息存到一種高度壓縮的數(shù)據(jù)結(jié)構(gòu) FP-樹(shù)里，避免生成候選項(xiàng)集，縮小了搜索空間，減少了數(shù)據(jù)模式匹配的開(kāi)銷，進(jìn)而有效地避免了多次掃描數(shù)據(jù)庫(kù)和生成大量候選項(xiàng)集所造成的時(shí)間、空間上的浪費(fèi)。但由于 FP-樹(shù)算法沒(méi)有充分考慮層次數(shù)據(jù)的自身特點(diǎn)，在查找頻繁項(xiàng)集的過(guò)程中，計(jì)算了大量的無(wú)用項(xiàng)集。使得該算法不能根據(jù)層次數(shù)據(jù)的特點(diǎn)去除關(guān)聯(lián)規(guī)則的冗余，從而產(chǎn)生大量冗余關(guān)聯(lián)規(guī)則。

2 幾種關(guān)聯(lián)規(guī)則挖掘算法的改進(jìn)

基于 FP-樹(shù)頻集算法的改進(jìn)算法，針對(duì)層次結(jié)構(gòu)數(shù)據(jù)的內(nèi)在特征，研究高效的去冗余多層關(guān)聯(lián)規(guī)則挖掘算法。通過(guò)采取聚類的方法，對(duì)已有的評(píng)價(jià)關(guān)聯(lián)規(guī)則的支持度和可信度（兩個(gè)常用的客觀性指標(biāo)），增加一個(gè)相關(guān)的業(yè)務(wù)參數(shù)，達(dá)到對(duì)樹(shù)的進(jìn)一步劃分，不斷減小頻繁項(xiàng)集挖掘時(shí)需要掃描的數(shù)據(jù)庫(kù)，進(jìn)而提高挖掘效率，以便挖掘出收益較高、值得關(guān)注的業(yè)務(wù)。

基于遺傳算法的思想改進(jìn) Apriori算法，只需要對(duì)數(shù)據(jù)庫(kù)進(jìn)行一次掃描，便可以給定一個(gè)映射，實(shí)現(xiàn)據(jù)庫(kù)到矩陣的映射，以下均可通過(guò)在矩陣上的運(yùn)算來(lái)完成所有對(duì)數(shù)據(jù)庫(kù)的掃描。將某個(gè)生物種群對(duì)環(huán)境的適應(yīng)性問(wèn)題轉(zhuǎn)化為求解關(guān)聯(lián)規(guī)則最長(zhǎng)頻繁項(xiàng)集的問(wèn)題，生物種群的進(jìn)化過(guò)程即為優(yōu)化問(wèn)題的求解過(guò)程，生物種群的個(gè)體即為優(yōu)化變量。基于遺傳算法改進(jìn)Apriori算法的基本思想：

（1）進(jìn)行二進(jìn)制或十進(jìn)制編碼；

（2）根據(jù)實(shí)際要求，選取遺傳算法的適應(yīng)度函數(shù)，并由適應(yīng)度函數(shù)求出頻繁 1-項(xiàng)集，進(jìn)行交叉、變異運(yùn)算進(jìn)化該組項(xiàng)集；

（3）進(jìn)行選擇運(yùn)算產(chǎn)生下一代頻繁項(xiàng)集，反復(fù)迭代運(yùn)算若干代，直至最終滿足遺傳算法的終止條件，此時(shí)得到一組最長(zhǎng)頻繁項(xiàng)集。

3 改進(jìn)算法分析

（一）基于 FP-樹(shù)頻集算法的改進(jìn)算法以大型的商業(yè)交易為例，每次商業(yè)交易都有層次結(jié)構(gòu)樹(shù)的特征，對(duì)整個(gè)交易樹(shù)利用特定的業(yè)務(wù)參數(shù)進(jìn)行分類，通過(guò)自頂向下方式（下層分類是在上層分類結(jié)果基礎(chǔ)上進(jìn)行的），依次對(duì)各層子樹(shù)（第1層根節(jié)點(diǎn)除外）進(jìn)行分類。分類過(guò)程主要分為以下幾個(gè)步驟：

（1）對(duì)于交易樹(shù)的第i層，若第i-1層中每個(gè)分類交易子樹(shù)的層數(shù)是第2層，則考察整個(gè)交易子樹(shù)；

（2）對(duì)于交易樹(shù)的第i-1層，若其中1-項(xiàng)集不是頻繁項(xiàng)集的子樹(shù)，則將其從交易數(shù)據(jù)庫(kù)中刪除且不納入后續(xù)分類；

（3）對(duì)于交易樹(shù)的第i-1層，若每棵待分類的交易子樹(shù)，則計(jì)算所有子樹(shù)兩兩之間的業(yè)務(wù)參數(shù)。

由于包含這兩棵交易子樹(shù)的2-項(xiàng)集(subtree-i，subtree-j)表示的是這兩類交易在事務(wù)數(shù)據(jù)庫(kù)中同時(shí)出現(xiàn)的頻率，值越大，則這兩類交易子樹(shù)參數(shù)相關(guān)性程度可能會(huì)越高，按每一層上交易子樹(shù)之間的業(yè)務(wù)參數(shù)相關(guān)程度，根據(jù)層次連接聚類算法的方法，就可以得到該層上各交易子樹(shù)之間相互獨(dú)立(或說(shuō)弱利潤(rùn)相關(guān))的分類，然后依此對(duì)上層交易數(shù)據(jù)庫(kù)進(jìn)一步進(jìn)行劃分，使得生成k-項(xiàng)集時(shí)須掃描的數(shù)據(jù)庫(kù)變得越來(lái)越小，以此達(dá)到提高生成頻繁項(xiàng)集和關(guān)聯(lián)規(guī)則的效率。因此該改進(jìn)算法適用于大型的金融交易之中，比如銀行交易、大型企業(yè)交易等。

表1 算法參數(shù)Tab.1 Parameters of algorithm

（二）應(yīng)用遺傳算法的思想改進(jìn)Apriori算法，應(yīng)用此算法進(jìn)行求解，算法參數(shù)見(jiàn)表1。

在算法中還隨機(jī)產(chǎn)生了一組具有2000個(gè)事務(wù)、30個(gè)項(xiàng)的數(shù)據(jù)。

表2顯示了在不同支持度下所得到的最大頻繁項(xiàng)集的個(gè)數(shù)、消耗時(shí)間和循環(huán)次數(shù)。相對(duì)于原始的Apriori算法改進(jìn)后的算法節(jié)省了時(shí)間，提高了效率。

表2 實(shí)驗(yàn)運(yùn)行結(jié)果Tab.2 Result of experiment

4 結(jié)論

根據(jù)理論以及實(shí)驗(yàn)結(jié)果分析，改進(jìn)算法相比與傳統(tǒng)的算法，調(diào)高了效率，且節(jié)省了時(shí)間，在實(shí)際應(yīng)用中有一定的可行性，根據(jù)不同算法的不同特點(diǎn)，可以應(yīng)用到相應(yīng)的領(lǐng)域中去。

［1］馮潔，陶宏才.典型關(guān)聯(lián)規(guī)則挖掘算法的分析與比較［J］.計(jì)算機(jī)技術(shù)與發(fā)展，2007，17（3）：121-124.

［2］陳沛玲.決策樹(shù)分類算法研究［D］.中南大學(xué)，2007.

［3］Perner P.Recent advances in data mining［J］.Engineering Appli-cations of Artificial Intelligence，2006，19（4）：361-362.

［4］劉建.商務(wù)智能中關(guān)聯(lián)規(guī)則挖掘算法的研究及應(yīng)用［D］.長(zhǎng)春理工大學(xué)，2009.