Apriori算法Java实现示例(二)
, curItemSets);
preItemSetSize = curItemSetSize;
preItemSets = curItemSets;
}
return ret;
}
/**
* 扫描事务集以确定频繁1项集
*/
static Set findFrequentOneItemSets(Iterator> trans,
int MSF) {
// 扫描事务集以确定各个项出现的频次
Map frequences = new HashMap();
while (trans.hasNext()) {
Set tran = trans.next();
for (String item : tran) {
Integer frequence = frequences.get(item);
frequence = frequence == null 1 : frequence + 1;
frequences.put(item, frequence);
}
}
// 用每个出现频次不小于最小支持频次的项构造一个频繁1项集
Set ret = new HashSet();
for (Entry entry : frequences.entrySet()) {
String item = entry.getKey();
Integer frequence = entry.getValue();
if (frequence >= MSF) {
ItemSet set = new ItemSet(new String[] { item });
set.frequence = frequence;
ret.add(set);
}
}
return ret;
}
/**
* 根据所有频繁L-1项集获得所有频繁L项集的候选L项集
*/
static List aprioriGenCandidates(Set preItemSets) {
List ret = new LinkedList();
// 尝试将所有频繁L-1项集两两连接然后作剪枝处理以获得候选L项集
for (ItemSet set1 : preItemSets) {
for (ItemSet set2 : preItemSets) {
if (set1 != set2 && set1.canMakeJoin(set2)) {
// 连接
ItemSet union = new ItemSet();
union.addAll(set1);
union.add(set2.last());
// 剪枝
boolean missSubSet = false;
List subItemSets = union.listDirectSubItemSets();
for (ItemSet itemSet : subItemSets) {
if (!preItemSets.contains(itemSet)) {
missSubSet = true;
break;
}
}
if (!missSubSet)
ret.add(union);
}
}
}
return ret;
}
/**
* 由多个项组成的项集，每个项是一个字符串。使用TreeSet使项集中的项有序，以辅助算法实现
*/
static class ItemSet extends TreeSet {
private static final long serialVersionUID = 23883315835136949L;
int frequence; // 项集出现的频次
public ItemSet() {
this(new String[0]);
}
public ItemSet(String[] items) {
for (String item : items)
add(item);
}
/**
* 测试本项集（假定阶为L-1）能否与别一个项集连接以生成L阶项集
*/
public boolean canMakeJoin(ItemSet other) {
// 若两个项集的阶不同，则不能连接生成L阶项集
if (other.size() != this.size())
return false;
// 假定项集的阶为L-1，在项有序的前提下，当且仅当两个项集的前L-2个项相同
// 而本项集的第L-1个项小于另一个项集的第L-1个项时，可以连接生成L阶项集
Iterator
it1 = this.iterator();
Iterator it2 = other.iterator();
while (it1.hasNext()) {
String item1 = it1.next();
String item2 = it2.next();
int result = item1.compareTo(item2);
if (result != 0) {
if (it1.hasNext())
return false;
return result < 0 true : false;
}
}
return false;
}
/**
* 假定本项集的阶为L，列举本项集的所有阶为L-1的子项集
*/
public List listDirectSubItemSets() {
List ret = new LinkedList();
// 只有本项集的阶大于1，才可能存在非空子项集
if (size() > 1) {
for (String rmItem : this) {
ItemSet subSet = new ItemSet();
subSet.addAll(this);
subSet.remove(rmItem);
ret.add(subSet);
}
}
return ret;
}
/**
* 列出本项集除自身外的所有非空子项集
*/
public List listNotEmptySubItemSets() {
List ret = new LinkedList();
int size = size();
if (size > 0) {
char[] mapping = new char[size()];
initMapping(mapping);
while (nextMapping(mapping)) {
ItemSet set = new ItemSet();
Iterator it = this.iterator();
for (int i = 0; i < size; i++) {
String item = it.next();
if (mapping[i] == '1')
set.add(item);
}
if (set.size() < size)
ret.add(set);
}
}
return ret;
}
private void initMapping(char[] mapping) {
for (int i = 0; i < mapping.length; i++)
mapping[i] = '0';
}
private boolean nextMapping(char[] mapping) {
int pos = 0;
while (pos < mapping.length && mapping[pos] == '1') {
mapping[pos] = '0';
pos++;
}
if (pos < mapping.length) {
mapping[pos] = '1';
return true;
}
return false;
}
}
}