基于關聯規則的數據挖掘技術研究

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

基于關聯規則的數據挖掘技術研究

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

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

數據挖掘技術；Apriori算法；粒計算；關聯規則；數據挖掘平臺

0　引言

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

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

1　基于關聯規則的數據挖掘基本方法

1.1基本概念分析

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

若support（X?Y）minsupport且support（X?Y）minconfidence，就稱關聯規則X?Y為強規則，否則就稱關聯規則X?Y為弱規則。

挖掘數據集中的全部強規則，是關聯規則挖掘中的一個主要任務。強規則X?Y對應的項目集（X∪Y）為頻集，則頻集（X∪Y）導出的強關聯規則X?Y的置信度通過頻集與X?Y的支持度的計算結果得出。綜上所述，能夠將基于關聯規則的數據挖掘切割為兩個子問題：一是通過minsupport發現數據集中的全部頻集，二是通過頻繁項目集和最小置信度得出關聯規則的。

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

圖1　基于關聯規則的數據挖掘過程的基本模型

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

1.2基于關聯規則的數據挖掘技術方法核心

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

Apriori算法以構建頻繁項目集為主要方式來完成項目集元素的數量，首先獲得1-頻繁項集L1，再獲得2-頻繁項集L2，如擴展結束，則整個算法停止。當第k次循環時，需要首先產生k-候選項集，并且在集合ck內，在經過數據庫的支持度運算獲取k-頻繁項集Lk。

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

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

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

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

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

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

（1）通過減少次掃描數據集減少I/O操作。

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

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

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

2　基于粒計算的關聯數據挖掘分析

2.1粒計算

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

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

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

將信息根據其屬性值域對論域粒化，得到每個屬性的原子信息粒向量grc={a1,a2,…}，其中a1={Cg1,Cg2,…}，m為粒空間的分解層數即粒空間中向量的個數。

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

輸出L，算法結束。

2.2實證分析

設一個事務數據庫有九項事務，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　事務數據庫（D）表

首先運用Apriori算法對上述數據進行的關聯規則數據挖掘，結果如下表所示:

表2　一組頻繁項集表

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

表3　兩組頻繁項集表

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

表4　三組頻繁項集表

再用相同方法處理，不滿足聯接條件選集是空的。第二步通過粒計算的關聯數據挖掘將上述表的信息儲存，首先創建掃描數據集，如下表所示：

表5　粒計算表

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

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

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

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

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

圖3　兩種算法的執行時間圖

3　結語

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

[1]郭建威，張玉臣.基于關聯規則的創新矛盾矩陣的研究[J].計算機應用研究，2012，29（10）

[2]賈燕茹，王玉芬.基于數據挖掘關聯規則技術的程序設計訓練課程指導系統研究[J].大家，2010（2）：22～24

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

[4]王付山.關聯規則挖掘技術在商場中的應用[J].商場現代化，2008（4）

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

[6]毛國君，段立娟．數據挖掘原理與算法[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-），女，江西南昌人，碩士，講師，研究方向為數據挖掘

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

2015-03-24

2015-04-08