Apriori算法、FP-growth算法和Eclat算法比较分析
1、关联分析
关联分析是在大规模数据集中寻找有趣关系的任务。这些关系可以有两种形式：频繁项集、关联规则。频繁项集是经常出现在一块儿的物品的集合，关联规则暗示两种物品之间可能存在很强的关系。
下面用一个例子来说明：图1给出了某个杂货店的交易清单。交易号码商品
4豆奶，莴苣莴苣，尿布，葡萄酒，甜菜豆奶，尿布，葡萄酒，橙汁莴苣，豆奶，尿布，葡萄酒莴苣，豆奶，尿布，橙汁
频繁项集是指那些经常出现在一起的商品集合，图中的集合{葡萄酒,尿布,豆奶}就是频繁项集的一个例子。从这个数据集中也可以找到诸如尿布-&葡萄酒的关联规则，即如果有人买了尿布，那么他很可能也会买葡萄酒。
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.datthreshold:0.25
共用时：54015ms
共有5545项频繁模式
E:/DataMiningSample/FPmining/Mushroom.datthreshold:0.2
共用时：991610ms
共有53663项频繁模式
由仿真实验结果可知Apriori算法对Mushroom.dat挖掘出来的频繁模式及支持度、频繁模式总数正确，但是算法速度很慢。这种算法虽然比遍历的方法要好很多，但其空间复杂度还是非常高的，尤其是L1比较大时，L2的数量会暴增。每次增加频繁项集的大小，Apriori算法都会重新扫描整个数据集，开销也非常大。
即便如此apriori算法在很多场景下也足够用。在R语言中使用arules包来实现此算法（封装的是C实现，只要装载的sparsematrix可以载入内存，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
看过本文章的还看过。。。
apriori与fp-growth与eclat算法比较分析_互联网_it计算机......
http:www. fp_growth 与 apriori 算法比较应用杨威 1,耿立明 2,杨丹 3 辽宁工程技术大学电子与信息工程学院,辽宁葫芦岛(125105) 辽宁工程.........
杨华峰 宋旋婷 任智红梁志溢 贺冠文 主要内容 1 频繁模式挖掘实现概述 apriori算法 fp-growth算法 eclat算法 2 3 4 2 6 算法对比评价 频繁模式挖掘实现概述 ? .........
本文在eclat算法的基础上,提出了一种新的单调和反 单调约束条件下关联规则的挖掘算法。算法综合了cap算法 和cfg架构的特点,避免了apriori算法和fp—growth算法 的.........
本文首先总结了关联规则挖掘算法的研究成果,分析了ais、apriori、fp-growth 等...实验表明, 将ds-eclat算法应用在图书馆管理系统中,在效率和性能上可以满足读者.........
apriori算法和fp-growth算法_it计算机_专业资料。apriori算法和fp-growth算法详解 by王晨曦 apriori算法详解 ? 1 关联分析 关联分析是一种在大规模数据集中.........
关联规则挖掘算法及其应用(apriori,fp-growth,clementine)_it计算机_专业资料。关联规则挖掘算法及其应用(apriori,fp-growth,clementine) .........
fp-growth 算法及演示程序 fp-growth(频繁模式增长)算法是韩家炜老师在 2000 年...(fp-tree),但仍保留项集 关联信息;该算法和 apriori 算法最大的不同有两点:.........
在各种类型的大型数据集上比较每种算法的性能。写一个报告,分析在 哪些情况下(...数据非常稠密的数据集,性能为: fp-growth>apriori>eclat 各算法采用的数据表示.........
本文分析并且实现了fp-growth算法。fp-growth算法的优点是节省时间和空间,对大...在大多数以前的实现中,人们普遍采用了类似于 apriori[2]的算法。这种算法有一.........
二、数据分析和数据挖掘 数据分析和数据挖掘的区别 ? 共同点:都是从收集到的...数据各属性之间隐含的关联性; 代表算法:apriori算法、eclat算法、fp-growth算法 .........
改进策略:fa算法-fp-growth算法与apriori算法的结合 在原数据库得到的fp-tree的基础上,采用apriori算法的方法进行挖掘,挖掘过程中不构 造conditional fp-tree。 .........
其中比较常用的算法有早期的 apriori[5]的算 法,fp-growth 算法,以及这两种...本文旨在为中小电商卖 家(如淘宝、天猫上的店铺)提供一些有效的数据分析,因此在.........
52 eclat 算法的分析及改进张玉芳, 熊忠阳, 耿晓斐...尽管 fp gr ow th 算法有很多优点, 但 是它 ...dmstar组-基于apriori、... 暂无评价 24页 免费 .........
fp-growth fp-tree 汇报人:crstyal-yang 1 背景意义 apriori算法 在产生频繁模式完全集前需要对数据 库进行多次扫描,同时产生大量的候选频繁集, 这就使apriori.........
针对 apriori 算法的缺陷,jiawei han 提出 fp-growth 算法,该算法仅须扫描数据...(2)评价指标和性能分析 fp-growth 在密集的数据集上,一个大数据库能够被有效.........
基于fp_growth算法在学生成绩中的关联规则分析_工学_高等教育_教育专区。这是一...apriori 算法[2] 的主要优点是算法 思路比较简 单, 以递归统 计为基础 ,.........
典型apriori改进算法的分析与比较_工学_高等教育_教育专区。典型apriori改进算法的...3 fp-dfs 算法 在文献中作者以 fp-tree 为基本数据结构, 首先通过新的 .........
基于fp-growth算法的关联规则挖掘算法研究和应用_信息...17 图2 .1 apriori 算法描述. .……,.,.……...[31]和b io_ train一的 测试结果来比较分析 fp-.........
理论和实验表明该算法优于apriori算法。 fp-growth算法 fp-growth算法 其他关联规则挖掘算法约束性关联规则挖掘算法仅设置支持度和置信度阈值,缺乏用户控制,可能产生过.........
■ 24小时热门信息
? apriori算法是挖掘布尔关联规则频繁项集的算法 apriori算法利用频......
apriori算法c语言版_计算机软件及应用_it计算机_专业资料。apriori算法c语言源代码#include
#include <stdio..........
apriori算法_计算机软件及应用_it计算机_专业资料。apriori算法 日 讲述顺序 数据挖掘 关联规则 apriori 算法 三者关系 了解数据挖掘算法所处位置 数据.........
apriori算法详解_计算机软件及应用_it计算机_专业资料。apriori 算法详解之【一、相关概念和核心步骤】 apriori 算法核心步骤 感谢红兰整理的 ppt,简单易懂,现在将.........
■ 相关热门内容
apriori算法实验报告及程序_计算机软件及应用_it计算机_专业资料 暂无评价|0人阅读|0次下载|举报文档 apriori算法实验报告及程序_计算机软件及应用_it计算机_专业.........
- 11 - 1 人员分工黄健、龙云祥两人分工明确,对 apriori 算法都已熟练掌握。 黄健:画出程序流程图,负责实现书上 apriori 基本算法。 龙云祥:熟悉算法,测试程序.........
因此人们开始寻求一种能减少这种系统 1o 开销的更为快捷的算法。 七、实验程序 function my_apriori(x,minsup) %%%%主函数,输入 x 数据集,判断产生.........
apriori算法c语言版_计算机软件及应用_it计算机_专业资料。apriori算法c语言源代码#include
#include <stdio..........
对测试集进行测试 二、频繁项集挖掘 目前频繁项集挖掘已经有很多比较成熟的算法,在网上也可以找到相关的优秀论文或源代 码。算法中最经典的莫过于 apriori 算法,.........
apriori 算法描述如下 getoridata(); 获取原始数据集,并统计事务个数 产生输出候选 1 项集 产生频繁项集 根据频繁 1 项集,执行程序 gencanitemset.........
apriori算法流程图_计算机软件及应用_it计算机_专业资料。apriori算法,数据挖掘经典算法算法开始 扫描数据库,对每个项进行计数 候选1项集 是否大于最大支持数 y 频.........
apriori算法及java实现_计算机软件及应用_it计算机_专业资料。apriori算法详解及java代码实现 1 apriori 介绍 apriori 算法使用频繁项集的先验知识,使用一种称作逐层.........
■ 热门推荐大数据时代算法：机器学习、人工智能及其典型实例
来源：数据猿 作者：abby
中国在很早就开始了算法研究，如《周髀算经》《九章算术》这类最具历史的算法书籍，后来的唐宋元明清各历史朝代也出现了《一位算法》《算法绪论》《算法全书》《算法统宗》等一系列算法名著，算法已经成为各行各业的基础研究。
今天，小编为大家推荐的《大数据时代的算法：机器学习、人工智能及其典型实例》就主要介绍了在互联网行业中经常涉及的算法，包括排序算法、查找算法、资源分配算法、路径分析算法、相似度分析算法，以及与机器学习相关的算法，包括数据分类算法、聚类算法、预测与估算算法、决策算法、关联规则分析算法及推荐算法。《大数据时代的算法：机器学习、人工智能及其典型实例》涉及的相关算法均为解决实际问题中的主流算法，对于工作和学习都有实际参考意义。
《大数据时代的算法：机器学习、人工智能及其典型实例》通过介绍在互联网行业中经常涉及的算法，包括排序算法、查找算法、资源分配算法、路径分析算法、相似度分析算法，以及与机器学习相关的算法，包括数据分类算法、聚类算法、预测与估算算法、决策算法、关联规则分析算法及推荐算法。本书是一本算法领域内的技术手册，涵盖数十种算法，不仅能使读者深入了解各类算法的基本理论，还从应用的角度提供了大量实例，使读者能够快速、高效进阶各类算法，并能够熟练应用到将来的工作实践中。
本书不仅将目前工程应用中主流的基础算法和机器学习算法都做了详尽的介绍，还囊括了当前热门算法内容，如数据分类算法、聚类算法、推荐算法等。本书充分利用了最新算法的应用研究结果，通过实例为读者展现了清晰的算法应用，不拘泥于算法枯燥的理论，更多地从实用价值、工程价值的角度将算法知识呈现给读者。
本书中的算法可以广泛应用于各个领域，可以在自然语言处理研究、数据分析与挖掘、商务智能、广告与商品推荐等领域中深入应用。作者秉承数据结合算法产生价值的理论体系，在介绍算法的同时与数据紧密关联，并结合多年实际工作经验，将算法的内容阐述得淋漓尽致。本书中的算法研究在当前甚至未来相当一段时间内都具有很大的实际意义。
本书从内容上分为10个章节：
第1章 算法基础
从算法的分析类型，如分治法、动态规划法、回溯法、分支限界法、贪心法入手开始介绍算法内容，还分析了算法的性能，并介绍了概率论与数理统计基础部分的内容。同时，对算法中常用的距离计算算法、排序算法及字符串压缩编码也做了完整介绍。
第2章 数据查找与资源分配算法
以数据的查找和资源分配作为突破口，介绍了常用的数值查找算法，如二分搜索算法、分块查找及哈希查找算法。除此之外，还介绍了常见的字符串查找算法及在海量数据中的查找算法：布隆过滤器和倒排索引查找，介绍了资源分配算法，包括常用的银行家算法和背包问题的解决算法。
第3章 路径分析算法
主要介绍了路径分析算法，包括基于Dijkstra算法、Floyd算法、A*算法的路径分析方法。除了介绍传统的路径分析算法外，还介绍了维特比算法在概率中的路径选择，以及最长公共子串、最长公共子序列问题的求解算法。整个内容涵盖了绝大部分的路径选择算法。
第4章 相似度分析算法
主要介绍了相似内容的分析理论和应用，从简单的Jaccard相似系数开始入手，逐步深入到基于MinHash的相似性算法以及向量空间模型，向量空间模型已经成为众多算法的基础理论。后续还深入介绍了基于余弦相似性算法和基于语义主题模型的语义相似度算法，以及基于SimHash的指纹码重复值验证算法。
第5章 数据分类算法
集中介绍了数据分类算法的解决方案，从简单易于理解的朴素贝叶斯模型开始，由浅入深地介绍了AdaBoost分类器及支持向量机，它们都是数据分类的有效解决方案，还对机器学习的相关基础知识做了概要介绍，最后介绍了K邻近算法在数据分类中的应用。
第6章 数据聚类算法
介绍了数据聚类的相关算法，其中，无监督的聚类算法目前是比较热门的研究领域。首先介绍了传统的基于系统聚类的方法；然后介绍了基于K-Means聚类算法及基于密度的DBSCAN算法；最后介绍了基于BIRCH算法的聚类分析，通过聚类特征及聚类特征实现数据聚类。
第7章 数据预测与估算算法
介绍了数据的预测和估算的算法体系和应用范例，从产生式模型和判别式模型入手介绍各类模型的方法论。首先介绍了基于最大似然估计的预测以及基于线性回归的估算、基于最大期望算法；然后介绍了基于隐马尔科夫模型模型预测；最后介绍了基于条件随机场的序列预测。
第8章 数据决策分析算法
对数据决策的分析方法做了详细介绍，主要围绕决策树的理论基础展开。首先介绍了基于ID3算法的决策分析，包括信息熵、信息增益等；然后介绍了基于C4.5算法的分类决策树及基于分类回归树的决策划分；最后介绍了基于随机森林的决策分类。介绍过程中包含了大量实例。
第9章 数据关联规则分析算法
主要介绍了关联规则分析方法的理论和实践。Apriori算法作为最常用的关联规则分析算法已经被广泛应用到各个领域，本章也对Apriori算法进行了深入的介绍，并对和Apriori算法同等重要的FP-Growth算法也通过实例做了详细介绍。本章最后还介绍了利用倒排文件思想的Eclat算法。
第10章 数据与推荐算法
主要介绍了数据与推荐算法中的应用关系，推荐算法作为目前各行各业最热门的算法之一，已经应用非常广泛。本章介绍了基于物品本身属性关系的Item-Based协同过滤推荐算法，以及基于User-Based协同过滤推荐算法。除此之外，还介绍了基于流行度和潜在因子的推荐算法，以及推荐算法的效果评估相关内容。
适读人群：
对基本算法和机器学习算法有兴趣的读者；
对数据分析和统计学有兴趣的读者；
对算法有研究的基础算法、机器学习工程师；
互联网行业的不同层次从业者；
软件或计算机专业的在校大学生。
责任编辑：
声明：本文由入驻搜狐公众平台的作者撰写，除搜狐官方账号外，观点仅代表作者本人，不代表搜狐立场。29272人阅读
JAVA（12）
数据挖掘（26）
关于本项目下载及运行的常见问题 FAQ见 )一、Apriori算法& & & &Apriori是非常经典的关联分析频繁模式挖掘算法，其思想简明，实现方便，只是效率很低，可以作为频繁模式挖掘的入门算法。其主要特点是& & & &1、k-1项集连接规律：若有两个k-1项集，每个项集保证有序，如果两个k-1项集的前k-2个项相同，而最后一个项不同，则证明它们是可连接的，可连接生成k项集。& & & &2、反单调性。如果一个项集是频繁的，那么它的所有子集都是频繁的。即若一个项集的子集不是频繁项集，则该项集肯定也不是频繁项集。& & & &主要算法流程：& & &&1. 扫描数据库，生成候选1项集和频繁1项集。& & & 2. 从2项集开始循环，由频繁k-1项集生成频繁频繁k项集。& & & 2.1 &频繁k-1项集两两组合，判定是否可以连接，若能则连接生成k项集。& & & 2.2 &对k项集中的每个项集检测其子集是否频繁，舍弃掉子集不是频繁项集即 & 不在频繁k-1项集中的项集。& & & 2.3 &扫描数据库，计算2.3步中过滤后的k项集的支持度，舍弃掉支持度小于阈值的项集，生成频繁k项集。& & & 3. &若当前k项集中只有一个项集时循环结束。& & & 伪代码如下：& & JAVA实现代码package com.pku.
import java.io.BufferedR
import java.io.F
import java.io.FileR
import java.io.FileW
import java.io.IOE
import java.util.ArrayL
import java.util.HashM
import java.util.HashS
import java.util.L
import java.util.M
import java.util.S
import java.util.TreeS
/**频繁模式挖掘算法Apriori实现
public class AprioriFPMining {
private int minS//最小支持度
private static List&Set&String&& dataT//以List&Set&String&&格式保存的事物数据库,利用Set的有序性
public int getMinSup() {
return minS
public void setMinSup(int minSup) {
this.minSup = minS
* @param args
public static void main(String[] args) throws IOException {
AprioriFPMining apriori = new AprioriFPMining();
double [] threshold = {0.25, 0.20, 0.15, 0.10, 0.05};
String srcFile = &F:/DataMiningSample/FPmining/Mushroom.dat&;
String shortFileName = srcFile.split(&/&)[3];
String targetFile = &F:/DataMiningSample/FPmining/& + shortFileName.substring(0, shortFileName.indexOf(&.&))+&_fp_threshold&;
dataTrans = apriori.readTrans(srcFile);
for(int k = 0; k & threshold. k++){
System.out.println(srcFile + & threshold: & + threshold[k]);
long totalItem = 0;
long totalTime = 0;
FileWriter tgFileWriter = new FileWriter(targetFile + (threshold[k]*100));
apriori.setMinSup((int)(dataTrans.size() * threshold[k]));//原始蘑菇的数据0.25只需要67秒跑出结果
long startTime = System.currentTimeMillis();
Map&String, Integer& f1Set = apriori.findFP1Items(dataTrans);
long endTime = System.currentTimeMillis();
totalTime += endTime - startT
//频繁1项集信息得加入支持度
Map&Set&String&, Integer& f1Map = new HashMap&Set&String&, Integer&();
for(Map.Entry&String, Integer& f1Item : f1Set.entrySet()){
Set&String& fs = new HashSet&String&();
fs.add(f1Item.getKey());
f1Map.put(fs, f1Item.getValue());
totalItem += apriori.printMap(f1Map, tgFileWriter);
Map&Set&String&, Integer& result = f1M
startTime = System.currentTimeMillis();
result = apriori.genNextKItem(result);
endTime = System.currentTimeMillis();
totalTime += endTime - startT
totalItem += apriori.printMap(result, tgFileWriter);
} while(result.size() != 0);
tgFileWriter.close();
System.out.println(&共用时：& + totalTime + &ms&);
System.out.println(&共有& + totalItem + &项频繁模式&);
/**由频繁K-1项集生成频繁K项集
* @param preMap 保存频繁K项集的map
* @param tgFileWriter 输出文件句柄
* @return int 频繁i项集的数目
* @throws IOException
private Map&Set&String&, Integer& genNextKItem(Map&Set&String&, Integer& preMap) {
// TODO Auto-generated method stub
Map&Set&String&, Integer& result = new HashMap&Set&String&, Integer&();
//遍历两个k-1项集生成k项集
List&Set&String&& preSetArray = new ArrayList&Set&String&&();
for(Map.Entry&Set&String&, Integer& preMapItem : preMap.entrySet()){
preSetArray.add(preMapItem.getKey());
int preSetLength = preSetArray.size();
for (int i = 0; i & preSetLength - 1; i++) {
for (int j = i + 1; j & preSetL j++) {
String[] strA1 = preSetArray.get(i).toArray(new String[0]);
String[] strA2 = preSetArray.get(j).toArray(new String[0]);
if (isCanLink(strA1, strA2)) { // 判断两个k-1项集是否符合连接成k项集的条件　
Set&String& set = new TreeSet&String&();
for (String str : strA1) {
set.add(str);
set.add((String) strA2[strA2.length - 1]); // 连接成k项集
// 判断k项集是否需要剪切掉，如果不需要被cut掉，则加入到k项集列表中
if (!isNeedCut(preMap, set)) {//由于单调性，必须保证k项集的所有k-1项子集都在preMap中出现，否则就该剪切该k项集
result.put(set, 0);
return assertFP(result);//遍历事物数据库，求支持度，确保为频繁项集
/**检测k项集是否该剪切。由于单调性，必须保证k项集的所有k-1项子集都在preMap中出现，否则就该剪切该k项集
* @param preMap k-1项频繁集map
* @param set 待检测的k项集
* @return boolean 是否该剪切
* @throws IOException
private boolean isNeedCut(Map&Set&String&, Integer& preMap, Set&String& set) {
// TODO Auto-generated method stub
boolean flag =
List&Set&String&& subSets = getSubSets(set);
for(Set&String& subSet : subSets){
if(!preMap.containsKey(subSet)){
/**获取k项集set的所有k-1项子集
* @param set 频繁k项集
* @return List&Set&String&& 所有k-1项子集容器
* @throws IOException
private List&Set&String&& getSubSets(Set&String& set) {
// TODO Auto-generated method stub
String[] setArray = set.toArray(new String[0]);
List&Set&String&& result = new ArrayList&Set&String&&();
for(int i = 0; i & setArray. i++){
Set&String& subSet = new HashSet&String&();
for(int j = 0; j & setArray. j++){
if(j != i) subSet.add(setArray[j]);
result.add(subSet);
/**遍历事物数据库，求支持度，确保为频繁项集
* @param allKItem 候选频繁k项集
* @return Map&Set&String&, Integer& 支持度大于阈值的频繁项集和支持度map
* @throws IOException
private Map&Set&String&, Integer& assertFP(
Map&Set&String&, Integer& allKItem) {
// TODO Auto-generated method stub
Map&Set&String&, Integer& result = new HashMap&Set&String&, Integer&();
for(Set&String& kItem : allKItem.keySet()){
for(Set&String& data : dataTrans){
boolean flag =
for(String str : kItem){
if(!data.contains(str)){
if(flag) allKItem.put(kItem, allKItem.get(kItem) + 1);
if(allKItem.get(kItem) &= minSup) {
result.put(kItem, allKItem.get(kItem));
/**检测两个频繁K项集是否可以连接，连接条件是只有最后一个项不同
* @param strA1 k项集1
* @param strA1 k项集2
* @return boolean 是否可以连接
* @throws IOException
private boolean isCanLink(String[] strA1, String[] strA2) {
// TODO Auto-generated method stub
boolean flag =
if(strA1.length != strA2.length){
for(int i = 0; i & strA1.length - 1; i++){
if(!strA1[i].equals(strA2[i])){
if(strA1[strA1.length -1].equals(strA2[strA1.length -1])){
/**将频繁i项集的内容及支持度输出到文件 格式为 模式:支持度
* @param f1Map 保存频繁i项集的容器&i项集 , 支持度&
* @param tgFileWriter 输出文件句柄
* @return int 频繁i项集的数目
* @throws IOException
private int printMap(Map&Set&String&, Integer& f1Map, FileWriter tgFileWriter) throws IOException {
// TODO Auto-generated method stub
for(Map.Entry&Set&String&, Integer& f1MapItem : f1Map.entrySet()){
for(String p : f1MapItem.getKey()){
tgFileWriter.append(p + & &);
tgFileWriter.append(&: & + f1MapItem.getValue() + &\n&);
tgFileWriter.flush();
return f1Map.size();
/**生成频繁1项集
* @param fileDir 事务文件目录
* @return Map&String, Integer& 保存频繁1项集的容器&1项集 , 支持度&
* @throws IOException
private Map&String, Integer& findFP1Items(List&Set&String&& dataTrans) {
// TODO Auto-generated method stub
Map&String, Integer& result = new HashMap&String, Integer&();
Map&String, Integer& itemCount = new HashMap&String, Integer&();
for(Set&String& ds : dataTrans){
for(String d : ds){
if(itemCount.containsKey(d)){
itemCount.put(d, itemCount.get(d) + 1);
itemCount.put(d, 1);
for(Map.Entry&String, Integer& ic : itemCount.entrySet()){
if(ic.getValue() &= minSup){
result.put(ic.getKey(), ic.getValue());
/**读取事务数据库
* @param fileDir 事务文件目录
* @return List&String& 保存事务的容器
* @throws IOException
private List&Set&String&& readTrans(String fileDir) {
// TODO Auto-generated method stub
List&Set&String&& records = new ArrayList&Set&String&&();
FileReader fr = new FileReader(new File(fileDir));
BufferedReader br = new BufferedReader(fr);
String line =
while ((line = br.readLine()) != null) {
if (line.trim() != &&) {
Set&String& record = new HashSet&String&();
String[] items = line.split(& &);
for (String item : items) {
record.add(item);
records.add(record);
} catch (IOException e) {
System.out.println(&读取事务文件失败。&);
System.exit(-2);
硬件环境：Intel Core 2 Duo CPU T5750 2GHZ, 2G内存实验结果F:/DataMiningSample/FPmining/Mushroom.dat threshold: 0.25共用时：54015ms共有5545项频繁模式F:/DataMiningSample/FPmining/Mushroom.dat threshold: 0.2共用时：991610ms共有53663项频繁模式F:/DataMiningSample/FPmining/Mushroom.dat threshold: 0.15结论：对Mushroom.dat挖掘出来的频繁模式及支持度、频繁模式总数正确，但是算法速度很慢，对大数据量如T10I4D100K低阈值挖掘时间太长解决办法：改用C++写FP-Growth算法做频繁模式挖掘！二、FP-Growth算法& & & &FP-Growth算法由数据挖掘界大牛Han Jiawei教授于SIGMOD 00‘大会提出，提出根据事物数据库构建FP-Tree，然后基于FP-Tree生成频繁模式集。主要算法流程如下Step1 读取数据库，构造频繁1项集及FP-treeStep2 遍历FP-tree的头表，对于每个频繁项x，累积项x的所有前缀路径形成x的条件模式库CPBStep3 对CPB上每一条路径的节点更新计数为x的计数，根据CPB构造条件FP-treeStep4 从条件FP-tree中找到所有长路径，对该路径上的节点找出所有组合方式，然后合并计数Step5 将Step4中的频繁项集与x合并，得到包含x的频繁项集Step2-5 循环，直到遍历头表中的所有项由于时间关系，主要基于芬兰教授Bart Goethals的开源代码实现，源码下载见&，文件结构及运行结果如下对Mushroom.dat，accidents.dat和T10I4D100K.dat三个数据集做频繁模式挖掘的结果如下三、Eclat算法& & Eclat算法加入了倒排的思想，加快频繁集生成速度，其算法思想是 由频繁k项集求交集，生成候选k+1项集 。对候选k+1项集做裁剪，生成频繁k+1项集，再求交集生成候选k+2项集。如此迭代，直到项集归一。& & 算法过程：1.一次扫描数据库，获得初始数据。包括频繁1项集，数据库包含的所有items，事务总数（行）transNum，最小支持度minsup=limitValue*trans。2.二次扫描数据库，获得频繁2项集。3.按照Eclat算法，对频繁2项集迭代求交集，做裁剪，直到项集归一。& & & JAVA实现如下package com.pku.
import java.io.BufferedR
import java.io.BufferedW
import java.io.F
import java.io.FileInputS
import java.io.FileNotFoundE
import java.io.FileR
import java.io.FileW
import java.io.IOE
import java.io.InputStreamR
import java.util.ArrayL
import java.util.BitS
import java.util.I
import java.util.S
import java.util.TreeM
import java.util.TreeS
public class EclatRelease {
private File file=new File(&D:/mushroom.dat.txt&);
private float limitValue=0.25f;
private int transNum=0;
private ArrayList&HeadNode& array=new ArrayList&HeadNode&();
private HashHeadNode[] hashT//存放临时生成的频繁项集，作为重复查询的备选集合
public long newItemNum=0;
private File tempFile=
private BufferedWriter bw=
public static long modSum=0;
* 第一遍扫描数据库，确定Itemset,根据阈值计算出支持度数
public void init()
Set itemSet=new TreeSet();
MyMap&Integer,Integer& itemMap=new MyMap&Integer,Integer&();
int itemNum=0;
FileInputStream fis=new FileInputStream(file);
BufferedReader br=new BufferedReader(new InputStreamReader(fis));
String str=
//第一次扫描数据集合
while((str=br.readLine()) != null)
transNum++;
String[] line=str.split(& &);
for(String item:line)
itemSet.add(Integer.parseInt(item));
itemMap.add(Integer.parseInt((item)));
br.close();
// System.out.println(&itemMap lastKey:&+itemMap.lastKey());
// System.out.println(&itemsize:&+itemSet.size());
// System.out.println(&trans: &+transNum);
//ItemSet.limitSupport=(int)Math.ceil(transNum*limitValue);//上取整
ItemSet.limitSupport=(int)Math.floor(transNum*limitValue);//下取整
ItemSet.ItemSize=(Integer)itemMap.lastKey();
ItemSet.TransSize=transN
hashTable=new HashHeadNode[ItemSet.ItemSize*3];//生成项集hash表
for(int i=0;i&hashTable.i++)
hashTable[i]=new HashHeadNode();
// System.out.println(&limitSupport:&+ItemSet.limitSupport);
tempFile=new File(file.getParent()+&/&+file.getName()+&.dat&);
if(tempFile.exists())
tempFile.delete();
tempFile.createNewFile();
bw=new BufferedWriter(new FileWriter(tempFile));
Set oneItem=itemMap.keySet();
int countOneItem=0;
for(Iterator it=oneItem.iterator();it.hasNext();)
int key=(Integer)it.next();
int value=(Integer)itemMap.get(key);
if(value &= ItemSet.limitSupport)
bw.write(key+& &+&:&+& &+value);
bw.write(&\n&);
countOneItem++;
bw.flush();
modSum+=countOneI
itemNum=(Integer)itemMap.lastKey();
a=new TreeSet[itemNum+1][itemNum+1];
array.add(new HeadNode());//空项
for(short i=1;i&=itemNi++)
HeadNode hn=new HeadNode();
// hn.item=i;
array.add(hn);
BufferedReader br2=new BufferedReader(new FileReader(file));
//第二次扫描数据集合,形成2-项候选集
int counter=0;//事务
int max=0;
while((str=br2.readLine()) != null)
String[] line=str.split(& &);
counter++;
for(int i=0;i&line.i++)
int sOne=Integer.parseInt(line[i]);
for(int j=i+1;j&line.j++)
int sTwo=Integer.parseInt(line[j]);
if(a[sOne][sTwo] == null)
Set set=new TreeSet();
set.add(counter);
a[sOne][sTwo]=
a[sOne][sTwo].add(counter);
//将数组集合转换为链表集合
for(int i=1;i&=itemNi++)
HeadNode hn=array.get(i);
for(int j=i+1;j&=itemNj++)
if(a[i][j] != null && a[i][j].size() &= ItemSet.limitSupport)
hn.items++;
ItemSet is=new ItemSet(true);
is.item=2;
is.items.set(i);
is.items.set(j);
is.supports=a[i][j].size();
bw.write(i+& &+j+& &+&: &+is.supports);
bw.write(&\n&);
//统计频繁2-项集的个数
for(Iterator it=a[i][j].iterator();it.hasNext();)
int value=(Integer)it.next();
is.trans.set(value);
if( hn.first== null)
hn.last.next=
bw.flush();
} catch (FileNotFoundException e) {
e.printStackTrace();
} catch (IOException e) {
e.printStackTrace();
public void start()
boolean flag=
//TreeSet ts=new TreeSet();//临时存储项目集合，防止重复项集出现，节省空间
int count=0;
ItemSet shareFirst=new ItemSet(false);
while(flag)
//System.out.println(++count);
for(int i=1;i&array.size();i++)
HeadNode hn=array.get(i);
if(hn.items & 1 )//项集个数大于1
generateLargeItemSet(hn,shareFirst);
clear(hashTable);
bw.close();
} catch (IOException e) {
e.printStackTrace();
public void generateLargeItemSet(HeadNode hn,ItemSet shareFirst){
BitSet bsItems=new BitSet(ItemSet.ItemSize);//存放链两个k-1频繁项集的ItemSet交
BitSet bsTrans=new BitSet(ItemSet.TransSize);//存放两个k-1频繁项集的Trans交
BitSet containItems=new BitSet(ItemSet.ItemSize);//存放两个k-1频繁项集的ItemSet的并
BitSet bsItems2=new BitSet(ItemSet.ItemSize);//临时存放容器BitSet
ItemSet oldCurrent=null,oldNext=
oldCurrent=hn.
long countItems=0;
ItemSet newFirst=new ItemSet(false),newLast=newF
while(oldCurrent != null)
oldNext=oldCurrent.
while(oldNext != null)
//生成k—项候选集，由两个k-1项频繁集生成
bsItems.clear();
bsItems.or(oldCurrent.items);
bsItems.and(oldNext.items);
if(bsItems.cardinality() & oldCurrent.item-1)
//新合并的项集是否已经存在
containItems.clear();
containItems.or(oldCurrent.items);//将k-1项集合并
containItems.or(oldNext.items);
if(!containItems(containItems,bsItems2,newFirst)){
bsTrans.clear();
bsTrans.or(oldCurrent.trans);
bsTrans.and(oldNext.trans);
if(bsTrans.cardinality() &= ItemSet.limitSupport)
ItemSet is=
if(shareFirst.next == null)//没有共享ItemSet链表
is=new ItemSet(true);
newItemNum++;
is=shareFirst.
shareFirst.next=shareFirst.next.
is.items.clear();
is.trans.clear();
is.item=(oldCurrent.item+1);//生成k—项候选集，由两个k-1项频繁集生成
is.items.or(oldCurrent.items);//将k-1项集合并
is.items.or(oldNext.items);//将k-1项集合并
is.trans.or(oldCurrent.trans);//将bs1的值复制到bs中
is.trans.and(oldNext.trans);
is.supports=is.trans.cardinality();
writeToFile(is.items,is.supports);//将频繁项集及其支持度写入文件
countItems++;
newLast.next=
oldNext=oldNext.
oldCurrent=oldCurrent.
ItemSet temp1=hn.
ItemSet temp2=hn.
temp2.next=shareFirst.
shareFirst.next=temp1;
hn.first=newFirst.
hn.last=newL
hn.items=countI
public boolean containItems(BitSet containItems,BitSet bsItems2,ItemSet first)
long size=containItems.cardinality();//项集数目
int itemSum=0;
int temp=containItems.nextSetBit(0);
while(true)
temp=containItems.nextSetBit(temp+1);
if(temp == -1)
int hash=itemSum%(ItemSet.ItemSize*3);
HashNode hn=hashTable[hash].
Node pre=hashTable[hash];
while(true)
if(hn == null)//不包含containItems
HashNode node=new HashNode();
node.bs.or(containItems);
if(hn.bs.isEmpty())
hn.bs.or(containItems);
bsItems2.clear();
bsItems2.or(containItems);
bsItems2.and(hn.bs);
if(bsItems2.cardinality() == size)
public void clear(HashHeadNode[] hashTable)
for(int i=0;i&hashTable.i++)
HashNode node=hashTable[i].
while(node != null)
node.bs.clear();
node=node.
public void writeToFile(BitSet items,int supports)
StringBuilder sb=new StringBuilder();
//sb.append(&&&);
int temp=items.nextSetBit(0);
sb.append(temp);
while(true)
temp=items.nextSetBit(temp+1);
if(temp == -1)
//sb.append(&,&);
sb.append(& &);
sb.append(temp);
sb.append(& :&+& &+supports);
bw.write(sb.toString());
bw.write(&\n&);
} catch (IOException e) {
e.printStackTrace();
public static void main(String[] args) {
EclatRelease e=new EclatRelease();
long begin=System.currentTimeMillis();
e.start();
long end=System.currentTimeMillis();
double time=(double)(end-begin)/1000;
System.out.println(&共耗时&+time+&秒&);
System.out.println(&频繁模式数目:&+EclatRelease.modSum);
class MyMap&T,E& extends TreeMap
public void add(T obj)
if(this.containsKey(obj))
int value=(Integer)this.get(obj);
this.put(obj, value+1);
this.put(obj, 1);
}ItemSet类如下package com.pku.
import java.util.BitS
public class ItemSet {
public static
int limitS//根据阈值计算出的最小支持度数
public static int ItemS//Items数目
public static int TransS //事务数目
public boolean flag= //true，表示作为真正的ItemSet,false只作为标记节点，只在HashTabel中使用
public int item=0;// 某项集
public int supports=0;//项集的支持度
public BitSet items=
public BitSet trans=
//public TreeSet items=new TreeSet();//项集
//public TreeSet trans=new TreeSet();//事务集合
public ItemSet next=//下一个项集
public ItemSet(boolean flag)
this.flag=
item=0;// 某项集
supports=0;//项集的支持度
items=new BitSet(ItemSize+1);
trans=new BitSet(TransSize+1);
对mushroom.dat的频繁模式挖掘结果如下后期打算实现北大邓志鸿老师提出的PPV-Tree算法(基于节点列表的频繁模式挖掘算法)，挖掘速度超过Han Jiawei教授的FP-Growth算法，敬请关注:)
&&相关文章推荐
* 以上用户言论只代表其个人观点，不代表CSDN网站的观点或立场
访问：1231725次
积分：12619
积分：12619
排名：第991名
原创：240篇
转载：36篇
评论：741条
(1)(3)(3)(4)(1)(9)(5)(6)(4)(19)(13)(25)(2)(13)(7)(2)(1)(1)(1)(1)(1)(4)(1)(6)(3)(2)(2)(4)(9)(11)(5)(24)(17)(1)(27)(36)(1)(2)(2)