本文是个人对spmf中example1. mining frequent itemsets by using the apriori algorithm的学习.
What is Apriori?
Apriori is an algorithm for discovering frequent itemsets in transaction databases. It was proposed by Agrawal & Srikant
input file format:
1 3 4
2 3 5
1 2 3 5
2 5
1 2 3 5
so the transaction is:
Transaction
{1, 3, 4}
{2, 3, 5}
{1, 2, 3, 5}
{2, 5}
{1, 2, 3, 5}
在java实现中，可用
private List<int[]> database = null;
database = new ArrayList<int[]>(); 用来存储上面的结构(即存储各个transaction)
output(with minsup of 40%)
itemsets support
{1} 3
{2} 4
{3} 4
{5} 4
{1, 2} 2
{1, 3} 3
{1, 5} 2
{2, 3} 3
{2, 5} 4
{3, 5} 3
{1, 2, 3} 2
{1, 2, 5} 2
{1, 3, 5} 2
{2, 3, 5} 3
{1, 2, 3, 5} 2
java实现的一些实现细节记录
用HashMap结构 Map<Integer, Integer> mapItemCount = new HashMap<Integer, Integer>();来记录每个item和其出现的次数
当k=1时，（k为 the size of itemset）
List<Integer> frequent1 = new ArrayList<Integer>();
判断当HashMap中各item出现的次数满足minsup时:
frequent1.add(entry.getKey());
saveItemsetToFile(entry.getKey(), entry.getValue());
下面产生候选集合：
当k=2时，即｛1，2｝、｛1，3｝这些itemsets，此时从frequent1中产生候选集合项，生成candidates（所有情况）,然后通过计算各候选项集的支持度，找出k=2时满足minsup的项集。(计算各候选项集支持度方法见下文)
当k=3或以上时，选取封装了 k-1时 频繁项集 List<Itemset> 作为 生成大小为K的候选集函数 的输入，生成方法是：“we compare items of itemset1 and itemset2.If they have all the same k-1 items and the last item of itemset1 is smaller than the last item of itemset2, we will combine them to generate a candidate”，之后再利用allSubsetsOfSizeK_1AreFrequent()来检测生成的大小为k的 预备候选集 中，其所有的大小为k-1的子集是否存在于 大小为k-1的频繁项集中，如果都存在，则将此大小为k的预备候选集即被视为候选集，接下来再计算各候选项集的支持度，找出满足minsup的候选集作为频繁项集。
计算各候选项集支持度的计算过程如下：
对于文件(database)中的每行(transaction)，用candidates中所有的candidate来试验是否存在于第一个transaction中，方法是，拿第一个transaction中的item与candidate中每个位置(pos)上的item进行比较，能比较到pos == candidate.itemset.length位置上时，说明该candidate已经存在于此transaction中。换个candidate继续上述过程，所有candidate都完成上述过程后，换个transaction继续上述过程。
计算过程核心部分代码如下：
for(int[] transaction: database){
loopCand: for(Itemset candidate : candidatesK){
int pos = 0;
for(int item: transaction){
if(item == candidate.itemset[pos]){
pos++;
if(pos == candidate.itemset.length){
candidate.support++;
continue loopCand;
}//end the second if
}//end the first if
else if(item > candidate.itemset[pos]){
continue loopCand;}
}//end for
}//end for
}//end the first for