数据挖掘大作业1记录
一、简介
频繁模式和关联规则
大量数据中的频繁模式、关联和相关关系的发现，在选中市场、决策分析和商务关联方面是有用的。一个流行的应用领域是购物篮分析，通过搜索经常一块（或依次）购买的商品的集合，研究顾客的购买习惯，以发现一些隐藏的、有趣的规则。典型的如顾客购买啤酒的时候很有可能会购买尿布。关联规则挖掘首先找出频繁项集（项的集合，如A和B，满足最小支持度阀值，或任务相关元组的百分比），然后，由它们产生形如A=>B的强关联规则。这些规则也满足最小置信度阀值（预定义的、在满足A的条件下满足B的概率）。进一步分析关联，发现项集A和B之间具有统计相关的相关规则。
对于频繁模式的挖掘，已有许多有效的、可伸缩的算法，由它们可以导出关联和相关规则，书上介绍了Apriori和FP-growth两种算法，在mlxtend包中都有，我决定使用FP-growth算法
FP-growth算法
FP-Growth(频繁模式增长算法是韩嘉炜等人在2000年提出的关联分析算法，它采取如下分治策略：将提供频繁项集的数据库压缩到一棵频繁模式树（FP-tree），但仍保留项集关联信息。在算法中使用了一种称为频繁模式树（Frequent Pattern Tree）的数据结构。FP-tree是一种特殊的前缀树，由频繁项头表和项前缀树构成。FP-Growth算法基于以上的结构加快整个挖掘过程。
相比Apriori算法需要多次扫描数据库，FP-growth只需要对数据库扫描2次。第1次扫描获得当个项目的频率，去掉不满足支持度要求的项，并对剩下的项排序。第2次扫描建立一颗FP-Tree树。
挖掘频繁模式前首先要构造FP-Tree，输入一个交易数据库DB和一个最小支持度threshold，输出:它的FP-tree.
二、软件环境准备
Visual Studio Code
Anaconda3
在Anaconda中安装pandas和mlxtend
conda install -c conda-forge mlxtend
conda install -c conda-forge pandas
mlxtend-master程序源码（https://github.com/rasbt/mlxtend）
淘宝的用户行为数据集（https://tianchi.aliyun.com/dataset/dataDetail?dataId=649）
使用pip安装包时使用国内源，否则可能超时报错
pip install -i https://pypi.tuna.tsinghua.edu.cn/simple mlxtend
在使用vs2019安装python后要设置环境变量，在系统变量>path中添加C:\Program Files (x86)\Microsoft Visual Studio\Shared\Python37_64\Scripts，否则会提示pip等不是命令
三、作业基本思路
- 读懂mlxtend中的FP-growth算法部分，了解其原理和大致过程
- 在jupyter notebook中建立python3文件
- 通过Pandas读入数据，首先对数据进行观察：有无索引、标号、有没有数据缺失
- 数据预处理
- 频繁模式挖掘
- 结果分析
四、算法分析
在vscode中打开mlxtend-master文件夹
mlxtend-master\docs\sources\user_guide\frequent_patterns路径下可以找到介绍文档fpgrowth.ipynb，最好用jupyter notebook打开。
mlxtend-master\mlxtend\frequent_patterns路径下可以找到FP-growth和挖掘关联规则相关代码，
主要涉及三个文件的代码，fpgrowth.py是最后用到的主函数，其中调用的大多数函数在fpcommon.py中，输入一个数据集、最小支持度、是否使用列名、最大频繁度、是否显示树生成过程，返回支持度和频繁项集的列表。association_rules.py是关联规则挖掘的算法。
-
实际过程只用两个函数
fpgrowth(df, min_support, use_colnames, max_len, verbose):
association_rules(df, metric, min_threshold, support_only):
代码的具体分析见附录，之前没有python基础，根据自己理解进行了注解(谷歌机翻)，可能有误。
FP-growth简要步骤
- 检查数据，有错就抛出异常
- 将数据的列名组合为一个索引序列
- 调用setup_fptree建立FP树，
- 判断数据是否稀疏，计算每项的支持度
- 去掉支持度小于最小支持度的项，生成频繁1项的一维列表
- 定义要插入FP树的项目的排序
- 构建FP树，包含根节点、节点、子树和排序，每个节点包含内容、出现次数、父节点和子节点
- 构建FP树过程参考此视频 https://www.bilibili.com/video/BV1LJ411W7rD
- 计算支持度计数
- 执行fpgrowth算法的递归步骤。
- 如果树只有一条路径，可以组合生成所有剩余项集
- 生成子树以生成更大的频繁项集
- 生成支持度和项集的列表
挖掘关联规则
搬运自教材P164
一旦由数据库D中的事务找出频繁项集，就可以直接由它们产生强关联规则（强关联规则满足最小支持度和最小置信度）。对于置信度，可以用下式计算。
confidence(A=>B)= P(A|B) = support_count(AUB) / support_count(A)
条件概率用项集的支持度计数表示，其中， support_count（AUB）是包含项集AUB的事务数，而 support_count(A)是包含项集A的事务数。根据该式，关联规则可以产生如下：
对于每个频繁项集l，产生l的所有非空子集。
-
对于l的每个非空子集s，如果support_count(t) / support_count(s)≥min_conf,则输出规则"s=(l-s)。"
其中，min_conf是最小置信度阈值。
由于规则由频繁项集产生，因此每个规则都自动地满足最小支持度。频繁项集和它们的支持度可以预先存放在散列表中，使得它们可以被快速访问。
mlxtend示例 http://rasbt.github.io/mlxtend/user_guide/frequent_patterns/association_rules/
mlxtend使用了 DataFrame 方式来描述关联规则，而不是 —> 符号，其中：
- antecedents：规则先导项
- consequents：规则后继项
- antecedent support：规则先导项支持度
- consequent support：规则后继项支持度
- support：规则支持度 （前项后项并集的支持度）
- confidence：规则置信度 （规则置信度：规则支持度support / 规则先导项）
- lift：规则提升度，表示含有先导项条件下同时含有后继项的概率，与后继项总体发生的概率之比。
- leverage：规则杠杆率，表示当先导项与后继项独立分布时，先导项与后继项一起出现的次数比预期多多少。
- conviction：规则确信度，与提升度类似，但用差值表示。
五、实验步骤
打开anconda命令行进入合适位置
输入jupyter notebook进入编辑环境，新建python3文件
-
数据预处理
import pandas as pd # 导入Pandasdata = pd.read_csv('data_buy.csv', header=None) # 读入解压好的 csv 文件到 data 变量中 #这里pd.read_csv是将数据一次性读入内存，可以使用分块读取等方法-
data.info() # 先看一下读入的数据信息<class 'pandas.core.frame.DataFrame'> RangeIndex: 100150807 entries, 0 to 100150806 Data columns (total 5 columns): # Column Dtype --- ------ ----- 0 0 int64 1 1 int64 2 2 int64 3 3 object 4 4 int64 dtypes: int64(4), object(1) memory usage: 3.7+ GB -
data.head() # 查看数据前5行0 1 2 3 4 0 1 2268318 2520377 pv 1511544070 1 1 2333346 2520771 pv 1511561733 2 1 2576651 149192 pv 1511572885 3 1 3830808 4181361 pv 1511593493 4 1 4365585 2520377 pv 1511596146 现在表格没有列名称，不方便处理，我们可以手动添加
# 用户ID，商品ID，商品类目ID，行为类型，时间戳 data.columns = ['user', 'item', 'category', 'behavior', 'timestamp']-
data.head() # 再来看一下数据user item category behavior timestamp 0 1 2268318 2520377 pv 1511544070 1 1 2333346 2520771 pv 1511561733 2 1 2576651 149192 pv 1511572885 3 1 3830808 4181361 pv 1511593493 4 1 4365585 2520377 pv 1511596146 -
# 将时间戳转换为时间格式,读入数据按秒计算 data['time']=pd.to_datetime(data['timestamp'],unit='s') data.head()user item category behavior timestamp time 0 1 2268318 2520377 pv 1511544070 2017-11-24 17:21:10 1 1 2333346 2520771 pv 1511561733 2017-11-24 22:15:33 2 1 2576651 149192 pv 1511572885 2017-11-25 01:21:25 3 1 3830808 4181361 pv 1511593493 2017-11-25 07:04:53 4 1 4365585 2520377 pv 1511596146 2017-11-25 07:49:06 -
# 提取出时间的小时 data = data.drop(columns=['timestamp']) data['daily'] = data['time'].dt.hour data.head()user item category behavior time daily 0 1 2268318 2520377 pv 2017-11-24 17:21:10 17 1 1 2333346 2520771 pv 2017-11-24 22:15:33 22 2 1 2576651 149192 pv 2017-11-25 01:21:25 1 3 1 3830808 4181361 pv 2017-11-25 07:04:53 7 4 1 4365585 2520377 pv 2017-11-25 07:49:06 7 -
# 分组统计每个时间段发生的各种行为 table_time = data.groupby(['daily','behavior']).size().unstack() table_time.head()behavior buy cart fav pv daily 0 64917 192036 103721 3043136 1 96134 229890 127976 3729408 2 127933 266963 147752 4335949 3 122048 260831 145412 4214991 4 118591 255811 140862 4257521 -
# 画出柱状图，非堆叠，横轴标注不旋转，规定尺寸 table_time.plot.bar(stacked=False,rot=0,figsize=(16,7))<matplotlib.axes._subplots.AxesSubplot at 0x28e81de33c8>
table_time 用户行为有四种：pv（点击）、cart（加购）、fav（收藏）、buy（购买）
从图中可以看到 ，用户行为高峰在中午时间段，上午相对比较平稳，下午两点后开始下降到九点， 数据集包含了2017年11月25日至2017年12月3日之间,有两个周末，可能使用户活跃时间偏早。部分用户在深夜活跃，可能与商家活动有关。但是由于pv量显著高于其他用户行为的发生，因此需要根据不同行为进行研究。
# 去掉pv量后重新画图 table_time1 = table_time.drop(columns=['pv']) table_time1.plot.bar(stacked=False,rot=0,figsize=(16,7))<matplotlib.axes._subplots.AxesSubplot at 0x28e8215f848>
Ga4IOI.png 可以看到用户的其他行为趋势大致相同
我们的目的是挖掘用户购买商品类别间的频繁模式和关联规则，下面开始正式的数据预处理。
-
# 去除具体商品信息，时间信息，只看用户对某类商品的操作数据 data=data.drop(columns=['item', 'time', 'daily']) data.head()user category behavior 0 1 2520377 pv 1 1 2520771 pv 2 1 149192 pv 3 1 4181361 pv 4 1 2520377 pv -
# 若只关注用户购买行为 data=data[data['behavior']=='buy'] # 按照用户和商品种类去重 data=data.drop_duplicates(['user','category']).copy() data.head()user category behavior 71 100 2951233 buy 73 100 4869428 buy 100 100 2429887 buy 119 100 3002561 buy 125 100 4098232 buy -
# 先转换DataFrame数据为包含数据的列表，后续挖掘时再转换回来 data_list = data.groupby('user')['category'].apply(list) data_list[:5] # 查看列表前5行user
2 [2865017, 1849958, 2925160, 3439012, 2885642, ...
4 [2465336, 4145813, 4801426]
11 [3102419]
16 [3248072, 3898483]
17 [3702593]
Name: category, dtype: object -
transactions = list(data_list) transactions[:5][[2865017, 1849958, 2925160, 3439012, 2885642, 4159072],
[2465336, 4145813, 4801426],
[3102419],
[3248072, 3898483],
[3702593]] # 保存清洗后的数据 import json json.dump(transactions, open('transactions.json', 'w'))
-
频繁模式和关联规则
-
由于mlxtend的模型只接受特定的数据格式。
TransactionEncoder类似于独热编码，每个值转换为一个唯一的bool值
import pandas as pd import json # 传入模型的数据需要满足特定的格式，可以用这种方法来转换为bool值，也可以用函数转换为0、1 from mlxtend.preprocessing import TransactionEncoder # 导入Apriori算法、fpgrowth算法和导入关联规则 from mlxtend.frequent_patterns import apriori, fpgrowth from mlxtend.frequent_patterns import association_rules # 导入预处理好的数据“transactions.json” dataset = json.load(open('transactions.json'))-
# 使用FP-Growth算法挖掘频繁项集，最小支持度取值0.001 te = TransactionEncoder() te_ary = te.fit(dataset).transform(dataset) df = pd.DataFrame(te_ary, columns=te.columns_) frequent_itemsets = fpgrowth(df, min_support=0.001) frequent_itemsets # 频繁项集support itemsets 0 0.040330 (3973) 1 0.023215 (5751) 2 0.004299 (4765) 3 0.002152 (4030) 4 0.040941 (5734) ... ... ... 598 0.001825 (3627, 3541) 599 0.001126 (3449, 1790) 600 0.001038 (3449, 3766) 601 0.001208 (3449, 1349) 602 0.001048 (3449, 5734) 603 rows × 2 columns
-
-
# 获取置信度>=0.1的关联规则，并按提升度倒序排列 association_rules(frequent_itemsets, metric="confidence", min_threshold=0.1).sort_values('lift', ascending=False)antecedents consequents antecedent support consequent support support confidence lift leverage conviction 20 (6020) (3627) 0.004004 0.021094 0.001220 0.304606 14.440105 0.001135 1.407700 22 (3541) (3627) 0.007655 0.021094 0.001825 0.238391 11.301132 0.001663 1.285313 14 (5148) (3627) 0.012316 0.021094 0.002098 0.170390 8.077478 0.001839 1.179959 13 (1421) (2563) 0.014085 0.015971 0.001597 0.113399 7.100270 0.001372 1.109889 12 (2563) (1421) 0.015971 0.014085 0.001597 0.100009 7.100270 0.001372 1.095472 11 (2563) (1763) 0.015971 0.017494 0.001617 0.101220 5.785993 0.001337 1.093155 19 (194) (1790) 0.014359 0.022164 0.001605 0.111756 5.042266 0.001286 1.100864 0 (3973) (5751) 0.040330 0.023215 0.004433 0.109927 4.735128 0.003497 1.097421 1 (5751) (3973) 0.023215 0.040330 0.004433 0.190967 4.735128 0.003497 1.186194 15 (194) (1349) 0.014359 0.031514 0.001979 0.137856 4.374467 0.001527 1.123346 8 (1790) (1349) 0.022164 0.031514 0.002790 0.125881 3.994464 0.002092 1.107957 10 (3235) (1349) 0.015650 0.031514 0.001872 0.119643 3.796518 0.001379 1.100106 2 (3375) (6609) 0.016750 0.033797 0.002137 0.127586 3.775105 0.001571 1.107505 9 (1790) (6609) 0.022164 0.033797 0.002475 0.111655 3.303741 0.001726 1.087645 7 (1349) (6609) 0.031514 0.033797 0.003409 0.108164 3.200443 0.002344 1.083387 6 (6609) (1349) 0.033797 0.031514 0.003409 0.100858 3.200443 0.002344 1.077123 4 (3450) (6609) 0.013959 0.033797 0.001475 0.105689 3.127213 0.001004 1.080389 3 (5831) (6542) 0.018534 0.035327 0.001910 0.103033 2.916559 0.001255 1.075484 17 (194) (5734) 0.014359 0.040941 0.001486 0.103470 2.527278 0.000898 1.069745 5 (1349) (3766) 0.031514 0.042770 0.003267 0.103681 2.424128 0.001920 1.067956 16 (194) (3766) 0.014359 0.042770 0.001452 0.101088 2.363492 0.000837 1.064875 21 (6593) (2003) 0.020254 0.044546 0.002092 0.103312 2.319203 0.001190 1.065536 18 (194) (2003) 0.014359 0.044546 0.001465 0.102020 2.290203 0.000825 1.064003
六、代码分析
fpgrowth.py:
import math
import itertools
from ..frequent_patterns import fpcommon as fpc
def fpgrowth(df, min_support=0.5, use_colnames=False, max_len=None, verbose=0):
"""从一键式DataFrame获取频繁项集
参数
-----------
df : pandas DataFrame
pandas DataFrame的编码格式。 还支持具有稀疏数据的DataFrames
请注意，旧的pandas SparseDataFrame格式在mlxtend> = 0.17.2中不再受支持。
允许的值为0/1或True / False。
举例,
Apple Bananas Beer Chicken Milk Rice
0 True False True True False True
1 True False True False False True
2 True False True False False False
3 True True False False False False
4 False False True True True True
5 False False True False True True
6 False False True False True False
7 True True False False False False
min_support : float (default: 0.5)
0到1之间的浮点数，用于最小程度地支持返回的项目集。
相对支持度=发生项目的交易 / 总交易.
use_colnames : bool (default: False)
如果为true，则在返回的DataFrame中使用DataFrame的列名而不是列索引。
max_len : int (default: None)
生成的项目集的最大长度。 如果全部为“无”（默认）,评估可能的项目集长度。
verbose : int (default: 0)
显示条件树生成的阶段。
Returns
-----------
pandas DataFrame with columns ['support', 'itemsets'] of all itemsets
that are >= `min_support` and < than `max_len`
(if `max_len` is not None).
Each itemset in the 'itemsets' column is of type `frozenset`,
这是Python内置类型，其行为类似于设置，它是不可变的
"""
fpc.valid_input_check(df) #检查输入的数据
# 输入的最小支持度<=0，抛出异常
if min_support <= 0.:
raise ValueError('`min_support` must be a positive '
'number within the interval `(0, 1]`. '
'Got %s.' % min_support)
# 将数据的列名组合为一个索引序列
colname_map = None
if use_colnames:
colname_map = {idx: item for idx, item in enumerate(df.columns)}
tree = fpc.setup_fptree(df, min_support) #建立FP树
# 最小支持度计数 = 总数*相对支持度，index返回索引
minsup = math.ceil(min_support * len(df.index))
generator = fpg_step(tree, minsup, colname_map, max_len, verbose) #生成树
return fpc.generate_itemsets(generator, len(df.index), colname_map)
def fpg_step(tree, minsup, colnames, max_len, verbose):
"""
执行fpgrowth算法的递归步骤。
参数
----------
tree : FPTree
minsup : int
产量
------
字符串列表
minsup项目集中已发生的项目集。
"""
count = 0
items = tree.nodes.keys()
if tree.is_path():
# 如果树只有一条路径，可以组合生成所有剩余项集，而无需生成其他条件树
size_remain = len(items) + 1
if max_len:
size_remain = max_len - len(tree.cond_items) + 1
for i in range(1, size_remain):
for itemset in itertools.combinations(items, i):
count += 1
support = min([tree.nodes[i][0].count for i in itemset])
yield support, tree.cond_items + list(itemset)
elif not max_len or max_len > len(tree.cond_items):
for item in items:
count += 1
support = sum([node.count for node in tree.nodes[item]])
yield support, tree.cond_items + [item]
if verbose:
tree.print_status(count, colnames)
# 生成子树以生成更大的频繁项集
if not tree.is_path() and (not max_len or max_len > len(tree.cond_items)):
for item in items:
cond_tree = tree.conditional_tree(item, minsup)
for sup, iset in fpg_step(cond_tree, minsup,
colnames, max_len, verbose):
yield sup, iset
fpcommon.py:
import numpy as np
import pandas as pd
import collections
from distutils.version import LooseVersion as Version
from pandas import __version__ as pandas_version
def setup_fptree(df, min_support):
num_itemsets = len(df.index) #数据库中项目集的数量
# 判断df是否是稀疏的
is_sparse = False
if hasattr(df, "sparse"):
# 稀疏的DataFrame (pandas >= 0.24)
if df.size == 0:
itemsets = df.values
else:
itemsets = df.sparse.to_coo().tocsr() #转换为稀疏的
is_sparse = True
else:
# 稠密的DataFrame
itemsets = df.values
# 每个项目的支持度
# 如果项目集稀疏，则np.sum返回形状为（1，N）的np.matrix矩阵
item_support = np.array(np.sum(itemsets, axis=0) / float(num_itemsets))
# 不分行列改成一串
item_support = item_support.reshape(-1)
# 去掉小于设定的最小支持度的项，完成频繁一项集
items = np.nonzero(item_support >= min_support)[0]
# 定义要插入FPTree的项目的排序
# argsort()返回的是支持度从小到大的索引值。
# enumerate()将数据组合为一个索引序列，完成F-list
indices = item_support[items].argsort()
rank = {item: i for i, item in enumerate(items[indices])}
# 根据顺序插入项目集来构建树
# 为了减少树大小，插入按最频繁到最不频繁的顺序进行
tree = FPTree(rank)
for i in range(num_itemsets):
if is_sparse:
# 项目集已转换为CSR格式，以加快以下行的速度。 它具有3个属性：
# - itemsets.data 包含非null值, shape(#nnz,)
# - itemsets.indices 包含非空元素的列数, shape(#nnz,)
# - itemsets.indptr[i] 包含第i行中第一个非null元素的itemet.indices中的偏移量, shape(1+#nrows,)
nonnull = itemsets.indices[itemsets.indptr[i]:itemsets.indptr[i+1]]
else:
nonnull = np.where(itemsets[i, :])[0]
itemset = [item for item in nonnull if item in rank]
itemset.sort(key=rank.get, reverse=True)
tree.insert_itemset(itemset)
return tree, rank
# 生成支持度和项集的列表
def generate_itemsets(generator, num_itemsets, colname_map):
itemsets = []
supports = []
for sup, iset in generator:
itemsets.append(frozenset(iset))
supports.append(sup / num_itemsets)
res_df = pd.DataFrame({'support': supports, 'itemsets': itemsets})
if colname_map is not None:
res_df['itemsets'] = res_df['itemsets'] \
.apply(lambda x: frozenset([colname_map[i] for i in x]))
return res_df
# 检查数据，有错抛出异常
def valid_input_check(df):
if f"{type(df)}" == "<class 'pandas.core.frame.SparseDataFrame'>":
msg = ("SparseDataFrame support has been deprecated in pandas 1.0,"
" and is no longer supported in mlxtend. "
" Please"
" see the pandas migration guide at"
" https://pandas.pydata.org/pandas-docs/"
"stable/user_guide/sparse.html#sparse-data-structures"
" for supporting sparse data in DataFrames.")
raise TypeError(msg)
if df.size == 0:
return
if hasattr(df, "sparse"):
if not isinstance(df.columns[0], str) and df.columns[0] != 0:
raise ValueError('Due to current limitations in Pandas, '
'if the sparse format has integer column names,'
'names, please make sure they either start '
'with `0` or cast them as string column names: '
'`df.columns = [str(i) for i in df.columns`].')
# 捷径: 如果所有列均为布尔值，则无需检查
all_bools = df.dtypes.apply(pd.api.types.is_bool_dtype).all()
if not all_bools:
# Pandas比numpy慢得多，因此在Numpy数组上使用np.where
if hasattr(df, "sparse"):
if df.size == 0:
values = df.values
else:
values = df.sparse.to_coo().tocoo().data
else:
values = df.values
idxs = np.where((values != 1) & (values != 0))
if len(idxs[0]) > 0:
# idxs具有稀疏数据的1维和密集数据的2维
val = values[tuple(loc[0] for loc in idxs)]
s = ('The allowed values for a DataFrame'
' are True, False, 0, 1. Found value %s' % (val))
raise ValueError(s)
# 构建FP树
class FPTree(object):
def __init__(self, rank=None):
self.root = FPNode(None)
self.nodes = collections.defaultdict(list)
self.cond_items = []
self.rank = rank
def conditional_tree(self, cond_item, minsup):
"""
创建并返回以cond_item为条件的self的子树。
参数
----------
cond_item : int | str
树（自身）将作为条件的项目。
minsup : int
最低支持阈值。
Returns
-------
cond_tree : FPtree
"""
# 查找从根节点到项目节点的所有路径
branches = []
count = collections.defaultdict(int)
for node in self.nodes[cond_item]:
branch = node.itempath_from_root()
branches.append(branch)
for item in branch:
count[item] += node.count
# 定义新的顺序或深层树可能组合爆炸??
items = [item for item in count if count[item] >= minsup]
items.sort(key=count.get)
rank = {item: i for i, item in enumerate(items)}
# 创建条件树
cond_tree = FPTree(rank)
for idx, branch in enumerate(branches):
branch = sorted([i for i in branch if i in rank],
key=rank.get, reverse=True)
cond_tree.insert_itemset(branch, self.nodes[cond_item][idx].count)
cond_tree.cond_items = self.cond_items + [cond_item]
return cond_tree
def insert_itemset(self, itemset, count=1):
"""
将项目列表插入树中。
参数
----------
itemset : list
将插入树中的项目。
count : int
项目集的出现次数。
"""
self.root.count += count
if len(itemset) == 0:
return
# 尽可能遵循树中的现有路径
index = 0
node = self.root
for item in itemset:
if item in node.children:
child = node.children[item]
child.count += count
node = child
index += 1
else:
break
# 插入所有剩余的项目
for item in itemset[index:]:
child_node = FPNode(item, count, node)
self.nodes[item].append(child_node)
node = child_node
#判断树是否是一条路径
def is_path(self):
if len(self.root.children) > 1:
return False
for i in self.nodes:
if len(self.nodes[i]) > 1 or len(self.nodes[i][0].children) > 1:
return False
return True
def print_status(self, count, colnames):
cond_items = [str(i) for i in self.cond_items]
if colnames:
cond_items = [str(colnames[i]) for i in self.cond_items]
cond_items = ", ".join(cond_items)
print('\r%d itemset(s) from tree conditioned on items (%s)' %
(count, cond_items), end="\n")
#构建节点
class FPNode(object):
def __init__(self, item, count=0, parent=None):
self.item = item
self.count = count
self.parent = parent
self.children = collections.defaultdict(FPNode)
if parent is not None:
parent.children[item] = self
# 返回自上而下的项目的顺序，从自身（但不包括）到根节点。
def itempath_from_root(self):
path = []
if self.item is None:
return path
# append() 方法用于在列表末尾添加新的对象。
node = self.parent
while node.item is not None:
path.append(node.item)
node = node.parent
# reverse() 函数用于反向列表中元素。
path.reverse()
return path
association_rules.py:
from itertools import combinations
import numpy as np
import pandas as pd
def association_rules(df, metric="confidence",
min_threshold=0.8, support_only=False):
"""生成包括规则“得分”，“可信度”和“提升度”的关联规则的DataFrame
参数
-----------
df : pandas DataFrame
['support', 'itemsets']构成的频繁项集
metric : string (default: 'confidence')
评估规则是否有意义的度量。
**自动设置为 'support' if `support_only=True`.**
Otherwise, supported metrics are 'support', 'confidence', 'lift',
'leverage', and 'conviction'
These metrics are computed as follows:
- support(A->C) = support(A+C) [aka 'support'], range: [0, 1]\n
- confidence(A->C) = support(A+C) / support(A), range: [0, 1]\n
- lift(A->C) = confidence(A->C) / support(C), range: [0, inf]\n
- leverage(A->C) = support(A->C) - support(A)*support(C),
range: [-1, 1]\n
- conviction = [1 - support(C)] / [1 - confidence(A->C)],
range: [0, inf]\n
min_threshold : float (default: 0.8)
评估指标的最低阈值，以确定是否有候选规则感兴趣。
support_only : bool (default: False)
仅计算支持度，并用NaN填充其他指标列。 这在以下情况下有用：
a) 输入的DataFrame不完整，例如不包含所有规则前提的支持值和结果
b) 您只是想加快计算速度，因为您不需要其他指标。
Returns
----------
pandas DataFrame with columns "antecedents" and "consequents"
that store itemsets, plus the scoring metric columns:
"antecedent support", "consequent support",
"support", "confidence", "lift",
"leverage", "conviction"
of all rules for which
metric(rule) >= min_threshold.
Each entry in the "antecedents" and "consequents" columns are
of type `frozenset`, which is a Python built-in type that
behaves similarly to sets except that it is immutable
"""
# check for mandatory columns
if not all(col in df.columns for col in ["support", "itemsets"]):
raise ValueError("Dataframe needs to contain the\
columns 'support' and 'itemsets'")
def conviction_helper(sAC, sA, sC):
confidence = sAC/sA
conviction = np.empty(confidence.shape, dtype=float)
if not len(conviction.shape):
conviction = conviction[np.newaxis]
confidence = confidence[np.newaxis]
sAC = sAC[np.newaxis]
sA = sA[np.newaxis]
sC = sC[np.newaxis]
conviction[:] = np.inf
conviction[confidence < 1.] = ((1. - sC[confidence < 1.]) /
(1. - confidence[confidence < 1.]))
return conviction
# metrics for association rules
metric_dict = {
"antecedent support": lambda _, sA, __: sA,
"consequent support": lambda _, __, sC: sC,
"support": lambda sAC, _, __: sAC,
"confidence": lambda sAC, sA, _: sAC/sA,
"lift": lambda sAC, sA, sC: metric_dict["confidence"](sAC, sA, sC)/sC,
"leverage": lambda sAC, sA, sC: metric_dict["support"](
sAC, sA, sC) - sA*sC,
"conviction": lambda sAC, sA, sC: conviction_helper(sAC, sA, sC)
}
columns_ordered = ["antecedent support", "consequent support",
"support",
"confidence", "lift",
"leverage", "conviction"]
# check for metric compliance
if support_only:
metric = 'support'
else:
if metric not in metric_dict.keys():
raise ValueError("Metric must be 'confidence' or 'lift', got '{}'"
.format(metric))
# get dict of {frequent itemset} -> support
keys = df['itemsets'].values
values = df['support'].values
frozenset_vect = np.vectorize(lambda x: frozenset(x))
frequent_items_dict = dict(zip(frozenset_vect(keys), values))
# prepare buckets to collect frequent rules
rule_antecedents = []
rule_consequents = []
rule_supports = []
# iterate over all frequent itemsets
for k in frequent_items_dict.keys():
sAC = frequent_items_dict[k]
# to find all possible combinations
for idx in range(len(k)-1, 0, -1):
# of antecedent and consequent
for c in combinations(k, r=idx):
antecedent = frozenset(c)
consequent = k.difference(antecedent)
if support_only:
# support doesn't need these,
# hence, placeholders should suffice
sA = None
sC = None
else:
try:
sA = frequent_items_dict[antecedent]
sC = frequent_items_dict[consequent]
except KeyError as e:
s = (str(e) + 'You are likely getting this error'
' because the DataFrame is missing '
' antecedent and/or consequent '
' information.'
' You can try using the '
' `support_only=True` option')
raise KeyError(s)
# check for the threshold
score = metric_dict[metric](sAC, sA, sC)
if score >= min_threshold:
rule_antecedents.append(antecedent)
rule_consequents.append(consequent)
rule_supports.append([sAC, sA, sC])
# check if frequent rule was generated
if not rule_supports:
return pd.DataFrame(
columns=["antecedents", "consequents"] + columns_ordered)
else:
# generate metrics
rule_supports = np.array(rule_supports).T.astype(float)
df_res = pd.DataFrame(
data=list(zip(rule_antecedents, rule_consequents)),
columns=["antecedents", "consequents"])
if support_only:
sAC = rule_supports[0]
for m in columns_ordered:
df_res[m] = np.nan
df_res['support'] = sAC
else:
sAC = rule_supports[0]
sA = rule_supports[1]
sC = rule_supports[2]
for m in columns_ordered:
df_res[m] = metric_dict[m](sAC, sA, sC)
return df_res
