Java如何實(shí)現(xiàn)FP-Growth算法

本篇內(nèi)容介紹了“Java如何實(shí)現(xiàn)FP-Growth算法”的有關(guān)知識(shí)，在實(shí)際案例的操作過程中，不少人都會(huì)遇到這樣的困境，接下來就讓小編帶領(lǐng)大家學(xué)習(xí)一下如何處理這些情況吧！希望大家仔細(xì)閱讀，能夠?qū)W有所成！

FP-Growth算法的Java實(shí)現(xiàn)

這篇文章重點(diǎn)講一下實(shí)現(xiàn)。需要兩次掃描來構(gòu)建FP樹

第一次掃描

第一次掃描，過濾掉所有不滿足最小支持度的項(xiàng)；對(duì)于滿足最小支持度的項(xiàng)，按照全局支持度降序排序。

按照這個(gè)需求，可能的難點(diǎn)為如何按照全局支持度對(duì)每個(gè)事務(wù)中的item排序。

我的實(shí)現(xiàn)思路

• 掃描原數(shù)據(jù)集將其保存在二維列表sourceData中

• 維護(hù)一個(gè)Table，使其保存每個(gè)item的全局支持度TotalSup

• 在Table中過濾掉低于閾值minSup的項(xiàng)

• 將Table轉(zhuǎn)換為L(zhǎng)ist，并使其按照TotalSup降序排序

• 新建一個(gè)二維列表freqSource，其保留sourceData中的頻繁項(xiàng)，并將每個(gè)事務(wù)按全局支持度降序排序

代碼

/**
     * 掃描原數(shù)據(jù)集,生成事務(wù)集
     * @param path 數(shù)據(jù)集路徑
     * @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<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{
                        //將該項(xiàng)的全局支持度+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();
    }
        /**
     * 去除相似項(xiàng)表(similarSingleItemLinkedListHeadsTable)的非頻繁項(xiàng),并按全局支持度對(duì)similarSingleItemLinkedListHeads降序排序
     */
    private void deleteNonFreqInSSILLHTAndSort() {
        Hashtable<Integer,SimilarSingleItemLinkedListHead> copyOfSSILLHT =
                (Hashtable<Integer, SimilarSingleItemLinkedListHead>) similarSingleItemLinkedListHeadsTable.clone();
        Set<Integer> keySet = copyOfSSILLHT.keySet();
        //刪除非頻繁項(xiàng)
        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();
            }
        });

    }
        /**
     * 去除事務(wù)集(sourceDataSet)的非頻繁項(xiàng),并且按全局支持度對(duì)每個(gè)事務(wù)的item進(jìn)行降序排序
     * 其結(jié)果保存在freqSourceSortedDataSet
     */
    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);
                // 由于此時(shí)SSILLHT里的項(xiàng)都是頻繁項(xiàng),只需要確定item是否存在在其中即可,存在即代表頻繁.
                if(visitSupTotal(item)==-1){
                    //將非頻繁項(xiàng)標(biāo)記為最小整數(shù)值
                    freqSourceSortedDataSet.get(i).set(j,Integer.MIN_VALUE);
                }
            }
            //將標(biāo)記的項(xiàng)移除.
            freqSourceSortedDataSet.get(i).removeIf(e->e == Integer.MIN_VALUE);
            insertSort(freqSourceSortedDataSet.get(i));
        }
        freqSourceSortedDataSet.removeIf(e->e.size() == 0);

    }

第二次掃描

第二次掃描，構(gòu)造FP樹。
參與掃描的是過濾后的數(shù)據(jù)，如果某個(gè)數(shù)據(jù)項(xiàng)是第一次遇到，則創(chuàng)建該節(jié)點(diǎn)，并在headTable中添加一個(gè)指向該節(jié)點(diǎn)的指針；否則按路徑找到該項(xiàng)對(duì)應(yīng)的節(jié)點(diǎn)，修改節(jié)點(diǎn)信息

這里比較簡(jiǎn)單，因?yàn)橐呀?jīng)有過濾、排序好的數(shù)據(jù)freqSourceSortedDataSet。我們只需要

• 遍歷freqSourceSortedDataSet的每一個(gè)事務(wù)trans，遍歷trans中的每一個(gè)item構(gòu)建FP樹和相似項(xiàng)鏈表

• 如果某item第一次遇到，則需要?jiǎng)?chuàng)建該節(jié)點(diǎn)并在相似項(xiàng)鏈表中鏈接它。

• 鏈表不用多說。

• 這里的FP樹的子節(jié)點(diǎn)是不定個(gè)數(shù)的，需要用特殊的數(shù)據(jù)結(jié)構(gòu)。我這里使用了HashTable

  /**
     * 構(gòu)建FP樹
     */
    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);
            }
        }
    }
    /**
     * 構(gòu)建相似項(xiàng)鏈表
     */
    private void buildSimilarSingleItemLinkedList(int item,Node curTreeNode){
        //找到該item在相似項(xiàng)鏈表中的位置

        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中搜索某項(xiàng)的位置
     * @param item 項(xiàng)
     * @param similarSingleItemLinkedListHeads 頭結(jié)點(diǎn)鏈表
     * @return 位置,-1表示未找到
     */
    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;
    }

挖掘頻繁項(xiàng)集

這一部分個(gè)人覺得是實(shí)現(xiàn)上最困難的部分。但是我在B站或其他地方一涉及到這個(gè)地方都講得很快（B站也沒兩個(gè)視頻講這玩意兒，吐）。還有不同的概念，比如在黑皮書上講的是前綴路徑，在其他地方有條件模式基等概念。接下來的代碼均按照前綴路徑的說法來實(shí)現(xiàn)。

我們來捋一捋思路，挖掘頻繁項(xiàng)集需要干什么。

首先需要從后向前遍歷相似項(xiàng)鏈表的列表（這一列表已經(jīng)在第一次掃描中按全局支持度排過序了）的每一項(xiàng)。

對(duì)每一項(xiàng)遞歸地進(jìn)行如下步驟：

①記錄前綴路徑。我使用的方法是用一個(gè)HashSet記錄前綴路徑中出現(xiàn)的所有節(jié)點(diǎn)。

②記錄該FP樹的每一item的支持度。類似于前面的第一次掃描。

③根據(jù)記錄的支持度，如果item頻繁，則該item和當(dāng)前的后綴為頻繁項(xiàng)集。

④再根據(jù)record構(gòu)建該FP樹的相似項(xiàng)鏈表列表，去除掉非頻繁項(xiàng)（類似第一次掃描）和當(dāng)前item構(gòu)成條件FP樹。這里并不需要重新建立一個(gè)FP樹的結(jié)構(gòu)來構(gòu)成條件FP樹，因?yàn)橛涗浨熬Y路徑只需要訪問相似項(xiàng)和父項(xiàng)。

⑤對(duì)相似項(xiàng)鏈表列表的剩余項(xiàng)再進(jìn)行①步驟，直到相似項(xiàng)鏈表列表中沒有項(xiàng)，為終止。

/**
     * 算法執(zhí)行函數(shù)
     * @param minSupCnt 最小支持度計(jì)數(shù)
     * @param path 文件路徑
     * @param pT 輸出結(jié)果的項(xiàng)集大小閾值
     */
    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("頻繁項(xiàng)集個(gè)數(shù):\t"+cntOfFreqSet);
    }
/**
     * 生成頻繁項(xiàng)集
     * @param last 最后項(xiàng)
     * @param fPTree 條件FP樹
     * @param fatherSimilarSingleItemLinkedListHeads 父樹的相似項(xiàng)頭結(jié)點(diǎn)鏈表
     * @param freqItemSet 頻繁項(xiàng)集
     */
    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<>();  //用于記錄前綴路徑上出現(xiàn)的節(jié)點(diǎn)
        //記錄前綴路徑
        if(firstNode!=null){
            record.add(firstNode);
            Node nodeToVisitFather = firstNode;
            Node nodeToVisitSimilar = firstNode;
            while (nodeToVisitSimilar!=null){
                nodeToVisitSimilar.supInCFP = nodeToVisitSimilar.sup;
                nodeToVisitFather = nodeToVisitSimilar;
                while (nodeToVisitFather!=null){
                    // 計(jì)算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 ){    //根節(jié)點(diǎn)
                        return;
                    }
                    if(supRecord.containsKey(item)){
                        supRecord.put(item,supRecord.get(item)+ node.supInCFP);
                    }else{
                        supRecord.put(item,node.supInCFP);
                    }

                }
            });
            //輸出結(jié)果
            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("");
                }
            }

            //構(gòu)建相似項(xiàng)鏈表
            record.forEach(new Consumer<Node>() {
                @Override
                public void accept(Node node) {
                    if(node.item == -1){    //根節(jié)點(diǎn)
                        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){
                //遞歸搜索頻繁項(xiàng)
                for(int i =similarSingleItemLinkedListHeads.size()-1;i>=0;i--){
                    genFreqItemSet(similarSingleItemLinkedListHeads.get(i).getItemValue(),
                            conditionalFPTree,similarSingleItemLinkedListHeads,localFreqItemSet);
                    // similarSingleItemLinkedListHeads.remove(i);
                }
            }
        }
    }
/**
     * 遞歸構(gòu)建條件FP樹
     * @param rootNode 以該節(jié)點(diǎn)為根向下建立條件FP樹
     * @param originalNode  rootNode對(duì)應(yīng)在原樹中的節(jié)點(diǎn)
     * @param record    前綴路徑
     * @param similarSingleItemLinkedListHeads  相似項(xiàng)表頭鏈表
     * @param supRecord 支持度計(jì)數(shù)的記錄
     * @param last 最后項(xiàng)
     */
    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的所有兒子節(jié)點(diǎn),檢查其是否在前綴路徑中
                Node tempNode = originalNode.children.get(key);
                if(record.contains(tempNode)){
                    Node addedNode = new Node(tempNode.item, tempNode.supInCFP);
                    if(last == key){    //去除last的所有節(jié)點(diǎn)
                        tempNode.supInCFP = 0;
                        continue;
                    }
                    if(supRecord.get(key)>=minSupCnt){
                        //addedNode 拷貝 tempNode除兒子節(jié)點(diǎn)外的屬性
                        addedNode.supInCFP = tempNode.supInCFP;
                        rootNode.children.put(tempNode.item, addedNode);
                        addedNode.father = rootNode;
                        //構(gòu)建相似項(xiàng)表
                        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);
                    }

                }
            }
        }
    }

“Java如何實(shí)現(xiàn)FP-Growth算法”的內(nèi)容就介紹到這里了，感謝大家的閱讀。如果想了解更多行業(yè)相關(guān)的知識(shí)可以關(guān)注億速云網(wǎng)站，小編將為大家輸出更多高質(zhì)量的實(shí)用文章！