關(guān)聯(lián)規(guī)則數(shù)據(jù)挖掘算法淺析.doc

關(guān)聯(lián)規(guī)則數(shù)據(jù)挖掘算法淺析2009年08月24日 星期一 03:23文章編號(hào)：（）190206-03 收稿日期：摘 要：簡(jiǎn)要介紹了關(guān)聯(lián)規(guī)則的概念及其基本思想，重點(diǎn)分析和討論了兩個(gè)挖掘關(guān)聯(lián)規(guī)則的經(jīng)典算法，即算法和分段算法。關(guān)鍵詞：關(guān)聯(lián)規(guī)則；數(shù)據(jù)挖掘；頻繁項(xiàng)集中圖分類號(hào)：TP274 文獻(xiàn)標(biāo)識(shí)碼：隨著現(xiàn)代科學(xué)技術(shù)和數(shù)據(jù)庫(kù)技術(shù)的迅速發(fā)展，人們積累的數(shù)據(jù)越來(lái)越多，激增的數(shù)據(jù)背后隱藏著許多重要的信息，人們希望能夠?qū)ζ溥M(jìn)行更高層次的分析，以便更好地利用這些數(shù)據(jù)。目前的數(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)的一門技術(shù)。所謂數(shù)據(jù)挖掘（ ，簡(jiǎn)稱）是從大量數(shù)據(jù)中鑒別出有效模式（）的非平凡過(guò)程。該模式是新的，可能有用的和最終可理解的，又可稱為數(shù)據(jù)采掘。的定義還有一些不同的表達(dá)形式，但其本質(zhì)都是一樣的，即從數(shù)據(jù)庫(kù)中提出隱含的、高水平的模式，其目的是為數(shù)據(jù)庫(kù)理解與應(yīng)用提供自動(dòng)化、智能化的手段。關(guān)聯(lián)規(guī)則是數(shù)據(jù)挖掘的一個(gè)重要課題，目前已受到越來(lái)越多研究者的關(guān)注。 關(guān)聯(lián)規(guī)則及其基本思想關(guān)聯(lián)規(guī)則是數(shù)據(jù)挖掘過(guò)程中所能挖掘的一類重要的模式或知識(shí)，可以用來(lái)描述事物之間在特定條件下存在的某種強(qiáng)度的聯(lián)系。例如，在購(gòu)買鐵錘的顧客當(dāng)中，有的人同時(shí)購(gòu)買了鐵釘。這些關(guān)聯(lián)規(guī)則很有價(jià)值，商場(chǎng)管理人員可以根據(jù)這些規(guī)則更好地進(jìn)行規(guī)劃，如把鐵錘和鐵釘這樣的商品擺放在一起，能夠促進(jìn)銷售。關(guān)聯(lián)規(guī)則的基本思想：一是找到所有支持度大于最小支持度的頻繁項(xiàng)集，即頻集。二是使用第一步找到的頻集產(chǎn)生期望的規(guī)則。其核心方法是基于頻集理論的遞推方法。 挖掘關(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è)步驟。（）求出支持度項(xiàng)集的集合（ ），即找出目標(biāo)數(shù)據(jù)庫(kù)中包含的所有頻度項(xiàng)集。（）使用各頻度項(xiàng)集生成相應(yīng)的強(qiáng)關(guān)聯(lián)規(guī)則。不難看出，在上述兩步中，第二步的工作是比較簡(jiǎn)單直接的。具體來(lái)說(shuō)，若已知所有頻度項(xiàng)集的集合為，為中的任一頻度項(xiàng)集，設(shè)項(xiàng)集真包含于，測(cè)試（）是否大于設(shè)定的最小置信度門限，若是，則規(guī)則是強(qiáng)關(guān)聯(lián)規(guī)則。按此方法即能將中所能構(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è)的所有子集（若中包含個(gè)項(xiàng)，則共有個(gè)子集）。顯然，這種指數(shù)級(jí)數(shù)數(shù)據(jù)檢測(cè)方法是不可行的，除非的值很小。支持度和置信度是描述關(guān)聯(lián)規(guī)則的兩個(gè)重要概念，前者用于衡量關(guān)聯(lián)規(guī)則在整個(gè)數(shù)據(jù)集中的統(tǒng)計(jì)重要性，后者用于衡量關(guān)聯(lián)規(guī)則的可信程度。支持度和置信度均高的關(guān)聯(lián)規(guī)則才是有用的關(guān)聯(lián)規(guī)則。 挖掘關(guān)聯(lián)規(guī)則的經(jīng)典算法 算法算法基于這樣的一個(gè)原則：如果某一項(xiàng)不是頻度集，那么它的所有超集也都不可能是頻度集。反過(guò)來(lái)說(shuō)，就是任一頻度集的所有子集一定都是頻度集。算法采用逐維擴(kuò)展（ ）的方法，從求維頻度集的集合開始，依次生成維頻度集的集合、維頻度集的集合，直到所有維的頻度項(xiàng)集都生成為止。具體算法如下：輸入：，的值，目標(biāo)數(shù)據(jù)庫(kù)，的大小。輸出：上的所有頻度項(xiàng)集。 算法流程： （） /算法中的表示維的所有頻度項(xiàng)集組成的集合 / 表示維的所有候選項(xiàng)集組成的集合 （；（）；） （）；/利用（）生成 （K，）；/找出中包含于的所有項(xiàng)集 ； / 算法首先計(jì)算單元素項(xiàng)集的支持度，生成所有維頻度項(xiàng)集構(gòu)成的集合，然后，利用構(gòu)造維候選項(xiàng)集的集合，再去掃描數(shù)據(jù)庫(kù)，并根據(jù)設(shè)定的最小支持度門限值篩選出維頻度集的集合，之后，按照類似的方法，在維頻度集的集合基礎(chǔ)上構(gòu)造維候選項(xiàng)集的聚合，再去掃描數(shù)據(jù)庫(kù)，生成維頻度集的集合，直到再也構(gòu)造不出任何候選項(xiàng)集為止。這種生成的所有維的頻度項(xiàng)集即是所求的最終結(jié)果。算法中根據(jù)已求出的維頻度集構(gòu)造維候選項(xiàng)集的原則是下面的等式：k且的任一維子集都包含于集合k。在實(shí)際構(gòu)造候選項(xiàng)集的時(shí)候（算法中的（），可使用下述方法：先求出kkk，k，顯然，k包含k。然后，在k，的基礎(chǔ)上根據(jù)式中k的條件構(gòu)造k。（k，）的功能是篩選出k中所有包含于當(dāng)前記錄的項(xiàng)集。該算法針對(duì)每一維度集都要掃描數(shù)據(jù)庫(kù)一次。假如頻度集的最大維數(shù)是，則算法需要掃描數(shù)據(jù)庫(kù)或次。由此我們可看出，該算法的效率與目標(biāo)數(shù)據(jù)庫(kù)的數(shù)據(jù)特征密切相關(guān)。這種挖掘關(guān)聯(lián)規(guī)則算法的特點(diǎn)，即都需要對(duì)整個(gè)數(shù)據(jù)庫(kù)進(jìn)行多次掃描，然而，當(dāng)數(shù)據(jù)庫(kù)的容量很大時(shí)，多次掃描數(shù)據(jù)庫(kù)所需的磁盤/開銷是非常驚人的。上述算法在數(shù)據(jù)庫(kù)不太大時(shí)的效率還行，但在數(shù)據(jù)庫(kù)比較大時(shí)卻較難取得令人滿意的挖掘效率。這種算法缺乏必要的人機(jī)交互，是將所有可能的關(guān)聯(lián)規(guī)則全挖掘出來(lái)，然而，這里面有用的或用戶感興趣的規(guī)則也許只占很小部分，故冗余規(guī)則的挖掘降低了挖掘效率。這兩個(gè)問(wèn)題可通過(guò)下面討論的改進(jìn)算法（分段算法）來(lái)有效解決。 分段算法通過(guò)前面對(duì)基本算法的討論，可以看到一般的挖掘關(guān)聯(lián)規(guī)則的算法都需要對(duì)整個(gè)數(shù)據(jù)庫(kù)進(jìn)行多次掃描，對(duì)大型數(shù)據(jù)庫(kù)來(lái)說(shuō)，算法的/開銷較大。因而，/開銷問(wèn)題常常成為挖掘算法效率提高的一個(gè)瓶頸。不過(guò)，若能有效地減少數(shù)據(jù)庫(kù)的掃描次數(shù)，則能較好地解決該問(wèn)題。在關(guān)聯(lián)規(guī)則的挖掘中融入分段思想就是一個(gè)比較好的解決方法。下面詳細(xì)討論該方法。 關(guān)聯(lián)規(guī)則挖掘中的分段思想采用分段（）的思想挖掘關(guān)聯(lián)規(guī)則，只需掃描數(shù)據(jù)庫(kù)兩次。該思想是將原來(lái)很大的數(shù)據(jù)庫(kù)分成若干小的、適宜于內(nèi)存中處理的子數(shù)據(jù)庫(kù)，然后按常規(guī)算法（如算法）挖掘出各個(gè)子數(shù)據(jù)庫(kù)上局部支持度集（因?yàn)楦鞣侄巫銐蛐?，挖掘過(guò)程中的所有操作都在內(nèi)存中進(jìn)行，故各分段只需讀取一次），最后把各個(gè)子數(shù)據(jù)庫(kù)上的挖掘結(jié)果歸并，再次掃描數(shù)據(jù)庫(kù)，篩選出最終的關(guān)聯(lián)規(guī)則集。如下所示的算法即是該思想的體現(xiàn)。算法輸入：目標(biāo)數(shù)據(jù)庫(kù)，的大小，分段數(shù)，最小支持度門限。算法輸出：所有支持度集的集合。 ； / 的個(gè)分段； （） L（） ，L / / 包含于 / ； （） 該算法的執(zhí)行大體分兩個(gè)大的階段：第一階段（行），將大的目標(biāo)數(shù)據(jù)庫(kù)邏輯上分成個(gè)互不相交的分段，對(duì)每一分段進(jìn)行局部挖掘（）的過(guò)程可采用前面介紹的任一挖掘關(guān)聯(lián)規(guī)則的算法進(jìn)行），然后將每個(gè)分段上挖掘的結(jié)果，即各個(gè)段上的支持度集的集合（）進(jìn)行合并，生成一個(gè)全局候選項(xiàng)集的集合（）。第二步（行），再次掃描全局?jǐn)?shù)據(jù)庫(kù)，篩選出全局?jǐn)?shù)據(jù)庫(kù)上的支持度集的集合（）。由于分段算法只需掃描數(shù)據(jù)庫(kù)兩次，與前面討論的幾種挖掘關(guān)聯(lián)規(guī)則的算法相比大大減少了磁盤的/的開銷，其性能的優(yōu)越是無(wú)可非議的。分段思想之所以能用于挖掘關(guān)聯(lián)規(guī)則是基于這樣一個(gè)論斷：全局?jǐn)?shù)據(jù)庫(kù)的任一支持度集應(yīng)至少出現(xiàn)一個(gè)局部數(shù)據(jù)庫(kù)的支持度集的集合。 分段算法的性能分析為了更清楚地看到分段算法在處理大數(shù)據(jù)庫(kù)上的優(yōu)越性，下面用一組實(shí)驗(yàn)數(shù)據(jù)來(lái)說(shuō)明分段算法與算法的性能比較。實(shí)驗(yàn)的硬件條件： 的P ， 內(nèi)存；目標(biāo)數(shù)據(jù)取自于數(shù)據(jù)表，表長(zhǎng) 個(gè)元組，包含個(gè)屬性。通過(guò)實(shí)驗(yàn)結(jié)果，可以發(fā)現(xiàn)，分段算法能夠獲得穩(wěn)定的較佳性能。不過(guò)，我們還應(yīng)該看到，在支持度門限較大時(shí)，還是算法的性能要好一些。 分段大小的選取由上面的討論不難看出，分段算法的效率確實(shí)較高，但在具體實(shí)現(xiàn)時(shí)卻存在一個(gè)難點(diǎn)，即如何選取合適的分段大小。一般來(lái)說(shuō)，為了算法的效率最優(yōu)，對(duì)每個(gè)分段的處理最好都在主存中進(jìn)行。所有分段大小的選取就要基于這個(gè)原則，結(jié)合具體的實(shí)現(xiàn)環(huán)境，選擇合適的分段大小，使數(shù)據(jù)閃入閃出的操作最少。如果目標(biāo)數(shù)據(jù)庫(kù)較小，只需將其作為一個(gè)單獨(dú)的分段來(lái)處理即可；若目標(biāo)數(shù)據(jù)庫(kù)較大，可采用試探法（）來(lái)解決分段大小選取的問(wèn)題，即首先根據(jù)實(shí)際系統(tǒng)的可用容量估算一個(gè)段的大小，然后再按照實(shí)際運(yùn)行使閃入閃出的次數(shù)以及主存的利用率來(lái)動(dòng)態(tài)調(diào)整分段的大小，直至獲得一個(gè)最合適的分段大小。這樣，以后各分段的大小即按此選取。使用這種方法，前面若干段上的挖掘也許并不能獲得最佳效率，但后面按最佳分段大小選取的段卻能獲得較高的挖掘效率。 分段算法的局限及改進(jìn)由前面的討論我們可看到，使用分段算法挖掘關(guān)聯(lián)規(guī)則可獲得較好的性能。不過(guò)，這只是就某些情況而言，其性能的好壞其實(shí)是與目標(biāo)數(shù)據(jù)庫(kù)中數(shù)據(jù)分布的情況密切相關(guān)的。當(dāng)目標(biāo)數(shù)據(jù)庫(kù)中的數(shù)據(jù)分布比較均勻時(shí)，上述算法確實(shí)能獲得較好的性能，但當(dāng)目標(biāo)數(shù)據(jù)庫(kù)中的數(shù)據(jù)分布比較凌亂時(shí)，上述算法的性能卻要大打折扣。究其原因，是因?yàn)樯鲜鏊惴ú捎玫氖沁B續(xù)分段，當(dāng)數(shù)據(jù)分布不規(guī)則時(shí)，各分段上挖掘出的結(jié)果集差異性會(huì)很大，從而造成太多冗余項(xiàng)集的檢測(cè)，使算法性能下降。比如，目標(biāo)數(shù)據(jù)庫(kù)的某些屬性在某個(gè)分段上出現(xiàn)的頻率很高，由這些屬性構(gòu)成的項(xiàng)集很可能就是該分段上的支持度集。然而，這些屬性在其他分段上出現(xiàn)的頻率卻很低，也就是說(shuō)，由這些屬性構(gòu)成的項(xiàng)集在那些段上可能就是非支持度集，綜合起來(lái)，這些項(xiàng)集在全局?jǐn)?shù)據(jù)庫(kù)上很可能也是非支持度集。那么，這些項(xiàng)集顯然就是冗余項(xiàng)集了。當(dāng)數(shù)據(jù)分布不均時(shí)，這些冗余項(xiàng)集產(chǎn)生的概率還是很大的。那么如何有效減少類似的冗余項(xiàng)集呢？一種較好的策略是隨機(jī)采樣分段，即每個(gè)段中的元組并非來(lái)自于目標(biāo)數(shù)據(jù)庫(kù)中的連續(xù)的元組，而是從目標(biāo)數(shù)據(jù)庫(kù)中隨機(jī)采樣而得。當(dāng)然，所謂的“隨機(jī)”只是相對(duì)的，必須保證滿足條件：，且。這樣，可以大大減少因數(shù)據(jù)分布不均帶來(lái)的數(shù)據(jù)冗余增長(zhǎng)，從而使分段算法的優(yōu)越性能得以穩(wěn)定發(fā)揮。 結(jié)論數(shù)據(jù)挖掘技術(shù)，由于其誘人的實(shí)用前景，引起了眾多研究者的濃厚興趣。目前，國(guó)外有關(guān)數(shù)據(jù)挖掘技術(shù)的研究正方興未艾，而國(guó)內(nèi)該領(lǐng)域的研究也正在崛起。本文對(duì)數(shù)據(jù)挖掘技術(shù)中的一個(gè)重要分子關(guān)聯(lián)規(guī)則作了比較深入的研究，側(cè)重于分析挖掘規(guī)則的算法。算法需多次掃描數(shù)據(jù)庫(kù)，使得算法的效率在數(shù)據(jù)庫(kù)比較大時(shí)受到很大的制約。不過(guò)，算法在目標(biāo)數(shù)據(jù)庫(kù)不是很大時(shí)仍不失為一個(gè)好的挖掘關(guān)聯(lián)規(guī)則算法。分段算法在算法的基礎(chǔ)上，先將目標(biāo)數(shù)據(jù)庫(kù)分而挖掘之，然后再根據(jù)各部分的挖掘結(jié)果整體校驗(yàn)篩選出最后的結(jié)果。它只需掃描目標(biāo)數(shù)據(jù)庫(kù)兩次。該算法通