基于圖和矩陣的關(guān)聯(lián)規(guī)則挖掘算法.pdf

1、數(shù)據(jù)庫中的知識發(fā)現(xiàn)（Knowledge Discoveryin Databases，KDD）是利用計算機自動地從海量信息中提取有用的知識，是一種有效利用信息的新方法，目前已成為數(shù)據(jù)庫領域的研究熱點之一。KDD的研究焦點在于數(shù)據(jù)挖掘。社會的發(fā)展進入了網(wǎng)絡信息時代，各種形式的數(shù)據(jù)海量產(chǎn)生，在這些數(shù)據(jù)的背后隱藏著許多重要的信息，如何從這些數(shù)據(jù)中找出某種規(guī)律，發(fā)現(xiàn)有用信息，越來越受到關(guān)注。為了適應信息處理新需求和社會發(fā)展各方面的迫切需要而發(fā)展起

2、來一種新的信息分析技術(shù)，這種技術(shù)稱為數(shù)據(jù)挖掘。數(shù)據(jù)挖掘就是從大量的、不完全的、有噪聲的、模糊的、隨機的實際應用數(shù)據(jù)中，提取隱含在其中的、人們事先不知道的、但又是潛在有用的信息和知識的過程。目前，數(shù)據(jù)挖掘的主要技術(shù)為關(guān)聯(lián)規(guī)則、聚類、粗糙集、神經(jīng)網(wǎng)絡和遺傳算法等方面。 關(guān)聯(lián)規(guī)則是反映一個事務與其他事務之間的相互依存性和關(guān)聯(lián)性，關(guān)聯(lián)規(guī)則在數(shù)據(jù)挖掘領域應用很廣泛。關(guān)聯(lián)規(guī)則是發(fā)現(xiàn)交易數(shù)據(jù)庫中不同商品（項）之間的聯(lián)系，這些規(guī)則找出顧客購買行

3、為模式，如購買了某一商品對購買其他商品的影響．發(fā)現(xiàn)這樣的規(guī)則可以應用于商品貨架設計、貨存安排以及根據(jù)購買模式對用戶進行分類． 最經(jīng)典的關(guān)聯(lián)規(guī)則挖掘算法是Apriori算法。它是由R.Agrawal等人于1994年在AIS算法基礎上提出的改進算法。Apriori算法使用一種稱作“逐層搜索的迭代方法”，核心思想是基于頻集理論的一種遞推方法，目的是從數(shù)據(jù)庫中挖掘出那些支持度和信任度都不低于給定的最小支持度閾值和最小信任度閾值的關(guān)聯(lián)規(guī)則

4、。Apriori算法通常分為兩步：1）基于支持度，產(chǎn)生頻繁項集；2）基于可信度，產(chǎn)生強關(guān)聯(lián)規(guī)則。首先，找出頻繁1項集集合，該集合記為L1L2，L1用于尋找頻繁2項集的集合L2，L2用于尋找L3，如此下去直到不能找到頻繁k項集Lk，找出每個Lk需要掃描數(shù)據(jù)庫一次。 但Apriori算法存在固有的缺點：（1）由頻繁k-1項集進行自連接生成的候選頻繁k項集數(shù)量巨大。（2）在驗證候選頻繁k項集的時候需要對整個數(shù)據(jù)庫進行掃描，非常耗時。