臨床數(shù)據(jù)中挖掘關(guān)聯(lián)規(guī)則算法的選用

《臨床數(shù)據(jù)中挖掘關(guān)聯(lián)規(guī)則算法的選用》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在工程資料-天天文庫。

1、第25卷第1期20M年2月賢南大學(xué)學(xué)報(自然科學(xué)版)JournalofJinanUniversity(NaturalScience)臨床數(shù)據(jù)中挖掘關(guān)聯(lián)規(guī)則算法的選用殷彬，方思行(音南大學(xué)計算機科學(xué)系，廣東廣州510632)【摘要］對典型的挖掘關(guān)聯(lián)規(guī)則的Apriori算法和tP-growth算法進(jìn)行比較分析?然后，結(jié)合臨床數(shù)據(jù)的特點，建議在臨床數(shù)據(jù)關(guān)聯(lián)規(guī)則挖掘中采用FP-growth算法.［關(guān)鍵詞］數(shù)據(jù)挖掘；關(guān)聯(lián)規(guī)則；Apriori算法；FT-growth算法；支持度；稀疏數(shù)據(jù)集；稠密數(shù)據(jù)集［中圖分類號］TP311［文獻(xiàn)標(biāo)識碼］A［文章編號］1000?9965(2004)0—0026

2、?04數(shù)據(jù)挖掘(血tamining)是指從大型數(shù)據(jù)庫中提取潛在的、可理解的、有用的規(guī)律性知識或指導(dǎo)性規(guī)則的處理過程.關(guān)聯(lián)規(guī)則(associationnile)是數(shù)據(jù)挖掘研究中一個巫要方面.挖掘關(guān)聯(lián)規(guī)則的算法非常多，有R.Aprawal等人⑴提岀的Apriori算法、Park等人⑵提出的DHP算法、Brin等人⑶提出的DIC算法、Toivonen等人⑷的抽樣算法J.Han等人廿⑹提出FP-growth算法和H-Mine算法.其中以Apriori算法和FP-growth算法最為著名.面對眾多的算法，為了在臨床數(shù)據(jù)中挖掘出關(guān)聯(lián)規(guī)則，我們應(yīng)該采取哪種算法才能比較高效地進(jìn)行挖掘呢？本文將對典

3、型的Apriori算法和FP-growth算法進(jìn)行比較分析，然后根據(jù)臨床數(shù)據(jù)本身的特點，決定采用何種算法.1基本概念設(shè)/二｛",「2,…，心｝是m個不同項的集合.給定一個事務(wù)數(shù)據(jù)庫。，其中每一個事務(wù)T是/中某一組項的集合，即TQI.每一個事務(wù)都與一個唯一標(biāo)識符TID相聯(lián).假設(shè)？!是一個項集，事務(wù)T包含4當(dāng)且僅當(dāng)ACT.關(guān)聯(lián)規(guī)則是形如A斗B的蘊涵式，其中AU/,BU/,并且4D=0?如果事務(wù)數(shù)據(jù)庫D中有s%的事務(wù)包含4和則稱關(guān)聯(lián)規(guī)則在D中具有支持度(support)s%?如果D中包含4的事務(wù)中有c%同時包含則稱關(guān)聯(lián)規(guī)則A=>B在D中具有置信度(confidence)c%?挖掘關(guān)聯(lián)規(guī)則

4、就是要挖掘出所有同時具有不小于用戶指定的最小支持度(min.sup)和最小置信度(min.conf)的關(guān)聯(lián)規(guī)則⑴.關(guān)聯(lián)規(guī)則挖掘分為兩個子問題：(1)尋找所有支持度不小于最小支持度的項集，即頻繁項集.(2)利用頻繁項集生成所需的關(guān)聯(lián)規(guī)則，根據(jù)最小置信度選取關(guān)聯(lián)規(guī)則.第1個子問題更重要，也更為煩瑣.關(guān)聯(lián)規(guī)則挖掘的主要工作都集中在發(fā)現(xiàn)頻繁項集中.如果一個數(shù)據(jù)集是滿足公式I/I二0(loglDII)的集合，則稱為是稀疏數(shù)據(jù)集，反之則稱［收稿日期】2003-05^21［基金項目］國家自然科學(xué)基金重點資助頂目(9020903)；廣東省'自然科學(xué)基金資助項R(021149)［作者簡介］殷彬(19

5、78-)?男?族士研究生?研究方向：數(shù)撫挖掘與時公數(shù)據(jù)庫.通訊聯(lián)系人：方思行.為稠密數(shù)據(jù)集，其中I/I是事務(wù)的平均長度，IDII是數(shù)據(jù)集中不同項的數(shù)目?例如，當(dāng)數(shù)據(jù)集中有128個不同的項，而事務(wù)的平均長度小于7時，則該數(shù)據(jù)集是稀疏的.2算法比較分析Apriori算法使用的是一種逐層搜索的迭代方法-項集用于探索％+1)-項集.首先找出頻繁1-項集的集合，記為J.然后在兒的基礎(chǔ)上進(jìn)行連接操作，產(chǎn)生候選2■項集的集合,再在候選2~項集的集合中進(jìn)行剪枝操作?產(chǎn)生頻繁2-項集的集合L2.類似地，在L2的基礎(chǔ)上找出L3.如此下去，直到不能找到頻繁k-項集為止.FP-growth算法采取分而治之

6、的策略：在保持項集關(guān)聯(lián)信息的情況下，把數(shù)據(jù)庫壓縮到一棵頻繁模式樹(FP-Tree),它比原始數(shù)據(jù)庫小很多；然后，將壓縮后的數(shù)據(jù)庫按照頻繁項投影,分成一些條件數(shù)據(jù)庫，并分別挖掘每個數(shù)據(jù)庫，這樣就減少了后續(xù)的掃描數(shù)據(jù)庫的時間.它又采取頻繁模式增長的方式，不產(chǎn)生候選項集，這使得它在挖掘的過程中不會產(chǎn)生數(shù)據(jù)庫中沒有的新事務(wù).而Apriori算法則可能產(chǎn)牛大量的候選項集，同時可能需耍巫復(fù)地掃描數(shù)據(jù)庫.下面是用4個數(shù)據(jù)集進(jìn)行實驗的結(jié)果比較67】.其中,Gazelle數(shù)據(jù)集是…個稀疏數(shù)據(jù)集.它是從Gazelle.com獲得的對該網(wǎng)站訪問的數(shù)據(jù)集合(點擊記錄).它包含了59602個事務(wù)，在事務(wù)集中

7、總共有1000個項，每個事務(wù)含的項不超過267項，平均事務(wù)長度為2.5.25I5D10K是一個用合成數(shù)據(jù)產(chǎn)生器產(chǎn)生的稠密數(shù)據(jù)集，包含了10000個事務(wù)，在事務(wù)集中總共有1000個項，每個事務(wù)含的項不超過25項，平均事務(wù)長度是15.BMS-POS數(shù)據(jù)集是一個稀疏數(shù)據(jù)集,它是從一個規(guī)模很大的零售商那里獲得的包含兒年的零售數(shù)據(jù).在這個數(shù)據(jù)集中，一個消費者的購買事務(wù)就是消費者一次購買的商品目錄.它包含515597個事務(wù)，在事務(wù)集中總共有1657個項，最長的事務(wù)的長度為164,