数据挖掘课后作业.doc

数据挖掘课后作业

5.4（实现项目）使用你熟悉的程序设计语言（如C++或Java），实现本章介绍的三种频繁项集挖掘算法：（1）Apriori [AS94B]，（2）FP增长[HPY00]和（3）ECLAT [Zak00]（使用垂直数据格式挖掘）。在各种类型的大型数据集上比较每种算法的性能。写一个报告，分析在哪些情况下（如数据大小、数据分布、最小支持阀度值设置和模式的稠密度），某种算法比其他算法好，并陈述理由。
三种算法的比较
1、对与项集较大，频繁项集较分散，是一个稀疏型的数据集，性能为Apriori>FP-growth>Eclat
2、对与数据集的项集较小，数据非常稠密的数据集，性能为：FP-growth>Apriori>Eclat
各算法采用的数据表示模式及挖掘策略不同。采用优化措施后的 Apriori算法，对于非稠密数据己经具有较高的效率，其性能甚至优于FP-growth 算法;但由于其采用的是广度优先的挖掘策略，对稠密数据效率仍较差。而 Eclat 算法采用的纵向表示法，对数据集较小的稠密数据，效率相对较高;但对于数据集较大的稀疏数据，效率较低,FP一树浓缩了数据库的主要信息，分而治之的挖掘策略也使挖掘问题的复杂程度有所降低。

答：（1）Apriori算法的实现：使用Java语言实现Apriori算法，AprioriAlgorithm类包含了频繁项集的挖掘过程和频繁关联规则的挖掘过程；ProperSubsetCombination辅助类用于计算一个频繁项集的真子集，采用组合原理，基于数值编码原理实现的组合求解集合的真子集。
Apriori算法的核心实现类为AprioriAlgorithm，实现的Java代码如下所示：
（一）核心类
package org.shirdrn.datamining.association;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;
import java.util.Map;
import java.util.Set;
import java.util.TreeMap;
/**
* 关联规则挖掘：Apriori算法
*
* eCount; // 事务数据库中的事务数

private Map>> freqItemSet; // 频繁项集集合
private Map, Set>> assiciationRules; // 频繁关联规则集合

public AprioriAlgorithm(
    Map> txDatabase,
    Float minSup,
    Float minConf) {
   this.txDatabase = txDatabase;
   this.minSup = minSup;
   this.minConf = minConf;
   this.txDatabaseCount = this.txDatabase.size();
   freqItemSet = new TreeMap>>();
   assiciationRules = new HashMap, Set>>();
}

/**
* 扫描事务数据库，计算频繁1-项集
* @return
*/
public Map<Set, Float> getFreq1ItemSet() {
   Map, Float> freq1ItemSetMap = new HashMap, Float>();
   Map, Integer> candFreq1ItemSet = this.getCandFreq1ItemSet();
   Iterator, Integer>> it = candFreq1ItemSet.entrySet().iterator();
   while(it.hasNext()) {
    Map.Entry, Integer> entry = it.next();
    // 计算支持度
    Float supported = new Float(entry.getValue().toString())/new Float(txDatabaseCount);
    if(supported>=minSup) {
     freq1ItemSetMap.put(entry.getKey(), supported);
    }
   }
   return freq1ItemSetMap;
}

/**
* 计算候选频繁1-项集
* @return
*/
public Map, Integer> getCandFreq1ItemSet() {
   Map, Integer> candFreq1ItemSetMap = new HashMap, Integer>();
   Iterator>> it = txDatabase.entrySet().iterator();
   // 统计支持数，生成候选频繁1-项集
   while(it.hasNext()) {
    Map.Entry> entry = it.next();
    Set itemSet = entry.getValue();
    for(String item : itemSet) {
     Set key = new HashSet();
     key.add(item.trim());
     if(!candFreq1ItemSetMap.containsKey(key)) {
      Integer value = 1;
      candFreq1ItemSetMap.put(key, value);
     }
     else {
      Integer value = 1+candFreq1ItemSetMap.get(key);
      candFreq1ItemSetMap.put(key, value);
     }
    }
   }
   return candFreq1ItemSetMap;
}

/**
* 根据频繁(k-1)-项集计算候选频繁k-项集
*
* @param m 其中m=k-1
* @param freqMItemSet 频繁(k-1)-项集
* @return
*/
public Set> aprioriGen(int m, Set> freqMItemSet) {
   Set> candFreqKItemSet = new HashSet>();
   Iterator> it = freqMItemSet.iterator();
   Set originalItemSet = null;
   while(it.hasNext()) {
    originalItemSet = it.next();
    Iterator> itr = this.getIterator(originalItemSet, freqMItemSet);
    while(itr.hasNext()) {
     Set identicalSet = new HashSet(); // 两个项集相同元素的集合(集合的交运算)    
     identicalSet.addAll(originalItemSet);
     Set set = itr.next();
     identicalSet.retainAll(set); // identicalSet中剩下的元素是identicalSet与set集合中公有的元素
     if(identicalSet.size() == m-1) { // (k-1)-项集中k-2个相同
      Set differentSet = new HashSet(); // 两个项集不同元素的集合(集合的差运算)
      differentSet.addAll(originalItemSet);
      differentSet.removeAll(set); // 因为有k-2个相同，则differentSet中一定剩下一个元素，即differentSet大小为1
      differentSet.addAll(set); // 构造候选k-项集的一个元素(set大小为k-1,differentSet大小为k)
      candFreqKItemSet.add(differentSet); // 加入候选k-项集集合
     }
    }
   }
   return candFreqKItemSet;
}

/**
* 根据一个频繁k-项集的元素(集合)，获取到频繁k-项集的从该元素开始的迭代器实例
* @param itemSet
* @param freqKItemSet 频繁k-项集
* @return
*/
private Iterator> getIterator(Set itemSet, Set> freqKItemSet) {
   Iterator> it = freqKItemSet.iterator();
   while(it.hasNext()) {
    if(itemSet.equals(it.next())) {
     break;
    }

   }
   return it;
}

/**
* 根据频繁(k-1)-项集，调用aprioriGen方法，计算频繁k-项集
*
* @param k
* @param freqMItemSet 频繁(k-1)-项集
* @return
*/
public Map, Float> getFreqKItemSet(int k, Set> freqMItemSet) {
   Map, Integer> candFreqKItemSetMap = new HashMap Integer>();
   // 调用aprioriGen方法，得到候选频繁k-项集
   Set> candFreqKItemSet = this.aprioriGen(k-1, freqMItemSet);

   // 扫描事务数据库
   Iterator>> it = txDatabase.entrySet().iterator();
   // 统计支持数
   while(it.hasNext()) {
    Map.Entry>> entry = it.next();
    Iterator> kit = candFreqKItemSet.iterator();
    while(kit.hasNext()) {
     Set kSet = kit.next();
     Set set = new HashSet();
     set.addAll(kSet);
     set.removeAll(entry.getValue()); // 候选频繁k-项集与事务数据库中元素做差元算
     if(set.isEmpty()) { // 如果拷贝set为空，支持数加1
      if(candFreqKItemSetMap.get(kSet) == null) {
       Integer value = 1;
       candFreqKItemSetMap.put(kSet, value);
      }
      else {
       Integer value = 1+candFreqKItemSetMap.get(kSet);
       candFreqKItemSetMap.put(kSet, value);
      }
     }
    }
   }  
   // 计算支持度，生成频繁k-项集，并返回
   return support(candFreqKItemSetMap);
}

/**
* 根据候选频繁k-项集，得到频繁k-项集
*
* @param candFreqKItemSetMap 候选k项集(包含支持计数)
*/
public Map, Float> support(Map, Integer> candFreqKItemSetMap) {
   Map, Float> freqKItemSetMap = new HashMap, Float>();
   Iterator, Integer>> it = candFreqKItemSetMap.entrySet().iterator();
   while(it.hasNext()) {
    Map.Entry, Integer> entry = it.next();
    // 计算支持度
    Float supportRate = new Float(entry.getValue().toString())/new Float(txDatabaseCount);
    if(supportRate> freqKItemSet = this.getFreq1ItemSet().keySet();
   freqItemSet.put(1, freqKItemSet);
   // 计算频繁k-项集(k>1)
   int k = 2;
   while(true) {
    Map, Float> freqKItemSetMap = this.getFreqKItemSet(k, freqKItemSet);
    if(!freqKItemSetMap.isEmpty()) {
     this.freqItemSet.put(k, freqKItemSetMap.keySet());
     freqKItemSet = freqKItemSetMap.keySet();
    }
    else {
     break;
    }
    k++;
   }
}

/**
* g>>>> it = freqItemSet.entrySet().iterator();
   while(it.hasNext()) {
    Map.Entry>> entry = it.next();
    for(Set itemSet : entry.getValue()) {
     // 对每个频繁项集进行关联规则的挖掘
     mine(itemSet);
    }
   }
}

/**
* 对从频繁项集集合freqItemSet中每迭代出一个频繁项集元素，执行一次关联规则的挖掘
* @param itemSet 频繁项集集合freqItemSet中的一个频繁项集元素
*/
public void mine(Set itemSet) {  
   int n = itemSet.size()/2; // 根据集合的对称性，只需要得到一半的真子集
   for(int i=1; i<=n; i++) {
    // 得到频繁项集元素itemSet的作为条件的真子集集合
    Set> properSubset = ProperSubsetCombination.getProperSubset(i, itemSet);
    // 对条件的真子集集合中的每个条件项集，获取到对应的结论项集，从而进一步挖掘频繁关联规则
    for(Set conditionSet : properSubset) {
     Set conclusionSet = new HashSet();
     conclusionSet.addAll(itemSet);
     conclusionSet.removeAll(conditionSet); // 删除条件中存在的频繁项
     confide(conditionSet, conclusionSet); // 调用计算置信度的方法，并且挖掘出频繁关联规则
    }
   }
}

/**
* 对得到的一个条件项集和对应的结论项集，计算该关联规则的支持计数，从而根据置信度判断是否是频繁关联规则
* @param conditionSet 条件频繁项集
* @param conclusionSet 结论频繁项集
*/
public void confide(Set conditionSet, Set conclusionSet) {
   // 扫描事务数据库
   IteratorString>>> it = txDatabase.entrySet().iterator();
   // 统计关联规则支持计数
   int conditionToConclusionCnt = 0; // 关联规则(条件项集推出结论项集)计数
   int conclusionToConditionCnt = 0; // 关联规则(结论项集推出条件项集)计数
   int supCnt = 0; // 关联规则支持计数
   while(it.hasNext()) {
    Map.Entry> entry = it.next();
    Set txSet = entry.getValue();
    Set set1 = new HashSet();
    Set set2 = new HashSet();
    set1.addAll(conditionSet);

    set1.removeAll(txSet); // 集合差运算：set-txSet
    if(set1.isEmpty()) { // 如果set为空，说明事务数据库中包含条件频繁项conditionSet
     // 计数
     conditionToConclusionCnt++;
    }
    set2.addAll(conclusionSet);
    set2.removeAll(txSet); // 集合差运算：set-txSet
    if(set2.isEmpty()) { // 如果set为空，说明事务数据库中包含结论频繁项conclusionSet
     // 计数
     conclusionToConditionCnt++;

    }
    if(set1.isEmpty() && set2.isEmpty()) {
     supCnt++;
    }
   }
   // 计算置信度
   Float conditionToConclusionConf = new Float(supCnt)/new Float(conditionToConclusionCnt);
   if(conditionToConclusionConf>=minConf) {
    if(assiciationRules.get(conditionSet) == null) { // 如果不存在以该条件频繁项集为条件的关联规则
     Set> conclusionSetSet = new HashSet>();
     conclusionSetSet.add(conclusionSet);
     assiciationRules.put(conditionSet, conclusionSetSet);
    }
    else {
     assiciationRules.get(conditionSet).add(conclusionSet);
    }
   }
   Float conclusionToConditionConf = new Float(supCnt)/new Float(conclusionToConditionCnt);
   if(conclusionToConditionConf>=minConf) {
    if(assiciationRules.get(conclusionSet) == null) { // 如果不存在以该结论频繁项集为条件的关联规则
     Set> conclusionSetSet = new HashSet>();
     conclusionSetSet.add(conditionSet);
     assiciationRules.put(conclusionSet, conclusionSetSet);
    }
    else {
     assiciationRules.get(conclusionSet).add(conditionSet);
    }
   }
}
/**
* 经过挖掘得到的频繁项集Map
*
* @return 挖掘得到的频繁项集集合
*/
public Map>> getFreqItemSet() {
   return freqItemSet;
}
/**
* 获取挖掘到的全部的频繁关联规则的集合
* @return 频繁关联规则集合
*/
public Map, Set>> getAssiciationRules() {
   return assiciationRules;
}
}
（二）辅助类
ProperSubsetCombination类是一个辅助类，在挖掘频繁关联规则的过程中，用于生成一个频繁项集元素的非空真子集，实现代码如下：
package org.shirdrn.datamining.association;
import java.util.BitSet;
import java.util.HashSet;
import java.util.Set;
/**

* 求频繁项集元素(集合)的非空真子集集合
* erSubset; // 真子集集合
/**
* 计算得到一个集合的非空真子集集合
*
* @param n 真子集的大小
* @param itemSet 一个频繁项集元素
* @return 非空真子集集合
*/
public static Set> getProperSubset(int n, Set itemSet) {
   String[] array = new String[itemSet.size()];
   ProperSubsetCombination.array = itemSet.toArray(array);
   properSubset = new HashSet>();
   startBitSet = new BitSet();
   endBitSet = new BitSet();
   // 初始化startBitSet，左侧占满1
   for (int i=0; i=array.length-n; i--) {
    endBitSet.set(i, true);
   }

   // 根据起始startBitSet，将一个组合加入到真子集集合中
   get(startBitSet);   

   while(!startBitSet.equals(endBitSet)) {
    int zeroCount = 0; // 统计遇到10后，左边0的个数
    int oneCount = 0; // 统计遇到10后，左边1的个数
    int pos = 0; // 记录当前遇到10的索引位置

    // 遍历startBitSet来确定10出现的位置
    for (int i=0; ik;
     }
    }
    // 将遇到10后，左侧的1全部移动到最左侧
    int counter = Math.min(zeroCount, oneCount);
    int startIndex = 0;
    int endIndex = 0;
    if(pos>1 && counter>0) {
     pos--;
     endIndex = pos;
     for (int i=0; itBitSet.set(endIndex, false);
      startIndex = i+1;
      pos--;
      if(pos>0) {
       endIndex = pos;
      }
     }
    }
    get(startBitSet);
   }  
   return properSubset;
}

/**
* 根据一次移位操作得到的startBitSet，得到一个真子集
* @param bitSet
*/
private static void get(BitSet bitSet) {
   Set set = new HashSet();
   for(int i=0; i
using namespace std;
#include
#include
include
#include
#include
#define debug(a) printf((a))
struct Item{
string item_name;//项目
Item *node_link; //节点链
Item *parent_link; //父节点链
map child_link; //孩子节点
int support_count; //支持度
};
void print(vector< vector > ssvec)
{
for(int ii=0;ii ss=ssvec[ii];
for(int jj=0;jjitem_name<<":"<support_count<<"] ";
cout<support_count!=b->support_count)
return a->support_count>b->support_count;
return a->item_nameitem_name;
}
#ifndef _PF_TREE_H
#define _PF_TREE_H
class PFTree{
map head_table;
void insert(Item * root,Item **vec,int curP,int maxSize,int );
public :
Item * root;
vector T;
int min_support;
void build_PFTree(vector< vector >);//建表
void init_head_table(vector< vector >);//建树
void build_PFTree(vector< vector >);//建表
void init_head_table(vector< vector >);//建树
vector< vector > generate_base_pattern(Item *);//生成基模式
bool is_signal_path(); //查看是否是单源树

void print_tree(Item *r);
void delte_all(Item *root);
void print_head_ta