FP-Growth算法的Java实现
这篇文章重点讲一下实现。需要两次扫描来构建FP树
第一次扫描
第一次扫描，过滤掉所有不满足最小支持度的项；对于满足最小支持度的项，按照全局支持度降序排序。
按照这个需求，可能的难点为如何按照全局支持度对每个事务中的item排序。
我的实现思路
- 扫描原数据集将其保存在二维列表sourceData中
- 维护一个Table，使其保存每个item的全局支持度TotalSup
- 在Table中过滤掉低于阈值minSup的项
- 将Table转换为List，并使其按照TotalSup降序排序
- 新建一个二维列表freqSource，其保留sourceData中的频繁项，并将每个事务按全局支持度降序排序
代码
private void scanDataSet(String path) throws IOException {
if(path.equals("")){
path = filePath;
}
FileReader fr = new FileReader(path);
BufferedReader bufferedReader = new BufferedReader(fr);
String str;
// int maxLength = 0;
while ( (str = bufferedReader.readLine())!=null){
ArrayList<Integer> transaction = new ArrayList<>();
String[] tempEntry ;
tempEntry = str.split(" ");
for(int i =0;i< tempEntry.length;i++){
if(!tempEntry[i].equals("")){
int itemValue = Integer.parseInt(tempEntry[i]);
transaction.add(itemValue);
if(!similarSingleItemLinkedListHeadsTable.containsKey(itemValue)){
similarSingleItemLinkedListHeadsTable.put(itemValue, new SimilarSingleItemLinkedListHead(itemValue,null,1));
}else{
//将该项的全局支持度+1
similarSingleItemLinkedListHeadsTable.get(itemValue).addSupTotal();
}
}
}
// if(tempEntry.length>maxLength){
// maxLength = tempEntry.length;
// }
sourceDataSet.add(transaction);
}
// System.out.println(maxLength);
deleteNonFreqInSSILLHTAndSort();
deleteNonFreqInSDSAndSort();
bufferedReader.close();
fr.close();
}
private void deleteNonFreqInSSILLHTAndSort() {
Hashtable<Integer,SimilarSingleItemLinkedListHead> copyOfSSILLHT =
(Hashtable<Integer, SimilarSingleItemLinkedListHead>) similarSingleItemLinkedListHeadsTable.clone();
Set<Integer> keySet = copyOfSSILLHT.keySet();
//删除非频繁项
for(int key: keySet){
if(similarSingleItemLinkedListHeadsTable.get(key).getSupTotal()<minSupCnt){//低于支持度阈值
similarSingleItemLinkedListHeadsTable.remove(key);
}
}
//按全局支持度排序
similarSingleItemLinkedListHeadList = new ArrayList<>(similarSingleItemLinkedListHeadsTable.values());
similarSingleItemLinkedListHeadList.sort(new Comparator<SimilarSingleItemLinkedListHead>() {
@Override
public int compare(SimilarSingleItemLinkedListHead o1, SimilarSingleItemLinkedListHead o2) {
return o2.getSupTotal() - o1.getSupTotal();
}
});
}
private void deleteNonFreqInSDSAndSort(){
freqSourceSortedDataSet = (ArrayList<ArrayList<Integer>>) sourceDataSet.clone();
for(int i =0;i<sourceDataSet.size();i++){
for(int j = 0;j<sourceDataSet.get(i).size();j++){
int item = sourceDataSet.get(i).get(j);
// 由于此时SSILLHT里的项都是频繁项,只需要确定item是否存在在其中即可,存在即代表频繁.
if(visitSupTotal(item)==-1){
//将非频繁项标记为最小整数值
freqSourceSortedDataSet.get(i).set(j,Integer.MIN_VALUE);
}
}
//将标记的项移除.
freqSourceSortedDataSet.get(i).removeIf(e->e == Integer.MIN_VALUE);
insertSort(freqSourceSortedDataSet.get(i));
}
freqSourceSortedDataSet.removeIf(e->e.size() == 0);
}
第二次扫描
第二次扫描，构造FP树。
参与扫描的是过滤后的数据，如果某个数据项是第一次遇到，则创建该节点，并在headTable中添加一个指向该节点的指针；否则按路径找到该项对应的节点，修改节点信息
这里比较简单，因为已经有过滤、排序好的数据freqSourceSortedDataSet。我们只需要
- 遍历freqSourceSortedDataSet的每一个事务trans，遍历trans中的每一个item构建FP树和相似项链表
- 如果某item第一次遇到，则需要创建该节点并在相似项链表中链接它。
- 链表不用多说。
- 这里的FP树的子节点是不定个数的，需要用特殊的数据结构。我这里使用了HashTable
private void buildFPTree(){
for(ArrayList<Integer>trans:freqSourceSortedDataSet){
Node curTreeNode = fpTree.root;
for(int item :trans){
if(!curTreeNode.children.containsKey(item)){
Node node = new Node(item,1);
curTreeNode.children.put(item,node);
node.father = curTreeNode;
buildSimilarSingleItemLinkedList(item,curTreeNode);
}else{
curTreeNode.children.get(item).sup++;
}
curTreeNode=curTreeNode.children.get(item);
}
}
}
private void buildSimilarSingleItemLinkedList(int item,Node curTreeNode){
//找到该item在相似项链表中的位置
int index = searchForItemInHeadsList(item,
(ArrayList<SimilarSingleItemLinkedListHead>) similarSingleItemLinkedListHeadList);
if(similarSingleItemLinkedListHeadList.get(index).next == null){
similarSingleItemLinkedListHeadList.get(index).next = curTreeNode.children.get(item);
}else{
Node visitNode = similarSingleItemLinkedListHeadList.get(index).next;
while (visitNode.nextSimilar!=null){
visitNode = visitNode.nextSimilar;
}
if(visitNode != curTreeNode.children.get(item))
visitNode.nextSimilar = curTreeNode.children.get(item);
}
}
private int searchForItemInHeadsList(int item, ArrayList<SimilarSingleItemLinkedListHead> similarSingleItemLinkedListHeads) {
for(int i =0;i<similarSingleItemLinkedListHeads.size();i++){
if(similarSingleItemLinkedListHeads.get(i).getItemValue() == item){
return i;
}
}
return -1;
}
挖掘频繁项集
这一部分个人觉得是实现上最困难的部分。但是我在B站或其他地方一涉及到这个地方都讲得很快（B站也没两个视频讲这玩意儿，吐）。还有不同的概念，比如在黑皮书上讲的是前缀路径，在其他地方有条件模式基等概念。接下来的代码均按照前缀路径的说法来实现。
我们来捋一捋思路，挖掘频繁项集需要干什么。
首先需要从后向前遍历相似项链表的列表（这一列表已经在第一次扫描中按全局支持度排过序了）的每一项。
对每一项递归地进行如下步骤：
①记录前缀路径。我使用的方法是用一个HashSet记录前缀路径中出现的所有节点。
②记录该FP树的每一item的支持度。类似于前面的第一次扫描。
③根据记录的支持度，如果item频繁，则该item和当前的后缀为频繁项集。
④再根据record构建该FP树的相似项链表列表，去除掉非频繁项（类似第一次扫描）和当前item构成条件FP树。这里并不需要重新建立一个FP树的结构来构成条件FP树，因为记录前缀路径只需要访问相似项和父项。
⑤对相似项链表列表的剩余项再进行①步骤，直到相似项链表列表中没有项，为终止。
public void run(int minSupCnt,String path,int pT) throws IOException {
this.printThreshold = pT;
this.minSupCnt = minSupCnt;
scanDataSet(path);
buildFPTree();
for(int i = similarSingleItemLinkedListHeadList.size()-1;i>=0;i--){
genFreqItemSet(similarSingleItemLinkedListHeadList.get(i).getItemValue()
,fpTree,similarSingleItemLinkedListHeadList,new TreeSet<>());
}
//genFreqItemSet(14,fpTree,similarSingleItemLinkedListHeadList,new TreeSet<>());
System.out.println("频繁项集个数:\t"+cntOfFreqSet);
}
private void genFreqItemSet(int last,FPTree fPTree,
List<SimilarSingleItemLinkedListHead>fatherSimilarSingleItemLinkedListHeads,TreeSet<Integer>freqItemSet) {
FPTree conditionalFPTree = new FPTree();
List<SimilarSingleItemLinkedListHead>similarSingleItemLinkedListHeads = new ArrayList<>();
TreeSet<Integer>localFreqItemSet = (TreeSet<Integer>) freqItemSet.clone();
int index ;
index = searchForItemInHeadsList(last,
(ArrayList<SimilarSingleItemLinkedListHead>) fatherSimilarSingleItemLinkedListHeads);
Node firstNode = fatherSimilarSingleItemLinkedListHeads.get(index).next;
HashSet<Node>record = new HashSet<>(); //用于记录前缀路径上出现的节点
//记录前缀路径
if(firstNode!=null){
record.add(firstNode);
Node nodeToVisitFather = firstNode;
Node nodeToVisitSimilar = firstNode;
while (nodeToVisitSimilar!=null){
nodeToVisitSimilar.supInCFP = nodeToVisitSimilar.sup;
nodeToVisitFather = nodeToVisitSimilar;
while (nodeToVisitFather!=null){
// 计算supInCFT
if(nodeToVisitFather!=nodeToVisitSimilar)
nodeToVisitFather.supInCFP += nodeToVisitSimilar.supInCFP;
record.add(nodeToVisitFather);
nodeToVisitFather = nodeToVisitFather.father;
}
nodeToVisitSimilar = nodeToVisitSimilar.nextSimilar;
}
//记录在子树中的支持度
Hashtable<Integer,Integer> supRecord = new Hashtable<>();
record.forEach(new Consumer<Node>() {
@Override
public void accept(Node node) {
int item = node.item;
if(item == -1 ){ //根节点
return;
}
if(supRecord.containsKey(item)){
supRecord.put(item,supRecord.get(item)+ node.supInCFP);
}else{
supRecord.put(item,node.supInCFP);
}
}
});
//输出结果
if(supRecord.get(last)>=minSupCnt){
localFreqItemSet.add(last);
if(localFreqItemSet.size()>=printThreshold && !result.contains(localFreqItemSet)){
cntOfFreqSet++;
// for(int i = localFreqItemSet.size()-1;i>=0;i--){
// System.out.print(localFreqItemSet.get(i)+" ");
// }
localFreqItemSet.forEach(new Consumer<Integer>() {
@Override
public void accept(Integer integer) {
System.out.print(integer+" ");
}
});
result.add(localFreqItemSet);
System.out.println("");
}
}
//构建相似项链表
record.forEach(new Consumer<Node>() {
@Override
public void accept(Node node) {
if(node.item == -1){ //根节点
Node visitNode = node;
buildConditionalFPTree(conditionalFPTree.root, visitNode,record,
(ArrayList<SimilarSingleItemLinkedListHead>) similarSingleItemLinkedListHeads,supRecord,last);
}
}
});
//按支持度降序排序
similarSingleItemLinkedListHeads.sort(new Comparator<SimilarSingleItemLinkedListHead>() {
@Override
public int compare(SimilarSingleItemLinkedListHead o1, SimilarSingleItemLinkedListHead o2) {
return o2.getSupTotal() - o1.getSupTotal();
}
});
if(similarSingleItemLinkedListHeads.size()>=1){
//递归搜索频繁项
for(int i =similarSingleItemLinkedListHeads.size()-1;i>=0;i--){
genFreqItemSet(similarSingleItemLinkedListHeads.get(i).getItemValue(),
conditionalFPTree,similarSingleItemLinkedListHeads,localFreqItemSet);
// similarSingleItemLinkedListHeads.remove(i);
}
}
}
}
private void buildConditionalFPTree(Node rootNode,Node originalNode,HashSet<Node>record
,ArrayList<SimilarSingleItemLinkedListHead>similarSingleItemLinkedListHeads,Hashtable<Integer,Integer>supRecord,int last){
if(originalNode.children!=null){
for(int key:originalNode.children.keySet()){ //遍历originalNode的所有儿子节点,检查其是否在前缀路径中
Node tempNode = originalNode.children.get(key);
if(record.contains(tempNode)){
Node addedNode = new Node(tempNode.item, tempNode.supInCFP);
if(last == key){ //去除last的所有节点
tempNode.supInCFP = 0;
continue;
}
if(supRecord.get(key)>=minSupCnt){
//addedNode 拷贝 tempNode除儿子节点外的属性
addedNode.supInCFP = tempNode.supInCFP;
rootNode.children.put(tempNode.item, addedNode);
addedNode.father = rootNode;
//构建相似项表
int i = searchForItemInHeadsList(tempNode.item,similarSingleItemLinkedListHeads);
if(i==-1){
similarSingleItemLinkedListHeads.add(new SimilarSingleItemLinkedListHead(key,addedNode, addedNode.supInCFP));
}else{
similarSingleItemLinkedListHeads.get(i).setSupTotal(similarSingleItemLinkedListHeads.get(i).getSupTotal()+addedNode.supInCFP);
Node visitNode = similarSingleItemLinkedListHeads.get(i).next;
while (visitNode.nextSimilar!=null){
visitNode = visitNode.nextSimilar;
}
if(visitNode!=addedNode){
visitNode.nextSimilar= addedNode;
}
}
buildConditionalFPTree(addedNode,originalNode.children.get(key),record,similarSingleItemLinkedListHeads,supRecord,last);
addedNode.supInCFP = 0; //将supInCFP重置为0;
}else{
buildConditionalFPTree(rootNode,originalNode.children.get(key),record,similarSingleItemLinkedListHeads,supRecord,last);
}
}
}
}
}
完整代码
FP-Growth
到此这篇关于详解Java如何实现FP-Growth算法的文章就介绍到这了,更多相关Java实现FP-Growth算法内容请搜索编程网以前的文章或继续浏览下面的相关文章希望大家以后多多支持编程网！
