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

金育嬋

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

1 概述

1.1 課題的研究背景

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

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

1.2 研究目的和意義

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

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

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

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

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

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

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

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

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

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

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

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

2.2.4 預(yù)測(cè)分析

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

2.2.5 偏差分析

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

2.2.6 時(shí)序模式

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3.2 Apriori算法的基本思想

Apriori算法是一種基于數(shù)據(jù)挖掘的布爾關(guān)聯(lián)規(guī)則頻繁項(xiàng)集算法，這種算法具有一定的學(xué)術(shù)界影響力。這種算法首先需要找出所有的與數(shù)據(jù)相關(guān)聯(lián)的頻集，頻集中包含的項(xiàng)集出現(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ī)則包含集合的項(xiàng)中所有的數(shù)據(jù)關(guān)聯(lián)規(guī)則，其中每一個(gè)數(shù)據(jù)規(guī)則的右部有且只有一項(xiàng)，在Apriori算法中我們使用的是中規(guī)則的相關(guān)概念。

3.3 Apriori算法的不足

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

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

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

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

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

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

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

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

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

3.5 FP-growth算法的基本思想

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

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

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

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

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

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

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)用范圍是非常的廣泛，但是在實(shí)際應(yīng)用當(dāng)中卻沒有達(dá)到很深的程度。根據(jù)2010年度的Gartner報(bào)告，數(shù)據(jù)挖掘技術(shù)將會(huì)成為未來40年內(nèi)一項(xiàng)最重要的技術(shù)之一。

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

[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]錢志忠.偏差檢測(cè)的相關(guān)研究[J].計(jì)算機(jī)工程與應(yīng)用，2007，36(1)：60-63.

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

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

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