目錄FP-Growth算法的Java實(shí)現(xiàn)第一次掃描代碼第二次掃描挖掘頻繁項(xiàng)集總結(jié)FP-Growth算法原理

其他大佬的講解

FP-Growth算法詳解

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)的全局支持度+1similarSingleItemLinkedListHeadsTable.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>() {@Overridepublic 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>() {@Overridepublic void accept(Integer integer) { System.out.print(integer+' ');} }); result.add(localFreqItemSet); System.out.println('');} } //構(gòu)建相似項(xiàng)鏈表 record.forEach(new Consumer<Node>() {@Overridepublic 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>() {@Overridepublic 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); }} }} }總結(jié)

這篇文章就到這里，希望能給你帶來幫助，也希望你可以多多關(guān)注好吧啦網(wǎng)的其他精彩內(nèi)容！