關聯分析檢視原始碼討論檢視歷史

來自 搜狐網 的圖片

關聯分析是一個專用名詞。

漢字(拼音:hàn zì，注音符號:ㄏㄢˋ ㄗˋ)，又稱中文、中國字、方塊字，是漢語的記錄符號，屬於表意文字的詞素音節文字。世界上最古老的文字之一，已有六千多年的歷史。在形體上逐漸由圖形變為筆畫，象形變為象徵，複雜變為簡單;在造字原則上從表形、表意到形聲。除極個別漢字外(如瓩、兛、兣、呎、嗧等)，都是一個漢字一個音節。 需要注意的是，日本、韓國、朝鮮、越南等國在歷史上都深受漢文化的影響，甚至其語文都存在借用漢語言文字的現象。

名詞解釋

關聯分析就是對數據集中反覆出現的相關關係和關聯性進行挖掘提取，從而可以根據一個數據項的出現預測其他數據項的出現。

關聯分析的典型例子

啤酒和尿布案例，數據挖掘發現在大型超市中購買啤酒的男士經常同時購買小孩的紙尿褲，基於這一發現，超市把啤酒和紙尿褲擺放在一起，結果兩種商品的銷售量都有明顯提升。消費者行為海量數據的關聯分析在電商精準銷售中得到廣泛應用，對其貨品種類、庫存、倉儲、物流和廣告業務都有極大的效益回饋。

常見的關聯分析方法

Apriori算法

Apriori算法是挖掘產生布爾關聯規則所需頻繁項集的基本算法，也是最著名的關聯規則挖掘算法之一。Apriori算法就是根據有關頻繁項集特性的先驗知識而命名的。它使用一種稱作逐層搜索的迭代方法，k—項集用於探索（k+1）—項集。首先，找出頻繁1—項集的集合．記做L1，L1用於找出頻繁2—項集的集合L2，再用於找出L3，如此下去，直到不能找到頻繁k—項集。找每個Lk需要掃描一次數據庫。

為提高按層次搜索並產生相應頻繁項集的處理效率，Apriori算法利用了一個重要性質，並應用Apriori性質來幫助有效縮小頻繁項集的搜索空間。

Apriori性質：一個頻繁項集的任一子集也應該是頻繁項集。證明根據定義，若一個項集I不滿足最小支持度閾值min_sup，則I不是頻繁的，即P（I）<min_sup。若增加一個項A到項集I中，則結果新項集（I∪A）也不是頻繁的，在整個事務數據庫中所出現的次數也不可能多於原項集I出現的次數，因此P（I∪A）<min_sup，即（I∪A）也不是頻繁的。這樣就可以根據逆反公理很容易地確定Apriori性質成立。

針對Apriori算法的不足，對其進行優化：

1）基於劃分的方法。該算法先把數據庫從邏輯上分成幾個互不相交的塊，每次單獨考慮一個分塊並對它生成所有的頻繁項集，然後把產生的頻繁項集合併，用來生成所有可能的頻繁項集，最後計算這些項集的支持度。這裡分塊的大小選擇要使得每個分塊可以被放入主存，每個階段只需被掃描一次。而算法的正確性是由每一個可能的頻繁項集至少在某一個分塊中是頻繁項集保證的。

上面所討論的算法是可以高度並行的。可以把每一分塊分別分配給某一個處理器生成頻繁項集。產生頻繁項集的每一個循環結束後．處理器之間進行通信來產生全局的候選是一項集。通常這裡的通信過程是算法執行時間的主要瓶頸。而另一方面，每個獨立的處理器生成頻繁項集的時間也是一個瓶頸。其他的方法還有在多處理器之間共享一個雜湊樹來產生頻繁項集，更多關於生成頻繁項集的並行化方法可以在其中找到。

2）基於Hash的方法。Park等人提出了一個高效地產生頻繁項集的基於雜湊（Hash）的算法。通過實驗可以發現，尋找頻繁項集的主要計算是在生成頻繁2—項集Lk上，Park等就是利用這個性質引入雜湊技術來改進產生頻繁2—項集的方法。

3）基於採樣的方法。基於前一遍掃描得到的信息，對它詳細地做組合分析，可以得到一個改進的算法，其基本思想是：先使用從數據庫中抽取出來的採樣得到一些在整個數據庫中可能成立的規則，然後對數據庫的剩餘部分驗證這個結果。這個算法相當簡單並顯著地減少了FO代價，但是一個很大的缺點就是產生的結果不精確，即存在所謂的數據扭曲（Dataskew）。分布在同一頁面上的數據時常是高度相關的，不能表示整個數據庫中模式的分布，由此而導致的是採樣5%的交易數據所花費的代價同掃描一遍數據庫相近。

4）減少交易個數。減少用於未來掃描事務集的大小，基本原理就是當一個事務不包含長度為志的大項集時，則必然不包含長度為走k+1的大項集。從而可以將這些事務刪除，在下一遍掃描中就可以減少要進行掃描的事務集的個數。這就是AprioriTid的基本思想。

FP-growth算法

由於Apriori方法的固有缺陷．即使進行了優化，其效率也仍然不能令人滿意。2000年，Han Jiawei等人提出了基於頻繁模式樹（Frequent Pattern Tree，簡稱為FP-tree）的發現頻繁模式的算法FP-growth。在FP-growth算法中，通過兩次掃描事務數據庫，把每個事務所包含的頻繁項目按其支持度降序壓縮存儲到FP—tree中。在以後發現頻繁模式的過程中，不需要再掃描事務數據庫，而僅在FP-Tree中進行查找即可，並通過遞歸調用FP-growth的方法來直接產生頻繁模式，因此在整個發現過程中也不需產生候選模式。該算法克服了Apriori算法中存在的問顥．在執行效率上也明顯好於Apriori算法。