数据挖掘 FP-Growth算法实验报告

fp-growth算法例子FP-Growth（频繁模式增长）是一种在频繁项集挖掘中找出项集（itemsets）之间有趣的关联规则的算法。

其目的是寻找大型数据集中的频繁项集，并使用这些频繁项集来生成关联规则。

以下是一个简单的FP-Growth算法的Python实现示例：```pythonimport numpy as npfrom apriori import gen_候选项集, FPGrowth_Prefix_Frequent# 构造事务数据库data = [['苹果', '香蕉', '橙子'],['香蕉', '橙子', '葡萄'],['苹果', '香蕉', '葡萄'],['苹果', '橙子', '葡萄'],['橙子', '葡萄']]# 初始化FP-Growth算法参数min_support = 0.5 # 最小支持度阈值min_confidence = 0.7 # 最小置信度阈值num_transactions = len(data) # 事务数据库中事务数量database = data # 存储整个事务数据库num_patterns = 10 # 最大模式数量patterns = [] # 存储所有模式# 执行FP-Growth算法，找到频繁项集frequent_itemsets = FPGrowth_Prefix_Frequent(num_transactions, database, min_support)# 从频繁项集中生成关联规则，并过滤出满足最小置信度的规则rules = []for itemset in frequent_itemsets:for i in range(1, len(itemset)):left = [tuple(x) for x in zip(itemset[:i], itemset[i:])]right = itemset[i:]confidence = len(left) / num_transactionsif confidence >= min_confidence:rules.append((left, right, confidence))print('关联规则:', left, '->', right, '置信度:', confidence)print('支持度:', left + right, '/', num_transactions)print()```在这个例子中，我们首先定义了一个事务数据库，其中包含了一些水果的购买记录。

频繁模式挖掘中Apriori、FP-Growth和Eclat算法的实现和对⽐（Python实现）最近上数据挖掘的课程，其中学习到了频繁模式挖掘这⼀章，这章介绍了三种算法，Apriori、FP-Growth和Eclat算法；由于对于不同的数据来说，这三种算法的表现不同，所以我们本次就对这三种算法在不同情况下的效率进⾏对⽐。

从⽽得出适合相应算法的情况。

GitHub：（⼀）算法原理其中相应的算法原理在之前的博客中都有⾮常详细的介绍，这⾥就不再赘述，这⾥给出三种算法⼤概的介绍但是这⾥给出每个算法的关键点：1.1 Apriori算法：限制候选产⽣发现频繁项集重要性质：频繁项集所有⾮空⼦集也⼀定是频繁的。

主要步骤：1. 连接2. 剪枝特点：需要多次扫描数据库，对于⼤规模数据效率很低！1.2 FP-Growth算法通过模式增长挖掘频繁模式主要步骤：1. 构建频繁模式树2. 构造条件模式基3. 挖掘频繁模式特点：两次扫描数据库，采⽤分治的策略有效降低搜索开销1.3 Eclat算法使⽤垂直格式挖掘频繁项集主要步骤：1. 将数据倒排{ item：TID_set }2. 通过求频繁k项集的交集来获取k+1项集特点：仅需要⼀次扫描数据库，TID集合很长的话需要消耗⼤量的内存和计算时间（⼆）算法实现由于各个博客给出的算法实现并不统⼀，⽽且本⼈在实现《机器学习实战》中FP-Growth算法的时候发现，在在创建FP-Tree时根据headTable中元素的⽀持度顺序的排序过程中，这个地⽅的排序⽅法写的有问题，当在模式稠密时，具有很多⽀持度相同的项集，书中的代码并没有考虑着⼀点，所以如果遇到⽀持度相同的项集那个就会出现⼀定的随机性，导致建树过程出错，最后的频繁项集结果会偏⼩，因此这⾥对改错误进⾏了纠正，在⽀持度相同时，添加了按照项集排序的规则，这样建⽴的FP-Tree才完全正确。

1.1 Apriori算法实现：1# -*- coding: utf-8 -*-2'''3@author: Infaraway4@time: 2017/4/15 12:545@Function:6'''789def init_c1(data_set_dict, min_support):10 c1 = []11 freq_dic = {}12for trans in data_set_dict:13for item in trans:14 freq_dic[item] = freq_dic.get(item, 0) + data_set_dict[trans]15# 优化初始的集合，使不满⾜最⼩⽀持度的直接排除16 c1 = [[k] for (k, v) in freq_dic.iteritems() if v >= min_support]17 c1.sort()18return map(frozenset, c1)192021def scan_data(data_set, ck, min_support, freq_items):22"""23计算Ck中的项在数据集合中的⽀持度，剪枝过程24 :param data_set:25 :param ck:26 :param min_support: 最⼩⽀持度27 :param freq_items: 存储满⾜⽀持度的频繁项集28 :return:29"""30 ss_cnt = {}31# 每次遍历全体数据集32for trans in data_set:33for item in ck:34# 对每⼀个候选项集，检查是否是 term中的⼀部分（⼦集），即候选项能否得到⽀持35if item.issubset(trans):36 ss_cnt[item] = ss_cnt.get(item, 0) + 137 ret_list = []38for key in ss_cnt:39 support = ss_cnt[key] # 每个项的⽀持度40if support >= min_support:41 ret_list.insert(0, key) # 将满⾜最⼩⽀持度的项存⼊集合42 freq_items[key] = support #43return ret_list444546def apriori_gen(lk, k):47"""48由Lk的频繁项集⽣成新的候选项集连接过程49 :param lk: 频繁项集集合50 :param k: k 表⽰集合中所含的元素个数51 :return: 候选项集集合52"""53 ret_list = []54for i in range(len(lk)):55for j in range(i+1, len(lk)):56 l1 = list(lk[i])[:k-2]57 l2 = list(lk[j])[:k-2]58 l1.sort()59 l2.sort()60if l1 == l2:61 ret_list.append(lk[i] | lk[j]) # 求并集62# retList.sort()63return ret_list646566def apriori_zc(data_set, data_set_dict, min_support=5):67"""68 Apriori算法过程69 :param data_set: 数据集70 :param min_support: 最⼩⽀持度，默认值 0.571 :return:72"""73 c1 = init_c1(data_set_dict, min_support)74 data = map(set, data_set) # 将dataSet集合化，以满⾜scanD的格式要求75 freq_items = {}76 l1 = scan_data(data, c1, min_support, freq_items) # 构建初始的频繁项集77 l = [l1]78# 最初的L1中的每个项集含有⼀个元素，新⽣成的项集应该含有2个元素，所以 k=279 k = 280while len(l[k - 2]) > 0:81 ck = apriori_gen(l[k - 2], k)82 lk = scan_data(data, ck, min_support, freq_items)83 l.append(lk)84 k += 1 # 新⽣成的项集中的元素个数应不断增加85return freq_itemsView Code1.2 FP-Growth算法实现：1）FP_Growth⽂件：在create_tree()函数中修改《机器学习实战》中的代码：############################################################################################## # 这⾥修改机器学习实战中的排序代码：ordered_items = [v[0] for v in sorted(local_data.items(), key=lambda kv: (-kv[1], kv[0]))]##############################################################################################1# -*- coding: utf-8 -*-2"""3@author: Infaraway4@time: 2017/4/15 16:075@Function:6"""7from DataMining.Unit6_FrequentPattern.FP_Growth.TreeNode import treeNode8910def create_tree(data_set, min_support=1):11"""12创建FP树13 :param data_set: 数据集14 :param min_support: 最⼩⽀持度15 :return:16"""17 freq_items = {} # 频繁项集18for trans in data_set: # 第⼀次遍历数据集19for item in trans:20 freq_items[item] = freq_items.get(item, 0) + data_set[trans]2122 header_table = {k: v for (k, v) in freq_items.iteritems() if v >= min_support} # 创建头指针表23# for key in header_table:24# print key, header_table[key]2526# ⽆频繁项集27if len(header_table) == 0:28return None, None29for k in header_table:30 header_table[k] = [header_table[k], None] # 添加头指针表指向树中的数据31# 创建树过程32 ret_tree = treeNode('Null Set', 1, None) # 根节点3334# 第⼆次遍历数据集35for trans, count in data_set.items():36 local_data = {}37for item in trans:38if header_table.get(item, 0):39 local_data[item] = header_table[item][0]40if len(local_data) > 0:41############################################################################################## 42# 这⾥修改机器学习实战中的排序代码：43 ordered_items = [v[0] for v in sorted(local_data.items(), key=lambda kv: (-kv[1], kv[0]))]44############################################################################################## 45 update_tree(ordered_items, ret_tree, header_table, count) # populate tree with ordered freq itemset46return ret_tree, header_table474849def update_tree(items, in_tree, header_table, count):50'''51 :param items: 元素项52 :param in_tree: 检查当前节点53 :param header_table:54 :param count:55 :return:56'''57if items[0] in in_tree.children: # check if ordered_items[0] in ret_tree.children58 in_tree.children[items[0]].increase(count) # incrament count59else: # add items[0] to in_tree.children60 in_tree.children[items[0]] = treeNode(items[0], count, in_tree)61if header_table[items[0]][1] is None: # update header table62 header_table[items[0]][1] = in_tree.children[items[0]]63else:64 update_header(header_table[items[0]][1], in_tree.children[items[0]])65if len(items) > 1: # call update_tree() with remaining ordered items66 update_tree(items[1::], in_tree.children[items[0]], header_table, count)676869def update_header(node_test, target_node):70'''71 :param node_test:72 :param target_node:73 :return:74'''75while node_test.node_link is not None: # Do not use recursion to traverse a linked list!76 node_test = node_test.node_link77 node_test.node_link = target_node787980def ascend_tree(leaf_node, pre_fix_path):81'''82遍历⽗节点，找到路径83 :param leaf_node:84 :param pre_fix_path:85 :return:86'''87if leaf_node.parent is not None:88 pre_fix_path.append(leaf_)89 ascend_tree(leaf_node.parent, pre_fix_path)909192def find_pre_fix_path(base_pat, tree_node):93'''94创建前缀路径95 :param base_pat: 频繁项96 :param treeNode: FP树中对应的第⼀个节点97 :return:98'''99# 条件模式基100 cond_pats = {}101while tree_node is not None:102 pre_fix_path = []103 ascend_tree(tree_node, pre_fix_path)104if len(pre_fix_path) > 1:105 cond_pats[frozenset(pre_fix_path[1:])] = tree_node.count106 tree_node = tree_node.node_link107return cond_pats108109110def mine_tree(in_tree, header_table, min_support, pre_fix, freq_items):111'''112挖掘频繁项集113 :param in_tree:114 :param header_table:115 :param min_support:116 :param pre_fix:117 :param freq_items:118 :return:119'''120# 从⼩到⼤排列table中的元素，为遍历寻找频繁集合使⽤121 bigL = [v[0] for v in sorted(header_table.items(), key=lambda p: p[1])] # (sort header table) 122for base_pat in bigL: # start from bottom of header table123 new_freq_set = pre_fix.copy()124 new_freq_set.add(base_pat)125# print 'finalFrequent Item: ',new_freq_set #append to set126if len(new_freq_set) > 0:127 freq_items[frozenset(new_freq_set)] = header_table[base_pat][0]128 cond_patt_bases = find_pre_fix_path(base_pat, header_table[base_pat][1])129 my_cond_tree, my_head = create_tree(cond_patt_bases, min_support)130# print 'head from conditional tree: ', my_head131if my_head is not None: # 3. mine cond. FP-tree132# print 'conditional tree for: ',new_freq_set133# my_cond_tree.disp(1)134 mine_tree(my_cond_tree, my_head, min_support, new_freq_set, freq_items)135136137def fp_growth(data_set, min_support=1):138 my_fp_tree, my_header_tab = create_tree(data_set, min_support)139# my_fp_tree.disp()140 freq_items = {}141 mine_tree(my_fp_tree, my_header_tab, min_support, set([]), freq_items)142return freq_itemsView Code2）treeNode对象⽂件1# -*- coding: utf-8 -*-2'''3@author: Infaraway4@time: 2017/3/31 0:145@Function:6'''789class treeNode:10def__init__(self, name_value, num_occur, parent_node):11 = name_value # 节点元素名称12 self.count = num_occur # 出现的次数13 self.node_link = None # 指向下⼀个相似节点的指针，默认为None14 self.parent = parent_node # 指向⽗节点的指针15 self.children = {} # 指向孩⼦节点的字典⼦节点的元素名称为键，指向⼦节点的指针为值1617def increase(self, num_occur):18"""19增加节点的出现次数20 :param num_occur: 增加数量21 :return:22"""23 self.count += num_occur2425def disp(self, ind=1):26print'' * ind, , '', self.count27for child in self.children.values():28 child.disp(ind + 1)View Code1.3 Eclat算法实现1# -*- coding: utf-8 -*-2"""3@author: Infaraway4@time: 2017/4/15 19:335@Function:6"""78import sys9import time10 type = sys.getfilesystemencoding()111213def eclat(prefix, items, min_support, freq_items):14while items:15# 初始遍历单个的元素是否是频繁16 key, item = items.pop()17 key_support = len(item)18if key_support >= min_support:19# print frozenset(sorted(prefix+[key]))20 freq_items[frozenset(sorted(prefix+[key]))] = key_support21 suffix = [] # 存储当前长度的项集22for other_key, other_item in items:23 new_item = item & other_item # 求和其他集合求交集24if len(new_item) >= min_support:25 suffix.append((other_key, new_item))26 eclat(prefix+[key], sorted(suffix, key=lambda item: len(item[1]), reverse=True), min_support, freq_items)27return freq_items282930def eclat_zc(data_set, min_support=1):31"""32 Eclat⽅法33 :param data_set:34 :param min_support:35 :return:36"""37# 将数据倒排38 data = {}39 trans_num = 040for trans in data_set:41 trans_num += 142for item in trans:43if item not in data:44 data[item] = set()45 data[item].add(trans_num)46 freq_items = {}47 freq_items = eclat([], sorted(data.items(), key=lambda item: len(item[1]), reverse=True), min_support, freq_items)48return freq_itemsView Code（三）试验阶段：这样我们就统⼀了三种算法的调⽤以及返回值，现在我们可以开始试验阶段了，我们在试验阶段分别根据最⼩⽀持度阈值和数据规模的变化来判断这三种算法的效率：⾸先我们先统⼀调⽤者三个算法：1def test_fp_growth(minSup, dataSetDict, dataSet):2 freqItems = fp_growth(dataSetDict, minSup)3 freqItems = sorted(freqItems.iteritems(), key=lambda item: item[1])4return freqItems567def test_apriori(minSup, dataSetDict, dataSet):8 freqItems = apriori_zc(dataSet, dataSetDict, minSup)9 freqItems = sorted(freqItems.iteritems(), key=lambda item: item[1])10return freqItems111213def test_eclat(minSup, dataSetDict, dataSet):14 freqItems = eclat_zc(dataSet, minSup)15 freqItems = sorted(freqItems.iteritems(), key=lambda item: item[1])16return freqItems然后实现数据规模变化的效率改变1def do_experiment_min_support():23 data_name = 'unixData8_pro.txt'4 x_name = "Min_Support"5 data_num = 15006 minSup = data_num / 678 dataSetDict, dataSet = loadDblpData(open("dataSet/" + data_name), ',', data_num)9 step = minSup / 5 # #################################################################10 all_time = []11 x_value = []12for k in range(5):1314 x_value.append(minSup) # ################################################################# 15if minSup < 0: # #################################################################16break17 time_fp = 018 time_et = 019 time_ap = 020 freqItems_fp = {}21 freqItems_eclat = {}22 freqItems_ap = {}23for i in range(10):24 ticks0 = time.time()25 freqItems_fp = test_fp_growth(minSup, dataSetDict, dataSet)26 time_fp += time.time() - ticks027 ticks0 = time.time()28 freqItems_eclat = test_eclat(minSup, dataSetDict, dataSet)29 time_et += time.time() - ticks030 ticks0 = time.time()31 freqItems_ap = test_apriori(minSup, dataSetDict, dataSet)32 time_ap += time.time() - ticks033print"minSup :", minSup, " data_num :", data_num, \34" freqItems_fp:", len(freqItems_fp), " freqItems_eclat:", len(freqItems_eclat), " freqItems_ap:", len(35 freqItems_ap)36print"fp_growth:", time_fp / 10, " eclat:", time_et / 10, " apriori:", time_ap / 1037# print_freqItems("show", freqItems_eclat)38 minSup -= step # #################################################################39 use_time = [time_fp / 10, time_et / 10, time_ap / 10]40 all_time.append(use_time)41# print use_time42 y_value = []43for i in range(len(all_time[0])):44 tmp = []45for j in range(len(all_time)):46 tmp.append(all_time[j][i])47 y_value.append(tmp)48 plot_pic(x_value, y_value, data_name, x_name)49return x_value, y_valueView Code然后实现最⼩⽀持度变化的效率改变1def do_experiment_data_size():23 data_name = 'kosarakt.txt'4 x_name = "Data_Size"5 data_num = 20000067 step = data_num / 5 # #################################################################8 all_time = []9 x_value = []10for k in range(5):11 minSup = data_num * 0.01012 dataSetDict, dataSet = loadDblpData(open("dataSet/"+data_name), '', data_num)13 x_value.append(data_num) # #################################################################14if data_num < 0: # #################################################################15break16 time_fp = 017 time_et = 018 time_ap = 019 freqItems_fp = {}20 freqItems_eclat = {}21 freqItems_ap = {}22for i in range(2):23 ticks0 = time.time()24 freqItems_fp = test_fp_growth(minSup, dataSetDict, dataSet)25 time_fp += time.time() - ticks026 ticks0 = time.time()27 freqItems_eclat = test_eclat(minSup, dataSetDict, dataSet)28 time_et += time.time() - ticks029 ticks0 = time.time()30# freqItems_ap = test_apriori(minSup, dataSetDict, dataSet)31# time_ap += time.time() - ticks032print"minSup :", minSup, " data_num :", data_num, \33" freqItems_fp:", len(freqItems_fp), " freqItems_eclat:", len(freqItems_eclat), " freqItems_ap:", len(freqItems_ap) 34print"fp_growth:", time_fp / 10, " eclat:", time_et / 10, " apriori:", time_ap / 1035# print_freqItems("show", freqItems_eclat)36 data_num -= step # #################################################################37 use_time = [time_fp / 10, time_et / 10, time_ap / 10]38 all_time.append(use_time)39# print use_time4041 y_value = []42for i in range(len(all_time[0])):43 tmp = []44for j in range(len(all_time)):45 tmp.append(all_time[j][i])46 y_value.append(tmp)47 plot_pic(x_value, y_value, data_name, x_name)48return x_value, y_valueView Code同时为了观察⽅便，我们需要对三种算法返回的结果进⾏绘图1# -*- coding: utf-8 -*-2"""3@author: Infaraway4@time: 2017/4/16 20:485@Function:6"""78import matplotlib.pyplot as plt91011def plot_pic(x_value, y_value, title, x_name):12 plot1 = plt.plot(x_value, y_value[0], 'r', label='Kulc') # use pylab to plot x and y13 plot2 = plt.plot(x_value, y_value[1], 'g', label='IR') # use pylab to plot x and y14# plot3 = plt.plot(x_value, y_value[2], 'b', label='Apriori') # use pylab to plot x and y15 plt.title(title) # give plot a title16 plt.xlabel(x_name) # make axis labels17 plt.ylabel('value ')18 plt.legend(loc='upper right') # make legend1920 plt.show() # show the plot on the screenView Code将两个部分统⼀执⾏：1if__name__ == '__main__':23# x_value, y_value = do_experiment_min_support()4# x_value, y_value = do_experiment_data_size()5# do_test()（四）实验结果分析：本次实验我们主要从以下⼏个⽅⾯来讨论三种算法的效率：数据规模⼤⼩最⼩⽀持度阈值长事物数据模式的稠密性4.1 数据规模⼤⼩：数据集：unxiData8规模：900-1500Min_support = 1/30时 Min_support = 1/20时数据集：kosarakt规模：6000-10000Min_support = 1/50 Min_support = 1/80 Min_support = 1/100结论：⼀般情况下，数据规模越⼤，使⽤Apriori算法的效率越低，因为该算法需要多次扫描数据库，当数据量越⼤时，扫描数据库带来的消耗越多。

第1篇一、实验概述本次数据挖掘实验以Apriori算法为核心，通过对GutenBerg和DBLP两个数据集进行关联规则挖掘，旨在探讨数据挖掘技术在知识发现中的应用。

实验过程中，我们遵循数据挖掘的一般流程，包括数据预处理、关联规则挖掘、结果分析和可视化等步骤。

二、实验结果分析1. 数据预处理在实验开始之前，我们对GutenBerg和DBLP数据集进行了预处理，包括数据清洗、数据集成和数据变换等。

通过对数据集的分析，我们发现了以下问题：（1）数据缺失：部分数据集存在缺失值，需要通过插补或删除缺失数据的方法进行处理。

（2）数据不一致：数据集中存在不同格式的数据，需要进行统一处理。

（3）数据噪声：数据集中存在一些异常值，需要通过滤波或聚类等方法进行处理。

2. 关联规则挖掘在数据预处理完成后，我们使用Apriori算法对数据集进行关联规则挖掘。

实验中，我们设置了不同的最小支持度和最小置信度阈值，以挖掘出不同粒度的关联规则。

以下是实验结果分析：（1）GutenBerg数据集在GutenBerg数据集中，我们以句子为篮子粒度，挖掘了林肯演讲集的关联规则。

通过分析挖掘结果，我们发现：- 单词“the”和“of”在句子中频繁出现，表明这两个词在林肯演讲中具有较高的出现频率。

- “and”和“to”等连接词也具有较高的出现频率，说明林肯演讲中句子结构较为复杂。

- 部分单词组合具有较高的置信度，如“war”和“soldier”，表明在林肯演讲中提到“war”时，很可能同时提到“soldier”。

（2）DBLP数据集在DBLP数据集中，我们以作者为单位，挖掘了作者之间的合作关系。

实验结果表明：- 部分作者之间存在较强的合作关系，如同一研究领域内的作者。

- 部分作者在多个研究领域均有合作关系，表明他们在不同领域具有一定的学术影响力。

3. 结果分析和可视化为了更好地展示实验结果，我们对挖掘出的关联规则进行了可视化处理。

通过可视化，我们可以直观地看出以下信息：（1）频繁项集的分布情况：通过柱状图展示频繁项集的分布情况，便于分析不同项集的出现频率。

关联规则挖掘实验报告一、实验介绍关联规则挖掘是数据挖掘中的一种重要技术，用于发现数据集中的频繁项集和关联规则。

本次实验旨在通过使用Apriori算法和FP-Growth算法来挖掘一个超市销售数据集中的频繁项集和关联规则。

二、实验步骤1. 数据准备本次实验使用的数据集为一个超市销售数据，包括了超市中各个商品的销售记录。

首先需要将数据导入到Python环境中，并进行预处理，例如去除重复项、缺失值等。

2. Apriori算法挖掘频繁项集和关联规则Apriori算法是一种常用的关联规则挖掘算法，其基本思想是利用先验知识来减少搜索空间。

我们可以通过设置最小支持度和最小置信度来筛选出频繁项集和关联规则。

在本次实验中，我们首先使用Apriori算法来挖掘频繁项集和关联规则。

具体步骤如下：（1）设置最小支持度和最小置信度；（2）利用Apriori算法生成候选项集；（3）根据候选项集计算支持度，并筛选出满足最小支持度的频繁项集；（4）根据频繁项集生成候选规则；（5）根据候选规则计算置信度，并筛选出满足最小置信度的关联规则。

3. FP-Growth算法挖掘频繁项集和关联规则FP-Growth算法是一种基于频繁模式树的关联规则挖掘算法，相比于Apriori算法具有更高的效率。

在本次实验中，我们也使用FP-Growth算法来挖掘频繁项集和关联规则。

具体步骤如下：（1）设置最小支持度和最小置信度；（2）利用FP-Growth算法生成频繁模式树；（3）从频繁模式树中提取满足最小支持度的频繁项集；（4）根据频繁项集生成候选规则；（5）根据候选规则计算置信度，并筛选出满足最小置信度的关联规则。

三、实验结果分析1. Apriori算法结果分析在本次实验中，我们设置了最小支持度为0.05，最小置信度为0.5。

通过使用Apriori算法，我们得到了如下结果：（1）频繁项集：共有22个频繁项集，其中最大的频繁项集包含了5个商品。

（2）关联规则：共有87条关联规则，其中置信度最高的规则为{薯片} -> {可乐}，置信度为0.8。

基于fp-growth算法的数据挖掘实例研究-回复基于fpgrowth算法的数据挖掘实例研究数据挖掘是从大规模数据集中寻找隐藏的模式、关联和信息的过程。

在日益增长的数据量和复杂性的背景下，数据挖掘算法及其应用变得越来越重要。

而fpgrowth算法是一种非常有效的数据挖掘算法，用于发现数据集中频繁项集的关联规则。

本文将通过一个实例来阐述fpgrowth算法的应用过程。

实例背景和数据集我们将以一个超市的销售数据为例来说明fpgrowth算法的应用过程。

假设这个超市的销售数据中记录了每位顾客购买的商品清单，我们的目标是利用数据挖掘技术找出顾客购买商品的关联规则。

数据预处理首先，我们需要对数据进行预处理。

原始数据集中记录了每位顾客购买的商品清单，我们需要将数据转化成一个适合fpgrowth算法处理的格式。

通常情况下，数据集格式为每一行代表一位顾客的购买清单，清单中的商品用逗号分隔。

为了方便后续的处理，可以将数据集转化为交易的事务形式。

例如，原始数据集中的一行记录可能是这样的：[牛奶, 面包, 小麦, 鸡蛋]经过转化后，数据集可能变成这样：牛奶, 面包, 小麦, 鸡蛋数据挖掘过程步骤1：构建频繁项集和频繁模式树首先，我们需要构建频繁项集和频繁模式树。

fpgrowth算法通过构建一棵FP树来实现这一步骤。

FP树是一种非常高效的数据结构，用于存储事务数据库中的频繁项集和它们的支持度。

对于我们的超市销售数据集，我们首先需要计算每个商品的支持度，并筛选出频繁项集。

支持度是指一个项集在所有事务中的出现频率，频繁项集是指支持度大于等于预设阈值的项集。

通过计算数据集中每个商品的支持度，并筛选出支持度大于等于预设阈值的商品，我们可以得到一组频繁项集。

接下来，将这些频繁项集按照支持度排序，构建频繁模式树。

步骤2：从频繁模式树中发现关联规则在构建好频繁模式树后，我们可以从中发现关联规则。

关联规则是指商品之间的关联性，例如如果顾客购买了商品A，那么他们更有可能购买商品B。

FPGrowth算法是一种关联分析算法，用于发现频繁项集和关联规则。

以下是FPGrowth算法在关联规则挖掘中涉及的一些关键指标：1.支持度（Support）：o定义：在所有项集中{x,y}出现的可能性，即项集中同时出现含有x和y 的概率。

o作用：作为建立强关联规则的第一个门槛，衡量了所考察关联规则在“量”上的多少。

2.置信度（Confidence）：o定义：在先决条件x发生的情况下，关联结果y发生的概率。

o作用：作为生成强关联规则的第二个门槛，衡量了所考察的关联规则在“质”上的可靠性。

3.提升度（Lift）：o定义：表示在含有x的条件下同时含有y的可能性与没有x的条件下项集含有y的可能性之比。

o作用：评估关联规则的预测强度，提升度大于1表示规则具有正关联，而小于1则表示规则具有负关联。

4.频繁模式树（FP-tree）：o定义：这是一种特殊的前缀树，由频繁项头表和项前缀树构成。

它压缩了提供频繁项集的数据库，但仍保留项集关联信息。

o作用：在算法中用于快速查找频繁项集和生成关联规则。

5.频繁项集（Frequent Itemset）：o定义：在数据集中出现频率至少为预设值minSupport的项集。

o作用：是生成关联规则的基础，因为一个项集只有是频繁的，其关联规则才可能是有意义的。

6.关联规则（Association Rule）：o定义：形如“如果x则y”的规则，其中x和y是项集，且x和y满足支持度和置信度的阈值要求。

o作用：反映数据集中的不同物品之间的关联关系，有助于发现数据中的有趣模式和隐藏关系。

这些是FPGrowth算法中与关联规则挖掘相关的核心指标。

在进行数据挖掘和分析时，了解这些指标对于理解算法的工作原理和结果解释至关重要。

fpgrowth算法例题
（原创版）
目录
1.FPGrowth 算法简介
2.FPGrowth 算法例题概述
3.FPGrowth 算法例题解答过程
4.FPGrowth 算法例题结论
正文
【1.FPGrowth 算法简介】
FPGrowth 算法是一种挖掘频繁项集的算法，由 Philippe
Fournier-Viger 在 1998 年提出。

该算法主要应用于数据挖掘、关联规则挖掘等领域，可以帮助我们找出数据集中频繁出现的项集，从而发现数据背后的规律。

【2.FPGrowth 算法例题概述】
假设有一个数据集，包含以下五个事务：
事务 1：{牛奶，面包，黄油}
事务 2：{啤酒，牛奶，黄油}
事务 3：{啤酒，可乐}
事务 4：{牛奶，面包，可乐}
事务 5：{啤酒，可乐}
现在需要找出支持度大于 0.1 的频繁项集。

【3.FPGrowth 算法例题解答过程】
FPGrowth 算法主要包括两个步骤：生成候选项集和扫描事务数据库。

(1) 生成候选项集：
首先，将所有单个项作为候选项集的头部，然后依次将候选项集的头部扩展为长度为 2、3、4...的项集，将这些项集添加到候选项集库中。

候选项集库：
{牛奶，面包，黄油，啤酒，可乐}
(2) 扫描事务数据库：
依次扫描事务数据库中的每个事务，计算每个候选项集在当前事务中的支持度，如果支持度大于 0.1，则将该候选项集加入到频繁项集库中。

频繁项集库：
{牛奶，面包}
【4.FPGrowth 算法例题结论】
通过 FPGrowth 算法，我们找到了支持度大于 0.1 的频繁项集：{牛奶，面包}。

fp-growth算法过程FP-Growth算法是一种用于频繁项集挖掘的数据挖掘算法。

它通过构建FP树来加速频繁项集的挖掘过程，相比于Apriori算法，FP-Growth算法具有更高的效率和更小的内存消耗。

1. 构建FP树FP-Growth算法的第一步是构建FP树。

FP树是一种基于前缀树的数据结构，用于存储频繁项集。

构建FP树的过程如下：- 遍历数据集，统计每个项的出现频次，得到频繁1项集。

- 构建空的FP树，根节点为null。

- 再次遍历数据集，对于每个事务，按照频繁1项集的频次降序排序，构建当前事务的FP树。

- 对于每个事务中的项，从根节点开始，根据其频次依次插入FP树中的相应位置。

- 完成所有事务的插入后，得到完整的FP树。

2. 构建条件模式基构建FP树后，需要根据FP树构建条件模式基。

条件模式基是指以某个项为结尾的所有路径，以及每个路径上的条件模式基。

构建条件模式基的过程如下：- 对于每个频繁1项集中的项，从FP树的叶子节点开始，向上遍历路径，得到以该项为结尾的路径。

- 对于每个路径，去除该项，得到条件模式基。

3. 递归挖掘频繁项集得到条件模式基后，可以通过递归的方式挖掘频繁项集。

具体步骤如下：- 对于每个频繁1项集，根据其在FP树中的路径和条件模式基，构建新的数据集。

- 对于新的数据集，重新构建FP树。

- 重复上述步骤，直到无法构建新的FP树为止。

4. 生成频繁项集通过递归挖掘频繁项集后，可以得到所有的频繁项集。

根据频繁项集的支持度，可以筛选出满足最小支持度要求的频繁项集。

FP-Growth算法相比于Apriori算法的优势在于：- 构建FP树的过程只需要遍历数据集两次，而Apriori算法需要多次扫描数据集，因此FP-Growth算法的效率更高。

- FP-Growth算法使用FP树存储频繁项集，相比于Apriori算法的候选项集，占用的内存更小。

然而，FP-Growth算法也有一些限制：- 构建FP树需要遍历数据集两次，对于大规模数据集来说，构建FP树的时间和内存开销仍然较大。