一種基于事務規則樹的高效關聯規則挖掘算法

摘要：提出了基于事務規則樹改進的關聯規則快速挖掘算法——FG算法。該算法不需要查找頻繁項集，可直接求出所有無冗余的關聯規則；將FG算法與其他算法進行實驗比較，結果表明，FG算法在效率上優于其他算法，是有效的、可行的關聯規則挖掘算法。

關鍵詞：數據挖掘；關聯規則；支持度；事務規則樹

中圖分類號：TP311文獻標志碼：A

文章編號：1001－3695(2007)05－0083－04

0引言

數據挖掘(Data Mining)就是從大量的、不完全的、有噪聲的、模糊的、隨機的實際應用數據中，提取隱含在其中人們事先不知道的、但又是潛在有用的信息和知識的過程。提取的知識可以用來在數據庫記錄中識別聯系，為被挖掘的數據庫產生摘要，形成預報和分類模型。這些知識最終將提供給決策支持系統。

關聯規則（Association Rules）是一個重要的數據挖掘研究課題，它反映了大量數據中項目集之間有趣的關聯或相關聯系。目前已提出了很多關聯規則挖掘算法。其中以Agrawal等人[1]提出的Apriori算法一直作為經典的關聯規則挖掘算法被引用。其后的一些數據挖掘算法[2，3]大多是建立在Apriori算法基礎上的。

2．1算法思想

FG算法是用建立事務規則模型來說明問題的。將事務規則樹合并為規則鏈，在規則鏈上運用FG算法來實現事務規則樹模型的構造，構造完成后形成的規則已經去掉了大部分的冗余規則；然后FG算法運用過濾技術再去掉冗余規則，挖掘出所有無冗余的關聯規則。FG不需要查找頻繁項，直接找出關聯規則，方法比較靈活。

事務規則樹的構造是FG算法的主要過程，可以利用FG算法來查找事務數據庫中所有無冗余的關聯規則。但在最小支持度min_sup和最小置信度min_confi一定的情況下，此時的事務規則樹的構造是基于滿足支持度的節點集合上的。因此，FG算法首先要在項目全集中找出所有滿足支持度的節點，即頻繁1－項集。將這些滿足支持度的節點按照對應的項目順序排列，形成一個有序的節點集合。這是實現FG算法的基本前提。FG算法利用規則鏈實現了構造事務規則樹的過程。構造完成后，通過事務規則樹的所有路徑進行關聯規則的挖掘。

在規則鏈上構造事務規則樹模型的FG算法完成后，所提取到的就是所有的項目序列。這些項目序列對應事務規則樹模型的所有路徑，再對項目序列進行計算，就可求出所有的關聯規則。

2．2算法過程及描述

3算法的性能測試與分析

為了驗證FG算法的性能，選取性能較好的最大頻繁模式挖掘算法Apriori、FP－growth作為實驗比較的對象。實驗在Celeron Ⅱ 920MHz，256MB內存的環境下完成，Visual C++6.0實現源代碼，使用了與文獻[8]同樣的測試數據。該數據庫中共有8 124條記錄，實驗結果如圖4所示。比較算法FG和算法Apriori、FP－growth在事務數據庫上的運行時間可以發現，算法FG的運行時間明顯要少于算法Apriori和FP－growth。

另外FG算法可以觀察所求出的關聯規則，直接得到無冗余的頻繁項集，因此FG算法也可以用于求解頻繁項集。

4結束語

本文在研究和分析關聯規則算法的基礎上，提出了高效快速挖掘算法，即FG算法。通過實驗結果表明，FG算法較以前的一些關聯規則挖掘算法有所改進，性能有所提高，是一個高效、可行的關聯規則挖掘算法。目前已經將該關聯規則挖掘算法應用到醫院電子病歷系統中，為醫療智能診斷提供了較好的輔助性決策。

參考文獻：

［1］AGRAWAL R，IMIELINSKI T，SWAMI A.Mining association rules between sets of items in large databases:proc.of the ACMSIGMOD Conf. on Management of Data[C].Washingtion DC:[s.n.]，1993:207－216.[2]AGRAWAL R，SRIKANT R.Fast algorithms for mining association rules:proc.of the 20th VLDB Conf.[C].Santiago:[s.n.]，1994:487－499.

[3]PASQUITER N，BASTIDE Y，TAOUIL R.Efficient mining of association rules using colsed itemset latices[J].Information System，1999，24(1):25－26.

[4]秦亮曦，李謙，史忠植.基于排序FP樹的頻繁模式高效挖掘算法[J].計算機科學，2005，32（4）:31－33.

[5]毛國君，劉椿年.基于項目序列集操作的關聯規則挖掘算法[J].計算機學報，2002，25（4）:417－423.

[6]HART J，KAMBER M．數據挖掘概念與技術[M]．范明，孟小峰，等譯．北京：機械工業出版社，2004.

[7]高峰，謝劍英.一種無冗余的關聯規則發現算法[J].上海交通大學學報，2001，35（2）: 256－258.

[8]宋余慶，朱玉全，等.一種基于最大頻繁模式樹的約束最大頻繁項目集挖掘及其更新算法[J].計算機研究與發展，2005，42（5）：777－783.

注：“本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文”