第1页 / 共9页
第2页 / 共9页
第3页 / 共9页
第4页 / 共9页
第5页 / 共9页
第6页 / 共9页
第7页 / 共9页
第8页 / 共9页
Apriori算法及其改进算法.doc
package win;
import java.io.BufferedReader;
import java.io.File;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.io.IOException;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Set;
import java.util.TreeSet;
public class Apriori {
private int minSup;
private static List data;
private static List> dataSet;
/**
* @param args
*/
public static void main(String[] args) {
long startTime = System.currentTimeMillis();
Apriori apriori = new Apriori();
//使用书中的测试集
/*apriori.setMinSup(2);
data = apriori.buildData();*/
//设置最小支持度
apriori.setMinSup(3);
//构造数据集
//data = apriori.buildData("E:\\retail.dat");
data = apriori.buildData("");
//构造频繁 1 项集
List> f1Set = apriori.findF1Items(data);
apriori.printSet(f1Set, 1);
List> result = f1Set;
int i = 2;
do{
result = apriori.arioriGen(result);
apriori.printSet(result, i);
i++;
}while(result.size() != 0);
long endTime = System.currentTimeMillis();
System.out.println("共用时：" + (endTime - startTime) + "ms");
}
public void setMinSup(int minSup) {
this.minSup = minSup;
}
/**
* 构造原始数据集，可以为之提供参数，也可以不提供
* 如果不提供参数，将按程序默认构造的数据集；
* 如果提供参数为文件名，则使用文件中的数据集
*
* @return
*/
List buildData(String...fileName) {
List data = new ArrayList();
int length = fileName.length;
if(length > 1){
File file = new File(fileName[0]);
try {
BufferedReader reader = new BufferedReader(new FileReader(file));
String line;
while( (line = reader.readLine()) != null){
data.add(line);
}
} catch (FileNotFoundException e) {
e.printStackTrace();
} catch (IOException e) {
e.printStackTrace();
}
}else{
data.add("I1 I2 I5");
data.add("I2 I4");
data.add("I2 I3");
data.add("I1 I2 I4");
data.add("I1 I3");
data.add("I2 I3");
data.add("I1 I3");
data.add("I1 I2 I3 I5");
data.add("I1 I2 I3");
data.add("I1 I2 I3");
data.add("I1 I2 I3");
data.add("I2 I3 I4");
data.add("I2 I3 I4");
data.add("I2 I3 I4");
}
dataSet = new ArrayList>();
Set dSet;
for (String d : data) {
dSet = new TreeSet();
String[] dArr = d.split(" ");
for (String str : dArr) {
dSet.add(str);
}
dataSet.add(dSet);
}
return data;
}
/**
* 找出候选 1 项集
*
* @param data
* @return
*/
List> findF1Items(List data) {
List> result = new ArrayList>();
Map dc = new HashMap();
for (String d : data) {
String[] items = d.split(" ");
for (String item : items) {
if (dc.containsKey(item)) {
dc.put(item, dc.get(item) + 1);
} else {
dc.put(item, 1);
}
}
}
Set itemKeys = dc.keySet();
Set tempKeys = new TreeSet();
for (String str : itemKeys) {
tempKeys.add(str);
}
for (String item : tempKeys) {
if (dc.get(item) >= minSup) {
Set f1Set = new TreeSet();
f1Set.add(item);
result.add(f1Set);
}
}
return result;
}
/**
* 利用 arioriGen 方法由 k-1 项集生成 k 项集
*
* @param preSet
* @return
*/
List> arioriGen(List> preSet) {
List> result = new ArrayList>();
int preSetSize = preSet.size();
for (int i = 0; i < preSetSize - 1; i++) {
for (int j = i + 1; j < preSetSize; j++) {
String[] strA1 = preSet.get(i).toArray(new String[0]);
String[] strA2 = preSet.get(j).toArray(new String[0]);
if (isCanLink(strA1, strA2)) { // 判断两个 k-1 项集是否符合连接成 k 项集
的条件
Set set = new TreeSet();
for (String str : strA1) {
set.add(str);
}
set.add((String) strA2[strA2.length - 1]); // 连接成 k 项集
// 判断 k 项集是否需要剪切掉，如果不需要被 cut 掉，则加入到 k 项
集列表中
if (!isNeedCut(preSet, set)) {
result.add(set);
}
}
}
}
return checkSupport(result);
}
/**
* 把 set 中的项集与数量集比较并进行计算，求出支持度大于要求的项集
*
* @param set
* @return
*/
List> checkSupport(List> setList) {
List> result = new ArrayList>();
boolean flag = true;
int[] counter = new int[setList.size()];
for (int i = 0; i < setList.size(); i++) {
for (Set dSets : dataSet) {
if (setList.get(i).size() > dSets.size()) {
flag = true;
} else {
for (String str : setList.get(i)) {
if (!dSets.contains(str)) {
flag = false;
break;
}
}
if (flag) {
counter[i] += 1;
} else {
flag = true;
}
}
}
}
for (int i = 0; i < setList.size(); i++) {
if (counter[i] >= minSup) {
result.add(setList.get(i));
}
}
return result;
}
/**
* 判断两个项集合能否执行连接操作
*
* @param s1
* @param s2
* @return
*/
boolean isCanLink(String[] s1, String[] s2) {
boolean flag = true;
if (s1.length == s2.length) {
for (int i = 0; i < s1.length - 1; i++) {
if (!s1[i].equals(s2[i])) {
flag = false;
break;
}
}
if (s1[s1.length - 1].equals(s2[s2.length - 1])) {
flag = false;
}
} else {
flag = false;
}
return flag;
}
/**
* 判断 set 是否需要被 cut
*
* @param setList
* @param set
* @return
*/
boolean isNeedCut(List> setList, Set set) {
boolean flag = false;
List> subSets = getSubset(set); // 获得 k 项集的所有 k-1 项集
for (Set subSet : subSets) {
// 判断当前的 k-1 项集 set 是否在频繁 k-1 项集中出现，如出现，则不需要 cut
// 若没有出现，则需要被 cut
if (!isContained(setList, subSet)) {
flag = true;
break;
}
}
return flag;
}
/**
* 判断 k 项集的某 k-1 项集是否包含在频繁 k-1 项集列表中
*
* @param setList
* @param set
* @return
*/
boolean isContained(List> setList, Set set) {
boolean flag = false;
int position = 0;
for (Set s : setList) {
String[] sArr = s.toArray(new String[0]);
String[] setArr = set.toArray(new String[0]);
for (int i = 0; i < sArr.length; i++) {
if (sArr[i].equals(setArr[i])) { // 如果对应位置的元素相同，则 position 为当
前位置的值
position = i;
} else {
break;
}
}
// 如果 position 等于了数组的长度，说明已找到某个 setList 中的集合与
// set 集合相同了，退出循环，返回包含
// 否则，把 position 置为 0 进入下一个比较
if (position == sArr.length - 1) {
flag = true;
break;
} else {
flag = false;
position = 0;
}
}
return flag;
}
/**
* 获得 k 项集的所有 k-1 项集
*
* @param set
* @return
*/
List> getSubset(Set set) {
List> result = new ArrayList>();
String[] setArr = set.toArray(new String[0]);
for (int i = 0; i < setArr.length; i++) {
Set subSet = new TreeSet();
for (int j = 0; j < setArr.length; j++) {
if (i != j) {
subSet.add((String) setArr[j]);
}
}
result.add(subSet);
}
return result;
}
void printSet(List> setList, int i) {
System.out.print("频繁"+i+"项集： 共" + setList.size()+"项：{");
for (Set set : setList) {
System.out.print("[ ");
for (String str : set) {
System.out.print(str + " ");
}
System.out.print("], ");
}
相关推荐
2023年江西萍乡中考道德与法治真题及答案.doc
2012年重庆南川中考生物真题及答案.doc
2013年江西师范大学地理学综合及文艺理论基础考研真题.doc
2020年四川甘孜小升初语文真题及答案I卷.doc
2020年注册岩土工程师专业基础考试真题及答案.doc
2023-2024学年福建省厦门市九年级上学期数学月考试题及答案.doc
2021-2022学年辽宁省沈阳市大东区九年级上学期语文期末试题及答案.doc
2022-2023学年北京东城区初三第一学期物理期末试卷及答案.doc
2018上半年江西教师资格初中地理学科知识与教学能力真题及答案.doc
2012年河北国家公务员申论考试真题及答案-省级.doc
2020-2021学年江苏省扬州市江都区邵樊片九年级上学期数学第一次质量检测试题及答案.doc
2022下半年黑龙江教师资格证中学综合素质真题及答案.doc
