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

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

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

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

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