第一关：数据探索和预处理
本实训中，实验内容为完成数据探索和预处理，根据提示，在右侧编辑器补充代码，完成如下四个任务：
- 使用
pandas库的read_excel方法读入实验数据集； - 使用
info()函数, 观察数据属性类型并判断是否符合算法要求； - 若不符合要求，请选择合适的策略对数据进行离散化处理，即将六种类型数据分别标记为’ABCDEF’，再使用等频离散进行离散化。
import pandas as pd
def Task():
# 使用pandas库的read_excel方法读入数据中医数据
#*************** BEIGN ******************
data = pd.read_excel('data/data.xls')
answer_1 = data.head(5)
#**************** END *******************
#*************** BEIGN ******************
#观察数据属性类型是否符合算法要求
info = data.info()
answer_2 = info
#**************** END *******************
#*************** BEIGN ******************
# 使用合适的策略对数据进行离散化处理
typelabel = dict(zip(data.columns[:-1], 'ABCDEF'))
#**************** END *******************
keys = list(typelabel.keys())
answer_3 = keys
# 等频离散
k = 4
datas = list()
#*************** BEIGN ******************
for j in keys:
label = [typelabel[j]+str(i+1) for i in range(k)]
d = pd.qcut(data[j], k, labels=label)
datas.append(d)
#**************** END *******************
datas.append(data['TNM分期'])
# 经过离散化处理后的数据集
datas = pd.DataFrame(datas).T
answer_4 = datas.head(5)
#将离散化后的数据集存储到apriori.txt文件中
filepath = 'data/apriori.txt'
datas.to_csv(filepath, header=0, index=0, sep=',')
return answer_1, answer_2, answer_3, answer_4
第二关：FP增长树算法调用
根据提示，在右侧编辑器补充代码，调用FP增长树算法，实现寻找频繁项集。其中， minimum_support设置为 56， include_support设置为 True。
（1）FP-growth算法将数据存储在一种称为FP树的紧凑数据结构中。由于FP树比其他树更加复杂，因此需要一个类来保存树的每一个节点。首先，定义FP树的节点类。
class FPNode(object):
"""FP树中的节点"""
def __init__(self, tree, item, count=1):
self._tree = tree
self._item = item
self._count = count
self._parent = None
self._children = {}
self._neighbor = None
def add(self, child):
"""将给定的fp'孩子'节点添加为该节点的子节点"""
if not isinstance(child, FPNode):
raise TypeError("Can only add other FPNodes as children")
if not child.item in self._children:
self._children[child.item] = child
child.parent = self
def search(self, item):
"""
检查此节点是否包含给定项的子节点。
如果是，则返回该节点; 否则，返回None
"""
try:
return self._children[item]
except KeyError:
return None
def __contains__(self, item):
return item in self._children
@property
def tree(self):
"""出现此节点的树"""
return self._tree
@property
def item(self):
"""此节点中包含的项"""
return self._item
@property
def count(self):
"""与此节点项相关的计数。"""
return self._count
def increment(self):
"""增加与此节点项相关联的计数。"""
if self._count is None:
raise ValueError("Root nodes have no associated count.")
self._count += 1
@property
def root(self):
"""如果此节点是树的根，则为true；否则为false"""
return self._item is None and self._count is None
@property
def leaf(self):
"""如果此节点是树中的叶子，则为true；否则为false"""
return len(self._children) == 0
@property
def parent(self):
"""父节点"""
return self._parent
@parent.setter
def parent(self, value):
if value is not None and not isinstance(value, FPNode):
raise TypeError("A node must have an FPNode as a parent.")
if value and value.tree is not self.tree:
raise ValueError("Cannot have a parent from another tree.")
self._parent = value
@property
def neighbor(self):
"""
节点的邻居；在树中具有相同值的“右边”
"""
return self._neighbor
@neighbor.setter
def neighbor(self, value):
if value is not None and not isinstance(value, FPNode):
raise TypeError("A node must have an FPNode as a neighbor.")
if value and value.tree is not self.tree:
raise ValueError("Cannot have a neighbor from another tree.")
self._neighbor = value
@property
def children(self):
"""该节点的子节点"""
return tuple(self._children.itervalues())
def inspect(self, depth=0):
print (' ' * depth) + repr(self)
for child in self.children:
child.inspect(depth + 1)
def __repr__(self):
if self.root:
return "<%s (root)>" % type(self).__name__
return "<%s %r (%r)>" % (type(self).__name__, self.item, self.count)
（2） 定义Fptree函数来构建FP树
from collections import defaultdict, namedtuple
class FPTree(object):
Route = namedtuple('Route', 'head tail')
def __init__(self):
# 树的根节点.
self._root = FPNode(self, None, None)
#字典将项目映射到路径的头部和尾部
# "neighbors" that will hit every node containing that item.
self._routes = {}
@property
def root(self):
#树的根节点.
return self._root
def add(self, transaction):
#将事务添加到树中
point = self._root
for item in transaction:
next_point = point.search(item)
if next_point:
next_point.increment()
else:
next_point = FPNode(self, item)
point.add(next_point)
self._update_route(next_point)
point = next_point
def _update_route(self, point):
assert self is point.tree
try:
route = self._routes[point.item]
route[1].neighbor = point # route[1] 是尾部
self._routes[point.item] = self.Route(route[0], point)
except KeyError:
# 开始一个新路径
self._routes[point.item] = self.Route(point, point)
def items(self):
"""
为树中表示的每个项生成一个2元组。 元组的第一个元素是项本身，
第二个元素是一个生成器，它将生成树中属于该项的节点。
"""
for item in self._routes.keys():
yield (item, self.nodes(item))
def nodes(self, item):
"""
生成包含给定项的节点序列
"""
try:
node = self._routes[item][0]
except KeyError:
return
while node:
yield node
node = node.neighbor
def prefix_paths(self, item):
"""生成以给定项结尾的前缀路径."""
def collect_path(node):
path = []
while node and not node.root:
path.append(node)
node = node.parent
path.reverse()
return path
return (collect_path(node) for node in self.nodes(item))
def inspect(self):
print( 'Tree:')
self.root.inspect(1)
print()
print ('Routes:')
for item, nodes in self.items():
print (' %r' % item)
for node in nodes:
print( ' %r' % node)
（3）定义conditional_tree_from_paths()，从给定的前缀路径构建条件FP树。前缀路径是介于所查找元素项与树根节点之间的所有内容。
def conditional_tree_from_paths(paths):
"""从给定的前缀路径构建条件FP树."""
tree = FPTree()
condition_item = None
items = set()
#将路径中的节点导入新树。只有叶子节点的计数才重要;剩下的计数将根据叶子节点的计数进行重构。
for path in paths:
if condition_item is None:
condition_item = path[-1].item
point = tree.root
for node in path:
next_point = point.search(node.item)
if not next_point:
# Add a new node to the tree.
items.add(node.item)
count = node.count if node.item == condition_item else 0
next_point = FPNode(tree, node.item, count)
point.add(next_point)
tree._update_route(next_point)
point = next_point
assert condition_item is not None
# Calculate the counts of the non-leaf nodes.
for path in tree.prefix_paths(condition_item):
count = path[-1].count
for node in reversed(path[:-1]):
node._count += count
return tree
（4）从构建的条件FP树中寻找频繁项集。
#
在给定的事务中使用FP-growth查找频繁项集。该函数返回一个生成器，而不是快速填充的项列表。 “事务”参数可以是项的任何可迭代项。 “minimum_support”应该是一个整数，它指定要接受的项集出现的最小数量。 如果include_support为true，则yield（itemset，support）对，而不仅仅是项集。
def find_frequent_itemsets(transactions, minimum_support, include_support=False):
items = defaultdict(lambda: 0) #从项到其支持度的映射
#加载传入的事务并计算单个项的支持度
for transaction in transactions:
for item in transaction:
items[item] += 1
#从项支持字典中删除不常见的项。
items = dict((item, supports) for item, supports in items.items()
if supports >= minimum_support)
#建立FP-tree。 在任何事务可以被添加到树之前，他们必须被剥夺不常出现的项，并且剩余的项必须按照频率的降序排序。
def clean_transaction(transaction):
transaction = filter(lambda v: v in items, transaction)
transaction_list = list(transaction) # 为了防止变量在其他部分调用，这里引入临时变量transaction_list
transaction_list.sort(key=lambda v: items[v], reverse=True)
return transaction_list
master = FPTree()
for transaction in map(clean_transaction, transactions):
master.add(transaction)
def find_with_suffix(tree, suffix):
for item, nodes in tree.items():
supports = sum(nn.count for nn in nodes)
if supports >= minimum_support and item not in suffix:
# 新赢家
found_set = [item] + suffix
yield (found_set, supports) if include_support else found_set
# #从项支持字典中删除不常见的项。
cond_tree = conditional_tree_from_paths(tree.prefix_paths(item))
for s in find_with_suffix(cond_tree, found_set):
yield s # pass along the good news to our caller
# 搜索频繁的项目集，并产生我们找到的结果。
for itemset in find_with_suffix(master, []):
yield itemset
调用FP增长树算法，实现寻找频繁项集
def load_data(filename):
data=list()
with open(filename,'r',encoding='utf-8') as f:
for line in f.readlines():
linestr=line.strip()
linestrlist=linestr.split(",")
data.append(linestrlist)
return data
dataset = load_data('data/apriori.txt') # 读取数据
#*************** BEIGN ******************
frequent_itemsets = find_frequent_itemsets(transactions=dataset, minimum_support=56, include_support=True)
#**************** END *******************
print(type(frequent_itemsets)) # print type
result = []
for itemset, supports in frequent_itemsets: # 将generator结果存入list
result.append((itemset, supports))
result = sorted(result, key=lambda i: i[0]) # 排序后输出
for itemset, supports in result:
print(str(itemset) + ' ' + str(float(supports/len(dataset))))
print(len(result)) # 输出频繁项集的个数
</%s></%s>
第三关：Apriori算法
本关任务：根据Apriori算法步骤，编写代码实现寻找频繁项集。
算法步骤
对比，FP算法和Apriori算法，其寻找的频繁项集的结果是相同的，但是FP算法的运行时间明显小于Apriori算法的运行时间。这是因为apriori算法需要多次扫描数据集，每次利用候选频繁集产生频繁集；而FP-growth则利用树形结构，无需产生候选频繁集而是直接得到频繁集，大大减少扫描数据集的次数，从而提高了算法的效率。
本关任务
根据下面的文字提示，在右侧编辑器补充代码，在已有的代码框架下实现函数功能，完成实验。
根据Apriori算法步骤，编写代码实现寻找频繁项集
（1）首先，定义create_C1函数，通过扫描数据集创建大小为1的所有候选项集的集合
def create_C1(data_set):
C1 = set()
for t in data_set:
#*************** BEIGN ******************
for item in t:
item_set = frozenset([item]) # frozenset: 创建不可变集合
C1.add(item_set)
#**************** END *******************
return C1
（2）定义is_apriori函数来判断候选K项集是否满足先验原理.其中，CK_item是CK中的一个候选k项集；Lksub1是包含全部的频繁(k-1)项集的集合。
如果不满足先验原理（即一个候选k项集Ck-item的(k-1)项子集不在Lksub1中），则返回False，如果满足则返回True。
def is_apriori(Ck_item, Lksub1):
for item in Ck_item:
#*************** BEIGN ******************
sub_Ck = Ck_item - frozenset([item])
if sub_Ck not in Lksub1:
return False
#**************** END *******************
return True
(3）定义create_CK函数，由频繁(k-1)项集的集合Lksub1的自身连接产生候选k项集Ck。
#其中，对于不满足先验原理的Ck_item，进行剪枝，得到最终的候选K项集。其中，Lksub1包含频繁(k-1)项集的集合，k是频繁项集的项数
apriori_gen(Fk−1)apriori_gen(Fk−1)
def create_Ck(Lksub1, k): # ((A,B),(A,D),(C,D))
Ck = set()
len_Lksub1 = len(Lksub1)
list_Lksub1 = list(Lksub1) # [(A,B),(A,D),(C,D)]
for i in range(len_Lksub1):
for j in range(1, len_Lksub1):
l1 = list(list_Lksub1[i]) # [A,B]
l2 = list(list_Lksub1[j]) # [A,D]
l1.sort() # 排序
l2.sort() # 排序
#**************** BEGIN *******************
if l1[0:k-2] == l2[0:k-2]: # 如果list_Lksub1中的前一项等于它的后一项
Ck_item = list_Lksub1[i] | list_Lksub1[j] # (A,B) | (A,C)
if is_apriori(Ck_item, Lksub1): # 对于满足先验原理，加入频繁项集
Ck.add(Ck_item)
#***************** END ********************
return Ck # ((A,B,C),(...))
(4) 定义generate_Lk_by_Ck函数，通过从Ck执行删除策略来生成Lk，即对Ck中的每个项进行计数，然后删除不满足最小支持度的项，从而获得频繁k项集。Lk：包含所有频繁k项集的集合；Ck：包含所有候选k项集的集合；min_support：最小支持度；support_data是个字典，用来记录每个频繁项集的支持度。（算法中计算支持度计数的部分）
def generate_Lk_by_Ck(data_set, Ck, min_support, support_data):
Lk = set()
item_count = {}
#**************** BEGIN *******************
for t in data_set:
for item in Ck:
if item.issubset(t): # 判断集合的所有元素是否都包含在指定集合中，如果是则返回 True，否则返回 False。
# 更新项集的支持度计数
if item not in item_count:
item_count[item] = 1
else:
item_count[item] += 1
#**************** END *******************
t_num = float(len(data_set))
for item in item_count:
if (item_count[item] / t_num) >= min_support:
Lk.add(item)
#**************** BEGIN *******************
#存储每个频繁项集的支持度
support_data[item] = item_count[item] / t_num
#**************** END *******************
return Lk
（5）定义generate_L获取频繁项集。参数k是所有频繁项集的最大项数，min_support是最小支持度，data_set是要挖掘的数据集（整合前面几个函数，得到频繁项集）
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-项集得到频繁1-项集
Lksub1 = L1.copy() # 浅复制
L = []
L.append(Lksub1)
#**************** BEGIN *******************
for i in range(2, k+1):
Ci = create_Ck(Lksub1, i) # apriori_gen(Fk−1)
Li = generate_Lk_by_Ck(data_set, Ci, min_support, support_data) # 从候选i-项集得到频繁i-项集
Lksub1 = Li.copy()
L.append(Lksub1)
#**************** END ********************
return L, support_data # L所有频繁项集，support_data所有频繁项集的支持度
调用编写的函数，寻找本实验数据集中的频繁项集
def load_data(filename):
data = list()
with open(filename, 'r', encoding='utf-8') as f:
for line in f.readlines():
linestr = line.strip()
linestrlist = linestr.split(",")
data.append(linestrlist)
return data
import fpGrowth as fp
def Task():
data = load_data('data/apriori.txt')
#**************** BEGIN *****************
L, support_data = generate_L(data, k=3, min_support=0.06)
#**************** END *******************
sum = 0
for Lk in L: # Lk是k-频繁项集
sum += len(Lk)
len_number = sum # 输出频繁项集的总数
# 验证结果可靠性，将FP算法的结果与Apriori算法结果进行对比
# 从之前的实验结果可知，FP算法和Apriori算法寻找的频繁项集的数量是相同的，均为209个，频繁项集的最大项数都是3。
# 比较FP算法和Apriori算法得到的频繁项集是否相同
result = fp.getFrequentItemsets()
q = set(frozenset(itemset) for itemset, supports in result) # FP树的频繁项集集合
p = set(freqlist for Lk in L for freqlist in Lk) # Apriori算法的频繁项集集合
return len_number, q,p
第四关：实现关联规则抽取
from apriori import *
编写代码实现关联规则抽取
dataset = load_data('data/apriori.txt')
定义 generate_big_rules函数来获取关联规则
def generate_big_rules(L, support_data, min_conf):
big_rule_list = []
sub_set_list = []
for i in range(0, len(L)):
for freq_set in L[i]: # freq_set:（'B4'）、（'B4', 'C4', 'H4'）
for sub_set in sub_set_list:
#**************** BEGIN *****************
if sub_set.issubset(freq_set):
# 计算置信度
conf = support_data[freq_set] / support_data[freq_set - sub_set]
# 前件、后件、支持度、置信度
big_rule = (freq_set - sub_set, sub_set, support_data[freq_set], conf)
if conf >= min_conf and big_rule not in big_rule_list:
big_rule_list.append(big_rule)
#**************** END *******************
sub_set_list.append(freq_set)
return big_rule_list
def task():
L, support_data = generate_L(dataset, k=4, min_support=0.06)
# 根据频繁项集寻找关联规则，设置置信度为 0.75
big_rules_list = generate_big_rules(L, support_data, min_conf=0.75)
return big_rules_list
第五关：参数选择与关联规则结果分析
from apriori import *
编写代码实现关联规则抽取
def task():
dataset = load_data('data/apriori.txt')
#**************** BEGIN *****************
L, support_data = generate_L(dataset, k=4, min_support=0.1)
big_rules_list = generate_big_rules(L, support_data, min_conf=0.75)
#**************** END *******************
#**************** BEGIN *****************
L, support_data = generate_L(dataset, k=4, min_support=0.06)
big_rules_list_2 = generate_big_rules(L, support_data, min_conf=0.5)
#**************** END *******************
return big_rules_list, big_rules_list_2
Original: https://blog.csdn.net/m0_56494324/article/details/122056913
Author: 南风不竞呀
Title: Educoder关联规则挖掘
原创文章受到原创版权保护。转载请注明出处：https://www.johngo689.com/698487/
转载文章受原作者版权保护。转载请注明原作者出处！