Java实现Apriori算法
发布时间
阅读量：
阅读量
简介：
Apriori算法是第一个关联规则挖掘算法，也是最经典的算法。它利用逐层搜索的迭代方法找出数据库中项集的关系，以形成规则，其过程由连接（类矩阵运算）与剪枝（去掉那些没必要的中间结果）组成。该算法中项集的概念即为项的集合。包含K个项的集合为k项集。项集出现的频率是包含项集的事务数，称为项集的频率。如果某项集满足最小支持度，则称它为频繁项集。
基本思想：
首先扫描数据库中所需要进行分析的数据，在设置完支持度以及置信度以后，在最小支持度的支持下产生频繁项，即统计所有项目集中包含一个或一个以上的元素频数，找出大于或者等于设置的支持度的项目集。其次就是频繁项的自连接。再者是如果对频繁项自连接以后的项的子集如果不是频繁项的话，则进行剪枝处理。接着对频繁项处理后产生候选项。最后循环
调用产生频繁项集。
支持度：
支持度就是几个关联的数据在数据集中出现的次数占总数据集的比重。或者说几个数据关联出现的概率。
置信度：
置信度体现了一个数据出现后，另一个数据出现的概率，或者说数据的条件概率。
举例：
代码实现：
package com.ucm.utils;
import java.util.*;
public class Apriori {
private final static int SUPPORT = 2; // 支持度阈值
private final static double CONFIDENCE = 0.8; // 置信度阈值
private final static String ITEM_SPLIT="、"; // 项之间的分隔符
private final static String CON=" → "; // 项之间的分隔符
private List<String> transList ; //所有交易
public Apriori(List<String> transList) {
this.transList = transList;
}
/** *
* @return 交易的所有频繁项集
*/
public Map<List<String>,Integer> getFC(){
Map<List<String>,Integer> frequentCollectionMap = new HashMap<>();//所有的频繁集
frequentCollectionMap.putAll(getItem1FC());//合并频繁1项集
Map<List<String>,Integer> itemkFcMap = getItem1FC(),candidateCollection;
while (itemkFcMap!=null && itemkFcMap.size()!=0){
candidateCollection = getCandidateCollection(itemkFcMap);//获得候选集
//对候选集项进行累加计数
for (List<String> candidate : candidateCollection.keySet()){
for (String trans : transList){
boolean flag = true;// 用来判断交易中是否出现该候选项，如果出现，计数加1
for (String candidateItem : candidate){
if (trans.indexOf(candidateItem)==-1){
flag = false;
break;
}
}
if (flag){
candidateCollection.put(candidate,candidateCollection.get(candidate)+1);
}
}
}
itemkFcMap.clear();
//从候选集中找到符合支持度的频繁集项
for (List<String> candidate : candidateCollection.keySet()){
Integer fc = candidateCollection.get(candidate);
if (fc>=SUPPORT){
itemkFcMap.put(candidate,fc);
}
}
//合并所有频繁集
frequentCollectionMap.putAll(itemkFcMap);
}
return frequentCollectionMap;
}
/** * 关联规则
* @param frequentCollectionMap 频繁集
* @return 关联规则
*/
public Map<String,Double> getRelationRules(Map<List<String>,Integer> frequentCollectionMap){
Map<String,Double> relationRules=new HashMap<>();
for (List<String> itmes : frequentCollectionMap.keySet()){
if (itmes.size()>1){
double countAll = frequentCollectionMap.get(itmes);
List<List<String>> result = getSubsets(itmes);//获得itmes的所有非空子集
for (List<String> itemList : result){
if (itemList.size() < itmes.size()){//只处理真子集
StringBuilder reasonStr = new StringBuilder();//前置
StringBuilder resultStr = new StringBuilder();//结果
for (String item : itemList) reasonStr.append(ITEM_SPLIT).append(item);
for (String item : itmes) if (!itemList.contains(item)) resultStr.append(ITEM_SPLIT).append(item);
double countReason = frequentCollectionMap.get(itemList);
double itemConfidence = countAll / countReason;//计算置信度
if (itemConfidence >= CONFIDENCE){
String rule = reasonStr.append(CON).append(resultStr.substring(1)).substring(1);
relationRules.put(rule,itemConfidence);
}
}
}
}
}
return relationRules;
}
/** *对于给定的频繁K项集，获得他的K+1项候选集
* @param itemkFcMap 频繁K项集
* @return K+1项候选集
*/
private Map<List<String>,Integer> getCandidateCollection(Map<List<String>,Integer> itemkFcMap){
Map<List<String>,Integer> candidateCollection = new HashMap<>();
Set<List<String>> itemkSet1 = itemkFcMap.keySet();
Set<List<String>> itemkSet2 = itemkFcMap.keySet();
//连接
for (List<String> itemk1 : itemkSet1){
for (List<String> itemk2 : itemkSet2){
if (!itemk1.equals(itemk2)){
for (String item : itemk2){
if (itemk1.contains(item)) continue;
List<String> temp = new ArrayList<>(itemk1);
temp.add(item);
temp.sort(Comparator.naturalOrder());
candidateCollection.put(temp,0);
}
}
}
}
return candidateCollection;
}
/** * 获取频繁1项集
* @return map<key,value> key-items value-frequency
*/
private Map<List<String>,Integer> getItem1FC(){
Map<List<String>,Integer> sItem1FCMap = new HashMap<>();//statistics frequency of each item
Map<List<String>,Integer> rItem1FCMap = new HashMap<>();//频繁1项集
for (String trans : transList){
String[] items = trans.split(ITEM_SPLIT);
for (String item : items){
List<String> itemList = new ArrayList<>();
itemList.add(item);
sItem1FCMap.put(itemList,sItem1FCMap.getOrDefault(itemList,0)+1);
}
}
for (List itemList : sItem1FCMap.keySet()){
Integer fc = sItem1FCMap.get(itemList);
if (fc>=SUPPORT) rItem1FCMap.put(itemList,fc);
}
return rItem1FCMap;
}
/** * 构造子集
* @param sourceSet
* @return sourceSet的所有非空子集
*/
private List<List<String>> getSubsets(List<String> sourceSet){
List<List<String>> result = new ArrayList<>();
result.add(new ArrayList<>());
for(int i = 0;i<sourceSet.size();i++){
int size = result.size();
for (int j = 0;j<size;j++){
List<String> temp = new ArrayList<>(result.get(j));
temp.add(sourceSet.get(i));
result.add(temp);
}
}
return result.subList(1,result.size());//去掉空集
}
}测试代码：
import com.ucm.utils.Apriori;
import java.util.Arrays;
import java.util.List;
import java.util.Map;
public class TestApriori {
public static void main(String[] args) {
Apriori apriori = new Apriori(Arrays.asList("A、C、D","B、C、E","A、B、C、E","B、E"));
Map<List<String>,Integer> frequentCollectionMap = apriori.getFC();
System.out.println("-------------频繁集"+"----------------");
for(List<String> list : frequentCollectionMap.keySet()) System.out.println(list+ "\t"+ frequentCollectionMap.get(list));
Map<String,Double> relationRulesMap = apriori.getRelationRules(frequentCollectionMap);
System.out.println("-----------关联规则"+"----------------");
for (String s : relationRulesMap.keySet()) System.out.println(s+"\t"+relationRulesMap.get(s));
}
}测试结果：
全部评论 (0)
还没有任何评论哟~