import java.util.ArrayList;
import java.util.Collections;
import java.util.HashSet;
import java.util.Iterator;
import java.util.LinkedHashMap;
import java.util.List;
import java.util.Map;
import java.util.Map.Entry;
import java.util.Set;
import org.slf4j.Logger;
import org.slf4j.LoggerFactory;
/**
*
* 功能描述：pefixspan序列模式挖掘算法,输入:序列集合,输出:最大频繁序列
* @created 2012-01-28 下午2:42:54
* @version 1.0.0
* @date 2012-01-28 下午2:42:54
*/
public class PrefixSpanBuild {
private static Logger log = LoggerFactory.getLogger(PrefixSpanBuild.class);
/**
* 序列集合
*/
private List
>> sequences = null;
/**
* 最大频繁序列
*/
private List> maxFrSeqs = new ArrayList>();
/**
* 单项集合
*/
private List itemList = new ArrayList();
/**
* 单项序列总和数
*/
private int total = 0;
/**
* 最小支持数(默认两个)
*/
private int minSup = 0;
/**
* 最小限制频繁序列元素数(默认两个)
*/
private int minFrElemSize = 0;
/**
* 最大限制频繁序列元素数(默认3个)
*/
private int maxFrElemSize = 0;
public PrefixSpanBuild(List>> seqs) {
this(seqs, 2, 2, 3);
}
public PrefixSpanBuild(List>> seqs, int minSup) {
this(seqs, minSup, 2, 3);
}
public PrefixSpanBuild(List>> seqs, int minSup, int minFrElemSize) {
this(seqs, minSup, minFrElemSize, 3);
}
public PrefixSpanBuild(List>> seqs, int minSup, int minFrElemSize,
int maxFrElemSize) {
// 最小项集必须小于或等于限制项集数
if (minFrElemSize <= maxFrElemSize) {
this.sequences = seqs;
this.minSup = minSup;
this.minFrElemSize = minFrElemSize;
this.maxFrElemSize = maxFrElemSize;
for (List> elem : this.sequences) {
for (List items : elem) {
for (String item : items) {
if (!itemList.contains(item)) {
itemList.add(item);
total++;
}
}
}
}
}
}
/**
*
* 功能描述：计算每个单项的支持数
* @return 每个单项的支持数
*/
protected Map countFr1() {
log.info("开始读取每个单项的支持数");
Map supMap = new LinkedHashMap();
// sup计算每个单项出现的次数(支持数)
Integer sup = 0;
Set itemsSet = null;
for (List> elem : sequences) {
for (List items : elem) {
itemsSet = new HashSet();
itemsSet.addAll(items);
for (String item : itemsSet) {
if (itemList.contains(item)) {
if (supMap.containsKey(item)) {
sup = supMap.get(item) + 1;
} else {
sup = 1;
}
supMap.put(item, sup);
}
}
}
}
for (Iterator> iter = supMap.entrySet().iterator(); iter.hasNext();) {
Entry supEntry = (Entry) iter.next();
sup = supEntry.getValue();
if (sup < minSup) {
iter.remove();
}
}
total = supMap.size();
log.info("读取完毕");
return supMap;
}
public List replace(List strList, String[] prefixSeq) {
List retainList = null;
int i = strList.size();
int length = prefixSeq.length;
int pla = strList.indexOf(prefixSeq[length - 1]);
if (pla >= 0 && pla < i - 1) {
retainList = new ArrayList();
if (length == 1) {
retainList.add("_");
} else {
for (int k = 0; k <= pla; k++) {
retainList.add("_");
}
}
retainList.addAll(strList.subList(pla + 1, i));
}
return retainList;
}
/**
*
* 功能描述：temp_s在其投影数据库中查找再次出现他的次数
* @param t_num 序列总数
* @param temps 序列
* @param sd[]投影数据库
* @param sd_count[]对应的索引
* @return int
*/
public int makeout(String temps, List>> sdSeqs) {
return makeout(new String[] { temps }, sdSeqs);
}
/**
*
* 功能描述：temp_s在其投影数据库中查找再次出现他的次数
* @param tempSeq 序列
* @param sdSeqs 投影数据库
*/
public int makeout(String[] tempSeq, List>> sdSeqs) {
String[] tempsSeqClone = tempSeq.clone();
int tMincout = 0;
for (List> sdElem : sdSeqs) {
for (List sdItems : sdElem) {
int n = -1;
n = containArrays(sdItems, tempsSeqClone);
if (n >= 0) {
tMincout++;
break;
}
}
}
return tMincout;
}
/**
*
* 功能描述：用PrefixSpan算法求出序列集的频繁序列
*/
protected void prefixSpan(String[] prefixSeq, List>> seqs, int prefixNum) {
// 如果前缀得出的子序列的长度大于maxFrElemSize,则直接跳出
if (prefixNum > this.maxFrElemSize - 1) {
return;
}
for (int tTotal = 0; tTotal < total; tTotal++) {
// 第一种情况a的投影数据库seqs,循环整个单项集合ItemList,看是否存在某个item在seqs上还存在频繁单项eg:
int supNum1 = 0;
String tempSeq = itemList.get(tTotal);
supNum1 = makeout(tempSeq, seqs);
if (supNum1 >= minSup) {
// 开始记录频繁序列
List itemList = new ArrayList();
if (prefixNum >= this.minFrElemSize - 1) {
for (int i = 0; i < prefixNum; i++) {
itemList.add(prefixSeq[i]);
}
itemList.add(tempSeq);
// 添加支持数
itemList.add(supNum1 + "");
// 添加置信度
itemList.add((float) supNum1 / seqs.size() + "");
maxFrSeqs.add(itemList);
}
List>> sdSeqs = generateSD(seqs, tempSeq);
String prefixSeq2[] = new String[prefixNum + 1];
for (int e = 0; e < prefixNum; e++)
prefixSeq2[e] = prefixSeq[e];
prefixSeq2[prefixNum] = tempSeq;
prefixSpan(prefixSeq2, sdSeqs, prefixNum + 1);
}
// 第二种情况a和ItemList的某个单项进行组合,看是否在seqs是还存在大于最小支持数的item eg:
int supNum2 = 0;
String tempSeq1 = prefixSeq[prefixNum - 1] + "," + itemList.get(tTotal);
String tempSeq1s[] = tempSeq1.split(",");
supNum2 = makeout(tempSeq1s, seqs);
if (supNum2 >= minSup) {
// 开始记录频繁序列
List itemList = new ArrayList();
if (prefixNum >= this.minFrElemSize) {
for (int i = 0; i < prefixNum - 1; i++) {
itemList.add(prefixSeq[i]);
}
itemList.add(tempSeq1);
// 添加支持数
itemList.add(supNum2 + "");
// 添加置信度
itemList.add((float) supNum2 / seqs.size() + "");
maxFrSeqs.add(itemList);
}
List>> sdSeqs = generateSD(seqs, tempSeq1s);
String aa[] = new String[prefixNum];
for (int e = 0; e < prefixNum - 1; e++)
aa[e] = prefixSeq[e];
aa[prefixNum - 1] = tempSeq1;
prefixSpan(aa, sdSeqs, prefixNum);
}
}
}
public List> buildPrefixSpan() {
Map supMap = this.countFr1();
int times = 0;
log.info("符合支持度为{},项集数为{}的总item数为{}", new Integer[] { minSup, minFrElemSize, total });
String itemId = null;
for (Entry supEntry : supMap.entrySet()) {
itemId = supEntry.getKey();
// 生成投影数据库
List>> sdList = this.generateSD(itemId);
String prefixSeq[] = { itemId };
this.prefixSpan(prefixSeq, sdList, 1);
times++;
log.info("执行到itemId-{},已经循环到{}", new String[] { prefixSeq[0], times + "" });
}
return this.maxFrSeqs;
}
public static void main(String[] args) {
String sequence[] = { "a", "a,b,c", "a,c", "d", "c,f", "a,d", "a,b,c", "a,d", "d,e", "e,f",
"a,b", "d,f", "c", "b", "e", "g", "a,f", "c", "b", "c" };
List>> sLists = new ArrayList>>();
List> e1 = new ArrayList>();
String e = null;
List items = null;
for (int i = 0; i < 5; i++) {
e = sequence[i];
if (e != null) {
items = new ArrayList();
for (String item : e.split(",")) {
items.add(item);
}
Collections.sort(items);
e1.add(items);
}
}
List> e2 = new ArrayList>();
for (int i = 5; i < 9; i++) {
e = sequence[i];
if (e != null) {
items = new ArrayList();
for (String item : e.split(",")) {
items.add(item);
}
Collections.sort(items);
e2.add(items);
}
}
List> e3 = new ArrayList>();
for (int i = 9; i < 14; i++) {
e = sequence[i];
if (e != null) {
items = new ArrayList();
for (String item : e.split(",")) {
items.add(item);
}
Collections.sort(items);
e3.add(items);
}
}
List> e4 = new ArrayList>();
for (int i = 14; i < 20; i++) {
e = sequence[i];
if (e != null) {
items = new ArrayList();
for (String item : e.split(",")) {
items.add(item);
}
Collections.sort(items);
e4.add(items);
}
}
sLists.add(e1);
sLists.add(e2);
sLists.add(e3);
sLists.add(e4);
PrefixSpanBuild test = new PrefixSpanBuild(sLists, 2, 2);
test.buildPrefixSpan();
System.out.println("序列数据库如下：");
for (List> elem : test.sequences) {
for (List item2s : elem) {
System.out.print(item2s);
System.out.print(" ");
}
System.out.println();
}
System.out.println("");
System.out.println("");
System.out.println("执行PrefixSpan算法，生成频繁序列模式结果如下：");
// System.out.println(tempti);
test.printMaxFrSeq();
}
public void printMaxFrSeq() {
StringBuffer tempStrBuf = null;
int seqSize = 0;
for (List sequence : maxFrSeqs) {
tempStrBuf = new StringBuffer();
seqSize = sequence.size();
tempStrBuf.append("<");
for (int i = 0; i < seqSize - 3; i++) {
String skuId = sequence.get(i);
tempStrBuf.append(skuId + " ");
}
tempStrBuf.append(sequence.get(seqSize - 3));
tempStrBuf.append(">");
tempStrBuf.append(" - " + sequence.get(seqSize - 2));
tempStrBuf.append(" - " + sequence.get(seqSize - 1));
log.info(((tempStrBuf.toString())));
}
}
/**
* 根据前缀生成投影数据库
* @param seqs 序列数据库S
*/
public List>> generateSD(List>> seqs, String prefixSeq) {
return generateSD(seqs, new String[] { prefixSeq });
}
/**
* 根据前缀生成投影数据库
* @param prefixSeq 前缀
*/
public List>> generateSD(String prefixSeq) {
return generateSD(sequences, new String[] { prefixSeq });
}
/**
* 根据前缀生成投影数据库
* @param seqs 序列数据库S
*/
public List>> generateSD(List>> seqs, String[] prefixSeq) {
List>> sdList = new ArrayList>>();
List retainItems = null;
List> sdElem = null;
List> retainsdElem = null;
for (List> elem : seqs) {
sdElem = new ArrayList>();
for (List item2s : elem) {
int n = containArrays(item2s, prefixSeq);
if (n >= 0) {
retainItems = replace(item2s, prefixSeq);
if (retainItems != null) {
sdElem.add(retainItems);
}
retainsdElem = elem.subList(elem.indexOf(item2s) + 1, elem.size());
if (!retainsdElem.isEmpty()) {
sdElem.addAll(retainsdElem);
}
break;
}
}
if (!sdElem.isEmpty()) {
sdList.add(sdElem);
}
}
return sdList;
}
/**
*
* 功能描述：判断字符串中的数据是否在特殊集合(序列)中包含 eg:items=[a,b,c] temps=[_,_,c]是存在的"_"为任意字符串
*/
public int containArrays(List items, String[] temps) {
int n = exitsArrays(items, temps);
// log.info("containArrays{},{},{}", new Object[] { items, temps, n });
if (n == -1 && temps.length > 1) {
String[] tempsClone = temps.clone();
for (int i = 0; i < tempsClone.length - 1; i++) {
tempsClone[i] = "_";
}
n = exitsArrays(items, tempsClone);
}
return n;
}
/**
*
* 功能描述：判断字符串中的数据是否在集合中存在
*/
public int exitsArrays(List items, String[] temps) {
int n = -1;
int length = temps.length;
int size = items.size();
if (size >= length) {
if (length == 1 && !items.contains("_")) {
n = items.indexOf(temps[0]);
}
if (length > 1) {
// 首先找到数组的第一个元素出现在集合中个位置
n = items.indexOf(temps[0]);
// 如果集合够长,且第一个存在
if (n + length <= size && n != -1) {
// 再按顺序找第二个到第N个
for (int i = 1; i < length; i++) {
if (!temps[i].equals(items.get(i + n))) {
n = -1;
break;
}
}
} else {
n = -1;
}
}
}
return n;
}
浙公网安备 33021202002483