最新下载
热门教程
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
Java实现FP-Growth算法代码示例
时间:2022-06-29 02:21:38 编辑:袖梨 来源:一聚教程网
本篇文章小编给大家分享一下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){ ArrayListtransaction = 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;i 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(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,TreeSet freqItemSet) { FPTree conditionalFPTree = new FPTree(); List similarSingleItemLinkedListHeads = new ArrayList<>(); TreeSet localFreqItemSet = (TreeSet ) freqItemSet.clone(); int index ; index = searchForItemInHeadsList(last, (ArrayList ) fatherSimilarSingleItemLinkedListHeads); Node firstNode = fatherSimilarSingleItemLinkedListHeads.get(index).next; HashSet 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 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,HashSet record ,ArrayList similarSingleItemLinkedListHeads,Hashtable 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); } } } } } 相关文章
- 《原神》5.2卡池抽取建议 11-14
- 《原神》5.2版本新怪物介绍 11-14
- 《原神》希诺宁增伤触发方法 11-14
- 《原神》循音觅奇活动入口 11-14
- 《原神》循音觅奇兑换码获取方法 11-14
- 《原神》花羽会活动飞行技巧介绍 11-14