数据挖掘--频繁集测试--Apriori算法--java实现

标签: 数据挖掘 测试 apriori | 发表时间:2013-11-16 01:01 | 作者:fufengrui
出处:http://blog.csdn.net

Apriori算法原理:

如果某个项集是频繁的,那么它所有的子集也是频繁的。如果一个项集是非频繁的,那么它所有的超集也是非频繁的。

示意图

图一:

图二:


package cn.ffr.frequent.apriori;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.net.URL;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Set;

/**
 * Apriori的核心代码实现
 * @author [email protected]
 */
public class Apriori {
	
	public static final String STRING_SPLIT = ",";
	
	/**
	 * 主要的计算方法
	 * @param data 数据集
	 * @param minSupport 最小支持度
	 * @param maxLoop 最大执行次数,设NULL为获取最终结果
	 * @param containSet 结果中必须包含的子集
	 * @return
	 */
	public Map<String, Double> compute(List<String[]> data, Double minSupport, Integer maxLoop, String[] containSet){
	
		//校验
		if(data == null || data.size() <= 0){
			return null;
		}
		
		//初始化
		Map<String, Double> result = new HashMap<String, Double>();
		Object[] itemSet = getDataUnitSet(data);
		int loop = 0;
		//核心循环处理过程
		while(true){
			//重要步骤一:合并,产生新的频繁集
			Set<String> keys = combine(result.keySet(), itemSet);
			result.clear();//移除之前的结果
			for(String key : keys){				
				result.put(key, computeSupport(data, key.split(STRING_SPLIT)));
			}
			//重要步骤二:修剪,去除支持度小于条件的。
			cut(result, minSupport, containSet);
			loop++;
			//输出计算过程
			System.out.println("loop ["+loop+"], result : "+result);
			//循环结束条件
			if(result.size() <= 0){
				break;
			}
			if(maxLoop != null && maxLoop > 0 && loop >= maxLoop){//可控制循环执行次数
				break;
			}
		}
		return result;
	}

	/**
	 * 计算子集的支持度
	 * 
	 * 支持度 = 子集在数据集中的数据项 / 总的数据集的数据项
	 * 
	 * 数据项的意思是一条数据。
	 * @param data 数据集
	 * @param subSet 子集 
	 * @return
	 */
	public Double computeSupport(List<String[]> data, String[] subSet){
		Integer value = 0;
		for(int i = 0; i < data.size(); i++){
			if(contain(data.get(i), subSet)){
				value ++;
			}
		}
		return value*1.0/data.size();
	}
	/**
	 * 获得初始化唯一的数据集,用于初始化
	 * @param data
	 * @return
	 */
	public Object[] getDataUnitSet(List<String[]> data){
		List<String> uniqueKeys = new ArrayList<String>();
		for(String[] dat : data){
			for(String da : dat){
				if(!uniqueKeys.contains(da)){
					uniqueKeys.add(da);
				}
			}
		}
		return uniqueKeys.toArray();
	}
	/**
	 * 合并src和target来获取频繁集
	 * 增加频繁集的计算维度
	 * @param src
	 * @param target
	 * @return
	 */
	public Set<String> combine(Set<String> src, Object[] target){
		Set<String> dest = new HashSet<String>();
		if(src == null || src.size() <= 0){
			for(Object t : target){
				dest.add(t.toString());
			}
			return dest;
		}
		for(String s : src){
			for(Object t : target){
				if(s.indexOf(t.toString())<0){
					String key = s+STRING_SPLIT+t;
					if(!contain(dest, key)){
						dest.add(key);
					}
				}
			}
		}
		return dest;
	}
	/**
	 * dest集中是否包含了key
	 * @param dest
	 * @param key
	 * @return
	 */
	public boolean contain(Set<String> dest, String key){
		for(String d : dest){
			if(equal(d.split(STRING_SPLIT), key.split(STRING_SPLIT))){
				return true;
			}
		}
		return false;
	}
	/**
	 * 移除结果中,支持度小于所需要的支持度的结果。
	 * @param result
	 * @param minSupport
	 * @return
	 */
	public Map<String, Double> cut(Map<String, Double> result, Double minSupport, String[] containSet){
		for(Object key : result.keySet().toArray()){//防止 java.util.ConcurrentModificationException,使用keySet().toArray()
			if(minSupport != null && minSupport > 0 && minSupport < 1 && result.get(key) < minSupport){//比较支持度
				result.remove(key);
			}
			if(containSet != null && containSet.length > 0 && !contain(key.toString().split(STRING_SPLIT), containSet)){
				result.remove(key);
			}
		}
		return result;
	}
	/**
	 * src中是否包含dest,需要循环遍历查询
	 * @param src
	 * @param dest
	 * @return
	 */
	public static boolean contain(String[] src, String[] dest){
		for(int i = 0; i < dest.length; i++){
			int j = 0;
			for(; j < src.length; j++){
				if(src[j].equals(dest[i])){
					break;
				}
			}
			if(j == src.length){
				return false;//can not find
			}
		}
		return true;
	}
	/**
	 * src是否与dest相等
	 * @param src
	 * @param dest
	 * @return
	 */
	public boolean equal(String[] src, String[] dest){
		if(src.length == dest.length && contain(src, dest)){
			return true;
		}
		return false;
	}
	/**
	 * 主测试方法
	 * 测试方法,挨个去掉注释,进行测试。
	 */
	public static void main(String[] args) throws Exception{
		//test 1
//		List<String[]> data = loadSmallData();
//		Long start = System.currentTimeMillis();
//		Map<String, Double> result = new Apriori().compute(data, 0.5, 3, null);//求支持度大于指定值
//		Long end = System.currentTimeMillis();
//		System.out.println("Apriori Result [costs:"+(end-start)+"ms]: ");
//		for(String key : result.keySet()){
//			System.out.println("\tFrequent Set=["+key+"] & Support=["+result.get(key)+"];");
//		}
		
		//test 2
//		List<String[]> data = loadMushRoomData();
//		Long start = System.currentTimeMillis();
//		Map<String, Double> result = new Apriori().compute(data, 0.3, 4, new String[]{"2"});//求支持度大于指定值
//		Long end = System.currentTimeMillis();
//		System.out.println("Apriori Result [costs:"+(end-start)+"ms]: ");
//		for(String key : result.keySet()){
//			System.out.println("\tFrequent Set=["+key+"] & Support=["+result.get(key)+"];");
//		}
		
		//test 3
		List<String[]> data = loadChessData();
		Long start = System.currentTimeMillis();
		Map<String, Double> result = new Apriori().compute(data, 0.95, 3, null);//求支持度大于指定值
		Long end = System.currentTimeMillis();
		System.out.println("Apriori Result [costs:"+(end-start)+"ms]: ");
		for(String key : result.keySet()){
			System.out.println("\tFrequent Set=["+key+"] & Support=["+result.get(key)+"];");
		}
	}
	/*
	 *	SmallData: minSupport 0.5, maxLoop 3, containSet null, [costs: 16ms]
	 *	MushRoomData: minSupport 0.3, maxLoop 4, containSet {"2"}, [costs: 103250ms]	
	 *	ChessData: minSupport 0.95, maxLoop 34, containSet {null, [costs: 9718ms]
	 */
	
	//测试数据集-1
	public static List<String[]> loadSmallData() throws Exception{
		List<String[]> data = new ArrayList<String[]>();
		data.add(new String[]{"d1","d3","d4"});
		data.add(new String[]{"d2","d3","d5"});
		data.add(new String[]{"d1","d2","d3","d5"});
		data.add(new String[]{"d2","d5"});
		return data;
	}
	
	//测试数据集-2
	public static List<String[]> loadMushRoomData() throws Exception{
		String link = "http://fimi.ua.ac.be/data/mushroom.dat";
		URL url = new URL(link);
		BufferedReader reader = new BufferedReader(new InputStreamReader(url.openStream()));
		String temp = reader.readLine();
		List<String[]> result = new ArrayList<String[]>();
		int lineNumber = 0;
		while(temp != null){
			System.out.println("reading data... [No."+(++lineNumber)+"]");
			String[] item = temp.split(" ");
			result.add(item);
			temp = reader.readLine();
		}
		reader.close();
		return result;
	}
	
	//测试数据集-3
	public static List<String[]> loadChessData() throws Exception{
		String link = "http://fimi.ua.ac.be/data/chess.dat";
		URL url = new URL(link);
		BufferedReader reader = new BufferedReader(new InputStreamReader(url.openStream()));
		String temp = reader.readLine();
		List<String[]> result = new ArrayList<String[]>();
		int lineNumber = 0;
		while(temp != null){
			System.out.println("reading data... [No."+(++lineNumber)+"]");
			String[] item = temp.split(" ");
			result.add(item);
			temp = reader.readLine();
		}
		reader.close();
		return result;
	}
}


算法原理:



作者:fufengrui 发表于2013-11-15 17:01:30 原文链接
阅读:70 评论:0 查看评论

相关 [数据挖掘 测试 apriori] 推荐:

数据挖掘--频繁集测试--Apriori算法--java实现

- - CSDN博客互联网推荐文章
Apriori算法原理:. 如果某个项集是频繁的,那么它所有的子集也是频繁的. 如果一个项集是非频繁的,那么它所有的超集也是非频繁的. * @param data 数据集. * @param minSupport 最小支持度. * @param maxLoop 最大执行次数,设NULL为获取最终结果.

数据挖掘是神马?

- - 互联网分析
1、数据挖掘需要‘神马样’的流程.  2、哥,有没有详细点的,来个给力的. 4、数据在统计意义上有哪些类型. 9、知道这些工具不知道如何在工作中用呀. 11、还有没有更人性化、智能化的展现. 12、上面这图看起来很给力,背后很复杂吧.  16、转载的留个来源 ,毕竟是我辛苦收集和想出来的,谢谢. 忘记“大数据”,从“中数据”开始.

这就是数据挖掘

- - 互联网分析
当今数据库的容量已经达到上万亿的水平(T)— 1,000,000,000,000个字节. 在这些大量数据的背后隐藏了很多具有决策意义的信息,那么怎么得到这些“知识”呢. 也就是怎样通过一颗颗的树木了解到整个森林的情况. 计 算机科学对这个问题给出的最新回答就是:数据挖掘,在“数据矿山”中找到蕴藏的“知识金块”,帮助企业减少不必要投资的同时提高资金回报.

关于数据挖掘

- - 牛国柱
以下内容来自网络,关于数据挖掘的一些最基本的知识. 数据挖掘是对一系列数据进行分析和挖掘的方法的统称,在精准营销领域,最常用的数据挖掘方法主要包括以下三类:分类、聚类、关联. 分类(Classify)属于预测性模型. 分类模型的构建需要“训练样本”,训练样本中的每一个个体的类别必须是明确的. 分类模型的特征变量一般称为“自变量”,又叫“预测变量”,类别变量称为“目标变量”.

数据挖掘与Taco Bell编程

- everfly - 译言-每日精品译文推荐
来源Data Mining and Taco Bell Programming. Programmer Ted Dziuba suggests an alternative to traditional program that he called "Taco Bell Programming." The Taco Bell chain creates multiple menu items from about eight different ingredients.

使用Weka进行数据挖掘

- - 搜索研发部官方博客
数据挖掘、机器学习这些字眼,在一些人看来,是门槛很高的东西. 诚然,如果做算法实现甚至算法优化,确实需要很多背景知识. 但事实是,绝大多数数据挖掘工程师,不需要去做算法层面的东西. 他们的精力,集中在特征提取,算法选择和参数调优上. 那么,一个可以方便地提供这些功能的工具,便是十分必要的了. 而weka,便是数据挖掘工具中的佼佼者.

数据挖掘 - 分类算法比较

- - IBM developerWorks 中国 : 文档库
随着计算能力、存储、网络的高速发展,人类积累的数据量正以指数速度增长. 对于这些数据,人们迫切希望从中提取出隐藏其中的有用信息,更需要发现更深层次的规律,对决策,商务应用提供更有效的支持. 为了满足这种需求,数据挖掘技术的得到了长足的发展,而分类在数据挖掘中是一项非常重要的任务,目前在商业上应用最多.

数据挖掘分类技术

- - CSDN博客云计算推荐文章
从分类问题的提出至今,已经衍生出了很多具体的分类技术. 下面主要简单介绍四种最常用的分类技术,不过因为原理和具体的算法实现及优化不是本书的重点,所以我们尽量用应用人员能够理解的语言来表述这些技术. 而且我们会在第4章再次给读者讲述分类算法和相关原理. 在我们学习这些算法之前必须要清楚一点,分类算法不会百分百准确.

数据挖掘之R与SQL

- Wolf - 刘思喆 @ 贝吉塔行星
今天看到老同学@JulieJulieJulieJulie 的浪漫求婚,真的很浪漫、很唯美、很感动. 正如评论说的,我们又相信爱情了. 于是,小兴奋,睡不着,爬起来补一篇文章. 最近在数据挖掘专业网站 KDnuggets 上刊出了2011年度关于数据挖掘/分析语言流行度的调查,不出意料R、SQL、Python果然排在了前三位.

数据挖掘的标准流程

- - CSDN博客推荐文章
    CRISP-DM (cross-industry standard process for data mining), 即为"跨行业数据挖掘过程标准". 此KDD过程模型于1999年欧盟机构联合起草. 通过近几年的发展,CRISP-DM 模型在各种KDD过程模型中占据领先位置,采用量达到近60%.(数据引自Cios and Kurgan于2005年合著的论文trands in data mining and knowledge discovery中 )    在1996年,当时数据挖掘市场是年轻而不成熟的,但是这个市场显示了爆炸式的增长.