Accueil > > > ALGORITHME DE APRIORI POUR LA GÉNÉRATION DES ITEMSETS FRÉQUENT A PARTIR D'UNE TABLE BINAIRE PAR YERMES AMINE
ALGORITHME DE APRIORI POUR LA GÉNÉRATION DES ITEMSETS FRÉQUENT A PARTIR D'UNE TABLE BINAIRE PAR YERMES AMINE
Information sur la source
Description
Apriori pour la génération des Itemsets Fréquent a partir d'une table binaire Le fichier de configuration contient 3 lignes le nombre d'Item "Attribut de la Table" nombres de transaction "enregistrement" minsup Exemple : 125 120000 50
Source
- /*==============================================================================
- * Auteur: Mr. Yermes Mohammed EL Amine
- *
- *
- * Copyright: Centre Universitaire Mustapha Stambouli, MASCARA
- *==============================================================================*/
-
- //---- apriori.java
-
- //---- input file need:
- //---- 1. config.txt
- //---- four lines, each line a integer
- //---- item number, transaction number , minsup
- //---- 2. transa.txt
-
- package apriori_algo ;
-
- import java.io.*;
- import java.lang.Integer.* ;
- import java.lang.Object.* ;
- import java.util.*;
- import org.jdom.*;
- import org.jdom.output.*;
- import java.lang.String.*;
- //-------------------------------------------------------------
- // Class Name : apriori
- // Purpose : main program class
- //-------------------------------------------------------------
- public class apriori_algo {
-
- public static void main(String[] args) throws IOException {
-
- aprioriProcess process1=new aprioriProcess();
- System.exit(0);
-
- }
- }
-
- //-------------------------------------------------------------
- // Class Name : aprioriProcess
- // Purpose : main processing class
- //-------------------------------------------------------------
- class aprioriProcess {
-
- //Nous allons commencer notre arborescence en crant la racine XML
- //qui sera ici "personnes".
- static Element racine ;//= new Element("Apriori");
-
- //On cre un nouveau Document JDOM bas sur la racine que l'on vient de crer
- static org.jdom.Document document ;// = new Document(racine);
-
- private final int HT=1; // state of tree node (hash table or
- private final int IL=2; // itemset list)
- int N; // total item #
- int M; // total transaction #
- int minsup ;
-
- Vector largeitemset = new Vector() ;
- Vector candidate = new Vector() ;
- Vector Support = new Vector() ;
-
- String fullitemset;
- String configfile = "config.txt" ;
- String transafile = "transa25.txt" ;
-
-
- //-------------------------------------------------------------
- // Class Name : candidateelement
- // Purpose : object that will be stored in Vector candidate
- // : include 2 item
- // : a hash tree and a candidate list
- //-------------------------------------------------------------
- class candidateelement {
- hashtreenode htroot;
- Vector candlist;
- }
-
-
- //-------------------------------------------------------------
- // Class Name : hashtreenode
- // Purpose : node of hash tree
- //-------------------------------------------------------------
- class hashtreenode {
- int nodeattr; // IL or HT
- int depth;
- Hashtable ht;
- Vector itemsetlist;
-
- public void hashtreenode() {
- nodeattr=HT;
- ht=new Hashtable();
- itemsetlist=new Vector();
- depth=0;
- }
-
- public void hashtreenode(int i) {
- nodeattr=i;
- ht=new Hashtable();
- itemsetlist=new Vector();
- depth=0;
- }
- }
-
-
- //-------------------------------------------------------------
- // Class Name : itemsetnode
- // Purpose : node of itemset
- //-------------------------------------------------------------
- class itemsetnode {
- String itemset;
- int counter;
-
- public itemsetnode(String s1,int i1) {
- itemset=new String(s1);
- counter=i1;
- }
-
- public itemsetnode() {
- itemset=new String();
- counter=0;
- }
-
- public String toString() {
- String tmp=new String();
- tmp=tmp.concat("<\"");
- tmp=tmp.concat(itemset);
- tmp=tmp.concat("\",");
- tmp=tmp.concat(Integer.toString(counter));
- tmp=tmp.concat(">");
- return tmp;
- }
- }
-
-
- //-------------------------------------------------------------
- // Method Name: printhashtree
- // Purpose : print the whole hash tree
- // Parameter : htn is a hashtreenode (when other method call this method,it is the root)
- // : transa : special transaction with all items occurr in it.
- // : a : recursive depth
- // Return :
- //-------------------------------------------------------------
- public void printhashtree(hashtreenode htn,String transa,int a) {
- if (htn.nodeattr == IL ) {
- System.out.println("Node is an itemset list");
- System.out.println(" depth :<"+htn.depth+">");
- System.out.println(" iteset:<"+htn.itemsetlist+">");
- }
- else { // HT
- System.out.println("Node is a hashtable");
- if (htn.ht==null)
- return;
- for (int b=a+1;b<=N;b++)
- if (htn.ht.containsKey(Integer.toString(getitemat(b,transa)))) {
- System.out.println(" key:<"+getitemat(b,transa));
- printhashtree((hashtreenode)htn.ht.get(Integer.toString(getitemat(b,transa))),transa,b);
- }
- }
- }
-
-
- //-------------------------------------------------------------
- // Method Name: getconfig
- // Purpose : open file config.txt
- // : get the total number of items of transaction file
- // : and the total number of transactions
- // : and minsup
- //-------------------------------------------------------------
- public void getconfig() throws IOException {
-
- FileInputStream file_in;
- DataInputStream data_in;
- String oneline=new String();
- int i=0;
-
- InputStreamReader input = new InputStreamReader(System.in);
- BufferedReader reader = new BufferedReader(input);
- String response = "";
-
- System.out.println("Appuyer sur 'C' changer la configuration and le fichier de transaction par défault");
- System.out.print("Ou sur n'import quelle touche pour continuer. ");
- try {
- response = reader.readLine();
- } catch (Exception e) {
- System.out.println(e);
- }
-
- int res=response.compareTo("C") * response.compareTo("c");
-
- if(res == 0) {
- System.out.print("\nEnter new transaction filename: ");
- try {
- transafile = reader.readLine();
- } catch (Exception e) {
- System.out.println(e);
- }
- System.out.print("Enter new configuration filename: ");
- try {
- configfile = reader.readLine();
- } catch (Exception e) {
- System.out.println(e);
- }
- System.out.println("Filenames changed");
- }
-
- try {
- file_in = new FileInputStream(configfile);
- data_in = new DataInputStream(file_in);
-
- oneline=data_in.readLine();
- N=Integer.valueOf(oneline).intValue();
- oneline=data_in.readLine();
- M=Integer.valueOf(oneline).intValue();
- oneline=data_in.readLine();
- minsup=Integer.valueOf(oneline).intValue();
- System.out.print("\n configuration: "+N+" items, "+M+" transactions, ");
- System.out.println("minsup = "+minsup+"%");
- System.out.println();
- } catch (IOException e) {
- System.out.println(e);
- }
- }
-
-
- //-------------------------------------------------------------
- // Method Name: getitemat
- // Purpose : get an item from an itemset
- // : get the total number of items of transaction file
- // Parameter : int i : i-th item ; itemset : string itemset
- // Return : int : the item at i-th in the itemset
- //-------------------------------------------------------------
- public int getitemat(int i,String itemset) {
-
- String str1=new String(itemset);
- StringTokenizer st=new StringTokenizer(itemset);
- int j;
-
- if (i > st.countTokens())
- System.out.println("eRRor! in getitemat, !!!!");
-
- for (j=1;j<=i;j++)
- str1=st.nextToken();
-
- return(Integer.valueOf(str1).intValue());
- }
-
-
- //-------------------------------------------------------------
- // Method Name: itesetsize
- // Purpose : get item number of an itemset
- // Parameter : itemset : string itemset
- // Return : int : the number of item of the itemset
- //-------------------------------------------------------------
- public int itemsetsize(String itemset) {
- StringTokenizer st=new StringTokenizer(itemset);
- return st.countTokens();
- }
-
-
- //-------------------------------------------------------------
- // Method Name: gensubset
- // Purpose : generate all subset given an itemset
- // Parameter : itemset
- // Return : a string contains all subset deliminated by ","
- // : e.g. "1 2,1 3,2 3" is subset of "1 2 3"
- //-------------------------------------------------------------
- public String gensubset(String itemset) {
-
- int len=itemsetsize(itemset);
- int i,j;
- String str1;
- String str2=new String();
- String str3=new String();
-
- if (len==1)
- return null;
- for (i=1;i<=len;i++) {
- StringTokenizer st=new StringTokenizer(itemset);
- str1=new String();
- for (j=1;j<i;j++) {
- str1=str1.concat(st.nextToken());
- str1=str1.concat(" ");
- }
- str2=st.nextToken();
- for (j=i+1;j<=len;j++) {
- str1=str1.concat(st.nextToken());
- str1=str1.concat(" ");
- }
- if (i!=1)
- str3=str3.concat(",");
- str3=str3.concat(str1.trim());
- }
-
- return str3;
-
- } //end public String gensubset(String itemset)
-
-
- //-------------------------------------------------------------
- // Method Name: createcandidate
- // Purpose : generate candidate n-itemset
- // Parameter : int n : n-itemset
- // Return : Vector : candidate is stored in a Vector
- //-------------------------------------------------------------
- public Vector createcandidate(int n) {
-
- Vector tempcandlist=new Vector();
- Vector ln_1=new Vector();
- int i,j,length1;
- String cand1=new String();
- String cand2=new String();
- String newcand=new String();
-
- //System.out.println("Generating "+n+"-candidate item set ....");
- if (n==1)
- for (i=1;i<=N;i++)
- tempcandlist.addElement(Integer.toString(i));
- else {
- ln_1=(Vector)largeitemset.elementAt(n-2);
- length1=ln_1.size();
- for (i=0;i<length1;i++) {
- cand1=(String)ln_1.elementAt(i);
- for (j=i+1;j<length1;j++) {
- cand2=(String)ln_1.elementAt(j);
- newcand=new String();
- if (n==2) {
- newcand=cand1.concat(" ");
- newcand=newcand.concat(cand2);
- tempcandlist.addElement(newcand.trim());
- }
- else {
- int c,i1,i2;
- boolean same=true;
-
- for (c=1;c<=n-2;c++) {
- i1=getitemat(c,cand1);
- i2=getitemat(c,cand2);
- if ( i1!=i2 ) {
- same=false;
- break;
- }
- else {
- newcand=newcand.concat(" ");
- newcand=newcand.concat(Integer.toString(i1));
- }
- }
- if (same) {
- i1=getitemat(n-1,cand1);
- i2=getitemat(n-1,cand2);
- newcand=newcand.concat(" ");
- newcand=newcand.concat(Integer.toString(i1));
- newcand=newcand.concat(" ");
- newcand=newcand.concat(Integer.toString(i2));
- tempcandlist.addElement(newcand.trim());
- }
- } //end if n==2 else
- } //end for j
- } //end for i
- } //end if n==1 else
-
- if (n<=2)
- return tempcandlist;
-
- Vector newcandlist=new Vector();
- for (int c=0; c<tempcandlist.size(); c++) {
- String c1=(String)tempcandlist.elementAt(c);
- String subset=gensubset(c1);
- StringTokenizer stsubset=new StringTokenizer(subset,",");
- boolean fake=false;
- while (stsubset.hasMoreTokens())
- if (!ln_1.contains(stsubset.nextToken())) {
- fake=true;
- break;
- }
- if (!fake)
- newcandlist.addElement(c1);
- }
-
- return newcandlist;
-
- } //end public createcandidate(int n)
-
-
- //-------------------------------------------------------------
- // Method Name: createcandidatehashtre
- // Purpose : generate candidate hash tree
- // Parameter : int n : n-itemset
- // Return : hashtreenode : root of the hashtree
- //-------------------------------------------------------------
- public hashtreenode createcandidatehashtree(int n) {
-
- int i,len1;
- hashtreenode htn=new hashtreenode();
-
- //System.out.println("Generating candidate "+n+"-itemset hashtree ....");
- if (n==1)
- htn.nodeattr=IL;
- else
- htn.nodeattr=HT;
-
- len1=((candidateelement)candidate.elementAt(n-1)).candlist.size();
- for (i=1;i<=len1;i++) {
- String cand1=new String();
- cand1=(String)((candidateelement)candidate.elementAt(n-1)).candlist.elementAt(i-1);
- genhash(1,htn,cand1);
- }
-
- return htn;
-
- } //end public createcandidatehashtree(int n)
-
-
- //-------------------------------------------------------------
- // Method Name: genhash
- // Purpose : called by createcandidatehashtree
- // : recursively generate hash tree node
- // Parameter : htnf is a hashtreenode (when other method call this method,it is the root)
- // : cand : candidate itemset string
- // : int i : recursive depth,from i-th item, recursive
- // Return :
- //-------------------------------------------------------------
- public void genhash(int i, hashtreenode htnf, String cand) {
-
- int n=itemsetsize(cand);
- if (i==n) {
- htnf.nodeattr=IL;
- htnf.depth=n;
- itemsetnode isn=new itemsetnode(cand,0);
- if (htnf.itemsetlist==null)
- htnf.itemsetlist=new Vector();
- htnf.itemsetlist.addElement(isn);
- }
- else {
- if (htnf.ht==null)
- htnf.ht=new Hashtable(HT);
- if (htnf.ht.containsKey(Integer.toString(getitemat(i,cand)))) {
- htnf=(hashtreenode)htnf.ht.get(Integer.toString(getitemat(i,cand)));
- genhash(i+1,htnf,cand);
- }
- else {
- hashtreenode htn=new hashtreenode();
- htnf.ht.put(Integer.toString(getitemat(i,cand)),htn);
- if (i==n-1) {
- htn.nodeattr=IL;
- Vector isl=new Vector();
- htn.itemsetlist=isl;
- genhash(i+1,htn,cand);
- }
- else {
- htn.nodeattr=HT;
- Hashtable ht=new Hashtable();
- htn.ht=ht;
- genhash(i+1,htn,cand);
- }
- }
- }
- } //end public void genhash(int i, hashtreenode htnf, String cand)
-
-
- //-------------------------------------------------------------
- // Method Name: createlargeitemset
- // Purpose : find all itemset which have their counters>=minsup
- // Parameter : int n : n-itemset
- // Return :
- //-------------------------------------------------------------
- public void createlargeitemset(int n) {
-
- Vector candlist=new Vector();
- Vector lis=new Vector(); //large item set
- hashtreenode htn=new hashtreenode();
- int i;
-
- // System.out.println("Generating "+n+"-large item set ....");
- candlist=((candidateelement)candidate.elementAt(n-1)).candlist;
- htn=((candidateelement)candidate.elementAt(n-1)).htroot;
-
- getlargehash(0,htn,fullitemset,lis);
-
- largeitemset.addElement(lis);
-
- } // end public void createlargeitemset(int n)
-
-
- //-------------------------------------------------------------
- // Method Name: getlargehash
- // Purpose : recursively traverse candidate hash tree
- // : to find all large itemset
- // Parameter : htnf is a hashtreenode (when other method call this method,it is the root)
- // : cand : candidate itemset string
- // : int i : recursive depth
- // : Vector lis : Vector that stores large itemsets
- // Return :
- //-------------------------------------------------------------
- public void getlargehash(int i,hashtreenode htnf,String transa,Vector lis) {
-
- Vector tempvec=new Vector();
- int j;
-
- if (htnf.nodeattr==IL) {
- tempvec=htnf.itemsetlist;
- for (j=1;j<=tempvec.size();j++)
- if (((itemsetnode)tempvec.elementAt(j-1)).counter >= ((minsup * M) / 100))
- {
- lis.addElement( ((itemsetnode)tempvec.elementAt(j-1)).itemset ) ;
- Support.addElement(((itemsetnode)tempvec.elementAt(j-1)).counter ) ;
- }
-
- }
- else {
- if (htnf.ht==null)
- return;
- for (int b=i+1;b<=N;b++)
- {
- if (htnf.ht.containsKey(Integer.toString(getitemat(b,transa))))
- getlargehash(b,(hashtreenode)htnf.ht.get(Integer.toString(getitemat(b,transa))),transa,lis);
- }
-
- }
- }
-
-
- //-------------------------------------------------------------
- // Method Name: transatraverse
- // Purpose : read each transaction, traverse hashtree,
- // incrment approporiate itemset counter.
- // Parameter : int n : n-itemset
- // Return :
- //-------------------------------------------------------------
- public void transatraverse(int n) {
-
- FileInputStream file_in;
- DataInputStream data_in;
- String oneline=new String();
- int i=0,j=0,len=0;
- String transa;
- hashtreenode htn=new hashtreenode();
- StringTokenizer st;
- String str0;
- int numRead=0;
-
- //System.out.println("Traverse "+n+"-candidate hashtree ... ");
- htn=((candidateelement)candidate.elementAt(n-1)).htroot;
- try {
- file_in = new FileInputStream(transafile);
- data_in = new DataInputStream(file_in);
-
- while ( true ) {
- transa=new String();
- oneline=data_in.readLine();
- numRead++;
- if ((oneline==null)||(numRead > M))
- break;
- st=new StringTokenizer(oneline.trim());
- j=0;
- while ((st.hasMoreTokens()) && j < N) {
- j++;
- str0=st.nextToken();
- i=Integer.valueOf(str0).intValue();
- if (i!=0) {
- transa=transa.concat(" ");
- transa=transa.concat(Integer.toString(j));
- len++;
- }
- }
- transa=transa.trim();
- //transa=oneline.trim();
- //System.out.println(transa);
- transatrahash(0,htn,transa);
- }
- } catch (IOException e) {
- System.out.println(e);
- }
- }
-
-
- //-------------------------------------------------------------
- // Method Name: transatrahash
- // Purpose : called by transatraverse
- // : recursively traverse hash tree
- // Parameter : htnf is a hashtreenode (when other method call this method,it is the root)
- // : cand : candidate itemset string
- // : int i : recursive depth,from i-th item, recursive
- // Return :
- //-------------------------------------------------------------
- public void transatrahash(int i,hashtreenode htnf,String transa) {
-
- String stris=new String();
- Vector itemsetlist=new Vector();
- int j,lastpos,len,d;
- itemsetnode tmpnode=new itemsetnode();
-
- if (htnf.nodeattr==IL) {
- itemsetlist=(Vector)htnf.itemsetlist;
- len=itemsetlist.size();
- for (j=0;j<len;j++) {
- tmpnode=(itemsetnode)itemsetlist.elementAt(j);
- d=getitemat(htnf.depth,tmpnode.itemset);
- String v =Integer.toString(d) ;
- lastpos=transa.indexOf(" "+v+" ");
- if (lastpos!=-1)
- ((itemsetnode)(itemsetlist.elementAt(j))).counter++;
- }
- //return;
- }
- else //HT
- for (int b=i+1;b<=itemsetsize(transa);b++)
- if (htnf.ht.containsKey(Integer.toString(getitemat(b,transa))))
- transatrahash(i,(hashtreenode)htnf.ht.get(Integer.toString(getitemat(b,transa))),transa);
-
- } // public transatrahash(int ii,hashtreenode htnf,String transa)
-
-
- //-------------------------------------------------------------
- // Method Name: aprioriProcess()
- // Purpose : main processing method
- // Parameters :
- // Return :
- //-------------------------------------------------------------
- public aprioriProcess() throws IOException {
-
- candidateelement cande;
- int k=0;
- Vector large=new Vector();
- Date d=new Date();
- long s1,s2;
-
- System.out.println();
- System.out.println("Algorithm apriori starting now.....");
- System.out.println();
-
- getconfig();
-
- fullitemset=new String();
-
- fullitemset=fullitemset.concat("1");
- for (int i=2;i<=N;i++) {
- fullitemset=fullitemset.concat(" ");
- fullitemset=fullitemset.concat(Integer.toString(i));
- }
-
- d=new Date();
- s1=d.getTime();
-
-
- while (true) {
- k++;
- cande=new candidateelement();
- cande.candlist=createcandidate(k);
-
-
-
- //System.out.println("C"+k+"("+k+"-candidate-itemset): "+cande.candlist);
-
- if (cande.candlist.isEmpty())
- break;
-
- cande.htroot=null;
- candidate.addElement(cande);
-
- ((candidateelement)candidate.elementAt(k-1)).htroot=createcandidatehashtree(k);
-
- System.out.println("\nNow reading transactions, increment counters of itemset");
- transatraverse(k);
-
- createlargeitemset(k);
- System.out.println("\nFrequent "+k+"-itemsets:");
- System.out.println((Vector)(largeitemset.elementAt(k-1)));
-
- String itemfrequent =String.valueOf(largeitemset.elementAt(k-1));
-
- itemfrequent=itemfrequent.replace("[",",");
- itemfrequent=itemfrequent.replace("]",",");
- StringTokenizer sttt=new StringTokenizer(itemfrequent,",");
-
- racine = new Element("Apriori");
- document = new Document(racine);
-
- Element Frequent = new Element("Frequent");
- racine.addContent(Frequent);
- String h= String.valueOf(k);
- Attribute Niveau = new Attribute("Niveau",h);
- Frequent.setAttribute(Niveau);
-
- int o=1;
- while (sttt.hasMoreTokens()) {
-
- String hh = String.valueOf(o);
- Element itemfreqent = new Element("itemfreqent");
- Frequent.addContent(itemfreqent);
-
- Attribute Num = new Attribute("Num",hh);
- Attribute support = new Attribute("Support",String.valueOf(Support.elementAt(o-1)));
-
- itemfreqent.setAttribute(Num);
- itemfreqent.setAttribute(support);
- String fer =sttt.nextToken().toString();
-
- itemfreqent.setText(fer);
-
- o++;
- }
- enregistre("Frequents du Niveau "+k+".xml");
- //affiche();
- Support = new Vector() ;
- }
-
- hashtreenode htn=new hashtreenode();
- htn=((candidateelement)candidate.elementAt(k-2)).htroot;
-
- d=new Date();
- s2=d.getTime();
- System.out.println();
-
- System.out.println("Execution time is: "+((s2-s1)/1000) + " seconds.");
-
- System.out.println("End.");
-
- //affiche();
- //enregistre("Itemfrequent.xml");
-
- }
- //==============================================================================
- //
- // Afficher le contenue du fichier XML
- //
- //==============================================================================
- static void affiche()
- {
- try
- {
- //On utilise ici un affichage classique avec getPrettyFormat()
- XMLOutputter sortie = new XMLOutputter(Format.getPrettyFormat());
- sortie.output(document, System.out);
- }
- catch (java.io.IOException e){}
- }
-
- //==============================================================================
- //
- // Enregistrer dans le fichier XML
- //
- //==============================================================================
-
- static void enregistre(String fichier)
- {
- try
- {
- //On utilise ici un affichage classique avec getPrettyFormat()
- XMLOutputter sortie = new XMLOutputter(Format.getPrettyFormat());
- //Remarquez qu'il suffit simplement de crer une instance de FileOutputStream
- //avec en argument le nom du fichier pour effectuer la srialisation.
- sortie.output(document, new FileOutputStream(fichier));
- }
- catch (java.io.IOException e){}
- }
-
- //==============================================================================
- //
- //
- // Apriori Parametrer
- //
- //
- //==============================================================================
-
-
-
- }
/*==============================================================================
* Auteur: Mr. Yermes Mohammed EL Amine
*
*
* Copyright: Centre Universitaire Mustapha Stambouli, MASCARA
*==============================================================================*/
//---- apriori.java
//---- input file need:
//---- 1. config.txt
//---- four lines, each line a integer
//---- item number, transaction number , minsup
//---- 2. transa.txt
package apriori_algo ;
import java.io.*;
import java.lang.Integer.* ;
import java.lang.Object.* ;
import java.util.*;
import org.jdom.*;
import org.jdom.output.*;
import java.lang.String.*;
//-------------------------------------------------------------
// Class Name : apriori
// Purpose : main program class
//-------------------------------------------------------------
public class apriori_algo {
public static void main(String[] args) throws IOException {
aprioriProcess process1=new aprioriProcess();
System.exit(0);
}
}
//-------------------------------------------------------------
// Class Name : aprioriProcess
// Purpose : main processing class
//-------------------------------------------------------------
class aprioriProcess {
//Nous allons commencer notre arborescence en crant la racine XML
//qui sera ici "personnes".
static Element racine ;//= new Element("Apriori");
//On cre un nouveau Document JDOM bas sur la racine que l'on vient de crer
static org.jdom.Document document ;// = new Document(racine);
private final int HT=1; // state of tree node (hash table or
private final int IL=2; // itemset list)
int N; // total item #
int M; // total transaction #
int minsup ;
Vector largeitemset = new Vector() ;
Vector candidate = new Vector() ;
Vector Support = new Vector() ;
String fullitemset;
String configfile = "config.txt" ;
String transafile = "transa25.txt" ;
//-------------------------------------------------------------
// Class Name : candidateelement
// Purpose : object that will be stored in Vector candidate
// : include 2 item
// : a hash tree and a candidate list
//-------------------------------------------------------------
class candidateelement {
hashtreenode htroot;
Vector candlist;
}
//-------------------------------------------------------------
// Class Name : hashtreenode
// Purpose : node of hash tree
//-------------------------------------------------------------
class hashtreenode {
int nodeattr; // IL or HT
int depth;
Hashtable ht;
Vector itemsetlist;
public void hashtreenode() {
nodeattr=HT;
ht=new Hashtable();
itemsetlist=new Vector();
depth=0;
}
public void hashtreenode(int i) {
nodeattr=i;
ht=new Hashtable();
itemsetlist=new Vector();
depth=0;
}
}
//-------------------------------------------------------------
// Class Name : itemsetnode
// Purpose : node of itemset
//-------------------------------------------------------------
class itemsetnode {
String itemset;
int counter;
public itemsetnode(String s1,int i1) {
itemset=new String(s1);
counter=i1;
}
public itemsetnode() {
itemset=new String();
counter=0;
}
public String toString() {
String tmp=new String();
tmp=tmp.concat("<\"");
tmp=tmp.concat(itemset);
tmp=tmp.concat("\",");
tmp=tmp.concat(Integer.toString(counter));
tmp=tmp.concat(">");
return tmp;
}
}
//-------------------------------------------------------------
// Method Name: printhashtree
// Purpose : print the whole hash tree
// Parameter : htn is a hashtreenode (when other method call this method,it is the root)
// : transa : special transaction with all items occurr in it.
// : a : recursive depth
// Return :
//-------------------------------------------------------------
public void printhashtree(hashtreenode htn,String transa,int a) {
if (htn.nodeattr == IL ) {
System.out.println("Node is an itemset list");
System.out.println(" depth :<"+htn.depth+">");
System.out.println(" iteset:<"+htn.itemsetlist+">");
}
else { // HT
System.out.println("Node is a hashtable");
if (htn.ht==null)
return;
for (int b=a+1;b<=N;b++)
if (htn.ht.containsKey(Integer.toString(getitemat(b,transa)))) {
System.out.println(" key:<"+getitemat(b,transa));
printhashtree((hashtreenode)htn.ht.get(Integer.toString(getitemat(b,transa))),transa,b);
}
}
}
//-------------------------------------------------------------
// Method Name: getconfig
// Purpose : open file config.txt
// : get the total number of items of transaction file
// : and the total number of transactions
// : and minsup
//-------------------------------------------------------------
public void getconfig() throws IOException {
FileInputStream file_in;
DataInputStream data_in;
String oneline=new String();
int i=0;
InputStreamReader input = new InputStreamReader(System.in);
BufferedReader reader = new BufferedReader(input);
String response = "";
System.out.println("Appuyer sur 'C' changer la configuration and le fichier de transaction par défault");
System.out.print("Ou sur n'import quelle touche pour continuer. ");
try {
response = reader.readLine();
} catch (Exception e) {
System.out.println(e);
}
int res=response.compareTo("C") * response.compareTo("c");
if(res == 0) {
System.out.print("\nEnter new transaction filename: ");
try {
transafile = reader.readLine();
} catch (Exception e) {
System.out.println(e);
}
System.out.print("Enter new configuration filename: ");
try {
configfile = reader.readLine();
} catch (Exception e) {
System.out.println(e);
}
System.out.println("Filenames changed");
}
try {
file_in = new FileInputStream(configfile);
data_in = new DataInputStream(file_in);
oneline=data_in.readLine();
N=Integer.valueOf(oneline).intValue();
oneline=data_in.readLine();
M=Integer.valueOf(oneline).intValue();
oneline=data_in.readLine();
minsup=Integer.valueOf(oneline).intValue();
System.out.print("\n configuration: "+N+" items, "+M+" transactions, ");
System.out.println("minsup = "+minsup+"%");
System.out.println();
} catch (IOException e) {
System.out.println(e);
}
}
//-------------------------------------------------------------
// Method Name: getitemat
// Purpose : get an item from an itemset
// : get the total number of items of transaction file
// Parameter : int i : i-th item ; itemset : string itemset
// Return : int : the item at i-th in the itemset
//-------------------------------------------------------------
public int getitemat(int i,String itemset) {
String str1=new String(itemset);
StringTokenizer st=new StringTokenizer(itemset);
int j;
if (i > st.countTokens())
System.out.println("eRRor! in getitemat, !!!!");
for (j=1;j<=i;j++)
str1=st.nextToken();
return(Integer.valueOf(str1).intValue());
}
//-------------------------------------------------------------
// Method Name: itesetsize
// Purpose : get item number of an itemset
// Parameter : itemset : string itemset
// Return : int : the number of item of the itemset
//-------------------------------------------------------------
public int itemsetsize(String itemset) {
StringTokenizer st=new StringTokenizer(itemset);
return st.countTokens();
}
//-------------------------------------------------------------
// Method Name: gensubset
// Purpose : generate all subset given an itemset
// Parameter : itemset
// Return : a string contains all subset deliminated by ","
// : e.g. "1 2,1 3,2 3" is subset of "1 2 3"
//-------------------------------------------------------------
public String gensubset(String itemset) {
int len=itemsetsize(itemset);
int i,j;
String str1;
String str2=new String();
String str3=new String();
if (len==1)
return null;
for (i=1;i<=len;i++) {
StringTokenizer st=new StringTokenizer(itemset);
str1=new String();
for (j=1;j<i;j++) {
str1=str1.concat(st.nextToken());
str1=str1.concat(" ");
}
str2=st.nextToken();
for (j=i+1;j<=len;j++) {
str1=str1.concat(st.nextToken());
str1=str1.concat(" ");
}
if (i!=1)
str3=str3.concat(",");
str3=str3.concat(str1.trim());
}
return str3;
} //end public String gensubset(String itemset)
//-------------------------------------------------------------
// Method Name: createcandidate
// Purpose : generate candidate n-itemset
// Parameter : int n : n-itemset
// Return : Vector : candidate is stored in a Vector
//-------------------------------------------------------------
public Vector createcandidate(int n) {
Vector tempcandlist=new Vector();
Vector ln_1=new Vector();
int i,j,length1;
String cand1=new String();
String cand2=new String();
String newcand=new String();
//System.out.println("Generating "+n+"-candidate item set ....");
if (n==1)
for (i=1;i<=N;i++)
tempcandlist.addElement(Integer.toString(i));
else {
ln_1=(Vector)largeitemset.elementAt(n-2);
length1=ln_1.size();
for (i=0;i<length1;i++) {
cand1=(String)ln_1.elementAt(i);
for (j=i+1;j<length1;j++) {
cand2=(String)ln_1.elementAt(j);
newcand=new String();
if (n==2) {
newcand=cand1.concat(" ");
newcand=newcand.concat(cand2);
tempcandlist.addElement(newcand.trim());
}
else {
int c,i1,i2;
boolean same=true;
for (c=1;c<=n-2;c++) {
i1=getitemat(c,cand1);
i2=getitemat(c,cand2);
if ( i1!=i2 ) {
same=false;
break;
}
else {
newcand=newcand.concat(" ");
newcand=newcand.concat(Integer.toString(i1));
}
}
if (same) {
i1=getitemat(n-1,cand1);
i2=getitemat(n-1,cand2);
newcand=newcand.concat(" ");
newcand=newcand.concat(Integer.toString(i1));
newcand=newcand.concat(" ");
newcand=newcand.concat(Integer.toString(i2));
tempcandlist.addElement(newcand.trim());
}
} //end if n==2 else
} //end for j
} //end for i
} //end if n==1 else
if (n<=2)
return tempcandlist;
Vector newcandlist=new Vector();
for (int c=0; c<tempcandlist.size(); c++) {
String c1=(String)tempcandlist.elementAt(c);
String subset=gensubset(c1);
StringTokenizer stsubset=new StringTokenizer(subset,",");
boolean fake=false;
while (stsubset.hasMoreTokens())
if (!ln_1.contains(stsubset.nextToken())) {
fake=true;
break;
}
if (!fake)
newcandlist.addElement(c1);
}
return newcandlist;
} //end public createcandidate(int n)
//-------------------------------------------------------------
// Method Name: createcandidatehashtre
// Purpose : generate candidate hash tree
// Parameter : int n : n-itemset
// Return : hashtreenode : root of the hashtree
//-------------------------------------------------------------
public hashtreenode createcandidatehashtree(int n) {
int i,len1;
hashtreenode htn=new hashtreenode();
//System.out.println("Generating candidate "+n+"-itemset hashtree ....");
if (n==1)
htn.nodeattr=IL;
else
htn.nodeattr=HT;
len1=((candidateelement)candidate.elementAt(n-1)).candlist.size();
for (i=1;i<=len1;i++) {
String cand1=new String();
cand1=(String)((candidateelement)candidate.elementAt(n-1)).candlist.elementAt(i-1);
genhash(1,htn,cand1);
}
return htn;
} //end public createcandidatehashtree(int n)
//-------------------------------------------------------------
// Method Name: genhash
// Purpose : called by createcandidatehashtree
// : recursively generate hash tree node
// Parameter : htnf is a hashtreenode (when other method call this method,it is the root)
// : cand : candidate itemset string
// : int i : recursive depth,from i-th item, recursive
// Return :
//-------------------------------------------------------------
public void genhash(int i, hashtreenode htnf, String cand) {
int n=itemsetsize(cand);
if (i==n) {
htnf.nodeattr=IL;
htnf.depth=n;
itemsetnode isn=new itemsetnode(cand,0);
if (htnf.itemsetlist==null)
htnf.itemsetlist=new Vector();
htnf.itemsetlist.addElement(isn);
}
else {
if (htnf.ht==null)
htnf.ht=new Hashtable(HT);
if (htnf.ht.containsKey(Integer.toString(getitemat(i,cand)))) {
htnf=(hashtreenode)htnf.ht.get(Integer.toString(getitemat(i,cand)));
genhash(i+1,htnf,cand);
}
else {
hashtreenode htn=new hashtreenode();
htnf.ht.put(Integer.toString(getitemat(i,cand)),htn);
if (i==n-1) {
htn.nodeattr=IL;
Vector isl=new Vector();
htn.itemsetlist=isl;
genhash(i+1,htn,cand);
}
else {
htn.nodeattr=HT;
Hashtable ht=new Hashtable();
htn.ht=ht;
genhash(i+1,htn,cand);
}
}
}
} //end public void genhash(int i, hashtreenode htnf, String cand)
//-------------------------------------------------------------
// Method Name: createlargeitemset
// Purpose : find all itemset which have their counters>=minsup
// Parameter : int n : n-itemset
// Return :
//-------------------------------------------------------------
public void createlargeitemset(int n) {
Vector candlist=new Vector();
Vector lis=new Vector(); //large item set
hashtreenode htn=new hashtreenode();
int i;
// System.out.println("Generating "+n+"-large item set ....");
candlist=((candidateelement)candidate.elementAt(n-1)).candlist;
htn=((candidateelement)candidate.elementAt(n-1)).htroot;
getlargehash(0,htn,fullitemset,lis);
largeitemset.addElement(lis);
} // end public void createlargeitemset(int n)
//-------------------------------------------------------------
// Method Name: getlargehash
// Purpose : recursively traverse candidate hash tree
// : to find all large itemset
// Parameter : htnf is a hashtreenode (when other method call this method,it is the root)
// : cand : candidate itemset string
// : int i : recursive depth
// : Vector lis : Vector that stores large itemsets
// Return :
//-------------------------------------------------------------
public void getlargehash(int i,hashtreenode htnf,String transa,Vector lis) {
Vector tempvec=new Vector();
int j;
if (htnf.nodeattr==IL) {
tempvec=htnf.itemsetlist;
for (j=1;j<=tempvec.size();j++)
if (((itemsetnode)tempvec.elementAt(j-1)).counter >= ((minsup * M) / 100))
{
lis.addElement( ((itemsetnode)tempvec.elementAt(j-1)).itemset ) ;
Support.addElement(((itemsetnode)tempvec.elementAt(j-1)).counter ) ;
}
}
else {
if (htnf.ht==null)
return;
for (int b=i+1;b<=N;b++)
{
if (htnf.ht.containsKey(Integer.toString(getitemat(b,transa))))
getlargehash(b,(hashtreenode)htnf.ht.get(Integer.toString(getitemat(b,transa))),transa,lis);
}
}
}
//-------------------------------------------------------------
// Method Name: transatraverse
// Purpose : read each transaction, traverse hashtree,
// incrment approporiate itemset counter.
// Parameter : int n : n-itemset
// Return :
//-------------------------------------------------------------
public void transatraverse(int n) {
FileInputStream file_in;
DataInputStream data_in;
String oneline=new String();
int i=0,j=0,len=0;
String transa;
hashtreenode htn=new hashtreenode();
StringTokenizer st;
String str0;
int numRead=0;
//System.out.println("Traverse "+n+"-candidate hashtree ... ");
htn=((candidateelement)candidate.elementAt(n-1)).htroot;
try {
file_in = new FileInputStream(transafile);
data_in = new DataInputStream(file_in);
while ( true ) {
transa=new String();
oneline=data_in.readLine();
numRead++;
if ((oneline==null)||(numRead > M))
break;
st=new StringTokenizer(oneline.trim());
j=0;
while ((st.hasMoreTokens()) && j < N) {
j++;
str0=st.nextToken();
i=Integer.valueOf(str0).intValue();
if (i!=0) {
transa=transa.concat(" ");
transa=transa.concat(Integer.toString(j));
len++;
}
}
transa=transa.trim();
//transa=oneline.trim();
//System.out.println(transa);
transatrahash(0,htn,transa);
}
} catch (IOException e) {
System.out.println(e);
}
}
//-------------------------------------------------------------
// Method Name: transatrahash
// Purpose : called by transatraverse
// : recursively traverse hash tree
// Parameter : htnf is a hashtreenode (when other method call this method,it is the root)
// : cand : candidate itemset string
// : int i : recursive depth,from i-th item, recursive
// Return :
//-------------------------------------------------------------
public void transatrahash(int i,hashtreenode htnf,String transa) {
String stris=new String();
Vector itemsetlist=new Vector();
int j,lastpos,len,d;
itemsetnode tmpnode=new itemsetnode();
if (htnf.nodeattr==IL) {
itemsetlist=(Vector)htnf.itemsetlist;
len=itemsetlist.size();
for (j=0;j<len;j++) {
tmpnode=(itemsetnode)itemsetlist.elementAt(j);
d=getitemat(htnf.depth,tmpnode.itemset);
String v =Integer.toString(d) ;
lastpos=transa.indexOf(" "+v+" ");
if (lastpos!=-1)
((itemsetnode)(itemsetlist.elementAt(j))).counter++;
}
//return;
}
else //HT
for (int b=i+1;b<=itemsetsize(transa);b++)
if (htnf.ht.containsKey(Integer.toString(getitemat(b,transa))))
transatrahash(i,(hashtreenode)htnf.ht.get(Integer.toString(getitemat(b,transa))),transa);
} // public transatrahash(int ii,hashtreenode htnf,String transa)
//-------------------------------------------------------------
// Method Name: aprioriProcess()
// Purpose : main processing method
// Parameters :
// Return :
//-------------------------------------------------------------
public aprioriProcess() throws IOException {
candidateelement cande;
int k=0;
Vector large=new Vector();
Date d=new Date();
long s1,s2;
System.out.println();
System.out.println("Algorithm apriori starting now.....");
System.out.println();
getconfig();
fullitemset=new String();
fullitemset=fullitemset.concat("1");
for (int i=2;i<=N;i++) {
fullitemset=fullitemset.concat(" ");
fullitemset=fullitemset.concat(Integer.toString(i));
}
d=new Date();
s1=d.getTime();
while (true) {
k++;
cande=new candidateelement();
cande.candlist=createcandidate(k);
//System.out.println("C"+k+"("+k+"-candidate-itemset): "+cande.candlist);
if (cande.candlist.isEmpty())
break;
cande.htroot=null;
candidate.addElement(cande);
((candidateelement)candidate.elementAt(k-1)).htroot=createcandidatehashtree(k);
System.out.println("\nNow reading transactions, increment counters of itemset");
transatraverse(k);
createlargeitemset(k);
System.out.println("\nFrequent "+k+"-itemsets:");
System.out.println((Vector)(largeitemset.elementAt(k-1)));
String itemfrequent =String.valueOf(largeitemset.elementAt(k-1));
itemfrequent=itemfrequent.replace("[",",");
itemfrequent=itemfrequent.replace("]",",");
StringTokenizer sttt=new StringTokenizer(itemfrequent,",");
racine = new Element("Apriori");
document = new Document(racine);
Element Frequent = new Element("Frequent");
racine.addContent(Frequent);
String h= String.valueOf(k);
Attribute Niveau = new Attribute("Niveau",h);
Frequent.setAttribute(Niveau);
int o=1;
while (sttt.hasMoreTokens()) {
String hh = String.valueOf(o);
Element itemfreqent = new Element("itemfreqent");
Frequent.addContent(itemfreqent);
Attribute Num = new Attribute("Num",hh);
Attribute support = new Attribute("Support",String.valueOf(Support.elementAt(o-1)));
itemfreqent.setAttribute(Num);
itemfreqent.setAttribute(support);
String fer =sttt.nextToken().toString();
itemfreqent.setText(fer);
o++;
}
enregistre("Frequents du Niveau "+k+".xml");
//affiche();
Support = new Vector() ;
}
hashtreenode htn=new hashtreenode();
htn=((candidateelement)candidate.elementAt(k-2)).htroot;
d=new Date();
s2=d.getTime();
System.out.println();
System.out.println("Execution time is: "+((s2-s1)/1000) + " seconds.");
System.out.println("End.");
//affiche();
//enregistre("Itemfrequent.xml");
}
//==============================================================================
//
// Afficher le contenue du fichier XML
//
//==============================================================================
static void affiche()
{
try
{
//On utilise ici un affichage classique avec getPrettyFormat()
XMLOutputter sortie = new XMLOutputter(Format.getPrettyFormat());
sortie.output(document, System.out);
}
catch (java.io.IOException e){}
}
//==============================================================================
//
// Enregistrer dans le fichier XML
//
//==============================================================================
static void enregistre(String fichier)
{
try
{
//On utilise ici un affichage classique avec getPrettyFormat()
XMLOutputter sortie = new XMLOutputter(Format.getPrettyFormat());
//Remarquez qu'il suffit simplement de crer une instance de FileOutputStream
//avec en argument le nom du fichier pour effectuer la srialisation.
sortie.output(document, new FileOutputStream(fichier));
}
catch (java.io.IOException e){}
}
//==============================================================================
//
//
// Apriori Parametrer
//
//
//==============================================================================
}
Conclusion
Le résultat serais dans un fichier XML
Historique
- 31 juillet 2008 19:12:37 :
- La précision dans l'enregistrement des Itemsets de chaque niveau dans un fichier XML
Sources du même auteur
Sources de la même categorie
Commentaires et avis
Discussions en rapport avec ce code source dans le forum
Débuter en java... [ par OriOn ]
Bonjour, voilà alors je voudrais me mettre à java, et je voudrais savoir qu'est ce qu'il faut que je télécharge pour pouvoir tester mes créations et q
Editeur Java [ par syndrael ]
Bonjour,Je débute et je voulais savoir quel éditeur vous utilisez de votre coté. Moi, je fais appel à JPADPro 3.6, ca change de la fenetre DOS !! LOL
interaction entre html et java via javascript [ par rmo ]
Bonjour à tous.Je cherche à trouver comment par une action sur un boutoon html, lancer une action dans une applet java.Merci.
Comment on fait pour simplement dessiner [ par MeltedMind ]
Bonjour, je me demandais comment l'on fait pour afficher un image en java. J'utilise Code Warrior pour java version 6.0, je suis un nouvel utilisateu
Icône pour application Java [ par Mikonyx ]
Est-il possible de remplacer la tasse de café présente dans toutes les applications Java par un icône personnel? Ah aussi... existe t'il un equivalent
chat multiclients (JAVA) [ par Yzermat ]
Je suis a la recherche d'un chat multiclients en java! Ce serait bien si il était assez bien commenté! C'est tres urgent et assez important , sinon je
Urgent : Broadcast en JAVA [ par skysee ]
Bonjour,Je voudrais réaliser en JAVA un broadcast sur un réseau pour en lister toutes les machines qui y sont connectées. L'affichage se réalisant com
Programmation BROADCAST en JAVA [ par skysee ]
Bonsoir,Je voudrais réaliser en JAVA un broadcast sur un réseau pour en lister tout les PC qui y sont connectées. L'affichage de ses PC se réalisant c
URGENT: Broadcast en JAVA [ par skysee ]
Bonjour,Je voudrais réaliser en JAVA un broadcast sur un réseau pour en lister toutes les machines qui y sont connectées. L'affichage se réalisant com
Compilateur JAVA [ par BobH ]
J'ai du formater mon disque et je n'ai plus j++ donc je cherche juste un compilateur, merci!
|
Derniers Blogs
UNE JOLIE-HORLOGE ET PAS QU'UN PEU !UNE JOLIE-HORLOGE ET PAS QU'UN PEU ! par neodante
Pour les possesseurs d'iPhone, ça y est Bijin Tokei - qui se traduit littéralement en Français par " Jolie Horloge " - est arrivé et GRATUITEMENT s'il vous plaît ! Après la version Tokyo, Hokkaido, night club, racing, Gal, "pour les mademoiselles'", . voi...
Cliquez pour lire la suite de l'article par neodante TECHDAYS PARIS 2010 : CONNECTEZ VOS DONNéES à SHAREPOINT 2010 AVEC LES BUSINESS CONNECTIVITY SERVICESTECHDAYS PARIS 2010 : CONNECTEZ VOS DONNéES à SHAREPOINT 2010 AVEC LES BUSINESS CONNECTIVITY SERVICES par ROMELARD Fabrice
Animé par: Gaetan Bouveret et Julien Chomarat Business Connectivity Services (BCS) est dans SharePoint 2010 la version 2 de Business Data Catalog (BDC dans SharePoint 2007). Il s'agit de la solution permettant de visualiser des données provenan...
Cliquez pour lire la suite de l'article par ROMELARD Fabrice [DIVERS] SUIVRE VOS SéRIES PRéFéRéS SUR LA TOILE[DIVERS] SUIVRE VOS SéRIES PRéFéRéS SUR LA TOILE par orion
Comme de nombreux geek, je suis un grand amateur de série TV et je rate régulièrement des épisodes de mes séries préférés. Une solution s'offre à vous avec ce merveilleux site : Tv Gorge - www.tvgorge.com Moteur de recherche à l'appui, vous pouvez ...
Cliquez pour lire la suite de l'article par orion TECHDAYS PARIS 2010 : LA BI DANS SHAREPOINT 2010TECHDAYS PARIS 2010 : LA BI DANS SHAREPOINT 2010 par ROMELARD Fabrice
Animé par: Vincent Bellet et Baptiste Giraudier La BI dans SharePoint 2010, Les nouveaux services d'application dans SP2010 et SQL Server Reporting services 2008 R2. La BI dans SharePoint est généralisée pour tous afin de permettre à tous les coll...
Cliquez pour lire la suite de l'article par ROMELARD Fabrice
Logiciels
DB-MAIN (9.1.0)DB-MAIN (9.1.0)DB-MAIN is a data-modeling and data-architecture tool. It is designed to help developers and anal... Cliquez pour télécharger DB-MAIN Xilisoft DPG Convertisseur (5.1.37.0120)XILISOFT DPG CONVERTISSEUR (5.1.37.0120)Xilisoft DPG Convertisseur offre aux fans de Nintendo DS une bonne solution leur permettant de dé... Cliquez pour télécharger Xilisoft DPG Convertisseur GraphicsGale (2.01.01)GRAPHICSGALE (2.01.01)GraphicsGale est un logiciel de PixelArt avec de nombreuse fonctionnalités permettant de réalisé ... Cliquez pour télécharger GraphicsGale Architecte 3D (Platinum 2010)ARCHITECTE 3D (PLATINUM 2010)Architecte 3D Platinium vous permet de concevoir facilement les plans votre future maison, de l'é... Cliquez pour télécharger Architecte 3D TeamViewer 5 (TeamViewer 5)TEAMVIEWER 5 (TEAMVIEWER 5)Dépanner un ami,expliquer une manipulation devient un jeu d'enfant.
Prise en main d'un autre ord... Cliquez pour télécharger TeamViewer 5
Comparez les prix

HTC Hero
Entre 550€ et 550€
|