Windless
订阅/Feed
稗田千秋(i@wind.moe)

数据挖掘笔记其一 关联规则与Apriori

稗田千秋
Apr.07 2017 ai

开个新坑,作为数据挖掘这门课的学习笔记,前面的部分理论就暂且省去。

"啤酒与尿布"的故事想必各位都有听过,这种从海量数据中获取有用信息,寻找数据间隐含关系的方法叫做关联规则学习(Association rule learning)。好比平时购物时所推荐的购物信息,就是从其用户的活动情况来生成推荐。

基本概念

项集(Itemset):项目集合,如果包含k个项,称为 k-项集。

频繁项集(Frequent Itemsets):支持度不小于给予的最小支持度的非空项集。

最大频繁项集(Maximum Frequent Itemsets):不是被其他元素所包含的项集。

为方便描述,先定义 项目集合 $ I = \{i_1, i_2, ..., i_m\} $,事务数据库 $ D = \{t_1, t_2, ..., t_n\} $,每个事务 ti 对应 I 的一个子集。

支持度(Support):包含指定的项集A在数据集中所占的百分比,设 A ⊆ I,对于关联规则 A ⇒ B,有 $$ Support(A) = \frac{t \in D|A \subseteq I}{D} $$

置信度(Confidence):包含指定的项集A和另一个项集B的事务占指定事务A之比,设 A,B⊆ I 且 A ∩ B 不等于空集,对于关联规则 A ⇒ B,有 $$ Confidence(A \Rightarrow B) = \frac{Support(A \cup B)}{Support(A)} $$

关联规则(Association Rule):形如 X ⇒ Y 的蕴含式,即 $$ X \Rightarrow Y (X,Y \subseteq I,X \cap Y = \varnothing) $$

将满足最小支持度和最小置信度的关联规则称为 强关联规则(Strong Association Rule),通常所说的关联规则一般是指强关联规则。

一般的,关联规则挖掘分为两个子问题:根据支持度找出频繁项集 和 根据最大频繁项集找出关联规则,其中 Apriori 算法是发现频繁项集的常用算法之一。

Apriori 算法

Apriori算法的思想是先找出候选项集,然后根据所给的最小支持度筛选出频繁项集。

具体的一点描述是先找出所有的单项集,从中筛出频繁单项集,然后根据频繁单项集生成候选2-项集,接着筛出所有频繁2-项集,不断递归下去...

同时还用到了两个定理,暂略

算法描述

算法:Apriori (发现频繁项目集) 
输入:数据集D;最小支持度阈值minsup_count
输出:频繁项集L 
L1 = { large 1-itemsets };            //所有支持度不小于minsup_count的 1-项集
FOR( k=2; L_k − 1 ≠ Φ; k++) {
  C_k = apriori_gen(L_k−1);      // C_k 是k个元素的候选集 
  FOR all transactions t ∈D {
    C_t = subset(C_k, t);      // C_t 是所有t包含的候选集 
    FOR all candidates c∈C_t
      c.count++;             // 支持度计数增加
  } 
  L_k = { c∈C_k | c.count ≥ minsup_count }    // 提取频繁k-项集 
}
Return L=∪L_k;

函数:apriori_gen(L_k−1)  (候选集产生)
输入:(k-1)-频繁项目集L_k-1
输出:k-候选项目集C_k
FOR all itemset p∈L_k−1 
  FOR all itemset q∈L_k−1 
    IF p[1]=q[1] and … and p[k-2]=q[k-2] and p[k-1]<q[k-1]  THEN { 
      c = p∞q;           // 把q的第k-1个元素连到p后 
      IF has_infrequent_subset( c, L_k−1) THEN 
        delete c;      // 删除含有非频繁项目子集的候选元素
      ELSE 
        add c to C_k; 
    }
Return C_k; 

函数:has_infrequent_subset( c, L_k−1 )  (判断候选集的元素)
输入:一个k-候选项目集c,(k-1)-频繁项目集L__k1
输出:c是否从候选集中删除的布尔判断
FOR all ( k-1 )-subsets of c 
  IF s ∉L_k−1 THEN 
    Return TRUE; 
Return FALSE;
Python 实现
#!/usr/bin/env python3
# -*- coding: utf-8 -*-

from random import randint, sample

ALPHABET = list('ABCDE')


# 生成数据集
def generate_data(quantity: int = 20):
    return [sample(ALPHABET, randint(1, len(ALPHABET))) for i in range(quantity)]


# 构建单项集C_1
def generate_C1(dateset):
    C_1 = []
    for row in dateset:
        for item in row:
            if [item] not in C_1:
                C_1.append([item])
    C_1.sort()
    return list(map(frozenset, C_1))


# 筛选满足最小支持度的项集
def scan(transactions, C_k, minsup_count):
    Cnt, res, Freq = {}, [], {}
    for t in transactions:
        for c in C_k:
            if c.issubset(t):
                if c not in Cnt:
                    Cnt[c] = 1
                else:
                    Cnt[c] += 1

    for key in Cnt:
        if Cnt[key] >= minsup_count:
            res.append(key)
        Freq[key] = Cnt[key]
    return res, Freq


# 由频繁(k-1)-项集生成候选k-项集
def apriori_gen(L_k, k):
    res, length = [], len(L_k)
    for i in range(length):
        for j in range(i + 1, length):
            L1 = list(L_k[i])[:k - 2]
            L2 = list(L_k[j])[:k - 2]
            L1.sort()
            L2.sort()
            if L1 == L2:
                res.append(L_k[i] | L_k[j])
    return res

# 寻找频繁项目集
def apriori(dataset, minsup_count):
    C_1 = generate_C1(dataset)
    T = list(map(set, dataset))
    L_1, Freq = scan(T, C_1, minsup_count)
    L = [L_1]
    k = 2
    while len(L[k - 2]) > 0:
        C_k = apriori_gen(L[k - 2], k)
        L_k, FreqK = scan(T, C_k, minsup_count)
        Freq.update(FreqK)
        L.append(L_k)
        k += 1
    return L, Freq


data = generate_data()
L = apriori(data, 8)
[print(f"{item}=>{L[1][item]}") if item in L[1] else None for li in L[0] for item in li]

亦传于gist https://gist.github.com/chiaki64/3a43f44a8e53500a749aa2c44e808795

引用

--END--
文章创建于 2017-04-07 16:30:23,最后更新 2017-04-07 16:30:23
Comment
尝试加载Disqus评论, 失败则会使用基础模式.
    • play_arrow

    About this site

    version:1.02 Alpha
    博客主题: Lime
    联系方式: i@wind.moe
    写作语言: zh_CN & en_US
    博客遵循 CC BY-NC-SA 4.0许可进行创作

    此外,本博客会基于访客的Request Headers记录部分匿名数据用于统计(Logger的源码见Github),包含Referer, User-Agent & IP Address.个人绝不会主动将数据泄露给第三方