详解Java如何实现FP

详解Java如何实现FP

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 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 copyOfSSILLHT =

(Hashtable) similarSingleItemLinkedListHeadsTable.clone();

Set keySet = copyOfSSILLHT.keySet();

//删除非频繁项

for(int key: keySet){

if(similarSingleItemLinkedListHeadsTable.get(key).getSupTotal()

similarSingleItemLinkedListHeadsTable.remove(key);

}

}

//按全局支持度排序

similarSingleItemLinkedListHeadList = new ArrayList<>(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

for(int j = 0;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树。

参与扫描的是过滤后的数据，如果某个数据项是第一http://次遇到，则创建该节点，并在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

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,

ListfatherSimilarSingleItemLinkedListHeads,TreeSetfreqItemSet) {

FPTree conditionalFPTree = new FPTree();

ListsimilarSingleItemLinkedListHeads = new ArrayList<>();

TreeSetlocalFreqItemSet = (TreeSet) freqItemSet.clone();

int index ;

index = searchForItemInHeadsList(last,

(ArrayList) fatherSimilarSingleItemLinkedListHeads);

Node firstNode = fatherSimilarSingleItemLinkedListHeads.get(index).next;

HashSetrecord = 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);

}

}

http:// });

//输出结果

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){ //根节点

http:// 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,HashSetrecord

,ArrayListsimilarSingleItemLinkedListHeads,HashtablesupRecord,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

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。