APRIORI算法

Java

数据挖掘

Publish Date: 2023-01-01

Update Date: 2023-01-05

Word Count: 1.9k

Read Times: 8 Min

Read Count:

1、什么是APRIORI算法

apriori算法是一种关联规则算法，其目的是找出频繁项集。

2、APRIOIRI算法的基本思想

首先找出所有的频集，这些项集出现的频繁性至少和预定义的最小支持度一样。然后由频集产生强关联规则，这些规则必须满足最小支持度和最小可信度。然后使用第1步找到的频集产生期望的规则，产生只包含集合的项的所有规则，其中每一条规则的右部只有一项，这里采用的是中规则的定义。一旦这些规则被生成，那么只有那些大于用户给定的最小可信度的规则才被留下来。为了生成所有频集，采用递归的方法。（—-百度百科）

3、算法流程

准确的来说，应该是求关联规则的算法流程，APRIORI算法只不过是求频繁项集的罢了。这里给出APRIORI算法和根据频繁项集求关联规则的算法流程。

3.1 APRIORI算法流程

求出频繁1项集
根据频繁项集找候选项集
根据候选项集重新寻找频繁项集

其中2，3步一直寻找下去，一直把所有的频繁项集找完。

怎么说呢，APRIORI算法其实就这两步，但是由于要求关联规则，所以还需要最后一步–>根据求得的频繁项集挖掘出关联规则。

3.2 根据频繁项集求得关联规则

拿到一个频繁项集
找出这个频繁项集的所有真子集
按照“ 真子集–> 频繁项集除真子集外的集合：真子集出现次数/频繁项集出现次数”的格式一一列出。

流程图如下：

4、算法实现

4.1 主要数据结构：

数据结构	说明
List<List> dataSet	用于存放数据集
BidiMap<String, Integer> strToSumMap	名词、数字间相互转换的索引表
Map<List, Integer> frequentCountMap	记录频繁项集以及它的次数

BidiMap 是Apache Commons Collections 4.4下的工具类的一结构，可以用它来构造“值—>键”的map类型。注意如果有相同的值存在BidiMap会覆盖掉已有的key。

4.2 函数介绍：

函数名	位置	返回类型	作用
loadData(String fileName)	AprioriUtil.java	List	从数据集中加载数据
makeIndex(List<List> array)	AprioriUtil.java	BidiMap<String, Integer>	将原始数据集中的数据建立一个汉字（英文）-数值的索引表
strToSum(List<List> array, BidiMap<String, Integer> index)	AprioriUtil.java	List<List>	将文字数据集转变为数字数据集
sumToStr(List<List> array, BidiMap<String, Integer> index)	AprioriUtil.java	List<List>	将数字数据集变回文字
setToList(Map<List, Integer> map)	AprioriUtil.java	List<List>	从map集合中得到所有的键集合
getFrequentCount(List<List> dataSet, List<List> allFrequent)	AprioriUtil.java	Map<List, Integer>	得到频繁项集的次数
splitList(List frequent)	AprioriUtil.java	Map<List, List>	将一个频繁项集切割组合成多个List数组（找真子集）
oneFrequentSet(List<List> dataSet)	Apriori.java	Map<List, Integer>	生成频繁1项集,并统计其出现的次数
getSupportItemsSet(Map<List, Integer> result, int count)	Apriori.java	Map<List, Integer>	得到频繁项集
lkToCk(List<List> dataSet, int k)	Apriori.java	List<List>	得到Ck候选集
ckToLk(List<List> dataSet, List<List> frequent)	Apriori.java	Map<List, Integer>	频繁项集预处理（统计每个候选集的次数）

4.3 关键代码：

4.3.1 lkToCk(List<List> dataSet, int k)：

public List<List<Integer>> lkToCk(List<List<Integer>> dataSet, int k) {
        List<List<Integer>> list = new ArrayList<>();
        List<Integer> list2 = null;
        List<Integer> temp = null;

        // 1.遍历频繁K-1项目集
        for (int i = 0; i < dataSet.size()-1; i++) {
            for (int j = i+1; j < dataSet.size(); j++) {
                // 2.将两个数组合并为一个，并去重
                temp = new ArrayList<>(dataSet.get(i));
                temp.addAll(dataSet.get(j));
                Collections.sort(temp);
                temp = new ArrayList<Integer>(new LinkedHashSet<>(temp));

                // 3.判断读取的候选集的元素个数，如果大于k，则去掉,等于k+1则保存起来
                if (temp.size() == k+1 && !list.contains(temp)) {
                    list.add(temp);
                }
            }
        }

        return list;
    }

4.3.2 splitList(List frequent):

public static Map<List<Integer>, List<Integer>> splitList(List<Integer> frequent) {
        Map<List<Integer>, List<Integer>> map = new HashMap<List<Integer>, List<Integer>>();
        // 全部的子集
        List<List<Integer>> allTrueSubset = new ArrayList<List<Integer>>();
        // 1.求出频繁项集的所有真子集
        //子集的数量
        int n = 1 << frequent.size();
        List<Integer> temp = null;

        for(int i = 0; i < n; i ++)
        {
            temp = new ArrayList<>();
            int j = i;
            int index = frequent.size() - 1;
            //循环前检测j是否是000
            while(j > 0)
            {
                if((j&1) == 1)
                {
                    temp.add(frequent.get(index));
                }
                j = j >> 1;
                index --;
            }

            temp.sort(Comparator.comparing(Integer::intValue));
            if (temp.size() != 0 && temp.size() != frequent.size()) {
                allTrueSubset.add(temp);
            }
        }

        // 2.遍历真子集，并在频繁项集中去除
        List<Integer> allOtherSubset = null;
        for (List<Integer> list : allTrueSubset) {
            allOtherSubset = new ArrayList<Integer>();
            HashSet h1 = new HashSet(frequent);
            HashSet h2 = new HashSet(list);
            h1.removeAll(h2);
            allOtherSubset.addAll(h1);

            map.put(list, allOtherSubset);
        }

        return map;
    }

这里讲解一下寻找真子集的思路：

如图，假设这是一个数组，那么我们可以这样来寻找子集：将每一个数组元素是否出现用1或0来表示。然后我们只需要将出现1的元素重新拼接成一个新的数组，这样就可以找到该数组的子集。之后去除空集和该数组本身，就可以得到该数组的所有真子集了。

4.3.3 doApriori():

public List<List<Integer>> doApriori() {
        // 4.生成频繁1项集
        Map<List<Integer>, Integer> oneFreTemp = apriori.oneFrequentSet(dataSet);

        // 记录总个数（交易数、）
        int count = dataSet.size();

        // map形式的频繁1项集
        Map<List<Integer>, Integer> oneSupportItemsSet = apriori.getSupportItemsSet(oneFreTemp, count);

        // 记录一下频繁1项集的个数，可能会围绕其展开
        int oneFreCount = oneSupportItemsSet.size();

        // list形式的频繁1项集
        List<List<Integer>> oneFre = AprioriUtil.setToList(oneSupportItemsSet);

        List<List<Integer>> Lk = oneFre;
        List<List<Integer>> allFreSet = new ArrayList<List<Integer>>();
        allFreSet.addAll(Lk);
        // 5.循环执行Ck->Lk, Lk->Ck,直到没有频繁项集出现，就可以停止了。
        for (int k = 1; k <= count; k++) {
            // 6.根据频繁项集Lk生成候选Ck+1项集
            List<List<Integer>> CkAdd = apriori.lkToCk(Lk, k);
//            System.out.println(CkAdd);

            // 生成频繁项集Lk+1
            Map<List<Integer>, Integer> LkTempAdd = apriori.ckToLk(dataSet, CkAdd);
            Map<List<Integer>, Integer> LkAdd = apriori.getSupportItemsSet(LkTempAdd, count);

            Lk = AprioriUtil.setToList(LkAdd);
            // 7.判断频繁项集Lk+1是否为空，
            if (Lk.size() == 0) {
                break;
            } else {
                allFreSet.addAll(Lk);
            }
        }

        return allFreSet;
    }

5、运行结果

5.1 数据集：

A、B、C、D、E、F、G
A、B、C、D、E、H
A、B、C、D、E、F、G、H
A、B、C、G、H
A、B、C、D、G、H
A、B、C、D、E、F、G、H
A、B、C、D、E、F、G
A、B、C、E、G、H
A、B、C、D、E、F、H
C、D、E、F、G、H
A、B、C、D、G、H
A、C、D、E、F、G、H
A、B、C、E、F、G、H
B、C、E、F、G、H