詳解Java如何實(shí)現(xiàn)FP-Growth算法
更新時(shí)間：2021年06月22日 14:32:37 作者：Kidca
學(xué)校里的實(shí)驗(yàn),要求實(shí)現(xiàn)FP-Growth算法.FP-Growth算法比Apriori算法快很多（但是卻比不上時(shí)間）在網(wǎng)上搜索后發(fā)現(xiàn)Java實(shí)現(xiàn)的FP-Growth算法很少,且大多數(shù)不太能理解):太菜.所以就自己實(shí)現(xiàn)了一下.這篇文章重點(diǎn)介紹一下我的Java實(shí)現(xiàn)
,需要的朋友可以參考下
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)的全局支持度+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();
}
/**
* 去除相似項(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>() {
@Override
public 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>() {
@Override
public void accept(Integer integer) {
System.out.print(integer+" ");
}
});
result.add(localFreqItemSet);
System.out.println("");
}
}
//構(gòu)建相似項(xiàng)鏈表
record.forEach(new Consumer<Node>() {
@Override
public 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>() {
@Override
public 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);
}
}
}
}
}
完整代碼
到此這篇關(guān)于詳解Java如何實(shí)現(xiàn)FP-Growth算法的文章就介紹到這了,更多相關(guān)Java實(shí)現(xiàn)FP-Growth算法內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！
相關(guān)文章
idea創(chuàng)建maven項(xiàng)目速度慢的三種解決方案
這篇文章主要介紹了idea創(chuàng)建maven項(xiàng)目速度慢的三種解決方案，小編覺得挺不錯(cuò)的，現(xiàn)在分享給大家，也給大家做個(gè)參考。一起跟隨小編過來看看吧2019-01-01
這篇文章主要介紹了Java之springcloud Sentinel案例講解,本篇文章通過簡(jiǎn)要的案例,講解了該項(xiàng)技術(shù)的了解與使用,以下就是詳細(xì)內(nèi)容,需要的朋友可以參考下2021-08-08
這篇文章主要介紹了Java編程使用箱式布局管理器,結(jié)合實(shí)例形式分析了基于swing組件的箱式布局管理器定義與使用技巧,需要的朋友可以參考下2018-01-01
SpringBoot集成Spring Security用JWT令牌實(shí)現(xiàn)登錄和鑒權(quán)的方法
這篇文章主要介紹了SpringBoot集成Spring Security用JWT令牌實(shí)現(xiàn)登錄和鑒權(quán)的方法，文中通過示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2020-05-05
Java畢業(yè)設(shè)計(jì)實(shí)戰(zhàn)之在線蛋糕銷售商城的實(shí)現(xiàn)
這是一個(gè)使用了java+JSP+Springboot+maven+mysql+ThymeLeaf+FTP開發(fā)的在線蛋糕銷售商城，是一個(gè)畢業(yè)設(shè)計(jì)的實(shí)戰(zhàn)練習(xí)，具有線上蛋糕商城該有的所有功能，感興趣的朋友快來看看吧2022-01-01
Spring?4.0版本中更新了很多新功能，其中比較重要的一個(gè)就是對(duì)帶泛型的Bean進(jìn)行依賴注入的支持。本文將通過實(shí)例詳細(xì)講講Spring如何實(shí)現(xiàn)泛型注入，需要的可以參考一下2022-07-07
volatile這個(gè)關(guān)鍵字可能很多朋友都聽說過，或許也都用過。在Java 5之前，它是一個(gè)備受爭(zhēng)議的關(guān)鍵字，因?yàn)樵诔绦蛑惺褂盟鶗?huì)導(dǎo)致出人意料的結(jié)果。在Java 5之后，volatile關(guān)鍵字才得以重獲生機(jī)2021-11-11
SSM框架是spring MVC ，spring和mybatis框架的整合，是標(biāo)準(zhǔn)的MVC模式，將整個(gè)系統(tǒng)劃分為表現(xiàn)層，controller層，service層，DAO層四層，使用spring MVC負(fù)責(zé)請(qǐng)求的轉(zhuǎn)發(fā)和視圖管理，spring實(shí)現(xiàn)業(yè)務(wù)對(duì)象管理，mybatis作為數(shù)據(jù)對(duì)象的持久化引擎2021-10-10
Spring?component-scan?XML配置與@ComponentScan注解配置
這篇文章主要介紹了Spring?component-scan?XML配置與@ComponentScan注解配置，文章圍繞主題展開詳細(xì)的內(nèi)容介紹，具有一定的參考價(jià)值，需要的小伙伴可以參考一下2022-09-09
Java應(yīng)用程序開發(fā)學(xué)習(xí)之static關(guān)鍵字應(yīng)用
今天小編就為大家分享一篇關(guān)于Java應(yīng)用程序開發(fā)學(xué)習(xí)之static關(guān)鍵字應(yīng)用，小編覺得內(nèi)容挺不錯(cuò)的，現(xiàn)在分享給大家，具有很好的參考價(jià)值，需要的朋友一起跟隨小編來看看吧2018-12-12