FP.rar_FPgrowth _FP算法代码java_关联规则_关联规则代码

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.Arrays; import java.util.HashMap; import java.util.List; import java.util.Map; import java.util.Set; public class FPGrowth { private int minSup; /** * @param args */ public static void main(String[] args) { long begin=System.currentTimeMillis(); FPGrowth fpg = new FPGrowth(); fpg.setMinSup(441); List<String> data = fpg.buildData("retail.dat"); Item[] f1Items = fpg.buildF1Items(data); Map<String, List<String>> condBase; fpg.buildFPTree(data, f1Items); condBase = fpg.buildCondBase(f1Items); Map<String, Item> condFPTree = fpg.buildCondFPTree(condBase); //输出频繁子集 Map<String, List<List<String>>> fpSetMap = fpg.fpGrowth(condFPTree); fpg.printFPSet(fpSetMap); System.out.println((System.currentTimeMillis())-begin+"ms"); } /** * 输出频繁集 */ public void printFPSet(Map<String, List<List<String>>> fpSetMap){ List<List<String>> fpSet; Set<String> items = fpSetMap.keySet(); for(String item : items){ System.out.println("<I"+item+">"); fpSet = fpSetMap.get(item); for (int i = 0; i < fpSet.size(); i++) { for (String str : fpSet.get(i)) { // if(str != null && str.length() > 0){ System.out.print("I"+str + ", "); // } } System.out.println("I"+item); } } System.out.print("Total:"+"580\n"); } /** * 1.构造数据集 */ public List<String> buildData(String...fileName) { List<String> data = new ArrayList<String>(); if(fileName.length !=0){ 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{ System.out.println("Read Error!"); } return data; } /** * 2.构造频繁1项列表，同时作为树的项头表 */ public Item[] buildF1Items(List<String> data) { List<Item> itemList = new ArrayList<Item>(); Map<String, Item> resultMap = new HashMap<String, Item>(); for (String trans : data) { String[] items = trans.trim().split(" "); int i; for (String item : items) { if(resultMap.get(item) == null){ Item newItem = new Item(); newItem.setValue(item); newItem.setCounter(1); resultMap.put(item, newItem); }else{ resultMap.get(item).addCounter(); } } } Set<String> keySet = resultMap.keySet(); for(String key : keySet){ itemList.add(resultMap.get(key)); } List<Item> result = new ArrayList<Item>(); // 把支持度小于minSup的项从列表中删除 for (int i = 0; i < itemList.size(); i++) { if (itemList.get(i).getCounter() >= this.minSup) { result.add(itemList.get(i)); } } // 对列表进行排序 Item[] f1Items = result.toArray(new Item[0]); Arrays.sort(f1Items); return f1Items; } /** * 3. 构造fpTree */ public Item buildFPTree(List<String> data, Item[] f1Items) { Item fpTree = new Item(); List<Item> subItems; // 对每一条事务进行处理 for (String trans : data) { // 得出每条事件中涉及的元素项 String[] items = trans.trim().split(" "); // 对items中的元素按其在频繁1项集中出现次数排序 items = sortItem(items, f1Items); // 把items的值加入到fpTree中 subItems = fpTree.getNextItem(); if (subItems.size() == 0) { this.addLeaf(fpTree, items, f1Items); } else { Item temp = null; for (int i = 0; i < items.length; i++) { int j = 0; int size = subItems.size(); for (; j < subItems.size(); j++) { if (subItems.get(j).getValue().equals(items[i])) { temp = subItems.get(j); temp.addCounter(); subItems = temp.getNextItem(); break; } } if (j == size) { if (temp == null) { this.addLeaf(fpTree, Arrays.copyOfRange(items, i, items.length), f1Items); } else { this.addLeaf(temp, Arrays.copyOfRange(items, i, items.length), f1Items); } break; } } } } return fpTree; } /** * 3.1 对元素数组根据其在f1中出面的频繁进行排序 * * @param items * @return */ public String[] sortItem(String[] items, Item[] f1Items) { String[] temp = new String[f1Items.length]; int i; for (String item : items) { for (i = 0; i < f1Items.length; i++) { if (item.equals(f1Items[i].getValue())) { temp[i] = item; } } } List<String> list = new ArrayList<String>(); int j = 0; for (i = 0; i < temp.length; i++) { if (temp[i] != null) { list.add(temp[i]); } } return list.toArray(new String[0]); } /** * 3.2 给FPTree的节点添加子节点序列 * * @param preItem * @param items */ public void addLeaf(Item preItem, String[] items, Item[] f1Items) { if (items.length > 0) { Item item = new Item(items[0]); item.setCounter(1); item.setPreItem(preItem); preItem.addNextItem(item); for (Item i : f1Items) { if (i.getValue().equals(items[0])) { Item temp = i; while (temp.getSibling() != null) { temp = temp.getSibling(); } temp.setSibling(item); break; } } if (items.length > 1) { addLeaf(item, Arrays.copyOfRange(items, 1, items.length), f1Items); } } } // 4.生成条件模式基