正文之前
当初毕设的时候准备用这个算法来着，不过后来为了给自己减少工作量（俗称偷懒），就没搞了，没想到这两天看一篇论文看到了这个，重新捡起来学一下。对于我这种算法底子不是很好的来说。。只能代码实现来感受下了。。
正文
基本概念
关联分析是一种在大规模数据集中寻找有趣关系的非监督学习算法。这些关系可以有两种形式：频繁项集或者关联规则。频繁项集（frequent item sets)是经常出现在一块的物品的集合，关联规则(association rules)暗示两种物品之间可能存在很强的关系。
下图是一个乒乓球店的交易记录，〇表示顾客购买了商品。其中{底板,胶皮,浇水}就是一个频繁项集；从中可以找到底板->胶皮这样的关联规则：
然后是两个至关重要的参数的表示法：
支持度
怎样有效定义频繁和关联？其中最重要的两个概念是支持度和置信度。
支持度(support)从字面上理解就是支持的程度，一个项集的支持度(support)被定义为数据集中包含该项集的记录所占的比例。上图中{底板}的支持度=(5/6) * 100%。
这个概念其实经常在现实生活中出现，翻译成支持率似乎更好理解，典型的例子就是投票，比如英国脱欧的支持率为51.89%。
用数学去解释就是，设W 中有s％的事务同时支持物品集A和B，s％称为{A，B}的支持度，即:
support({A,B}) = num(A∪B) / W = P(A∩B)
num(A∪B)表示含有物品集{A,B}的事务集的个数，不是数学中的并集。
置信度
置信度(confidence)揭示了A出现时B是否一定出现，如果出现，则出现的概率是多大。如果A->B的置信度是100%，则说明A出现时B一定会出现（返回来不一定）。上图中底板共出现5次，其中4次同时购买了胶皮，底板->胶皮的置信度是80%。
用公式表示是，物品A->B的置信度=物品{A,B}的支持度 / 物品{A}的支持度：
Confidence(A->B) = support({A,B}) / support({A}) = P(B|A)
这是Apriori算法的关键数学模型。下面就是关键的Java实现，有时候我觉得看代码真的比算法更加直观些。。。不过，当我打开了算法流程图的大门。
Apriori算法过程
发现频繁项集的过程如上图所示：
- 由数据集生成候选项集C1（1表示每个候选项仅有一个数据项）；再由C1通过支持度过滤，生成频繁项集L1（1表示每个频繁项仅有一个数据项）。
- 将L1的数据项两两拼接成C2。
- 从候选项集C2开始，通过支持度过滤生成L2。L2根据Apriori原理拼接成候选项集C3；C3通过支持度过滤生成L3……直到Lk中仅有一个或没有数据项为止。
下面是一个超市的交易记录：
Apriori算法发现频繁项集的过程如下：
或者这是我抄代码的博客的图，也挺好看的：
还有一段伪代码奉上：
算法：Apriori
输入：D - 事务数据库；min_sup - 最小支持度计数阈值
输出：L - D中的频繁项集
方法：
L1=find_frequent_1-itemsets(D); // 找出所有频繁1项集
For(k=2;Lk-1!=null;k++){
Ck=apriori_gen(Lk-1); // 产生候选，并剪枝
For each 事务t in D{ // 扫描D进行候选计数
Ct =subset(Ck,t); // 得到t的子集
For each 候选c 属于 Ct
c.count++;
}
Lk={c属于Ck | c.count>=min_sup}
}
Return L=所有的频繁集；
Procedure apriori_gen(Lk-1:frequent(k-1)-itemsets)
For each项集l1属于Lk-1
For each项集 l2属于Lk-1
If((l1[1]=l2[1])&&( l1[2]=l2[2])&&…….
&& (l1[k-2]=l2[k-2])&&(l1[k-1]<l2[k-1])) then{
c=l1连接l2 //连接步：产生候选
if has_infrequent_subset(c,Lk-1) then
delete c; //剪枝步：删除非频繁候选
else add c to Ck;
}
Return Ck;
Procedure has_infrequent_sub(c:candidate k-itemset; Lk-1:frequent(k-1)-itemsets)
For each(k-1)-subset s of c
If s不属于Lk-1 then
Return true;
Return false;
下面就是真正的Java代码实现了。
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Set;
public class Apriori{
// 支持度阈值
private final static int SUPPORT = 2;
// 置信度阈值
private final static double CONFIDENCE = 0.7;
// 项之间的分隔符
private final static String GAP = ";";
// 项之间的分隔符
private final static String CON = "-->";
/**
* 这个是用来找出1-频繁项集的方法，因为1-频繁项集的特殊性，
* 所以需要特别的方法来返回1-频繁项集
* @param dataList
* @return
*/
private Map<String, Integer> find1_FrequentSet(ArrayList<String> dataList){
Map<String, Integer> resultSetMap = new HashMap<>();
for (String data:dataList) {
String [] strings = data.split(GAP);
//这是把所有的购买记录一条条的筛选出来
for (String string : strings) {
string += GAP;
if (resultSetMap.get(string)==null) {
resultSetMap.put(string,1);
}
else {
resultSetMap.put(string, resultSetMap.get(string)+1);
}
}
}
//返回的是一个各种商品对应出现频次的Map（或可称之为频繁项集）。键为商品序号，值为出现次数。
return resultSetMap;
}
/**
* 使用先验知识，判断候选集是否是频繁项集
* @param candidate
* @param setMap
* @return
*/
private boolean hasInfrequentSubset(String candidateString, Map<String, Integer> setMap){
String[] strings = candidateString.split(GAP);
//找出候选集所有的子集，并判断每个子集是否属于频繁子集
for (int i=0; i<strings.length; ++i ) {
String subString = "";
for (int j = 0; j<strings.length;++j ) {
if (j!=i) {
subString += strings[j]+GAP;
}
}
if (setMap.get(subString)==null) {
return true;
}
}
return false;
}
/**
* 根据上面的频繁项集的集合选出候选集
* @param setMap
* @return
*/
private Map<String,Integer> aprioriGen(Map<String, Integer> setMap){
//此处传入的参数就是上面返回的频繁项集。
Map<String, Integer> candidateSetMap = new HashMap<>();
// 对每个商品取集合
Set<String> candidateSet = setMap.keySet();
//单独考虑每个商品的支持度，如果合格，就可以进行拼接。否则丢掉。
for (String s1 : candidateSet) {
String[] strings1 = s1.split(GAP);
String s1string = "";
for (String temp : strings1) {
s1string += temp+GAP;
}
for (String s2 : candidateSet) {
//此处也是默认商品序号是有序的。这样先判定前len-1项是否相等。
//如果前面相等，第len项不相等，那么就可以拼接成len+1长度的候选集了。
String[] strings2 = s2.split(GAP);
boolean flag = true;
for (int i=0; i< strings1.length-1;++i) {
if (strings1[i].compareTo(strings2[i]) != 0) {
flag = false;
break;
}
}
if (flag && strings1[strings1.length-1].compareTo(strings2[strings2.length-1])<0) {
//连接步：产生候选
String c=s1string+strings2[strings2.length-1]+GAP;
if (hasInfrequentSubset(c,setMap)) {
//剪枝步：删除非频繁的候选
}
else {
candidateSetMap.put(c,0);
}
}
}
}
return candidateSetMap;
}
/**
* 算法主程序
* @param dataList
* @return
*/
public Map<String, Integer> apriori(ArrayList<String> dataList){
Map<String, Integer> setpFrequentSetMap = new HashMap<>();
setpFrequentSetMap.putAll(find1_FrequentSet(dataList));
Map<String, Integer> frequentSetMap = new HashMap<String, Integer>();
frequentSetMap.putAll(setpFrequentSetMap);
// Into the loop choose
while(setpFrequentSetMap!=null && setpFrequentSetMap.size() > 0){
Map<String, Integer> candidateSetMap = aprioriGen(setpFrequentSetMap);
//得到的就是候选集 candidateSetMap ，当然我们只要key部分即可啦！
Set<String> candidateKeySet = candidateSetMap.keySet();
//扫描D，进行计数
for (String data : dataList) {
for (String candidate : candidateKeySet) {
boolean flag = true;
String[] strings = candidate.split(GAP);
for (String string : strings) {
//意味着在Data，也就是在初始的购物记录中查找当前的频繁项集中的某一条。寻找string如果不成功，则返回-1；
// indexOf(Object o)方法
// 功能：查找某个元素在ArrayList中第一次出现的位置。
if (data.indexOf(string+GAP)==-1) {
flag = false;
break;
}
}
//如果查找成功，那么就可以丢到正式的候选集中了。
if (flag) {
candidateSetMap.put(candidate,candidateSetMap.get(candidate)+1);
}
}
}
//从候选集中找到符合支持度的频繁项集，stepFrequentSetMap顾名思义就是每一次找到的新的频繁集。
//所以在置入新的频繁集之前，都要先把上次的清空掉。
setpFrequentSetMap.clear();
for (String candidate : candidateKeySet) {
Integer count = candidateSetMap.get(candidate);
if (count>=SUPPORT) {
setpFrequentSetMap.put(candidate,count);
}
}
// puaAll的作用是把一个Map的所有元素置入并且去重。
// 合并所有频繁集
frequentSetMap.putAll(setpFrequentSetMap);
}
//While循环结束的条件是新的频繁项集的大小为0.也就是必须要完全空了才出来。
//这时候已经确保了frequentSetMap包含有所有的频繁项集了。
return frequentSetMap;
}
/**
* 求一个集合所有的非空真子集
*
* @param sourceSet
* @return
* 为了以后可以用在其他地方，这里我们不是用递归的方法
*
* 参考：http://blog.163.com/xiaohui_1123@126/blog/static/3980524020109784356915/
* 思路：假设集合S（A,B,C,D），其大小为4，拥有2的4次方个子集，即0-15，二进制表示为0000，0001，...，1111。
* 对应的子集为空集，{D}，...，{A,B,C,D}。
*/
private List<String> subset(String sourceSet){
//“按位对应法”,从1-2^strings.length-1位，可以用二进制来表示是否取到该值。
/*
如集合A={a,b,c},对于任意一个元素，在每个子集中，要么存在，要么不存在。 映射为子集：
(a,b,c)
(1,1,1)->(a,b,c)
(1,1,0)->(a,b)
(1,0,1)->(a,c)
(1,0,0)->(a)
(0,1,1)->(b,c)
(0,1,0)->(b)
(0,0,1)->(c)
(0,0,0)->@(@表示空集)
*/
List<String> result = new ArrayList<>();
String[] strings = sourceSet.split(GAP);
for (int i = 1; i<(Math.pow(2,strings.length)) - 1; ++i ) {
String item = "";
int ii = i;
int[] flag = new int[strings.length];
int count = 0;
while(ii>=0 && count<strings.length ){
flag[count] = ii%2;
//此处可以理解为右移操作，即检查完当前位之后，可以跳到更高位去检测是否取值。
ii=ii/2;
++count;
}
for (int s=0;s<flag.length;++s) {
if (flag[s]==1) {
//此处应该是从右边开始往左边加。所以item在后面
item+=strings[s]+GAP+item;
}
}
result.add(item);
}
return result;
}
/**
* 集合运算，A/B
* @param A
* @param B
* @return
*/
private String expect(String stringA, String stringB){
String result = "";
String[] stringAs = stringA.split(GAP);
String[] stringBs = stringB.split(GAP);
for(int i=0; i<stringAs.length;++i){
boolean flag = true;
for (int j = 0; j<stringBs.length ;++j ) {
//如果指定的数与参数相等返回0。
// 如果指定的数小于参数返回 -1。
// 如果指定的数大于参数返回 1。
if (stringAs[i].compareTo(stringBs[j])==0) {
flag= false;
break;
}
}
if (flag) {
result += stringAs[i]+GAP;
}
}
return result;
}
/**
* 由频繁项集产生关联规则
* @param frequentSetMap
* @return
*/
public Map<String, Double> getRelationRules(Map<String, Integer> frequentSetMap){
Map<String, Double> relationMap = new HashMap<>();
Set<String> KeySet = frequentSetMap.keySet();
for (String key : KeySet) {
List<String> keySubset = subset(key);
for (String keySubSetItem : keySubset) {
//子集keySubsetItem也是频繁项
Integer count = frequentSetMap.get(keySubSetItem);
if (count!=null) {
/*
置信度
置信度(confidence)揭示了A出现时B是否一定出现，如果出现，则出现的概率是多大。如果A->B的置信度是100%，则说明A出现时B一定会出现（返回来不一定）。
上图中底板共出现5次，其中4次同时购买了胶皮，底板->胶皮的置信度是80%。
用公式表示是，物品A->B的置信度=物品{A,B}的支持度 / 物品{A}的支持度：
Confidence(A->B) = support({A,B}) / support({A}) = P(B|A)
*/
Double confidence = (1.0*frequentSetMap.get(key))/(1.0*frequentSetMap.get(keySubSetItem));
if (confidence > CONFIDENCE) {
relationMap.put(keySubSetItem+CON+expect(key,keySubSetItem),confidence);
}
}
}
}
return relationMap;
}
public static void main(String[] args){
ArrayList<String> dataList = new ArrayList<>();
dataList.add("1;2;5;");
dataList.add("2;4;");
dataList.add("2;3;");
dataList.add("1;2;4;");
dataList.add("1;3;");
dataList.add("2;3;");
dataList.add("1;3;");
dataList.add("1;2;3;5;");
dataList.add("1;2;3;");
System.out.println("=数据集合==========");
for(String string:dataList){
System.out.println(string);
}
Apriori2 apriori2 = new Apriori2();
System.out.println("=频繁项集==========");
Map<String, Integer> frequentSetMap = apriori2.apriori(dataList);
Set<String> keySet = frequentSetMap.keySet();
for(String key:keySet){
System.out.println(key+" : "+frequentSetMap.get(key));
}
System.out.println("=关联规则==========");
Map<String, Double> relationRulesMap = apriori2.getRelationRules(frequentSetMap);
Set<String> rrKeySet = relationRulesMap.keySet();
for (String rrKey : rrKeySet){
System.out.println(rrKey + " : " + relationRulesMap.get(rrKey));
}
}
}
上面这些代码基本是照抄下面这个博客里面的。我就改动了一下那个获取真子集的函数而已。其他的不好怎么改，还不如直接抄。不过自己过一遍手之后确实感觉理解深刻了很多。
控制台输出如下：
[zbzhang@node61 JavaCode]$ java Apriori2
=数据集合==========
1;2;5;
2;4;
2;3;
1;2;4;
1;3;
2;3;
1;3;
1;2;3;5;
1;2;3;
=频繁项集==========
1;2; : 4
1;3; : 4
5; : 2
2;3; : 4
4; : 2
2;4; : 2
1;5; : 2
3; : 6
2; : 7
1; : 6
1;2;5; : 2
1;2;3; : 2
2;5; : 2
=关联规则==========
4;->2; : 1.0
5;->1;2; : 1.0
5;->1; : 1.0
1;5;->2; : 1.0
5;->2; : 1.0
2;5;->1; : 1.0
[zbzhang@node61 JavaCode]$
正文之后
下面是参考文献时间：
使用Apriori进行关联分析（一）
频繁模式挖掘apriori算法介绍及Java实现
Java compareTo() 方法
Map获取其键和值
Java进阶--深入理解ArrayList实现原理
ArrayList的用法整理
网友评论