算法分析與研究關聯規則挖掘的優化算法

摘要：頻繁項集挖掘是關聯規則挖掘的核心部分，目前大多數關于關聯規則挖掘的研究都集中于如何提高頻繁項集挖掘的效率，然而在實際應用中，決策者面對的是最終從頻繁項集中生成的規則集，因此優化規則的生成過程及生成規則同樣值得重視。本文提出頻繁項集的子集樹這一模式來生成關聯規則，不僅簡化規則的生成過程還可縮小決策者面對的規則集，更便于規則的增量更新。

關鍵詞：頻繁項集；關聯規則；項集子集樹

中圖分類號：TP113 文獻標識碼：A

1引言關聯規則挖掘是數據挖掘中重要的研究任務。自從1993年Agrawal[1]提出后，關聯規則挖掘問題就受到了廣泛的關注。

一般來說，關聯規則挖掘的過程由以下兩步組成：

1）采用某種頻繁項集挖掘方法發現所有的頻繁項集。

2）根據所獲得的頻繁項集，產生相應的強關聯規則。

由于第二步的開銷遠低于第一步，挖掘關聯規則的總體性能由第一步決定。因此，許多關聯規則的研究都是圍繞著第一步算法效率改進的研究，如Apriori算法[2]及其改進形式[3-5]和后來的FP-growth[6]算法。然而這些研究僅從技術的角度理解和描述挖掘問題，注重的是算法的效率，但是對于一定應用領域，決策者最終面對的是從頻繁項集中產生的規則，他們希望從規則中發現有用的知識來輔助決策的制定。如果直接從頻繁項集中生成全部規則，將是一個龐大的集合，不利于決策者辨別。并且在挖掘的過程中有兩個由用戶設定的閾值，而用戶有時也不能給出一個合適的閾值，因此常常需要多調整幾次閾值來產生令決策者滿意的結果。但是，每調整一次閾值就重新生成一次所有規則，不僅浪費時間而且浪費之前已產生的資源。

現有關于優化關聯規則的的研究可概括為以下兩種方法：一種是采用附加度量，如信任度conviction [7]，χ2度量[8]，全置信度[9]等；另一種是由用戶定義約束條件，如項集約束[10]，概念層次約束[8]，規則形式約束[11]等。第一種方法相當于重新定義了規則的有趣性。然而規則是否有趣只有用戶能夠確定，這種判斷是主觀的，因用戶而異。因此，可以說不存在在任何情況都能夠產生有趣規則的度量方式。第二種方式是采取一定度量方式后結合實際應用情況按用戶的需求增加附加約束來縮小被考慮的規則的范圍。本文是在傳統的支持度-置信度框架下生成有趣規則，首先采用Apriori算法生成頻繁項集，然后根據文中定義的頻繁項集的子集樹生成關聯規則。該方法在不丟失挖掘信息的基礎上減少了規則數量并且最大限度地利用了舊的閾值下生成的關聯規則，不僅有利于決策者的分析，還可以提高規則增量更新的效率。

（4）為了盡量縮小產生的規則數，在建立項集的頻繁子集樹過程中對生成的具有相同根結點的同層頻繁項集按項集的支持度進行升序排序。

該過程將規則的剪枝過程融合在了規則的生成過程中，不僅減小了規則數量而且有利于閾值更新的情況下規則的更新。

4算例分析

為了說明算法的應用過程，本文以表1的交易數據集為例進行分析.

5結論

本文主要是針對規則的生成過程，提出了一種基于頻繁項集的子集樹挖掘方法，先通過生成頻繁項集的頻繁子集樹，然后在子集樹上搜索滿足閾值的頻繁子結點，最后由滿足條件的子結點生成相應的規則。用該子集樹進行規則的生成，不僅可以減少部分冗余規則的生成，更可以便于規則的增量新。

參考文獻

[1]R. Agrawal， T. Imielinski， A. Swami. Mining Association Rules between Sets of Items in Large Database[C]. ACM SIGMOD Conference Proceedings on Management of Data，Washington DC，USA，1993： 207-216.

[2]R. Agrawal， R. Srikant. Fast Algorithms for Mining Association Rules[C]. International conference on very large database （VLDB）， Santiago，Chile，1994： 487-499.

[3]H. Toivonen. Sampling Large Database for Association Rules[C]. In Proc. Of the 22nd Int. Conference on Very Large Databases，Mumbai，India，996： 134-145.

[4]R. Agrawal， J. Shafer. Parallel Mining of Association Rules[J]. IEEE Transactions on Knowledge and Data Engineering，1996， 8（6）：962-969.

[5]H. E. Han， G. Karypis， V. Kumar. Scalable Parallel Data Mining for Association Rules[C]. In Proc. of the ACM SIGMOD Conference on Management of Data， NY，USA，1997：277-288.

[6]J. Han， J. Pei， and Y. Yin. Ming Frequent Patterns without Candidate Generation[C]. In Proceeding of Special Interest Group on Management of Data， NY，USA，2000：1-12.

[7]S. Brin， R. Motwani， J. Ullman，and S. Tsur. Dynamic Itemset Counting and Implication Rules for Market Basket Data[J]. Proc. ACM SIGMOD Conf.， NY，USA，1997：255-264.

[8]S. Brin， R. Motwani， and C. Silverstein. Beyond Market Baskets： Generalizing Association Rules to Correlations[C]. Proc. ACM SIGMOD Conf.NY，USA， 1997：265-276.

[9]E. R. Omiecinski. Alternative Interest Measures for Mining Associations in Databases[J]. IEEE Trans on Knowledge and Data Engineering， 2003， 15（1）：57-69.

[10]R. Srikant， Q. Vu and R. Agarawal. Mining association rules with item constraint[C]. In Proceeding of 3th International Conference on Knowledge Discovery and Data Mining（KDD），USA， 1997：67-73.

[11]Roberto J. Bayardo Jr， Rakesh Agrawal， Dimitrios Gunopulos. Constraint-Based Rule Mining in Large， Dense Databases[J]. Journal of Data Mining and Knowledge Discovery， 2000，4（2-3） 217-240.

[12]Jiawei Han， Micheline Kamber. Data Mining Concepts and Techniques， Second Edition， Translated by Fanming， Menxiao Feng[M].Shenyang：China Machine Press， 2007.