从Apriori到MS-Apriori算法

前言

最近的几个月一直在研究和学习各种经典的DM，机器学习的相关算法，收获还是挺多的，另外还整了一个DM算法库，集成了很多数据挖掘算法，放在了我的github上，博友的热度超出我的想象，有很多人给我点了star，在此感谢各大博友们，我将会继续更新我的DM算法库。也许这些算法还不能直接拿来用，但是可以给你提供思路，或变变数据的输入格式就能用了。好，扯得有点远了，现在说正题，本篇文章重新回到讲述Apriori算法，当然我这次不会讲之前说过的Apriori，（比较老套的那些东西网上也很多，我分析的也不一定是最好)，本文的主题是Apriori算法的升级版本算法--MS-Apriori。在前面加了Ms，是什么意思呢，他可不是升级的意思，Ms是Mis的缩写，MIS的全称是Min Item Support，最小项目支持度。这有何Apriori算法有什么关系呢，在后面的正文中，我会主要解释这是什么意思，其实这只是其中的一个小的点，Ms-Apriori还是有很多对于Apriori算法的改进的。

Apriori

在了解Ms-Apriori算法之前，还是有必要重新回顾一下Apriori算法，Apriori算法是一种演绎算法，后一次的结果是依赖于上一次的计算结果的，算法的目的就是通过给定的数据挖掘出其中的频繁项，进而推导出关联规则，属于模式挖掘的范畴。Apriori算法的核心步骤可以概括为2个过程，1个是连接运算，1个剪枝运算，这具体的过程就不详细说了，如果想要了解的话，请点击我的Apriori算法分析。尽管Apriori算法在一定的程度上看起来非常的好用，但是他并不是十全十美的，首先在选择的类型上就存在限制，他无法照顾到不同类型的频繁项的挖掘。比如说一些稀有项目的挖掘，比如部分奢侈品。换句话说，如果最小支持度设置的过大，就会导致这些稀有的项集就很难被发现，于是我们就想把这个最小支持度值调得足够小不久OK了吗，事实并非这么简单，支持度调小的话，会造成巨大量的频繁项集合候选项的产生，同时会有大量的一些无关的关联规则被推导出来，当然这个问题就是ms-apriori所要解决的主要问题。下面看看ms-apropri给出了怎么样的解决办法。

Ms-Apriori

Ms-Apriori算法采用另外一种办法，既然统一的支持度值不能兼顾所有的情况，那我可以设置多个支持度值啊，每个种类项都有一个最小支持度阈值，然后一个频繁项的最小支持度阈值取其中项集元素中的最小支持度值作为该项集的最小支持度值。这样的话，如果一个频繁项中出现了稀有项集，则这个项集的最小支持度值就会被拉低，如果又有某个项都是出现频率很高的项构成的话，则支持度阈值又会被拉高。当然，如果出现了一个比较难变态的情况就是，频繁项中同时出现了稀有项和普通项，我们可以通过设置SDC支持度差别限制来限制这种情况的发生，使之挖掘的频繁项更加的合理。通过这里的描述，你就可以发现，当mis最小支持度阈值数组的个数只有1个的时候，ms-apriori算法就退化成了Apriori算法了。

其实ms-apriori算法在某些细节的处理上也有对原先的算法做过一定的优化，这里提及2点。

1、每个候选项的支持度值的统计

原先Apriori算法的操作是扫描整个数据集，进行计数的统计，说白了就是线性扫描一遍，效率自不必说，但是如果你自己思考，其实每次的统计的结果一定不会超过他的上一次子集的结果值，因为他是从上一次的计算过程演绎而来的，当前项集的结果是包含了子项集的结果的，所以改进的算法是每次从子集的计数量中再次计算支持度值，具体操作详见后面我的代码实现，效率还是提高了不少。

2、第二是关联规则的推导

找到了所有的频繁项，找出其中的关联规则最笨的办法就是一个个去算置信度，然后输出满足要求条件的规则，但是其实这里面也包含有上条规则中类似的特点，举个例子，如果已经有一条规则，{1}-->{2, 3, 4}，代表在存在1的情况下能退出2,3,4,的存在，那么我们就一定能退出{1, 2}--->{3, 4}，因为这是后者的情况其实是被包含于前者的情况的，如果你还不能理解，代入置信度计算的公式，分子相同的情况下，{1,2}发生的情况数一定小于或等于{1}的情况，于是整个置信度必定{1，2}的大于{1}的情况。

关联规则挖掘的数据格式

这里再随便说说关联规则的数据格式，也许在很多书中，用于进行Apriori这类算法的测试的数据都是事务型的数据，其实不是的关系表型的数据同样可以做关联规则的挖掘，不过这需要经过一步预处理的方式，让机器能够更好的识别，推荐一种常见的做法，就是采用属性名+属性值的方式，单单用属性值是不够的，因为属性值是在不同的属性中可能会有重，这点在CBA(基于关联规则分类算法)中也提到过一些，具体的可以查阅CBA基于关联规则分类。

MS-Apriori算法的代码实现

算法的测试我采用了2种类型数据做测试一种是事务型数据，一种是非事务型的数据，输入分别如下：

input.txt:

T1 1 2 5
T2 2 4
T3 2 3
T4 1 2 4
T5 1 3
T6 2 3
T7 1 3
T8 1 2 3 5
T9 1 2 3

input2.txt

Rid Age Income Student CreditRating BuysComputer
1 Youth High No Fair No
2 Youth High No Excellent No
3 MiddleAged High No Fair Yes
4 Senior Medium No Fair Yes
5 Senior Low Yes Fair Yes
6 Senior Low Yes Excellent No
7 MiddleAged Low Yes Excellent Yes
8 Youth Medium No Fair No
9 Youth Low Yes Fair Yes
10 Senior Medium Yes Fair Yes
11 Youth Medium Yes Excellent Yes
12 MiddleAged Medium No Excellent Yes
13 MiddleAged High Yes Fair Yes
14 Senior Medium No Excellent No

算法工具类MSAprioriTool.java:

package DataMining_MSApriori;

import java.io.BufferedReader;
import java.io.File;
import java.io.FileReader;
import java.io.IOException;
import java.text.MessageFormat;
import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.Map;

import DataMining_Apriori.FrequentItem;

/**
 * 基于多支持度的Apriori算法工具类
 * 
 * @author lyq
 * 
 */
public class MSAprioriTool {
	// 前件判断的结果值，用于关联规则的推导
	public static final int PREFIX_NOT_SUB = -1;
	public static final int PREFIX_EQUAL = 1;
	public static final int PREFIX_IS_SUB = 2;

	// 是否读取的是事务型数据
	private boolean isTransaction;
	// 最大频繁k项集的k值
	private int initFItemNum;
	// 事务数据文件地址
	private String filePath;
	// 最小支持度阈值
	private double minSup;
	// 最小置信度率
	private double minConf;
	// 最大支持度差别阈值
	private double delta;
	// 多项目的最小支持度数,括号中的下标代表的是商品的ID
	private double[] mis;
	// 每个事务中的商品ID
	private ArrayList<String[]> totalGoodsIDs;
	// 关系表数据所转化的事务数据
	private ArrayList<String[]> transactionDatas;
	// 过程中计算出来的所有频繁项集列表
	private ArrayList<FrequentItem> resultItem;
	// 过程中计算出来频繁项集的ID集合
	private ArrayList<String[]> resultItemID;
	// 属性到数字的映射图
	private HashMap<String, Integer> attr2Num;
	// 数字id对应属性的映射图
	private HashMap<Integer, String> num2Attr;
	// 频繁项集所覆盖的id数值
	private Map<String, int[]> fIt