Apriori与FP-growth与ECLAT算法比较分析
- 格式:docx
- 大小:280.72 KB
- 文档页数:6
【最新】谈两种关联规则算法在中医药治疗方面的应用及比较-范文模板本文部分内容来自网络,本司不为其真实性负责,如有异议或侵权请及时联系,本司将予以删除!== 本文为word格式,下载后可随意编辑修改! ==谈两种关联规则算法在中医药治疗方面的应用及比较关联规则反映一个事物与其他事物之间的相互依存性和关联性。
而关联规则挖掘则是数据挖掘中最活跃的研究方法之一,其本质是要找出隐藏在数据间的相互关系。
关联规则数据挖掘的步骤主要有两步: 找出所有支持度大于或等于规定最小支持度的频繁项集,再由频繁项集产生所期望的关联规则。
其关联规则的产生由支持度和置信度决定。
在中医药领域,数据挖掘技术可用于证候诊断、方剂配伍、文献研究、临床病历等方面,以辅助传承中医文化,指导现代中医的发展。
在目前针对中医药领域的数据挖掘中,关联规则Apriori 算法和FP-growth 算法倍受研究人员的青睐。
1 概念Apriori 算法为布尔关联规则挖掘频繁项集的原创性算法。
该算法属于宽度优先算法,使用逐层搜索的迭代方法,其中k 项集用于探索( k + 1) 项集。
首先,扫描整个数据库,累计每个项的计数,找出满足最小支持度的项,得到频繁1 项集的集合L1。
接下来循环进行以下两步: 连接步,产生候选项集Ck;剪枝步,根据先验性质频繁项集的所有非空子集也一定是频繁的,剪除( k - 1) 项子集不在Lk - 1中的候选k 项集,当Lk为空时终止循环。
FP-growth 算法则是一种不产生候选项目集而采用模式增长的方式挖掘频繁模式的算法。
通过两个步骤来完成: 构造频繁模式树FP-tree 和调用FPgrowth算法进行频繁项集挖掘。
其原理是通过把每个事物映射到FP 树中的一条路径将数据库压缩到一颗频繁模式树,但仍保留项目集关联信息,然后将这种压缩后的数据库分成一组条件数据库,每个关联一个频繁项,并分别挖掘每个数据库。
对于每个模式片段,只需要考察与它相关联数据集。
大数据分析中关联分析技术的使用教程大数据分析已经成为当今信息时代的重中之重,企业和组织通过对数据进行深入分析,能够获得有价值的洞察,为业务决策提供有力支持。
而在大数据分析中,关联分析技术被广泛用于揭示数据之间的关联关系,发现隐藏在数据背后的规律和潜在的相关性。
在本篇文章中,我们将为您介绍关联分析技术的基本概念、常用算法以及实际应用。
一、关联分析概述关联分析是一种从大规模数据集中寻找有趣关系、相互依赖的任务。
它通过发现项目集中的频繁模式来完成,频繁模式指的是在数据集中经常出现的物品组合。
关联分析被广泛应用于市场篮子分析、商品推荐、交叉销售等领域。
二、关联分析算法1. Apriori算法Apriori算法是关联分析中最常用的算法之一,它基于频繁模式的性质。
Apriori算法通过扫描数据集多次来找到频繁项集,利用逐层递加的方式来发现频繁项集的超集,直到无法找到更多频繁项集为止。
Apriori算法的核心思想是:如果一个物品组合是频繁的,那么它的子集也一定是频繁的。
2. FP-Growth算法FP-Growth算法是一种高效的关联分析算法,通过构造FP树(频繁模式树)来实现快速的频繁模式挖掘。
与Apriori算法相比,FP-Growth算法避免了多次扫描事务数据库的操作,通过构造FP树和利用后缀路径来发现频繁模式。
FP-Growth算法适合处理包含大量事务和高维度特征的数据集。
3. Eclat算法Eclat算法也是一种经典的关联分析算法,它通过交集来计算频繁模式。
Eclat算法首先构建一个频繁项集的垂直格式数据结构,然后利用递归的方式来生成频繁项集。
与Apriori算法和FP-Growth算法相比,Eclat算法更适用于处理稀疏数据集。
三、关联分析的实际应用1. 市场篮子分析市场篮子分析是关联分析的经典应用之一,它通过挖掘购物篮中的频繁模式,从而揭示商品之间的关联关系。
利用市场篮子分析,商户可以了解消费者购买习惯,进行商品陈列、促销策略的优化,提高销售额和客户满意度。
频繁模式挖掘中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算法的效率越低,因为该算法需要多次扫描数据库,当数据量越⼤时,扫描数据库带来的消耗越多。
使⽤Apriori算法和FP-growth算法进⾏关联分析系列⽂章:最近看了《机器学习实战》中的第11章(使⽤Apriori算法进⾏关联分析)和第12章(使⽤FP-growth算法来⾼效发现频繁项集)。
正如章节标题所⽰,这两章讲了⽆监督机器学习⽅法中的关联分析问题。
关联分析可以⽤于回答"哪些商品经常被同时购买?"之类的问题。
书中举了⼀些关联分析的例⼦:通过查看哪些商品经常在⼀起购买,可以帮助商店了解⽤户的购买⾏为。
这种从数据海洋中抽取的知识可以⽤于商品定价、市场促销、存活管理等环节。
在美国国会投票记录中发现关联规则。
在⼀个国会投票记录的数据集中发现议案投票的相关性,(原⽂:这⾥只是出于娱乐的⽬的,不过也可以……)使⽤分析结果来为政治竞选活动服务,或者预测选举官员会如何投票。
发现毒蘑菇的相似特征。
这⾥只对包含某个特定元素(有毒性)的项集感兴趣,从中寻找毒蘑菇中的⼀些公共特征,利⽤这些特征来避免吃到那些有毒蘑菇。
在Twitter源中发现⼀些共现词。
对于给定搜索词,发现推⽂中频繁出现的单词集合。
从新闻⽹站点击流中挖掘新闻流⾏趋势,挖掘哪些新闻⼴泛被⽤户浏览到。
搜索引擎推荐,在⽤户输⼊查询词时推荐同相关的查询词项。
从⼤规模数据集中寻找物品间的隐含关系被称作关联分析(association analysis)或者关联规则学习(association rule learning)。
这⾥的主要问题在于,寻找物品的不同组合是⼀项⼗分耗时的任务,所需的计算代价很⾼,蛮⼒搜索⽅法并不能解决这个问题,所以需要⽤更智能的⽅法在合理的时间范围内找到频繁项集。
本⽂分别介绍如何使⽤Apriori算法和FP-growth算法来解决上述问题。
1.关联分析是在⼤规模数据集中寻找有趣关系的任务。
这些关系可以有两种形式:频繁项集关联规则频繁项集(frequent item sets)是经常出现在⼀块⼉的物品的集合,关联规则(association rules)暗⽰两种物品之间可能存在很强的关系。
《数据挖掘中关联规则算法研究》篇一一、引言随着信息技术和大数据时代的飞速发展,数据挖掘技术逐渐成为各个领域研究的重要课题。
关联规则算法作为数据挖掘的核心技术之一,能够从大量数据中提取出有价值的信息和知识。
本文将深入探讨数据挖掘中关联规则算法的研究现状、常用算法及其应用领域。
二、关联规则算法概述关联规则算法是一种在大规模数据集中寻找项集之间有趣关系的技术。
其主要目标是发现数据集中项集之间的关联性或因果结构,从而帮助人们更好地理解和利用数据。
关联规则算法通常用于购物篮分析、用户行为分析、生物信息学等领域。
三、常用关联规则算法1. Apriori算法:Apriori算法是一种经典的关联规则挖掘算法,其核心思想是通过寻找频繁项集来生成关联规则。
Apriori算法通过不断迭代,逐步找出满足最小支持度和最小置信度的规则。
2. FP-Growth算法:FP-Growth算法是一种改进的关联规则挖掘算法,它通过构建频繁模式树(FP-Tree)来发现数据集中的频繁项集和关联规则。
与Apriori算法相比,FP-Growth算法具有更高的效率。
3. Eclat算法:Eclat算法也是一种常用的关联规则挖掘算法,其基本思想是将数据库分割成若干个不相交的子集,然后对每个子集进行局部搜索,最后将局部搜索结果合并得到全局的关联规则。
四、关联规则算法的应用领域1. 购物篮分析:通过分析顾客的购物行为,发现商品之间的关联关系,从而帮助商家制定更有效的营销策略。
2. 用户行为分析:在互联网领域,通过分析用户的浏览、点击等行为数据,发现用户兴趣之间的关联关系,为个性化推荐等应用提供支持。
3. 生物信息学:在生物信息学领域,关联规则算法可以用于分析基因、蛋白质等生物分子之间的相互作用关系,从而揭示生物系统的复杂网络结构。
五、研究现状与展望目前,关联规则算法已经广泛应用于各个领域,并取得了显著的成果。
然而,随着数据规模的日益增大和复杂性的提高,传统的关联规则算法面临着诸多挑战。
查找候选码的判定方法在数据挖掘和机器学习领域中,候选码是一种非常重要的概念。
候选码是指在数据集中出现频率较高的一组项集,这些项集可以用来发现数据集中的关联规则。
在实际应用中,如何快速准确地查找候选码是一个非常重要的问题。
本文将介绍一些常用的查找候选码的判定方法。
1. Apriori算法Apriori算法是一种经典的查找候选码的方法。
该算法的基本思想是利用频繁项集的性质,从而减少候选项集的数量。
具体来说,Apriori算法分为两个步骤:(1)生成候选项集:首先扫描数据集,统计每个项的出现次数,然后根据最小支持度阈值,筛选出频繁项集。
接着,利用频繁项集的性质,生成下一级候选项集。
(2)剪枝:对于每个候选项集,检查其所有子集是否都是频繁项集。
如果不是,则该候选项集被剪枝。
通过这两个步骤,Apriori算法可以快速地查找候选码。
但是,该算法存在一些缺点,如需要多次扫描数据集、生成大量的候选项集等。
2. FP-Growth算法FP-Growth算法是一种基于频繁模式树的查找候选码的方法。
该算法的基本思想是将数据集压缩成一棵频繁模式树,然后利用该树来查找候选码。
具体来说,FP-Growth算法分为两个步骤:(1)构建频繁模式树:首先扫描数据集,统计每个项的出现次数,然后根据最小支持度阈值,筛选出频繁项集。
接着,利用频繁项集的性质,构建频繁模式树。
(2)查找候选码:对于每个频繁项集,从其对应的条件模式基中构建一棵条件模式树,然后递归地查找该树中的频繁项集。
通过这种方式,可以快速地查找候选码。
与Apriori算法相比,FP-Growth算法具有更快的速度和更少的内存消耗。
但是,该算法的实现较为复杂,需要对频繁模式树进行多次遍历。
3. Eclat算法Eclat算法是一种基于垂直数据格式的查找候选码的方法。
该算法的基本思想是将数据集转换成垂直数据格式,然后利用该格式来查找候选码。
具体来说,Eclat算法分为两个步骤:(1)转换数据格式:首先将数据集转换成垂直数据格式,即每个项对应一个事务ID集合。
数据挖掘中的关联规则挖掘算法随着数据量的不断增大,如何从海量数据中发现有意义的关联规则成为数据挖掘的一项重要任务。
关联规则挖掘是指在大规模数据集中寻找项集之间的关系,其中一个项集称为前提集(antecedent),另一个项集称为结果集(consequent)。
关联规则挖掘算法可以帮助我们发现数据中隐藏的相关性,为企业做出决策提供支持。
数据挖掘中的关联规则挖掘算法主要包括Apriori算法、FP-Growth算法和ECLAT算法。
这些算法都能有效地从大规模数据集中挖掘关联规则,但其原理和运算方式略有不同。
首先是Apriori算法。
Apriori算法是关联规则挖掘中最早也是最经典的算法之一。
它基于频繁项集的理念进行工作,通过逐层搜索的方式,不断扩展候选项集,从而挖掘出频繁项集和关联规则。
Apriori算法的思想是利用频繁项集性质,从最小的频繁项集开始,逐步扩大项集的大小,直到不能再产生更多的频繁项集为止。
这样可以减少搜索空间,提高算法效率。
Apriori算法的时间复杂度较高,但其优点在于可以挖掘任意大小的频繁项集。
Apriori算法的应用广泛,常用于市场篮子分析、推荐系统等领域。
其次是FP-Growth算法。
FP-Growth算法是一种基于前缀树(FP树)的关联规则挖掘算法。
它通过构建FP树,将数据集压缩成频繁项的紧凑表示,并利用树结构实现高效的关联规则挖掘。
FP-Growth算法首先构建FP树,通过频繁项集的排序和条件模式树的生成,得到频繁项集和条件模式基。
然后,通过递归地挖掘条件模式基,生成关联规则。
FP-Growth算法相对于Apriori算法而言,无需生成候选项集,减少了搜索空间,大大提高了算法的效率。
FP-Growth算法的时间复杂度较低,尤其适用于大规模数据集的关联规则挖掘。
最后是ECLAT算法。
ECLAT算法(Equivalence Class Transformation)是一种基于垂直数据表示的关联规则挖掘算法。
Apriori算法、FP-growth算法和Eclat算法比较分析1、关联分析关联分析是在大规模数据集中寻找有趣关系的任务。
这些关系可以有两种形式:频繁项集、关联规则。
频繁项集是经常出现在一块儿的物品的集合,关联规则暗示两种物品之间可能存在很强的关系。
下面用一个例子来说明:图1给出了某个杂货店的交易清单。
频繁项集是指那些经常出现在一起的商品集合,图中的集合{葡萄酒,尿布,豆奶}就是频繁项集的一个例子。
从这个数据集中也可以找到诸如尿布->葡萄酒的关联规则,即如果有人买了尿布,那么他很可能也会买葡萄酒。
2、Apriori算法Apriori算法使用频繁项集的先验知识,使用一种称作逐层搜索的迭代方法,k项集用于探索(k+1)项集。
首先,通过扫描事务(交易)记录,找出所有的频繁1项集,该集合记做L1,然后利用L1找频繁2项集的集合L2,L2找L3,如此下去,直到不能再找到任何频繁k项集。
最后再在所有的频繁集中找出强规则,即产生用户感兴趣的关联规则。
用下面的实例具体实现Apriori算法:上图为某商场的交易记录,共有9个事务,利用Apriori算法寻找所有的频繁项集的过程如下:详细介绍下候选3项集的集合C3的产生过程:从连接步,首先C3={{I1,I2,I3},{I1,I2,I5},{I1,I3,I5},{I2,I3,I4},{I2,I3,I5},{I2,I4,I5}}(C3是由L2与自身连接产生)。
根据Apriori性质,频繁项集的所有子集也必须频繁的,可以确定有4个候选集{I1,I3,I5},{I2,I3,I4},{I2,I3,I5},{I2,I4,I5}}不可能时频繁的,因为它们存在子集不属于频繁集,因此将它们从C3中删除。
注意,由于Apriori算法使用逐层搜索技术,给定候选k项集后,只需检查它们的(k-1)个子集是否频繁。
将Apriori算法应用于Mushroom.dat数据集时:E:/DataMiningSample/FPmining/Mushroom.dat threshold: 0.25共用时:54015ms共有5545项频繁模式E:/DataMiningSample/FPmining/Mushroom.dat threshold: 0.2共用时:991610ms共有53663项频繁模式由仿真实验结果可知Apriori算法对Mushroom.dat挖掘出来的频繁模式及支持度、频繁模式总数正确,但是算法速度很慢。
大数据常用的算法引言概述:随着信息技术的发展,大数据已经成为了当今社会的热门话题。
大数据的处理和分析需要借助各种算法来提取有价值的信息。
本文将介绍大数据常用的算法,包括聚类分析、关联规则挖掘、分类算法、回归分析和推荐系统算法。
一、聚类分析:1.1 K-means算法:K-means是一种常用的聚类算法,它将数据集分成K个簇,每个簇都有一个代表性的中心点。
该算法通过迭代计算,将数据点分配到最近的簇中,并更新簇的中心点,直到达到收敛条件。
1.2 DBSCAN算法:DBSCAN是一种基于密度的聚类算法,它通过定义邻域半径和最小邻居数来划分簇。
该算法将密度相连的数据点划分为一个簇,并通过扩展核心对象的方式逐渐扩展簇的大小。
1.3 层次聚类算法:层次聚类是一种自底向上或自顶向下的聚类方式。
该算法通过计算数据点之间的相似度或距离来构建聚类树或聚类图,最终将数据点划分为不同的簇。
二、关联规则挖掘:2.1 Apriori算法:Apriori算法是一种挖掘频繁项集和关联规则的经典算法。
该算法通过迭代计算,生成候选项集,并通过剪枝策略来减少计算量。
最终,Apriori 算法可以找到频繁项集和关联规则。
2.2 FP-growth算法:FP-growth算法是一种基于前缀树的关联规则挖掘算法。
该算法通过构建FP树来表示数据集,并利用频繁模式的特性来高效地挖掘关联规则。
2.3 Eclat算法:Eclat算法是一种基于垂直数据格式的关联规则挖掘算法。
该算法通过交易数据库的交易项集来构建倒排索引表,并利用倒排索引表来高效地挖掘频繁项集和关联规则。
三、分类算法:3.1 决策树算法:决策树是一种基于树结构的分类算法。
该算法通过对数据集进行递归划分,构建一个树状模型,用于预测新数据的分类。
常用的决策树算法包括ID3、C4.5和CART。
3.2 支持向量机算法:支持向量机是一种二分类的线性分类算法,它通过在特征空间中构建一个超平面来进行分类。
Apriori算法、FP-growth算法和Eclat算法比较分析
1、关联分析
关联分析是在大规模数据集中寻找有趣关系的任务。
这些关系可以有两种形式:频繁项集、关联规则。
频繁项集是经常出现在一块儿的物品的集合,关联规则暗示两种物品之间可能存在很强的关系。
下面用一个例子来说明:图1给出了某个杂货店的交易清单。
频繁项集是指那些经常出现在一起的商品集合,图中的集合{葡萄酒,尿布,豆奶}就是频繁项集的一个例子。
从这个数据集中也可以找到诸如尿布->葡萄酒的关联规则,即如果有人买了尿布,那么他很可能也会买葡萄酒。
2、Apriori算法
Apriori算法使用频繁项集的先验知识,使用一种称作逐层搜索的迭代方法,k项集用于探索(k+1)项集。
首先,通过扫描事务(交易)记录,找出所有的频繁1项集,该集合记做L1,然后利用L1找频繁2项集的集合L2,L2找L3,如此下去,直到不能再找到任何频繁k项集。
最后再在所有的频繁集中找出强规则,即产生用户感兴趣的关联规则。
用下面的实例具体实现Apriori算法:
上图为某商场的交易记录,共有9个事务,利用Apriori算法寻找所有的频繁项集的过程如下:
详细介绍下候选3项集的集合C3的产生过程:从连接步,首先C3={{I1,I2,I3},{I1,I2,I5},{I1,I3,I5},{I2,I3,I4},{I2,I3,I5},{I2,I4,I5}}(C3是由L2与自身连接产生)。
根据Apriori性质,频繁项集的所有子集也必须频繁的,可以确定有4个候选集{I1,I3,I5},{I2,I3,I4},{I2,I3,I5},{I2,I4,I5}}不可能时频繁的,因为它们存在子集不属于频繁集,因此将它们从C3中删除。
注意,由于Apriori算法使用逐层搜索技术,
给定候选k项集后,只需检查它们的(k-1)个子集是否频繁。
将Apriori算法应用于Mushroom.dat数据集时:
E:/DataMiningSample/FPmining/Mushroom.dat threshold: 0.25
共用时:54015ms
共有5545项频繁模式
E:/DataMiningSample/FPmining/Mushroom.dat threshold: 0.2
共用时:991610ms
共有53663项频繁模式
由仿真实验结果可知Apriori算法对Mushroom.dat挖掘出来的频繁模式及支持度、频繁模式总数正确,但是算法速度很慢。
这种算法虽然比遍历的方法要好很多,但其空间复杂度还是非常高的,尤其是L1 比较大时,L2 的数量会暴增。
每次增加频繁项集的大小,Apriori算法都会重新扫描整个数据集,开销也非常大。
即便如此apriori 算法在很多场景下也足够用。
在R语言中使用arules 包来实现此算法(封装的是C实现,只要装载的sparse matrix 可以载入内存,support 设置合理,速度非常快)。
3、FP-growth算法
FP-growth算法基于Apriori构建,可以不用每次都扫描全表,而是用一个简洁的数据结构(压缩之后的数据库)把整个数据库的信息都包含进去,通过对数据结构的递归就完成整个频繁模式的挖掘,只对数据库进行两次扫描。
所以运算速度优于Apriori算法。
这个算法因为数据结构的size 远远小于原始的数据库,所有的数据操作可以完全在内存中计算,挖掘速度就可以大大提高。
具体的算法步骤如下:
(1)、读取数据库,构造频繁1项集及FP-tree
(2)、遍历FP-tree的头表,对于每个频繁项x,累积项x的所有前缀路径形成x的条件模式库CPB
(3)、对CPB上每一条路径的节点更新计数为x的计数,根据CPB构造条件FP-tree
(4)、从条件FP-tree中找到所有长路径,对该路径上的节点找出所有组合方式,然后合并计数
(5)、将(4)中的频繁项集与x合并,得到包含x的频繁项集
(6)、循环,直到遍历头表中的所有项
使用上述步骤,对Mushroom.dat数据集做频繁模式挖掘的结果如下:
虽然FP-growth算法已经算是关联规则挖掘算法中较为高效的一种算法,但还是存在着一些不足:
(1)为满足FP-tree的构建和频繁项集的挖掘,FP-tree中节点结构需要设计大量的指针;
(2)生成的频繁项集存在过多的冗余信息;
(3)频繁项头表的遍历耗费了过多的时间。
4、Eclat算法
Eclat算法是一种深度优先算法,采用垂直数据表示形式,在概念格理论的基础上利用基于前缀的等价关系将搜索空间(概念格)划分为较小的子空间(子概念格)。
Eclat算法加入了倒排的思想,加快频繁集生成速度,其算法思想是由频繁k项集求交集,生成候选k+1项集。
对候选k+1项集做裁剪,生成频繁k+1项集,再求交集生成候选k+2项集。
如此迭代,直到项集归一。
具体实现算法步骤如下:
(1)、一次扫描数据库,获得初始数据。
包括频繁1项集,数据库包含的所有items,事务总数(行)transNum,最小支持度minsup=limitValue*trans。
(2)、二次扫描数据库,获得频繁2项集。
(3)、按照Eclat算法,对频繁2项集迭代求交集,做裁剪,直到项集归一。
使用Eclat算法,对mushroom.dat的频繁模式挖掘结果如下:
关联规则算法中的数据通常采用水平数据形式,而采用垂直数据表示的挖掘性能优于水平表示。
Eclat算法在项集规模庞大时,交集操作消耗大量时间和系统内存。
为此,结合划分思想和突出基于概率的先验约束方法,把数据库中的事务划分成多个非重叠部分,对每一部分采用Eclat算法,减少每次"交"操作时项集的规模,从而减少比较次数。
通过基于概率的先验约束,减少产生的局部频繁项集数。
这样的设计具有更高的效率。
5、总结
FP-growth算法是一种用于发现数据集中频繁模式的有效方法。
FP-growth算法利用Apriori原则,执行更快。
Apriori算法产生候选项集,然后扫描数据集来检查它们是否频繁。
由于只对数据集扫描两次,因此FP-growth算法执行更快。
在FP-growth算法中,数据集存储在一个称为FP树的结构中。
FP树构建完成后,
可以通过查找元素项的条件基及构建条件FP树来发现频繁项集。
该过程不断以更多元素作为条件重复进行,直到FP树只包含一个元素为止。
人们主要通过减少扫描数据库次数以及尽可能产生最少的候选项集对Apriori算法进行改进优化,而FP-Growth 算法的改进则主要考虑减少构建FP-growth树产生的消耗以及尽可能千方百计地节省内存,这些算法都只能挖掘单维的布尔型关联规则。
虽然改进算法应用在部分传统数据集中取得了成功,但随着现在数据规模越来越大,应用环境越来越复杂,传统改进算法已经不适应时代的发展要求。
然而,传统Eclat 算法并未充分利用Apriori 先验性质,因此会产生比较多的候选项集。
传统Eclat 算法通过不断地循环,逐个比较两Tidset集合中各个项(事务)的值来求交集。
这种求交集算法通俗简单,但随着事务数规模的不断扩大,Tidset 的规模也会不断扩大,导致算法的比较次数成倍增长,最终影响到Eclat 算法的挖掘效率。
根据对传统算法的仔细分析,发现其存在如下的问题:
(1)、算法的大量操作消耗在Tidset 的求交集过程上,这是原有算法的主要瓶颈之一;
(2)、求交集操作所使用的Tidset 这种数据表示形式,会占用系统大量的内存空间。
依据Eclat算法存在的不足,将散列表与布尔矩阵相结合,提出了散列布尔矩阵的思想,运用这种新的求交集计算方法来改进传统关联规则Eclat算法,加快支持度计数过程,提高频繁项集挖掘效率。
附录:
I.代码
II.检查报告结果:。