郝林倩

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

0 引言

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

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

數(shù)據(jù)挖掘是集統(tǒng)計學、數(shù)據(jù)庫、模式識別、高性能計算、專家系統(tǒng)等多種學科交叉的新學科。數(shù)據(jù)采集和數(shù)據(jù)存儲技術(shù)的快速發(fā)展使得數(shù)據(jù)庫中數(shù)據(jù)量飛速增加,數(shù)據(jù)挖掘為決策者及管理者的決策提供了參考。數(shù)據(jù)挖掘應用涉及到民用普通領(lǐng)域,例如商場超市交易數(shù)據(jù)分析、電子商務購物行為分析等,也涉及到天文圖像分析、化學分子數(shù)據(jù)分析、醫(yī)療記錄分析等[2]。數(shù)據(jù)挖掘處理流程包括問題定義、數(shù)據(jù)準備、挖掘算法執(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ù)準備主要包括數(shù)據(jù)提取,數(shù)據(jù)預處理及數(shù)據(jù)轉(zhuǎn)換。數(shù)據(jù)提取即按照挖掘任務需求,從海量數(shù)據(jù)中提取有用的目標數(shù)據(jù)(Target Data)[3]。

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

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

挖掘結(jié)果解析和評估即挖掘任務結(jié)果不一定符合挖掘任務預期,因此選擇數(shù)據(jù)挖掘算法允許存在冗余模式。數(shù)據(jù)挖掘是一個不斷迭代過程,通過結(jié)果解析和評估,往前一個環(huán)節(jié)推導,直接導致選擇有用有價值目標數(shù)據(jù)及適合的數(shù)據(jù)挖掘算法,通過直觀的挖掘結(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)、時序關(guān)聯(lián)等。把所有可能的聯(lián)系或者模式全部抽取出來,然后再估算其重要性和正確性,通過支持度和可信度兩個屬性來定義所抽取的關(guān)聯(liá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ù)項集合,其中Ik(1,2,3…,k)為項,而項的集合為項集。如果包括K數(shù)據(jù)項目集合,稱之為K-項集。每一個事務為一個項集T(Transaction),不同的事務構(gòu)成一個[4]事務集合D,即事務數(shù)據(jù)庫。定義關(guān)聯(lián)規(guī)則4個屬性定義如下:

2.1 支持度(Support)

2.2 可信度(Confidence)

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

2.3 期望可信度(Expected Confidence)

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

2.4 作用度(Lift)

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

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

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ī)則所需頻繁項集基本算法，該算法利用一個層次順序搜索的循環(huán)方法來完成挖掘頻繁項集的工作，即利用k-項集來產(chǎn)生(k+1)-項集。具體操作步驟如下：首先找到頻繁1-項集，記為L1，然后利用L1挖掘L2，即2-頻繁集，依此類推層層挖掘直到無法再找到更多的頻繁集Lk，而其中每挖掘一層k都需要掃描一遍集合數(shù)據(jù)庫。Apriori具有一個重要性質(zhì)，即頻繁集合任意子集都為頻繁集合。所以Apriori算法處理過程描述如下：

第一步：在項集1-項集C1中，找出頻繁項集1-項集L1。

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

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

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

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

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

4 總結(jié)

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