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

郭昌建

（合肥學院 計算機科學與技術系，安徽 合肥 230601）

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

郭昌建

（合肥學院 計算機科學與技術系，安徽 合肥 230601）

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

數據挖掘；關聯規則；BDIF

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

1 關聯規則挖掘綜述

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

1.1 關聯規則的基本概念

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

1.2 關聯規則的分類

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

2 關聯規則挖掘算法分析

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

2.1 經典Apriori算法

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

所有支持度大于最小支持度的項集稱為頻繁項集，簡稱頻集。算法的基本思想是：找出所有的頻集，這些項集出現的頻繁性至少和預定義的最小支持度一樣。然后由頻集產生強關聯規則，這些規則必須滿足最小支持度和最小可信度[6]。

2.2 幾種優化方法

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

3 BDIF算法及其實現

3.1 BDIF算法描述

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

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

3.1.1 產生頻繁1-項集

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

3.1.2 搜尋包含最大頻繁項集的事務集

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

3.1.3 頻繁項集的產生

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

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

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

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

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

3.2 BDIF算法的實現

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

3.3 BDIF算法分析與性能測試

為了測試算法的性能，將BDIF算法與經典的基于Apriori算法的的并行算法CD（CountDistribution）等進行性能比較。開發環境為Borland C++ Builder6.0，消息傳遞庫為標準MPI，測試結果如圖1所示。

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

圖1 測試結果

4 結束語

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

[1] 李文實.用關聯規則挖掘算法的研究和實現[J].現代計算機2000(11):6-8.

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

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

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

[5] 杜孝平,馬秀莉.快速關聯規則挖掘算法[J].計算機工程與應用,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] 吉根林,孫志揮.數據挖掘技術[J].中國圖象圖形學報, 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.

（責任編輯、校對：田敬軍）

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

合肥學院重點建設學科（2014xk08）

2014-09-02

郭昌建（1965-），男，安徽合肥人，碩士，副教授，研究方向為計算機網絡、人工智能。