文档章节

weka实战005:基于HashSet实现的apriori关联规则算法

brian_2017
 brian_2017
发布于 2017/01/17 09:47
字数 1013
阅读 4
收藏 0

这个一个apriori算法的演示版本,所有的代码都在一个类。仅供研究算法参考


package test;

import java.util.Collections;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;
import java.util.Vector;

//用set写的apriori算法
public class AprioriSetBasedDemo {

	class Transaction {
		/*
		 * 购物记录,用set保存多个货物名
		 */
		private HashSet<String> pnSet = new HashSet<String>();

		public Transaction() {
			pnSet.clear();
		}

		public Transaction(String[] names) {
			pnSet.clear();
			for (String s : names) {
				pnSet.add(s);
			}
		}

		public HashSet<String> getPnSet() {
			return pnSet;
		}

		public void addPname(String s) {
			pnSet.add(s);
		}

		public boolean containSubSet(HashSet<String> subSet) {
			return pnSet.containsAll(subSet);
		}

		@Override
		public String toString() {
			StringBuilder sb = new StringBuilder();
			Iterator<String> iter = pnSet.iterator();
			while (iter.hasNext()) {
				sb.append(iter.next() + ",");
			}
			return "Transaction = [" + sb.toString() + "]";
		}

	}

	class TransactionDB {
		// 记录所有的Transaction
		private Vector<Transaction> vt = new Vector<Transaction>();

		public TransactionDB() {
			vt.clear();
		}

		public int getSize() {
			return vt.size();
		}

		public void addTransaction(Transaction t) {
			vt.addElement(t);
		}

		public Transaction getTransaction(int idx) {
			return vt.elementAt(idx);
		}

	}

	public class AssoRule implements Comparable<AssoRule> {
		private String ruleContent;
		private double confidence;

		public void setRuleContent(String ruleContent) {
			this.ruleContent = ruleContent;
		}

		public void setConfidence(double confidence) {
			this.confidence = confidence;
		}

		public AssoRule(String ruleContent, double confidence) {
			this.ruleContent = ruleContent;
			this.confidence = confidence;
		}

		@Override
		public int compareTo(AssoRule o) {
			if (o.confidence > this.confidence) {
				return 1;
			} else if (o.confidence == this.confidence) {
				return 0;
			} else {
				return -1;
			}
		}

		@Override
		public String toString() {
			return ruleContent + ", confidence=" + confidence * 100 + "%";
		}

	}

	public static String getStringFromSet(HashSet<String> set) {
		StringBuilder sb = new StringBuilder();
		Iterator<String> iter = set.iterator();
		while (iter.hasNext()) {
			sb.append(iter.next() + ", ");
		}
		if (sb.length() > 2) {
			sb.delete(sb.length() - 2, sb.length() - 1);
		}
		return sb.toString();
	}

	// 计算具有最小支持度的一项频繁集 >= minSupport
	public static HashMap<String, Integer> buildMinSupportFrequenceSet(
			TransactionDB tdb, int minSupport) {
		HashMap<String, Integer> minSupportMap = new HashMap<String, Integer>();

		for (int i = 0; i < tdb.getSize(); i++) {
			Transaction t = tdb.getTransaction(i);
			Iterator<String> it = t.getPnSet().iterator();
			while (it.hasNext()) {
				String key = it.next();
				if (minSupportMap.containsKey(key)) {
					minSupportMap.put(key, minSupportMap.get(key) + 1);
				} else {
					minSupportMap.put(key, new Integer(1));
				}
			}
		}

		Iterator<String> iter = minSupportMap.keySet().iterator();
		Vector<String> toBeRemoved = new Vector<String>();
		while (iter.hasNext()) {
			String key = iter.next();
			if (minSupportMap.get(key) < minSupport) {
				toBeRemoved.add(key);
			}
		}

		for (int i = 0; i < toBeRemoved.size(); i++) {
			minSupportMap.remove(toBeRemoved.get(i));
		}

		return minSupportMap;
	}

	public void buildRules(TransactionDB tdb,
			HashMap<HashSet<String>, Integer> kItemFS, Vector<AssoRule> var,
			double ruleMinSupportPer) {

		// 如果kItemFS的成员数量不超过1不需要计算
		if (kItemFS.size() <= 1) {
			return;
		}

		// k+1项频项集
		HashMap<HashSet<String>, Integer> kNextItemFS = new HashMap<HashSet<String>, Integer>();

		// 获得第k项频项集
		@SuppressWarnings("unchecked")
		HashSet<String>[] kItemSets = new HashSet[kItemFS.size()];
		kItemFS.keySet().toArray(kItemSets);

		/*
		 * 根据k项频项集,用两重循环获得k+1项频项集 然后计算有多少个tranction包含这个k+1项频项集
		 * 然后支持比超过ruleMinSupportPer,就可以生成规则,放入规则向量
		 * 然后,将k+1项频项集及其支持度放入kNextItemFS,进入下一轮计算
		 */
		for (int i = 0; i < kItemSets.length - 1; i++) {
			HashSet<String> set_i = kItemSets[i];
			for (int j = i + 1; j < kItemSets.length; j++) {
				HashSet<String> set_j = kItemSets[j];
				// k+1 item set
				HashSet<String> kNextSet = new HashSet<String>();
				kNextSet.addAll(set_i);
				kNextSet.addAll(set_j);
				if (kNextSet.size() <= set_i.size()
						|| kNextSet.size() <= set_j.size()) {
					continue;
				}

				// 计算k+1 item set在所有transaction出现了几次
				int count = 0;
				for (int k = 0; k < tdb.getSize(); k++) {
					if (tdb.getTransaction(k).containSubSet(kNextSet)) {
						count++;
					}
				}
				if (count <= 0) {
					continue;
				}

				Integer n_i = kItemFS.get(set_i);
				double per = 1.0 * count / n_i.intValue();
				if (per >= ruleMinSupportPer) {
					kNextItemFS.put(kNextSet, new Integer(count));
					HashSet<String> tmp = new HashSet<String>();
					tmp.addAll(kNextSet);
					tmp.removeAll(set_i);
					String s1 = "{" + getStringFromSet(set_i) + "}" + "(" + n_i
							+ ")" + "==>" + getStringFromSet(tmp).toString()
							+ "(" + count + ")";
					var.addElement(new AssoRule(s1, per));
				}
			}
		}

		// 进入下一轮计算
		buildRules(tdb, kNextItemFS, var, ruleMinSupportPer);
	}

	public void test() {
		// Transaction数据集
		TransactionDB tdb = new TransactionDB();

		// 添加Transaction交易记录
		tdb.addTransaction(new Transaction(new String[] { "a", "b", "c", "d" }));
		tdb.addTransaction(new Transaction(new String[] { "a", "b" }));
		tdb.addTransaction(new Transaction(new String[] { "b", "c" }));
		tdb.addTransaction(new Transaction(new String[] { "b", "c", "d", "e" }));

		// 规则最小支持度
		double minRuleConfidence = 0.5;
		Vector<AssoRule> vr = computeAssociationRules(tdb, minRuleConfidence);
		// 输出规则
		int i = 0;
		for (AssoRule ar : vr) {
			System.out.println("rule[" + (i++) + "]: " + ar);
		}
	}

	public Vector<AssoRule> computeAssociationRules(TransactionDB tdb,
			double ruleMinSupportPer) {
		// 输出关联规则
		Vector<AssoRule> var = new Vector<AssoRule>();

		// 计算最小支持度频项
		HashMap<String, Integer> minSupportMap = buildMinSupportFrequenceSet(
				tdb, 2);

		// 计算一项频项集
		HashMap<HashSet<String>, Integer> oneItemFS = new HashMap<HashSet<String>, Integer>();
		for (String key : minSupportMap.keySet()) {
			HashSet<String> oneItemSet = new HashSet<String>();
			oneItemSet.add(key);
			oneItemFS.put(oneItemSet, minSupportMap.get(key));
		}

		// 根据一项频项集合,递归计算规则
		buildRules(tdb, oneItemFS, var, ruleMinSupportPer);
		// 将规则按照可信度排序
		Collections.sort(var);
		return var;
	}

	public static void main(String[] args) {
		AprioriSetBasedDemo asbd = new AprioriSetBasedDemo();
		asbd.test();
	}

}

运行结果如下:


rule[0]: {d }(2)==>b (2), confidence=100.0%
rule[1]: {d }(2)==>c (2), confidence=100.0%
rule[2]: {d, a }(1)==>c (1), confidence=100.0%
rule[3]: {d, a }(1)==>b (1), confidence=100.0%
rule[4]: {d, a }(1)==>b (1), confidence=100.0%
rule[5]: {d, c }(2)==>b (2), confidence=100.0%
rule[6]: {d, b, a }(1)==>c (1), confidence=100.0%
rule[7]: {d, b, a }(1)==>c (1), confidence=100.0%
rule[8]: {d, c, a }(1)==>b (1), confidence=100.0%
rule[9]: {b }(4)==>c (3), confidence=75.0%
rule[10]: {b, c }(3)==>d (2), confidence=66.66666666666666%
rule[11]: {b, c }(3)==>d (2), confidence=66.66666666666666%
rule[12]: {d }(2)==>a (1), confidence=50.0%
rule[13]: {b }(4)==>a (2), confidence=50.0%
rule[14]: {d, c }(2)==>b, a (1), confidence=50.0%
rule[15]: {d, b }(2)==>a (1), confidence=50.0%

© 著作权归作者所有

brian_2017
粉丝 3
博文 61
码字总数 145216
作品 0
私信 提问
Weka 中的算法名说明

数据输入和输出 WOW():查看Weka函数的参数。 Weka_control():设置Weka函数的参数。 read.arff():读Weka Attribute-Relation File Format (ARFF)格式的数据。 write.arff:将数据写入Weka ...

pior
2015/10/17
422
0
与数据挖掘有关或有帮助的R包和函数的集合

与数据挖掘有关或者有帮助的R包和函数的集合。 1、聚类 常用的包:fpc,cluster,pvclust,mclust 基于划分的方法:kmeans,pam,pamk,clara 基于层次的方法:hclust,pvclust,agnes,diana 基于模...

dongzhumao
2015/01/28
0
0
数据挖掘和R包(转)

下面列出了可用于数据挖掘的R包和函数的集合。其中一些不是专门为了数据挖掘而开发,但数据挖掘过程中这些包能帮我们不少忙,所以也包含进来。 1、聚类 2、分类 3、关联规则与频繁项集 4、序...

MtrS
2016/04/26
55
0
数据挖掘-关联分析 Apriori算法和FP-growth 算法

•1.关联分析概念 关联分析是从大量数据中发现项集之间有趣的关联和相关联系。 •定义: 1、事务:每一条交易称为一个事务,如上图包含5个事务。 2、项:交易的每一个物品称为一个项,例如豆...

蜘蛛侠不会飞
2018/07/19
0
0
数据挖掘十大经典算法概述、优势及使用场景

国际权威的学术组织theIEEEInternationalConferenceonDataMining(ICDM)2006年12月评选出了数据挖掘领域的十大经典算法:C4.5,k-Means,SVM,Apriori,EM,PageRank,AdaBoost,kNN,NaiveBayes,andC......

加米谷
2018/06/14
0
0

没有更多内容

加载失败,请刷新页面

加载更多

只需一步,在Spring Boot中统一Restful API返回值格式与统一处理异常

统一返回值 在前后端分离大行其道的今天,有一个统一的返回值格式不仅能使我们的接口看起来更漂亮,而且还可以使前端可以统一处理很多东西,避免很多问题的产生。 比较通用的返回值格式如下:...

晓月寒丶
昨天
59
0
区块链应用到供应链上的好处和实际案例

区块链可以解决供应链中的很多问题,例如记录以及追踪产品。那么使用区块链应用到各产品供应链上到底有什么好处?猎头悬赏平台解优人才网小编给大家做个简单的分享: 使用区块链的最突出的优...

猎头悬赏平台
昨天
28
0
全世界到底有多少软件开发人员?

埃文斯数据公司(Evans Data Corporation) 2019 最新的统计数据(原文)显示,2018 年全球共有 2300 万软件开发人员,预计到 2019 年底这个数字将达到 2640万,到 2023 年达到 2770万。 而来自...

红薯
昨天
65
0
Go 语言基础—— 通道(channel)

通过通信来共享内存(Java是通过共享内存来通信的) 定义 func service() string {time.Sleep(time.Millisecond * 50)return "Done"}func AsyncService() chan string {retCh := mak......

刘一草
昨天
58
0
Apache Flink 零基础入门(一):基础概念解析

Apache Flink 的定义、架构及原理 Apache Flink 是一个分布式大数据处理引擎,可对有限数据流和无限数据流进行有状态或无状态的计算,能够部署在各种集群环境,对各种规模大小的数据进行快速...

Vincent-Duan
昨天
60
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部