说明:參考Mahout FP算法相关相关源代码。
算法project能够在FP关联规则计算置信度下载:(仅仅是单机版的实现,并没有MapReduce的代码)
使用FP关联规则算法计算置信度基于以下的思路:
1. 首先使用原始的FP树关联规则挖掘出全部的频繁项集及其支持度;这里须要注意,这里是输出全部的频繁项集,并没有把频繁项集合并,所以须要改动FP树的相关代码,在某些步骤把全部的频繁项集输出;(ps:參考Mahout的FP树单机版的实现,进行了改动,暂不确定是否已经输出了全部频繁项集)
为举例简单,能够以以下的数据为例(原始事务集):
牛奶,鸡蛋,面包,薯片
鸡蛋,爆米花,薯片,啤酒
鸡蛋,面包,薯片
牛奶,鸡蛋,面包,爆米花,薯片,啤酒
牛奶,面包,啤酒
鸡蛋,面包,啤酒
牛奶,面包,薯片
牛奶,鸡蛋,面包,黄油,薯片
牛奶,鸡蛋,黄油,薯片
2. 得到全部的频繁项集例如以下:
0,2,3=4
2,4=3
0,1,2,3=3
3=6
2=7
1,2=5
1=7
0=7
0,3=5
0,2=6
0,1=5
4=4
0,1,2=4
0,1,3=4
1,3=5
1,4=3
上面的频繁项集中,等号后面的是支持度;每条频繁项集显示的是经过编码的,编码的规则例如以下:{薯片=0, 牛奶=3, 鸡蛋=2, 面包=1, 啤酒=4}。同一时候。能够看到上面的频繁项集中的编码是依照顺序排列的(从小到大);
计算每条频繁项集的置信度(仅仅计算2项和2项以上的频繁项集):
1) 对于频繁n项集,查找其前向(前向定义为前面n-1项集。比方频繁项集:0,2,3那么其前向为0,2)的支持度。假设频繁n项集存在。那么其前向(频繁n-1项集)必定存在(假设频繁项集是全部的频繁项集的话,这个规则一定是成立的);
2)使用n项集的支持度除以n项集的前向的支持度就可以得到n项集的置信度。
3. 依照2中的计算方法是能够计算全部的频繁项集的置信度的。可是这里有个问题:仅仅能计算比方0,2,3这个频繁项集的置信度,而不能计算0,3,2这个频繁项集的置信度(FP算法中频繁项集0,2,3和0,3,2是一样的频繁项集。可是计算置信度的时候就会不一样);
4. 针对3的问题,能够给出以下的解决方式。
// generateTopKFrequentPatterns(new TransactionIterator<A>(
// transactionStream, attributeIdMapping), attributeFrequency,
// minSupport, k, reverseMapping.size(), returnFeatures,
// new TopKPatternsOutputConverter<A>(output, reverseMapping),
// updater);
改动为以下的代码:
generateTopKFrequentPatterns(new TransactionIterator<A>(
transactionStream, attributeIdMapping), attributeFrequency,
minSupport, k, reverseMapping.size(), returnFeatures,reverseMapping
);
这种改动在FPTree里面有非常多,就不一一赘述,详情參考本文源代码下载的project;
addFrequentPatternMaxHeap(frequentPatterns);
这种方法的详细代码为:
/**
* 存储全部频繁项集
* @param patternsOut
*/
private static void addFrequentPatternMaxHeap(FrequentPatternMaxHeap patternsOut){
String[] pStr=null; // 这里的Pattern有问题。临时使用字符串解析
for(Pattern p:patternsOut.getHeap()){ pStr=p.toString().split("-");
if(pStr.length<=0){
continue;
}
// 对字符串进行下处理,这样能够降低存储
pStr[0]=pStr[0].replaceAll(" ", "");
pStr[0]=pStr[0].substring(1,pStr[0].length()-1);
if(patterns.containsKey(pStr[0])){
if(patterns.get(pStr[0])<p.support()){// 仅仅取支持度最大的
patterns.remove(pStr[0]);
patterns.put(pStr[0], p.support());
}
}else{
patterns.put(pStr[0], p.support());
}
} }
这里假定这种操作能够得到全部的频繁项集。而且存入到了patterns静态map变量中。
/**
* 依据排序频繁相机支持度 生成多频繁项集支持度
*/
public void generateFatPatterns(){
int[] patternInts=null;
for(String p :patterns.keySet()){
patternInts = getIntsFromPattern(p);
if(patternInts.length==1){// 针对频繁一项集
fatPatterns.put(String.valueOf(patternInts[0]), patterns.get(p));
}else{
putInts2FatPatterns(patternInts,patterns.get(p));
} }
} /**
* 把数组中的每一项作为后向进行输出,加入到fatpatterns中
* @param patternInts
* @param support
*/
private void putInts2FatPatterns(int[] patternInts, Long support) {
// TODO Auto-generated method stub
String patternStr =Ints2Str(patternInts);
fatPatterns.put(patternStr, support);// 处理最后一个后向
for(int i=0;i<patternInts.length-1;i++){// 最后一个后向在前面已经处理
// 不能使用同一个数组
patternStr=Ints2Str(swap(patternInts,i,patternInts.length-1));
fatPatterns.put(patternStr, support);
} }
4. 针对上面输出的频发项集进行置信度的计算:
public void savePatterns(String output,Map<String,Long> map){
// 清空patternsMap
patternsMap.clear(); String preItem=null;
for(String p:map.keySet()){
// 单项没有前向。不用找
if(p.lastIndexOf(",")==-1){
continue;
}
// 找出前向
preItem = p.substring(0, p.lastIndexOf(","));
if(map.containsKey(preItem)){
// patterns.get(p) 支持度,patterns.get(preItem)前向支持度
patternsMap.put(p, map.get(p)*1.0/map.get(preItem));
}
}
FPTreeDriver.createFile(patternsMap, output);
}
因为把频繁项集和支持度都放入了Map中,所以这样计算比較简单。
这里能够使用MapReduce的思路来实现。
1. 把文件A复制一份得到文件B;
对A的处理为直接输出频繁项集,输出的key为频繁项集,value是支持度和A的标签;对B的处理为输出全部的频繁项集中项大于1的频繁项集,其输出的key是频繁项集的前向(定义为频繁项集前面n-1个项)。value是频繁项集的后向(后向定义为频繁项集的最后一项)和支持度和标签。
分享,成长,快乐
转载请注明blog地址:http://blog.csdn.net/fansy1990