Weka資料挖掘——關聯

挫折感很大、覺得很難熬的時候，可以閉上眼睛，想像自己已經是十年之後的自己，置身一段距離之外，轉頭去看正在遭遇的那些事。 練習這樣做，心情可能會平靜些，知道眼前這一切，都會過去。——蔡康永

别太嚣張，對自己沒好處。——李秘書

你今天潑給我的冷水，我定要燒開了給你潑回去。——宋曉峰

小人别得地，得地就起屁。 ——劉能

目錄

• • • 目錄
    • 關聯規則概述
    • 關聯算法的介紹
      • 2-1 Apriori算法
      • 2-2 FP-Growth算法
    • 關聯算法Weka實作
      • 3-1 Apriori關聯規則挖掘

1 關聯規則概述

關聯規則挖掘是資料挖掘的熱點之一。關聯規則反映一個對象與其他對象之間的互相依賴性，如果多個對象之間存在一定的關系，那麼一個對象就能夠通過其他對象來進行預測。

關聯規則可以采用與分類規則相同的方式産生。由于得到的關聯規則的數量龐大，通常需要通過使用覆寫率和準确率進行修剪，覆寫率也稱為支援度，指的是應用規則之後預測正确的執行個體數量。準确率也稱為置信度，表示為支援度數值應用規則後的數量比例。

相關術語：

支援度: P(A∩B)，即A和B這兩個項集在事務集D中同時出現的機率。

置信度: P(B∣A)，即在出現項集A的事務集D中，項集B也同時出現的機率。

頻繁項集：指經常出現在一塊的物品的集合。 關聯規則暗示兩種物品之間存在很強的關系。(這裡我們事先定義閥值，超過該閥值，證明兩者之間存在很強的關系).

2 關聯算法的介紹

2-1 Apriori算法

算法介紹

Apriori算法利用了兩個重要的性質，用于壓縮搜尋的空間。

【1】若X為頻繁項目集，則X的所有子集都是頻繁項目集。

【2】若X為非頻繁項目集，則X的所有超集均為非頻繁項目集。

Apriori算法的處理流程為：寬度優先搜尋整個項集空間，從k=0開始，疊代産生長度為k+1的候選項集的集合Ck+1。候選項集是其所有子集都是頻繁項集的項集（初始化C1由I0中所有的項構成），在第k層産生所有長度為k+1的項集。

由兩步完成：

第一步，Fk自連接配接。将Fk中具有相同(k-1)-字首的項集連接配接成長度為k的候選項集。

第二步是剪枝，如果項集的所有長度為k的子集都在Fk中，該項集才能作為候選項集被加入Ck+1中。為了計算所有長度為k的候選項集的支援度，在資料庫水準表示方式下，需要掃描資料庫一遍。在每次掃描中，對資料庫中的每條交易記錄，為其中所包含的所有候選k-項集的支援度計數加1。所有頻繁的k-項集被加入Fk中。

此過程直至Ck+1等于空集時結束。

算法  Apriori
Input:          Transaction DataBase D，Minimum support threshold minsup。
Output：      Frequent pattern L
() L1=search_frequent_1-itemsets( D );///生成頻繁一項集
() for(k=;Lk-≠φ;k++) do
() begin
()    Ck=apriori-gen(Lk-);//生成候選k項集
()    for all transactions t D do /// 掃描資料庫中的每一個事務t
()    begin
()      Ct=subset(Ck，t);//識别屬于t的所有候選項集
()      for all candidates c Ct do
()        c.count++;
()    end
()    Lk ={c Ck|c.count≥minsup}  //根據支援度來提取頻繁k項集
() end
() Answer L=∪kLk;
Procedure Search_frequent_1-itemsets( D )
(1) begin
(2)  for all transactions t D do
(3)  begin
(4)    for each item ik t do
(5)      ik.count++;
()  end
()  L1 ={ i I | i.count≥minsup}
()  return L1;
() end
Procedure apriori_gen(Lk)
(1) begin
(2)   for each itemset l1 Lk do
(3)     for each itemset l2 Lk do
(4)     begin
(5)       if ( l1[1]=l2[1]) ( l1[2]=l2[2]) … ( l1[k-1]=l2[k-1]) ( l1[k]<l2[k]) then
(6)       begin
(7)          c= l1 l2;//連接配接步
()          if Is_include_infrenquent_subset(c,Lk) then
()             delete c; //剪枝步
()         else add c to Ck+ ;
()       end
()      end
()    return Ck+ ;
() end
Procedure Is_include_infrenquent_subset(c,Lk)
(1)begin
(2)  for each k-subset s of c
(3)     if s Lk then
(4)       return TURE;
()  return FALSE ;
()end
           

在主程式中，第一步首先掃描整個交易資料庫D，統計每個項目(item)的支援數，計算其支援度，将支援度大于等于最小支援度minsup的項目構成的集合放入到L1 中；從第2步到第11步，用k-1頻繁項集構成的Lk-1生成候選集的集合Ck，以便從中生成Lk，其中apriori_gen函數(第4步)用來從Lk-1中生成Ck，然後對資料庫進行掃描(第5步)，對于資料庫中的每一個交易，subset函數用來發現此交易包含的所有候選集(第7步)，并為這些候選集的計數器加1(第8-9步)。最後滿足minsup的候選集被放入到Lk中。

apriori_gen 過程完成兩種操作：并(join)和剪枝(prune)。在并運算步驟中，Lk-1 與Lk-1 進行并運算生成潛在的候選集(2-7步)，條件l1[k-1]

2-2 FP-Growth算法

FP-Growth(頻繁模式增長)算法是韓家炜老師在2000年提出的關聯分析算法，它采取如下分治政策：将提供頻繁項集的資料庫壓縮到一棵頻繁模式樹（FP-Tree），但仍保留項集關聯資訊；該算法和Apriori算法最大的不同有兩點：第一，不産生候選集，第二，隻需要兩次周遊資料庫，大大提高了效率。

算法僞代碼

算法：FP-增長。使用FP-樹，通過模式段增長，挖掘頻繁模式。

輸入：事務資料庫D；最小支援度門檻值min_sup。

輸出：頻繁模式的完全集。

． 按以下步驟構造FP-樹：

(a) 掃描事務資料庫D 一次。收集頻繁項的集合F 和它們的支援度。對F 按支援度降序排序，結果為頻繁項表L。

(b) 建立FP-樹的根結點，以“null”标記它。對于D 中每個事務Trans，執行：選擇 Trans 中的頻繁項，并按L 中的次序排序。設排序後的頻繁項表為[p | P]，其中，p 是第一個元素，而P 是剩餘元素的表。調用insert_tree([p | P], T)。該過程執行情況如下。如果T 有子女N 使得N.item-name = p.item-name，則N 的計數增加；否則建立一個新結點N，将其計數設定為，連結到它的父結點T，并且通過結點鍊結構将其連結到具有相同item-name 的結點。如果P 非空，遞歸地調用insert_tree(P, N)。
           

procedure FP_growth(Tree, a)
if Tree 含單個路徑P then{
         for 路徑P中結點的每個組合（記作b）
         産生模式b U a，其支援度support = b 中結點的最小支援度；
} else {
         for each a i 在Tree的頭部(按照支援度由低到高順序進行掃描){
                  産生一個模式b = ai U a，其支援度support = ai .support；
                  構造b的條件模式基，然後構造b的條件FP-樹Treeb；
                  if Treeb 不為空 then
                            調用 FP_growth (Treeb, b)；
           }
}
FP-growth是整個算法的核心，再多啰嗦幾句。
FP-growth函數的輸入：tree是指原始的FPTree或者是某個模式的條件FPTree，a是指模式的字尾（在第一次調用時a=NULL，在之後的遞歸調用中a是模式字尾）
FP-growth函數的輸出：在遞歸調用過程中輸出所有的模式及其支援度（比如{I1,I2,I3}的支援度為）。每一次調用FP_growth輸出結果的模式中一定包含FP_growth函數輸入的模式字尾。
           

參考這裡

3 關聯算法Weka實作

3-1 Apriori關聯規則挖掘

對天氣的标稱資料進行Apriori關聯規則挖掘。

=== Run information ===

Scheme:       weka.associations.Apriori -N 10 -T 0 -C 0.9 -D 0.05 -U 1.0 -M 0.1 -S -1.0 -c -1
Relation:     weather.symbolic
Instances:    14
Attributes:   5
              outlook
              temperature
              humidity
              windy
              play
=== Associator model (full training set) ===


Apriori
=======

Minimum support: 0.15 (2 instances)
Minimum metric <confidence>: 0.9
Number of cycles performed: 17

Generated sets of large itemsets:
Size of set of large itemsets L(1): 12
Size of set of large itemsets L(2): 47
Size of set of large itemsets L(3): 39
Size of set of large itemsets L(4): 6

Best rules found:

 1. outlook=overcast 4 ==> play=yes 4    <conf:(1)> lift:(1.56) lev:(0.1) [1] conv:(1.43)
 2. temperature=cool 4 ==> humidity=normal 4    <conf:(1)> lift:(2) lev:(0.14) [2] conv:(2)
 3. humidity=normal windy=FALSE 4 ==> play=yes 4    <conf:(1)> lift:(1.56) lev:(0.1) [1] conv:(1.43)
 4. outlook=sunny play=no 3 ==> humidity=high 3    <conf:(1)> lift:(2) lev:(0.11) [1] conv:(1.5)
 5. outlook=sunny humidity=high 3 ==> play=no 3    <conf:(1)> lift:(2.8) lev:(0.14) [1] conv:(1.93)
 6. outlook=rainy play=yes 3 ==> windy=FALSE 3    <conf:(1)> lift:(1.75) lev:(0.09) [1] conv:(1.29)
 7. outlook=rainy windy=FALSE 3 ==> play=yes 3    <conf:(1)> lift:(1.56) lev:(0.08) [1] conv:(1.07)
 8. temperature=cool play=yes 3 ==> humidity=normal 3    <conf:(1)> lift:(2) lev:(0.11) [1] conv:(1.5)
 9. outlook=sunny temperature=hot 2 ==> humidity=high 2    <conf:(1)> lift:(2) lev:(0.07) [1] conv:(1)
10. temperature=hot play=no 2 ==> outlook=sunny 2    <conf:(1)> lift:(2.8) lev:(0.09) [1] conv:(1.29)

           

轉載于:https://www.cnblogs.com/mrzhang123/p/5365812.html