FP-Growth算法的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 */ 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{//将该项的全局支持度+1similarSingleItemLinkedListHeadsTable.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>() {@Overridepublic 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>() {@Overridepublic void accept(Integer integer) { System.out.print(integer+' ');} }); result.add(localFreqItemSet); System.out.println('');} } //构建相似项链表 record.forEach(new Consumer<Node>() {@Overridepublic 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>() {@Overridepublic 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); }} }} }总结

这篇文章就到这里，希望能给你带来帮助，也希望你可以多多关注好吧啦网的其他精彩内容！