4.2.4 劃分

Savasere等設(shè)計(jì)了一個(gè)基于劃分的算法[SON95]，這個(gè)算法先把數(shù)據(jù)庫(kù)從邏輯上分成幾個(gè)互不相交的塊，每次單獨(dú)考慮一個(gè)分塊并對(duì)它生成所有的頻集，然后把產(chǎn)生的頻集合并，用來(lái)生成所有可能的頻集，最后計(jì)算這些項(xiàng)集的支持度。這里分塊的大小選擇要使得每個(gè)分塊可以被放入主存，每個(gè)階段只需被掃描一次。而算法的正確性是由每一個(gè)可能的頻集至少在某一個(gè)分塊中是頻集保證的。上面所討論的算法是可以高度并行的，可以把每一分塊分別分配給某一個(gè)處理器生成頻集。產(chǎn)生頻集的每一個(gè)循環(huán)結(jié)束后，處理器之間進(jìn)行通信來(lái)產(chǎn)生全局的候選k-項(xiàng)集。通常這里的通信過(guò)程是算法執(zhí)行時(shí)間的主要瓶頸；而另一方面，每個(gè)獨(dú)立的處理器生成頻集的時(shí)間也是一個(gè)瓶頸。其他的方法還有在多處理器之間共享一個(gè)雜湊樹(shù)來(lái)產(chǎn)生頻集。更多的關(guān)于生成頻集的并行化方法可以在文獻(xiàn)[AS96]中找到。



4.2.5 選樣

基本思想是在給定數(shù)據(jù)的一個(gè)子集挖掘。對(duì)前一遍掃描得到的信息，仔細(xì)地組合分析，可以得到一個(gè)改進(jìn)的算法，Mannila等先考慮了這一點(diǎn)[MTV94]，他們認(rèn)為采樣是發(fā)現(xiàn)規(guī)則的一個(gè)有效途徑。隨后又由Toivonen進(jìn)一步發(fā)展了這個(gè)思想[Toi96]，先使用從數(shù)據(jù)庫(kù)中抽取出來(lái)的采樣得到一些在整個(gè)數(shù)據(jù)庫(kù)中可能成立的規(guī)則，然后對(duì)數(shù)據(jù)庫(kù)的剩余部分驗(yàn)證這個(gè)結(jié)果。Toivonen的算法相當(dāng)簡(jiǎn)單并顯著地減少了I/O代價(jià)，但是一個(gè)很大的缺點(diǎn)就是產(chǎn)生的結(jié)果不精確，即存在所謂的數(shù)據(jù)扭曲(data skew)。分布在同一頁(yè)面上的數(shù)據(jù)時(shí)常是高度相關(guān)的，可能不能表示整個(gè)數(shù)據(jù)庫(kù)中模式的分布，由此而導(dǎo)致的是采樣5%的交易數(shù)據(jù)所花費(fèi)的代價(jià)可能同掃描一遍數(shù)據(jù)庫(kù)相近。



4.2.6 動(dòng)態(tài)項(xiàng)集計(jì)數(shù)

Brin等人給出該算法[BMUT97]。動(dòng)態(tài)項(xiàng)集計(jì)數(shù)技術(shù)將數(shù)據(jù)庫(kù)劃分為標(biāo)記開(kāi)始點(diǎn)的塊。不象Apriori僅在每次完整的數(shù)據(jù)庫(kù)掃描之前確定新的候選，在這種變形中，可以在任何開(kāi)始點(diǎn)添加新的候選項(xiàng)集。該技術(shù)動(dòng)態(tài)地評(píng)估以被計(jì)數(shù)的所有項(xiàng)集的支持度，如果一個(gè)項(xiàng)集的所有子集以被確定為頻繁的，則添加它作為新的候選。結(jié)果算法需要的數(shù)據(jù)庫(kù)掃描比Apriori 少。





4.3 FP-樹(shù)頻集算法



針對(duì)Apriori算法的固有缺陷，J. Han等提出了不產(chǎn)生候選挖掘頻繁項(xiàng)集的方法—FP-樹(shù)頻集算法[HPY00]。采用分而治之的策略，在經(jīng)過(guò)第一遍掃描之后，把數(shù)據(jù)庫(kù)中的頻集壓縮進(jìn)一棵頻繁模式樹(shù)（FP-tree），同時(shí)依然保留其中的關(guān)聯(lián)信息，隨后再將FP-tree分化成一些條件庫(kù)，每個(gè)庫(kù)和一個(gè)長(zhǎng)度為1的頻集相關(guān)，然后再對(duì)這些條件庫(kù)分別進(jìn)行挖掘。當(dāng)原始數(shù)據(jù)量很大的時(shí)候，也可以結(jié)合劃分的方法,使得一個(gè)FP-tree可以放入主存中。實(shí)驗(yàn)表明，F(xiàn)P-growth對(duì)不同長(zhǎng)度的規(guī)則都有很好的適應(yīng)性，同時(shí)在效率上較之a(chǎn)priori算法有巨大的提高。





4.4 多層關(guān)聯(lián)規(guī)則挖掘



對(duì)于很多的應(yīng)用來(lái)說(shuō)，由于數(shù)據(jù)分布的分散性，所以很難在數(shù)據(jù)最細(xì)節(jié)的層次上發(fā)現(xiàn)一些強(qiáng)關(guān)聯(lián)規(guī)則。當(dāng)我們引入概念層次后，就可以在較高的層次上進(jìn)行挖掘[HF95, SA95]。雖然較高層次上得出的規(guī)則可能是更普通的信息，但是對(duì)于一個(gè)用戶來(lái)說(shuō)是普通的信息，對(duì)于另一個(gè)用戶卻未必如此。所以數(shù)據(jù)挖掘應(yīng)該提供這樣一種在多個(gè)層次上進(jìn)行挖掘的功能。

多層關(guān)聯(lián)規(guī)則的分類(lèi)：根據(jù)規(guī)則中涉及到的層次，多層關(guān)聯(lián)規(guī)則可以分為同層關(guān)聯(lián)規(guī)則和層間關(guān)聯(lián)規(guī)則。

多層關(guān)聯(lián)規(guī)則的挖掘基本上可以沿用“支持度-可信度”的框架。不過(guò)，在支持度設(shè)置的問(wèn)題上有一些要考慮的東西。

同層關(guān)聯(lián)規(guī)則可以采用兩種支持度策略：

1)  統(tǒng)一的最小支持度。對(duì)于不同的層次，都使用同一個(gè)最小支持度。這樣對(duì)于用戶和算法實(shí)現(xiàn)來(lái)說(shuō)都比較的容易，但是弊端也是顯然的。

2)  遞減的最小支持度。每個(gè)層次都有不同的最小支持度，較低層次的最小支持度相對(duì)較小。同時(shí)還可以利用上層挖掘得到的信息進(jìn)行一些過(guò)濾的工作。

層間關(guān)聯(lián)規(guī)則考慮最小支持度的時(shí)候，應(yīng)該根據(jù)較低層次的最小支持度來(lái)定。





4.5 多維關(guān)聯(lián)規(guī)則挖掘



對(duì)于多維數(shù)據(jù)庫(kù)而言，除維內(nèi)的關(guān)聯(lián)規(guī)則外，還有一類(lèi)多維的關(guān)聯(lián)規(guī)則。例如：

年齡（X，“20...30”） 職業(yè)（X,“學(xué)生”）==> 購(gòu)買(mǎi)(X，“筆記本電腦”)

在這里我們就涉及到三個(gè)維上的數(shù)據(jù)：年齡、職業(yè)、購(gòu)買(mǎi)。

根據(jù)是否允許同一個(gè)維重復(fù)出現(xiàn)，可以又細(xì)分為維間的關(guān)聯(lián)規(guī)則（不允許維重復(fù)出現(xiàn)）和混合維關(guān)聯(lián)規(guī)則（允許維在規(guī)則的左右同時(shí)出現(xiàn)）。

年齡（X，“20...30”） 購(gòu)買(mǎi)(X，“筆記本電腦”) ==> 購(gòu)買(mǎi)(X，“打印機(jī)”)

這個(gè)規(guī)則就是混合維關(guān)聯(lián)規(guī)則。

在挖掘維間關(guān)聯(lián)規(guī)則和混合維關(guān)聯(lián)規(guī)則的時(shí)候，還要考慮不同的字段種類(lèi)：種類(lèi)型和數(shù)值型。

對(duì)于種類(lèi)型的字段，原先的算法都可以處理。而對(duì)于數(shù)值型的字段，需要進(jìn)行一定的處理之后才可以進(jìn)行[KHC97]。處理數(shù)值型字段的方法基本上有以下幾種：

1)  數(shù)值字段被分成一些預(yù)定義的層次結(jié)構(gòu)。這些區(qū)間都是由用戶預(yù)先定義的。得出的規(guī)則也叫做靜態(tài)數(shù)量關(guān)聯(lián)規(guī)則。

2)  數(shù)值字段根據(jù)數(shù)據(jù)的分布分成了一些布爾字段。每個(gè)布爾字段都表示一個(gè)數(shù)值字段的區(qū)間，落在其中則為1，反之為0。這種分法是動(dòng)態(tài)的。得出的規(guī)則叫布爾數(shù)量關(guān)聯(lián)規(guī)則。

3)  數(shù)值字段被分成一些能體現(xiàn)它含義的區(qū)間。它考慮了數(shù)據(jù)之間的距離的因素。得出的規(guī)則叫基于距離的關(guān)聯(lián)規(guī)則。

4)  直接用數(shù)值字段中的原始數(shù)據(jù)進(jìn)行分析。使用一些統(tǒng)計(jì)的方法對(duì)數(shù)值字段的值進(jìn)行分析，并且結(jié)合多層關(guān)聯(lián)規(guī)則的概念，在多個(gè)層次之間進(jìn)行比較從而得出一些有用的規(guī)則。得出的規(guī)則叫多層數(shù)量關(guān)聯(lián)規(guī)則。





5 展望



對(duì)于關(guān)聯(lián)規(guī)則挖掘領(lǐng)域的發(fā)展，筆者認(rèn)為可以在如下一些方向上進(jìn)行深入研究：在處理極大量的數(shù)據(jù)時(shí)，如何提高算法效率；對(duì)于挖掘迅速更新的數(shù)據(jù)的挖掘算法的進(jìn)一步研究；在挖掘的過(guò)程中，提供一種與用戶進(jìn)行交互的方法，將用戶的領(lǐng)域知識(shí)結(jié)合在其中；對(duì)于數(shù)值型字段在關(guān)聯(lián)規(guī)則中的處理問(wèn)題；生成結(jié)果的可視化，等等。





參考文獻(xiàn)



[AIS93b] R. Agrawal, T. Imielinski, and A. Swami. Mining association rules between sets of items in large databases. Proceedings of the ACM SIGMOD Conference on Management of data, p.p. 207-216, May 1993.



[AS94a] R. Agrawal, and R. Srikant.  Fast algorithms for mining association rules in large database. Technical Report FJ9839, IBM Almaden Research Center, San Jose, CA, Jun. 1994.



[AS94b] R. Agrawal, and R. Srikant.  Fast algorithms for mining association rules. In Proc. 1994 Int. Conf. Very Large Databases(VLDB’94), Sep. 1994.



[AS96] R. Agrawal, and J. Shafer.  Parallel mining of association rules: Design, Implementation, and Experience. IEEE Trans. Knowledge and data engineering, 8:962-969, Jan. 1996.



[BMUT97] S. Brin, R. Motwani, J. D. Ullman, and S. Tsur. Dynamic itemset counting and implication rules for market basket data. In ACM SIGMOD International Conference On the Management of Data, p.p. 255-264, May 1997.



[HF95] J, Han and Y. Fu. Discovery of multiple-level association rules from large databases. In Proc. 1995 Int. Conf. Very Large Databases(VLDB’95), p.p. 402-431, Sep. 1995.



[HPY00] J.Han,J.Pei, and Y.Yin.Mining. Frequent patterns without candidate generation. In Proc. 2000 ACM-SIGMOD Int. Conf. Management of Data (SIGMOD’00), p.p. 1-12, May 2000.



[KHC97] M. Kamber, J. Han, J. Chang. Metarule-guided mining of multi-dimensional association rules using data cubes. In Proc. 1997 Int. Conf. Khowledge Discovery and Data Mining(KDD’97), p.p. 207-210, Aug. 1997

[KPR98] J. Kleinberg, C. Papadimitriou, and P. Raghavan. Segmentation problems. Proceedings of the 30th Annual Symposium on Theory of Computing, ACM. Sep. 1998.

[MTV94] H. Mannila, H. Toivonen, and A. Verkamo. Efficient algorithm for discovering association  rules. AAAI Workshop on Knowledge Discovery in Databases, p.p. 181-192, Jul. 1994.

[PCY95a] J. S. Park, M. S. Chen, and P. S. Yu. An effective hash-based algorithm for mining association rules. Proceedings of ACM SIGMOD International Conference on Management of Data, p.p. 175-186, May 1995.

[PCY95b] J. S. Park, M. S. Chen, and P. S. Yu. Efficient parallel data mining of association rules. 4th International Conference on Information and Knowledge Management, Baltimore, Maryland, Nov. 1995.

[SA95] R. Srikant, and R. Agrawal. Mining generalized association rules. Proceedings of the 21st International Conference on Very Large Database, p.p. 407-419, Sep.1995.

[SON95] A. Savasere, E. Omiecinski, and S. Navathe. An efficient algorithm for mining association rules in large databases. Proceedings of the 21st International Conference on Very Large Database, p.p. 432-443, Sep. 1995.

[Toi96] H. Toivonen. Sampling large databases for association rules. Proceedings of the 22nd International Conference on Very Large Database, Bombay, India, p.p. 134-145, Sep. 1996.