基于BDIF的關(guān)聯(lián)規(guī)則挖掘算法研究

郭昌建

（合肥學(xué)院 計算機(jī)科學(xué)與技術(shù)系，安徽 合肥 230601）

基于BDIF的關(guān)聯(lián)規(guī)則挖掘算法研究

郭昌建

（合肥學(xué)院 計算機(jī)科學(xué)與技術(shù)系，安徽 合肥 230601）

闡述了關(guān)聯(lián)規(guī)則挖掘的研究情況，關(guān)聯(lián)規(guī)則的分類方法等，對經(jīng)典Apriori算法進(jìn)行了分析和評價，在此基礎(chǔ)上提出了一種高效產(chǎn)生頻繁集的BDIF（Based Transactional Databases Including Frequent ItemSet）算法；它通過劃分?jǐn)?shù)據(jù)塊，快速的搜尋頻繁項目集，從而減少對數(shù)據(jù)塊的掃描次數(shù)，提高了算法的效率。并用BorlandC++Builder6.0開發(fā)環(huán)境來調(diào)試、驗證該算法。

數(shù)據(jù)挖掘；關(guān)聯(lián)規(guī)則；BDIF

隨著經(jīng)濟(jì)的發(fā)展和信息的增長，許多企業(yè)和組織積累了大量的數(shù)據(jù)，隱含在數(shù)據(jù)中的關(guān)聯(lián)規(guī)則、模式等知識是對決策有幫助的信息。數(shù)據(jù)挖掘的目的就是發(fā)現(xiàn)隱含在數(shù)據(jù)中對決策有幫助的信息，它是實現(xiàn)智能決策支持系統(tǒng)的一個重要手段。數(shù)據(jù)挖掘是從大量的、不完全的、有噪聲的、模糊的、隨機(jī)的數(shù)據(jù)集中識別有效的、新穎的、潛在有用的，以及最終可理解的模式的非平凡過程[1]。

1 關(guān)聯(lián)規(guī)則挖掘綜述

關(guān)聯(lián)規(guī)則挖掘是數(shù)據(jù)挖掘中最活躍的研究方法之一。關(guān)聯(lián)規(guī)則是發(fā)現(xiàn)交易數(shù)據(jù)庫中不同商品（項）之間的聯(lián)系，這些規(guī)則找出顧客購買行為模式，如購買了某一商品對購買其他商品的影響。發(fā)現(xiàn)這樣的規(guī)則可以應(yīng)用于商品貨架設(shè)計、貨存安排以及根據(jù)購買模式對用戶進(jìn)行分類。最早是由Agrawal等人提出的。之后有諸多的研究人員對關(guān)聯(lián)規(guī)則的挖掘問題進(jìn)行了大量的研究。包括對關(guān)聯(lián)規(guī)則挖掘的理論探索、原有的算法的改進(jìn)和新算法的設(shè)計、并行關(guān)聯(lián)規(guī)則挖掘等問題[2]。

1.1 關(guān)聯(lián)規(guī)則的基本概念

設(shè)I={i1, i2,…, im}是二進(jìn)制文字的集合，其中的元素稱為項（item），其中ik（k=1,2,…,m）可以是購物籃中的物品，也可以是保險公司的顧客。設(shè)任務(wù)相關(guān)的數(shù)據(jù)D是事務(wù)集（DB），其中每個事務(wù)T是項集，使得T?I。這里沒有考慮事務(wù)中項的數(shù)量，也就是說項是由一個二進(jìn)制的變量來表示它是否在事務(wù)中出現(xiàn)。每個事務(wù)都有一個相關(guān)的標(biāo)識符或TID。（設(shè)A是一個項集，且A?T。）關(guān)聯(lián)規(guī)則是如下形式的邏輯蘊(yùn)涵：A?B，A?I, B?I，且A∩B=φ。關(guān)聯(lián)規(guī)則具有支持度和置信度兩個重要的屬性[3]。

1.2 關(guān)聯(lián)規(guī)則的分類

關(guān)聯(lián)規(guī)則按不同情況可分為：（1）基于規(guī)則中處理的變量的類別：關(guān)聯(lián)規(guī)則可分為布爾型和數(shù)值型；（2）基于規(guī)則中數(shù)據(jù)的抽象層次：可以分為單層關(guān)聯(lián)規(guī)則和多層關(guān)聯(lián)規(guī)則；（3）基于規(guī)則中涉及到的數(shù)據(jù)的維數(shù)：關(guān)聯(lián)規(guī)則可分為單維的和多維的[4]。

2 關(guān)聯(lián)規(guī)則挖掘算法分析

由關(guān)聯(lián)規(guī)則的定義，可把關(guān)聯(lián)規(guī)則挖掘分成兩個階段：一是基于最小支持度獲取頻繁項目集；二是在頻繁項目集上基于最小置信度產(chǎn)生關(guān)聯(lián)規(guī)則。在完成第一步后，第二步可很自然的得到結(jié)果。所以，關(guān)聯(lián)規(guī)則的算法側(cè)重討論如何快速地實現(xiàn)第一步[5]。

2.1 經(jīng)典Apriori算法

Agrawal等于1994年提出了一個挖掘顧客交易數(shù)據(jù)庫中項集間的關(guān)聯(lián)規(guī)則的重要方法，其核心是基于兩階段頻集思想的遞推算法。該關(guān)聯(lián)規(guī)則在分類上屬于單維、單層、布爾關(guān)聯(lián)規(guī)則。

所有支持度大于最小支持度的項集稱為頻繁項集，簡稱頻集。算法的基本思想是：找出所有的頻集，這些項集出現(xiàn)的頻繁性至少和預(yù)定義的最小支持度一樣。然后由頻集產(chǎn)生強(qiáng)關(guān)聯(lián)規(guī)則，這些規(guī)則必須滿足最小支持度和最小可信度[6]。

2.2 幾種優(yōu)化方法

雖然Apriori算法自身已經(jīng)進(jìn)行了一定的優(yōu)化，但在實際的應(yīng)用中，還是存在不令人滿意的地方，于是人們相繼提出了一些優(yōu)化的方法，主要有：基于劃分的方法、基于Hash的方法、基于采樣的方法和減少交易的個數(shù)等。但這些方法都是基于Apriori的頻集方法。即使進(jìn)行了優(yōu)化，但是Apriori方法一些固有的缺陷還是無法克服；如：可能產(chǎn)生大量的候選集，無法對稀有信息進(jìn)行分析，重復(fù)掃描數(shù)據(jù)庫等。對產(chǎn)生大量的候選集問題可采用一種FP-growth的方法[6]。下面提出的BDIF算法通過劃分?jǐn)?shù)據(jù)塊，有效快速的搜尋頻繁項目集，從而減少對數(shù)據(jù)塊的掃描次數(shù)，提高了算法的效率[7,8]。

3 BDIF算法及其實現(xiàn)

3.1 BDIF算法描述

黃酮類化合物是一種重要的植物生物活性成分，具有抗心腦血管疾病、抗衰老、抗氧化、消炎、鎮(zhèn)痛、免疫調(diào)節(jié)和降血糖等多種功效[15]。仙草黃酮類化合物的主要成分為槲皮素[16]，具有祛痰、止咳、平喘等功效。馮國金等[17]利用高效液相色譜法測定仙草的槲皮素含量為0.18 mg/g。

BDIF（Based Transactional Databases Including Frequent Itemset）算法是一種在包含頻繁k-項集的事務(wù)集中，搜索包含頻繁k+1-項集的事務(wù)集算法。該算法將數(shù)據(jù)庫D劃分為若干個包含事務(wù)集的數(shù)據(jù)塊；數(shù)據(jù)塊的劃分是根據(jù)各個事務(wù)中是否包含的頻繁項目集。這樣，對數(shù)據(jù)庫D的掃描轉(zhuǎn)換為對數(shù)據(jù)塊的掃描。

3.1.1 產(chǎn)生頻繁1-項集

掃描數(shù)據(jù)庫，統(tǒng)計各個項目的支持度。按支持度從大到小對頻繁1-項集進(jìn)行排序，如果支持度相同，則按字典順序，并記下每個頻繁1-項集的序號x（序號從1開始計）。根據(jù)該順序，排列相應(yīng)的事務(wù)集Tx1。

3.1.2 搜尋包含最大頻繁項集的事務(wù)集

經(jīng)過第一步后，利用以上推論，掃描包含頻繁1—項集的事務(wù)集Tx1。若P為數(shù)據(jù)庫D中的項目數(shù)，為避免重復(fù)產(chǎn)生相同的事務(wù)集，對事務(wù)集Tx1只產(chǎn)生P-X個包含頻繁2—項集的事務(wù)集Tx+12，……依次類推，對于每一個包含頻繁K—項集的事務(wù)集，分別搜索其中所包含的不同的頻繁K+1—項集，直到搜索到最大頻繁項目集，或是用戶指定的頻繁M-項集。

3.1.3 頻繁項集的產(chǎn)生

對每一個包含最大頻繁項集的事務(wù)集，輸出其中包含的最大頻繁項集。如何依次掃描所有的事務(wù)集Txk以產(chǎn)生包含頻繁K+1項集的事務(wù)集Tx+1k+1？這是算法能順利實現(xiàn)的關(guān)鍵所在。在此引用一種數(shù)據(jù)結(jié)構(gòu)——隊列，以輔助算法的實現(xiàn)。引用隊列來存儲尚未進(jìn)行搜索的若干個包含頻繁k—項集的事務(wù)集，以及已搜索過的、滿足再次搜索條件的、包含頻繁k+1—項集的事務(wù)集，使得算法不會重復(fù)掃描相同的事務(wù)集。該方法的具體實現(xiàn)如下：

（1）選擇頻繁1-項集中支持度最大的頻繁項目L[1]，若事務(wù)中包含此項目L[1]，則將該事務(wù)加入相應(yīng)的T集合中。

（3）根據(jù)支持度大小，依次選擇頻繁1—項集中的頻繁項目L[k]，重復(fù)（1）（2）。這樣，依次入隊的是根據(jù)支持度大小分別包含頻繁1-項集的事務(wù)集。

對于列隊中的事務(wù)集，依次出隊；使D＝對頭元素。從D中搜索包含給定候選項集的事務(wù)并生成新集合T，若T中的事務(wù)數(shù)>=minsup，則將T入隊；

否則，若D中包含的頻繁項目數(shù)最多，則D就是包含最大頻繁項集的事務(wù)集。

3.2 BDIF算法的實現(xiàn)

輸入：數(shù)據(jù)庫D，最小支持度minsup；輸出：若干個最大頻繁項集I。過程如下：

3.3 BDIF算法分析與性能測試

為了測試算法的性能，將BDIF算法與經(jīng)典的基于Apriori算法的的并行算法CD（CountDistribution）等進(jìn)行性能比較。開發(fā)環(huán)境為Borland C++ Builder6.0，消息傳遞庫為標(biāo)準(zhǔn)MPI，測試結(jié)果如圖1所示。

由測試的結(jié)果可知，在相同支持度下，與CD等并行挖掘算法相比，數(shù)據(jù)庫掃描次數(shù)和執(zhí)行時間都降低了，而且隨著支持度的下降，BDIF算法性能優(yōu)勢更加明顯。

圖1 測試結(jié)果

4 結(jié)束語

Apriori算法需多次掃描數(shù)據(jù)庫所有事務(wù)，程序時間開銷很大。而BDIF算法把整個數(shù)據(jù)庫按頻繁k-項集劃分為幾個小事務(wù)集，然后根據(jù)Apriori性質(zhì)：包含頻繁k+1-項集的事務(wù)集是包含頻繁k-項集的事務(wù)集的子集，直接從包含頻繁k-項集事務(wù)集推出包含頻繁k+1-項集的事務(wù)集，無需多次掃描整個數(shù)據(jù)庫。和經(jīng)典算法相比，更節(jié)省時間，效率更高。

[1] 李文實.用關(guān)聯(lián)規(guī)則挖掘算法的研究和實現(xiàn)[J].現(xiàn)代計算機(jī)2000(11):6-8.

[2] 劉大有,劉亞波,尹治東.關(guān)聯(lián)規(guī)則最大頻繁項目集的快速發(fā)現(xiàn)算法[J].吉林大學(xué)學(xué)報(理學(xué)版),2004,42(2):56-58.

[3] 胡侃,夏紹瑋.基于大型數(shù)據(jù)倉庫的數(shù)據(jù)采掘研究綜述[J].軟件學(xué)報,1998,9(1):53-63.

[4] 陸麗娜,陳亞萍挖掘關(guān)聯(lián)規(guī)則中Apriori算法的研究[J].小型微型計算機(jī)系統(tǒng),2000,21(9):940-943.

[5] 杜孝平,馬秀莉.快速關(guān)聯(lián)規(guī)則挖掘算法[J].計算機(jī)工程與應(yīng)用,2002(11):1-4.

[6] J. Han, J. Pei, Y Yin. Mining frequent patterns without candidate generation[A]. Proc. 2000 ACM-SIGMOD Int. Conf. Management of Data(SIGMOD’00)[C]. Dalas: TX, 2000.

[7] 吉根林,孫志揮.數(shù)據(jù)挖掘技術(shù)[J].中國圖象圖形學(xué)報, 2001,6(8):715-721.

[8] F. Korn, A. Labrinidis, Y. Kotidis, and C. Faloutsos. Ratio rules: A new paradigm.for fast, quantifiable data mining. In Proc. 1998 VLDB, PP582-593.

（責(zé)任編輯、校對：田敬軍）

On the Mining Algorithm Based on BDIF Association Rule

GUO Chang-jian

(Department of Computer Science and Technology, Hefei University, Hefei 230601, China)

This article describes research on association rule mining and classification methods of association rules, analyzes and evaluates the classic Apriori algorithm, which gives rise to an efficient frequent BDIF (Based Transactional Databases Including Frequent Item Set) algorithm. It thereby reduces scanning data block and improves algorithm efficiency by dividing data block and quickly searching for frequent item set.

data mining; association rules; based transactional databases including frequent item set

TP391.1

A

1009-9115(2015)02-0042-03

10.3969/j.issn.1009-9115.2015.02.013

合肥學(xué)院重點建設(shè)學(xué)科（2014xk08）

2014-09-02

郭昌建（1965-），男，安徽合肥人，碩士，副教授，研究方向為計算機(jī)網(wǎng)絡(luò)、人工智能。