关联规则用于发现交易数据中，不同商品之间的关系，这些规则反映了顾客的购买行为模式。如顾客经常在购买A商品的时候也会购买B商品，著名的“啤酒与尿布”的案例就是关联规则的成功应用案例
基本概念
- 交易数据库（Transaction Database）：存储着二维结构的记录集。定义为：D
- 所有项集（Items）：所有项目的集合。定义为：I。
- 记录 （Transaction ）：在资料库里的一笔记录。定义为：T，T ∈ D
- 项集（Itemset）：同时出现的项的集合。定义为：k-itemset（k项集），k-itemset ? T。除非特别说明，否则下文出现的k均表示项数。
-
支持度（Support）：定 义为 supp(X) = occur(X) / count(D) = P(X)。
1. 解释一：比如选秀比赛，那个支持和这个有点类似，那么多人（资料库），其中有多少人是选择（支持）你的，那个就是支持度； 2. 解释二：在100个人去超市买东西的，其中买苹果的有9个人，那就是说苹果在这里的支持度是 9，9/100； 3. 解释三：P(X)，意思是事件X出现的概率； 4. 解释四：关联规则当中是有绝对支持度（个数）和相对支持度（百分比）之分的。 -
置信度（Confidence/Strength）： 定义为 conf(X->Y) = supp(X ∪ Y) / supp(X) = P(Y X)。 在历史数据中，已经买了某某（例如：A、B）的支持度和经过挖掘的某规则（例如：A=>B）中A的支持度的比 例，也就是说买了A和B的人和已经买了 A的人的比例，这就是对A推荐B的置信度（A=>B的置信度）< /span> - 候选集（Candidate itemset）：通过向下合并得出的项集。定义为C[k]。
- 频繁集（Frequent itemset）：支持度大于等于特定的最小支持度（Minimum Support/minsup）的项集。表示为L[k]。注意，频繁集的子集一定是频繁集。
-
提升比率（提升度Lift）：lift(X -> Y) = lift(Y -> X) = conf(X -> Y)/supp(Y) = conf(Y -> X)/supp(X) = P(X and Y)/(P(X)P(Y))
经过关联规则分析后，针对某些人推销（根据某规则）比盲目推销（一般来说是整个数据）的比率，这个比率越高越好，我们称这个规则为强规则；
获取频繁项集
Aprior算法的重点在于寻找频繁项集，其算法过程如下：
- 由交易数据库产生频繁1项集，产生方式：通过扫描交易数据库，对每个交易事务中的记录进行扫描，对每个记录进行计数，过滤出满足频繁项集支持数的那些记录。
- 频繁1项集产生频繁K项集合的过程
- 假设存在频繁K-1项集，产生频繁K项集合的候选集，产生方式：频繁K-1项集进行自连接，得到频繁K项集的候选集。
- 对候选集中的记录进行筛选，其筛选规则：首先剔除相同元素的自连接，然后扫描数据库，保留出现在数据库中的候选集元素，并对出线次数计数，接着过滤出满足频繁项集支持数的进行，得到频繁K项集
- 把得到的频繁K项集并入频繁项集中。
虚线框右下角的N表示执行找到频繁N项集，该虚线框内的内容表示迭代过程。
获取关联规则
由频繁项集，可以产生关联规则。对频繁项集中的任意两个事务，如果这两个事务的商品条目（Item）没有交集，而这两个事务的的条目的并集又包含在该频繁项集合中，那么就可以计算出相应的置信度，如果置信度大于给定的阀值，则这两个事务具有关联关系。
简要算法实现
package association;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Map.Entry;
import java.util.Set;
public class Apriori2 {
public static String SPLIT = ";";
public static int F = 2;
public static double C = 0.7;
public static List<String> transList = new ArrayList<String>();
static {
transList.add("A;B;E;");
transList.add("B;D;");
transList.add("B;C;");
transList.add("A;B;D");
transList.add("A;C;");
transList.add("B;C;");
transList.add("A;C;");
transList.add("A;B;C;E;");
transList.add("A;B;C;");
}
private Map<String, Integer> getF1Item() {
Map<String, Integer> F1items = new HashMap<String, Integer>();
for (String tran : transList) {
String[] items = tran.split(SPLIT);
for (String item : items) {
if (F1items.get(item + SPLIT) == null) {
F1items.put(item + SPLIT, 1);
} else {
F1items.put(item + SPLIT, F1items.get(item + SPLIT) + 1);
}
}
}
Map<String, Integer> res = new HashMap<String, Integer>();
for (Map.Entry<String, Integer> entry : F1items.entrySet()) {
if (entry.getValue() >= F) {
res.put(entry.getKey(), entry.getValue());
}
}
return res;
}
public Map<String, Integer> getFItems() {
Map<String, Integer> f1items = getF1Item();
Map<String, Integer> fItems = new HashMap<String, Integer>();
Map<String, Integer> tFItems = new HashMap<String, Integer>();
fItems.putAll(f1items);
tFItems.putAll(f1items);
while (tFItems != null && tFItems.size() != 0) {
Map<String, Integer> cItems = getCItems(tFItems);
//过滤候选集
for (String tran : transList) {
for (String citems : cItems.keySet()) {
boolean flag = false;
String[] items = citems.split(SPLIT);
for (String item : items) {
if (tran.indexOf(item + SPLIT) == -1) {
flag = true;
break;
}
}
if (!flag) {
cItems.put(citems, cItems.get(citems) + 1);
}
}
}
tFItems.clear();
for (Entry<String, Integer> citem : cItems.entrySet()) {
if (citem.getValue() >= F) {
tFItems.put(citem.getKey(), citem.getValue());
}
}
fItems.putAll(tFItems);
}
return fItems;
}
/**
* 产生候选集
* @param fitems
* @return
*/
private Map<String, Integer> getCItems(Map<String, Integer> fitems) {
Map<String, Integer> citems = new HashMap<String, Integer>();
Set<String> items = new HashSet<String>();
for (String item1 : fitems.keySet()) {//频繁K项集的自连接，产生候选集
for (String item2 : fitems.keySet()) {
if (!item1.equals(item2)) {
String[] items1 = item1.split(SPLIT);
String[] items2 = item2.split(SPLIT);
items.addAll(Arrays.asList(items1));
items.addAll(Arrays.asList(items2));
StringBuilder builder = new StringBuilder();
for (String string : items) {
builder.append(string).append(SPLIT);
}
items.clear();
citems.put(builder.toString(), 0);
}
}
}
return citems;
}
/**
* 由频繁项集构建关联规则
* @param fItems
* @return
*/
public Map<String,Double> getRule(Map<String,Integer> fItems){
Map<String,Double> rules = new HashMap<String, Double>();
Set<String> result = new HashSet<String>();
for(String key1 : fItems.keySet()){
for(String key2:fItems.keySet()){
Set<String> union1 = new HashSet<String>();
Set<String> union2 = new HashSet<String>();
union1.addAll(Arrays.asList(key1.split(SPLIT)));
union2.addAll(Arrays.asList(key2.split(SPLIT)));
result.clear();
result.addAll(union1);
result.retainAll(union2);
if(result.size()==0){//两个频繁项没有交集
result.clear();
result.addAll(union1);
result.addAll(union2);
boolean flag = false;
for(String key3:fItems.keySet()){//两个频繁项的的并集也是频繁项
flag=false;
for(String item:result){
if(!key3.contains(item+SPLIT)){
flag = true;
break;
}
}
if(!flag){//计算这两个频繁项关联关系的置信度
double conf = fItems.get(key3)/(double)fItems.get(key1);
if(conf>C){
rules.put(key1+"->"+key2, conf);
}
}
}
}
}
}
return rules;
}
public static void main(String[] args) {
Apriori2 ap2 = new Apriori2();
Map<String, Integer> fItems = ap2.getFItems();
for (Entry<String, Integer> item : fItems.entrySet()) {
System.out.println(item.getKey() + ": " + item.getValue());
}
}
}