基于關(guān)聯(lián)規(guī)則的數(shù)據(jù)挖掘技術(shù)研究

萬曉燕，陳　姍（青島酒店管理職業(yè)技術(shù)學院信息工程技術(shù)學院，青島266100）

基于關(guān)聯(lián)規(guī)則的數(shù)據(jù)挖掘技術(shù)研究

萬曉燕，陳姍
（青島酒店管理職業(yè)技術(shù)學院信息工程技術(shù)學院，青島266100）

由于信息技術(shù)領(lǐng)域的飛速發(fā)展，在我國數(shù)據(jù)挖掘技術(shù)已經(jīng)被廣泛應(yīng)用于與生活息息相關(guān)的領(lǐng)域中，針對Apriori算法的關(guān)聯(lián)規(guī)則的數(shù)據(jù)挖掘中所存在的諸多問題，介紹基于粒計算算法的關(guān)聯(lián)規(guī)則數(shù)據(jù)挖掘技術(shù)，它是在傳統(tǒng)算法上的優(yōu)化改進。通過具體的實證分析，比較分析Apriori算法和基于粒計算算法的不同效果。因而得出結(jié)論，粒計算算法的關(guān)聯(lián)規(guī)則數(shù)據(jù)挖掘技術(shù)在進行數(shù)據(jù)挖掘處理時更加可行直觀且高效，構(gòu)建一個良好的、開放式的數(shù)據(jù)挖掘平臺。

數(shù)據(jù)挖掘技術(shù)；Apriori算法；粒計算；關(guān)聯(lián)規(guī)則；數(shù)據(jù)挖掘平臺

0　引言

數(shù)據(jù)挖掘技術(shù)是在信息領(lǐng)域中發(fā)展最迅速的技術(shù)，許多領(lǐng)域內(nèi)的專家，例如統(tǒng)計學家和數(shù)據(jù)庫專家都需要準確盡快地獲取自己所需信息，這都促進了數(shù)據(jù)挖掘技術(shù)的不斷進步。同時隨著信息技術(shù)的發(fā)展也帶動了采集方式和能力的不斷高端化，使我們積累的數(shù)據(jù)快速膨脹。一方面，這些海量的數(shù)據(jù)為合理正確的決策提供了基礎(chǔ)條件，但如何從一堆數(shù)據(jù)中識別有用信息則需要耗費大量的人力物力。數(shù)據(jù)挖掘技術(shù)在發(fā)展進步的過程中綜合理論統(tǒng)計學知識等發(fā)展出了自動的模式識別功能和數(shù)字人工智能，廣泛應(yīng)用到機器研究和神經(jīng)網(wǎng)絡(luò)等專業(yè)領(lǐng)域。

關(guān)聯(lián)規(guī)則的數(shù)據(jù)挖掘方法的流程主要是：綜合頻繁項集，由頻繁項集尋找強關(guān)聯(lián)規(guī)則，發(fā)現(xiàn)在某一交易數(shù)據(jù)庫中各個不同項之間的聯(lián)系，所有這些關(guān)聯(lián)規(guī)則是對所需檢測對象的某種特殊模式的反映[3]。但無論在商業(yè)零售領(lǐng)域還是金融電信等領(lǐng)域整個數(shù)據(jù)量是巨大的，提高算法的效率這才是發(fā)展數(shù)據(jù)挖掘技術(shù)的重中之重。通過粒計算算法的關(guān)聯(lián)規(guī)則數(shù)據(jù)挖掘分析，可以解決傳統(tǒng)算法帶來的問題，從而達到簡單快速的發(fā)現(xiàn)在數(shù)據(jù)庫當中的頻繁項集。

1　基于關(guān)聯(lián)規(guī)則的數(shù)據(jù)挖掘基本方法

1.1基本概念分析

關(guān)聯(lián)規(guī)則的數(shù)據(jù)挖掘的數(shù)據(jù)集稱作事務(wù)數(shù)據(jù)庫，給定為D={t1，t2，…，tk，…，tn）。其中tk={i1，i2，…，im，ip）（k= 1，2，…，n）稱為事務(wù)，im（m=1，2，…，p）稱為項目。

若support（X?Y）minsupport且support（X?Y）minconfidence，就稱關(guān)聯(lián)規(guī)則X?Y為強規(guī)則，否則就稱關(guān)聯(lián)規(guī)則X?Y為弱規(guī)則。

挖掘數(shù)據(jù)集中的全部強規(guī)則，是關(guān)聯(lián)規(guī)則挖掘中的一個主要任務(wù)。強規(guī)則X?Y對應(yīng)的項目集（X∪Y）為頻集，則頻集（X∪Y）導出的強關(guān)聯(lián)規(guī)則X?Y的置信度通過頻集與X?Y的支持度的計算結(jié)果得出。綜上所述，能夠?qū)⒒陉P(guān)聯(lián)規(guī)則的數(shù)據(jù)挖掘切割為兩個子問題：一是通過minsupport發(fā)現(xiàn)數(shù)據(jù)集中的全部頻集，二是通過頻繁項目集和最小置信度得出關(guān)聯(lián)規(guī)則的。

第一個子問題是通過minsupport迅速高效發(fā)現(xiàn)數(shù)據(jù)集中的全部頻集，其主要是基于關(guān)聯(lián)規(guī)則數(shù)據(jù)挖掘技術(shù)的核心，主要使用其衡量關(guān)聯(lián)規(guī)則的數(shù)據(jù)挖掘算法；第二個子問題是通過頻繁項目集和最小置信度來獲取關(guān)聯(lián)規(guī)則，具體如下圖所示為關(guān)聯(lián)規(guī)則挖掘的基本模型。

圖1　基于關(guān)聯(lián)規(guī)則的數(shù)據(jù)挖掘過程的基本模型

在上圖中，表示為這個數(shù)據(jù)集，其中Algorithm-1是頻繁項目集的搜索算法，Algorithm-2是經(jīng)過關(guān)聯(lián)規(guī)則而產(chǎn)生的算法，R表示經(jīng)過關(guān)聯(lián)規(guī)則數(shù)據(jù)挖掘技術(shù)處理得到的集合。當用戶指定了minsupport和minconfidence，再進行搜索算法的交互，并跟R進行交互，進行評價解釋得出的挖掘結(jié)果。

1.2基于關(guān)聯(lián)規(guī)則的數(shù)據(jù)挖掘技術(shù)方法核心

當前的普遍的串行算法表述中，Agrawal R.等人提出的Apriori算法是應(yīng)用最為廣泛的，以Apriori算法為基礎(chǔ)，衍生出更多的算法，其核心是最大限度的構(gòu)建最小的候選項目集，再將頻繁項目集的隨機子集進行關(guān)聯(lián)運算分析。

Apriori算法以構(gòu)建頻繁項目集為主要方式來完成項目集元素的數(shù)量，首先獲得1-頻繁項集L1，再獲得2-頻繁項集L2，如擴展結(jié)束，則整個算法停止。當?shù)趉次循環(huán)時，需要首先產(chǎn)生k-候選項集，并且在集合ck內(nèi)，在經(jīng)過數(shù)據(jù)庫的支持度運算獲取k-頻繁項集Lk。

因此將Apriori算法歸納為三個步驟[7～9]：

首先是頻繁k-1項集自連接獲得長度為k的候選k項集ck；

其次是對兩個或兩個以上的非頻繁子集的候選項剪枝；

最后將掃描得到的全部事務(wù)用來獲取候選項集的支持度。

表1中反映了在傳統(tǒng)的Apriori算法中選用Apriori-gen（Lk-1），目的得到（k-1）-頻繁項集所得到得k候選集。

但是作為一個經(jīng)典關(guān)聯(lián)規(guī)則，Apriori算法仍然存在著許多問題：一是需要掃描數(shù)據(jù)庫反復；二是產(chǎn)生的候選項目集數(shù)目太過龐大。如果要解決以上的問題，可以通過改進四個方面來實現(xiàn):

（1）通過減少次掃描數(shù)據(jù)集減少I/O操作。

（2）減少計算支持度項目集的數(shù)量，使之與頻繁項目集的數(shù)目達到相近。

（3）使用的一個子項目集的數(shù)量獲得最大程度的分解。

（4）生成的多個同時進行的項目集。

2　基于粒計算的關(guān)聯(lián)數(shù)據(jù)挖掘分析

2.1粒計算

基于粒計算的關(guān)聯(lián)規(guī)則挖掘可以高效實現(xiàn)上述改進。粒計算（Grc）指是一種基于粒子的問題求解和進行信息處理的方法，該算法的基本思想已經(jīng)應(yīng)用于多種領(lǐng)域，例如聚類分析、決策數(shù)、神經(jīng)網(wǎng)絡(luò)、語義網(wǎng)絡(luò)、區(qū)間分析等。我們在處理大數(shù)量并且復雜的問題時，常常對問題進行信息粒化，所謂信息粒化就是根據(jù)各自特征和性能把信息劃分為多個簡單粒子。

因此可以將基于粒計算的關(guān)聯(lián)數(shù)據(jù)挖掘技術(shù)基本問題概括為兩個方面，一方面是，如何去構(gòu)建信息粒度（也稱作粒的結(jié)構(gòu)）另一方面就是如何進行粒的計算。粒的結(jié)構(gòu)實際上就是粒的形式化表示和解釋。計算的目的是試圖找到最小的計算復雜性近似解去滿足足夠的可行性誤差范圍。計算的基礎(chǔ)取決于前面討論的信息粒化的概念，可以研究來自不同的語義和算法的數(shù)據(jù)。基本任務(wù)之一是粒計算，一個可以檢查和進一步探索顆粒之間的關(guān)系，例如：鄰近、依賴、關(guān)聯(lián)等，信息粒化之間的關(guān)系處在較低的水平還是較高的水平，并且要定義和解釋基于粒的各種算子；并且設(shè)計能夠計算粒的算法和工具。

信息和信息表的基本組成是通過粒空間中的基本粒來表述的，基于粒計算關(guān)聯(lián)規(guī)則的數(shù)據(jù)挖掘算法主要解決的是在過程中粒空間內(nèi)獲取所有的頻繁項集。這種算法輸入的是信息表和支持度，輸出的是頻繁項集合。

將信息根據(jù)其屬性值域?qū)φ撚蛄；玫矫總€屬性的原子信息粒向量grc={a1,a2,…}，其中a1={Cg1,Cg2,…}，m為粒空間的分解層數(shù)即粒空間中向量的個數(shù)。

L=L∪（LT的每個元素的所有子集）；

輸出L，算法結(jié)束。

2.2實證分析

設(shè)一個事務(wù)數(shù)據(jù)庫有九項事務(wù)，T1={B，D，E}，T2= {A，D}，T3={C，D}，T4={A，B，D}，T5={B，C}，T6={C，D}，T7={B，C}，T8={B，C，D，E}，T9={B，C，D}。

表1　事務(wù)數(shù)據(jù)庫（D）表

首先運用Apriori算法對上述數(shù)據(jù)進行的關(guān)聯(lián)規(guī)則數(shù)據(jù)挖掘，結(jié)果如下表所示:

表2　一組頻繁項集表

將上表中掃描數(shù)據(jù)集，并對每一項掃描進行設(shè)置和計數(shù)，去除那些支持度小的，保留支持度大的，結(jié)果如圖所示:

表3　兩組頻繁項集表

從上表可知，比較各選項的支持數(shù)和最小支持度，去除那些確實不滿足最低要求的支持度的項目。例如，（B，C）可以和（B，D）相關(guān)，但不與（C，D）相關(guān)，通過這一原則，得到（B，C，D），（B，C，E），（B，D，E）之間關(guān)系，因為（C，E）不是（B，C，E）的頻繁的子集，所以刪除（B，C，E）在這三個項目。如下所示：

表4　三組頻繁項集表

再用相同方法處理，不滿足聯(lián)接條件選集是空的。第二步通過粒計算的關(guān)聯(lián)數(shù)據(jù)挖掘?qū)⑸鲜霰淼男畔Υ妫紫葎?chuàng)建掃描數(shù)據(jù)集，如下表所示：

表5　粒計算表

上表可知，所有粒度大小達到最小支持度，所以它們通常是一組。在我們得到頻繁項集中，讓所有粒子組合，進一步合并得到:[A，B]，[A，C]，[A，D]，[A，E]，[B，C]，[B，D]，[B，E]，[C，D]，[C，E]，[D，E]。結(jié)果如下。

表6　粒計算后的兩組頻繁項集表

得到獲取的項目集的數(shù)量，它由新的頻繁項集組合可以表示為:[B，C，D]，[B，C，E]，[B，D，E]。二進制字符串是用來表達信息的，用點位提取頻繁項集和關(guān)聯(lián)規(guī)則發(fā)現(xiàn)的。通過分析，[C，E]非候選頻繁集，所以只有[B，C，D]、[B，D，E]是頻繁集，但[B，C，E]并不是。它們的二進制表示和二進制計算結(jié)果如下:

表7　粒計算后的三組頻繁項集表

由以上算法可得，對于Apriori算法的應(yīng)用，其數(shù)據(jù)庫的掃描需要對整個統(tǒng)計數(shù)值進行多次的匹配才能完成，由于匹配時間過長，在實際應(yīng)用中并不能夠體現(xiàn)算法所具有的快捷性，但是基于粒計算關(guān)聯(lián)規(guī)則的數(shù)據(jù)挖掘技術(shù)在一定程度上可以解決這個問題，故，兩種算法的執(zhí)行時間比較如圖3所示。

圖3　兩種算法的執(zhí)行時間圖

3　結(jié)語

伴隨信息技術(shù)的不斷發(fā)展，網(wǎng)絡(luò)數(shù)據(jù)域數(shù)據(jù)庫的構(gòu)建需求日益增長，同時會導致數(shù)據(jù)信息處理規(guī)模不斷增大，因此，如何快速高效的數(shù)據(jù)挖掘是當前該領(lǐng)域亟待解決的問題。粒子算法的核心是通過粒度計算關(guān)聯(lián)規(guī)則的挖掘頻繁項集，其具有實現(xiàn)減少對象掃描數(shù)據(jù)集的工作量，有效提高算法效率的優(yōu)點。使得基于粒計算的關(guān)聯(lián)規(guī)則數(shù)據(jù)挖掘算法能夠被企業(yè)用來進行篩選評估，為該領(lǐng)域的研究提供定量性的參考依據(jù)，同時使服務(wù)對象更加具有優(yōu)化的競爭優(yōu)勢和更專注自身需

[1]郭建威，張玉臣.基于關(guān)聯(lián)規(guī)則的創(chuàng)新矛盾矩陣的研究[J].計算機應(yīng)用研究，2012，29（10）

[2]賈燕茹，王玉芬.基于數(shù)據(jù)挖掘關(guān)聯(lián)規(guī)則技術(shù)的程序設(shè)計訓練課程指導系統(tǒng)研究[J].大家，2010（2）：22～24

[3]瞿麗.基于數(shù)據(jù)挖掘技術(shù)的查詢優(yōu)化[D].東華大學出版社，2009（12）

[4]王付山.關(guān)聯(lián)規(guī)則挖掘技術(shù)在商場中的應(yīng)用[J].商場現(xiàn)代化，2008（4）

[5]范明譯．數(shù)據(jù)挖掘概念與技術(shù)[M]．北京：機械工業(yè)出版社，2004．2

[6]毛國君，段立娟．數(shù)據(jù)挖掘原理與算法[M]．北京：清華大學出版社，2005．7

Data Mining Technology;Apriori Algorithm;Granular Computing;Association Rule;Data Mining Platform

Research on Data Mining Technology of Association Rule

WAN Xiao-yan，CHEN Shan
（Department of Information Technology,Qingdao Vocational and Technical College of Hotel Management,Qingdao 266100）

With the rapidly development of the information field,data mining technology is widely used in the field closely related with our life. Improves the traditional algorithm based on the association rule data mining technology and the problems of Apriori algorithm of association rules mining.Analyzes the differences between Apriori algorithm and granular computing algorithm through the empirical analysis.The result shows that the granular computing data mining association rules are more feasible and effective in data processing，it can provide necessary conditions for the construction of open data mining platform.

1007-1423（2015）14-0018-05

10.3969/j.issn.1007-1423.2015.14.005

萬曉燕（1980-），女，江西南昌人，碩士，講師，研究方向為數(shù)據(jù)挖掘

陳姍（1980-），女，濟南人，本科，副教授，研究方向為計算機軟件技術(shù)

2015-03-24

2015-04-08