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

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

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

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

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

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

0　引言

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

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

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）稱為項(xiàng)目。

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

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

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

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

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

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

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

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

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

首先是頻繁k-1項(xiàng)集自連接獲得長(zhǎng)度為k的候選k項(xiàng)集ck；

其次是對(duì)兩個(gè)或兩個(gè)以上的非頻繁子集的候選項(xiàng)剪枝；

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

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

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

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

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

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

（4）生成的多個(gè)同時(shí)進(jìn)行的項(xiàng)目集。

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

2.1粒計(jì)算

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

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

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

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

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

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

2.2實(shí)證分析

設(shè)一個(gè)事務(wù)數(shù)據(jù)庫有九項(xiàng)事務(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）表

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

表2　一組頻繁項(xiàng)集表

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

表3　兩組頻繁項(xiàng)集表

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

表4　三組頻繁項(xiàng)集表

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

表5　粒計(jì)算表

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

表6　粒計(jì)算后的兩組頻繁項(xiàng)集表

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

表7　粒計(jì)算后的三組頻繁項(xiàng)集表

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

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

3　結(jié)語

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

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

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

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

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

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

[6]毛國(guó)君，段立娟．?dāng)?shù)據(jù)挖掘原理與算法[M]．北京：清華大學(xué)出版社，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-），女，江西南昌人，碩士，講師，研究方向?yàn)閿?shù)據(jù)挖掘

陳姍（1980-），女，濟(jì)南人，本科，副教授，研究方向?yàn)橛?jì)算機(jī)軟件技術(shù)

2015-03-24

2015-04-08