對于基于搜索方法的關聯規則發現算法的研究

摘要：挖掘關聯規則是數據挖掘領域的一個重要研究方向，本文首先介紹了一種基于層次的Apriori算法和一種基于搜索算法的QAIS算法，通過二者的比較，指出了QAIS算法中的優點以及不足之處。然后有針對性的提出了解決的方案，形成了ImprovedQAIS算法。

關鍵詞：關聯規則；數據挖掘；基于搜索；算法

中圖分類號：TP311文獻標識碼：A 文章編號：1009-3044(2008)12-20000-00

Research Of Association Rule Finding Based on Searching Algorithm

LIU Jin-zhong

(Hunan Medical secondary specialized schools，Changsha 410014，China)

Abstract:Mining association rules are major aspect of data mining Domain. This paper first introduces Apriori algorithm， and then show a mining association rule algorithm based on searching algorithm， which can be called NewQAIS. By comparing to Apriori algorithm， we can realize that NewQAIS algorithm is better in some aspects. The paper also points out some drawbacks of NewQAIS algorithm. On the basis of the comprehension， a method to solve the above drawbacks is pointed out， which leads to the ImprovedQAIS algorithm.

Key words:data mining; association rules; searching algorithm

1 數據挖掘中的關聯規則發現

隨著數據庫技術的飛速發展以及人們獲取數據手段的多樣化，人類所擁有的數據急劇的增加，可是目前用于對這些數據進行分析處理的工具卻很少。數據挖掘（DM，Data Mining）是近年來隨著數據庫和人工智能技術的發展而出現的一種全新信息技術，它從大量的、不完全的、有噪聲的、模糊的、隨機的數據中，提取隱含在其中的、新穎的、潛在有用的信息和知識的過程，也就是從數據資料中發掘信息或知識（KDD，Knowledge Discover in Database）。數據挖掘首先應該依據對問題的定義明確挖掘的任務或目的，然后決定使用什么樣的算法。常見的挖掘任務有分類或預測模型發現、數據總結、聚類、關聯規則發現、序列模式發現、依賴關系或依賴模型發現、異常和趨勢發現等。

關聯規則發現是在數據庫中尋找數據對象間的關聯模式。挖掘關聯規則需要根據最小只吃度找出數據集中所有的頻繁集，然后根據頻繁項目集和最小置信度產生關聯規則。

2 基于層次的Apriori算法和基于搜索的QAIS算法

2.1 典型層次發現算法——Apriori先驗算法

現有的多數挖掘關聯規則的算法均是以Apriori先驗算法為基礎，Apriori算法是一個基于兩階段頻繁集的方法，將關聯規則挖掘算法分解為兩個子問題：（1）求出數據庫D 中滿足最小支持度minsup的所有頻繁項目集，記為Lk；（2）利用頻繁集生成滿足最小可信度minconf的所有關聯規則。其中第一個問題是算法的關鍵，Apriori算法用基于頻繁集理論的遞推方法來解決這一問題。尋找頻繁集是規則發現的核心部分，該算法使用一種稱作逐層搜索的迭代方法，頻繁k項集Lk用于搜索頻繁(k+1)項集Lk+1，尋找每一個Lk需要掃描一次數據庫。

為了盡可能地減少項集的組合和掃描次數，以提高頻繁項集逐層產生的效率，發現算法在產生頻繁項集時使用了Apriori性質，即：頻繁項集的所有非空子集也都是頻繁集的。可以解釋為：任何頻繁集的子集都是頻繁集；任何非頻繁集的包含（超集）都是非頻繁集。Apriori性質是基于這樣的事實：由定義知，如果項集I不滿足最小支持度minsup，則I不是頻繁集。如果一個項A添加到I中，則結果項集不可能比I更頻繁，因此I∪A也不是頻繁集，即P(I∪A)＜minsup。

Apriori 算法出現較早，它強調的是如何高效地發現初始數據庫中的頻繁集，而關聯規則的更新可以說不在它的考慮范圍之內。但從規則更新的角度來看，當定義頻繁集的條件稍做變動，在這被丟棄的項集中就有可能是在新頻繁集里。正因為如此，以Apriori算法為基礎的關聯規則更新算法諸如FUP 算法、IUA 算法都較復雜。Apriori 算法的另一個很顯著的特點是在尋找頻繁集的過程中不可避免的生成了許多的中間候選項集。中間候選項集的數目即便是對同一個初始數據庫也不是一個常量，它依賴于給定的最小支持度。一般來說，最小支持度越小，中間候選項集的數目的也就越多，在算法執行過程中占用的空間也就越多。

2.2 快速關聯規則挖掘算法——QAIS先驗算法

QAIS算法通過對事務數據庫DB 中的每一條事務求出所有的項目子集，保存在項目集聚集之中，并記錄每一個項目集的出現的次數（支持度），然后遍歷整合項集過濾出大于給定最小支持度的項目集，形成頻繁集，最后根據給定的置信度生成優化了的關聯規則。

QAIS算法只要對數據庫進行一次的掃描，即可建立一個具有支持度計數整合項集(AggItemSet)，整理后的數據集可以取代原始的數據庫，減少了反復搜尋數據庫的時間，由于頻繁項目集的合并與分解都在這個整合項目集中就可完成，所以可以顯著降低找出所有頻繁項目集所需要的時間。QAIS 算法可用于初始數據庫關聯規則的挖掘。

QAIS 算法對初始數據庫中的信息進行某種整合，這種整合不僅是想滿足尋找初始數據庫中的頻繁集，它還更有意識的為以后的關聯規則的更新作鋪墊。當尋找頻繁集所需要的最小支持度發生變化時，對QAIS 算法來說，它只要重新掃描一遍（或不用一遍）整合項集就可以了；而對Apriori 算法來說，要么重新運行Apriori 算法，要么運行以Apriori 算法為基礎的關聯規則更新算法，二者無論那一個，都要比掃描一遍QAIS 算法早已形成的整合項集要復雜的多。

事實上，即便是對初始頻繁集的形成，整合項集也有它有利的一方面。一般來說，為了發現事先未知的關聯規則，用戶必然需要通過對最小支持度和最小可信度這兩個閾值的不斷調整來逐步聚焦到那些真正令人感興趣的關聯規則上去，這將是一個動態的交互過程。而QAIS 算法可以說滿足了這種對時間要求較高的交互過程，從這一方面來說，Apriori 算法對這種交互過程的適應性是比較差的。

而且，QAIS算法不存在系統要給算法分配多少內存空間的不確定性。對于QAIS算法用到的兩個數據結構來說，任一給定的初始數據庫，事務的所有非空子集SubItemSet與整合項集 占用的空間都是可以預見的。若每一個內存單元都能存儲一個項集，而數據庫中有n 個交易，數據庫中交易所能形成的SubItemSet占用空間的大小是??2x-n，（x 為交易的長度），那么 所能占用的最大空間是n×（??2x -n）。

3 QAIS算法的改進算法——ImprovedQAIS算法

3.1 QAIS算法存在的問題

QAIS 算法的關鍵是只需要對初始數據庫一次掃描就要生成所有的頻繁項目集的最大超集。對每一個包含n個項目的交易都將產生2n-1個非空項目集。由這些交易形成的項集的并集組成了這個最大超集。而一般要挖掘的初始數據庫都有成千上萬個交易，所需計算和存儲的候選項目集的數量往往非常龐大，這樣，如果不對該算法進行一定的改進，它只能適應于交易數量較少并且交易本身的長度較短的數據庫關聯規則挖掘。

3.2 改進的QAIS算法——ImprovedQAIS算法

針對上述問題，必須對原程序做一些變化。首先，可以將SubItemSet這種數據結構棄之不用。然后，為適應新算法，對 的數據結構做一個改動：由于知道最長的交易為max_T，所以首先可先建立一個長度為max_T的一維數組。其次，分別建立max_T個單鏈表，分別用于存儲長度是從1 到max_T的項集，該鏈表的每個節點將有三個域：一個存項集，一個存該項集的支持數，一個存指向下一個節點的指針。最后，這max_T個鏈表的首地址分別存儲在先前建立的一維數組中，存儲時按照其指向的項集的長短來進行，即：數組的單元1 存指向長度為1 的鏈表首地址，單元2 存指向長度為2 的鏈表首地址，依次類推。第三，設立一個固定的存儲單元，允許項目作為集合元素存放入該單元。

3.3 新舊QAIS算法的比較

新舊QAIS 算法的最顯著的不同在于：ImprovedQAIS算法改進了交易非空子集的生成方法，廢除了SubItemSet結構，改變了通過集合并交運算進行記數的方法，使用了一種適應新算法的項目集存儲結構 。

新的子集生成方法大大地降低了項目子集生成的復雜度。同時，由于復雜度的降低，非空子集元素（項集）生成過程中占用的空間大大減少，這將使該算法能夠處理較大的數據集，在某種程度上增強了算法的適應性。

廢除SubItemSet結構，直接將生成的項集送入 整合項集合，節約了內存空間，用簡單的查找代替并交運算進行記數，也降低了算法的復雜度。我們知道，能夠尋找到給定最小支持度下的頻繁集是形成關聯規則的基礎，而項集是不是頻繁集并不是一成不變的，關鍵就是看它們的支持度能否滿足最小支持度。而項集支持度只能通過直接的或間接的方法從初始數據庫中獲取。Apriori算法對項集支持數的獲取是通過一遍又一遍掃描初始數據庫直接實現的。QAIS 算法不同于Apriori算法的一個顯著特點就是將初始數據庫中有關于頻繁集的信息進行了整合，歸并到了一起集中管理，方便查詢，QAIS 算法雖然指出了整合的概念，但并沒有提出一個切實可行的方案，可操作性不強。ImprovedQAIS算法使用了一種適應于整合信息的數據結構，在這個結構中，將不同長度的項集分開存儲，同一長度的項又按計數值大小排列，方便而又節省查詢時間。該結構的一個特點是采用了鏈表結構，方便插入操作。

另外需強調的是，ImprovedQAIS算法還比QAIS 算法避免了項集的重復生成，節省了時間和空間。

參考文獻：

[1] 邵峰晶．數據挖掘——原理與算法，北京：中國水利水電出版社，2003.

[2] 顏雪松，蔡之華．一種基于Apriori算法的高效關聯規則挖掘算法的研究[J].計算機工程與應用，2002，38（10）.

[3] 李緒成，王保保．挖掘關聯規則中Apriori 算法的改進[J].計算機工程，2002，28(7).

收稿日期：2008-03-27

作者簡介：劉金忠（1972-），男，湖南桃源人，中級職稱，就只于湖南省醫藥中等專業學校，研究方向：計算機教育。