?? apriori.java
字號:
/**
* Copyright (c) 2003 HCYCOM, Inc. All Rights Reserved.
*
* A Java application of Apriori algorithm.
*
* Make sure that your DBMS Service is running before the OS loads the program.
* Either SQLServer2000 or MySQL4.0 is your good start.
*
* @author Zengli, China Agricultural University.
* @version 0.01 03/07/09
*
* mailto:zengli@hcycom.com
*/
import java.sql.*;
import java.util.*;
import java.math.*;
public class Apriori
{
Connection conn;
int rowCount;
private String url,user,passwd;
String[] itemList = null;
int[] itemCount = null;
final double MIN_SUP = 0.4;//最小支持度s
final double MIN_CONF = 0.5;//最小置信度c
PreparedStatement pstmt = null;
ResultSet rs = null; //定義結果集
PreparedStatement ckPstmt = null;
ResultSet ckRs = null;
PreparedStatement lkPstmt = null;
//構造函數
Apriori()
{
url = "jdbc:odbc:AprioriMySQL";//定義JDBC-ODBC橋的URL
user = "root";
passwd = "";
conn = null;
rowCount = 0;
//預設項列表(商品集)={啤酒,尿布,擦身粉,面包,雨傘,牛奶,洗衣粉,可樂}
itemList = new String[]{"beer","diaper","toiletpowder","bread","umbrella","milk","washingpowder","coke"};
itemCount = new int[itemList.length];
}
public static void main(String[] args)
{
Apriori a = new Apriori();
a.execute();
}
//加載指定的數據庫驅動程序
void loadJdbcOdbcDriver(String driverName)
{
try{
System.out.println("加載數據庫驅動程序 ...OK!");
Class.forName(driverName);
}
catch(java.lang.ClassNotFoundException e){
System.err.print("ClassNotFoundException:");
System.err.println(e.getMessage());
}
}
//Apriori算法實現
void execute()
{
//加載數據庫驅動程序
loadJdbcOdbcDriver("sun.jdbc.odbc.JdbcOdbcDriver");
System.out.println("初次掃描數據庫commodity ...OK!\n");
try{
//建立連接ODBC數據源
conn = DriverManager.getConnection(url,user,passwd);
//提交連接請求
conn.setAutoCommit(false);
//------- 初次掃描數據庫commodity的transaction表,對每個候選(即商品項)以及事務(即交易)計數 ------
pstmt = conn.prepareStatement("SELECT * FROM transaction",ResultSet.TYPE_SCROLL_SENSITIVE,ResultSet.CONCUR_UPDATABLE);
rs = pstmt.executeQuery();
int id;
String commodity_list;
Statement stmt5 = null;
Statement stmt8 = null;
Statement stmt9 = null;
stmt5 = conn.createStatement();
stmt5.execute("DELETE FROM lk");
for (int i = 0; i < itemList.length; i++){
rowCount = 0;
while (rs.next()){
id = rs.getInt(1);
commodity_list = rs.getString("commodity_list");
if (commodity_list.indexOf(itemList[i]) != -1) itemCount[i]++;//對每個候選計數
rowCount++;
}
System.out.println(itemList[i] + "\t\t\t(" + itemCount[i] + ")");
//比較候選支持度計數與最小支持度計數,得出L1表
if (itemCount[i] >= (int)(MIN_SUP * rowCount)){
pstmt = conn.prepareStatement("INSERT INTO Lk(itemsets,sup_count) VALUES(?,?)",ResultSet.TYPE_SCROLL_SENSITIVE,ResultSet.CONCUR_UPDATABLE);
pstmt.setString(1,itemList[i]);
pstmt.setInt(2,itemCount[i]);
pstmt.executeUpdate();
}
rs.beforeFirst();
}
//------- 算法核心 : 使用候選項集Ck找頻繁項集Lk -------
for (int k = 2; ; k++){
if (!aproiri_gen(k - 1, MIN_SUP)) break;//連接-剪枝生成候選集Ck(即Ck表)
//讀取Ck表的每一個候選項集
pstmt = conn.prepareStatement("SELECT * FROM ck",ResultSet.TYPE_SCROLL_SENSITIVE,ResultSet.CONCUR_UPDATABLE);
rs = pstmt.executeQuery();
stmt8 = conn.createStatement();
stmt8.execute("DELETE FROM lk");//清空舊的Lk表(即Lk-1表)
while (rs.next()){
String ck = rs.getString("itemsets");//讀出Ck中每個候選項集(即Ck表的第一個字段)
//將Ck當前候選項集中各元素分離并復制到Vector向量的各分量中
Vector ckItemList = new Vector(k);
ckItemList = splitItemList(k, ck);
int ckSupCnt = 0;//Ck項集支持度
//掃描數據庫commodity的transaction表,為Ck中的每個候選項集計數
ckPstmt = conn.prepareStatement("SELECT * FROM transaction",ResultSet.TYPE_SCROLL_SENSITIVE,ResultSet.CONCUR_UPDATABLE);
ckRs = ckPstmt.executeQuery();
while (ckRs.next()){//循環讀入transaction表的記錄
String s = ckRs.getString("commodity_list");//得到commodity_list字段內容
System.out.println("commodity_field = "+s);
int j = 0;
for (; j < k; j++){
if (s.indexOf(ckItemList.elementAt(j).toString()) == -1) break;//掃描當前記錄,判斷是否同時存在Ck當前候選項集中的所有元素
}
if (j >= k) ckSupCnt++;//Ck候選項集支持度計數
}
//比較候選支持度計數與最小支持度計數,生成新的Lk表
System.out.println("ckSupCnt = " + ckSupCnt +" (int)(MIN_SUP * rowCount)=" +(int)(MIN_SUP * rowCount));
if (ckSupCnt >= (int)(MIN_SUP * rowCount)){
stmt9 = conn.createStatement();
stmt9.execute("INSERT INTO lk(itemsets,sup_count) VALUES('" + ck + "'," + ckSupCnt + ")");
}
}
}
//操作語句提交
conn.commit();
conn.setAutoCommit(true);
if (ckPstmt != null) ckPstmt.close();
if (lkPstmt != null) lkPstmt.close();
if (pstmt != null) pstmt.close();
if (conn != null) conn.close();
System.out.println("-- END --");
}
catch(BatchUpdateException b){
System.err.println("--BatchUpdateException--");
System.err.println("SQLState: " + b.getSQLState());
System.err.println("Message: " + b.getMessage());
System.err.println("Vendor: " + b.getErrorCode());
System.err.print("Update counts: ");
int [] updateCounts = b.getUpdateCounts();
for(int i = 0; i<updateCounts.length;i++){
System.err.print(updateCounts[i] + " ");
}
System.err.println("");
}
catch(SQLException ex){
System.err.println("--SQLException--");
System.err.println("SQLState: " + ex.getSQLState());
System.err.println("Message: " + ex.getMessage());
System.err.println("Vendor: " + ex.getErrorCode());
}
}
//連接-剪枝動作,產生候選k-項集(即得到Ck表)
boolean aproiri_gen(int k, double min_sup)
{
ResultSet lkRs1 = null;
ResultSet lkRs2 = null;
int ckCnt = 0;
Statement stmt = null;
Statement stmt2 = null;
Statement stmt7 = null;
try{
//讀取舊Lk表(即Lk-1表)中的所有項集
stmt = conn.createStatement();
lkRs1 = stmt.executeQuery("SELECT * FROM lk");
stmt7 = conn.createStatement();
stmt7.execute("DELETE FROM ck");
ResultSet tRs1 = lkRs1;
while (lkRs1.next()){
String lkItemsets1 = lkRs1.getString("itemsets");//讀取當前lkRs1結果集記錄的第一個字段
stmt2 = conn.createStatement();
lkRs2 = stmt2.executeQuery("SELECT * FROM lk");
while (lkRs2.next()){
String lkItemsets2 = lkRs2.getString("itemsets");//讀取當前lkRs2結果集記錄的第一個字段
if (isLinkable(k, lkItemsets1, lkItemsets2)){//判斷當前lkRs1項集與當前lkRs2項集是否存在可連接性
System.out.println("k="+ k +" lkItemsets1 = "+ lkItemsets1 + " lkItemsets2= "+ lkItemsets2);
if (!pruneAction(joinAction(k, lkItemsets1, lkItemsets2), tRs1)) ckCnt++;//連接-剪枝;統計剪枝后剩余的Ck項集數
}
else break;//不存在可連接性則中斷本次lkRs2結果集循環
}
}
}
catch(Exception e){
e.printStackTrace();
}
System.out.println("ckCnt=" + ckCnt);
if (ckCnt == 0) return false;//如剪枝后Ck項集的計數值為0則算法終止
else return true;
}
//分離字符串并返回到向量中
Vector splitItemList(int k, String cl)
{
String[] strArray = cl.split(",");
Vector v = new Vector(Arrays.asList(strArray));//將字符串數組轉換為向量
System.out.println("splitItem = "+v);
return v;
}
//判斷是否具有可連接性
boolean isLinkable(int k, String s1,String s2)
{
Vector v1 = splitItemList(k, s1);
Vector v2 = splitItemList(k, s2);
int i = 0;
int cnt = 0;
for (; i < v1.size(); i++){
if (v1.elementAt(i) == v2.elementAt(i)) cnt++;//break;//未滿足可連接條件
}
if ((cnt == v1.size() -1) && !v1.equals(v2)){
return true;//可連接
}
else return false;
}
//連接動作
Vector joinAction(int k, String s1,String s2)
{
Vector v1 = splitItemList(k, s1);
Vector v2 = splitItemList(k, s2);
v1.add(v2.elementAt(v2.size() -1));//取v2最后一個分量插入到v1的尾部
return v1;
}
//判斷當前頻繁項集Ck中的所有(k-1)子集是否頻繁,否則進行剪枝
boolean pruneAction(Vector v, ResultSet rs)
{
//----------- 該處對原Apriori算法中描述的剪枝動作有所改動 ------------
//用頻繁項集L(k-1)與剪枝前的候選項集Ck相匹配,然后由 ?(計數值 > k) 判斷是否應當剪去該候選項集
Statement stmt3 = null;
Statement stmt4 = null;
ResultSet rs2 = null;
ResultSet rs3 = null;
int containCnt = 0;
try{
stmt3 = conn.createStatement();
rs2 = stmt3.executeQuery("SELECT * FROM lk");
while (rs2.next()){
String lkItemsets = rs2.getString("itemsets");//讀入L(k-1)的各項集
Vector lkItemList = splitItemList(v.size() - 1, lkItemsets);//(v.size - 1)即 k - 1
System.out.println("v_list = " +v +" lkItemList = "+lkItemList);
if (v.containsAll(lkItemList)) containCnt++;
}
System.out.println("v.size = " +v.size() +" containCnt = "+containCnt);
if (containCnt >= v.size()){//匹配數 >= k說明該候選項集需保留(非剪枝)
//------ 得到候選集(Ck表) --------
String s = new String(v.elementAt(0).toString());
for (int i = 1; i < v.size(); i++){
s = s + "," + v.elementAt(i);
}
System.out.println("s = " +s);
stmt4 = conn.createStatement();
stmt4.execute("INSERT INTO ck(itemsets,sup_count) VALUES('" + s + "',0)");
stmt4.close();
return false;//非剪枝,保留
}
}
catch(Exception e){
e.printStackTrace();
}
return true;//剪枝,返回true
}
}?? 快捷鍵說明
復制代碼
Ctrl + C
搜索代碼
Ctrl + F
全屏模式
F11
切換主題
Ctrl + Shift + D
顯示快捷鍵
?
增大字號
Ctrl + =
減小字號
Ctrl + -