java实现频繁集_数据挖掘--频繁集测试--Apriori算法--java实现
[ 關(guān)聯(lián)規(guī)則挖掘用于尋找給定數(shù)據(jù)集中項之間的有趣的關(guān)聯(lián)或相關(guān)關(guān)系。 關(guān)聯(lián)規(guī)則揭示了數(shù)據(jù)項間的未知的依賴關(guān)系，根據(jù)所挖掘的關(guān)聯(lián)關(guān)系，可以從� ...]
2013年11月19日注：以下算法中，combine算法實現(xiàn)不正確，應(yīng)該是從已有的頻繁中來產(chǎn)生。需要進(jìn)一步修改
=================================================================================
Apriori算法原理：
如果某個項集是頻繁的，那么它所有的子集也是頻繁的。如果一個項集是非頻繁的，那么它所有的超集也是非頻繁的。
示意圖
圖一：[頻繁模式是頻繁地出現(xiàn)在數(shù)據(jù)集中的模式(如項集、子序列或者子結(jié)構(gòu))。例如，頻繁地同時出現(xiàn)在交易數(shù)據(jù)集中的商品(如牛奶和面包)的集合是頻繁項集。]
圖二：
package cn.ffr.frequent.apriori;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.net.URL;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Set;
/**
* Apriori的核心代碼實現(xiàn)
* @author neu_fufengrui@163.com
*/
public class Apriori {
public static final String STRING_SPLIT = ",";
/**
* 主要的計算方法
* @param data 數(shù)據(jù)集
* @param minSupport 最小支持度
* @param maxLoop 最大執(zhí)行次數(shù)，設(shè)NULL為獲取最終結(jié)果
* @param containSet 結(jié)果中必須包含的子集
* @return
*/
public Map compute(List data, Double minSupport, Integer maxLoop, String[] containSet){
//校驗
if(data == null || data.size() <= 0){
return null;
}
//初始化
Map result = new HashMap();
Object[] itemSet = getDataUnitSet(data);
int loop = 0;
//核心循環(huán)處理過程
while(true){
//重要步驟一：合并，產(chǎn)生新的頻繁集
Set keys = combine(result.keySet(), itemSet);
result.clear();//移除之前的結(jié)果
for(String key : keys){
result.put(key, computeSupport(data, key.split(STRING_SPLIT)));
}
//重要步驟二：修剪，去除支持度小于條件的。
cut(result, minSupport, containSet);
loop++;
//輸出計算過程
System.out.println("loop ["+loop+"], result : "+result);
//循環(huán)結(jié)束條件
if(result.size() <= 0){
break;
}
if(maxLoop != null && maxLoop > 0 && loop >= maxLoop){//可控制循環(huán)執(zhí)行次數(shù)
break;
}
}
return result;
}
/**
* 計算子集的支持度
*
* 支持度 = 子集在數(shù)據(jù)集中的數(shù)據(jù)項 / 總的數(shù)據(jù)集的數(shù)據(jù)項
*
* 數(shù)據(jù)項的意思是一條數(shù)據(jù)。
* @param data 數(shù)據(jù)集
* @param subSet 子集
* @return
*/
public Double computeSupport(List data, String[] subSet){
Integer value = 0;
for(int i = 0; i < data.size(); i++){
if(contain(data.get(i), subSet)){
value ++;
}
}
return value*1.0/data.size();
}
/**
* 獲得初始化唯一的數(shù)據(jù)集，用于初始化
* @param data
* @return
*/
public Object[] getDataUnitSet(List data){
List uniqueKeys = new ArrayList();
for(String[] dat : data){
for(String da : dat){
if(!uniqueKeys.contains(da)){
uniqueKeys.add(da);
}
}
}
return uniqueKeys.toArray();
}
/**
* 合并src和target來獲取頻繁集
* 增加頻繁集的計算維度
* @param src
* @param target
* @return
*/
public Set combine(Set src, Object[] target){
Set dest = new HashSet();
if(src == null || src.size() <= 0){
for(Object t : target){
dest.add(t.toString());
}
return dest;
}
for(String s : src){
for(Object t : target){
if(s.indexOf(t.toString())<0){
String key = s+STRING_SPLIT+t;
if(!contain(dest, key)){
dest.add(key);
}
}
}
}
return dest;
}
/**
* dest集中是否包含了key
* @param dest
* @param key
* @return
*/
public boolean contain(Set dest, String key){
for(String d : dest){
if(equal(d.split(STRING_SPLIT), key.split(STRING_SPLIT))){
return true;
}
}
return false;
}
/**
* 移除結(jié)果中，支持度小于所需要的支持度的結(jié)果。
* @param result
* @param minSupport
* @return
*/
public Map cut(Map result, Double minSupport, String[] containSet){
for(Object key : result.keySet().toArray()){//防止 java.util.ConcurrentModificationException，使用keySet().toArray()
if(minSupport != null && minSupport > 0 && minSupport < 1 && result.get(key) < minSupport){//比較支持度
result.remove(key);
}
if(containSet != null && containSet.length > 0 && !contain(key.toString().split(STRING_SPLIT), containSet)){
result.remove(key);
}
}
return result;
}
/**
* src中是否包含dest，需要循環(huán)遍歷查詢
* @param src
* @param dest
* @return
*/
public static boolean contain(String[] src, String[] dest){
for(int i = 0; i < dest.length; i++){
int j = 0;
for(; j < src.length; j++){
if(src[j].equals(dest[i])){
break;
}
}
if(j == src.length){
return false;//can not find
}
}
return true;
}
/**
* src是否與dest相等
* @param src
* @param dest
* @return
*/
public boolean equal(String[] src, String[] dest){
if(src.length == dest.length && contain(src, dest)){
return true;
}
return false;
}
/**
* 主測試方法
* 測試方法，挨個去掉注釋，進(jìn)行測試。
*/
public static void main(String[] args) throws Exception{
//test 1
//List data = loadSmallData();
//Long start = System.currentTimeMillis();
//Map result = new Apriori().compute(data, 0.5, 3, null);//求支持度大于指定值
//Long end = System.currentTimeMillis();
//System.out.println("Apriori Result [costs:"+(end-start)+"ms]: ");
//for(String key : result.keySet()){
//System.out.println("\tFrequent Set=["+key+"] & Support=["+result.get(key)+"];");
//}
//test 2
//List data = loadMushRoomData();
//Long start = System.currentTimeMillis();
//Map result = new Apriori().compute(data, 0.3, 4, new String[]{"2"});//求支持度大于指定值
//Long end = System.currentTimeMillis();
//System.out.println("Apriori Result [costs:"+(end-start)+"ms]: ");
//for(String key : result.keySet()){
//System.out.println("\tFrequent Set=["+key+"] & Support=["+result.get(key)+"];");
//}
//test 3
List data = loadChessData();
Long start = System.currentTimeMillis();
Map result = new Apriori().compute(data, 0.95, 3, null);//求支持度大于指定值
Long end = System.currentTimeMillis();
System.out.println("Apriori Result [costs:"+(end-start)+"ms]: ");
for(String key : result.keySet()){
System.out.println("\tFrequent Set=["+key+"] & Support=["+result.get(key)+"];");
}
}
/*
*SmallData: minSupport 0.5, maxLoop 3, containSet null, [costs: 16ms]
*MushRoomData: minSupport 0.3, maxLoop 4, containSet {"2"}, [costs: 103250ms]
*ChessData: minSupport 0.95, maxLoop 34, containSet {null, [costs: 9718ms]
*/
//測試數(shù)據(jù)集-1
public static List loadSmallData() throws Exception{
List data = new ArrayList();
data.add(new String[]{"d1","d3","d4"});
data.add(new String[]{"d2","d3","d5"});
data.add(new String[]{"d1","d2","d3","d5"});
data.add(new String[]{"d2","d5"});
return data;
}
//測試數(shù)據(jù)集-2
public static List loadMushRoomData() throws Exception{
String link = "http://fimi.ua.ac.be/data/mushroom.dat";
URL url = new URL(link);
BufferedReader reader = new BufferedReader(new InputStreamReader(url.openStream()));
String temp = reader.readLine();
List result = new ArrayList();
int lineNumber = 0;
while(temp != null){
System.out.println("reading data... [No."+(++lineNumber)+"]");
String[] item = temp.split(" ");
result.add(item);
temp = reader.readLine();
}
reader.close();
return result;
}
//測試數(shù)據(jù)集-3
public static List loadChessData() throws Exception{
String link = "http://fimi.ua.ac.be/data/chess.dat";
URL url = new URL(link);
BufferedReader reader = new BufferedReader(new InputStreamReader(url.openStream()));
String temp = reader.readLine();
List result = new ArrayList();
int lineNumber = 0;
while(temp != null){
System.out.println("reading data... [No."+(++lineNumber)+"]");
String[] item = temp.split(" ");
result.add(item);
temp = reader.readLine();
}
reader.close();
return result;
}
}
算法原理：
總結(jié)
以上是生活随笔為你收集整理的java实现频繁集_数据挖掘--频繁集测试--Apriori算法--java实现的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： mysql server 5.6root
- 下一篇： mysql数据库 支付_如何管理MySQ