Apriori算法

不同语言的实现

【CSDN】Java实现Apriori算法

【CSDN】Python实现Apriori算法

【CSDN】C实现Apriori算法

感谢这些作者

简介

Apriori算法 是第一个关联规则挖掘算法，也是最经典的算法。它利用逐层搜索的迭代方法找出数据库中项集的关系，以形成规则，其过程由连接（类矩阵运算）与剪枝（去掉那些没必要的中间结果）组成。该算法中项集的概念即为项的集合。包含K个项的集合为k项集。项集出现的频率是包含项集的事务数，称为项集的频率。如果某项集满足最小支持度，则称它为频繁项集。

基本思想

首先扫描数据库中所需要进行分析的数据，在设置完支持度以及置信度以后，在最小支持度的支持下产生频繁项，即统计所有项目集中包含一个或一个以上的元素频数，找出大于或者等于设置的支持度的项目集。其次就是频繁项的自连接。再者是如果对频繁项自连接以后的项的子集如果不是频繁项的话，则进行剪枝处理。接着对频繁项处理后产生候选项。最后循环
调用产生频繁项集。

名词解释

支持度

支持度就是几个关联的数据在数据集中出现的次数占总数据集的比重。或者说几个数据关联出现的概率。

置信度

置信度体现了一个数据出现后，另一个数据出现的概率，或者说数据的条件概率。

最小支持度

用户或专家 定义的衡量支持度的一个阈值，表示项目集在统计意义上的最低重要性；

最小置信度

用户或专家 定义的衡量置信度的一个阈值，表示关联规则的最低可靠性。

同时满足最小支持度阈值和最小置信度阈值的规则称作强规则。

强规则

同时满足最小支持度阈值和最小置信度阈值的规则

项集

• 项集是项的集合。包含 k 个项的项集称为 k 项集，如集合 {牛奶，麦片，糖}是一个3项集。

• 项集的出现频率是所有包含项集的事务计数，又称作绝对支持度或支持度计数。如果项集 I 的相对支持度满足预定义的最小支持度阈值，则 I 是频繁项集。频繁k项集通常记作Lk。

代码

感觉以后是有可能再用上的，所以我直接将这个算法写成了工具类(第一次造轮子hhhh)

Apriori

我感觉我的注释已经写得很详细了，不做赘述直接看代码吧，有问题可以评论或联系我。

唯二比较生僻的方法

【菜鸟教程 (runoob.com)】 HashMap getOrDefault() 方法 【CSDN】Comparator.naturalOrder | 自然排序_猫巳的博客-CSDN博客

import java.io.*;
import java.util.*;

//author:rygdsddssd
//date:2023.5
public class Apriori {

    //这样做是为了可调阈值，以及让这次作业直接变成我的一个轮子
    int SUPPORT = 2; // 支持度阈值
    double CONFIDENCE = 0.8; // 置信度阈值
    String ITEM_SPLIT = ","; // 项的分隔符
    String RULE_SPLIT = "->"; // 项的分隔符

    //频繁集：frequentCollectionMap ---> list(k项集)-int(出现次数)
    //注意这里List是key,Integer是value哦
    /**
     * 所有的频繁集
     */
    private Map<List<String>,Integer> frequentCollectionMap = new HashMap<>();
    /**
     * 存放处理完的原始数据
     */
    public List<String[]> Data;
    /**
     * 1项集
     */
    private Map<List<String>,Integer> F1C;
    /**
     * 候选集
     */
    private Map<List<String>,Integer> candidateCollection= new HashMap<>();
    /**
     * 关联规则
     */
    private Map<String,Double> relationRules;
    //构造方法
    public Apriori() {
    }
    public Apriori(int SUPPORT, double CONFIDENCE, String ITEM_SPLIT,String RULE_SPLIT) {
        this.SUPPORT = SUPPORT;
        this.CONFIDENCE = CONFIDENCE;
        this.ITEM_SPLIT = ITEM_SPLIT;
        this.RULE_SPLIT = RULE_SPLIT;
    }

    @Override
    public String toString() {
        return "Apriori{" +
                "SUPPORT=" + SUPPORT +
                ", CONFIDENCE=" + CONFIDENCE +
                ", ITEM_SPLIT=" + ITEM_SPLIT +
                '}';
    }

    /**
     * 读取数据
     * @param fileName
     * @return 剔除无效数据的Data
     */
    public  List<String[]> Read(String fileName,int index)
    {

        System.out.println("===========================================");
        System.out.println("读取数据");
        Data = new ArrayList<>();
        //在类里加了一个private的Data，只要读取一次就到Data里了
//        //读取文件放入cells中
//        List<String[]> cells = new ArrayList<>();

        // 创建 reader
        try {

            File file = new File(fileName);
            FileInputStream fis = null;
            fis = new FileInputStream(file);
            InputStreamReader isr = new InputStreamReader(fis,"GBK");
            BufferedReader br = new BufferedReader(isr);


            // 按行读取
            String line;
            line = br.readLine();

            if(line!=null){
                System.out.println(line);
            }

            //数据处理
            //把读取的不规范数据处理成模范数据modData
            while ((line = br.readLine()) != null) {
                // 分割                // CSV文件的分隔符: ITEM_SPLIT

                String[] columns = line.split(ITEM_SPLIT);// CSV文件的分隔符: ITEM_SPLIT
                String[] modData;
                if(index!=0){
                    modData = new String[columns.length-index];
                    for (int i = 0; i < modData.length; i++) {
                        modData[i]=columns[i+1];
                    }
                }else {
                    modData = columns;
                }
                    /*
                    //这里不能直接判断 columns[2] == "yes" 哦
                    if(modData[1].equals("yes")){
                        modData[1] = "true";
                    }else{
                        modData[1] = "false";
                    }
                    */

                Data.add(modData);
            }
            System.out.println("读取完毕");
            System.out.println("===========================================");
            br.close();
        } catch (IOException ex) {
            ex.printStackTrace();
        }
        return Data;
    }

    /**
     *获取频繁集
     * @return 所有1-k项频繁集
     */
    public Map<List<String>,Integer> getFrequentCollectionMap(){
        System.out.println("生成频繁集ing...");
        //frequentCollectionMap需要合并F1C以及各个FkC
        Map<List<String>,Integer> F1C = getFrequent1ItemCollections();
        frequentCollectionMap.putAll(F1C);

        Map<List<String>,Integer> FkC = F1C;
        //已经获取过1项,-1
        for (int i = 0; i < Data.get(0).length - 1; i++) {

            //获取k+1项候选频繁集
            getFrequentMoreOneItemCandidateCollections(FkC);
            FkC.clear();
            //处理候选集

            //计数

            //对于每一个候选项,都要查找一遍Data计数
            for (List<String> cC : candidateCollection.keySet()) {
                //对于每条data，必须包含所有候选项的元素才能计数+1
                for (String[] dataItem : Data) {

                    //每个候选项中的元素都要被包含于dataItem
                    boolean flag1 = true;//true->候选项是dataItem的子集

                    for (String s1 : cC) {
                        boolean flag2 = false;//true->候选项元素是dataItem的子集
                        //只要有一个相等，说明当前候选项元素是dataItem的子集
                        for (String s2 : dataItem) {
                            if(s2.equals(s1)){
                                flag2 = true;
                            }
                        }
                        //只要有一个候选项元素不是子集，那这个候选项不是子集
                        if(flag2 == false){
                            flag1 = false;
                        }
                    }
                    if(flag1){
                        candidateCollection.put(cC,candidateCollection.get(cC)+1);
                    }
                }
            }

            //筛选

            for (List<String> stringList : candidateCollection.keySet()) {
                int fc = candidateCollection.get(stringList);
                if(fc>=SUPPORT){
                    FkC.put(stringList,fc);
                }
            }
            frequentCollectionMap.putAll(FkC);
        }

        //最后return所有的频繁集
        return frequentCollectionMap;
    }


    /**
     * 获取频繁1项集
     * @return F1C
     */
    public Map<List<String>,Integer> getFrequent1ItemCollections(){
        Map<List<String>,Integer> tempF1C = new HashMap<>();
        F1C = new HashMap<>();
        //获取1项集
        //遍历Data
        for (int i = 0; i < Data.size(); i++) {
        String[] row = Data.get(i);
            for (int j = 0; j < row.length; j++) {
                    List<String> tempL = new ArrayList<>();
                    tempL.add(row[j]);
                    //如果row[j]不存在，默认设0，然后这里统计+1
                //自行搜索getOrDefault方法
                    tempF1C.put(tempL, tempF1C.getOrDefault(tempL,0)+1);
//                    F1C.put(tempL, F1C.get(row[j] + 1));
            }
        }
        //此时全部的1项集已经全部完成，接下来要按支持度阈值筛选
        for (List<String> stringList : tempF1C.keySet()) {
            int fc = tempF1C.get(stringList);
            if(fc>=SUPPORT){
                F1C.put(stringList,fc);
            }
        }
        return F1C;
    }

    //这里重构了一下，刚才在犹豫要不要把获取频繁1项和k项写成private
    //想了想觉得毕竟这个类的命名是Apriori算法，那么这个即使是其他问题，也可能使用这个算法来获取频繁1项k项
    //所以逻辑上来说这个方法是应该开放的
    //然后就顺利成章的在类里添加了private F1C

    /**
     * 传入Data获取频繁1项集
     * @param Data 不能有多余数据
     * @return 频繁1项集
     */
    public Map<List<String>,Integer> getFrequent1ItemCollections(List<String[]> Data){
        Map<List<String>,Integer> tempF1C = new HashMap<>();
        Map<List<String>,Integer> F1C = new HashMap<>();
        //获取1项集
        //遍历Data
        for (int i = 0; i < Data.size(); i++) {
            String[] row = Data.get(i);
            //这里修改了哦，从0开始，也就意味着如果是外部数据要调用这个方法，Data里不能有多余数据
            for (int j = 0; j < row.length; j++) {
                List<String> tempL = new ArrayList<>();
                tempL.add(row[j]);
                //如果row[j]不存在，默认设0，然后这里统计+1
                //自行搜索getOrDefault方法
                tempF1C.put(tempL, tempF1C.getOrDefault(tempL,0)+1);
//                    F1C.put(tempL, F1C.get(row[j] + 1));
            }
        }
        //此时全部的1项集已经全部完成，接下来要按支持度阈值筛选
        for (List<String> stringList : tempF1C.keySet()) {
            int fc = tempF1C.get(stringList);
            if(fc>=SUPPORT){
                F1C.put(stringList,fc);
            }
        }
        return F1C;
    }

    //为了安全，应该是private
    //又想了一下，如果私有，没有必要return
    //感觉不行，这个候选集实际上类似于一个缓存数据，没有必要创建私有成员变量，既然写了return，那么这个方法实际上就相当于把获取候选集的步骤封装了起来方便外部调用，那么他按理来说应该是一个public的
    //烦,就这样吧
    
    /**
     *有频繁k项集，获取频繁k+1项候选集
     * @param FkC 频繁k项集
     * @return k+1项候选集
     */
    public Map<List<String>,Integer> getFrequentMoreOneItemCandidateCollections(Map<List<String>,Integer> FkC){
        candidateCollection.clear();

        //st1与st2都是k项，两个循环，链接成k+1项放入候选集
        //因为是直接从k项集中找的元素链接，所以也不需要再进行”剪枝“步了
        Set<List<String>> st1 = FkC.keySet();
        Set<List<String>> st2 = FkC.keySet();

        //切k项集
        for (List<String> s1 : st1) {
            for (List<String> s2 : st2) {
                //切k项
                for (String s : s2) {
                    //k项中查项
                    if(!s1.contains(s)){
                        List<String> tempL = new ArrayList<>(s1);
                        tempL.add(s);
                        //排序
                        tempL.sort(Comparator.naturalOrder());
                        candidateCollection.put(tempL,0);
                    }
                }
            }
        }

        return candidateCollection;
    }

//    public Map<List<String>,Double> getRelationRules(Map<List<String>,Integer> frequentCollectionMap){
//
//        Map<List<String>,Double> relationRule = new HashMap<>();
//        Map<List<String>,Integer> maxItemsFC = new HashMap<>();
//
//        //最大k项频繁集
//        for (List<String> fc : frequentCollectionMap.keySet()) {
//            if(fc.size()==Data.size()){
//                maxItemsFC.put(fc,frequentCollectionMap.get(fc));
//            }
//        }
//
//
//        return relationRule;
//    }

    /**
     * 根据传入频繁集获得规则
     * @param frequentCollectionMap 全部频繁项
     * @return 关联规则
     */
    public Map<String,Double> getRelationRules(Map<List<String>,Integer> frequentCollectionMap){
        System.out.println("生成规则ing...");
        //将频繁项的子集相互链接，计算置信度，筛选
        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(RULE_SPLIT).append(resultStr.substring(1)).substring(1);
                            relationRules.put(rule,itemConfidence);
                        }
                    }
                }

            }
        }
        return relationRules;
    }


    /**
     * 打印所有频繁项
     */
    public void showFC(){

        System.out.println("===========================================");
        System.out.println("所有频繁项");

        if(frequentCollectionMap == null){
            System.out.println("未创建！！！");
            return;
        }
        if(frequentCollectionMap.isEmpty()){
            System.out.println("当前为空集！！！");
            return;
        }

        for (List<String> strings : frequentCollectionMap.keySet()) {
            System.out.println(strings +":"+ frequentCollectionMap.get(strings));
        }
    }

    /**
     * 打印规则
     */
    public void showRule(){

        System.out.println("===========================================");
        System.out.println("关联规则");

        if(relationRules == null){
            System.out.println("未创建！！！");
            return;
        }
        if(relationRules.isEmpty()){
            System.out.println("当前为空集！！！");
            return;
        }
        for (String strings : relationRules.keySet()) {
            System.out.println(strings +":"+ relationRules.get(strings));
        }
    }

    /**
     * 打印1项集
     */
    public void showF1C(){

        System.out.println("===========================================");
        System.out.println("单项集");

        if(relationRules == null || relationRules.isEmpty()){
            getFrequent1ItemCollections();
        }

        for (List<String> strings : F1C.keySet()) {
            System.out.println(strings +":"+ F1C.get(strings));
        }
    }

    /**
     * 打印数据
     */
    public void showData(){
        System.out.println("===========================================");
        System.out.println("Data");

        if(Data == null || Data.isEmpty()){
            getFrequent1ItemCollections();
        }

        for (String[] strings : Data) {
            System.out.println("Row:" + Arrays.toString(strings));
        }
    }

    /**
     * 构造子集
     * @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());//去掉空集
    }
}

example

我的这个例子文件就直接是中医证型关联规则.java

public class 中医证型关联规则 {
    public static void main(String[] args) {
        Apriori apriori = new Apriori(2,0.8,",","->");
        apriori.Read("src/中医证型关联规则.csv",0);
        apriori.getRelationRules(apriori.getFrequentCollectionMap());
        apriori.showRule();
    }
}

Data

原始数据图 931*7

(第一行是表头，格式不同则请自行重写Read方法)

所有元素也必须是各异的，否则请自行替换。

作业数据中出现了这样的情况

可以看到周末和促销列都是(yes/no),不进行处理显然会出现问题，我的处理方式就是直接在重写方法里读取数据时将某一列替换成不同字符了(见Apriori类103-110行)

理想的处理应该自动将每一列的数据读取种类自行分配特征值，不过我懒得写了。

运行结果

数据量有点大，需要等一会儿的