FP-Growth算法的Java实现+具体实现思路+代码

2022-08-11 12:55:53

前言

学校里的实验，要求实现FP-Growth算法。FP-Growth算法比Apriori算法快很多。
在网上搜索后发现Java实现的FP-Growth算法很少，且大多数不太能理解):太菜。所以就自己实现了一下。这篇文章重点介绍一下我的Java实现。

FP-Growth算法原理

其他大佬的讲解
FP-Growth算法详解

FP-Growth算法的Java实现

这篇文章重点讲一下实现。
如果看了上述给的讲解，可知，需要两次扫描来构建FP树

第一次扫描

第一次扫描，过滤掉所有不满足最小支持度的项；对于满足最小支持度的项，按照全局支持度降序排序。

按照这个需求，可能的难点为如何按照全局支持度对每个事务中的item排序。
我的实现思路

  • 扫描原数据集将其保存在二维列表sourceData中
  • 维护一个Table，使其保存每个item的全局支持度TotalSup
  • 在Table中过滤掉低于阈值minSup的项
  • 将Table转换为List，并使其按照TotalSup降序排序
  • 新建一个二维列表freqSource，其保留sourceData中的频繁项，并将每个事务按全局支持度降序排序

代码

/**
     * 扫描原数据集,生成事务集
     * @param path 数据集路径
     * @throws IOException
     */privatevoidscanDataSet(String path)throws IOException{if(path.equals("")){
            path= filePath;}
        FileReader fr=newFileReader(path);
        BufferedReader bufferedReader=newBufferedReader(fr);
        String str;//        int maxLength = 0;while((str= bufferedReader.readLine())!=null){
            ArrayList<Integer> transaction=newArrayList<>();
            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,newSimilarSingleItemLinkedListHead(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();}/**
     * 去除相似项表(similarSingleItemLinkedListHeadsTable)的非频繁项,并按全局支持度对similarSingleItemLinkedListHeads降序排序
     */privatevoiddeleteNonFreqInSSILLHTAndSort(){
        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=newArrayList<>(similarSingleItemLinkedListHeadsTable.values());
        similarSingleItemLinkedListHeadList.sort(newComparator<SimilarSingleItemLinkedListHead>(){@Overridepublicintcompare(SimilarSingleItemLinkedListHead o1, SimilarSingleItemLinkedListHead o2){return o2.getSupTotal()- o1.getSupTotal();}});}/**
     * 去除事务集(sourceDataSet)的非频繁项,并且按全局支持度对每个事务的item进行降序排序
     * 其结果保存在freqSourceSortedDataSet
     */privatevoiddeleteNonFreqInSDSAndSort(){
        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
/**
     * 构建FP树
     */privatevoidbuildFPTree(){for(ArrayList<Integer>trans:freqSourceSortedDataSet){
            Node curTreeNode= fpTree.root;for(int item:trans){if(!curTreeNode.children.containsKey(item)){
                    Node node=newNode(item,1);
                    curTreeNode.children.put(item,node);
                    node.father= curTreeNode;buildSimilarSingleItemLinkedList(item,curTreeNode);}else{
                    curTreeNode.children.get(item).sup++;}
                curTreeNode=curTreeNode.children.get(item);}}}/**
     * 构建相似项链表
     */privatevoidbuildSimilarSingleItemLinkedList(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);}}/**
     * 在HeadList中搜索某项的位置
     * @param item 项
     * @param similarSingleItemLinkedListHeads 头结点链表
     * @return 位置,-1表示未找到
     */privateintsearchForItemInHeadsList(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树，因为记录前缀路径只需要访问相似项和父项。
    ⑤对相似项链表列表的剩余项再进行①步骤，直到相似项链表列表中没有项，为终止。
/**
     * 算法执行函数
     * @param minSupCnt 最小支持度计数
     * @param path 文件路径
     * @param pT 输出结果的项集大小阈值
     */publicvoidrun(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,newTreeSet<>());}//genFreqItemSet(14,fpTree,similarSingleItemLinkedListHeadList,new TreeSet<>());
        System.out.println("频繁项集个数:\t"+cntOfFreqSet);}/**
     * 生成频繁项集
     * @param last 最后项
     * @param fPTree 条件FP树
     * @param fatherSimilarSingleItemLinkedListHeads 父树的相似项头结点链表
     * @param freqItemSet 频繁项集
     */privatevoidgenFreqItemSet(int last,FPTree fPTree,
                                List<SimilarSingleItemLinkedListHead>fatherSimilarSingleItemLinkedListHeads,TreeSet<Integer>freqItemSet){

        FPTree conditionalFPTree=newFPTree();
        List<SimilarSingleItemLinkedListHead>similarSingleItemLinkedListHeads=newArrayList<>();

        TreeSet<Integer>localFreqItemSet=(TreeSet<Integer>) freqItemSet.clone();int index;
        index=searchForItemInHeadsList(last,(ArrayList<SimilarSingleItemLinkedListHead>) fatherSimilarSingleItemLinkedListHeads);

        Node firstNode= fatherSimilarSingleItemLinkedListHeads.get(index).next;
        HashSet<Node>record=newHashSet<>();//用于记录前缀路径上出现的节点//记录前缀路径if(firstNode!=null){
            record.add(firstNode);
            Node nodeToVisitFather= firstNode;
            Node nodeToVisitSimilar= firstNode;while(nodeToVisitSimilar!=null){
                nodeToVisitSimilar.supInCFP= nodeToVisitSimilar.sup;
                nodeToVisitFather= nodeToVisitSimilar;while(nodeToVisitFather!=null){// 计算supInCFTif(nodeToVisitFather!=nodeToVisitSimilar)
                        nodeToVisitFather.supInCFP+= nodeToVisitSimilar.supInCFP;
                    record.add(nodeToVisitFather);
                    nodeToVisitFather= nodeToVisitFather.father;}
                nodeToVisitSimilar= nodeToVisitSimilar.nextSimilar;}//记录在子树中的支持度
            Hashtable<Integer,Integer> supRecord=newHashtable<>();
            record.forEach(newConsumer<Node>(){@Overridepublicvoidaccept(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(newConsumer<Integer>(){@Overridepublicvoidaccept(Integer integer){
                            System.out.print(integer+" ");}});
                    result.add(localFreqItemSet);

                    System.out.println("");}}//构建相似项链表
            record.forEach(newConsumer<Node>(){@Overridepublicvoidaccept(Node node){if(node.item==-1){//根节点
                        Node visitNode= node;buildConditionalFPTree(conditionalFPTree.root, visitNode,record,(ArrayList<SimilarSingleItemLinkedListHead>) similarSingleItemLinkedListHeads,supRecord,last);}}});//按支持度降序排序
            similarSingleItemLinkedListHeads.sort(newComparator<SimilarSingleItemLinkedListHead>(){@Overridepublicintcompare(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);}}}}/**
     * 递归构建条件FP树
     * @param rootNode 以该节点为根向下建立条件FP树
     * @param originalNode  rootNode对应在原树中的节点
     * @param record    前缀路径
     * @param similarSingleItemLinkedListHeads  相似项表头链表
     * @param supRecord 支持度计数的记录
     * @param last 最后项
     */privatevoidbuildConditionalFPTree(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=newNode(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(newSimilarSingleItemLinkedListHead(key,addedNode, addedNode.supInCFP))
  • 作者：Kidca
  • 原文链接：https://blog.csdn.net/Kidca/article/details/117914837
    更新时间：2022-08-11 12:55:53