关联分析-Apriori算法

1. 主函数:

package net.highersoft.service;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Map.Entry;
import java.util.TreeSet;

import org.springframework.stereotype.Service;

import net.highersoft.entity.FreqItemSeqApriori;
import net.highersoft.entity.FrequentItem;

@Service
public class Apriori {
	public static void main(String arsgs[]) {
		Integer minsupNum = 2;
		List<FrequentItem> items =new ArrayList<>();
		items.add(new FrequentItem(10,new TreeSet<String>(Arrays.asList("A","C","D"))));
		items.add(new FrequentItem(20,new TreeSet<String>(Arrays.asList("B","C","E"))));
		items.add(new FrequentItem(30,new TreeSet<String>(Arrays.asList("A","B","C","E"))));
		items.add(new FrequentItem(40,new TreeSet<String>(Arrays.asList("B","E"))));
		
		
		FreqItemSeqApriori freqItemSeq=queryFrenquence(items, minsupNum, 1);
		List<TreeSet<Object>> sourceItems=freqItemSeq.getItems();
		Map<Integer, FrequentItem> freqItems=freqItemSeq.getSeqs();
		System.out.println("找到了最大频繁项,序列:"+sourceItems+" 原始订单:"+freqItems);
	}
	

	
	/**
	 * Apriori算法，找出频繁项
	 * @param items 原始序列(购买清单list)
	 * @param minsupNum 最小支持度数
	 * @param chooseNum 本次选择的元素个数
	 * return 最大频繁数序列
	 */
	public static  FreqItemSeqApriori queryFrenquence(List<FrequentItem> items,Integer minsupNum,int chooseNum){
		Map<Object,Integer> idNumMap=new HashMap<Object,Integer>();
		for(FrequentItem item:items) {
			for(Object id:item.getIds()) {
				Integer num=idNumMap.get(id);
				num=(num==null?1:num+1);
				idNumMap.put(id, num);
			}
		}
		
		List<TreeSet<Object>> freqList=new ArrayList<TreeSet<Object>>();
		//把频繁项转为有序的字符串
		List<TreeSet<Object>> unFreqList=new ArrayList<TreeSet<Object>>();
		for(Entry<Object,Integer> entry:idNumMap.entrySet()) {
			if(entry.getValue()>=minsupNum) {
				freqList.add(new TreeSet<Object>(Arrays.asList(entry.getKey())));
			}else {
				unFreqList.add(new TreeSet<Object>(Arrays.asList(entry.getKey())));
			}
		}
		FreqItemSeqApriori   freqItemSeq=null;
		if(freqList.size()>0) {
			Map<Integer,FrequentItem> freqItems=new HashMap<Integer,FrequentItem>();
			for(TreeSet<Object> key: freqList) {
				for(FrequentItem  fi:items) {
					if(fi.getIds().containsAll(key)) {
						freqItems.put(fi.getId(), fi);
					}
				}
			}
			System.out.println("1.从"+idNumMap.size()+"个数中选"+chooseNum+"个元素，构成"+idNumMap.size()+"个组合, 剪技过滤后剩下"+freqList.size()+"侯选项, 最小支持度数为:"+minsupNum);
			freqItemSeq=chooseNextChildren(freqList,unFreqList,freqItems,chooseNum+1,minsupNum);
		}
		return freqItemSeq;
		
	}
	
	/**
	 * 
	 * @param lastFreq 侯选项
	 * @param lastUnFreq 历史不频繁项
	 * @param freqItems 频繁项的原始记录
	 * @param chooseNum 本次选择N个元素
	 * @param minsupNum 最少支持数
	 * @return
	 */
	private static FreqItemSeqApriori  chooseNextChildren(List<TreeSet<Object>> lastFreq,List<TreeSet<Object>> lastUnFreq,   Map<Integer,FrequentItem> freqItems, int chooseNum,int minsupNum) {
		
		
		
		
		List<TreeSet<Object>> combination=CombinationTwoItem.combination2Item(lastFreq, lastUnFreq, chooseNum);
		
		
		
		
		
		int totalNum=0;
		System.out.println(chooseNum+".从"+lastFreq+"侯选项中选"+chooseNum+"个元素,剪技(排除不频繁项)后剩下"+combination.size()+"侯选项, 最小支持度数为:"+minsupNum);
		if(combination.size()==0) {
			System.out.println("没有侯选项，退出");
			//没有侯选项，退出
			return new  FreqItemSeqApriori(lastFreq,freqItems);
		}
		
		
		List<TreeSet<Object>> curFreq=new ArrayList<>();
		Map<Integer,FrequentItem> curMarchSeqs=new HashMap<Integer,FrequentItem>();
		for(int i=0;i<combination.size();i++) {
			TreeSet<Object> set=combination.get(i);
			int marchedNum=0;
			Map<Integer,FrequentItem> cfreqItems=new HashMap<Integer,FrequentItem>();
			for(Entry<Integer,FrequentItem> entry:freqItems.entrySet()) {
				boolean containFlag= entry.getValue().getIds().containsAll(set);
				if(containFlag) {
					marchedNum++;
					cfreqItems.put(entry.getKey(), entry.getValue());
				}
			}
			if(marchedNum>=minsupNum) {
				totalNum++;
				curFreq.add(set);
				curMarchSeqs.putAll(cfreqItems);
			}else {
				lastUnFreq.add(set);
			}
			
		}
		
		
		System.out.println("满足支持度的组合数为:"+totalNum+",含这些组合(商品)的原始订单数:"+curMarchSeqs.size());
		
		
		return chooseNextChildren(curFreq, lastUnFreq, curMarchSeqs, chooseNum+1, minsupNum);
	}
}

2.组合工具类

package net.highersoft.entity;

import java.util.List;
import java.util.Map;
import java.util.TreeSet;

import lombok.Data;
@Data
public class FreqItemSeqApriori {
	private List<TreeSet<Object>> items;
	private Map<Integer,FrequentItem> seqs;
	public FreqItemSeqApriori(List<TreeSet<Object>> items, Map<Integer,FrequentItem> seqs) {
		super();
		this.items = items;
		this.seqs = seqs;
	}
	
}

package net.highersoft.entity;

import java.util.TreeSet;

import lombok.Data;

@Data
public class FrequentItem {
	private Integer id;
	//private String clientId;
	//数据库存的id的格式
	private String sequence;
	private TreeSet<String> ids;
	
	public FrequentItem(Integer id, TreeSet<String> ids) {
		super();
		this.id = id;
		this.ids = ids;
	}
	@Override
	public String toString() {
		return "FrequentItem [id=" + id + ", ids=" + ids + "]";
	}
	public FrequentItem() {
		super();
	}
}

相关教程图示:

算法整个流程:

剪枝过程:

输出结果:

设最小支持度数为:2
原始订单数据为:
OrderItem [id(订单主键)=10, ids(商品主键)=[65, 67, 68]]
OrderItem [id(订单主键)=20, ids(商品主键)=[66, 67, 69]]
OrderItem [id(订单主键)=30, ids(商品主键)=[65, 66, 67, 69]]
OrderItem [id(订单主键)=40, ids(商品主键)=[66, 69]]


1.从5个数中选1个元素，构成5个侯选项, 剪枝过滤后剩下4个频繁项
频繁项:[[65], [66], [67], [69]]
2.从上面4个频繁项中选2个元素,剪枝(排除上层不频繁项)后剩下6侯选项
侯选项为:[[65, 66], [65, 67], [65, 69], [66, 67], [66, 69], [67, 69]]
满足支持度的侯选项有4项,即频繁项:[[65, 67], [66, 67], [66, 69], [67, 69]]
含这些组合(商品)的原始订单数:4
3.从上面4个频繁项中选3个元素,剪枝(排除上层不频繁项)后剩下1侯选项
侯选项为:[[66, 67, 69]]
满足支持度的侯选项有1项,即频繁项:[[66, 67, 69]]
含这些组合(商品)的原始订单数:2
4.从上面1个频繁项中选4个元素,剪枝(排除上层不频繁项)后剩下0侯选项
侯选项为:[]
没有侯选项，退出
找到了最大频繁项,序列:[[66, 67, 69]]
拥有最大频繁项的原始订单:{20=OrderItem [id(订单主键)=20, ids(商品主键)=[66, 67, 69]], 30=OrderItem [id(订单主键)=30, ids(商品主键)=[65, 66, 67, 69]]}

new FrequentItem(10,new TreeSet(Arrays.asList("A","C","D"))表示订单号为10的订单，买了A、C、D三种商品。

这里得到了最长的频繁项:B、C、E。两项中的【A、C】，【B、C】是满足支持度的，但他们是关联规则么？  不一定。

这要用到另一个概念:置信度。大于等于最小置信度的才能认为是关联规则。比如，设最小置信度为80%, 那么对于BE->C 即count(BCE)/count(BE)=2/3<80%,这个BE就不能认为是关联规则。

如果存在BCE的序列的有2项，存在BE序列的有3项,那么Confidence=2/3,其它的组合同理。这就是置信度的意义。

k项频繁集生成k+1项频繁集的时侯有两种办法，一种是上面算所有组合数，这是基于一种A->B->C,那么认为A与C相关的做法。

例如: 我在当当看了一本语文书,又看了一本作文书，又看了一本数学书。如果以教材来区分是否关联，那么这三者有关联。如果以学科来区分，语文与数学就没有关联了。

所以另一种是{A,B},{B,C}不能形成{A,B,C}的频繁项。