一. 基本概念

1.1 概述

? 關(guān)聯(lián)規(guī)則（Association Rules）反映一個(gè)事務(wù)與其他事務(wù)之間的相
互依存性和關(guān)聯(lián)性。如果兩個(gè)或者多個(gè)事務(wù)之間存在一定的關(guān)聯(lián)關(guān)
系毅访，那么，其中一個(gè)事務(wù)就能夠通過其他事務(wù)預(yù)測到兄猩。
? 關(guān)聯(lián)規(guī)則是無監(jiān)督的機(jī)器學(xué)習(xí)方法掌栅，用于知識發(fā)現(xiàn)，而非預(yù)測
? 關(guān)聯(lián)規(guī)則的學(xué)習(xí)器（learner）無需事先對訓(xùn)練數(shù)據(jù)進(jìn)行打標(biāo)簽操漠，因
為無監(jiān)督學(xué)習(xí)沒有訓(xùn)練這個(gè)步驟。缺點(diǎn)是很難對關(guān)聯(lián)規(guī)則學(xué)習(xí)器進(jìn)
行模型評估，一般都可以通過業(yè)務(wù)經(jīng)驗(yàn)觀測結(jié)果是否合理

1.2 相關(guān)概念

關(guān)聯(lián)規(guī)則之前浊伙，需要理解一些基本概念撞秋。
下圖數(shù)據(jù)集中，每一組數(shù)據(jù)ti表示不同的顧客一次在商場購買的商品
的集合嚣鄙，以該數(shù)據(jù)為例來說明關(guān)聯(lián)規(guī)則相關(guān)概念吻贿。

111.png

概念1-事務(wù)數(shù)據(jù)集

圖片顯示, 表中存儲(chǔ)著二維結(jié)構(gòu)的記錄集，記為D哑子，簡稱事務(wù)集D舅列，含事務(wù)的個(gè)數(shù)稱為|D|。那么圖片中從t1,t2,......直到t7含7個(gè)事務(wù)卧蜓，|D|=7帐要。

概念2-所有項(xiàng)集

設(shè)I={i1,i2,…im}是m個(gè)不同項(xiàng)目的集合，每個(gè)ik（k=1,2,…m）稱為一個(gè)項(xiàng)目(Item),I是所有項(xiàng)目(Item)的集合弥奸，稱為所有項(xiàng)集(Items)宠叼。圖片中所有項(xiàng)集I={牛肉，雞肉其爵，牛奶冒冬，奶酪，靴子摩渺，衣服}简烤，其中，“牛 肉”摇幻、“雞肉”等均為項(xiàng)目横侦。

概念3-事務(wù)

在事務(wù)數(shù)據(jù)集里的一筆記錄，記為事務(wù)T绰姻，{牛肉枉侧、雞肉、牛奶}便是一個(gè)事務(wù)狂芋，每個(gè)事務(wù)T（Transaction）是所有項(xiàng)集I的一個(gè)子集榨馁。

概念4-項(xiàng)集

項(xiàng)目的集合簡稱為項(xiàng)集（Itemset），其元素個(gè)數(shù)為項(xiàng)集的長度帜矾，長度為k的項(xiàng)集稱為k-項(xiàng)集（k-Itemset）翼虫。
如{牛肉}、{雞肉}均為1-項(xiàng)集屡萤，{牛肉珍剑、奶酪}為2-項(xiàng)集，{雞肉死陆、衣 服招拙、牛奶}為3-項(xiàng)集。

概念5-項(xiàng)集的支持度

重點(diǎn)概念5-項(xiàng)集的支持度：項(xiàng)集支持度用于描述X的重要性，對于項(xiàng)集X别凤，count為事務(wù)集D中包含X的事務(wù)的數(shù)量劈愚，項(xiàng)集X的支持度就是項(xiàng)集X出現(xiàn)的概率。

image.png

項(xiàng)集的支持度就是該項(xiàng)集出現(xiàn)的次數(shù)除以總的記錄數(shù)闻妓，例如，上述的7個(gè)事務(wù)中掠械，{牛肉由缆、雞肉}出現(xiàn)的次數(shù)是3次，支持度就是3/7 猾蒂。

image.png

概念6-最小支持度與頻繁集

我們在發(fā)現(xiàn)規(guī)則的時(shí)候均唉，希望關(guān)注頻次高的項(xiàng)集，發(fā)現(xiàn)關(guān)聯(lián)規(guī)則要求項(xiàng)集必須滿足的最小支持閾值肚菠，稱為項(xiàng)集的最小支持度（Minimum Support）舔箭，記為supmin。支持度大于或等于最小支持度的項(xiàng)集稱為頻繁項(xiàng)集蚊逢，簡稱頻繁集层扶，反之則稱為非頻繁集。支持度在這個(gè)算法中通常是人為規(guī)定的參數(shù)烙荷。

概念7-關(guān)聯(lián)規(guī)則的支持度（support）

規(guī)則R的支持度是交易集中同時(shí)包含X和Y的交易數(shù)與所有交易數(shù)之比镜会；

image.png

支持度計(jì)算在事務(wù)集中，既有A又有B的概率终抽。
例：在7條記錄中戳表，既有牛肉又有雞肉的記錄有3條，則 R:牛肉 雞肉的支持度為3/7昼伴，即 匾旭，表示在所有顧客當(dāng)中有3/7同時(shí)購買了牛肉和雞肉，其反映了同時(shí)購買牛肉和雞肉的顧客在所有顧客當(dāng)中的覆蓋范圍圃郊。

概念8-置信度（confidence）

規(guī)則R的置信度是指包含X和Y的交易數(shù)與包含X的交易數(shù)之比价涝。

image.png

規(guī)則的置信度的意義在于項(xiàng)集{X，Y}同時(shí)出現(xiàn)的次數(shù)占項(xiàng)集{X}出現(xiàn)次數(shù)的比例持舆，即發(fā)生X的條件下飒泻，又發(fā)生Y的概率。

image.png

image.png

關(guān)聯(lián)規(guī)則的最小支持度也就是衡量頻繁集的最小支持度（Minimum
Support）耙蔑，記為supmin见妒，它用于衡量規(guī)則需要滿足的最低重要性。
Minimum Support是一個(gè)閾值參數(shù)甸陌，必須在處理關(guān)聯(lián)規(guī)則之前指定該
參數(shù)须揣。該參數(shù)表示用戶對某些項(xiàng)集和規(guī)則感興趣，這些規(guī)則表示數(shù)
據(jù)集的最低支持度钱豁。它是用于對項(xiàng)集進(jìn)行限制耻卡，而不是對規(guī)則進(jìn)行
限制。

概念9-強(qiáng)關(guān)聯(lián)規(guī)則

? 如果關(guān)聯(lián)規(guī)則R: A→B滿足Support(A→B )>=supmin 且
Confidence( A→B )>=confmin,則稱關(guān)聯(lián)規(guī)則R: 為強(qiáng)關(guān)聯(lián)規(guī)則牲尺，否
則稱關(guān)聯(lián)規(guī)則為弱關(guān)聯(lián)規(guī)則;
? 在挖掘關(guān)聯(lián)規(guī)則時(shí)卵酪，產(chǎn)生的關(guān)聯(lián)規(guī)則要經(jīng)過supmin和confmin的衡量，
篩選出來的強(qiáng)關(guān)聯(lián)規(guī)則才能用于指導(dǎo)商家的決策;

概念10-提升度Lift

引入例題來計(jì)算這個(gè)概念谤碳，例：在所分析的10000個(gè)事務(wù)中溃卡，6000個(gè)事務(wù)包含計(jì)算機(jī)游戲，7500包含游戲機(jī)游戲蜒简，4000個(gè)事務(wù)同時(shí)包含兩者塑煎。
下面我們計(jì)算：關(guān)聯(lián)規(guī)則（計(jì)算機(jī)游戲 → 游戲機(jī)游戲）支持度=4000/10000=0.4，置信度=4000/6000=0.67臭蚁，但其實(shí)這個(gè)關(guān)聯(lián)規(guī)則是一個(gè)誤導(dǎo)最铁。

在用戶購買了計(jì)算機(jī)游戲后有（4000/6000）=0.667的概率去購買游戲機(jī)游戲，而在沒有任何前提條件下垮兑，用戶反而有（7500/10000） =0.75的概率去購買游戲機(jī)游戲冷尉，也就是說設(shè)置了購買計(jì)算機(jī)游戲這樣的條件反而會(huì)降低用戶去購買游戲機(jī)游戲的概率，所以計(jì)算機(jī)游戲和游戲機(jī)游戲是相斥的系枪。

此時(shí)需要引入提升度的概念雀哨。

image.png

如果兩個(gè)條件相互獨(dú)立，則P(XY)=P(X)· P(Y),即提升度為1私爷；如果小于1雾棺，說明使用這條規(guī)則來進(jìn)行推薦，還不如不推薦（推薦無效）衬浑；
一般在數(shù)據(jù)挖掘中當(dāng)提升度大于3時(shí)捌浩，我們才承認(rèn)挖掘出的關(guān)聯(lián)規(guī)則是有價(jià)值的。

上述例子中工秩，假設(shè)購買計(jì)算機(jī)游戲?yàn)閄尸饺，購買游戲機(jī)游戲?yàn)閅进统，則有提升度數(shù)=0.667/0.75<1

微信截圖_20211116162341.png

這表明這樣的推薦是無效的，提升度小于1浪听，還不如不推薦螟碎。

二. 算法步驟

2.1 生成頻繁項(xiàng)集

第一步，生成候選項(xiàng)集迹栓，然后根據(jù)指定的最小支持度掉分，過濾掉非頻繁項(xiàng)集，生成頻繁項(xiàng)集克伊。
該步驟需要多次遍歷：第一次遍歷酥郭，對所有單項(xiàng)的支持度進(jìn)行計(jì)數(shù)并確定頻繁項(xiàng)；在后續(xù)的每次遍歷中答毫，利用上一次遍歷所得頻繁項(xiàng)集作為種子項(xiàng)集，產(chǎn)生新的頻繁項(xiàng)集-候選項(xiàng)集季春，并對候選項(xiàng)集的支持度進(jìn)行計(jì)數(shù)洗搂，在本次遍歷結(jié)束時(shí)統(tǒng)計(jì)滿足最小支持度的候選項(xiàng)集，本次遍歷對應(yīng)的頻繁項(xiàng)集就算是確定了载弄，這些頻繁項(xiàng)集又成為下一次遍歷的種子耘拇；重復(fù)此遍歷過程，直到再不能發(fā)現(xiàn)新的頻繁項(xiàng)集宇攻。

2.2 生成關(guān)聯(lián)規(guī)則

第二步惫叛，找出第一步的頻繁項(xiàng)集中的規(guī)則，然后根據(jù)指定的最小置信度逞刷，過濾掉弱規(guī)則嘉涌。第一步的計(jì)算量比第二步的計(jì)算量大。

2.3 舉例說明

微信截圖_20211116163025.png

步驟1：
? 生成候選1-項(xiàng)集C1,計(jì)算支持度
? 根據(jù)最小支持度夸浅，生成頻繁1-項(xiàng)集L1

微信截圖_20211116163125.png

步驟2：
? 生成候選2-項(xiàng)集C2,計(jì)算支持度
? 根據(jù)最小支持度仑最，生成頻繁2-項(xiàng)集L2

微信截圖_20211116163209.png

微信截圖_20211116163310.png

? 生成關(guān)聯(lián)規(guī)則時(shí)帆喇，最簡單的方法就是對于每個(gè)頻繁項(xiàng)集警医，列出其所有非空
真子集，任取其中兩個(gè)分別作為LHS和RHS坯钦，形成關(guān)聯(lián)規(guī)則预皇，并計(jì)算每條關(guān)
聯(lián)規(guī)則的置信度，刪除弱規(guī)則
? 上例中 婉刀， 對于頻繁項(xiàng)集 {B,C,E} 吟温， 它的非空子集有 {B},{C},{E},
{B,C},{B,E},{C,E}。據(jù)此獲得的關(guān)聯(lián)規(guī)則及其置信度突颊，置信度>=50%(最小
置信度)溯街，都是強(qiáng)關(guān)聯(lián)規(guī)則

微信截圖_20211116163415.png

微信截圖_20211116163457.png

三. 關(guān)聯(lián)算法-Apriori

3.1 Apriori算法原理

? Apriori原理可以幫助減少計(jì)算量
? Apriori原理：某個(gè)項(xiàng)集是頻繁的诱桂，那么它的所有子集也是頻繁的；
更常用的是它的逆否命題呈昔，即如果一個(gè)項(xiàng)集是非頻繁的挥等，那么它的
所有超集也是非頻繁的（稱為項(xiàng)集的反單調(diào)性，向下閉合性）

已知陰影項(xiàng)集{2,3}是非頻繁的堤尾。利用Apriori原理肝劲，我們知道項(xiàng)集{0,2,3}， {1,2,3}以及{0,1,2,3}也是非頻繁的郭宝。也就是說辞槐，一旦計(jì)算出了{(lán)2,3}的支持 度 ， 知 道 它 是 非 頻 繁 的 粘室， 就 可 以 緊 接 著 排 除 {0,2,3} 榄檬， {1,2,3} 和 {0,1,2,3}。

微信截圖_20211116164119.png

? 反單調(diào)性能迅速剪枝衔统，提高搜索頻繁項(xiàng)集的處理效率

3.2 案例-銷售商品分析

在商品列表中找出頻繁項(xiàng)集,構(gòu)建商品列表鹿榜。

import pandas as pd
from matplotlib import pyplot as plt
from mlxtend.frequent_patterns import apriori, association_rules
import warnings
warnings.filterwarnings("ignore")

dataset = [['Milk', 'Onion', 'Nutmeg', 'Kidney Beans', 'Eggs', 'Yogurt'],
           ['Dill', 'Onion', 'Nutmeg', 'Kidney Beans', 'Eggs', 'Yogurt'],
           ['Milk', 'Apple', 'Kidney Beans', 'Eggs'],
           ['Milk', 'Unicorn', 'Corn', 'Kidney Beans', 'Yogurt'],
           ['Corn', 'Onion', 'Onion', 'Kidney Beans', 'Ice cream', 'Eggs']]

找出頻繁項(xiàng)集

創(chuàng)建模型，傳入數(shù)據(jù)锦爵，輸出的support就是支持度舱殿。

from mlxtend.preprocessing import TransactionEncoder
te = TransactionEncoder()
te_ary = te.fit_transform(dataset)

df = pd.DataFrame(te_ary, columns=te.columns_)
#選擇和過濾,設(shè)置支持度0.6以上，給項(xiàng)集加長度方便篩選
frequent_itemsets = apriori(df, min_support=0.6, use_colnames=True)
frequent_itemsets['length'] = frequent_itemsets['itemsets'].apply(lambda x:len(x))#增加一列存儲(chǔ)項(xiàng)集的長度
frequent_itemsets

該段輸出結(jié)果如下

image.png

接下來可以篩選支持度大于某特定值的二項(xiàng)集

image.png

找出關(guān)聯(lián)規(guī)則

rules = association_rules(frequent_itemsets,metric='lift',min_threshold=1.2)
rules["antecedent_len"] = rules['consequents'].apply(lambda x:len(x))
#選擇與過濾
rules[ (rules['antecedent_len'] >= 2) &
       (rules['confidence'] > 0.75) &
       (rules['lift'] > 1.2) ]

輸出結(jié)果

image.png