郭昌建

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

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

郭昌建

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

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

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

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

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

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

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

設(shè)I={i1, i2,…, im}是二進(jìn)制文字的集合，其中的元素稱為項(xiàng)（item），其中ik（k=1,2,…,m）可以是購(gòu)物籃中的物品，也可以是保險(xiǎn)公司的顧客。設(shè)任務(wù)相關(guān)的數(shù)據(jù)D是事務(wù)集（DB），其中每個(gè)事務(wù)T是項(xiàng)集，使得T?I。這里沒(méi)有考慮事務(wù)中項(xiàng)的數(shù)量，也就是說(shuō)項(xiàng)是由一個(gè)二進(jìn)制的變量來(lái)表示它是否在事務(wù)中出現(xiàn)。每個(gè)事務(wù)都有一個(gè)相關(guān)的標(biāo)識(shí)符或TID。（設(shè)A是一個(gè)項(xiàng)集，且A?T。）關(guān)聯(lián)規(guī)則是如下形式的邏輯蘊(yùn)涵：A?B，A?I, B?I，且A∩B=φ。關(guān)聯(lián)規(guī)則具有支持度和置信度兩個(gè)重要的屬性[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ī)則挖掘分成兩個(gè)階段：一是基于最小支持度獲取頻繁項(xiàng)目集；二是在頻繁項(xiàng)目集上基于最小置信度產(chǎn)生關(guān)聯(lián)規(guī)則。在完成第一步后，第二步可很自然的得到結(jié)果。所以，關(guān)聯(lián)規(guī)則的算法側(cè)重討論如何快速地實(shí)現(xiàn)第一步[5]。

2.1 經(jīng)典Apriori算法

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

所有支持度大于最小支持度的項(xiàng)集稱為頻繁項(xiàng)集，簡(jiǎn)稱頻集。算法的基本思想是：找出所有的頻集，這些項(xiàng)集出現(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)化，但在實(shí)際的應(yīng)用中，還是存在不令人滿意的地方，于是人們相繼提出了一些優(yōu)化的方法，主要有：基于劃分的方法、基于Hash的方法、基于采樣的方法和減少交易的個(gè)數(shù)等。但這些方法都是基于Apriori的頻集方法。即使進(jìn)行了優(yōu)化，但是Apriori方法一些固有的缺陷還是無(wú)法克服；如：可能產(chǎn)生大量的候選集，無(wú)法對(duì)稀有信息進(jìn)行分析，重復(fù)掃描數(shù)據(jù)庫(kù)等。對(duì)產(chǎn)生大量的候選集問(wèn)題可采用一種FP-growth的方法[6]。下面提出的BDIF算法通過(guò)劃分?jǐn)?shù)據(jù)塊，有效快速的搜尋頻繁項(xiàng)目集，從而減少對(duì)數(shù)據(jù)塊的掃描次數(shù)，提高了算法的效率[7,8]。

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

3.1 BDIF算法描述

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3.3 BDIF算法分析與性能測(cè)試

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

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

圖1 測(cè)試結(jié)果

4 結(jié)束語(yǔ)

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

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

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

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

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

[5] 杜孝平,馬秀莉.快速關(guān)聯(lián)規(guī)則挖掘算法[J].計(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].中國(guó)圖象圖形學(xué)報(bào), 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é)任編輯、校對(duì)：田敬軍）

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é)院重點(diǎn)建設(shè)學(xué)科（2014xk08）

2014-09-02

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