摘  要： 關聯規則是數據挖掘的主要技術之一，它是描述數據庫中一組數據項之間的某種潛在關系的規則。關聯規則挖掘算法——Apriori算法，主要過程是對頻繁項集的挖掘,而在對頻繁項集的挖掘中首先要生成候選頻繁項集，然后再從候選集中確定出滿足最小支持度計數的頻繁項集,這會耗費大量的CPU開銷。使用垂直數據格式挖掘頻繁項集可避免候選項目集的求解。
關鍵詞: 關聯規則；Apriori算法；頻繁項集；垂直數據格式

    通常，關聯規則挖掘是指從一個大型的數據集中發現有趣的關聯或相關關系，即從數據集中識別出頻繁出現的屬性值集（Sets of Attribute-Values），也稱為頻繁項集（Frequent Itemsets,簡稱頻繁集），然后再利用這些頻繁集創建描述關聯規則的過程。
1 關聯規則挖掘算法
    關聯規則挖掘算法——Apriori算法是使用候選項集找頻繁項集的過程。
    Apriori算法通過對數據庫D的多趟掃描來發現所有的頻繁項目集。在第一趟掃描數據庫時，對項集I中的每一個數據項計算其支持度，確定出滿足最小支持度的頻繁1項集的集合L1，然后，L1用于找頻繁2項集的集合L2，如此下去……在后續的第k次掃描中，首先以k-1次掃描中所發現的含k-1個元素的頻繁項集的集合Lk-1為基礎，生成所有新的候選項目集CK（Candidate Itemsets），即潛在的頻繁項目集，然后掃描數據庫D，計算這些候選項目集的支持度，最后從候選集CK中確定出滿足最小支持度的頻繁k項集的集合Lk,并將Lk作為下一次掃描的基礎。重復上述過程直到不再發現新的頻繁項目集[1]。
2 關聯規則算法的改進
    從Apriori算法中由k頻繁項集生成k+1頻繁項集時，首先生成候選項目集Ck+1，該函數不僅要對k項集的所有符合Apriori算法條件的數據進行交集，并且要判斷候選項目集的所有子集是否在k頻繁項集中。該函數生成的許多候選項目集并不是要找的頻繁項集，但在掃描數據庫時，要記錄下這些數據的出現次數，這會耗費大量的CPU開銷。如果D中的事務數很大，k頻繁項集中項數很多，則侯選項目集的元素個數就會很大，例如2 000個頻繁1項集，將產生2 000×999/2=999 000個候選2項集。如此巨大數量的候選項目集，對它進行出現次數的統計時開銷非常大，這也是整個算法性能優劣的關鍵所在。
 （1）使用垂直數據格式挖掘頻繁項集
   Apriori算法是從TID項集格式（即{TID：itemset}）的事務集挖掘頻繁模式，其中TID是事務標識符，而itemset是事務TID中購買的商品集。這種數據格式稱作水平數據格式。另外,數據也可以用項-TID集格式(即{item:TID_set})表示，其中item是項的名稱，而TID_set是包含item事務標識符的集合。這種格式稱作垂直數據格式。下面使用垂直數據格式進行有效的挖掘頻繁項集。
    首先，通過掃描一次數據庫D，在求頻繁l項集的同時，把數據由水平格式轉化為垂直格式，即記錄下每個項集在事務數據庫中出現時該條數據在數據庫D中的TID號，則項集的支持度計數直接是項集的TID集的長度。從k=2開始，根據Apriori性質中相交條件的項集進行Apriroi連接運算，使用頻繁k項集來構造候選k+1項集。通過取頻繁k項集的TID集的交計算對應的k+1項集的TID集。如果該TID集的長度大于最小支持度計數，則該記錄為頻繁項集。重復該過程，每次k值增加1，直到不能再找到頻繁項集或候選項集。
 

    通過挖掘可以驗證最終得到的頻繁項集和用Apriori算法得到的結果是相同的[2-3]。

3 改進算法的分析

    理論上，改進算法應快于算法Apriori，原因如下：
    (1)該算法不用求候選頻繁項集，從而省去了項集進行連接步以后對該項集所有子集的判斷，這會節省大量
的CPU開銷，尤其是當數據庫D中的數據比較多，同時候選項集比較多時，例如頻繁1項集2 000個，根據Apriori性質,則候選頻繁1項集要有2 000×999/2=999 000個，但其中也許只有少數是要找的頻繁2項集。Apriori算法要求其中所有999 000個在數據庫中的頻繁度。
    (2) 除了由頻繁k項集產生候選k+1項集時利用Apriori性質之外，這種方法的另一優點是不需要掃描數據庫來確定k+1項集(k≥1)的支持度。這是因為每個k項集的TID集攜帶了計算該支持度所需的完整信息。
    該算法的缺點是TID集可能很長，長集合不僅需要大量空間，而且求交運算需要大量計算時間。
參考文獻
[1] 韓家煒. 數據挖掘概念與技術[M].北京：機械工業出版社，2000.
[2] 陸楠.關聯規則的挖掘及其算法的研究[D]. 長春：吉林大學，2007.
[3] 羅可，張學茂. 一種高效的頻集挖掘算法[J]. 長沙理工大學學報(自然科學版)，2006，3(3)：84-90.
[4] 汪光一. 關聯規則挖掘算法的研究[D]. 北京：北京交通大學,2007.
[5] 高峰，謝劍英. 發現關聯規則的增量式更新算法[J].計算機工程，2000(12):49-50.
[6] KANTARDZIC M(美).數據挖掘-概念、模型、方法和算法[M]. 北京：清華大學出版社，2003.