詳解Java如何實現FP-Growth算法
FP-Growth算法的Java實現
這篇文章重點講一下實現。需要兩次掃描來構建FP樹
第一次掃描
第一次掃描,過濾掉所有不滿足最小支持度的項;對於滿足最小支持度的項,按照全局支持度降序排序。
按照這個需求,可能的難點為如何按照全局支持度對每個事務中的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<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(); } /** * 去除相似項表(similarSingleItemLinkedListHeadsTable)的非頻繁項,並按全局支持度對similarSingleItemLinkedListHeads降序排序 */ 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(); } }); } /** * 去除事務集(sourceDataSet)的非頻繁項,並且按全局支持度對每個事務的item進行降序排序 * 其結果保存在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); // 由於此時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樹 */ 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); } } /** * 在HeadList中搜索某項的位置 * @param item 項 * @param similarSingleItemLinkedListHeads 頭結點鏈表 * @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; }
挖掘頻繁項集
這一部分個人覺得是實現上最困難的部分。但是我在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, 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); } } } } /** * 遞歸構建條件FP樹 * @param rootNode 以該節點為根向下建立條件FP樹 * @param originalNode rootNode對應在原樹中的節點 * @param record 前綴路徑 * @param similarSingleItemLinkedListHeads 相似項表頭鏈表 * @param supRecord 支持度計數的記錄 * @param last 最後項 */ 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算法內容請搜索WalkonNet以前的文章或繼續瀏覽下面的相關文章希望大傢以後多多支持WalkonNet!
推薦閱讀:
- vue中的el-tree @node-click傳自定義參數
- java數據結構實現雙向鏈表功能
- 詳解Java實現拓撲排序算法
- Java ArrayList與LinkedList使用方法詳解
- java數據結構基礎:單,雙向鏈表