자바 가 FP-Growth 알고리즘 을 어떻게 실현 하 는 지 상세 하 게 설명 합 니 다.
이 글 은 실현 에 중점 을 두 었 다.FP 트 리 를 구축 하기 위해 서 는 두 번 의 스 캔 이 필요 합 니 다.
첫 번 째 스 캔
첫 번 째 스 캔 은 최소 지지 도 에 만족 하지 않 는 모든 항목 을 걸 러 냅 니 다.최소 지원 도 를 만족 시 키 는 항목 에 대해 서 는 전역 지원 도 내림차 순 으로 정렬 합 니 다.
이 수요 에 따라 전역 지원 도 에 따라 모든 업무 의 item 을 정렬 하 는 것 이 어 려 울 수 있 습 니 다.
나의 실현 사고.
4
/**
* ,
* @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 트 리.
스 캔 에 참여 한 것 은 필터 후의 데이터 입 니 다.만약 에 데이터 항목 이 처음 만나면 이 노드 를 만 들 고 헤드 테이블 에 이 노드 를 가리 키 는 지침 을 추가 합 니 다.그렇지 않 으 면 경로 에 따라 해당 하 는 노드 를 찾 아 노드 정 보 를 수정 합 니 다.
여 기 는 필터,정렬 된 데이터 가 있 기 때문에 간단 합 니 다.우 리 는 단지
/**
* 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 역 이나 다른 곳 에서 이곳 과 관련 되면 모두 빨리 말한다.그리고 서로 다른 개념 도 있다.예 를 들 어 흑 피 책 에서 말 하 는 것 은 접두사 경로 이 고 다른 곳 에서 조건 부 모델 기반 등 개념 이 있다.다음 코드 는 모두 접두사 경로 에 따라 이 루어 집 니 다.
잦 은 항목 집 을 발굴 하려 면 무엇 을 해 야 할 지 생각 을 정리 해 보 자.
우선 비슷 한 목걸이 목록 을 뒤에서 옮 겨 다 녀 야 합 니 다.
각 항목 의 귀속 지 에 대해 다음 과 같은 절 차 를 진행한다.
① 접두사 경 로 를 기록한다.내 가 사용 하 는 방법 은 접두사 경로 에 나타 난 모든 노드 를 HashSet 로 기록 하 는 것 이다.
② 이 FP 트 리 의 항목 별 지지 도 를 기록 합 니 다.앞의 첫 번 째 스 캔 과 유사 합 니 다.
③ 기록 의 지지 도 에 따라 item 이 잦 으 면 이 item 과 현재 접 두 사 는 빈번 한 항목 집합 입 니 다.
④ record 에 따라 이 FP 트 리 의 비슷 한 목걸이 목록 을 구축 하여 비 빈번 항목(첫 번 째 스 캔 과 유사)과 현재 아 이 템 구성 조건 인 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
자바 가 FP-Growth 알고리즘 을 어떻게 실현 하 는 지 에 관 한 이 글 은 여기까지 소개 되 었 습 니 다.더 많은 자바 가 FP-growth 알고리즘 을 실현 하 는 내용 은 우리 의 이전 글 을 검색 하거나 아래 의 관련 글 을 계속 조회 하 시기 바 랍 니 다.앞으로 많은 응원 바 랍 니 다!
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
JPA + QueryDSL 계층형 댓글, 대댓글 구현(2)이번엔 전편에 이어서 계층형 댓글, 대댓글을 다시 리팩토링해볼 예정이다. 이전 게시글에서는 계층형 댓글, 대댓글을 구현은 되었지만 N+1 문제가 있었다. 이번에는 그 N+1 문제를 해결해 볼 것이다. 위의 로직은 이...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
