基于關(guān)聯(lián)規(guī)則的數(shù)據(jù)挖掘算法分析

郝林倩

(福建船政交通職業(yè)學(xué)院 信息工程系,福建 福州 350007)

0 引言

隨著數(shù)據(jù)時(shí)代來臨,人們已不滿足于海量數(shù)據(jù)存儲(chǔ)、查詢和顯示,更關(guān)心海量數(shù)據(jù)背后的信息價(jià)值,目前人們對于數(shù)據(jù)信息掌握遠(yuǎn)遠(yuǎn)跟不上數(shù)據(jù)增長速度。如何在海量數(shù)據(jù)中挖掘有用的信息成為了當(dāng)前關(guān)注的焦點(diǎn),知識發(fā)現(xiàn)、數(shù)據(jù)挖掘等技術(shù)成為了學(xué)術(shù)界研究的熱點(diǎn)。數(shù)據(jù)挖掘技術(shù)就是從海量的、包含噪聲的、不完整的隨機(jī)數(shù)據(jù)中挖掘出事先未知[1]的,但卻存在潛在價(jià)值信息的過程。目前國內(nèi)處于大數(shù)據(jù)大力發(fā)展時(shí)期,為數(shù)據(jù)挖掘提供了良好外部環(huán)境,但目前對于數(shù)據(jù)挖掘,特別關(guān)聯(lián)規(guī)則算法研究論文及成果相對薄弱和單一,所以本文重點(diǎn)對關(guān)聯(lián)規(guī)則Apriori和FP-tree經(jīng)典算法進(jìn)行分析研究,并對兩者性能進(jìn)行比照,提出性能優(yōu)化建議，所以本文對于數(shù)據(jù)挖掘關(guān)聯(lián)規(guī)則探討研究具有重要的意義。

1 數(shù)據(jù)挖掘定義及應(yīng)用

數(shù)據(jù)挖掘是集統(tǒng)計(jì)學(xué)、數(shù)據(jù)庫、模式識別、高性能計(jì)算、專家系統(tǒng)等多種學(xué)科交叉的新學(xué)科。數(shù)據(jù)采集和數(shù)據(jù)存儲(chǔ)技術(shù)的快速發(fā)展使得數(shù)據(jù)庫中數(shù)據(jù)量飛速增加,數(shù)據(jù)挖掘?yàn)闆Q策者及管理者的決策提供了參考。數(shù)據(jù)挖掘應(yīng)用涉及到民用普通領(lǐng)域,例如商場超市交易數(shù)據(jù)分析、電子商務(wù)購物行為分析等,也涉及到天文圖像分析、化學(xué)分子數(shù)據(jù)分析、醫(yī)療記錄分析等[2]。數(shù)據(jù)挖掘處理流程包括問題定義、數(shù)據(jù)準(zhǔn)備、挖掘算法執(zhí)行、結(jié)果解析及評估等環(huán)節(jié)。

問題定義即數(shù)據(jù)挖掘人員與研究領(lǐng)域?qū)＜壹白罱K用戶協(xié)作確定數(shù)據(jù)挖掘要求及范圍(如聚類、關(guān)聯(lián)規(guī)則發(fā)現(xiàn)等),確定最優(yōu)的挖掘算法,為后續(xù)環(huán)節(jié)定下基礎(chǔ)及方向。

數(shù)據(jù)準(zhǔn)備主要包括數(shù)據(jù)提取,數(shù)據(jù)預(yù)處理及數(shù)據(jù)轉(zhuǎn)換。數(shù)據(jù)提取即按照挖掘任務(wù)需求,從海量數(shù)據(jù)中提取有用的目標(biāo)數(shù)據(jù)(Target Data)[3]。

數(shù)據(jù)預(yù)處理對目標(biāo)數(shù)據(jù)進(jìn)行數(shù)據(jù)清洗,包括消除噪聲,剔除重復(fù)數(shù)據(jù),完善缺省數(shù)據(jù)或者數(shù)據(jù)類型轉(zhuǎn)換(一般為離散型數(shù)據(jù)與連續(xù)型數(shù)據(jù)互轉(zhuǎn))。數(shù)據(jù)轉(zhuǎn)換主要對目標(biāo)數(shù)據(jù)進(jìn)行降維處理,從數(shù)據(jù)初始特征中提取目標(biāo)特征,減少不必要的輸入?yún)?shù),提升處理效率。

挖掘算法執(zhí)行即根據(jù)挖掘問題定義的任務(wù)及目的選擇適合的算法,包括聚類、分類、規(guī)則發(fā)現(xiàn)或者序號模式發(fā)現(xiàn)等,在選擇合理的數(shù)據(jù)挖掘算法時(shí)必須依據(jù)數(shù)據(jù)的特征、用戶和系統(tǒng)的任務(wù)要求。不同特點(diǎn)的數(shù)據(jù)適合不同的算法。而用戶的要求可以分為易于理解型結(jié)果和精確預(yù)測型結(jié)果,所以選擇的執(zhí)行算法,根據(jù)實(shí)際情況來決定。

挖掘結(jié)果解析和評估即挖掘任務(wù)結(jié)果不一定符合挖掘任務(wù)預(yù)期,因此選擇數(shù)據(jù)挖掘算法允許存在冗余模式。數(shù)據(jù)挖掘是一個(gè)不斷迭代過程,通過結(jié)果解析和評估,往前一個(gè)環(huán)節(jié)推導(dǎo),直接導(dǎo)致選擇有用有價(jià)值目標(biāo)數(shù)據(jù)及適合的數(shù)據(jù)挖掘算法,通過直觀的挖掘結(jié)果,評估出有效的挖掘任務(wù),從而得到有價(jià)值的挖掘算法。

數(shù)據(jù)挖掘關(guān)聯(lián)規(guī)則算法,通過關(guān)聯(lián)分析發(fā)現(xiàn)關(guān)聯(lián)規(guī)則,即發(fā)現(xiàn)數(shù)據(jù)與數(shù)據(jù)之間隱藏的關(guān)聯(lián)信息,包括數(shù)量關(guān)聯(lián)、因果關(guān)聯(lián)、時(shí)序關(guān)聯(lián)等。把所有可能的聯(lián)系或者模式全部抽取出來,然后再估算其重要性和正確性,通過支持度和可信度兩個(gè)屬性來定義所抽取的關(guān)聯(lián)信息的重要性和準(zhǔn)確性。

2 關(guān)聯(lián)規(guī)則相關(guān)概念及定義

關(guān)聯(lián)規(guī)則為數(shù)據(jù)挖掘領(lǐng)域重要研究分支,即研究數(shù)據(jù)間關(guān)系,如何提升數(shù)據(jù)挖掘效率,在海量數(shù)據(jù)信息中尋找到有用的數(shù)據(jù)信息。關(guān)聯(lián)規(guī)則如下表示,X?Y,其中X?I,Y?I,且X∩Y≠φ。設(shè)I={I1,I2,I3,I4…Im}為所有數(shù)據(jù)項(xiàng)集合,其中Ik(1,2,3…,k)為項(xiàng),而項(xiàng)的集合為項(xiàng)集。如果包括K數(shù)據(jù)項(xiàng)目集合,稱之為K-項(xiàng)集。每一個(gè)事務(wù)為一個(gè)項(xiàng)集T(Transaction),不同的事務(wù)構(gòu)成一個(gè)[4]事務(wù)集合D,即事務(wù)數(shù)據(jù)庫。定義關(guān)聯(lián)規(guī)則4個(gè)屬性定義如下:

2.1 支持度(Support)

2.2 可信度(Confidence)

假設(shè)在事務(wù)集D中支持X項(xiàng)集的事務(wù)中,同時(shí)也k%的概率支持事務(wù)Y,則稱之k為X?Y的可信度。按照公式表示如下:

2.3 期望可信度(Expected Confidence)

假設(shè)集合D中存在k%支持集合Y,則k%為支持X?Y的期望可信度,按照公式表示X?Y的期望可信度如下:

2.4 作用度(Lift)

所謂作用度為期望可信度與可信度之間的比值結(jié)果,即支持集合X對支持集合Y存在多大的影響概率,按照數(shù)學(xué)公式表示X?Y作用度如下:

在關(guān)聯(lián)規(guī)則如上4個(gè)衡量標(biāo)準(zhǔn)中,可信度反應(yīng)關(guān)聯(lián)規(guī)則的準(zhǔn)確性,而支持度反應(yīng)關(guān)聯(lián)規(guī)則的重要性。期望可信度反應(yīng)其中在沒有X項(xiàng)集影響下[5],Y項(xiàng)集的可信度情況。而作用度反應(yīng)項(xiàng)集X對項(xiàng)集Y的影響度大小。如果作用度越大,說明項(xiàng)集X對于項(xiàng)集Y影響力越大,一般情況作用度大于1,說明項(xiàng)集X對于項(xiàng)集Y具有正面作用,從而說明項(xiàng)集X和項(xiàng)集Y相關(guān)性更強(qiáng)。

3 經(jīng)典關(guān)聯(lián)規(guī)則算法Apriori研究及優(yōu)化

目前關(guān)聯(lián)規(guī)則經(jīng)典算法包括Apriori和FP-tree算法。Apriori算法為布爾關(guān)聯(lián)規(guī)則所需頻繁項(xiàng)集基本算法，該算法利用一個(gè)層次順序搜索的循環(huán)方法來完成挖掘頻繁項(xiàng)集的工作，即利用k-項(xiàng)集來產(chǎn)生(k+1)-項(xiàng)集。具體操作步驟如下：首先找到頻繁1-項(xiàng)集，記為L1，然后利用L1挖掘L2，即2-頻繁集，依此類推層層挖掘直到無法再找到更多的頻繁集Lk，而其中每挖掘一層k都需要掃描一遍集合數(shù)據(jù)庫。Apriori具有一個(gè)重要性質(zhì)，即頻繁集合任意子集都為頻繁集合。所以Apriori算法處理過程描述如下：

第一步：在項(xiàng)集1-項(xiàng)集C1中，找出頻繁項(xiàng)集1-項(xiàng)集L1。

第二步：在第一步基礎(chǔ)上，利用Lk-1項(xiàng)集連接產(chǎn)生候選集合Ck。公式表示如下：

l1⊕l2={l1[1],l2[2],……,l1[k-1],l2[k-1]},由Lk-1中可連接的項(xiàng)集所連接的K-項(xiàng)集,即為Ck。

第三步:刪除Ck中非頻繁的子項(xiàng)集的候選集合[6]。

第四步:掃描整體數(shù)據(jù)庫,并統(tǒng)計(jì)候選集合計(jì)數(shù),從而得出最終的項(xiàng)集Ck。根據(jù)Apriori算法的偽代碼實(shí)現(xiàn)通過層層挖掘找出頻繁項(xiàng)集Lk,實(shí)現(xiàn)輸入?yún)?shù)包括事務(wù)數(shù)據(jù)庫D及最小支持度min-sup,代碼輸出結(jié)果頻繁項(xiàng)集L[7]。

L1=find_frequent_1_itset(D);

for(k=2;Lk-1≠φ;k++){

Ck=apriori_gen(Lk-1,min _sup);

for eachT∈D{

CT=subset(Ck,T);

for eachc∈CTc.count++;

}

}

Lk={c∈Ck|c.count≥min _sup};

returnL=UkLk;

else returnFALSE

for eachl1∈Lk-1

for eachl2∈Lk-1

f(l1[1]=l2[1])&&(l1[2]=l2[2]&&…&&(l1[k-2]=l2[k-2])&&l1[k-1]=l2[k-1])

{

c=l1⊕l2

fhas_infrequent_itemset(c,Lk-1)

deletec;

elseCk=Ck∪{c};

}

returenCk;

procedure has_infrequent_subset(c,Lk-1);

for each(k-1)subsetsofc

fs?Lk-1return TRUE

else return FALSE

利用如上偽代碼獲取頻繁項(xiàng)集所有的相關(guān)關(guān)聯(lián)規(guī)則的子集合Ck。此算法利用數(shù)據(jù)特質(zhì)任何頻繁項(xiàng)集的子集都是頻繁集合，反向定理若集合存在非頻繁集項(xiàng)，則包含此數(shù)據(jù)項(xiàng)的超集合都不是頻繁集合，從而優(yōu)化Apriori算法的查找效率，在進(jìn)行層層挖掘任務(wù)中剔除非頻繁集合項(xiàng)，根據(jù)如上偽代碼完成Apriori算法優(yōu)化[8]。

4 總結(jié)

本文著重分析了數(shù)據(jù)挖掘技術(shù)及其關(guān)聯(lián)規(guī)則模式下的Apriori算法,并研究了基于算法的頻繁集合特質(zhì),在進(jìn)行層層挖掘過程中剔除非頻繁集合項(xiàng)目,從而提升了Apriori算法挖掘效率,繼而再提升挖掘功效。