資源描述：
《關(guān)聯(lián)規(guī)則數(shù)據(jù)挖掘算法淺析》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在學(xué)術(shù)論文-天天文庫(kù)。
1、關(guān)聯(lián)規(guī)則數(shù)據(jù)挖掘算法淺析2009年08月24日星期一03:23IT168.COM旗下網(wǎng)站文章編號(hào)：1005-6033（2006）19-0206-03收稿F1期：2006-08-16摘要：簡(jiǎn)要介紹了關(guān)聯(lián)規(guī)則的概念及其基本思想，重點(diǎn)分析和討論了兩個(gè)挖掘關(guān)聯(lián)規(guī)則的經(jīng)典算法，即Apriori算法和分段算法。關(guān)鍵詞：關(guān)聯(lián)規(guī)則；數(shù)據(jù)挖掘；頻繁項(xiàng)集中圖分類號(hào)：TP274文獻(xiàn)標(biāo)識(shí)碼：A隨著現(xiàn)代科學(xué)技術(shù)和數(shù)據(jù)庫(kù)技術(shù)的迅速發(fā)展，人們積累的數(shù)據(jù)越來(lái)越多，激增的數(shù)據(jù)背后隱藏著許多重要的信息，人們希望能夠?qū)τ⑦M(jìn)行更高層次的分析，以便更好地利用這些數(shù)據(jù)
2、。目前的數(shù)據(jù)庫(kù)系統(tǒng)可以高效地實(shí)現(xiàn)數(shù)據(jù)的錄入、查詢、統(tǒng)計(jì)等功能，但無(wú)法發(fā)現(xiàn)數(shù)據(jù)屮存在的關(guān)系和規(guī)則，無(wú)法根據(jù)現(xiàn)有的數(shù)據(jù)預(yù)測(cè)未來(lái)的發(fā)展趨勢(shì)。為此，人們需要冇新的、更為冇效的手段對(duì)各種信息資源進(jìn)行挖掘以發(fā)揮其應(yīng)用潛能。數(shù)據(jù)挖掘正是在這樣的應(yīng)用需求背景下產(chǎn)生并迅速發(fā)展起來(lái)的一門(mén)技術(shù)。所謂數(shù)據(jù)挖掘（DataMining，簡(jiǎn)稱DM）是從大量數(shù)據(jù)中鑒別出有效模式（Pattern）的非平凡過(guò)程。該模式是新的，可能有用的和最終可理解的，又可稱為數(shù)據(jù)采掘。DM的定義還冇一些不同的表達(dá)形式，但其本質(zhì)都是一樣的，即從數(shù)據(jù)庫(kù)中提出隱含的、高水平的模式，
3、其目的是為數(shù)據(jù)庫(kù)理解與應(yīng)用捉供自動(dòng)化、智能化的手段。關(guān)聯(lián)規(guī)則是數(shù)據(jù)挖掘的一個(gè)重要課題，目前已受到越來(lái)越多研究者的關(guān)注。1關(guān)聯(lián)規(guī)則及其基木思想關(guān)聯(lián)規(guī)則是數(shù)據(jù)挖掘過(guò)程中所能挖掘的一類重要的模式或知識(shí)，可以用來(lái)描述事物Z間在特定條件卜?存在的某種強(qiáng)度的聯(lián)系。例如，在購(gòu)買(mǎi)鐵錘的顧客當(dāng)中，有70%的人同時(shí)購(gòu)買(mǎi)了鐵釘。這些關(guān)聯(lián)規(guī)則很冇價(jià)值，商場(chǎng)管理人員可以根據(jù)這些規(guī)則更好地進(jìn)行規(guī)劃，如把鐵錘和鐵釘這樣的商品擺放在一起，能夠促進(jìn)銷售。關(guān)聯(lián)規(guī)則的基木思想:一是找到所有支持度大于最小支持度的頻繁項(xiàng)集，即頻集。二是使用第一步找到的頻集產(chǎn)生期望的
4、規(guī)則。其核心方法是基于頻集理論的遞推方法。2挖掘關(guān)聯(lián)規(guī)則的基本算法挖掘關(guān)聯(lián)規(guī)則，就是在大型數(shù)據(jù)庫(kù)中發(fā)現(xiàn)所有可能有用的或者用戶感興趣的強(qiáng)關(guān)聯(lián)規(guī)則的過(guò)程。按照它的基木思想，挖掘關(guān)聯(lián)規(guī)則一般可以分為以下兩個(gè)步驟。（1）求出支持度項(xiàng)集的集合（FrequentSets）,即找出目標(biāo)數(shù)據(jù)庫(kù)中包含的所有頻度項(xiàng)集。（2）使用各頻度項(xiàng)集生成相應(yīng)的強(qiáng)關(guān)聯(lián)規(guī)則。不難看出，在上述兩步中，第二步的工作是比較簡(jiǎn)單直接的。具體來(lái)說(shuō)，若已知所有頻度項(xiàng)集的集合為F,X為F屮的任一頻度項(xiàng)集，設(shè)項(xiàng)集Y真包含于X,測(cè)試C（Y>X-Y）是否大于設(shè)定的最小置信度門(mén)限，
5、若是，則規(guī)則Y>X-Y是強(qiáng)關(guān)聯(lián)規(guī)則。按此方法即能將F中所能構(gòu)造的所有強(qiáng)關(guān)聯(lián)規(guī)則找出來(lái)。因此，挖掘關(guān)聯(lián)規(guī)則算法的主要工作應(yīng)集屮在第一步，即設(shè)法高效地發(fā)現(xiàn)目標(biāo)數(shù)據(jù)庫(kù)屮包含的所有頻度項(xiàng)集。為了測(cè)試某些特定項(xiàng)集是否是頻度項(xiàng)集，不可避免地需要掃描整個(gè)數(shù)據(jù)庫(kù)。如果目標(biāo)數(shù)據(jù)庫(kù)很大，應(yīng)設(shè)法盡可能減少掃描數(shù)據(jù)庫(kù)的次數(shù)?？紤]一種極端的情況：只需掃描數(shù)據(jù)庫(kù)一次，但要檢測(cè)R的所有子集(若R中包含m個(gè)項(xiàng)，則共冇2m個(gè)子集)。顯然，這種指數(shù)級(jí)數(shù)數(shù)據(jù)檢測(cè)方法是不可行的，除非m的值很小。支持度和置信度是描述關(guān)聯(lián)規(guī)則的兩個(gè)重要概念，前者用于衡量關(guān)聯(lián)規(guī)則在整個(gè)
6、數(shù)據(jù)集中的統(tǒng)計(jì)重要性，后者用于衡量關(guān)聯(lián)規(guī)則的可信程度。支持度和置信度均高的關(guān)聯(lián)規(guī)則才是有用的關(guān)聯(lián)規(guī)則。3挖掘關(guān)聯(lián)規(guī)則的經(jīng)典算法3.1Apriori算法Apriori算法基于這樣的一個(gè)原則：如果某一項(xiàng)不是頻度集，那么它的所冇超集也都不口J能是頻度集。反過(guò)來(lái)說(shuō)，就是任一頻度集的所冇子集一定都是頻度集。算法采用逐維擴(kuò)展(Level—wiseExtention)的方法，從求1一維頻度集的集合開(kāi)始，依次生成2—維頻度集的集合、3—維頻度集的集合……，直到所有維的頻度項(xiàng)集都生成為止。具體算法如下：輸入：6屮的值，目標(biāo)數(shù)據(jù)庫(kù)D,D的大小d
7、bsize。輸出：D上的所有頻度項(xiàng)集。算法流程：PROCEDUREAprioriA1g()Begin〃算法中的LK表示k—維的所冇頻度項(xiàng)集組成的集合//CK表示k—維的所有候選項(xiàng)集組成的集合Ll={Frequent1—ItemSets}For(k=2；1(k—1)<>0；k++)dobeginCK=Apriori_gen(L(k—1))；〃利用L(k一1)生成CKFora11transactionstEDdobeginCt=subset(CK,t)；〃找illCK屮包含于t的所有項(xiàng)集Fora11candidatesetscW
8、Ctdoc?count++；endLK={cWCkc.count/bdsize>=o}EndAnswer=UkLkEnd算法首先計(jì)算單元素項(xiàng)集的支持度，生成所有1—維頻度項(xiàng)集構(gòu)成的集合L1,然后，利用L1構(gòu)造2—維候選項(xiàng)集的集合C2,再去掃描數(shù)據(jù)庫(kù)，并根據(jù)設(shè)定的最小支持度門(mén)限值篩選出2—維
