?? gsp.java
字號:
package gsp;
import java.util.ArrayList;
import java.util.Map;
import java.util.HashMap;
/**
* <title>GSP算法實現類</title>
* 本類為核心類，在本類中實現了GSP算法
* @author guangqingzhong
*
*/
public class GSP {
private ArrayList<Sequence> c; //長度為i的候選序列模式
private ArrayList<Sequence> l; //長度為i的序列模式
private ArrayList<Sequence> result;
private SeqDB db;
private int support;
/**
* 構造方法
* 在實例化GSP對象時，同時賦值支持度
* 并獲取序列集和初始化序列模式結果
* @param support 支持度
*/
public GSP(int support) {
this.support = support; //賦值支持度
this.db = new SeqDB(); //從SeqDB類中獲取設置好的序列集
this.result = new ArrayList<Sequence>(); //初始化序列模式結果對象
}
/**
* 產生序列模式
* 核心方法，在該方法中調用連接和剪枝操作，并將最后獲得的序列模式放到result中
* @return 序列模式
*/
public ArrayList getSequences() {
long start = System.currentTimeMillis();
//調用初始化方法
initialize();
System.out.println("序列模式L(1) 為：" +l);
System.out.println(".................................................");
for (int i = 0; i < l.size(); i++) {
//產生進行連接操作后的候選集
genCandidate();
if (!(c.size() > 0)) {
break;
}
System.out.println("剪枝前候選集的大小為："+c.size()+" 候選集c為："+c);
//進行剪枝操作
pruneC();
System.out.println("剪枝后候選集的大小為："+c.size()+" 候選集c為："+c);
//產生序列模式
generateL();
System.out.println("序列模式L(" + (i + 2) + ") 為：" +l);
addToResult(l);
System.out.println(".................................................");
}
long end = System.currentTimeMillis();
System.out.println("計算花費時間" + (end - start) + "毫秒!");
return this.result;
}
/*
* 初始化方法
* 獲取設置好的序列集
*/
private void initialize() {
Map<Integer, Integer> can = new HashMap<Integer, Integer>();
//對于序列集中的所有序列
for (Sequence s : db.getSeqs()) {
//對于序列中的所有項目集
for (Element e : s.getElements()) {
//對于項目集中的所有項目
for (int i : e.getItems()) {
//比較項目的出現次數，并計數，用于與支持度比較
if (can.containsKey(i)) {
int count = can.get(i).intValue() + 1;
can.put(i, count);
} else {
can.put(i, 1);
}
}
}
}
this.l = new ArrayList<Sequence>();
//對于產生的候選集，如果支持度大于最小支持度閾值，則添加到序列模式L中
for (int i : can.keySet()) {
if (can.get(i).intValue() >= support) {
Element e = new Element(new int[] {i});
Sequence seq = new Sequence();
seq.addElement(e);
this.l.add(seq);
}
}
//將第一次頻繁序列模式加入結果集中
this.addToResult(l);
}
/*
* 產生經過連接操作后的候選集
*
*/
private void genCandidate() {
this.c = new ArrayList<Sequence>();
//對于種子集L進行連接操作
for (int i = 0; i < this.l.size(); i++) {
for (int j = i; j < this.l.size(); j++) {
this.joinAndInsert(l.get(i), l.get(j));
if (i != j) {
this.joinAndInsert(l.get(j), l.get(i));
}
}
}
}
/*
* 對種子集進行連接操作
*/
private void joinAndInsert(Sequence s1, Sequence s2) {
Sequence s, st;
//去除第一個元素
Element ef = s1.getElement(0).getWithoutFistItem();
//去除最后一個元素
Element ee = s2.getElement(s2.size() - 1).getWithoutLastItem();
int i = 0, j = 0;
if (ef.size() == 0) {
i++;
}
for (; i < s1.size() && j < s2.size(); i++, j++) {
Element e1, e2;
if (i == 0) {
e1 = ef;
} else {
e1 = s1.getElement(i);
}
if (j == s2.size() - 1) {
e2 = ee;
} else {
e2 = s2.getElement(j);
}
if (!e1.equalsTo(e2)) {
return;
}
} //end of for
s = new Sequence(s1);
//將s2的最后一個元素添加到s中
(s.getElement(s.size() - 1)).addItem(s2.getElement(s2.size() - 1).
getLastItem());
//如果候選集中沒有s，則添加到候選集
if (s.notInSeqs(c)) {
c.add(s);
}
st = new Sequence(s1);
//將s2的最后一個元素添加到st中
st.addElement(new Element(new int[] {s2.getElement(s2.size() - 1).
getLastItem()}));
//如果候選集中沒有st，則添加到候選集
if (st.notInSeqs(c)) {
c.add(st);
}
return;
}
/*
* 剪枝操作
* 看每個候選序列的連續子序列是不是頻繁序列
* 采用逐個取元素，只去其中一個項目，然后看是不是有相應的頻繁序列在l中。
* 如果元素只有一個項目，則去除該元素做相應判斷。
*/
private void pruneC() {
Sequence s;
//對于序列中的所有元素
for (int i = 0; i < this.c.size();i++) {
s = c.get(i);
//對于元素中的所有項目
for (int j = 0; j < s.size(); j++) {
Element ce = s.getElement(j);
boolean prune=false;
//只有一個元素的情況
if (ce.size() == 1) {
s.removeElement(j);
//如果子序列不是序列模式，則將它從候選序列模式中刪除，否則添加
if (s.notInSeqs(this.l)) {
prune=true;
}
s.insertElement(j, ce);
} else {
for (int k = 0; k < ce.size(); k++) {
int item=ce.removeItem(k);
//如果子序列不是序列模式，則將它從候選序列模式中刪除。否則添加
if (s.notInSeqs(this.l)) {
prune=true;
}
ce.addItem(item);
}
}
//如果剪枝，則將該序列刪除
if(prune){
c.remove(i);
i--;
break;
}
}
}
}
/*
* 生成序列模式L
* 用于已經經過連接和剪枝操作后的后選序列集
*/
private void generateL() {
this.l = new ArrayList<Sequence>();
for (Sequence s : db.getSeqs()) {
for (Sequence seq : this.c) {
if (seq.isSubsequenceOf(s)) {
//支持度計數
seq.incrementSupport();
}
}
}
for (Sequence seq : this.c) {
//大于最小支持度閾值的放到序列模式中
if (seq.getSupport() >= this.support) {
this.l.add(seq);
}
}
}
/*
* 將該頻繁序列模式加入結果中
*/
private void addToResult(ArrayList<Sequence> l) {
for (int i = 0; i < l.size(); i++) {
this.result.add(l.get(i));
}
}
/**
* 輸出輸入的序列信息
* 輸出需要進行序列模式分析的序列以及最小支持度（計數）
*/
public void outputInput() {
System.out.println("最小支持度計數為：" + this.support);
System.out.println("輸入的序列集合為：");
System.out.println(db.getSeqs());
System.out.println();
}
}
?? 快捷鍵說明
復制代碼
Ctrl + C
搜索代碼
Ctrl + F
全屏模式
F11
切換主題
Ctrl + Shift + D
顯示快捷鍵
?
增大字號
Ctrl + =
減小字號
Ctrl + -