Java实现FP-Growth算法代码示例

本篇文章小编给大家分享一下Java实现FP-Growth算法代码示例，文章代码介绍的很详细，小编觉得挺不错的，现在分享给大家供大家参考，有需要的小伙伴们可以来看看。

第一次扫描

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

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

我的实现思路

扫描原数据集将其保存在二维列表sourceData中

维护一个Table，使其保存每个item的全局支持度TotalSup

在Table中过滤掉低于阈值minSup的项

将Table转换为List，并使其按照TotalSup降序排序

新建一个二维列表freqSource，其保留sourceData中的频繁项，并将每个事务按全局支持度降序排序

代码

/**
     * 扫描原数据集,生成事务集
     * @param path 数据集路径
     * @throws IOException
     */

    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 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();
    }
        /**
     * 去除相似项表(similarSingleItemLinkedListHeadsTable)的非频繁项,并按全局支持度对similarSingleItemLinkedListHeads降序排序
     */
    private void deleteNonFreqInSSILLHTAndSort() {
        Hashtable copyOfSSILLHT =
                (Hashtable) similarSingleItemLinkedListHeadsTable.clone();
        Set keySet = copyOfSSILLHT.keySet();
        //删除非频繁项
        for(int key: keySet){
            if(similarSingleItemLinkedListHeadsTable.get(key).getSupTotal()(similarSingleItemLinkedListHeadsTable.values());
        similarSingleItemLinkedListHeadList.sort(new Comparator() {
            @Override
            public int compare(SimilarSingleItemLinkedListHead o1, SimilarSingleItemLinkedListHead o2) {
                return o2.getSupTotal() - o1.getSupTotal();
            }
        });

    }
        /**
     * 去除事务集(sourceDataSet)的非频繁项,并且按全局支持度对每个事务的item进行降序排序
     * 其结果保存在freqSourceSortedDataSet
     */
    private void deleteNonFreqInSDSAndSort(){
        freqSourceSortedDataSet = (ArrayList>) sourceDataSet.clone();
        for(int i =0;ie == 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树
     */
    private void buildFPTree(){
        for(ArrayListtrans: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) 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表示未找到
     */
    private int searchForItemInHeadsList(int item, ArrayList similarSingleItemLinkedListHeads) {
        for(int i =0;i

	挖掘频繁项集


	这一部分个人觉得是实现上最困难的部分。但是我在B站或其他地方一涉及到这个地方都讲得很快（B站也没两个视频讲这玩意儿，吐）。还有不同的概念，比如在黑皮书上讲的是前缀路径，在其他地方有条件模式基等概念。接下来的代码均按照前缀路径的说法来实现。


	我们来捋一捋思路，挖掘频繁项集需要干什么。


	首先需要从后向前遍历相似项链表的列表（这一列表已经在第一次扫描中按全局支持度排过序了）的每一项。


	对每一项递归地进行如下步骤：


	①记录前缀路径。我使用的方法是用一个HashSet记录前缀路径中出现的所有节点。


	②记录该FP树的每一item的支持度。类似于前面的第一次扫描。


	③根据记录的支持度，如果item频繁，则该item和当前的后缀为频繁项集。


	④再根据record构建该FP树的相似项链表列表，去除掉非频繁项（类似第一次扫描）和当前item构成条件FP树。这里并不需要重新建立一个FP树的结构来构成条件FP树，因为记录前缀路径只需要访问相似项和父项。


	⑤对相似项链表列表的剩余项再进行①步骤，直到相似项链表列表中没有项，为终止。

/**
     * 算法执行函数
     * @param minSupCnt 最小支持度计数
     * @param path 文件路径
     * @param pT 输出结果的项集大小阈值
     */
    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);
    }
/**
     * 生成频繁项集
     * @param last 最后项
     * @param fPTree 条件FP树
     * @param fatherSimilarSingleItemLinkedListHeads 父树的相似项头结点链表
     * @param freqItemSet 频繁项集
     */
    private void genFreqItemSet(int last,FPTree fPTree,
                                ListfatherSimilarSingleItemLinkedListHeads,TreeSetfreqItemSet) {

        FPTree conditionalFPTree = new FPTree();
        ListsimilarSingleItemLinkedListHeads = new ArrayList<>();

        TreeSetlocalFreqItemSet = (TreeSet) freqItemSet.clone();
        int index ;
        index = searchForItemInHeadsList(last,
                (ArrayList) fatherSimilarSingleItemLinkedListHeads);

        Node firstNode = fatherSimilarSingleItemLinkedListHeads.get(index).next;
        HashSetrecord = 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 supRecord = new Hashtable<>();
            record.forEach(new Consumer() {
                @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() {
                        @Override
                        public void accept(Integer integer) {
                            System.out.print(integer+" ");
                        }
                    });
                    result.add(localFreqItemSet);

                    System.out.println("");
                }
            }

            //构建相似项链表
            record.forEach(new Consumer() {
                @Override
                public void accept(Node node) {
                    if(node.item == -1){    //根节点
                        Node visitNode = node;
                        buildConditionalFPTree(conditionalFPTree.root, visitNode,record,
                                (ArrayList) similarSingleItemLinkedListHeads,supRecord,last);
                    }
                }
            });
            //按支持度降序排序
            similarSingleItemLinkedListHeads.sort(new Comparator() {
                @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);
                }
            }
        }
    }
/**
     * 递归构建条件FP树
     * @param rootNode 以该节点为根向下建立条件FP树
     * @param originalNode  rootNode对应在原树中的节点
     * @param record    前缀路径
     * @param similarSingleItemLinkedListHeads  相似项表头链表
     * @param supRecord 支持度计数的记录
     * @param last 最后项
     */
    private void buildConditionalFPTree(Node rootNode,Node originalNode,HashSetrecord
            ,ArrayListsimilarSingleItemLinkedListHeads,HashtablesupRecord,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);
                    }

                }
            }
        }
    }