欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

[数据挖掘笔记 01] 关联规则Apriori算法

程序员文章站 2022-04-23 08:46:24
...

1.原理

关联规则用来找出事物之间的关联性,比如“如果小明买了面包,那么他也会买果汁”,下面我们通过一个实例来理解关联规则。

有这样一个交易数据集D,最小支持度为0.3,最小置信度为0.7,要求我们基于这个数据集求出商品间的关联规则。
[数据挖掘笔记 01] 关联规则Apriori算法
这里需要引入两个概念:

  • 支持度:Support(X) = X\frac{X在数据集中出现的次数}{数据集的条数}
  • 置信度:Confidence(X => Y) = XYX\frac{在有X的交易项中Y出现的次数}{X在数据集中出现的次数}

比如对于{牛肉}和{鸡肉},牛肉在数据集中出现的次数为4,那么Support({牛肉}) = 47\frac{4}{7},鸡肉在数据集中出现的次数为5,那么Support({鸡肉}) = 57\frac{5}{7}
在有牛肉的交易项中,鸡肉出现的次数为3,那么置信度Confidence({牛肉} => {鸡肉}) = 34\frac{3}{4} = 0.75。

(1)扫描数据集D,计算1-项集的支持度,筛选出频繁1-项集
最小支持度为0.3,交易条数为7,因此只要支持度计数大于 0.3 * 7 = 2.1,该项就是频繁项集。
[数据挖掘笔记 01] 关联规则Apriori算法
(2)根据频繁1-项集,连接生成候选2-项集,筛选出频繁2-项集
[数据挖掘笔记 01] 关联规则Apriori算法
(3)根据频繁2-项集,连接生成候选3-项集,筛选出频繁3-项集
[数据挖掘笔记 01] 关联规则Apriori算法
(4)计算置信度,生成强关联规则
如果一条关联规则的置信度 >= 最小置信度,我们就说这条关联规则是强关联规则。
对于频繁3-项集{牛奶,鸡肉,衣服}:
[数据挖掘笔记 01] 关联规则Apriori算法
对于频繁2-项集{牛肉,鸡肉}:
[数据挖掘笔记 01] 关联规则Apriori算法
其他关联规则的计算同理,依次计算就可以得出所有的关联规则。

2.代码实现

(1)原生代码

def load_data_set():
    
    data_set = [['牛肉','鸡肉','牛奶'],
                ['牛肉','奶酪'],
                ['奶酪','靴子'],
                ['牛肉','鸡肉','奶酪'],
                ['牛肉','鸡肉','衣服','奶酪','牛奶'],
                ['鸡肉','衣服','牛奶'],
                ['鸡肉','牛奶','衣服']]
    
    return data_set

'''创建候选1-项集'''
def create_C1(data_set):
    C1 = set() #1项集
    for t in data_set:  #遍历
        for item in t:
            item_set = frozenset([item])    #转换为不可变集合
            C1.add(item_set)    #加入1项集中
    return C1

'''判断频繁项集'''
def is_apriori(Ck_item, Lksub1):
    for item in Ck_item:    #遍历候选项集
        sub_Ck = Ck_item - frozenset([item])    #从候选项集中减去一项
        if sub_Ck not in Lksub1:    #如果该项集不在频繁(k-1)-项集中,则返回False
            return False
    return True

'''创建候选k-项集'''
def create_Ck(Lksub1, k):
    #Lksub1: 频繁(k-1)-项集
    Ck = set()  #候选k-项集
    len_Lksub1 = len(Lksub1)
    
    list_Lksub1 = list(Lksub1)
    for i in range(len_Lksub1): #遍历
        for j in range(1, len_Lksub1):
            l1 = list(list_Lksub1[i])
            l2 = list(list_Lksub1[j])
            l1.sort()
            l2.sort()
            if l1[0:k-2] == l2[0:k-2]:  #l1和l2的前n-1项如果相同
                Ck_item = list_Lksub1[i] | list_Lksub1[j]   #取并集
                if is_apriori(Ck_item, Lksub1): #如果属于频繁(k-1)-项集
                    Ck.add(Ck_item) #添加到候选项集中
    return Ck
    
'''筛选出频繁项集'''
def generate_Lk_by_Ck(data_set, Ck, min_support, support_data):
    Lk = set()  #频繁k-项集
    item_count = {} #计数集
    for t in data_set:  #遍历数据集
        for item in Ck: #遍历候选k-项集
            if item.issubset(t):    #如果item是t的子集
                if item not in item_count:  #如果item不在item_count中
                    item_count[item] = 1
                else:
                    item_count[item] += 1
    t_num = float(len(data_set))    #交易条数
    for item in item_count:
        if (item_count[item] / t_num) >= min_support:   #如果支持度大于等于最小支持度
            Lk.add(item)    #加入到频繁k-项集中
            support_data[item] = item_count[item] / t_num    #支持度数据
    return Lk

'''迭代计算频繁项集和支持度'''
def generate_L(data_set, k, min_support):
    support_data = {}   #支持度计数
    C1 = create_C1(data_set)    #建立候选1-项集
    L1 = generate_Lk_by_Ck(data_set, C1, min_support, support_data) #生成频繁1-项集
    Lksub1 = L1.copy()  #复制一份
    L = []  #总频繁项集
    L.append(Lksub1)    #加入频繁1-项集
    for i in range(2, k+1): 
        Ci = create_Ck(Lksub1, i)   #生成候选i-项集
        Li = generate_Lk_by_Ck(data_set, Ci, min_support, support_data) #生产频繁i-项集
        Lksub1 = Li.copy()  #复制一份
        L.append(Lksub1)    #加入频繁i-项集
    return L, support_data

'''生成关联规则'''
def generate_related_rules(L, support_data, min_conf):
    related_rule_list = []
    sub_set_list = []
    for i in range(0, len(L)):  #遍历总频繁项集
        for freq_set in L[i]:   #遍历单个频繁项集
            for sub_set in sub_set_list:    #遍历子集列表
                if sub_set.issubset(freq_set):  #如果子集是频繁项集的子集
                    #置信度 = 频繁项集的支持度 / 包含剩下项集的项集的支持度
                    conf = support_data[freq_set] / support_data[freq_set - sub_set]
                    related_rule = (freq_set - sub_set, sub_set, conf)  #关联规则
                    if conf >= min_conf and related_rule not in related_rule_list:
                        #print(freq_set - sub_set, "==>", sub_set, "conf:", conf)
                        related_rule_list.append(related_rule)  #强关联规则
            sub_set_list.append(freq_set)   #加入频繁项集到子集列表
    return related_rule_list

if __name__ == '__main__':
    #加载数据集
    data_set = load_data_set()
    #生成频繁项集和支持度
    L, support_data = generate_L(data_set, k=3, min_support=0.3)
    #生成关联规则
    related_rules_list = generate_related_rules(L, support_data, min_conf=0.7)
    #遍历输出
    for Lk in L:
        print("=" * 60)
        print("frequent " + str(len(list(Lk)[0])) + "-itemsets\t\tsupport")
        print("=" * 60)
        for freq_set in Lk:
            print(freq_set, support_data[freq_set])
    
    print("=" * 60)        
    print("Related Rules")
    for item in related_rules_list:
        print(item[0], "=>", item[1], "conf:", item[2])

运行结果:
[数据挖掘笔记 01] 关联规则Apriori算法
[数据挖掘笔记 01] 关联规则Apriori算法

(2)使用efficient_apriori库

通过命令行安装

pip install efficient-apriori

之后就可以运行如下代码

from efficient_apriori import apriori

data_set = [['牛肉','鸡肉','牛奶'],
                ['牛肉','奶酪'],
                ['奶酪','靴子'],
                ['牛肉','鸡肉','奶酪'],
                ['牛肉','鸡肉','衣服','奶酪','牛奶'],
                ['鸡肉','衣服','牛奶'],
                ['鸡肉','牛奶','衣服']]

itemsets, rules = apriori(data_set, min_support=0.3, min_confidence=0.7)
print(itemsets)	#生成频繁项集的支持度计数集
print("\n")
print(rules) #生成关联规则

运行结果:
[数据挖掘笔记 01] 关联规则Apriori算法

3.实战

我们知道王家卫是一个有名的香港导演,看过他的电影的人应该都知道,他来来去去就是用那几个演员,比如梁朝伟、张国荣、张曼玉,现在我们就用关联规则来看看墨镜王是怎么选用演员的。

首页要将参演王家卫电影的演员爬下来,我们打开王家卫的360百科,可以看到王家卫执导的电影和电影的演员。我们需要把电影名称和主要演员扒拉下来。
[数据挖掘笔记 01] 关联规则Apriori算法
这是爬取到的结果:
[数据挖掘笔记 01] 关联规则Apriori算法
爬取到演员列表,就可以使用efficient_apriori库进行关联规则挖掘了,代码如下:

import requests
from lxml import etree
from requests.exceptions import RequestException
from efficient_apriori import apriori

data_dict = {}

def get_html():
    url = 'https://baike.so.com/doc/1517409-1604273.html'
    headers = {
                    "User-Agent":"Mozilla/5.0 (Windows NT 10.0; Win64; x64) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/80.0.3987.87 Safari/537.36"
            }
    
    try:
        response = requests.get(url,headers=headers)
        if response.status_code == 200:
            return response.content.decode('utf-8')
        return None
    except RequestException:
        return None

def parse_html(html):
    xpath_html = etree.HTML(html)
    for item in xpath_html.xpath('//div[@id="main-content-text"]/div[2]/div[1]//tr[td]')[:-1]:
        if item.xpath('./td')[1].text:
            movie = item.xpath('./td')[1].text
        else:
            movie = item.xpath('./td/a')[0].text
        if movie == '东邪西毒':
            actors_list =[x.text for x in item.xpath('./td[2]//a')]
        else:
            actors_list =[x.text for x in item.xpath('./td[3]//a')]
        data_dict[movie] = actors_list
    return data_dict

if __name__ == '__main__':
    html = get_html()
    parse_html(html)
    print(data_dict)
    print("\n")
    
    data_set = [item[1] for item in data_dict.items()]
    print(data_set)
    print("\n")
    itemsets, rules = apriori(data_set, min_support=0.3, min_confidence=0.6)
    print(itemsets)
    print("\n")
    print(rules)

运行结果:
[数据挖掘笔记 01] 关联规则Apriori算法
梁朝伟、刘嘉玲、张曼玉、张学友、张国荣是王家卫最喜欢用的演员,其中梁朝伟出演电影次数达8次,可以说是御用演员了。

相关标签: 数据挖掘