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

金育嬋

浙江工商大學(xué)，浙江杭州 310018

1 概述

1.1 課題的研究背景

現(xiàn)代計算機(jī)科學(xué)技術(shù)發(fā)展的歷史，同時也是數(shù)據(jù)和信息加工手段不斷更新和改善的歷史。隨著計算機(jī)硬件和軟件不斷的發(fā)展，尤其是數(shù)據(jù)庫技術(shù)與應(yīng)用的廣泛推廣，擺在人們面前的問題出現(xiàn)了，這些急劇膨脹的信息數(shù)據(jù)，如何有效利用這一豐富數(shù)據(jù)海洋的寶藏為人類服務(wù)，也已成為廣大信息技術(shù)工作者所重點關(guān)注的焦點之一。

傳統(tǒng)的收集數(shù)據(jù)技術(shù)可以在一定程度上對收集來的數(shù)據(jù)信息進(jìn)行統(tǒng)計分析，能夠獲得一定的數(shù)據(jù)價值，這種傳統(tǒng)的收集數(shù)據(jù)技術(shù)具有一定的效果，但當(dāng)這種方法在面對海量的數(shù)據(jù)并從中進(jìn)行數(shù)據(jù)分析時，卻沒有一個比較好的解決方案。無論是數(shù)據(jù)的統(tǒng)計、數(shù)據(jù)的查詢、數(shù)據(jù)的報表等這些傳統(tǒng)的數(shù)據(jù)處理方式都是對收集來的數(shù)據(jù)簡單的進(jìn)行處理，而不能對這些數(shù)據(jù)內(nèi)部所隱含的價值信息進(jìn)行有效的提取和分析。在這些大量數(shù)據(jù)的背后隱藏了很多具有決策意義的信息，如何得到這些能夠為我們提供決策依據(jù)的數(shù)據(jù)依據(jù)已經(jīng)成為當(dāng)前的一個熱點的研究方向。

1.2 研究目的和意義

數(shù)據(jù)挖掘技術(shù)是面向應(yīng)用型的。目前，在很多重要的領(lǐng)域，數(shù)據(jù)挖掘都可以發(fā)揮積極促進(jìn)的作用，尤其是在如保險、交通、零售、銀行、電信等商業(yè)應(yīng)用領(lǐng)域。數(shù)據(jù)挖掘能夠幫助用戶解決許多典型的商業(yè)性的問題，其中包括：數(shù)據(jù)庫營銷、客戶群體劃分、背景分析、交叉銷售等市場分析行為，以及客戶流失性分析、客戶信用評分、欺詐發(fā)現(xiàn)等等。

數(shù)據(jù)挖掘技術(shù)已經(jīng)廣泛的在企業(yè)市場的營銷中得到了應(yīng)用，它以市場營銷學(xué)的市場細(xì)分原理為基礎(chǔ)，通過對涉及到消費者消費行為的信息進(jìn)行收集、加工和處理，得出結(jié)論以確定目標(biāo)消費者地興趣、消費傾向、習(xí)慣以及消費需求，從而能夠推出目標(biāo)消費者下一步的消費方向，然后以得出來的結(jié)論為基礎(chǔ)，對目標(biāo)消費者和消費群體進(jìn)行定向的營銷，這與傳統(tǒng)的盲目營銷的方式相比，可以在很大程度上節(jié)省因營銷而產(chǎn)生的開支，能夠提高營銷的成功率，從而可以為企業(yè)帶來更大的利潤，也能夠幫助企業(yè)樹立起好的口碑。

2 數(shù)據(jù)挖掘技術(shù)的理論基礎(chǔ)

2.1 數(shù)據(jù)挖掘技術(shù)概述

數(shù)據(jù)挖掘的定義是能夠從大量、有噪聲、模糊、隨機(jī)、不完全、實際應(yīng)用數(shù)據(jù)中提取出隱含在其中的，又不為人們所知的，同時具有潛在價值的知識和信息的過程，又被稱為從數(shù)據(jù)庫中的知識發(fā)現(xiàn)。數(shù)據(jù)挖掘不同于傳統(tǒng)的數(shù)據(jù)分析，二者有著本質(zhì)的區(qū)別，數(shù)據(jù)挖掘是在沒有明確假設(shè)的前提下去挖掘信息、發(fā)現(xiàn)知識。通過挖掘所得到的信息應(yīng)該具有未知、有效和實用等3個特征。整個KDD通常會有若干個挖掘的步驟組成，通常，數(shù)據(jù)挖掘是其中最重要的一個步驟。

通常情況來講，數(shù)據(jù)挖掘與知識發(fā)現(xiàn)這兩個概念很容易被人們所混淆，其主要原因是它們有相似性以及共同點，并且究其表面信息來講，似乎如出一轍。但是就其實質(zhì)來講，兩者是有顯著不同的[1]。

圖1 數(shù)據(jù)挖掘技術(shù)結(jié)構(gòu)圖

2.2 數(shù)據(jù)挖掘的任務(wù)

數(shù)據(jù)挖掘的任務(wù)主要是關(guān)聯(lián)分析、聚類分析、分類、預(yù)測、偏差分析和時序模式。

2.2.1 關(guān)聯(lián)分析

關(guān)聯(lián)規(guī)則挖掘是由2個或2個以上變量來取值的。這些變量之間假如存在著某種關(guān)系，就可以稱這些變量之間相互關(guān)聯(lián)。數(shù)據(jù)的關(guān)聯(lián)在數(shù)據(jù)庫中可以把分為簡單、時序和因果的關(guān)聯(lián)，同時也是目前對數(shù)據(jù)關(guān)聯(lián)的一個熱門的研究方向。

2.2.2 聚類分析

聚類分析就是把數(shù)據(jù)按其相似性進(jìn)行分類，分為不同的類別，同一類別中的數(shù)據(jù)是相似的，不同類中的數(shù)據(jù)是不相同的。通過聚類分析我們可以發(fā)現(xiàn)數(shù)據(jù)的分布模式，通過數(shù)據(jù)的分布模式找出可能的數(shù)據(jù)屬性之間的關(guān)系。

2.2.3 分類

分類就是在數(shù)據(jù)的分析過程中找到一個分類的概念，然后對這個分類的概念進(jìn)行詳細(xì)的概述，不同的分類代表不同類別數(shù)據(jù)的信息，并用對這種分類的詳細(xì)定義來構(gòu)造相應(yīng)的模型，這種構(gòu)造的模型一般用決策樹的模式或者規(guī)則模式進(jìn)行詳細(xì)的描述。

2.2.4 預(yù)測分析

預(yù)測就是希望通過對數(shù)據(jù)的系統(tǒng)分析，以找到數(shù)據(jù)變化的趨勢和發(fā)展的規(guī)律，并依照這種趨勢和發(fā)展的規(guī)律建立對應(yīng)的數(shù)學(xué)模型，然后用這種數(shù)學(xué)模型對數(shù)據(jù)的未來走勢和發(fā)展進(jìn)行對應(yīng)的預(yù)測。對預(yù)測結(jié)果關(guān)心的是預(yù)測的準(zhǔn)確度，這個準(zhǔn)確度通常可以用預(yù)測的方差進(jìn)行度量。

2.2.5 偏差分析

在對偏差的分析過程中能夠用到很多的知識，而數(shù)據(jù)庫中的數(shù)據(jù)多多少少有著異常的情況，通過對數(shù)據(jù)使用偏差分析來發(fā)現(xiàn)數(shù)據(jù)庫中數(shù)據(jù)存在的異常狀況，這對對于數(shù)據(jù)挖掘來說是非常重要的。

2.2.6 時序模式

時序模式是指通過時間序列的方法來找出的發(fā)生概率比較高的數(shù)據(jù)模式。這種數(shù)據(jù)模式與回歸模式是一樣的，也就是通過使用己知的數(shù)據(jù)來對數(shù)據(jù)未來的值進(jìn)行預(yù)測。

2.3 數(shù)據(jù)挖掘的方法

數(shù)據(jù)挖掘的方法包括：神經(jīng)網(wǎng)絡(luò)方法、統(tǒng)計分析方法、模糊集方法、遺傳算法、決策樹方法、覆蓋正例排斥反例方法等等。

圖2 數(shù)據(jù)挖掘的方法

2.4 數(shù)據(jù)挖掘的對象和流程

根據(jù)信息存儲格式，用于挖掘的對象有關(guān)系數(shù)據(jù)庫、文本數(shù)據(jù)源、多媒體數(shù)據(jù)庫、空間數(shù)據(jù)庫、時態(tài)數(shù)據(jù)庫、面向?qū)ο髷?shù)據(jù)庫、數(shù)據(jù)倉庫、異質(zhì)數(shù)據(jù)庫以及Internet等。

數(shù)據(jù)挖掘的流程包括：定義問題、數(shù)據(jù)準(zhǔn)備、數(shù)據(jù)挖掘、結(jié)果分析和知識運用等。如下圖所示：

圖3 數(shù)據(jù)挖掘流程圖

2.5 數(shù)據(jù)挖掘的應(yīng)用

數(shù)據(jù)挖掘在各領(lǐng)域的應(yīng)用還是比較廣泛的，只要該產(chǎn)業(yè)的數(shù)據(jù)具有分析價值并且需要利用數(shù)據(jù)倉庫和數(shù)據(jù)庫，皆可利用數(shù)據(jù)挖掘工具來進(jìn)行有目的的挖掘分析與評估。通常情況來講，較為常見的數(shù)據(jù)挖掘應(yīng)用多發(fā)生在制造業(yè)、零售業(yè)、財務(wù)金融保險、直效行銷界、通訊業(yè)以及醫(yī)療服務(wù)等。

3 關(guān)聯(lián)規(guī)則的理論基礎(chǔ)和算法研究

3.1 關(guān)聯(lián)規(guī)則概述

如果假設(shè)I是項的集合。那么給定一個交易數(shù)據(jù)庫，交易數(shù)據(jù)庫中每個事務(wù)是I的一個非空子集，即，每一個交易都與一個唯一的標(biāo)識符TID對應(yīng)。關(guān)聯(lián)規(guī)則在D中的支持度是D中事務(wù)同時包含X、Y的百分比，即概率；置信度是包含X的事務(wù)中同時又包含Y的百分比，即條件概率。關(guān)聯(lián)規(guī)則是有趣的，如果滿足最小支持度閾值和最小置信度閾值。這些閾值是根據(jù)挖掘需要人為設(shè)定。

關(guān)聯(lián)規(guī)則的數(shù)據(jù)挖掘過程大體的可以分成2個過程：

1）首先從數(shù)據(jù)資料的集合中找出所有相關(guān)的高頻數(shù)據(jù)項目組；

2）接下來對這些高頻數(shù)據(jù)項目組生成相應(yīng)的關(guān)聯(lián)規(guī)則。

3.2 Apriori算法的基本思想

Apriori算法是一種基于數(shù)據(jù)挖掘的布爾關(guān)聯(lián)規(guī)則頻繁項集算法，這種算法具有一定的學(xué)術(shù)界影響力。這種算法首先需要找出所有的與數(shù)據(jù)相關(guān)聯(lián)的頻集，頻集中包含的項集出現(xiàn)的頻率需要和事先定義的最小支持度至少保持一樣。接下來由頻集產(chǎn)生相應(yīng)的數(shù)據(jù)的強(qiáng)關(guān)聯(lián)規(guī)則，這些數(shù)據(jù)的強(qiáng)關(guān)聯(lián)規(guī)則需要滿足最小的可信度和最小的支持度。最后使用一開始找到的頻集，利用頻集產(chǎn)生期望的數(shù)據(jù)規(guī)則，產(chǎn)生的數(shù)據(jù)規(guī)則包含集合的項中所有的數(shù)據(jù)關(guān)聯(lián)規(guī)則，其中每一個數(shù)據(jù)規(guī)則的右部有且只有一項，在Apriori算法中我們使用的是中規(guī)則的相關(guān)概念。

3.3 Apriori算法的不足

由頻繁k-1項集進(jìn)行自連接生成的候選頻繁k項集的數(shù)量是非常巨大的。在驗證候選頻繁k項集的時候需要對整個數(shù)據(jù)庫進(jìn)行掃描，這個掃描的過程是非常耗費時間的。

3.4 Apriori算法的改進(jìn)

Apriori算法為了減少因自身原有的缺陷，而帶來的消極影響，以提高Apriori算法在執(zhí)行方面的效率，針對Apriori算法本身的缺陷，并在Apriori算法的基礎(chǔ)上提出了幾個基于Apriori算法改進(jìn)的算法。在此介紹幾種典型的改進(jìn)的算法:

1）基于散列的優(yōu)化方法

基于散列的優(yōu)化方法的典型算法就是DHP算法。這種算法利用散列表來產(chǎn)生候選集，可以用于壓縮侯選k-項集的集合q（k>-2)的大小。基于散列的優(yōu)化方法算法能夠有效地減少了2維和3維的候選項目集的數(shù)量，是對Apriori算法的直接改進(jìn)。

2）基于事務(wù)壓縮的優(yōu)化方法

AprioriTid和APriorHybrid算法是基于事務(wù)壓縮的優(yōu)化方法的典型算法。這種算法的主旨思想是通過減少不必要的事務(wù)的個數(shù)來達(dá)到減少掃描數(shù)據(jù)庫數(shù)量的目的。

3）基于劃分的優(yōu)化方法

基于劃分的優(yōu)化方法的典型改進(jìn)算法-Partition算法。這種優(yōu)化方法最大的優(yōu)勢就是掃描數(shù)據(jù)庫的次數(shù)較少，只需對原事務(wù)數(shù)據(jù)庫D兩遍掃描。

3.5 FP-growth算法的基本思想

FP-growth算法的基本思想是采用分而治之的方法。這種思想需要首先在對數(shù)據(jù)庫進(jìn)行第一次掃描時導(dǎo)出相應(yīng)的和Apriori算法相同的頻集項的集合與相應(yīng)的頻集項的支持度。

然后可以根據(jù)導(dǎo)出的頻集項的支持度的大小來對頻繁項集進(jìn)行一個大小的排序，利用這種方法可以構(gòu)造一個FP樹，在構(gòu)造FP-growth樹的時候，可以將數(shù)據(jù)庫中的頻集項壓縮到一棵頻繁模式的樹中去，在壓縮的過程中需要保留各頻集項的基本相關(guān)信息，根據(jù)頻集項的FP樹中的關(guān)聯(lián)信息，再將頻繁模式的樹分化成一些條件庫，之后采用不同的數(shù)據(jù)挖掘方法對這些條件庫進(jìn)行相應(yīng)的數(shù)據(jù)挖掘，實行數(shù)據(jù)挖掘的目的是得到生成長度為2的頻集項。

3.6 FP-growth算法的優(yōu)缺點

FP-growth增長算法有著很明顯的優(yōu)點，主要的優(yōu)點是：

1）能夠?qū)⒃瓉淼臄?shù)據(jù)庫能夠有效地壓縮成比較小存儲空間；

2）不會產(chǎn)生候選項集，所以這種FP-growth增長算法在執(zhí)行的效率方面會比其他的算法要高很多；

3）數(shù)據(jù)挖掘的數(shù)據(jù)與要遠(yuǎn)遠(yuǎn)的小于原數(shù)據(jù)庫。

4 結(jié)論

數(shù)據(jù)挖掘可以應(yīng)用在很多行業(yè)，目前主要應(yīng)用在農(nóng)業(yè)、電信、銀行、生物、天體、電力、化工、零售、醫(yī)藥等方面。從表面上看，數(shù)據(jù)挖掘的應(yīng)用范圍是非常的廣泛，但是在實際應(yīng)用當(dāng)中卻沒有達(dá)到很深的程度。根據(jù)2010年度的Gartner報告，數(shù)據(jù)挖掘技術(shù)將會成為未來40年內(nèi)一項最重要的技術(shù)之一。

基于關(guān)聯(lián)規(guī)則的數(shù)據(jù)挖掘技術(shù)的發(fā)展應(yīng)是挖掘工具在先進(jìn)理論指導(dǎo)下的一種改進(jìn)，而就目前的情況來看，數(shù)據(jù)挖掘技術(shù)還有很大的發(fā)展空間。雖然數(shù)據(jù)挖掘是一個過程，但是與此過程相關(guān)聯(lián)的是以前數(shù)據(jù)挖掘之前的結(jié)果和數(shù)據(jù)，那些已獲得的數(shù)據(jù)正是我們想要的，可以不斷的分析和產(chǎn)看，因為如果沒有進(jìn)行相應(yīng)的數(shù)據(jù)挖掘，是不可能得到有價值的數(shù)據(jù)。就實際情況來看，只有那些可以依據(jù)過去經(jīng)驗形成的合理的解釋才是有價值的。

[1]張鳳荔.基于關(guān)聯(lián)規(guī)則的數(shù)據(jù)挖掘算法研究[D].電子科技大學(xué)，2010.

[2]梅俊.數(shù)據(jù)挖掘中關(guān)聯(lián)規(guī)則算法的研究與應(yīng)用[D].安徽工程大學(xué)，2010.

[3]百度百科. http://baike.baidu.com/view/1076817.htm

[4]錢志忠.偏差檢測的相關(guān)研究[J].計算機(jī)工程與應(yīng)用，2007，36(1)：60-63.

[5]范明,劉艷波，尹軍.數(shù)據(jù)挖掘：概念與技術(shù)[M].北京：機(jī)械工業(yè)出版社，2001.

[6]廖波，王天明.新型數(shù)據(jù)挖掘算法[J].計算機(jī)學(xué)報，2003，18(3)：364-368.

[7]譚光明，馮圣中，孫凝暉.一種基于新型的數(shù)據(jù)挖掘算法研究[J].軟件學(xué)報，2006，17(7)：1501-1509.