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 ListSet 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项集 ListSet f1Set = apriori.findF1Items(data); apriori.printSet(f1Set, 1); ListSet 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(fileName0); 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 ArrayListSet(); 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 */ ListSet findF1Items(List data) ListSet result = new ArrayListSet(); 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 */ ListSet arioriGen(ListSet preSet) ListSet result = new ArrayListSet(); 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 String0); String strA2 = preSet.get(j).toArray(new String0); if (isCanLink(strA1, strA2) / 判断两个k-1项集是否符合连接成k项集的条件 Set set = new TreeSet(); for (String str : strA1) set.add(str); set.add(String) strA2strA2.length - 1); / 连接成k项集 / 判断k项集是否需要剪切掉，如果不需要被cut掉，则加入到k项集列表中 if (!isNeedCut(preSet, set) result.add(set); return checkSupport(result); /* * 把set中的项集与数量集比较并进行计算，求出支持度大于要求的项集 * * param set * return */ ListSet checkSupport(ListSet setList) ListSet result = new ArrayListSet(); boolean flag = true; int counter = new intsetList.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) counteri += 1; else flag = true; for (int i = 0; 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 (!s1i.equals(s2i) flag = false; break; if (s1s1.length - 1.equals(s2s2.length - 1) flag = false; else flag = false; return flag; /* * 判断set是否需要被cut * * param setList * param set * return */ boolean isNeedCut(ListSet setList, Set set) boolean flag = false; ListSet 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(ListSet setList, Set set) boolean flag = false; int position = 0; for (Set s : setList) String sArr = s.toArray(new String0); String setArr = set.toArray(new String0); for (int i = 0; i sArr.length; i+) if (sArri.equals(setArri) / 如果对应位置的元素相同，则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 */ ListSet getSubset(Set set) ListSet result = new ArrayListSet(); String setArr = set.toArray(new String0); 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) s