apriori && fpgrowth:频繁模式与关联规则挖掘
详细代码我放在github上:click me 一、实验说明1.1 任务描述1.2 数据集说明
二、代码设计与实现对apriori算法手动实现了一个dummy版本和一个advanced版本,dummy版本没有使用剪枝的trick,使用暴力的方法生成候选项级,対事务表不做任何处理。而advanced版本则在dummy版本的基础上加入了一剪枝的trick,性能更胜一筹。对fpgrowth算法使用了已有的python包,其中的实现细节没有深入去review了。下面对这几份代码的详细设计与实现做一个说明。 2.1 dummy apriori从命令行接收算法的控制参数 if len(sys.argv) != 4: print('usage: python apriori_dummy.py dataset-path support-ratio K') else: dataset_path_name = sys.argv[1] # 要处理的数据集GroceryStore or UNIX_usage min_sup = float(sys.argv[2]) # 支持率 itemset_size = int(sys.argv[3]) # 要挖掘的最大频繁项集大小 读取数据集之后每一事务以set形式存储在一个列表data中,然后匹配、统计生成频繁一项集: oneitem_freq = {} for itemset in data: for item in itemset: oneitem_freq[item] = 0 for itemset in data: for item in itemset: oneitem_freq[item] += 1 oneitem_freqset = [] for oneitem in oneitem_freq.keys(): if oneitem_freq[oneitem] >= frequency_threshold: oneitem_freqset.append([oneitem]) 接下来就进入循环过程:由k项频繁项集生成k+1项候选项集,然后匹配事务表统计频次,筛选出高于支持率对应频次的作为k+1项频繁项集,以此往复循环直到生成的频繁项集为空或者达到要挖掘的频繁项集大小的上限。 pre_freqset = oneitem_freqset for k in range(2,itemset_size + 1): start_time = time.time() candidates_k = generate_candidates(pre_freqset) k_item_freq = count_freqset(data,candidates_k) pre_freqset = [] new_k_item_freq = {} for key in k_item_freq.keys(): if k_item_freq[key] >= frequency_threshold: pre_freqset.append(sorted(key.split(','))) new_k_item_freq[','.join(pre_freqset[-1])] = k_item_freq[key] k_item_freq = new_k_item_freq if len(pre_freqset) == 0: break pre_freqset.sort() output(pre_freqset,k_item_freq,frequency_threshold,k,dataset_path_name) 这段主控制程序中调用了2个甚为关键的函数:generate_candidates用于生成候选项集,count_freqset用于匹配事务表进行统计。 generate_candidates: 使用纯暴力拼接的方式,由上一轮的k频繁项集构成的单项元素集合中每一个元素与任一k频繁项连接(前提是该单项元素不出现在这一频繁项中)构成一个k+1候选项 def generate_candidates(pre_freqset): """ 由k-1的频繁项集生成k候选项集 :param pre_freqset: 前一次生成的k-1频繁项集 :param k: 要生成的k频繁项集对应的k :return: 包含k候选项集的列表 """ items = [] for itemset in pre_freqset: for item in itemset: items.append(item) items = list(set(items)) candidates = [] for itemset in pre_freqset: for item in items: if item not in itemset: itemset_backup = copy.deepcopy(itemset) itemset_backup.append(item) candidates.append(','.join(sorted(itemset_backup))) candidates_unique = [] candidates = set(candidates) for can in candidates: candidates_unique.append(can.split(',')) return candidates_unique count_freqset: 对由generate_candidates生成的每一候选项在事务表中扫描匹配,统计出现频次 def count_freqset(data,candidates_k): """ 对照事务表统计候选项集频次 :param data: 事务集 :param candidates_k: k候选项集 :return: 候选项映射到频次的dict """ counter = {} for can in candidates_k: canset = set(can) canstr = ','.join(can) counter[canstr] = 0 for itemset in data: if canset <= itemset: counter[canstr] += 1 return counter 2.2 advanced aprioriadvanced apriori在dummy apriori的基础上加入了一些剪枝的技巧,包括减小生成候选项集的规模、不断减少事务表规模。
2.3 基于apriori的频繁项集挖掘关联规则基于每论迭代得到的k-频繁项集,对其中每一k-频繁项利用二进制法构造其所有势大于0的子集 def get_all_subsets(itemset): """ 计算itemset的所有势大于0的子集 :param itemset: 包含一个项集的列表 :return: 项集itemset的所有势大于0的子集(type: list(set...)) """ n = len(itemset) all_subsets = [] for i in range(1,2**(n - 1)): subset = set() for j in range(n): if (i >> j) % 2 == 1: subset.add(itemset[j]) all_subsets.append(subset) return all_subsets 任一子集与该子集和生成它的父集k-频繁项之间的差集构造k项的关联规则,筛选出大于置信度且提升度大于1.0的关联规则作为要挖掘的强关联规则 def generate_association_rules(k_freqset,itemset_freq,min_con,dataset_size): """ 生成关联规则 :param k_freqset: k频繁项集 :param itemset_freq: 项集与频次之间的字典映射 :param min_con: 置信度 :param dataset_size: 数据集记录总数 :return: 关联规则列表(list(list(previous item,post item,frequency)...)) """ association_rules = [] for i in range(len(k_freqset)): all_subsets = get_all_subsets(k_freqset[i]) par_set = set(k_freqset[i]) par_cnt = itemset_freq[','.join(k_freqset[i])] for subset in all_subsets: subset_str = ','.join(sorted(list(subset))) diffset_str = ','.join(sorted(list(par_set.difference(subset)))) subset_cnt = itemset_freq[subset_str] diffset_cnt = itemset_freq[diffset_str] subset_prob = 1.0 * subset_cnt / dataset_size diffset_prob = 1.0 * diffset_cnt / dataset_size if 1.0 * par_cnt / subset_cnt >= min_con and 1.0 * par_cnt / (subset_cnt * diffset_prob) >= 1.0: association_rules.append([subset_str,diffset_str,1.0 * par_cnt / subset_cnt]) elif 1.0 * par_cnt / diffset_cnt >= min_con and 1.0 * par_cnt / (diffset_cnt * subset_prob) >= 1.0: association_rules.append([diffset_str,subset_str,1.0 * par_cnt / diffset_cnt]) return association_rules 2.4 fpgrowth这里没有多少要讲的,直接调用接口 import pyfpgrowth data = [] read(data,dataset_path_name) freq_patterns = pyfpgrowth.find_frequent_patterns(data,frequency_threshold) association_rules = pyfpgrowth.generate_association_rules(freq_patterns,min_con) 三、实验结果及分析对比3.1 实验结果展示
&,-l,<1>,<2>,cd : 131 &,>,cd : 142 &,rm : 111 &,cd,cp : 139 &,ll : 193 &,ls : 198 &,mv : 155 &,rm : 217 &,vi : 209 &,ll,rm : 127 &,vi : 132 &,ls,mv,rm : 114
bottled water,other vegetables,whole milk : 106 butter,whole milk : 113 citrus fruit,root vegetables : 102 citrus fruit,whole milk : 128 citrus fruit,whole milk,yogurt : 101 curd,yogurt : 99 domestic eggs,whole milk : 121 fruit/vegetable juice,whole milk : 103 other vegetables,pastry,whole milk : 104 other vegetables,pip fruit,whole milk : 133
butter,other vegetables -> whole milk confidence:0.5736040609137056 citrus fruit,root vegetables -> other vegetables confidence:0.5862068965517241 curd,yogurt -> whole milk confidence:0.5823529411764706 domestic eggs,other vegetables -> whole milk confidence:0.5525114155251142 other vegetables,pip fruit -> whole milk confidence:0.5175097276264592 rolls/buns,root vegetables -> other vegetables confidence:0.502092050209205 root vegetables,tropical fruit -> other vegetables confidence:0.5845410628019324
curd,yogurt -> whole milk confidence: 0.5823529411764706 butter,other vegetables -> whole milk confidence: 0.5736040609137056 domestic eggs,other vegetables -> whole milk confidence: 0.5525114155251142 other vegetables,whipped/sour cream -> whole milk confidence: 0.5070422535211268 other vegetables,pip fruit -> whole milk confidence: 0.5175097276264592
从上面挖掘出的关联规则可以发现,GroceryStore数据集的相关度很低,将置信度调到0.5的才挖掘到少量的关联规则,但是置信度不高并不一定代表它就没什么意义,上面列出的几条规则人眼观察还是很合理的,从如此多的数据记录中只挖掘出少量的几条关联规则使其更直观更具有参考价值,挖出太多关联规则反而更容易让人眼花缭乱,从而失去判断。反观在UNIX_usage上挖掘出的关联规则,置信度高而且数量又多,但很多都看起来让人难以理解,意义不大,但还是可以大致看出来哪些命令经常一起共用。fpgrowth算法在UNIX_usage数据集上运行时递归深度太深而没能跑出结果来。 3.2 时间性能对比3.2.1 频繁项集挖掘3.2.1.1 UNIX_usage Dataset对比dummy apriori,仅剪枝候选项集规模的advanced_1 apriori,剪枝候选项集规模和事务表规模的advanced_2 apriori在相同数据集、实验环境和实验参数下的时间损耗(单位:秒/s)
下面表格中以da表示dummy apriori,a1a表示advance_1 apriori,a2a表示advanced_2 apriori
3.2.1.2 GroceryStore Dataset
3.2.2 关联规则挖掘3.2.2.1 UNIX_usage Dataset
3.2.2.2 GroceryStore Dataset
3.2.3 简要分析从两个数据集的表现来看,advanced_2 apriori性能是最好的,advanced_1 apriori性能与advanced_2 apriori性能相近,在较小的数据集GroceryStore上差距在毫秒级别,在较大数据集UNIX_usage上差距在几秒以内。而advanced apriori的两个算法相比dummy apriori在时间性能上提升了好几倍。由此可知,时间性能的主要提升点在减小候选项集规模,减小事务表规模的时间性能提升效果不明显,但是当数据规模较大时也能带来秒级的性能提升。在aporiori挖掘出的频繁项集基础上挖掘强关联规则的时间消耗基本与只作频繁项集挖掘的时间消一致,这是因为k-频繁项的k还比较小,生成的子集不多,相对于候选集生成与数据记录扫描匹配的时间复杂度可忽略不计,这才使得两者时间消耗基本一致。当频繁项足够长时,子集的数目是呈指数增长的,那是复杂度将变得让人难以接受,因此使用apriori挖掘关联规则时最好限制要挖掘的最大频繁项的大小。 3.3 内存占用对比3.3.1 UNIX_usage Dataset
3.3.2 GroceryStore Dataset
3.3.3 简要分析对比advanced_1 apriori和advanced_2 apriori的内存消耗基本一致,在程序运行期间比较平稳,而dummy apriori相比advanced apriori占用内存较大,峰值达到了advanced apriori的2倍以上,主要消耗在暴力穷举候选项集,导致候选项集规模太大,占用内存过多。 (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |