* Attribute.java
* Copyright (C) 1999 Pierre Geurts
*
* This program is free software; you can redistribute it and/or modify
* it under the terms of the GNU General Public License as published by
* the Free Software Foundation; either version 2 of the License, or
* (at your option) any later version.
*
* This program is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
* GNU General Public License for more details.
*
* You should have received a copy of the GNU General Public License
* along with this program; if not, write to the Free Software
* Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
*/
import java.io.*;
abstract class Attribute{
/* the name of the attributes */
String name;
/* the database of the attributes */
Database db;
/* attribute index in the database */
int index;
/* the lastbestscore of this attribute */
double lastbestscore;
public Object Value(Obj o) {
return o.attributesvalues.elementAt(index);
}
abstract void SetAttValue(Obj o,Object s);
public String toString() {
return name;
}
abstract String describe();
abstract String describeBestTest();
abstract int ReadAttValue(Obj o,StreamTokenizer stt);
// compute the best score we can obtain with this attribute
abstract double bestscore(ObjectSet os, SymbAtt goal);
// effectively compute the partition resulting from this best score
abstract Partition bestpartition(ObjectSet os, SymbAtt goal);
}
----------------------
/*
* BuildDt.java
* Copyright (C) 1999 Pierre Geurts
*
* This program is free software; you can redistribute it and/or modify
* it under the terms of the GNU General Public License as published by
* the Free Software Foundation; either version 2 of the License, or
* (at your option) any later version.
*
* This program is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
* GNU General Public License for more details.
*
* You should have received a copy of the GNU General Public License
* along with this program; if not, write to the Free Software
* Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
*/
import java.util.*;
import java.net.*;
/**
* examples:
* java buildDt database/omib.db security 700
* java buildDt database/iris.db class 100
* java buildDt database/color.db color 1500
*/
public class BuildDt {
public static void main(String args[]){
if (args.length<3) {
System.out.println("usage : database goal learning_set_size [entthres stopthres]");
return;
}
/* creation of a database */
Database db = new Database();
System.out.println("Database loading:");
try {
db.loadDb(new URL(args[0]));
} catch (Exception e) {
System.out.println("database file not found");
return;
}
if (db.objects.size==0) {
System.out.println("no object");
return;
}
ObjectSet ls=db.objects.selectRandom(Integer.parseInt(args[2]));
ObjectSet ts=db.objects.selectNotIn(ls);
// select the goal attribute
Attribute goal=db.findAttribute(args[1]);
if (goal==null) {
System.out.println("goal attribute not found");
return;
}
// select all candidate attributes
Vector ca=db.getCandidateAttributes(args[1]);
if (ca.size()==0) {
System.out.println("no candidate attributes");
return;
}
double entthres=0.0;
double stopthres=2.0;
if (args.length>=4) {
entthres=(new Double(args[3])).doubleValue();
}
if (args.length>=5) {
stopthres=(new Double(args[4])).doubleValue();
}
DecisionTree dt=new DecisionTree(db, ls, ca, (SymbAtt)goal,entthres,stopthres);
dt.buildDt();
dt.printDt();
System.out.println("ls errors : " + 100.0*dt.testDt(ls) + "%");
System.out.println("ts errors : " + 100.0*dt.testDt(ts) + "%");
}
}
---------------------------
/*
* 1.1 version.
*/
import java.awt.*;
import java.awt.event.*;
import java.applet.Applet;
/*
* This displays a framed area. When the user clicks within
* the area, this program displays a dot and a string indicating
* the coordinates where the click occurred.
*/
public class CoordinatesDemo extends Applet {
FramedArea framedArea;
Label label;
public void init() {
GridBagLayout gridBag = new GridBagLayout();
GridBagConstraints c = new GridBagConstraints();
setLayout(gridBag);
framedArea = new FramedArea(this);
c.fill = GridBagConstraints.BOTH;
c.weighty = 1.0;
c.gridwidth = GridBagConstraints.REMAINDER; //end row
gridBag.setConstraints(framedArea, c);
add(framedArea);
label = new Label("Click within the framed area.");
c.fill = GridBagConstraints.HORIZONTAL;
c.weightx = 1.0;
c.weighty = 0.0;
gridBag.setConstraints(label, c);
add(label);
}
public void updateLabel(Point point) {
label.setText("Click occurred at coordinate ("
+ point.x + ", " + point.y + ").");
}
}
/* This class exists solely to put a frame around the coordinate area. */
class FramedArea extends Panel {
public FramedArea(CoordinatesDemo controller) {
super();
//Set layout to one that makes its contents as big as possible.
setLayout(new GridLayout(1,0));
add(new CoordinateArea(controller));
}
public Insets getInsets() {
return new Insets(4,4,5,5);
}
public void paint(Graphics g) {
Dimension d = getSize();
Color bg = getBackground();
g.setColor(bg);
g.draw3DRect(0, 0, d.width - 1, d.height - 1, true);
g.draw3DRect(3, 3, d.width - 7, d.height - 7, false);
}
}
class CoordinateArea extends Canvas {
Point point = null;
CoordinatesDemo controller;
public CoordinateArea(CoordinatesDemo controller) {
super();
this.controller = controller;
addMouseListener(new MouseAdapter() {
public void mousePressed(MouseEvent e) {
int x = e.getX();
int y = e.getY();
if (point == null) {
point = new Point(x, y);
} else {
point.x = x;
point.y = y;
}
repaint();
}
});
}
public void paint(Graphics g) {
//If user has chosen a point, paint a tiny rectangle on top.
if (point != null) {
controller.updateLabel(point);
g.fillRect(point.x - 1, point.y - 1, 2, 2);
}
}
}
-----------------------------------------
/*
* Database.java
* Copyright (C) 1999 Pierre Geurts
*
* This program is free software; you can redistribute it and/or modify
* it under the terms of the GNU General Public License as published by
* the Free Software Foundation; either version 2 of the License, or
* (at your option) any later version.
*
* This program is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
* GNU General Public License for more details.
*
* You should have received a copy of the GNU General Public License
* along with this program; if not, write to the Free Software
* Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
*/
import java.util.*;
import java.io.*;
import java.net.*;
public class Database{
/* the name of the database */
String name;
/* the filename from which the database has been loaded */
String filename;
/* the set of objects */
ObjectSet objects=new ObjectSet();
/* the vector of atttributes */
Vector attributes=new Vector();
/* method to add an object */
public int addObjToDb(Obj o) {
objects.addElement(o);
return objects.size-1;
}
/* method to add an attribute */
public int addAttToDb(Attribute att){
attributes.addElement(att);
return attributes.size()-1;
}
/* a short description of the database */
public String toString(){
StringBuffer s=new StringBuffer();
s.append(name);
s.append(" o(");
s.append(objects.size);
s.append(") a(");
s.append(attributes.size());
s.append(")");
return s.toString();
}
/* to "pretty" print the content of the database */
public void printDb() {
System.out.println(toString());
System.out.print("Object ");
for (int i=0;
i
System.out.print(((Attribute)attributes.
elementAt(i)).
toString() + " ");
}
System.out.println("");
for (int i=0; i
System.out.print(o.toString() + " ");
for (int j=0; j
System.out.print(" ");
}
System.out.println("");
}
}
/* utilities */
private static void skipBlankLines(StreamTokenizer stt) throws IOException {
while (stt.ttype==stt.TT_EOL)
stt.nextToken();
}
/* loading of a database from a file */
/* return 1 if there is an error, 0 otherwise */
public int loadDb (URL u) {
boolean objectname=false;
int objectnameindex=0;
filename=u.toString();
try {
// URL u=new URL(fn);
URLConnection urlConnection=u.openConnection();
urlConnection.connect();
InputStream in=urlConnection.getInputStream();
BufferedReader r=new BufferedReader(new InputStreamReader(in));
StreamTokenizer stt=new StreamTokenizer(r);
/* some streamtokenizer inititialisations*/
stt.lowerCaseMode(false);
stt.parseNumbers();
stt.eolIsSignificant(true);
stt.commentChar(';');
stt.wordChars('$','$');
stt.wordChars('_','_');
/* file reading */
stt.nextToken();
skipBlankLines(stt);
/**************************
* read the database name *
**************************/
if (stt.ttype==stt.TT_WORD)
name=stt.sval;
else {
System.out.println("the database name must be a symbol");
return 1;
}
stt.nextToken();
skipBlankLines(stt);
/*******************************
* read attributes declaration *
*******************************/
int nreadvalue=0;
int natt=0;
while (stt.ttype!=stt.TT_EOL) {
String attname;
String atttype;
if (stt.ttype!=stt.TT_WORD) {
System.out.println("error in attribute declaration");
return 1;
}
attname=stt.sval;
stt.nextToken();
if (stt.ttype!=stt.TT_WORD) {
System.out.println("error in attribute declaration");
return 1;
}
atttype=stt.sval;
if (atttype.equals("name") || atttype.equals("NAME")) {
if (!objectname) {
objectname=true;
objectnameindex=nreadvalue;
} else {
System.out.println("error in attribute declaration");
return 1;
}
} else {
if (atttype.equals("symbolic") || atttype.equals("SYMBOLIC"))
new SymbAtt(attname,this);
else if (atttype.equals("numerical") || atttype.equals("NUMERICAL"))
new NumAtt(attname,this);
else {
System.out.println("not recognised attribute type");
return 1;
}
natt++;
}
nreadvalue++;
stt.nextToken();
}
System.out.println("" + natt + " attributes have been read");
System.out.println(attributes.toString());
/**************************
* read objects definitions *
**************************/
int exactnatt=natt;
int nobject=1;
while(stt.ttype!=stt.TT_EOF) {
skipBlankLines(stt);
/* number of readed values*/
nreadvalue=0;
/* number of readed attributes (as nreadvalue but
without the object name) */
natt=0;
Obj o;
if (objectname)
o=new Obj("",this);
else
o=new Obj("O" + nobject,this);
nobject++;
/* read attributes values */
while(stt.ttype!=stt.TT_EOL && stt.ttype!=stt.TT_EOF) {
if (objectname==true &&
objectnameindex==nreadvalue &&
nreadvalue==objectnameindex) {
if (stt.ttype==stt.TT_WORD) {
o.name=stt.sval;
nreadvalue++;
} else {
System.out.println("Object name must be a string");
return 1;
}
} else {
if (((Attribute)attributes.elementAt(natt)).ReadAttValue(o,stt)
==1) {
System.out.println("objet " + nobject + " value " + nreadvalue);
return 1;
}
natt++;
nreadvalue++;
}
stt.nextToken();
}
if (natt
return 1;
}
skipBlankLines(stt);
}
System.out.println("" + (nobject-1) + " objects have been read");
// System.out.println(objects.toString());
in.close();
}
catch (Exception e){
System.err.println(e);
}
return 0;
}
/* a method to find an attribute by its name */
public Attribute findAttribute(String name) {
int as=attributes.size();
for (int i=0; i
if (name.equals(a.name))
return a;
}
return null;
}
/* a method to find all attributes except one */
public Vector getCandidateAttributes(String goal) {
int as=attributes.size();
Attribute a;
Vector result=new Vector();
for (int i=0; i
if (!goal.equals(a.name)) {
result.addElement(a);
}
}
return result;
}
/* a method to find a object by its name */
public Obj findObject(String name) {
int os=objects.size;
for (int i=0; i
if (name.equals(o.name))
return o;
}
return null;
}
}
----------------------------
/*
* DbReader.java
* Copyright (C) 1999 Pierre Geurts
*
* This program is free software; you can redistribute it and/or modify
* it under the terms of the GNU General Public License as published by
* the Free Software Foundation; either version 2 of the License, or
* (at your option) any later version.
*
* This program is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
* GNU General Public License for more details.
*
* You should have received a copy of the GNU General Public License
* along with this program; if not, write to the Free Software
* Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
*/
import java.io.*;
public class DbReader {
private static void skipBlankLines(StreamTokenizer stt) throws IOException {
while (stt.ttype==stt.TT_EOL)
stt.nextToken();
}
/* return 1 if there is an error, 0 otherwise */
public static int loadDb (Database db, String filename) {
boolean objectname=false;
int objectnameindex=0;
try {
File f=new File(filename);
Reader in=new FileReader(f);
StreamTokenizer stt=new StreamTokenizer(in);
/* some streamtokenizer initialisations*/
stt.lowerCaseMode(true);
stt.parseNumbers();
stt.eolIsSignificant(true);
stt.commentChar(';');
/* file reading */
stt.nextToken();
skipBlankLines(stt);
/*******************************
* read attributes declaration *
*******************************/
int nreadvalue=0;
int natt=0;
while (stt.ttype!=stt.TT_EOL) {
String attname;
String atttype;
if (stt.ttype!=stt.TT_WORD) {
System.out.println("error in attribute declaration");
return 1;
}
attname=stt.sval;
stt.nextToken();
if (stt.ttype!=stt.TT_WORD) {
System.out.println("error in attribute declaration");
return 1;
}
atttype=stt.sval;
if (attname.equals("object")) {
if (!objectname) {
objectname=true;
objectnameindex=nreadvalue;
} else {
System.out.println("error in attribute declaration");
return 1;
}
} else {
if (atttype.equals("symbolic"))
new SymbAtt(attname,db);
else if (atttype.equals("numerical"))
new NumAtt(attname,db);
else {
System.out.println("not recognised attribute type");
return 1;
}
natt++;
}
nreadvalue++;
stt.nextToken();
}
System.out.println("" + natt + " attributes have been read");
System.out.println(db.attributes.toString());
/**************************
* read objects definitions *
**************************/
int exactnatt=natt;
int nobject=1;
while(stt.ttype!=stt.TT_EOF) {
skipBlankLines(stt);
/* number of readed values*/
nreadvalue=0;
/* number of readed attributes (as nreadvalue but
without the object name) */
natt=0;
Obj o;
if (objectname)
o=new Obj("",db);
else
o=new Obj("O" + nobject,db);
nobject++;
/* read attributes values */
while(stt.ttype!=stt.TT_EOL && stt.ttype!=stt.TT_EOF) {
if (objectname==true &&
objectnameindex==nreadvalue &&
nreadvalue==objectnameindex) {
if (stt.ttype==stt.TT_WORD) {
o.name=stt.sval;
nreadvalue++;
} else {
System.out.println("Object name must be a string");
return 1;
}
} else {
if (((Attribute)db.attributes.elementAt(natt)).ReadAttValue(o,stt)
==1) {
return 1;
}
natt++;
nreadvalue++;
}
stt.nextToken();
}
if (natt
return 1;
}
skipBlankLines(stt);
}
System.out.println("" + nobject + " objects have been read");
System.out.println(db.objects.toString());
in.close();
}
catch (IOException e){
System.err.println(e);
}
return 0;
}
}
----------------------------------
/*
* DecisionTree.java
* Copyright (C) 1999 Pierre Geurts
*
* This program is free software; you can redistribute it and/or modify
* it under the terms of the GNU General Public License as published by
* the Free Software Foundation; either version 2 of the License, or
* (at your option) any later version.
*
* This program is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
* GNU General Public License for more details.
*
* You should have received a copy of the GNU General Public License
* along with this program; if not, write to the Free Software
* Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
*/
import java.util.*;
public class DecisionTree {
/* problem definition */
Database db;
ObjectSet LearningSet;
Vector CandAttributes;
SymbAtt goal;
/* parameter */
double EntropyThres=0;
double ScoreThres=0;
/* root node */
DtNode root;
/* stack of open node */
Stack openNodes=new Stack();
/* Ordered attributes list for the current node */
Vector CurrentNodeAtt;
/**
* create a trivial tree with the default parameters values
*/
DecisionTree(Database d, ObjectSet ls, Vector CandAtt, SymbAtt g) {
db=d;
LearningSet=ls;
CandAttributes=CandAtt;
goal=g;
DtNode.nbnodes=0;
root=new DtNode(LearningSet, g);
root.graphnode=new WNode("open", null, null, null, null, 0, 0, 0, root);
root.graphnode.selected=true;
// openNodes.push(root);
}
/**
* create a trivial tree with the user's parameter values
*/
DecisionTree(Database d, ObjectSet ls, Vector CandAtt, SymbAtt g,
double et, double st) {
EntropyThres=et;
ScoreThres=st;
db=d;
LearningSet=ls;
CandAttributes=CandAtt;
goal=g;
DtNode.nbnodes=0;
root=new DtNode(LearningSet, g);
root.graphnode=new WNode("open", null, null, null, null, 0, 0, 0, root);
root.graphnode.selected=true;
// openNodes.push(root);
}
/**
* build completely the decision tree
*/
public void buildDt() {
// we search this tree for all the remaining open nodes
getOpenNodes();
// then we build the tree
while(!openNodes.empty()) {
expandTopNode();
}
}
/**
* expand the node on the top of stack always with the best choice
*/
public void expandTopNode() {
DtNode topnode=(DtNode)openNodes.pop();
scanNode(topnode);
Vector result=topnode.split(CurrentNodeAtt,0,goal);
//-- we put the successors on the top of the stack (in reverse order)
if (result!=null) {
for (int i=result.size()-1; i>=0; i--) {
openNodes.push(result.elementAt(i));
}
}
}
/**
* scan the attributes for the top node
*/
public Vector scanNode(DtNode topnode) {
CurrentNodeAtt=topnode.scanAttributes(CandAttributes, goal, EntropyThres, ScoreThres);
/* build a vector of textual description of candidate tests */
Vector result=new Vector();
for (int i=0; i
result.addElement(CurrentNodeAtt.lastElement());
return result;
}
/**
* split the top node according to the choice in the CurrentNodeAtt
* Vector
*/
public DtNode splitNode(DtNode topnode, int choice) {
Vector result=topnode.split(CurrentNodeAtt,choice,goal);
if (result!=null) {
// we return the first successor
return (DtNode)result.elementAt(0);
} else {
// otherwise, we return the leftmost open node
return getLeftMostOpenNode();
}
}
/**
* get all the open nodes of the tree (needed because the user can
* now open the node by himself)
*/
public void getOpenNodes() {
openNodes.removeAllElements();
root.getOpenNodes(openNodes);
}
/**
* look for the leftmost open node in the tree
* (this is used after splitting to find the next node to split)
*/
public DtNode getLeftMostOpenNode() {
return root.getLeftMostOpenNode();
}
/**
* get a description of the current open node
*/
public String getNodeDescription(DtNode node) {
return node.getNodeDescription(goal);
}
/**
* propagate this object across the tree and get the associated class
*/
public String Propagate(Obj o) {
return root.getClass(o);
}
/**
* test the dt on an objectset
*/
public double testDt(ObjectSet ts) {
String treeclass, trueclass;
int nberrors=0;
for (int i=0; i
trueclass=(String)goal.Value(ts.elementAt(i));
if (!trueclass.equals(treeclass))
nberrors++;
}
System.out.println("nb of errors : " + nberrors + " out of " + ts.size);
return 1.0*nberrors/ts.size;
}
/**
* test the tree using cross-validation
* argument - the number of subsets into which
* the data base must be divided
*/
public double testDtCrossvalidation(int tssize) {
DecisionTree dt;
int n=LearningSet.size/tssize;
Vector tsvector=new Vector();
ObjectSet remainingobjects=LearningSet;
System.out.println("");
System.out.println("Cross validation : " + n + ", LS : "
+ (LearningSet.size-tssize) + " , TS: " +
tssize);
System.out.println("");
// we construct the set of test sets
for (int i=0; i
tsvector.addElement(os);
remainingobjects=remainingobjects.selectNotIn(os);
}
// we construct the trees
double result=0;
for (int i=0; i
System.out.println("Tree number " + (i+1));
System.out.println("");
ObjectSet ts=(ObjectSet)tsvector.elementAt(i);
dt=new DecisionTree(db, LearningSet.selectNotIn(ts),
CandAttributes, goal,
EntropyThres, ScoreThres);
dt.buildDt();
result+=dt.testDt(ts);
}
// we return the average
return result/n;
}
public void printDt() {
System.out.println(root.printNode(0));
}
}
----------------------------
/*
* DecisionTreeApplet.java
* Copyright (C) 1999 Pierre Geurts
*
* This program is free software; you can redistribute it and/or modify
* it under the terms of the GNU General Public License as published by
* the Free Software Foundation; either version 2 of the License, or
* (at your option) any later version.
*
* This program is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
* GNU General Public License for more details.
*
* You should have received a copy of the GNU General Public License
* along with this program; if not, write to the Free Software
* Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
*/
import java.applet.Applet;
import java.awt.*;
import java.awt.event.*;
import java.util.*;
import java.net.*;
import java.io.*;
/**
* Displays the tree building process
*/
public class DecisionTreeApplet extends Applet
implements ActionListener,ItemListener, Runnable
{
/* Following are workarounds for font size calculations, as Netscape
* reports unappealing font height/ascents on varying platforms. */
static final int FIXED_FONT_HEIGHT = 10;
static final int FIXED_FONT_ASCENT = 3;
boolean running;
Thread t;
WNode root;
WalTreeCanvas tc;
SimpleNodeDrawer snd;
DetailedNodeDrawer dnd;
/* decision tree data */
Database db;
DecisionTree CurrentDt;
DtNode CurrentDtn;
ObjectSet ls;
ObjectSet ts;
Button btn_scan; // scan the attribute
Button btn_split; // split one node (if it is still possible)
Button btn_build; // build the tree
Button btn_refresh; // refresh the graph (actually not useful)
Label lbl_zoom=new Label("Zoom", Label.RIGHT);
Button btn_zoominc;
Button btn_zoomdec;
Choice AttChoice; // selection list for the best attribute
String messagechoice="Click 'Scan Attributes' to see the choices";
TextField tf_opennode=new TextField(); // description of the current node
// input parameters
Panel top=new Panel();
Label lbl_database=new Label("Database url : ", Label.RIGHT);
TextField tf_database= new TextField(65); // to enter the file name
Button btn_loaddb=new Button("Load Database");
// to restart with a new database
Label lbl_goal=new Label("Goal Attribute : ", Label.RIGHT); // goal attribute
Choice GoalAttributeChoice; // a choice list for the goal attribute (only the symbolic)
// (at the same time, it displays all the attribute)
Label lbl_candatt=new Label("Candidate attributes : ");
java.awt.List lst_candatt; // a selection list for the candidate attributes
// learning set selection
Label lbl_learningset=new Label("Learning set :", Label.RIGHT);
Label lbl_lssize=new Label("size :", Label.RIGHT);
TextField tf_lssize=new TextField(5);
Label lbl_lsmode=new Label("Selection mode:", Label.RIGHT);
Choice SelectionChoiceLs;
// tree parameters
Label lbl_entthres=new Label("Entropy Threshold : ", Label.RIGHT);
TextField tf_entthres=new TextField(4);
Label lbl_scorethres=new Label("Inf X LS size Threshold : ", Label.RIGHT);
TextField tf_scorethres= new TextField(4);
double default_scorethres=0.0;
double default_entthres=0.0;
// start tree button
Button btn_starttree=new Button("New Tree");
// test parameters
Label lbl_testset=new Label("Test set :", Label.RIGHT);
Label lbl_tssize=new Label("size :", Label.RIGHT);
TextField tf_tssize=new TextField(5);
Label lbl_tsmode=new Label("Selection mode:", Label.RIGHT);
Choice SelectionChoiceTs;
TextField tf_testresult=new TextField(20);
Button btn_testtree;
Button btn_crossvalidation;
// panels
Panel t_p0=new Panel(new GridLayout(3,1,0,0));
Panel t_loaddb=new Panel(new FlowLayout(FlowLayout.CENTER,5,0));
Panel t_p1=new Panel(new FlowLayout(FlowLayout.CENTER,5,0));
Panel t_p2=new Panel(new FlowLayout(FlowLayout.CENTER,5,0));
Panel t_p3=new Panel(new FlowLayout(FlowLayout.CENTER,5,0));
Panel t_p4=new Panel(new FlowLayout(FlowLayout.CENTER,5,0));
Panel t_p5=new Panel(new BorderLayout());
Panel b_p1=new Panel(new FlowLayout(FlowLayout.CENTER,5,0));
Panel b_p2=new Panel(new FlowLayout(FlowLayout.CENTER,5,0));
Panel b_p3=new Panel(new FlowLayout(FlowLayout.CENTER,5,0));
Panel b_p4=new Panel(new FlowLayout(FlowLayout.CENTER,5,0));
Panel bottom=new Panel();
ScrollPane sp=new ScrollPane();
CheckboxGroup treedrawer=new CheckboxGroup();
Checkbox chk_simple=new Checkbox("Simple",treedrawer,true);
Checkbox chk_detailed=new Checkbox("Detailed",treedrawer,false);
/**
* Initialize the applet.
*/
public void init ()
{
super.init();
String str;
setLayout(new BorderLayout());
t_loaddb.add(lbl_database);
t_loaddb.add(tf_database);
t_loaddb.add(btn_loaddb);
t_p1.add(lbl_goal);
t_p1.add(GoalAttributeChoice=new Choice());
t_p2.add(lbl_entthres);
t_p2.add(tf_entthres);
t_p3.add(lbl_scorethres);
t_p3.add(tf_scorethres);
t_p4.add(lbl_learningset);
t_p4.add(lbl_lssize);
t_p4.add(tf_lssize);
t_p4.add(lbl_lsmode);
t_p4.add(SelectionChoiceLs=new Choice());
t_p4.add(btn_starttree);
SelectionChoiceLs.add("Random");
SelectionChoiceLs.add("First");
SelectionChoiceLs.add("Last");
t_p5.add(lbl_candatt,"North");
t_p5.add(lst_candatt=new java.awt.List(5,true),"Center");
t_p0.add(t_p1) ; t_p0.add(t_p2) ; t_p0.add(t_p3);
top.setLayout(new BorderLayout());
top.add(t_loaddb, "North");
top.add(t_p0, "West");
top.add(t_p5,"Center");
top.add(t_p4,"South");
// center : the tree canvas
sp.add(tc=new WalTreeCanvas());
// bottom : control of the building process
bottom.setLayout(new GridLayout(4,1,0,0));
b_p1.add(tf_opennode=new TextField(100));
tf_opennode.setEditable(false);
bottom.add(b_p1);
b_p3.add(AttChoice=new Choice());
bottom.add(b_p3);
b_p2.add(btn_scan=new Button("Scan attributes"));
b_p2.add(btn_split=new Button("Split"));
b_p2.add(btn_build=new Button("Build"));
b_p2.add(chk_simple);
b_p2.add(chk_detailed);
b_p2.add(btn_refresh=new Button("Refresh"));
b_p2.add(lbl_zoom);
b_p2.add(btn_zoominc=new Button("+"));
b_p2.add(btn_zoomdec=new Button("-"));
bottom.add(b_p2);
b_p4.add(lbl_testset);
b_p4.add(lbl_tssize);
b_p4.add(tf_tssize);
b_p4.add(lbl_tsmode);
b_p4.add(SelectionChoiceTs=new Choice());
SelectionChoiceTs.add("Not in ls");
SelectionChoiceTs.add("Random");
SelectionChoiceTs.add("First");
SelectionChoiceTs.add("Last");
SelectionChoiceTs.add("Learning set");
b_p4.add(btn_testtree=new Button("Test tree"));
b_p4.add(btn_crossvalidation=new Button("Cross Validation"));
b_p4.add(tf_testresult);
tf_testresult.setEditable(false);
bottom.add(b_p4);
add(top, "North");
add(bottom, "South");
add(sp, "Center");
snd=new SimpleNodeDrawer(tc);
dnd=new DetailedNodeDrawer(tc);
tc.nd=snd;
tc.setParentDistance(30);
// load the database
if (getParameter("DBFILE")!=null) {
URL u;
try {
u=new URL(getDocumentBase(), getParameter("DBFILE"));
initDb(u);
} catch (MalformedURLException e) {
System.out.println("-- database file not found");
showStatus("Bad url");
}
}
// different actions binding
// buttons
btn_split.addActionListener(this);
btn_refresh.addActionListener(this);
btn_scan.addActionListener(this);
btn_starttree.addActionListener(this);
btn_testtree.addActionListener(this);
btn_crossvalidation.addActionListener(this);
btn_build.addActionListener(this);
btn_loaddb.addActionListener(this);
btn_zoominc.addActionListener(this);
btn_zoomdec.addActionListener(this);
// check button
chk_simple.addItemListener(this);
chk_detailed.addItemListener(this);
// selection list
SelectionChoiceTs.addItemListener(this);
// mouse
MyMouseListener ml=new MyMouseListener();
tc.addMouseListener(ml);
}
public void loadDb() {
URL u;
try {
u=new URL(tf_database.getText());
initDb(u);
tc.setTree(root);
tc.repaint();
} catch (MalformedURLException e) {
System.out.println("-- database file not found");
showStatus("Bad url");
}
}
public void initDb(URL u) {
db = new Database();
System.out.println("Database loading:");
showStatus("Loading database");
if (db.loadDb(u)==1) {
showStatus("Loading failed : bad file format");
return;
}
tf_database.setText(u.toString());
if (db.objects.size==0) {
System.out.println("no object");
}
//-- fill candidate attribute selection list
lst_candatt.removeAll();
GoalAttributeChoice.removeAll();
int last_symb=0;
for (int i=0; i
lst_candatt.add(att.describe());
lst_candatt.select(i);
if (att instanceof SymbAtt) {
GoalAttributeChoice.add(att.toString());
last_symb=i;
}
}
GoalAttributeChoice.select(GoalAttributeChoice.getItemCount()-1);
lst_candatt.deselect(last_symb);
//-- initialise score and entropy threshold
tf_entthres.setText("" + default_entthres);
tf_scorethres.setText("" + default_scorethres);
//-- initialise ls size and type
tf_lssize.setText("" + (int)(2*db.objects.size/3));
SelectionChoiceLs.select(0);
tf_tssize.setText("" + (int)(db.objects.size/3));
SelectionChoiceTs.select(0);
AttChoice.add(messagechoice);
AttChoice.select(0);
//-- initialise the tree
root=null;
//-- garbage collecting after this (to remove the previous database)
System.gc();
showStatus("done");
setComment("");
}
public void NewTree() {
//-- learning set selection
int lssize=GetLsSize();
int lsmode=GetLsMode();
if (lsmode==0)
ls=db.objects.selectRandom(lssize);
else if (lsmode==1)
ls=db.objects.selectFirst(lssize);
else if (lsmode==2)
ls=db.objects.selectLast(lssize);
//-- we build a trivial tree
CurrentDt=new DecisionTree(db, ls, GetCandAtt(), GetGoalAttribute(),
GetEntThres(), GetScoreThres());
CurrentDtn=CurrentDt.root;
root=CurrentDt.root.graphnode;
//-- we initialise the graphical interface
setComment(CurrentDt.getNodeDescription(CurrentDtn));
AttChoice.removeAll();
AttChoice.add(messagechoice);
AttChoice.select(0);
refreshcurrenttree();
}
/**
* some functions to get the parameters value
*/
public Vector GetCandAtt() {
int[] index=lst_candatt.getSelectedIndexes();
if (index.length==0)
return new Vector();
Vector result=new Vector();
for (int i=0; i
}
return result;
}
public SymbAtt GetGoalAttribute() {
return (SymbAtt)db.findAttribute(GoalAttributeChoice.getSelectedItem());
}
public double GetEntThres() {
return (new Double(tf_entthres.getText())).doubleValue();
}
public double GetScoreThres() {
return (new Double(tf_scorethres.getText())).doubleValue();
}
public int GetLsSize() {
if (tf_lssize.getText()=="")
return 0;
else
return Integer.parseInt(tf_lssize.getText());
}
public int GetLsMode() {
return SelectionChoiceLs.getSelectedIndex();
}
public int GetTsSize() {
if (tf_lssize.getText()=="")
return 0;
else
return Integer.parseInt(tf_tssize.getText());
}
public int GetTsMode() {
return SelectionChoiceTs.getSelectedIndex();
}
public void setComment(String t) {
tf_opennode.setText(t);
}
/**
* Start the main applet thread.
*/
public void start ()
{
running = true;
t = new Thread(this);
t.start();
}
/**
* Stop the applet.
*/
public void stop ()
{
running = false;
}
/**
* Main event loop.
*/
public void run () { }
/**
* scan all the attributes at the top node for the best attribute.
* display the result into the choice list.
*/
public void Scanatt() {
if (CurrentDtn==null)
return;
Vector choices=CurrentDt.scanNode(CurrentDtn);
AttChoice.removeAll();
for (int i=0; i
}
/**
* Split the current node
*
*/
public void SplitMore() {
if (CurrentDtn==null)
return;
if (CurrentDtn.type!="open") {
// if the node is not open, we open it
CurrentDtn.open();
}
if (AttChoice.getItem(0)==messagechoice) {
//-- the user has not asked for attributes scanning
CurrentDt.scanNode(CurrentDtn);
changeSelectedNode(CurrentDt.splitNode(CurrentDtn,0));
} else {
//-- we take into account the user's choice
changeSelectedNode(CurrentDt.splitNode(CurrentDtn,AttChoice.getSelectedIndex()));
}
refreshcurrenttree();
}
public void changeSelectedNode(DtNode dtn) {
if (CurrentDtn!=null)
CurrentDtn.graphnode.selected=false;
if (AttChoice.getItem(0)!=messagechoice) {
AttChoice.removeAll();
AttChoice.add(messagechoice);
AttChoice.select(0);
}
CurrentDtn=dtn;
if (CurrentDtn!=null) {
CurrentDtn.graphnode.selected=true;
setComment(CurrentDt.getNodeDescription(CurrentDtn));
} else {
setComment("");
}
}
public void buildalltree() {
showStatus("Building the tree...");
CurrentDt.buildDt();
changeSelectedNode(null);
refreshcurrenttree();
CurrentDt.printDt();
showStatus("done");
}
public void testtree() {
//-- learning set selection
showStatus("Testing the tree...");
int tssize=GetTsSize();
int tsmode=GetTsMode();
if (tsmode==0)
ts=db.objects.selectNotIn(ls);
else if (tsmode==1)
ts=db.objects.selectRandom(tssize);
else if (tsmode==2)
ts=db.objects.selectFirst(tssize);
else if (tsmode==3)
ts=db.objects.selectLast(tssize);
else if (tsmode==4)
ts=ls;
String result="" + CurrentDt.testDt(ts)*100;
if (result.length()<5)
tf_testresult.setText("" + result + "%");
else
tf_testresult.setText("" + result.substring(0,5) + "%");
showStatus("done");
}
public void CrossValidation() {
showStatus("Cross validation...please wait");
double result=CurrentDt.testDtCrossvalidation(GetTsSize());
String sr="" + result*100;
if (sr.length()<5)
tf_testresult.setText(sr + "%");
else
tf_testresult.setText(sr.substring(0,5) + "%");
showStatus("done");
}
public void actionPerformed(ActionEvent event) {
String command=event.getActionCommand();
if (command=="Split" && root!=null) {
SplitMore();
} else if (command=="Build" && root!=null) {
buildalltree();
} else if (command=="Scan attributes" && root!=null) {
Scanatt();
} else if (command=="Refresh" && root!=null) {
refreshcurrenttree();
} else if (command=="Test tree" && root!=null) {
testtree();
} else if (command=="New Tree") {
NewTree();
} else if (command=="Load Database") {
loadDb();
} else if (command=="Cross Validation" && root!=null) {
CrossValidation();
} else if (command=="+") {
snd.increaseZoom();
dnd.increaseZoom();
tc.repaint();
} else if (command=="-") {
snd.decreaseZoom();
dnd.decreaseZoom();
tc.repaint();
}
}
public void refreshcurrenttree() {
if (root==null)
return;
tc.nd.computeNodeSize(root);
tc.setTree(root);
tc.repaint();
}
public void itemStateChanged(ItemEvent event) {
String command=(String)event.getItem();
if (command == "Simple") {
tc.nd=snd;
refreshcurrenttree();
} else if (command == "Detailed") {
tc.nd=dnd;
if (root!=null) {
dnd.initWidth(root);
refreshcurrenttree();
}
} else if (command == "Not in ls") {
tf_tssize.setText("" + (db.objects.size - Integer.parseInt(tf_lssize.getText())));
} else if (command == "Learning set") {
tf_tssize.setText(tf_lssize.getText());
}
}
/* gestion de la souris */
class MyMouseListener extends MouseAdapter {
public void mousePressed(MouseEvent e) {
int x=e.getX();
int y=e.getY();
if (root!=null) {
DtNode dtn=root.getPointedNode((int)(x/tc.nd.zoom),(int)(y/tc.nd.zoom));
if (dtn!=null) {
// select this node
changeSelectedNode(dtn);
// retrace the graph (there must exist a better way to do this)
tc.repaint();
}
}
}
}
}
-------------------------
/*
* DetailedNodeDrawer.java
* Copyright (C) 1999 Pierre Geurts
*
* This program is free software; you can redistribute it and/or modify
* it under the terms of the GNU General Public License as published by
* the Free Software Foundation; either version 2 of the License, or
* (at your option) any later version.
*
* This program is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
* GNU General Public License for more details.
*
* You should have received a copy of the GNU General Public License
* along with this program; if not, write to the Free Software
* Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
*/
import java.awt.*;
import java.util.*;
/**
* a abstract class to allow many representation for
* a node
*/
public class DetailedNodeDrawer extends NodeDrawer {
FontMetrics metrics_small,metrics_big, metrics_current;
Font smallfont, bigfont;
int SMALL_FIXED_FONT_HEIGHT=8;
int BIG_FIXED_FONT_HEIGHT=14;
int current_font_height;
int default_border=10;
Vector colours=new Vector();
int max_width=60;
int max_height=40;
int max_ls_size=1;
double coef;
Canvas cv;
DetailedNodeDrawer(Canvas c) {
cv=c;
bigfont=new Font("Helvetica", Font.PLAIN, BIG_FIXED_FONT_HEIGHT);
c.setFont(bigfont);
metrics_big=c.getFontMetrics(c.getFont());
smallfont=new Font("Helvetica", Font.PLAIN, SMALL_FIXED_FONT_HEIGHT);
c.setFont(smallfont);
metrics_small=c.getFontMetrics(c.getFont());
metrics_current=metrics_small;
current_font_height=SMALL_FIXED_FONT_HEIGHT;
coef=Math.exp(1)*20;
colours.addElement(Color.black);
colours.addElement(Color.red);
colours.addElement(Color.green);
colours.addElement(Color.blue);
colours.addElement(Color.orange);
colours.addElement(Color.darkGray);
colours.addElement(Color.cyan);
colours.addElement(Color.gray);
colours.addElement(Color.magenta);
colours.addElement(Color.pink);
colours.addElement(Color.black);
colours.addElement(Color.yellow);
colours.addElement(Color.white);
colours.addElement(Color.red);
colours.addElement(Color.green);
colours.addElement(Color.blue);
colours.addElement(Color.orange);
colours.addElement(Color.darkGray);
colours.addElement(Color.cyan);
colours.addElement(Color.gray);
colours.addElement(Color.magenta);
colours.addElement(Color.pink);
colours.addElement(Color.black);
colours.addElement(Color.yellow);
colours.addElement(Color.white);
}
public void initWidth(WNode t) {
t.width=0;
if (t.sibling!=null) {
initWidth(t.sibling);
}
if (t.child!=null) {
initWidth(t.child);
}
}
public void computeNodeSize(WNode t) {
max_ls_size=t.dtnode.subset.size;
computeSize(t);
}
public void computeSize(WNode t) {
if (t.width==0) { //-- we compute the size only once
double correction;
if (t.dtnode.subset.size!=0)
correction=Math.log(coef)/Math.log(coef*max_ls_size/t.dtnode.subset.size);
else
correction=Math.log(coef)/Math.log(coef*max_ls_size);
t.height=(int)(max_width*correction);
t.width=(int)(max_height*correction);
}
t.border=default_border;
if (t.sibling!=null) {
computeSize(t.sibling);
}
if (t.child!=null) {
computeSize(t.child);
}
}
public void drawArc(Graphics g, int x1, int y1, int x2,
int y2, String arclabel) {
g.setColor(Color.black);
g.drawLine((int)(x1*zoom), (int)(y1*zoom), (int)(x2*zoom),(int)(y2*zoom));
g.drawString(arclabel,
(int)(((x1 + x2)*zoom - metrics_current.stringWidth(arclabel)) / 2),
(int)((y1 + y2)*zoom/2));
}
public void drawNode(Graphics g, WNode t) {
int tposx=(int)(t.pos.x*zoom);
int tposy=(int)(t.pos.y*zoom);
int tw=(int)(t.width*zoom);
int th=(int)(t.height*zoom);
int current_x=tposy*t.dtnode.subset.size;
int incr_x;
int y=tposx;
//-- draw the box
if (t.dtnode.subset.size!=0) {
for (int i=0; i
incr_x=th*t.dtnode.subset.summary[i];
g.setColor((Color)colours.elementAt(i+1));
g.fillRect((int)(current_x/t.dtnode.subset.size),y,
(int)(incr_x/t.dtnode.subset.size)+1,tw);
current_x+=incr_x;
}
}
}
g.setColor(Color.black);
g.drawRect(tposy, tposx, th, tw);
//-- we highlight the current open node
if (t.selected) {
g.setColor(Color.pink);
g.drawRect(tposy-current_font_height, tposx-current_font_height,
th+2*current_font_height, tw+2*current_font_height);
}
//-- we put information beneath the box ...
String bottomtext;
if (t.dtnode.type.equals("test"))
bottomtext=t.label;
else if (t.dtnode.type.equals("open"))
bottomtext="open";
else if (t.dtnode.type.equals("open"))
bottomtext="leaf : " + t.dtnode.majclass;
else
bottomtext="error";
g.setColor(Color.black);
g.drawString(t.label,
tposy + (th - metrics_current.stringWidth(t.label)) / 2,
tposx + tw + current_font_height);
//-- ... and on top of the box
g.drawString(t.dtnode.name, tposy, tposx+1);
}
// increase the zoom
public void increaseZoom() {
if (zoom==0.5)
zoom=0.7;
else if (zoom==0.7)
zoom=1.0;
else if (zoom==1.0)
zoom=1.2;
else if (zoom==1.2) {
zoom=1.5;
metrics_current=metrics_big;
current_font_height=BIG_FIXED_FONT_HEIGHT;
cv.setFont(bigfont);
} else if (zoom==1.5)
zoom=2.0;
else if (zoom==2.0)
zoom=2.5;
else if (zoom==2.5)
zoom=3.0;
}
// decrease the zoom
public void decreaseZoom() {
if (zoom==3.0)
zoom=2.5;
else if (zoom==2.5)
zoom=2.0;
else if (zoom==2.0)
zoom=1.5;
else if (zoom==1.5) {
zoom=1.2;
metrics_current=metrics_small;
current_font_height=SMALL_FIXED_FONT_HEIGHT;
cv.setFont(smallfont);
} else if (zoom==1.2)
zoom=1.0;
else if (zoom==1.0)
zoom=0.7;
else if (zoom==0.7)
zoom=0.5;
}
}
----------------------------------
/*
* DtNode.java
* Copyright (C) 1999 Pierre Geurts
*
* This program is free software; you can redistribute it and/or modify
* it under the terms of the GNU General Public License as published by
* the Free Software Foundation; either version 2 of the License, or
* (at your option) any later version.
*
* This program is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
* GNU General Public License for more details.
*
* You should have received a copy of the GNU General Public License
* along with this program; if not, write to the Free Software
* Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
*/
import java.util.*;
public class DtNode {
static int nbnodes;
ObjectSet subset;
String type="open"; // leaf, test or open
String majclass="default"; // the majority class in this node
String name;
WNode graphnode; // for the tree visualisation
Test test;
Vector successors;
DtNode(ObjectSet s, SymbAtt goal) {
subset=s;
name="node" + nbnodes++;
ComputeInfoNode(goal);
}
/**
* Compute some information about this node (entropy, subset summary
* and class maj). This should be call when the node is created.
*/
public void ComputeInfoNode(SymbAtt goal) {
subset.computeEntropy(goal);
majclass=subset.getMajClass(goal);
}
/**
* Scan all the cancidate attributes, compute the information gain of the
* best score. Return a vector of attributes ordered by decreasing values
* of information.
*/
public Vector scanAttributes(Vector ca, SymbAtt goal, double entthres, double scorethres) {
Vector result=new Vector();
System.out.println("expanding " + getNodeDescription(goal));
//-- no object in this node (this should never happen)
if (subset.size==0) {
result.addElement("No object in this node -> a leaf");
return result;
}
//-- entropy is low enough, we can stop splitting this node
if (subset.entropy<=entthres) {
result.addElement("Entropy low enough (threshold=" +
entthres + ") -> a leaf");
return result;
}
//-- in the other case, we scan the attributes
// System.out.println("number of candidate attributes : " + ca.size());
System.out.print("[");
double score;
int i=0,j=0;
Attribute att;
for (; i
att=(Attribute)ca.elementAt(i);
score=att.bestscore(subset,goal);
// System.out.println(att.name + " " + score);
//-- the score must be greater than the threshold (forward pruning)
if ((score*subset.size)>scorethres) {
j=0;
while (j
j++;
if (j==result.size())
result.addElement(att);
else
result.insertElementAt(att,j);
}
}
System.out.println("]");
//-- we always let the possibility to user to make this node a leaf
result.addElement("make this node a leaf");
return result;
}
public Vector split(Vector scanresult, int choice, SymbAtt goal) {
//-- make this node a leaf
if (choice==scanresult.size()-1) {
System.out.println((String)scanresult.elementAt(choice));
type="leaf";
buildGraphLeafNode(goal);
return null;
}
//-- we take the attribute and construct the partition
Attribute selectedatt=(Attribute)scanresult.elementAt(choice);
Partition partition=selectedatt.bestpartition(subset,goal);
test=partition.test;
successors=new Vector();
type="test";
System.out.println("-> a test node (score : " + selectedatt.lastbestscore +
" , test : " + test.TestDescription + ")");
//-- we create the successor nodes
for (int i=0; i
goal));
}
//-- we create the graphnodes
buildGraphTestNodes();
//- we return the successors (open nodes)
return successors;
}
/**
* expand this node and return a vector of open nodes resulting from
* the expansion
*/
public Vector expand(Vector ca, SymbAtt goal, double entthres, double scorethres) {
//-- if the subset is empty, this is a leaf and the class is default
if (subset.size==0) {
System.out.println("-> a leaf (no objects)");
majclass="default";
type="leaf";
buildGraphLeafNode(goal);
return null;
}
System.out.println("expanding " + getNodeDescription(goal));
//-- if the entropy is lower than the threshold, then we stop the splitting
if (subset.entropy<=entthres) { // a new leaf
System.out.println("-> a leaf (entropy low, " + subset.entropy
+ "<=" + entthres + ")");
type="leaf";
buildGraphLeafNode(goal);
return null;
}
//-- otherwise, we screen all the attributes
double bestscore=0,score;
Attribute bestatt=null,att;
System.out.print("[");
for (int i=0; i
att=(Attribute)ca.elementAt(i);
score=att.bestscore(subset,goal);
if (score>bestscore) {
bestscore=score;
bestatt=att;
}
}
System.out.println("]");
//-- the best score must be greater than the threshold (stop-splitting rule)
if ((bestscore*subset.size)<=scorethres) {
System.out.println("-> a leaf (score too low, "
+ (bestscore*subset.size) + "<=" +
scorethres + ")");
type="leaf";
buildGraphLeafNode(goal);
return null;
}
//-- we construct the partition of the learning set
Partition partition=bestatt.bestpartition(subset,goal);
test=partition.test;
successors=new Vector();
type="test";
System.out.println("-> a test node (score : " + bestscore +
" , test : " + test.TestDescription + ")");
//-- we create the successor nodes
for (int i=0; i
goal));
}
//-- we create the graphnodes
buildGraphTestNodes();
//-- we return the successors (open node)
return successors;
}
/**
* complete the graphnode for a leaf
*/
public void buildGraphLeafNode(SymbAtt goal) {
graphnode.label=majclass;
if (majclass.equals("default")) {
graphnode.colour=0;
} else {
graphnode.colour=goal.values.indexOf(majclass)+1;
}
}
/**
* build the graphnodes for the successors of this node
*/
public void buildGraphTestNodes() {
//-- first we put the label of this node (the size will be computed afterwards)
graphnode.label=test.TestDescription;
//-- then the first successor
DtNode dtchild=(DtNode)successors.elementAt(0);
dtchild.graphnode=new WNode("open", (String)test.valuesIssues.elementAt(0),
graphnode, null, null,0,0,0,dtchild);
graphnode.child=dtchild.graphnode;
WNode previousgchild=dtchild.graphnode;
DtNode nextdtchild;
//-- and finally the others
for (int i=1; i
nextdtchild.graphnode=new WNode("open", (String)test.valuesIssues.elementAt(i),
graphnode,null,null,0,0,0,nextdtchild);
previousgchild.sibling=nextdtchild.graphnode;
previousgchild=nextdtchild.graphnode;
}
}
/**
* open a node (destroy all his successors and tests)
*/
public void open() {
test=null;
type="open";
graphnode.child=null;
graphnode.colour=0;
graphnode.label="open";
}
/**
* get all the open nodes of this subtree (in a depth first way but
* in the oposite direction (right to left and bottom to top)
*/
public void getOpenNodes(Stack opennodes) {
if (type.equals("open"))
opennodes.push(this);
else if (successors!=null) {
for (int i=successors.size()-1; i>=0; i--) {
((DtNode)successors.elementAt(i)).getOpenNodes(opennodes);
}
}
}
/**
* get the leftmost open node
*/
public DtNode getLeftMostOpenNode() {
if (type.equals("open"))
return this;
else if (successors!=null) {
for (int i=0; i
if (dtn!=null)
return dtn;
}
return null;
} else
return null;
}
/**
* return the class associated to this object by the subtree corresponding
* to this node
*/
public String getClass(Obj o) {
if (type.equals("leaf") || type.equals("open"))
return majclass;
else
return ((DtNode)successors.elementAt(test.TestIndex(o))).getClass(o);
}
/**
* give a textual description of this node
*/
public String getNodeDescription(SymbAtt goal) {
String s="";
s+=name;
s+=" - LS : " + subset.getSummaryString(goal);
s+=" - ENTROPY : " + subset.entropy;
return s;
}
/**
* print n spaces (to pretty print the decision tree)
*/
private String printNtab(int n) {
String result="";
for (int i=0; i
}
return result;
}
/**
* print a textual description of the subtree corresponding
* to this node.
*/
public String printNode(int depth) {
String result="";
if (type.equals("leaf") || type.equals("open")) {
result+=printNtab(depth);
result+="return \"" + majclass + "\";\n";
} else if (type.equals("test")) {
for (int i=0; i
if (i!=0)
result+="} else ";
result+="if (" + test.testDescription(i) + ") {\n";
result+=((DtNode)successors.elementAt(i)).printNode(depth+1);
}
result+=printNtab(depth) + "}\n";
} else {
System.out.println("printNode - bad node type");
return "";
}
return result;
}
}
-------------------------------
/*
* Entropy.java
* Copyright (C) 1999 Pierre Geurts
*
* This program is free software; you can redistribute it and/or modify
* it under the terms of the GNU General Public License as published by
* the Free Software Foundation; either version 2 of the License, or
* (at your option) any later version.
*
* This program is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
* GNU General Public License for more details.
*
* You should have received a copy of the GNU General Public License
* along with this program; if not, write to the Free Software
* Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
*/
import java.io.*;
/* this class contains some functions to calculate
* entropy values
*/
public class Entropy{
static double entropy(int freq[], int size, int sum) {
// when we don't have example then the entropy is zero
if (sum==0)
return 0.0;
double result=sum*java.lang.Math.log(sum);
for (int i=0; i
result-=freq[i]*java.lang.Math.log(freq[i]);
}
result/=java.lang.Math.log((double)2.0);
result/=sum;
return result;
}
}
-------------------------
/*
* NodeDrawer.java
* Copyright (C) 1999 Pierre Geurts
*
* This program is free software; you can redistribute it and/or modify
* it under the terms of the GNU General Public License as published by
* the Free Software Foundation; either version 2 of the License, or
* (at your option) any later version.
*
* This program is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
* GNU General Public License for more details.
*
* You should have received a copy of the GNU General Public License
* along with this program; if not, write to the Free Software
* Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
*/
import java.awt.*;
import java.util.*;
/**
* a abstract class to allow many representation for
* a node
*/
public abstract class NodeDrawer {
double zoom=1.0;
abstract void computeNodeSize(WNode t);
abstract void drawNode(Graphics g, WNode t);
abstract void drawArc(Graphics g, int x1, int y1, int x2,
int y2, String arclabel);
abstract void increaseZoom();
abstract void decreaseZoom();
}
--------------------------
/*
* NumAtt.java
* Copyright (C) 1999 Pierre Geurts
*
* This program is free software; you can redistribute it and/or modify
* it under the terms of the GNU General Public License as published by
* the Free Software Foundation; either version 2 of the License, or
* (at your option) any later version.
*
* This program is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
* GNU General Public License for more details.
*
* You should have received a copy of the GNU General Public License
* along with this program; if not, write to the Free Software
* Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
*/
import java.io.*;
import java.util.*;
public class NumAtt extends Attribute{
/* le domaine de l'attribut dans la bd */
float rangemin=(float)1.0, rangemax=(float)0.0;
/* le meilleur score precedemment obtenu par cet attribut */
float bestthreshold;
NumAtt(String s, Database dab) {
name=s;
db=dab;
index=db.addAttToDb(this);
}
public void SetAttValue(Obj o,Object f) {
float fl=((Float)f).floatValue();
if (rangemin>rangemax) {
rangemin=fl;
rangemax=fl;
} else {
if (fl
else if (fl>rangemax)
rangemax=fl;
}
o.attributesvalues.setElementAt(f,index);
}
public int ReadAttValue(Obj o, StreamTokenizer stt) {
if (stt.ttype==stt.TT_NUMBER) {
SetAttValue(o,new Float(stt.nval));
return 0;
} else {
System.out.println("A numerical value was expected");
return 1;
}
}
public String describe() {
return toString()+ " - numerical - range : [" + rangemin + "," + rangemax + "]";
}
public String describeBestTest() {
return toString() + " - threshold : " + bestthreshold + " - Information gain : " +
lastbestscore;
}
/* return the best partition for a numerical attribute
* we assume that the best threshold is already computed (by
* using bestscore
*/
public Partition bestpartition(ObjectSet os, SymbAtt goal) {
TestNum t=new TestNum(this,bestthreshold);
Vector v=os.splitOn(t);
return new Partition(t,v);
}
/* searches the best threshold value for a numerical attribute
* assumes that the objectset size is greater than 0
*/
public double bestscore(ObjectSet os, SymbAtt goal) {
// first, the set is ordered by increasing attribute values
os.orderOn(this);
// then prepare the data, we suppose that we have already
// computed the entropy value
int gvs=goal.values.size();
int freqyes[]=new int[gvs+1];
int freqno[]=new int[gvs+1];
// in the beginning, the test is false for all objects
for (int i=0; i
}
freqno[gvs]=os.size;
float currentthreshold=rangemin;
double bestscore=0,actualscore=os.entropy;
double entyes,entno;
int ico;
int iconext=goal.values.indexOf(goal.Value((Obj)os.elementAt(0)));
float av;
float avnext=((Float)Value((Obj)os.elementAt(0))).floatValue();
for (int i=0; i
ico=iconext;
iconext=goal.values.indexOf(goal.Value((Obj)os.elementAt(i+1)));
av=avnext;
avnext=((Float)Value((Obj)os.elementAt(i+1))).floatValue();
freqno[ico]--;freqno[gvs]--;
freqyes[ico]++;freqyes[gvs]++;
if (
// ico!=iconext && // i'm not sure of this -> skip it
av!=avnext
) {
// only if the class of this point is different from the next point
// class and if its attribute value if also different from the next
// point attribute value
entno=Entropy.entropy(freqno,gvs,freqno[gvs]);
entyes=Entropy.entropy(freqyes,gvs,freqyes[gvs]);
actualscore=os.entropy-(freqno[gvs]*entno+freqyes[gvs]*entyes)/os.size;
if (actualscore>bestscore) {
bestscore=actualscore;
currentthreshold=(float)((av+avnext)/2.0);
}
}
}
bestthreshold=currentthreshold;
lastbestscore=bestscore;
return bestscore;
}
}
--------------------------
/*
* Obj.java
* Copyright (C) 1999 Pierre Geurts
*
* This program is free software; you can redistribute it and/or modify
* it under the terms of the GNU General Public License as published by
* the Free Software Foundation; either version 2 of the License, or
* (at your option) any later version.
*
* This program is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
* GNU General Public License for more details.
*
* You should have received a copy of the GNU General Public License
* along with this program; if not, write to the Free Software
* Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
*/
import java.util.*;
public class Obj {
/* the name of the object */
String name;
/* the database it belongs to */
Database db;
/* the vector of attributes values */
Vector attributesvalues=new Vector();
Obj(String s, Database db) {
this.db=db;
name=s;
db.addObjToDb(this);
/* it allocates place for the attribute values */
attributesvalues.setSize(db.attributes.size());
}
public String toString() {
return name;
}
}
----------------------
/*
* ObjectSet.java
* Copyright (C) 1999 Pierre Geurts
*
* This program is free software; you can redistribute it and/or modify
* it under the terms of the GNU General Public License as published by
* the Free Software Foundation; either version 2 of the License, or
* (at your option) any later version.
*
* This program is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
* GNU General Public License for more details.
*
* You should have received a copy of the GNU General Public License
* along with this program; if not, write to the Free Software
* Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
*/
import java.util.*;
/* simplement un vecteur d'object, on verra apres si on garde
ce niveau d'abstraction ou pas
*/
public class ObjectSet {
/* objects list*/
Vector objectslist;
/* a cache value for the entropy in this set */
double entropy;
/* the size of the learning set */
int size;
/* summary, the frequence of each class in this set */
int summary[];
ObjectSet(Vector vo) {
objectslist=vo;
size=vo.size();
}
ObjectSet() {
objectslist=new Vector();
size=0;
}
/* only for compatibility (primary an objectset was simply a vector) */
public int size() {
return size;
}
public Obj elementAt(int index) {
return (Obj)objectslist.elementAt(index);
}
public void addElement(Obj o) {
objectslist.addElement(o);
size++;
}
public void setElementAt(Obj o, int index) {
objectslist.setElementAt(o, index);
}
public int indexOf(Obj o) {
return objectslist.indexOf(o);
}
public String toString() {
return objectslist.toString();
}
/* split a set according to the given test */
public Vector splitOn(Test t) {
int index;
Vector v=new Vector();
Obj o;
for (int i=0; i
}
for (int i=0; i
index=t.TestIndex(o);
((ObjectSet)v.elementAt(index)).addElement(o);
}
return v;
}
/* methods to select subset of objects from the database */
/* select the first n objects from this subset */
public ObjectSet selectFirst(int n) {
ObjectSet os=new ObjectSet();
for (int i=0;i
}
return os;
}
/* select the last n objects from this subset */
public ObjectSet selectLast(int n) {
ObjectSet os=new ObjectSet();
int i;
if (n>size)
i=0;
else
i=size-n;
for (;i
}
return os;
}
/* select randomly n objects from this set (very stupid) */
public ObjectSet selectRandom(int n) {
ObjectSet os=new ObjectSet();
Vector v=(Vector)objectslist.clone();
int sv=size;
int pos;
if (n>size)
n=size;
for (int i=0;i
os.addElement((Obj)v.elementAt(pos));
v.removeElementAt(pos);
sv--;
}
return os;
}
/* select objects which are not in a given subset */
public ObjectSet selectNotIn(ObjectSet oset) {
ObjectSet os=new ObjectSet();
Obj o;
for (int i=0;i
if (oset.indexOf(o)==-1)
os.addElement(o);
}
return os;
}
/* method to compute the entropy of an symbolic attribute in this subset
* it computes also the subset summary
*/
public double computeEntropy(SymbAtt goal) {
int sum=size;
int i,x,gvs=goal.values.size();
summary=new int[gvs];
for (i=0; i
summary[x]++;
}
entropy=Entropy.entropy(summary, gvs, sum);
return entropy;
}
/* give a textual description of the subset summary */
public String getSummaryString(SymbAtt goal) {
String s="";
for (int i=0; i
s+=":" + summary[i]+ " ";
}
s+="total:" + size;
return s;
}
/* method that gives the majority class in this subset (using the summary) */
public String getMajClass(SymbAtt goal) {
int imax=0;
int maxfreq=summary[0];
for (int i=1; i
maxfreq=summary[i];
imax=i;
}
}
return (String)goal.values.elementAt(imax);
}
/* order a subset on numerical attribute values
* use quicksort algorithm
*/
public void orderOn(NumAtt att) {
orderOn(att,0,size-1);
}
public void orderOn(NumAtt att, int lo0, int hi0) {
int lo=lo0;
int hi=hi0;
float mid;
if (hi0>lo0) {
mid = ((Float)att.Value((Obj)objectslist.elementAt((lo0+hi0)/2))).floatValue();
while (lo<= hi) {
while((lo
while((hi>lo0) &&
(((Float)att.Value((Obj)objectslist.elementAt(hi))).floatValue()>mid))
--hi;
if(lo<=hi) {
Object tmp=objectslist.elementAt(lo);
objectslist.setElementAt(objectslist.elementAt(hi),lo);
objectslist.setElementAt(tmp,hi);
++lo;
--hi;
}
}
if(lo0
if (lo
}
}
}
---------------------------
/*
* Partition.java
* Copyright (C) 1999 Pierre Geurts
*
* This program is free software; you can redistribute it and/or modify
* it under the terms of the GNU General Public License as published by
* the Free Software Foundation; either version 2 of the License, or
* (at your option) any later version.
*
* This program is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
* GNU General Public License for more details.
*
* You should have received a copy of the GNU General Public License
* along with this program; if not, write to the Free Software
* Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
*/
import java.util.*;
public class Partition{
/* a test */
Test test;
/* a vector of ObjectSet */
Vector sets;
Partition(Test t, Vector oss) {
test=t;
sets=oss;
}
}
------------------------
/**
* Represents a polygon area for use in spacing/positioning calculations.
*/
class Polygon {
PolyLine lower_head, lower_tail;
PolyLine upper_head, upper_tail;
};
------------------------
/**
* Used to build Polygons.
*/
class PolyLine {
int dx, dy;
PolyLine link;
PolyLine(int dx, int dy, PolyLine link) {
this.dx = dx;
this.dy = dy;
this.link = link;
}
};
--------------------------
/*
* 1.1 version.
*/
import java.awt.*;
import java.awt.event.*;
import java.applet.Applet;
/*
* This displays a framed area. When the user clicks within
* the area, this program displays a dot and a string indicating
* the coordinates where the click occurred.
*/
public class RectangleDemo extends Applet {
RFramedArea framedArea;
Label label;
public void init() {
GridBagLayout gridBag = new GridBagLayout();
GridBagConstraints c = new GridBagConstraints();
setLayout(gridBag);
framedArea = new RFramedArea(this);
c.fill = GridBagConstraints.BOTH;
c.weighty = 1.0;
c.gridwidth = GridBagConstraints.REMAINDER; //end row
gridBag.setConstraints(framedArea, c);
add(framedArea);
label = new Label("Drag within the framed area.");
c.fill = GridBagConstraints.HORIZONTAL;
c.weightx = 1.0;
c.weighty = 0.0;
gridBag.setConstraints(label, c);
add(label);
}
public void updateLabel(Rectangle rect) {
label.setText("Rectangle goes from ("
+ rect.x + ", " + rect.y + ") to ("
+ (rect.x + rect.width - 1) + ", "
+ (rect.y + rect.height - 1) + ").");
}
}
/* This class exists solely to put a frame around the coordinate area. */
class RFramedArea extends Panel {
public RFramedArea(RectangleDemo controller) {
super();
//Set layout to one that makes its contents as big as possible.
setLayout(new GridLayout(1,0));
add(new SelectionArea(controller));
}
public Insets getInsets() {
return new Insets(4,4,5,5);
}
public void paint(Graphics g) {
Dimension d = getSize();
Color bg = getBackground();
g.setColor(bg);
g.draw3DRect(0, 0, d.width - 1, d.height - 1, true);
g.draw3DRect(3, 3, d.width - 7, d.height - 7, false);
}
}
class SelectionArea extends Canvas {
Rectangle currentRect = null;
RectangleDemo controller;
public SelectionArea(RectangleDemo controller) {
super();
this.controller = controller;
MyListener myListener = new MyListener();
addMouseListener(myListener);
addMouseMotionListener(myListener);
}
class MyListener extends MouseAdapter
implements MouseMotionListener {
public void mousePressed(MouseEvent e) {
int x = e.getX();
int y = e.getY();
currentRect = new Rectangle(x, y, 0, 0);
repaint();
}
public void mouseDragged(MouseEvent e) {
updateSize(e);
}
public void mouseMoved(MouseEvent e) {
}
public void mouseReleased(MouseEvent e) {
updateSize(e);
}
void updateSize(MouseEvent e) {
int x = e.getX();
int y = e.getY();
currentRect.setSize(x - currentRect.x,
y - currentRect.y);
repaint();
}
}
public void paint(Graphics g) {
//update has already cleared the previous rectangle,
//so we dn't need to here.
//If currentRect exists, paint a rectangle on top.
if (currentRect != null) {
Dimension d = getSize();
Rectangle box = getDrawableRect(currentRect, d);
controller.updateLabel(box);
//Draw the box outline.
g.drawRect(box.x, box.y,
box.width - 1, box.height - 1);
}
}
Rectangle getDrawableRect(Rectangle originalRect,
Dimension drawingArea) {
int x = originalRect.x;
int y = originalRect.y;
int width = originalRect.width;
int height = originalRect.height;
//Make sure rectangle width and height are positive.
if (width < 0) {
width = 0 - width;
x = x - width + 1;
if (x < 0) {
width += x;
x = 0;
}
}
if (height < 0) {
height = 0 - height;
y = y - height + 1;
if (y < 0) {
height += y;
y = 0;
}
}
//The rectangle shouldn't extend past the drawing area.
if ((x + width) > drawingArea.width) {
width = drawingArea.width - x;
}
if ((y + height) > drawingArea.height) {
height = drawingArea.height - y;
}
//If the width or height is 0, make it 1
//so that the box is visible.
if (width == 0) {
width = 1;
}
if (height == 0) {
height = 1;
}
return new Rectangle(x, y, width, height);
}
}
----------------------
/*
* SimpleNodeDrawer.java
* Copyright (C) 1999 Pierre Geurts
*
* This program is free software; you can redistribute it and/or modify
* it under the terms of the GNU General Public License as published by
* the Free Software Foundation; either version 2 of the License, or
* (at your option) any later version.
*
* This program is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
* GNU General Public License for more details.
*
* You should have received a copy of the GNU General Public License
* along with this program; if not, write to the Free Software
* Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
*/
import java.awt.*;
import java.util.*;
/**
* a abstract class to allow many representation for
* a node
*/
public class SimpleNodeDrawer extends NodeDrawer {
FontMetrics metrics_small,metrics_big,metrics_current;
Font smallfont, bigfont;
int SMALL_FIXED_FONT_HEIGHT=8;
int BIG_FIXED_FONT_HEIGHT=14;
int current_font_height;
int default_border=5;
Vector colours=new Vector();
Canvas cv;
SimpleNodeDrawer(Canvas c) {
cv=c;
bigfont=new Font("Helvetica", Font.PLAIN, BIG_FIXED_FONT_HEIGHT);
c.setFont(bigfont);
metrics_big=c.getFontMetrics(c.getFont());
smallfont=new Font("Helvetica", Font.PLAIN, SMALL_FIXED_FONT_HEIGHT);
c.setFont(smallfont);
metrics_small=c.getFontMetrics(c.getFont());
metrics_current=metrics_small;
current_font_height=SMALL_FIXED_FONT_HEIGHT;
colours.addElement(Color.black);
colours.addElement(Color.red);
colours.addElement(Color.green);
colours.addElement(Color.blue);
colours.addElement(Color.orange);
colours.addElement(Color.darkGray);
colours.addElement(Color.cyan);
colours.addElement(Color.gray);
colours.addElement(Color.magenta);
colours.addElement(Color.pink);
colours.addElement(Color.black);
colours.addElement(Color.yellow);
colours.addElement(Color.white);
colours.addElement(Color.red);
colours.addElement(Color.green);
colours.addElement(Color.blue);
colours.addElement(Color.orange);
colours.addElement(Color.darkGray);
colours.addElement(Color.cyan);
colours.addElement(Color.gray);
colours.addElement(Color.magenta);
colours.addElement(Color.pink);
colours.addElement(Color.black);
colours.addElement(Color.yellow);
colours.addElement(Color.white);
}
public void computeNodeSize(WNode t) {
t.width=2 * current_font_height;
t.height=metrics_current.stringWidth(t.label) + 10;
t.border=default_border;
if (t.sibling !=null) {
computeNodeSize(t.sibling);
}
if (t.child != null) {
computeNodeSize(t.child);
}
}
public void drawArc(Graphics g, int x1, int y1, int x2,
int y2, String arclabel) {
g.setColor(Color.black);
g.drawLine((int)(x1*zoom), (int)(y1*zoom), (int)(x2*zoom),(int)(y2*zoom));
g.drawString(arclabel,
(int)(((x1 + x2)*zoom - metrics_current.stringWidth(arclabel)) / 2),
(int)((y1 + y2)*zoom/2));
}
public void drawNode(Graphics g, WNode t) {
int tposx=(int)(t.pos.x*zoom);
int tposy=(int)(t.pos.y*zoom);
int tw=(int)(t.width*zoom);
int th=(int)(t.height*zoom);
// Draw highlights
g.setColor(Color.lightGray);
g.drawLine(tposy + 2, tposx + tw + 1, tposy + th,
tposx + tw + 1);
g.drawLine(tposy + th + 1, tposx + tw + 1,
tposy + th + 1, tposx + 2);
// we draw the box corresponding to this node
if (t.colour>=colours.size())
g.setColor(Color.black);
else
g.setColor((Color)colours.elementAt(t.colour));
g.drawRect(tposy, tposx, th, tw);
// we draw the node label
g.drawString(t.label,
tposy + (th - metrics_current.stringWidth(t.label)) / 2,
tposx + tw - (tw - current_font_height) / 2);
if (t.selected) {
int border=(int)(3*zoom);
g.setColor(Color.pink);
g.drawRect(tposy-border, tposx-border, th+2*border, tw+2*border);
}
}
// increase the zoom
public void increaseZoom() {
if (zoom==0.5)
zoom=0.7;
else if (zoom==0.7)
zoom=1.0;
else if (zoom==1.0)
zoom=1.2;
else if (zoom==1.2) {
zoom=1.5;
metrics_current=metrics_big;
current_font_height=BIG_FIXED_FONT_HEIGHT;
cv.setFont(bigfont);
} else if (zoom==1.5)
zoom=2.0;
else if (zoom==2.0)
zoom=2.5;
else if (zoom==2.5)
zoom=3.0;
}
// decrease the zoom
public void decreaseZoom() {
if (zoom==3.0)
zoom=2.5;
else if (zoom==2.5)
zoom=2.0;
else if (zoom==2.0)
zoom=1.5;
else if (zoom==1.5) {
zoom=1.2;
metrics_current=metrics_small;
current_font_height=SMALL_FIXED_FONT_HEIGHT;
cv.setFont(smallfont);
} else if (zoom==1.2)
zoom=1.0;
else if (zoom==1.0)
zoom=0.7;
else if (zoom==0.7)
zoom=0.5;
}
}
-----------------------
/*
* SymbAtt.java
* Copyright (C) 1999 Pierre Geurts
*
* This program is free software; you can redistribute it and/or modify
* it under the terms of the GNU General Public License as published by
* the Free Software Foundation; either version 2 of the License, or
* (at your option) any later version.
*
* This program is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
* GNU General Public License for more details.
*
* You should have received a copy of the GNU General Public License
* along with this program; if not, write to the Free Software
* Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
*/
/* recherche de la meilleure partition binaire de l'ensemble des valeurs de
l'attribut */
import java.util.*;
import java.io.*;
public class SymbAtt extends Attribute{
Vector values=new Vector();
/* la valeur de l'attribut symbolique qui donne le meilleur score */
Vector bestsubset;
SymbAtt(String s, Database dab) {
name=s;
db=dab;
index=db.addAttToDb(this);
}
public void SetAttValue(Obj o,Object s) {
int i;
for (i=0; i
break;
if (i
else {
o.attributesvalues.setElementAt(s,index);
values.addElement(s);
}
}
public int ReadAttValue(Obj o, StreamTokenizer stt) {
if (stt.ttype==stt.TT_WORD) {
SetAttValue(o,stt.sval);
return 0;
} else if (stt.ttype==stt.TT_NUMBER) {
// we transform number to a string
SetAttValue(o,"" + stt.nval);
return 0;
} else {
System.out.println("A symbolic value was expected");
return 1;
}
}
public String describe() {
return toString()+ " - symbolic - values : " + values.toString();
}
public String describeBestTest() {
return toString() + " - values : " + bestsubset.toString() + " - Information gain : " + lastbestscore;
}
public double bestscore(ObjectSet os, SymbAtt goal) {
/* attention cette partie est tres tres mal ecrite */
double result;
double tmpresult;
double currentbestscore=-1;
int currentbestvalue=0;
int pbv;
int i,j,x,y;
/* liste des index*/
Vector remainingvalues=new Vector();
for (i=0; i
}
/* les valeurs dans l'ordre dans lequel elles sont selectionnees */
Vector ordervalues=new Vector();
/* les valeurs de score */
Vector scores=new Vector();
int gvs=goal.values.size();
int sum=os.size;
/* pour chaque valeur de l'attribut, on conserve la matrice des frequences */
int tabfreq[][][]=new int[values.size()][2][gvs+1];
/* calcul des matrices de frequences */
for (j=0; j
for (i=0; i
y=goal.values.indexOf(goal.Value((Obj)os.elementAt(i)));
if (x==j) { /* la valeur est la valeur testee */
tabfreq[j][0][y]++;
tabfreq[j][0][gvs]++;
} else {
tabfreq[j][1][y]++;
tabfreq[j][1][gvs]++;
}
}
/* calcul de l'entropie */
result=os.entropy;
result-=tabfreq[j][0][gvs]*Entropy.entropy(tabfreq[j][0], gvs,tabfreq[j][0][gvs])/sum;
result-=tabfreq[j][1][gvs]*Entropy.entropy(tabfreq[j][1], gvs,tabfreq[j][1][gvs])/sum;
if (result>currentbestscore) {
currentbestscore=result;
currentbestvalue=j;
}
}
/* on va maintenant regrouper les attributs de maniere recursive */
int currenttabfreq[][]=new int[2][gvs+1];
for (i=0;i
currenttabfreq[1][i]=tabfreq[currentbestvalue][0][i]
+ tabfreq[currentbestvalue][1][i];
}
// printtab(currenttabfreq,gvs+1);
/* on ajoute cet element dans la liste */
Integer cbv=new Integer(currentbestvalue);
ordervalues.addElement(cbv);
scores.addElement(new Double(currentbestscore));
i=0;
while (i
i++;
remainingvalues.removeElementAt(i);
while (remainingvalues.size()!=1) {
/* copier le tableau courant dans la valeur correspondant
a l'element precedent */
for (i=0;i
currenttabfreq[1][i]-=tabfreq[currentbestvalue][0][i];
}
// printtab(currenttabfreq,gvs+1);
/* on va utiliser la matrice correspondant a la precedente
valeur comme moyen de stockage temporaire
*/
pbv=currentbestvalue;
/* recherche de la meilleure valeur a ajouter au sous-ensemble */
currentbestscore=-1;
for (j=0; j
for (i=0; i
tabfreq[pbv][1][i]=currenttabfreq[1][i]-tabfreq[cv][0][i];
}
result=os.entropy;
result-=tabfreq[pbv][0][gvs]*
Entropy.entropy(tabfreq[pbv][0], gvs, tabfreq[pbv][0][gvs])/sum;
result-=tabfreq[pbv][1][gvs]*
Entropy.entropy(tabfreq[pbv][1], gvs, tabfreq[pbv][1][gvs])/sum;
if (result>currentbestscore) {
currentbestscore=result;
currentbestvalue=cv;
}
}
cbv=new Integer(currentbestvalue);
ordervalues.addElement(cbv);
scores.addElement(new Double(currentbestscore));
i=0;
while (i
i++;
remainingvalues.removeElementAt(i);
}
/* recherche du meilleur score */
currentbestscore=((Double)scores.elementAt(0)).doubleValue();
currentbestvalue=0;
for (i=1; i
if (sc>currentbestscore) {
currentbestscore=sc;
currentbestvalue=i;
}
}
/* on garde uniquement les elements de l'ensemble */
ordervalues.setSize(currentbestvalue+1);
bestsubset=new Vector();
for (i=0; i
// System.out.println(name + " " + values.toString() + " " + bestsubset.toString());
lastbestscore=currentbestscore;
return currentbestscore;
}
public Partition bestpartition(ObjectSet os, SymbAtt goal) {
TestSymb t=new TestSymb(this, bestsubset);
Vector v=os.splitOn(t);
return new Partition(t,v);
}
/*
public static void printtab(int[][] tab,int size) {
System.out.print("[[");
for (int i=0; i
}
System.out.println("]");
System.out.print("[");
for (int i=0; i
}
System.out.println("]]");
}
*/
}
-------------------
/*
* Test.java
* Copyright (C) 1999 Pierre Geurts
*
* This program is free software; you can redistribute it and/or modify
* it under the terms of the GNU General Public License as published by
* the Free Software Foundation; either version 2 of the License, or
* (at your option) any later version.
*
* This program is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
* GNU General Public License for more details.
*
* You should have received a copy of the GNU General Public License
* along with this program; if not, write to the Free Software
* Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
*/
import java.util.*;
/* a test should also be an extension of a Symbolic Attribute
* so that we could use it later
*/
abstract class Test {
/* a description of the test */
String TestDescription;
/* the attribute */
Attribute Att;
/* the number of issues of this test */
int nbIssues;
/* the vector of the values corresponding to each issues */
Vector valuesIssues;
/* TestObject gives the value associated to this object */
abstract String TestObject(Obj o);
/* return a description of the nth value of this test */
abstract String testDescription(int value);
/* TestIndex gives the index of this values in valuesissues */
public int TestIndex(Obj o) {
return valuesIssues.indexOf(TestObject(o));
}
}
----------------------------
/*
* Test.java
* Copyright (C) 1999 Pierre Geurts
*
* This program is free software; you can redistribute it and/or modify
* it under the terms of the GNU General Public License as published by
* the Free Software Foundation; either version 2 of the License, or
* (at your option) any later version.
*
* This program is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
* GNU General Public License for more details.
*
* You should have received a copy of the GNU General Public License
* along with this program; if not, write to the Free Software
* Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
*/
import java.util.*;
/* a test should also be an extension of a Symbolic Attribute
* so that we could use it later
*/
abstract class Test {
/* a description of the test */
String TestDescription;
/* the attribute */
Attribute Att;
/* the number of issues of this test */
int nbIssues;
/* the vector of the values corresponding to each issues */
Vector valuesIssues;
/* TestObject gives the value associated to this object */
abstract String TestObject(Obj o);
/* return a description of the nth value of this test */
abstract String testDescription(int value);
/* TestIndex gives the index of this values in valuesissues */
public int TestIndex(Obj o) {
return valuesIssues.indexOf(TestObject(o));
}
}
----------------------
/*
* Test.java
* Copyright (C) 1999 Pierre Geurts
*
* This program is free software; you can redistribute it and/or modify
* it under the terms of the GNU General Public License as published by
* the Free Software Foundation; either version 2 of the License, or
* (at your option) any later version.
*
* This program is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
* GNU General Public License for more details.
*
* You should have received a copy of the GNU General Public License
* along with this program; if not, write to the Free Software
* Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
*/
import java.util.*;
/* a test should also be an extension of a Symbolic Attribute
* so that we could use it later
*/
abstract class Test {
/* a description of the test */
String TestDescription;
/* the attribute */
Attribute Att;
/* the number of issues of this test */
int nbIssues;
/* the vector of the values corresponding to each issues */
Vector valuesIssues;
/* TestObject gives the value associated to this object */
abstract String TestObject(Obj o);
/* return a description of the nth value of this test */
abstract String testDescription(int value);
/* TestIndex gives the index of this values in valuesissues */
public int TestIndex(Obj o) {
return valuesIssues.indexOf(TestObject(o));
}
}
--------------------
import java.awt.*;
/**
* "There flowered a White Tree, and that was for Gondor; but Seven Stars
* were about it, and a high crown above it, the signs of Elendil that no
* lord had borne for years beyond count. And the stars flamed in the
* sunlight, for they were wrought of gems by Arwen daughter of Elrond;
* and the crown was bright in the morning, for it was wrought of mithril
* and gold." - J. R. R. Tolkien, _The Return of the King_
*
* Basic canvas for creating and displaying a WalTree.
*/
public class WalTreeCanvas extends Canvas {
int default_border;
WTFactory wt_factory; // contain functions to draw a tree
NodeDrawer nd; // contain functions to draw a node
WNode t;
boolean dirty; // tell us if the node positions should be computed again
int root_x;
/**
* Constructs new WalTreeCanvas, an associated WTFactory, and inits state.
*/
public WalTreeCanvas() {
super();
wt_factory = new WTFactory();
t = null;
default_border = 5;
root_x = 8;
dirty = false;
}
public Dimension getPreferredSize() {
return new Dimension(2000, 2000);
}
public Dimension getMiminimumSize() {
return new Dimension(40, 40);
}
/**
* Set the tree to be displayed by this canvas.
*/
public void setTree(WNode t) {
this.t = t;
dirty = true;
}
/**
* Set the default border size for nodes
*/
public void setDefaultBorder(int b) {
default_border = b;
}
/**
* Set the distance between parent nodes.
*/
public void setParentDistance(int val) {
wt_factory.setParentDistance(val);
}
/**
* Set the horizontal offset between edge of canvas and root node.
*/
public void setRootOffset(int val) {
root_x = val;
}
/**
* Draw the tree associated with this canvas.
*/
public void paint(Graphics g) {
super.paint(g);
Dimension d = getSize();
/* Wipe background */
g.setColor(Color.white);
g.fillRect(0, 0, d.width, d.height);
if(t == null) {
return;
}
if(dirty == true) {
/* Calculate node offsets */
wt_factory.layout(t);
/* Calculate absolute node positions */
wt_factory.plantTree(t, root_x, root_x-wt_factory.computeMaxOffset(t,0));
dirty = false;
}
/* Paint the beastie */
wt_factory.paintFullTree(g, t, nd);
}
};
------------------------
import java.awt.Point;
/**
* Represents a node (or tree) in the WalTree.
*/
public class WNode {
String label; // the label of the node (test)
String arclabel; // the label of the arc leading to this node
WNode parent, child, sibling;
int width, height, border; // the width, height and border of this node
Point pos, offset;
Polygon contour;
int colour=0; // a colour number
DtNode dtnode; // the associated DtNode
boolean selected=false; // tell us if this node is the current node
public WNode(String l, String a, WNode p, WNode c, WNode s, int w, int h, int b, DtNode dtn) {
label = l;
arclabel=a;
parent = p;
child = c;
sibling = s;
width = w;
height = h;
border = b;
pos = new Point(0, 0);
offset = new Point(0, 0);
contour = new Polygon();
dtnode=dtn;
}
public boolean containsPoint(int x, int y) {
return (((y>=pos.x) && (y<=pos.x+width)) && ((x>=pos.y) && (x<=pos.y+height)));
}
public DtNode getPointedNode(int x,int y) {
if (containsPoint(x,y))
return dtnode;
if (child!=null && y>pos.x) {
// not worth going further down if y
if (dtchild!=null)
return dtchild;
}
if (sibling!=null)
return sibling.getPointedNode(x,y);
return null;
}
}
-------------------------
/**
* A direct port from Sven Moen's "Drawing Dynamic Trees" article in
* IEEE Software, July 1990. Thanks to Allan Brighton for commenting the
* Brighton Tree Widget source code with the aforementioned reference.
*
* mai 1999 : modified by Pierre Geurts to display decision trees
*
*/
import java.awt.*;
import java.util.*;
/**
* Encapsulates all operations performed on a WalTree.
*/
public class WTFactory {
int parent_dist = 30;
/**
* Allows setting of the distance between levels in the tree.
*/
public void setParentDistance(int val) {
parent_dist = val;
}
/**
* Lays out the tree node spacing in typical tidy fashion.
*/
void layout(WNode t) {
WNode c;
if(t == null) {
return;
}
c = t.child;
while(c != null) {
layout(c);
c = c.sibling;
}
if(t.child != null) {
attachParent(t, join(t));
} else {
layoutLeaf(t);
}
}
/**
* Attaches the specified node to its children, setting offsets.
*/
void attachParent(WNode t, int h) {
int x, y1, y2;
x = t.border + parent_dist;
y2 = (h - t.height) / 2 - t.border;
y1 = y2 + t.height + 2 * t.border - h;
t.child.offset.x = x + t.width;
t.child.offset.y = y1;
t.contour.upper_head = new PolyLine(t.width, 0, new PolyLine(x, y1,
t.contour.upper_head));
t.contour.lower_head = new PolyLine(t.width, 0, new PolyLine(x, y2,
t.contour.lower_head));
}
/**
* Arranges contour for leaf node appropriately.
*/
void layoutLeaf(WNode t) {
t.contour.upper_tail = new PolyLine(t.width + 2 * t.border, 0, null);
t.contour.upper_head = t.contour.upper_tail;
t.contour.lower_tail = new PolyLine(0, -t.height - 2 * t.border, null);
t.contour.lower_head = new PolyLine(t.width + 2 * t.border, 0,
t.contour.lower_tail);
}
/**
* Joins children/siblings together, merging contours.
*/
int join(WNode t) {
WNode c;
int d, h, sum;
c = t.child;
t.contour = c.contour;
sum = h = c.height + 2 * c.border;
c = c.sibling;
while(c != null) {
d = merge(t.contour, c.contour);
c.offset.y = d + h;
c.offset.x = 0;
h = c.height + 2 * c.border;
sum += d + h;
c = c.sibling;
}
return sum;
}
/**
* Merges two polygons together. Returns total height of final polygon.
*/
int merge(Polygon c1, Polygon c2) {
int x, y, total, d;
PolyLine lower, upper, b;
x = y = total = 0;
upper = c1.lower_head;
lower = c2.upper_head;
while(lower != null && upper != null) { /* compute offset total */
d = offset(x, y, lower.dx, lower.dy, upper.dx, upper.dy);
y += d;
total += d;
if(x + lower.dx <= upper.dx) {
y += lower.dy;
x += lower.dx;
lower = lower.link;
} else {
y -= upper.dy;
x -= upper.dx;
upper = upper.link;
}
}
/* store result in c1 */
if(lower != null) {
b = bridge(c1.upper_tail, 0, 0, lower, x, y);
c1.upper_tail = (b.link != null) ? c2.upper_tail : b;
c1.lower_tail = c2.lower_tail;
} else { /* (upper) */
b = bridge(c2.lower_tail, x, y, upper, 0, 0);
if(b.link == null) {
c1.lower_tail = b;
}
}
c1.lower_head = c2.lower_head;
return total;
}
/**
* Calculates the offset for specified points.
*/
int offset(int p1, int p2, int a1, int a2, int b1, int b2) {
int d, s, t;
if(b1 <= p1 || p1 + a1 <= 0) {
return 0;
}
t = b1 * a2 - a1 * b2;
if(t > 0) {
if(p1 < 0) {
s = p1 * a2;
d = s / a1 - p2;
} else if(p1 > 0) {
s = p1 * b2;
d = s / b1 - p2;
} else {
d = -p2;
}
} else if(b1 < p1 + a1) {
s = (b1 - p1) * a2;
d = b2 - (p2 + s / a1);
} else if(b1 > p1 + a1) {
s = (a1 + p1) * b2;
d = s / b1 - (p2 + a2);
} else {
d = b2 - (p2 + a2);
}
if(d > 0) {
return d;
} else {
return 0;
}
}
/**
* bridge
*/
PolyLine bridge(PolyLine line1, int x1, int y1, PolyLine line2, int x2,
int y2) {
int dy, dx, s;
PolyLine r;
dx = x2 + line2.dx - x1;
if(line2.dx == 0) {
dy = line2.dy;
} else {
s = dx * line2.dy;
dy = s / line2.dx;
}
r = new PolyLine(dx, dy, line2.link);
line1.link = new PolyLine(0, y2 + line2.dy - dy - y1, r);
return r;
}
void plantTree(WNode t, int off_x, int off_y) {
WNode c, s;
int cur_y;
t.pos.x = off_x + t.offset.x;
t.pos.y = off_y + t.offset.y;
/* Plant child node */
c = t.child;
if(c != null) {
plantTree(c, t.pos.x, t.pos.y);
/* Plant sibling nodes */
s = c.sibling;
cur_y = t.pos.y + c.offset.y;
while(s != null) {
plantTree(s, t.pos.x + c.offset.x, cur_y);
cur_y += s.offset.y;
s = s.sibling;
}
}
}
/**
* PG 05/1999 : compute the maximum y offset to the right (or bottom)
* of the tree (to put the tree at the most left part (we go down
* along the first branch).
*/
int computeMaxOffset(WNode t, int y) {
WNode c, s;
int cur_y;
int current_pos_y;
current_pos_y = y + t.offset.y;
c = t.child;
if(c != null) {
int min=computeMaxOffset(c, current_pos_y), newmin=min;
/* Plant sibling nodes */
s = c.sibling;
cur_y = current_pos_y + c.offset.y;
while(s != null) {
newmin=computeMaxOffset(s, cur_y);
if (newmin
cur_y += s.offset.y;
s = s.sibling;
}
return min;
} else
return current_pos_y;
}
void paintFullTree(Graphics g, WNode t, NodeDrawer nd) {
if(t == null) {
System.out.println("paintFullTree::null tree.");
return;
}
g.setColor(Color.black);
paintTree(g, t, nd);
}
void paintTree(Graphics g, WNode t, NodeDrawer nd) {
nd.drawNode(g,t);
if(t.parent != null) {
int x1 = t.pos.y + t.height / 2;
int y1 = t.pos.x;
int x2 = t.parent.pos.y + t.parent.height / 2;
int y2 = t.parent.pos.x + t.parent.width;
nd.drawArc(g,x1,y1,x2,y2,t.arclabel);
}
/* Draw siblings, using the main child's x-offset. */
if(t.sibling != null) {
paintTree(g, t.sibling, nd);
}
/* Draw children */
if(t.child != null) {
paintTree(g, t.child, nd);
}
}
}
-------------
System.out.println("");
for (int i=0; i
System.out.print(o.toString() + " ");
for (int j=0; j
System.out.print(" ");
}
System.out.println("");
}
}
/* utilities */
private static void skipBlankLines(StreamTokenizer stt) throws IOException {
while (stt.ttype==stt.TT_EOL)
stt.nextToken();
}
/* loading of a database from a file */
/* return 1 if there is an error, 0 otherwise */
public int loadDb (URL u) {
boolean objectname=false;
int objectnameindex=0;
filename=u.toString();
try {
// URL u=new URL(fn);
URLConnection urlConnection=u.openConnection();
urlConnection.connect();
InputStream in=urlConnection.getInputStream();
BufferedReader r=new BufferedReader(new InputStreamReader(in));
StreamTokenizer stt=new StreamTokenizer(r);
/* some streamtokenizer inititialisations*/
stt.lowerCaseMode(false);
stt.parseNumbers();
stt.eolIsSignificant(true);
stt.commentChar(';');
stt.wordChars('$','$');
stt.wordChars('_','_');
/* file reading */
stt.nextToken();
skipBlankLines(stt);
/**************************
* read the database name *
**************************/
if (stt.ttype==stt.TT_WORD)
name=stt.sval;
else {
System.out.println("the database name must be a symbol");
return 1;
}
stt.nextToken();
skipBlankLines(stt);
/*******************************
* read attributes declaration *
*******************************/
int nreadvalue=0;
int natt=0;
while (stt.ttype!=stt.TT_EOL) {
String attname;
String atttype;
if (stt.ttype!=stt.TT_WORD) {
System.out.println("error in attribute declaration");
return 1;
}
attname=stt.sval;
stt.nextToken();
if (stt.ttype!=stt.TT_WORD) {
System.out.println("error in attribute declaration");
return 1;
}
atttype=stt.sval;
if (atttype.equals("name") || atttype.equals("NAME")) {
if (!objectname) {
objectname=true;
objectnameindex=nreadvalue;
} else {
System.out.println("error in attribute declaration");
return 1;
}
} else {
if (atttype.equals("symbolic") || atttype.equals("SYMBOLIC"))
new SymbAtt(attname,this);
else if (atttype.equals("numerical") || atttype.equals("NUMERICAL"))
new NumAtt(attname,this);
else {
System.out.println("not recognised attribute type");
return 1;
}
natt++;
}
nreadvalue++;
stt.nextToken();
}
System.out.println("" + natt + " attributes have been read");
System.out.println(attributes.toString());
/**************************
* read objects definitions *
**************************/
int exactnatt=natt;
int nobject=1;
while(stt.ttype!=stt.TT_EOF) {
skipBlankLines(stt);
/* number of readed values*/
nreadvalue=0;
/* number of readed attributes (as nreadvalue but
without the object name) */
natt=0;
Obj o;
if (objectname)
o=new Obj("",this);
else
o=new Obj("O" + nobject,this);
nobject++;
/* read attributes values */
while(stt.ttype!=stt.TT_EOL && stt.ttype!=stt.TT_EOF) {
if (objectname==true &&
objectnameindex==nreadvalue &&
nreadvalue==objectnameindex) {
if (stt.ttype==stt.TT_WORD) {
o.name=stt.sval;
nreadvalue++;
} else {
System.out.println("Object name must be a string");
return 1;
}
} else {
if (((Attribute)attributes.elementAt(natt)).ReadAttValue(o,stt)
==1) {
System.out.println("objet " + nobject + " value " + nreadvalue);
return 1;
}
natt++;
nreadvalue++;
}
stt.nextToken();
}
if (natt
return 1;
}
skipBlankLines(stt);
}
System.out.println("" + (nobject-1) + " objects have been read");
// System.out.println(objects.toString());
in.close();
}
catch (Exception e){
System.err.println(e);
}
return 0;
}
/* a method to find an attribute by its name */
public Attribute findAttribute(String name) {
int as=attributes.size();
for (int i=0; i
if (name.equals(a.name))
return a;
}
return null;
}
/* a method to find all attributes except one */
public Vector getCandidateAttributes(String goal) {
int as=attributes.size();
Attribute a;
Vector result=new Vector();
for (int i=0; i
if (!goal.equals(a.name)) {
result.addElement(a);
}
}
return result;
}
/* a method to find a object by its name */
public Obj findObject(String name) {
int os=objects.size;
for (int i=0; i
if (name.equals(o.name))
return o;
}
return null;
}
}
----------------------------
/*
* DbReader.java
* Copyright (C) 1999 Pierre Geurts
*
* This program is free software; you can redistribute it and/or modify
* it under the terms of the GNU General Public License as published by
* the Free Software Foundation; either version 2 of the License, or
* (at your option) any later version.
*
* This program is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
* GNU General Public License for more details.
*
* You should have received a copy of the GNU General Public License
* along with this program; if not, write to the Free Software
* Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
*/
import java.io.*;
public class DbReader {
private static void skipBlankLines(StreamTokenizer stt) throws IOException {
while (stt.ttype==stt.TT_EOL)
stt.nextToken();
}
/* return 1 if there is an error, 0 otherwise */
public static int loadDb (Database db, String filename) {
boolean objectname=false;
int objectnameindex=0;
try {
File f=new File(filename);
Reader in=new FileReader(f);
StreamTokenizer stt=new StreamTokenizer(in);
/* some streamtokenizer initialisations*/
stt.lowerCaseMode(true);
stt.parseNumbers();
stt.eolIsSignificant(true);
stt.commentChar(';');
/* file reading */
stt.nextToken();
skipBlankLines(stt);
/*******************************
* read attributes declaration *
*******************************/
int nreadvalue=0;
int natt=0;
while (stt.ttype!=stt.TT_EOL) {
String attname;
String atttype;
if (stt.ttype!=stt.TT_WORD) {
System.out.println("error in attribute declaration");
return 1;
}
attname=stt.sval;
stt.nextToken();
if (stt.ttype!=stt.TT_WORD) {
System.out.println("error in attribute declaration");
return 1;
}
atttype=stt.sval;
if (attname.equals("object")) {
if (!objectname) {
objectname=true;
objectnameindex=nreadvalue;
} else {
System.out.println("error in attribute declaration");
return 1;
}
} else {
if (atttype.equals("symbolic"))
new SymbAtt(attname,db);
else if (atttype.equals("numerical"))
new NumAtt(attname,db);
else {
System.out.println("not recognised attribute type");
return 1;
}
natt++;
}
nreadvalue++;
stt.nextToken();
}
System.out.println("" + natt + " attributes have been read");
System.out.println(db.attributes.toString());
/**************************
* read objects definitions *
**************************/
int exactnatt=natt;
int nobject=1;
while(stt.ttype!=stt.TT_EOF) {
skipBlankLines(stt);
/* number of readed values*/
nreadvalue=0;
/* number of readed attributes (as nreadvalue but
without the object name) */
natt=0;
Obj o;
if (objectname)
o=new Obj("",db);
else
o=new Obj("O" + nobject,db);
nobject++;
/* read attributes values */
while(stt.ttype!=stt.TT_EOL && stt.ttype!=stt.TT_EOF) {
if (objectname==true &&
objectnameindex==nreadvalue &&
nreadvalue==objectnameindex) {
if (stt.ttype==stt.TT_WORD) {
o.name=stt.sval;
nreadvalue++;
} else {
System.out.println("Object name must be a string");
return 1;
}
} else {
if (((Attribute)db.attributes.elementAt(natt)).ReadAttValue(o,stt)
==1) {
return 1;
}
natt++;
nreadvalue++;
}
stt.nextToken();
}
if (natt
return 1;
}
skipBlankLines(stt);
}
System.out.println("" + nobject + " objects have been read");
System.out.println(db.objects.toString());
in.close();
}
catch (IOException e){
System.err.println(e);
}
return 0;
}
}
----------------------------------
/*
* DecisionTree.java
* Copyright (C) 1999 Pierre Geurts
*
* This program is free software; you can redistribute it and/or modify
* it under the terms of the GNU General Public License as published by
* the Free Software Foundation; either version 2 of the License, or
* (at your option) any later version.
*
* This program is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
* GNU General Public License for more details.
*
* You should have received a copy of the GNU General Public License
* along with this program; if not, write to the Free Software
* Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
*/
import java.util.*;
public class DecisionTree {
/* problem definition */
Database db;
ObjectSet LearningSet;
Vector CandAttributes;
SymbAtt goal;
/* parameter */
double EntropyThres=0;
double ScoreThres=0;
/* root node */
DtNode root;
/* stack of open node */
Stack openNodes=new Stack();
/* Ordered attributes list for the current node */
Vector CurrentNodeAtt;
/**
* create a trivial tree with the default parameters values
*/
DecisionTree(Database d, ObjectSet ls, Vector CandAtt, SymbAtt g) {
db=d;
LearningSet=ls;
CandAttributes=CandAtt;
goal=g;
DtNode.nbnodes=0;
root=new DtNode(LearningSet, g);
root.graphnode=new WNode("open", null, null, null, null, 0, 0, 0, root);
root.graphnode.selected=true;
// openNodes.push(root);
}
/**
* create a trivial tree with the user's parameter values
*/
DecisionTree(Database d, ObjectSet ls, Vector CandAtt, SymbAtt g,
double et, double st) {
EntropyThres=et;
ScoreThres=st;
db=d;
LearningSet=ls;
CandAttributes=CandAtt;
goal=g;
DtNode.nbnodes=0;
root=new DtNode(LearningSet, g);
root.graphnode=new WNode("open", null, null, null, null, 0, 0, 0, root);
root.graphnode.selected=true;
// openNodes.push(root);
}
/**
* build completely the decision tree
*/
public void buildDt() {
// we search this tree for all the remaining open nodes
getOpenNodes();
// then we build the tree
while(!openNodes.empty()) {
expandTopNode();
}
}
/**
* expand the node on the top of stack always with the best choice
*/
public void expandTopNode() {
DtNode topnode=(DtNode)openNodes.pop();
scanNode(topnode);
Vector result=topnode.split(CurrentNodeAtt,0,goal);
//-- we put the successors on the top of the stack (in reverse order)
if (result!=null) {
for (int i=result.size()-1; i>=0; i--) {
openNodes.push(result.elementAt(i));
}
}
}
/**
* scan the attributes for the top node
*/
public Vector scanNode(DtNode topnode) {
CurrentNodeAtt=topnode.scanAttributes(CandAttributes, goal, EntropyThres, ScoreThres);
/* build a vector of textual description of candidate tests */
Vector result=new Vector();
for (int i=0; i
result.addElement(CurrentNodeAtt.lastElement());
return result;
}
/**
* split the top node according to the choice in the CurrentNodeAtt
* Vector
*/
public DtNode splitNode(DtNode topnode, int choice) {
Vector result=topnode.split(CurrentNodeAtt,choice,goal);
if (result!=null) {
// we return the first successor
return (DtNode)result.elementAt(0);
} else {
// otherwise, we return the leftmost open node
return getLeftMostOpenNode();
}
}
/**
* get all the open nodes of the tree (needed because the user can
* now open the node by himself)
*/
public void getOpenNodes() {
openNodes.removeAllElements();
root.getOpenNodes(openNodes);
}
/**
* look for the leftmost open node in the tree
* (this is used after splitting to find the next node to split)
*/
public DtNode getLeftMostOpenNode() {
return root.getLeftMostOpenNode();
}
/**
* get a description of the current open node
*/
public String getNodeDescription(DtNode node) {
return node.getNodeDescription(goal);
}
/**
* propagate this object across the tree and get the associated class
*/
public String Propagate(Obj o) {
return root.getClass(o);
}
/**
* test the dt on an objectset
*/
public double testDt(ObjectSet ts) {
String treeclass, trueclass;
int nberrors=0;
for (int i=0; i
trueclass=(String)goal.Value(ts.elementAt(i));
if (!trueclass.equals(treeclass))
nberrors++;
}
System.out.println("nb of errors : " + nberrors + " out of " + ts.size);
return 1.0*nberrors/ts.size;
}
/**
* test the tree using cross-validation
* argument - the number of subsets into which
* the data base must be divided
*/
public double testDtCrossvalidation(int tssize) {
DecisionTree dt;
int n=LearningSet.size/tssize;
Vector tsvector=new Vector();
ObjectSet remainingobjects=LearningSet;
System.out.println("");
System.out.println("Cross validation : " + n + ", LS : "
+ (LearningSet.size-tssize) + " , TS: " +
tssize);
System.out.println("");
// we construct the set of test sets
for (int i=0; i
tsvector.addElement(os);
remainingobjects=remainingobjects.selectNotIn(os);
}
// we construct the trees
double result=0;
for (int i=0; i
System.out.println("Tree number " + (i+1));
System.out.println("");
ObjectSet ts=(ObjectSet)tsvector.elementAt(i);
dt=new DecisionTree(db, LearningSet.selectNotIn(ts),
CandAttributes, goal,
EntropyThres, ScoreThres);
dt.buildDt();
result+=dt.testDt(ts);
}
// we return the average
return result/n;
}
public void printDt() {
System.out.println(root.printNode(0));
}
}
----------------------------
/*
* DecisionTreeApplet.java
* Copyright (C) 1999 Pierre Geurts
*
* This program is free software; you can redistribute it and/or modify
* it under the terms of the GNU General Public License as published by
* the Free Software Foundation; either version 2 of the License, or
* (at your option) any later version.
*
* This program is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
* GNU General Public License for more details.
*
* You should have received a copy of the GNU General Public License
* along with this program; if not, write to the Free Software
* Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
*/
import java.applet.Applet;
import java.awt.*;
import java.awt.event.*;
import java.util.*;
import java.net.*;
import java.io.*;
/**
* Displays the tree building process
*/
public class DecisionTreeApplet extends Applet
implements ActionListener,ItemListener, Runnable
{
/* Following are workarounds for font size calculations, as Netscape
* reports unappealing font height/ascents on varying platforms. */
static final int FIXED_FONT_HEIGHT = 10;
static final int FIXED_FONT_ASCENT = 3;
boolean running;
Thread t;
WNode root;
WalTreeCanvas tc;
SimpleNodeDrawer snd;
DetailedNodeDrawer dnd;
/* decision tree data */
Database db;
DecisionTree CurrentDt;
DtNode CurrentDtn;
ObjectSet ls;
ObjectSet ts;
Button btn_scan; // scan the attribute
Button btn_split; // split one node (if it is still possible)
Button btn_build; // build the tree
Button btn_refresh; // refresh the graph (actually not useful)
Label lbl_zoom=new Label("Zoom", Label.RIGHT);
Button btn_zoominc;
Button btn_zoomdec;
Choice AttChoice; // selection list for the best attribute
String messagechoice="Click 'Scan Attributes' to see the choices";
TextField tf_opennode=new TextField(); // description of the current node
// input parameters
Panel top=new Panel();
Label lbl_database=new Label("Database url : ", Label.RIGHT);
TextField tf_database= new TextField(65); // to enter the file name
Button btn_loaddb=new Button("Load Database");
// to restart with a new database
Label lbl_goal=new Label("Goal Attribute : ", Label.RIGHT); // goal attribute
Choice GoalAttributeChoice; // a choice list for the goal attribute (only the symbolic)
// (at the same time, it displays all the attribute)
Label lbl_candatt=new Label("Candidate attributes : ");
java.awt.List lst_candatt; // a selection list for the candidate attributes
// learning set selection
Label lbl_learningset=new Label("Learning set :", Label.RIGHT);
Label lbl_lssize=new Label("size :", Label.RIGHT);
TextField tf_lssize=new TextField(5);
Label lbl_lsmode=new Label("Selection mode:", Label.RIGHT);
Choice SelectionChoiceLs;
// tree parameters
Label lbl_entthres=new Label("Entropy Threshold : ", Label.RIGHT);
TextField tf_entthres=new TextField(4);
Label lbl_scorethres=new Label("Inf X LS size Threshold : ", Label.RIGHT);
TextField tf_scorethres= new TextField(4);
double default_scorethres=0.0;
double default_entthres=0.0;
// start tree button
Button btn_starttree=new Button("New Tree");
// test parameters
Label lbl_testset=new Label("Test set :", Label.RIGHT);
Label lbl_tssize=new Label("size :", Label.RIGHT);
TextField tf_tssize=new TextField(5);
Label lbl_tsmode=new Label("Selection mode:", Label.RIGHT);
Choice SelectionChoiceTs;
TextField tf_testresult=new TextField(20);
Button btn_testtree;
Button btn_crossvalidation;
// panels
Panel t_p0=new Panel(new GridLayout(3,1,0,0));
Panel t_loaddb=new Panel(new FlowLayout(FlowLayout.CENTER,5,0));
Panel t_p1=new Panel(new FlowLayout(FlowLayout.CENTER,5,0));
Panel t_p2=new Panel(new FlowLayout(FlowLayout.CENTER,5,0));
Panel t_p3=new Panel(new FlowLayout(FlowLayout.CENTER,5,0));
Panel t_p4=new Panel(new FlowLayout(FlowLayout.CENTER,5,0));
Panel t_p5=new Panel(new BorderLayout());
Panel b_p1=new Panel(new FlowLayout(FlowLayout.CENTER,5,0));
Panel b_p2=new Panel(new FlowLayout(FlowLayout.CENTER,5,0));
Panel b_p3=new Panel(new FlowLayout(FlowLayout.CENTER,5,0));
Panel b_p4=new Panel(new FlowLayout(FlowLayout.CENTER,5,0));
Panel bottom=new Panel();
ScrollPane sp=new ScrollPane();
CheckboxGroup treedrawer=new CheckboxGroup();
Checkbox chk_simple=new Checkbox("Simple",treedrawer,true);
Checkbox chk_detailed=new Checkbox("Detailed",treedrawer,false);
/**
* Initialize the applet.
*/
public void init ()
{
super.init();
String str;
setLayout(new BorderLayout());
t_loaddb.add(lbl_database);
t_loaddb.add(tf_database);
t_loaddb.add(btn_loaddb);
t_p1.add(lbl_goal);
t_p1.add(GoalAttributeChoice=new Choice());
t_p2.add(lbl_entthres);
t_p2.add(tf_entthres);
t_p3.add(lbl_scorethres);
t_p3.add(tf_scorethres);
t_p4.add(lbl_learningset);
t_p4.add(lbl_lssize);
t_p4.add(tf_lssize);
t_p4.add(lbl_lsmode);
t_p4.add(SelectionChoiceLs=new Choice());
t_p4.add(btn_starttree);
SelectionChoiceLs.add("Random");
SelectionChoiceLs.add("First");
SelectionChoiceLs.add("Last");
t_p5.add(lbl_candatt,"North");
t_p5.add(lst_candatt=new java.awt.List(5,true),"Center");
t_p0.add(t_p1) ; t_p0.add(t_p2) ; t_p0.add(t_p3);
top.setLayout(new BorderLayout());
top.add(t_loaddb, "North");
top.add(t_p0, "West");
top.add(t_p5,"Center");
top.add(t_p4,"South");
// center : the tree canvas
sp.add(tc=new WalTreeCanvas());
// bottom : control of the building process
bottom.setLayout(new GridLayout(4,1,0,0));
b_p1.add(tf_opennode=new TextField(100));
tf_opennode.setEditable(false);
bottom.add(b_p1);
b_p3.add(AttChoice=new Choice());
bottom.add(b_p3);
b_p2.add(btn_scan=new Button("Scan attributes"));
b_p2.add(btn_split=new Button("Split"));
b_p2.add(btn_build=new Button("Build"));
b_p2.add(chk_simple);
b_p2.add(chk_detailed);
b_p2.add(btn_refresh=new Button("Refresh"));
b_p2.add(lbl_zoom);
b_p2.add(btn_zoominc=new Button("+"));
b_p2.add(btn_zoomdec=new Button("-"));
bottom.add(b_p2);
b_p4.add(lbl_testset);
b_p4.add(lbl_tssize);
b_p4.add(tf_tssize);
b_p4.add(lbl_tsmode);
b_p4.add(SelectionChoiceTs=new Choice());
SelectionChoiceTs.add("Not in ls");
SelectionChoiceTs.add("Random");
SelectionChoiceTs.add("First");
SelectionChoiceTs.add("Last");
SelectionChoiceTs.add("Learning set");
b_p4.add(btn_testtree=new Button("Test tree"));
b_p4.add(btn_crossvalidation=new Button("Cross Validation"));
b_p4.add(tf_testresult);
tf_testresult.setEditable(false);
bottom.add(b_p4);
add(top, "North");
add(bottom, "South");
add(sp, "Center");
snd=new SimpleNodeDrawer(tc);
dnd=new DetailedNodeDrawer(tc);
tc.nd=snd;
tc.setParentDistance(30);
// load the database
if (getParameter("DBFILE")!=null) {
URL u;
try {
u=new URL(getDocumentBase(), getParameter("DBFILE"));
initDb(u);
} catch (MalformedURLException e) {
System.out.println("-- database file not found");
showStatus("Bad url");
}
}
// different actions binding
// buttons
btn_split.addActionListener(this);
btn_refresh.addActionListener(this);
btn_scan.addActionListener(this);
btn_starttree.addActionListener(this);
btn_testtree.addActionListener(this);
btn_crossvalidation.addActionListener(this);
btn_build.addActionListener(this);
btn_loaddb.addActionListener(this);
btn_zoominc.addActionListener(this);
btn_zoomdec.addActionListener(this);
// check button
chk_simple.addItemListener(this);
chk_detailed.addItemListener(this);
// selection list
SelectionChoiceTs.addItemListener(this);
// mouse
MyMouseListener ml=new MyMouseListener();
tc.addMouseListener(ml);
}
public void loadDb() {
URL u;
try {
u=new URL(tf_database.getText());
initDb(u);
tc.setTree(root);
tc.repaint();
} catch (MalformedURLException e) {
System.out.println("-- database file not found");
showStatus("Bad url");
}
}
public void initDb(URL u) {
db = new Database();
System.out.println("Database loading:");
showStatus("Loading database");
if (db.loadDb(u)==1) {
showStatus("Loading failed : bad file format");
return;
}
tf_database.setText(u.toString());
if (db.objects.size==0) {
System.out.println("no object");
}
//-- fill candidate attribute selection list
lst_candatt.removeAll();
GoalAttributeChoice.removeAll();
int last_symb=0;
for (int i=0; i
lst_candatt.add(att.describe());
lst_candatt.select(i);
if (att instanceof SymbAtt) {
GoalAttributeChoice.add(att.toString());
last_symb=i;
}
}
GoalAttributeChoice.select(GoalAttributeChoice.getItemCount()-1);
lst_candatt.deselect(last_symb);
//-- initialise score and entropy threshold
tf_entthres.setText("" + default_entthres);
tf_scorethres.setText("" + default_scorethres);
//-- initialise ls size and type
tf_lssize.setText("" + (int)(2*db.objects.size/3));
SelectionChoiceLs.select(0);
tf_tssize.setText("" + (int)(db.objects.size/3));
SelectionChoiceTs.select(0);
AttChoice.add(messagechoice);
AttChoice.select(0);
//-- initialise the tree
root=null;
//-- garbage collecting after this (to remove the previous database)
System.gc();
showStatus("done");
setComment("");
}
public void NewTree() {
//-- learning set selection
int lssize=GetLsSize();
int lsmode=GetLsMode();
if (lsmode==0)
ls=db.objects.selectRandom(lssize);
else if (lsmode==1)
ls=db.objects.selectFirst(lssize);
else if (lsmode==2)
ls=db.objects.selectLast(lssize);
//-- we build a trivial tree
CurrentDt=new DecisionTree(db, ls, GetCandAtt(), GetGoalAttribute(),
GetEntThres(), GetScoreThres());
CurrentDtn=CurrentDt.root;
root=CurrentDt.root.graphnode;
//-- we initialise the graphical interface
setComment(CurrentDt.getNodeDescription(CurrentDtn));
AttChoice.removeAll();
AttChoice.add(messagechoice);
AttChoice.select(0);
refreshcurrenttree();
}
/**
* some functions to get the parameters value
*/
public Vector GetCandAtt() {
int[] index=lst_candatt.getSelectedIndexes();
if (index.length==0)
return new Vector();
Vector result=new Vector();
for (int i=0; i
}
return result;
}
public SymbAtt GetGoalAttribute() {
return (SymbAtt)db.findAttribute(GoalAttributeChoice.getSelectedItem());
}
public double GetEntThres() {
return (new Double(tf_entthres.getText())).doubleValue();
}
public double GetScoreThres() {
return (new Double(tf_scorethres.getText())).doubleValue();
}
public int GetLsSize() {
if (tf_lssize.getText()=="")
return 0;
else
return Integer.parseInt(tf_lssize.getText());
}
public int GetLsMode() {
return SelectionChoiceLs.getSelectedIndex();
}
public int GetTsSize() {
if (tf_lssize.getText()=="")
return 0;
else
return Integer.parseInt(tf_tssize.getText());
}
public int GetTsMode() {
return SelectionChoiceTs.getSelectedIndex();
}
public void setComment(String t) {
tf_opennode.setText(t);
}
/**
* Start the main applet thread.
*/
public void start ()
{
running = true;
t = new Thread(this);
t.start();
}
/**
* Stop the applet.
*/
public void stop ()
{
running = false;
}
/**
* Main event loop.
*/
public void run () { }
/**
* scan all the attributes at the top node for the best attribute.
* display the result into the choice list.
*/
public void Scanatt() {
if (CurrentDtn==null)
return;
Vector choices=CurrentDt.scanNode(CurrentDtn);
AttChoice.removeAll();
for (int i=0; i
}
/**
* Split the current node
*
*/
public void SplitMore() {
if (CurrentDtn==null)
return;
if (CurrentDtn.type!="open") {
// if the node is not open, we open it
CurrentDtn.open();
}
if (AttChoice.getItem(0)==messagechoice) {
//-- the user has not asked for attributes scanning
CurrentDt.scanNode(CurrentDtn);
changeSelectedNode(CurrentDt.splitNode(CurrentDtn,0));
} else {
//-- we take into account the user's choice
changeSelectedNode(CurrentDt.splitNode(CurrentDtn,AttChoice.getSelectedIndex()));
}
refreshcurrenttree();
}
public void changeSelectedNode(DtNode dtn) {
if (CurrentDtn!=null)
CurrentDtn.graphnode.selected=false;
if (AttChoice.getItem(0)!=messagechoice) {
AttChoice.removeAll();
AttChoice.add(messagechoice);
AttChoice.select(0);
}
CurrentDtn=dtn;
if (CurrentDtn!=null) {
CurrentDtn.graphnode.selected=true;
setComment(CurrentDt.getNodeDescription(CurrentDtn));
} else {
setComment("");
}
}
public void buildalltree() {
showStatus("Building the tree...");
CurrentDt.buildDt();
changeSelectedNode(null);
refreshcurrenttree();
CurrentDt.printDt();
showStatus("done");
}
public void testtree() {
//-- learning set selection
showStatus("Testing the tree...");
int tssize=GetTsSize();
int tsmode=GetTsMode();
if (tsmode==0)
ts=db.objects.selectNotIn(ls);
else if (tsmode==1)
ts=db.objects.selectRandom(tssize);
else if (tsmode==2)
ts=db.objects.selectFirst(tssize);
else if (tsmode==3)
ts=db.objects.selectLast(tssize);
else if (tsmode==4)
ts=ls;
String result="" + CurrentDt.testDt(ts)*100;
if (result.length()<5)
tf_testresult.setText("" + result + "%");
else
tf_testresult.setText("" + result.substring(0,5) + "%");
showStatus("done");
}
public void CrossValidation() {
showStatus("Cross validation...please wait");
double result=CurrentDt.testDtCrossvalidation(GetTsSize());
String sr="" + result*100;
if (sr.length()<5)
tf_testresult.setText(sr + "%");
else
tf_testresult.setText(sr.substring(0,5) + "%");
showStatus("done");
}
public void actionPerformed(ActionEvent event) {
String command=event.getActionCommand();
if (command=="Split" && root!=null) {
SplitMore();
} else if (command=="Build" && root!=null) {
buildalltree();
} else if (command=="Scan attributes" && root!=null) {
Scanatt();
} else if (command=="Refresh" && root!=null) {
refreshcurrenttree();
} else if (command=="Test tree" && root!=null) {
testtree();
} else if (command=="New Tree") {
NewTree();
} else if (command=="Load Database") {
loadDb();
} else if (command=="Cross Validation" && root!=null) {
CrossValidation();
} else if (command=="+") {
snd.increaseZoom();
dnd.increaseZoom();
tc.repaint();
} else if (command=="-") {
snd.decreaseZoom();
dnd.decreaseZoom();
tc.repaint();
}
}
public void refreshcurrenttree() {
if (root==null)
return;
tc.nd.computeNodeSize(root);
tc.setTree(root);
tc.repaint();
}
public void itemStateChanged(ItemEvent event) {
String command=(String)event.getItem();
if (command == "Simple") {
tc.nd=snd;
refreshcurrenttree();
} else if (command == "Detailed") {
tc.nd=dnd;
if (root!=null) {
dnd.initWidth(root);
refreshcurrenttree();
}
} else if (command == "Not in ls") {
tf_tssize.setText("" + (db.objects.size - Integer.parseInt(tf_lssize.getText())));
} else if (command == "Learning set") {
tf_tssize.setText(tf_lssize.getText());
}
}
/* gestion de la souris */
class MyMouseListener extends MouseAdapter {
public void mousePressed(MouseEvent e) {
int x=e.getX();
int y=e.getY();
if (root!=null) {
DtNode dtn=root.getPointedNode((int)(x/tc.nd.zoom),(int)(y/tc.nd.zoom));
if (dtn!=null) {
// select this node
changeSelectedNode(dtn);
// retrace the graph (there must exist a better way to do this)
tc.repaint();
}
}
}
}
}
-------------------------
/*
* DetailedNodeDrawer.java
* Copyright (C) 1999 Pierre Geurts
*
* This program is free software; you can redistribute it and/or modify
* it under the terms of the GNU General Public License as published by
* the Free Software Foundation; either version 2 of the License, or
* (at your option) any later version.
*
* This program is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
* GNU General Public License for more details.
*
* You should have received a copy of the GNU General Public License
* along with this program; if not, write to the Free Software
* Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
*/
import java.awt.*;
import java.util.*;
/**
* a abstract class to allow many representation for
* a node
*/
public class DetailedNodeDrawer extends NodeDrawer {
FontMetrics metrics_small,metrics_big, metrics_current;
Font smallfont, bigfont;
int SMALL_FIXED_FONT_HEIGHT=8;
int BIG_FIXED_FONT_HEIGHT=14;
int current_font_height;
int default_border=10;
Vector colours=new Vector();
int max_width=60;
int max_height=40;
int max_ls_size=1;
double coef;
Canvas cv;
DetailedNodeDrawer(Canvas c) {
cv=c;
bigfont=new Font("Helvetica", Font.PLAIN, BIG_FIXED_FONT_HEIGHT);
c.setFont(bigfont);
metrics_big=c.getFontMetrics(c.getFont());
smallfont=new Font("Helvetica", Font.PLAIN, SMALL_FIXED_FONT_HEIGHT);
c.setFont(smallfont);
metrics_small=c.getFontMetrics(c.getFont());
metrics_current=metrics_small;
current_font_height=SMALL_FIXED_FONT_HEIGHT;
coef=Math.exp(1)*20;
colours.addElement(Color.black);
colours.addElement(Color.red);
colours.addElement(Color.green);
colours.addElement(Color.blue);
colours.addElement(Color.orange);
colours.addElement(Color.darkGray);
colours.addElement(Color.cyan);
colours.addElement(Color.gray);
colours.addElement(Color.magenta);
colours.addElement(Color.pink);
colours.addElement(Color.black);
colours.addElement(Color.yellow);
colours.addElement(Color.white);
colours.addElement(Color.red);
colours.addElement(Color.green);
colours.addElement(Color.blue);
colours.addElement(Color.orange);
colours.addElement(Color.darkGray);
colours.addElement(Color.cyan);
colours.addElement(Color.gray);
colours.addElement(Color.magenta);
colours.addElement(Color.pink);
colours.addElement(Color.black);
colours.addElement(Color.yellow);
colours.addElement(Color.white);
}
public void initWidth(WNode t) {
t.width=0;
if (t.sibling!=null) {
initWidth(t.sibling);
}
if (t.child!=null) {
initWidth(t.child);
}
}
public void computeNodeSize(WNode t) {
max_ls_size=t.dtnode.subset.size;
computeSize(t);
}
public void computeSize(WNode t) {
if (t.width==0) { //-- we compute the size only once
double correction;
if (t.dtnode.subset.size!=0)
correction=Math.log(coef)/Math.log(coef*max_ls_size/t.dtnode.subset.size);
else
correction=Math.log(coef)/Math.log(coef*max_ls_size);
t.height=(int)(max_width*correction);
t.width=(int)(max_height*correction);
}
t.border=default_border;
if (t.sibling!=null) {
computeSize(t.sibling);
}
if (t.child!=null) {
computeSize(t.child);
}
}
public void drawArc(Graphics g, int x1, int y1, int x2,
int y2, String arclabel) {
g.setColor(Color.black);
g.drawLine((int)(x1*zoom), (int)(y1*zoom), (int)(x2*zoom),(int)(y2*zoom));
g.drawString(arclabel,
(int)(((x1 + x2)*zoom - metrics_current.stringWidth(arclabel)) / 2),
(int)((y1 + y2)*zoom/2));
}
public void drawNode(Graphics g, WNode t) {
int tposx=(int)(t.pos.x*zoom);
int tposy=(int)(t.pos.y*zoom);
int tw=(int)(t.width*zoom);
int th=(int)(t.height*zoom);
int current_x=tposy*t.dtnode.subset.size;
int incr_x;
int y=tposx;
//-- draw the box
if (t.dtnode.subset.size!=0) {
for (int i=0; i
incr_x=th*t.dtnode.subset.summary[i];
g.setColor((Color)colours.elementAt(i+1));
g.fillRect((int)(current_x/t.dtnode.subset.size),y,
(int)(incr_x/t.dtnode.subset.size)+1,tw);
current_x+=incr_x;
}
}
}
g.setColor(Color.black);
g.drawRect(tposy, tposx, th, tw);
//-- we highlight the current open node
if (t.selected) {
g.setColor(Color.pink);
g.drawRect(tposy-current_font_height, tposx-current_font_height,
th+2*current_font_height, tw+2*current_font_height);
}
//-- we put information beneath the box ...
String bottomtext;
if (t.dtnode.type.equals("test"))
bottomtext=t.label;
else if (t.dtnode.type.equals("open"))
bottomtext="open";
else if (t.dtnode.type.equals("open"))
bottomtext="leaf : " + t.dtnode.majclass;
else
bottomtext="error";
g.setColor(Color.black);
g.drawString(t.label,
tposy + (th - metrics_current.stringWidth(t.label)) / 2,
tposx + tw + current_font_height);
//-- ... and on top of the box
g.drawString(t.dtnode.name, tposy, tposx+1);
}
// increase the zoom
public void increaseZoom() {
if (zoom==0.5)
zoom=0.7;
else if (zoom==0.7)
zoom=1.0;
else if (zoom==1.0)
zoom=1.2;
else if (zoom==1.2) {
zoom=1.5;
metrics_current=metrics_big;
current_font_height=BIG_FIXED_FONT_HEIGHT;
cv.setFont(bigfont);
} else if (zoom==1.5)
zoom=2.0;
else if (zoom==2.0)
zoom=2.5;
else if (zoom==2.5)
zoom=3.0;
}
// decrease the zoom
public void decreaseZoom() {
if (zoom==3.0)
zoom=2.5;
else if (zoom==2.5)
zoom=2.0;
else if (zoom==2.0)
zoom=1.5;
else if (zoom==1.5) {
zoom=1.2;
metrics_current=metrics_small;
current_font_height=SMALL_FIXED_FONT_HEIGHT;
cv.setFont(smallfont);
} else if (zoom==1.2)
zoom=1.0;
else if (zoom==1.0)
zoom=0.7;
else if (zoom==0.7)
zoom=0.5;
}
}
----------------------------------
/*
* DtNode.java
* Copyright (C) 1999 Pierre Geurts
*
* This program is free software; you can redistribute it and/or modify
* it under the terms of the GNU General Public License as published by
* the Free Software Foundation; either version 2 of the License, or
* (at your option) any later version.
*
* This program is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
* GNU General Public License for more details.
*
* You should have received a copy of the GNU General Public License
* along with this program; if not, write to the Free Software
* Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
*/
import java.util.*;
public class DtNode {
static int nbnodes;
ObjectSet subset;
String type="open"; // leaf, test or open
String majclass="default"; // the majority class in this node
String name;
WNode graphnode; // for the tree visualisation
Test test;
Vector successors;
DtNode(ObjectSet s, SymbAtt goal) {
subset=s;
name="node" + nbnodes++;
ComputeInfoNode(goal);
}
/**
* Compute some information about this node (entropy, subset summary
* and class maj). This should be call when the node is created.
*/
public void ComputeInfoNode(SymbAtt goal) {
subset.computeEntropy(goal);
majclass=subset.getMajClass(goal);
}
/**
* Scan all the cancidate attributes, compute the information gain of the
* best score. Return a vector of attributes ordered by decreasing values
* of information.
*/
public Vector scanAttributes(Vector ca, SymbAtt goal, double entthres, double scorethres) {
Vector result=new Vector();
System.out.println("expanding " + getNodeDescription(goal));
//-- no object in this node (this should never happen)
if (subset.size==0) {
result.addElement("No object in this node -> a leaf");
return result;
}
//-- entropy is low enough, we can stop splitting this node
if (subset.entropy<=entthres) {
result.addElement("Entropy low enough (threshold=" +
entthres + ") -> a leaf");
return result;
}
//-- in the other case, we scan the attributes
// System.out.println("number of candidate attributes : " + ca.size());
System.out.print("[");
double score;
int i=0,j=0;
Attribute att;
for (; i
att=(Attribute)ca.elementAt(i);
score=att.bestscore(subset,goal);
// System.out.println(att.name + " " + score);
//-- the score must be greater than the threshold (forward pruning)
if ((score*subset.size)>scorethres) {
j=0;
while (j
j++;
if (j==result.size())
result.addElement(att);
else
result.insertElementAt(att,j);
}
}
System.out.println("]");
//-- we always let the possibility to user to make this node a leaf
result.addElement("make this node a leaf");
return result;
}
public Vector split(Vector scanresult, int choice, SymbAtt goal) {
//-- make this node a leaf
if (choice==scanresult.size()-1) {
System.out.println((String)scanresult.elementAt(choice));
type="leaf";
buildGraphLeafNode(goal);
return null;
}
//-- we take the attribute and construct the partition
Attribute selectedatt=(Attribute)scanresult.elementAt(choice);
Partition partition=selectedatt.bestpartition(subset,goal);
test=partition.test;
successors=new Vector();
type="test";
System.out.println("-> a test node (score : " + selectedatt.lastbestscore +
" , test : " + test.TestDescription + ")");
//-- we create the successor nodes
for (int i=0; i
goal));
}
//-- we create the graphnodes
buildGraphTestNodes();
//- we return the successors (open nodes)
return successors;
}
/**
* expand this node and return a vector of open nodes resulting from
* the expansion
*/
public Vector expand(Vector ca, SymbAtt goal, double entthres, double scorethres) {
//-- if the subset is empty, this is a leaf and the class is default
if (subset.size==0) {
System.out.println("-> a leaf (no objects)");
majclass="default";
type="leaf";
buildGraphLeafNode(goal);
return null;
}
System.out.println("expanding " + getNodeDescription(goal));
//-- if the entropy is lower than the threshold, then we stop the splitting
if (subset.entropy<=entthres) { // a new leaf
System.out.println("-> a leaf (entropy low, " + subset.entropy
+ "<=" + entthres + ")");
type="leaf";
buildGraphLeafNode(goal);
return null;
}
//-- otherwise, we screen all the attributes
double bestscore=0,score;
Attribute bestatt=null,att;
System.out.print("[");
for (int i=0; i
att=(Attribute)ca.elementAt(i);
score=att.bestscore(subset,goal);
if (score>bestscore) {
bestscore=score;
bestatt=att;
}
}
System.out.println("]");
//-- the best score must be greater than the threshold (stop-splitting rule)
if ((bestscore*subset.size)<=scorethres) {
System.out.println("-> a leaf (score too low, "
+ (bestscore*subset.size) + "<=" +
scorethres + ")");
type="leaf";
buildGraphLeafNode(goal);
return null;
}
//-- we construct the partition of the learning set
Partition partition=bestatt.bestpartition(subset,goal);
test=partition.test;
successors=new Vector();
type="test";
System.out.println("-> a test node (score : " + bestscore +
" , test : " + test.TestDescription + ")");
//-- we create the successor nodes
for (int i=0; i
goal));
}
//-- we create the graphnodes
buildGraphTestNodes();
//-- we return the successors (open node)
return successors;
}
/**
* complete the graphnode for a leaf
*/
public void buildGraphLeafNode(SymbAtt goal) {
graphnode.label=majclass;
if (majclass.equals("default")) {
graphnode.colour=0;
} else {
graphnode.colour=goal.values.indexOf(majclass)+1;
}
}
/**
* build the graphnodes for the successors of this node
*/
public void buildGraphTestNodes() {
//-- first we put the label of this node (the size will be computed afterwards)
graphnode.label=test.TestDescription;
//-- then the first successor
DtNode dtchild=(DtNode)successors.elementAt(0);
dtchild.graphnode=new WNode("open", (String)test.valuesIssues.elementAt(0),
graphnode, null, null,0,0,0,dtchild);
graphnode.child=dtchild.graphnode;
WNode previousgchild=dtchild.graphnode;
DtNode nextdtchild;
//-- and finally the others
for (int i=1; i
nextdtchild.graphnode=new WNode("open", (String)test.valuesIssues.elementAt(i),
graphnode,null,null,0,0,0,nextdtchild);
previousgchild.sibling=nextdtchild.graphnode;
previousgchild=nextdtchild.graphnode;
}
}
/**
* open a node (destroy all his successors and tests)
*/
public void open() {
test=null;
type="open";
graphnode.child=null;
graphnode.colour=0;
graphnode.label="open";
}
/**
* get all the open nodes of this subtree (in a depth first way but
* in the oposite direction (right to left and bottom to top)
*/
public void getOpenNodes(Stack opennodes) {
if (type.equals("open"))
opennodes.push(this);
else if (successors!=null) {
for (int i=successors.size()-1; i>=0; i--) {
((DtNode)successors.elementAt(i)).getOpenNodes(opennodes);
}
}
}
/**
* get the leftmost open node
*/
public DtNode getLeftMostOpenNode() {
if (type.equals("open"))
return this;
else if (successors!=null) {
for (int i=0; i
if (dtn!=null)
return dtn;
}
return null;
} else
return null;
}
/**
* return the class associated to this object by the subtree corresponding
* to this node
*/
public String getClass(Obj o) {
if (type.equals("leaf") || type.equals("open"))
return majclass;
else
return ((DtNode)successors.elementAt(test.TestIndex(o))).getClass(o);
}
/**
* give a textual description of this node
*/
public String getNodeDescription(SymbAtt goal) {
String s="";
s+=name;
s+=" - LS : " + subset.getSummaryString(goal);
s+=" - ENTROPY : " + subset.entropy;
return s;
}
/**
* print n spaces (to pretty print the decision tree)
*/
private String printNtab(int n) {
String result="";
for (int i=0; i
}
return result;
}
/**
* print a textual description of the subtree corresponding
* to this node.
*/
public String printNode(int depth) {
String result="";
if (type.equals("leaf") || type.equals("open")) {
result+=printNtab(depth);
result+="return \"" + majclass + "\";\n";
} else if (type.equals("test")) {
for (int i=0; i
if (i!=0)
result+="} else ";
result+="if (" + test.testDescription(i) + ") {\n";
result+=((DtNode)successors.elementAt(i)).printNode(depth+1);
}
result+=printNtab(depth) + "}\n";
} else {
System.out.println("printNode - bad node type");
return "";
}
return result;
}
}
-------------------------------
/*
* Entropy.java
* Copyright (C) 1999 Pierre Geurts
*
* This program is free software; you can redistribute it and/or modify
* it under the terms of the GNU General Public License as published by
* the Free Software Foundation; either version 2 of the License, or
* (at your option) any later version.
*
* This program is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
* GNU General Public License for more details.
*
* You should have received a copy of the GNU General Public License
* along with this program; if not, write to the Free Software
* Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
*/
import java.io.*;
/* this class contains some functions to calculate
* entropy values
*/
public class Entropy{
static double entropy(int freq[], int size, int sum) {
// when we don't have example then the entropy is zero
if (sum==0)
return 0.0;
double result=sum*java.lang.Math.log(sum);
for (int i=0; i
result-=freq[i]*java.lang.Math.log(freq[i]);
}
result/=java.lang.Math.log((double)2.0);
result/=sum;
return result;
}
}
-------------------------
/*
* NodeDrawer.java
* Copyright (C) 1999 Pierre Geurts
*
* This program is free software; you can redistribute it and/or modify
* it under the terms of the GNU General Public License as published by
* the Free Software Foundation; either version 2 of the License, or
* (at your option) any later version.
*
* This program is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
* GNU General Public License for more details.
*
* You should have received a copy of the GNU General Public License
* along with this program; if not, write to the Free Software
* Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
*/
import java.awt.*;
import java.util.*;
/**
* a abstract class to allow many representation for
* a node
*/
public abstract class NodeDrawer {
double zoom=1.0;
abstract void computeNodeSize(WNode t);
abstract void drawNode(Graphics g, WNode t);
abstract void drawArc(Graphics g, int x1, int y1, int x2,
int y2, String arclabel);
abstract void increaseZoom();
abstract void decreaseZoom();
}
--------------------------
/*
* NumAtt.java
* Copyright (C) 1999 Pierre Geurts
*
* This program is free software; you can redistribute it and/or modify
* it under the terms of the GNU General Public License as published by
* the Free Software Foundation; either version 2 of the License, or
* (at your option) any later version.
*
* This program is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
* GNU General Public License for more details.
*
* You should have received a copy of the GNU General Public License
* along with this program; if not, write to the Free Software
* Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
*/
import java.io.*;
import java.util.*;
public class NumAtt extends Attribute{
/* le domaine de l'attribut dans la bd */
float rangemin=(float)1.0, rangemax=(float)0.0;
/* le meilleur score precedemment obtenu par cet attribut */
float bestthreshold;
NumAtt(String s, Database dab) {
name=s;
db=dab;
index=db.addAttToDb(this);
}
public void SetAttValue(Obj o,Object f) {
float fl=((Float)f).floatValue();
if (rangemin>rangemax) {
rangemin=fl;
rangemax=fl;
} else {
if (fl
else if (fl>rangemax)
rangemax=fl;
}
o.attributesvalues.setElementAt(f,index);
}
public int ReadAttValue(Obj o, StreamTokenizer stt) {
if (stt.ttype==stt.TT_NUMBER) {
SetAttValue(o,new Float(stt.nval));
return 0;
} else {
System.out.println("A numerical value was expected");
return 1;
}
}
public String describe() {
return toString()+ " - numerical - range : [" + rangemin + "," + rangemax + "]";
}
public String describeBestTest() {
return toString() + " - threshold : " + bestthreshold + " - Information gain : " +
lastbestscore;
}
/* return the best partition for a numerical attribute
* we assume that the best threshold is already computed (by
* using bestscore
*/
public Partition bestpartition(ObjectSet os, SymbAtt goal) {
TestNum t=new TestNum(this,bestthreshold);
Vector v=os.splitOn(t);
return new Partition(t,v);
}
/* searches the best threshold value for a numerical attribute
* assumes that the objectset size is greater than 0
*/
public double bestscore(ObjectSet os, SymbAtt goal) {
// first, the set is ordered by increasing attribute values
os.orderOn(this);
// then prepare the data, we suppose that we have already
// computed the entropy value
int gvs=goal.values.size();
int freqyes[]=new int[gvs+1];
int freqno[]=new int[gvs+1];
// in the beginning, the test is false for all objects
for (int i=0; i
}
freqno[gvs]=os.size;
float currentthreshold=rangemin;
double bestscore=0,actualscore=os.entropy;
double entyes,entno;
int ico;
int iconext=goal.values.indexOf(goal.Value((Obj)os.elementAt(0)));
float av;
float avnext=((Float)Value((Obj)os.elementAt(0))).floatValue();
for (int i=0; i
ico=iconext;
iconext=goal.values.indexOf(goal.Value((Obj)os.elementAt(i+1)));
av=avnext;
avnext=((Float)Value((Obj)os.elementAt(i+1))).floatValue();
freqno[ico]--;freqno[gvs]--;
freqyes[ico]++;freqyes[gvs]++;
if (
// ico!=iconext && // i'm not sure of this -> skip it
av!=avnext
) {
// only if the class of this point is different from the next point
// class and if its attribute value if also different from the next
// point attribute value
entno=Entropy.entropy(freqno,gvs,freqno[gvs]);
entyes=Entropy.entropy(freqyes,gvs,freqyes[gvs]);
actualscore=os.entropy-(freqno[gvs]*entno+freqyes[gvs]*entyes)/os.size;
if (actualscore>bestscore) {
bestscore=actualscore;
currentthreshold=(float)((av+avnext)/2.0);
}
}
}
bestthreshold=currentthreshold;
lastbestscore=bestscore;
return bestscore;
}
}
--------------------------
/*
* Obj.java
* Copyright (C) 1999 Pierre Geurts
*
* This program is free software; you can redistribute it and/or modify
* it under the terms of the GNU General Public License as published by
* the Free Software Foundation; either version 2 of the License, or
* (at your option) any later version.
*
* This program is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
* GNU General Public License for more details.
*
* You should have received a copy of the GNU General Public License
* along with this program; if not, write to the Free Software
* Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
*/
import java.util.*;
public class Obj {
/* the name of the object */
String name;
/* the database it belongs to */
Database db;
/* the vector of attributes values */
Vector attributesvalues=new Vector();
Obj(String s, Database db) {
this.db=db;
name=s;
db.addObjToDb(this);
/* it allocates place for the attribute values */
attributesvalues.setSize(db.attributes.size());
}
public String toString() {
return name;
}
}
----------------------
/*
* ObjectSet.java
* Copyright (C) 1999 Pierre Geurts
*
* This program is free software; you can redistribute it and/or modify
* it under the terms of the GNU General Public License as published by
* the Free Software Foundation; either version 2 of the License, or
* (at your option) any later version.
*
* This program is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
* GNU General Public License for more details.
*
* You should have received a copy of the GNU General Public License
* along with this program; if not, write to the Free Software
* Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
*/
import java.util.*;
/* simplement un vecteur d'object, on verra apres si on garde
ce niveau d'abstraction ou pas
*/
public class ObjectSet {
/* objects list*/
Vector objectslist;
/* a cache value for the entropy in this set */
double entropy;
/* the size of the learning set */
int size;
/* summary, the frequence of each class in this set */
int summary[];
ObjectSet(Vector vo) {
objectslist=vo;
size=vo.size();
}
ObjectSet() {
objectslist=new Vector();
size=0;
}
/* only for compatibility (primary an objectset was simply a vector) */
public int size() {
return size;
}
public Obj elementAt(int index) {
return (Obj)objectslist.elementAt(index);
}
public void addElement(Obj o) {
objectslist.addElement(o);
size++;
}
public void setElementAt(Obj o, int index) {
objectslist.setElementAt(o, index);
}
public int indexOf(Obj o) {
return objectslist.indexOf(o);
}
public String toString() {
return objectslist.toString();
}
/* split a set according to the given test */
public Vector splitOn(Test t) {
int index;
Vector v=new Vector();
Obj o;
for (int i=0; i
}
for (int i=0; i
index=t.TestIndex(o);
((ObjectSet)v.elementAt(index)).addElement(o);
}
return v;
}
/* methods to select subset of objects from the database */
/* select the first n objects from this subset */
public ObjectSet selectFirst(int n) {
ObjectSet os=new ObjectSet();
for (int i=0;i
}
return os;
}
/* select the last n objects from this subset */
public ObjectSet selectLast(int n) {
ObjectSet os=new ObjectSet();
int i;
if (n>size)
i=0;
else
i=size-n;
for (;i
}
return os;
}
/* select randomly n objects from this set (very stupid) */
public ObjectSet selectRandom(int n) {
ObjectSet os=new ObjectSet();
Vector v=(Vector)objectslist.clone();
int sv=size;
int pos;
if (n>size)
n=size;
for (int i=0;i
os.addElement((Obj)v.elementAt(pos));
v.removeElementAt(pos);
sv--;
}
return os;
}
/* select objects which are not in a given subset */
public ObjectSet selectNotIn(ObjectSet oset) {
ObjectSet os=new ObjectSet();
Obj o;
for (int i=0;i
if (oset.indexOf(o)==-1)
os.addElement(o);
}
return os;
}
/* method to compute the entropy of an symbolic attribute in this subset
* it computes also the subset summary
*/
public double computeEntropy(SymbAtt goal) {
int sum=size;
int i,x,gvs=goal.values.size();
summary=new int[gvs];
for (i=0; i
summary[x]++;
}
entropy=Entropy.entropy(summary, gvs, sum);
return entropy;
}
/* give a textual description of the subset summary */
public String getSummaryString(SymbAtt goal) {
String s="";
for (int i=0; i
s+=":" + summary[i]+ " ";
}
s+="total:" + size;
return s;
}
/* method that gives the majority class in this subset (using the summary) */
public String getMajClass(SymbAtt goal) {
int imax=0;
int maxfreq=summary[0];
for (int i=1; i
maxfreq=summary[i];
imax=i;
}
}
return (String)goal.values.elementAt(imax);
}
/* order a subset on numerical attribute values
* use quicksort algorithm
*/
public void orderOn(NumAtt att) {
orderOn(att,0,size-1);
}
public void orderOn(NumAtt att, int lo0, int hi0) {
int lo=lo0;
int hi=hi0;
float mid;
if (hi0>lo0) {
mid = ((Float)att.Value((Obj)objectslist.elementAt((lo0+hi0)/2))).floatValue();
while (lo<= hi) {
while((lo
while((hi>lo0) &&
(((Float)att.Value((Obj)objectslist.elementAt(hi))).floatValue()>mid))
--hi;
if(lo<=hi) {
Object tmp=objectslist.elementAt(lo);
objectslist.setElementAt(objectslist.elementAt(hi),lo);
objectslist.setElementAt(tmp,hi);
++lo;
--hi;
}
}
if(lo0
if (lo
}
}
}
---------------------------
/*
* Partition.java
* Copyright (C) 1999 Pierre Geurts
*
* This program is free software; you can redistribute it and/or modify
* it under the terms of the GNU General Public License as published by
* the Free Software Foundation; either version 2 of the License, or
* (at your option) any later version.
*
* This program is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
* GNU General Public License for more details.
*
* You should have received a copy of the GNU General Public License
* along with this program; if not, write to the Free Software
* Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
*/
import java.util.*;
public class Partition{
/* a test */
Test test;
/* a vector of ObjectSet */
Vector sets;
Partition(Test t, Vector oss) {
test=t;
sets=oss;
}
}
------------------------
/**
* Represents a polygon area for use in spacing/positioning calculations.
*/
class Polygon {
PolyLine lower_head, lower_tail;
PolyLine upper_head, upper_tail;
};
------------------------
/**
* Used to build Polygons.
*/
class PolyLine {
int dx, dy;
PolyLine link;
PolyLine(int dx, int dy, PolyLine link) {
this.dx = dx;
this.dy = dy;
this.link = link;
}
};
--------------------------
/*
* 1.1 version.
*/
import java.awt.*;
import java.awt.event.*;
import java.applet.Applet;
/*
* This displays a framed area. When the user clicks within
* the area, this program displays a dot and a string indicating
* the coordinates where the click occurred.
*/
public class RectangleDemo extends Applet {
RFramedArea framedArea;
Label label;
public void init() {
GridBagLayout gridBag = new GridBagLayout();
GridBagConstraints c = new GridBagConstraints();
setLayout(gridBag);
framedArea = new RFramedArea(this);
c.fill = GridBagConstraints.BOTH;
c.weighty = 1.0;
c.gridwidth = GridBagConstraints.REMAINDER; //end row
gridBag.setConstraints(framedArea, c);
add(framedArea);
label = new Label("Drag within the framed area.");
c.fill = GridBagConstraints.HORIZONTAL;
c.weightx = 1.0;
c.weighty = 0.0;
gridBag.setConstraints(label, c);
add(label);
}
public void updateLabel(Rectangle rect) {
label.setText("Rectangle goes from ("
+ rect.x + ", " + rect.y + ") to ("
+ (rect.x + rect.width - 1) + ", "
+ (rect.y + rect.height - 1) + ").");
}
}
/* This class exists solely to put a frame around the coordinate area. */
class RFramedArea extends Panel {
public RFramedArea(RectangleDemo controller) {
super();
//Set layout to one that makes its contents as big as possible.
setLayout(new GridLayout(1,0));
add(new SelectionArea(controller));
}
public Insets getInsets() {
return new Insets(4,4,5,5);
}
public void paint(Graphics g) {
Dimension d = getSize();
Color bg = getBackground();
g.setColor(bg);
g.draw3DRect(0, 0, d.width - 1, d.height - 1, true);
g.draw3DRect(3, 3, d.width - 7, d.height - 7, false);
}
}
class SelectionArea extends Canvas {
Rectangle currentRect = null;
RectangleDemo controller;
public SelectionArea(RectangleDemo controller) {
super();
this.controller = controller;
MyListener myListener = new MyListener();
addMouseListener(myListener);
addMouseMotionListener(myListener);
}
class MyListener extends MouseAdapter
implements MouseMotionListener {
public void mousePressed(MouseEvent e) {
int x = e.getX();
int y = e.getY();
currentRect = new Rectangle(x, y, 0, 0);
repaint();
}
public void mouseDragged(MouseEvent e) {
updateSize(e);
}
public void mouseMoved(MouseEvent e) {
}
public void mouseReleased(MouseEvent e) {
updateSize(e);
}
void updateSize(MouseEvent e) {
int x = e.getX();
int y = e.getY();
currentRect.setSize(x - currentRect.x,
y - currentRect.y);
repaint();
}
}
public void paint(Graphics g) {
//update has already cleared the previous rectangle,
//so we dn't need to here.
//If currentRect exists, paint a rectangle on top.
if (currentRect != null) {
Dimension d = getSize();
Rectangle box = getDrawableRect(currentRect, d);
controller.updateLabel(box);
//Draw the box outline.
g.drawRect(box.x, box.y,
box.width - 1, box.height - 1);
}
}
Rectangle getDrawableRect(Rectangle originalRect,
Dimension drawingArea) {
int x = originalRect.x;
int y = originalRect.y;
int width = originalRect.width;
int height = originalRect.height;
//Make sure rectangle width and height are positive.
if (width < 0) {
width = 0 - width;
x = x - width + 1;
if (x < 0) {
width += x;
x = 0;
}
}
if (height < 0) {
height = 0 - height;
y = y - height + 1;
if (y < 0) {
height += y;
y = 0;
}
}
//The rectangle shouldn't extend past the drawing area.
if ((x + width) > drawingArea.width) {
width = drawingArea.width - x;
}
if ((y + height) > drawingArea.height) {
height = drawingArea.height - y;
}
//If the width or height is 0, make it 1
//so that the box is visible.
if (width == 0) {
width = 1;
}
if (height == 0) {
height = 1;
}
return new Rectangle(x, y, width, height);
}
}
----------------------
/*
* SimpleNodeDrawer.java
* Copyright (C) 1999 Pierre Geurts
*
* This program is free software; you can redistribute it and/or modify
* it under the terms of the GNU General Public License as published by
* the Free Software Foundation; either version 2 of the License, or
* (at your option) any later version.
*
* This program is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
* GNU General Public License for more details.
*
* You should have received a copy of the GNU General Public License
* along with this program; if not, write to the Free Software
* Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
*/
import java.awt.*;
import java.util.*;
/**
* a abstract class to allow many representation for
* a node
*/
public class SimpleNodeDrawer extends NodeDrawer {
FontMetrics metrics_small,metrics_big,metrics_current;
Font smallfont, bigfont;
int SMALL_FIXED_FONT_HEIGHT=8;
int BIG_FIXED_FONT_HEIGHT=14;
int current_font_height;
int default_border=5;
Vector colours=new Vector();
Canvas cv;
SimpleNodeDrawer(Canvas c) {
cv=c;
bigfont=new Font("Helvetica", Font.PLAIN, BIG_FIXED_FONT_HEIGHT);
c.setFont(bigfont);
metrics_big=c.getFontMetrics(c.getFont());
smallfont=new Font("Helvetica", Font.PLAIN, SMALL_FIXED_FONT_HEIGHT);
c.setFont(smallfont);
metrics_small=c.getFontMetrics(c.getFont());
metrics_current=metrics_small;
current_font_height=SMALL_FIXED_FONT_HEIGHT;
colours.addElement(Color.black);
colours.addElement(Color.red);
colours.addElement(Color.green);
colours.addElement(Color.blue);
colours.addElement(Color.orange);
colours.addElement(Color.darkGray);
colours.addElement(Color.cyan);
colours.addElement(Color.gray);
colours.addElement(Color.magenta);
colours.addElement(Color.pink);
colours.addElement(Color.black);
colours.addElement(Color.yellow);
colours.addElement(Color.white);
colours.addElement(Color.red);
colours.addElement(Color.green);
colours.addElement(Color.blue);
colours.addElement(Color.orange);
colours.addElement(Color.darkGray);
colours.addElement(Color.cyan);
colours.addElement(Color.gray);
colours.addElement(Color.magenta);
colours.addElement(Color.pink);
colours.addElement(Color.black);
colours.addElement(Color.yellow);
colours.addElement(Color.white);
}
public void computeNodeSize(WNode t) {
t.width=2 * current_font_height;
t.height=metrics_current.stringWidth(t.label) + 10;
t.border=default_border;
if (t.sibling !=null) {
computeNodeSize(t.sibling);
}
if (t.child != null) {
computeNodeSize(t.child);
}
}
public void drawArc(Graphics g, int x1, int y1, int x2,
int y2, String arclabel) {
g.setColor(Color.black);
g.drawLine((int)(x1*zoom), (int)(y1*zoom), (int)(x2*zoom),(int)(y2*zoom));
g.drawString(arclabel,
(int)(((x1 + x2)*zoom - metrics_current.stringWidth(arclabel)) / 2),
(int)((y1 + y2)*zoom/2));
}
public void drawNode(Graphics g, WNode t) {
int tposx=(int)(t.pos.x*zoom);
int tposy=(int)(t.pos.y*zoom);
int tw=(int)(t.width*zoom);
int th=(int)(t.height*zoom);
// Draw highlights
g.setColor(Color.lightGray);
g.drawLine(tposy + 2, tposx + tw + 1, tposy + th,
tposx + tw + 1);
g.drawLine(tposy + th + 1, tposx + tw + 1,
tposy + th + 1, tposx + 2);
// we draw the box corresponding to this node
if (t.colour>=colours.size())
g.setColor(Color.black);
else
g.setColor((Color)colours.elementAt(t.colour));
g.drawRect(tposy, tposx, th, tw);
// we draw the node label
g.drawString(t.label,
tposy + (th - metrics_current.stringWidth(t.label)) / 2,
tposx + tw - (tw - current_font_height) / 2);
if (t.selected) {
int border=(int)(3*zoom);
g.setColor(Color.pink);
g.drawRect(tposy-border, tposx-border, th+2*border, tw+2*border);
}
}
// increase the zoom
public void increaseZoom() {
if (zoom==0.5)
zoom=0.7;
else if (zoom==0.7)
zoom=1.0;
else if (zoom==1.0)
zoom=1.2;
else if (zoom==1.2) {
zoom=1.5;
metrics_current=metrics_big;
current_font_height=BIG_FIXED_FONT_HEIGHT;
cv.setFont(bigfont);
} else if (zoom==1.5)
zoom=2.0;
else if (zoom==2.0)
zoom=2.5;
else if (zoom==2.5)
zoom=3.0;
}
// decrease the zoom
public void decreaseZoom() {
if (zoom==3.0)
zoom=2.5;
else if (zoom==2.5)
zoom=2.0;
else if (zoom==2.0)
zoom=1.5;
else if (zoom==1.5) {
zoom=1.2;
metrics_current=metrics_small;
current_font_height=SMALL_FIXED_FONT_HEIGHT;
cv.setFont(smallfont);
} else if (zoom==1.2)
zoom=1.0;
else if (zoom==1.0)
zoom=0.7;
else if (zoom==0.7)
zoom=0.5;
}
}
-----------------------
/*
* SymbAtt.java
* Copyright (C) 1999 Pierre Geurts
*
* This program is free software; you can redistribute it and/or modify
* it under the terms of the GNU General Public License as published by
* the Free Software Foundation; either version 2 of the License, or
* (at your option) any later version.
*
* This program is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
* GNU General Public License for more details.
*
* You should have received a copy of the GNU General Public License
* along with this program; if not, write to the Free Software
* Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
*/
/* recherche de la meilleure partition binaire de l'ensemble des valeurs de
l'attribut */
import java.util.*;
import java.io.*;
public class SymbAtt extends Attribute{
Vector values=new Vector();
/* la valeur de l'attribut symbolique qui donne le meilleur score */
Vector bestsubset;
SymbAtt(String s, Database dab) {
name=s;
db=dab;
index=db.addAttToDb(this);
}
public void SetAttValue(Obj o,Object s) {
int i;
for (i=0; i
break;
if (i
else {
o.attributesvalues.setElementAt(s,index);
values.addElement(s);
}
}
public int ReadAttValue(Obj o, StreamTokenizer stt) {
if (stt.ttype==stt.TT_WORD) {
SetAttValue(o,stt.sval);
return 0;
} else if (stt.ttype==stt.TT_NUMBER) {
// we transform number to a string
SetAttValue(o,"" + stt.nval);
return 0;
} else {
System.out.println("A symbolic value was expected");
return 1;
}
}
public String describe() {
return toString()+ " - symbolic - values : " + values.toString();
}
public String describeBestTest() {
return toString() + " - values : " + bestsubset.toString() + " - Information gain : " + lastbestscore;
}
public double bestscore(ObjectSet os, SymbAtt goal) {
/* attention cette partie est tres tres mal ecrite */
double result;
double tmpresult;
double currentbestscore=-1;
int currentbestvalue=0;
int pbv;
int i,j,x,y;
/* liste des index*/
Vector remainingvalues=new Vector();
for (i=0; i
}
/* les valeurs dans l'ordre dans lequel elles sont selectionnees */
Vector ordervalues=new Vector();
/* les valeurs de score */
Vector scores=new Vector();
int gvs=goal.values.size();
int sum=os.size;
/* pour chaque valeur de l'attribut, on conserve la matrice des frequences */
int tabfreq[][][]=new int[values.size()][2][gvs+1];
/* calcul des matrices de frequences */
for (j=0; j
for (i=0; i
y=goal.values.indexOf(goal.Value((Obj)os.elementAt(i)));
if (x==j) { /* la valeur est la valeur testee */
tabfreq[j][0][y]++;
tabfreq[j][0][gvs]++;
} else {
tabfreq[j][1][y]++;
tabfreq[j][1][gvs]++;
}
}
/* calcul de l'entropie */
result=os.entropy;
result-=tabfreq[j][0][gvs]*Entropy.entropy(tabfreq[j][0], gvs,tabfreq[j][0][gvs])/sum;
result-=tabfreq[j][1][gvs]*Entropy.entropy(tabfreq[j][1], gvs,tabfreq[j][1][gvs])/sum;
if (result>currentbestscore) {
currentbestscore=result;
currentbestvalue=j;
}
}
/* on va maintenant regrouper les attributs de maniere recursive */
int currenttabfreq[][]=new int[2][gvs+1];
for (i=0;i
currenttabfreq[1][i]=tabfreq[currentbestvalue][0][i]
+ tabfreq[currentbestvalue][1][i];
}
// printtab(currenttabfreq,gvs+1);
/* on ajoute cet element dans la liste */
Integer cbv=new Integer(currentbestvalue);
ordervalues.addElement(cbv);
scores.addElement(new Double(currentbestscore));
i=0;
while (i
i++;
remainingvalues.removeElementAt(i);
while (remainingvalues.size()!=1) {
/* copier le tableau courant dans la valeur correspondant
a l'element precedent */
for (i=0;i
currenttabfreq[1][i]-=tabfreq[currentbestvalue][0][i];
}
// printtab(currenttabfreq,gvs+1);
/* on va utiliser la matrice correspondant a la precedente
valeur comme moyen de stockage temporaire
*/
pbv=currentbestvalue;
/* recherche de la meilleure valeur a ajouter au sous-ensemble */
currentbestscore=-1;
for (j=0; j
for (i=0; i
tabfreq[pbv][1][i]=currenttabfreq[1][i]-tabfreq[cv][0][i];
}
result=os.entropy;
result-=tabfreq[pbv][0][gvs]*
Entropy.entropy(tabfreq[pbv][0], gvs, tabfreq[pbv][0][gvs])/sum;
result-=tabfreq[pbv][1][gvs]*
Entropy.entropy(tabfreq[pbv][1], gvs, tabfreq[pbv][1][gvs])/sum;
if (result>currentbestscore) {
currentbestscore=result;
currentbestvalue=cv;
}
}
cbv=new Integer(currentbestvalue);
ordervalues.addElement(cbv);
scores.addElement(new Double(currentbestscore));
i=0;
while (i
i++;
remainingvalues.removeElementAt(i);
}
/* recherche du meilleur score */
currentbestscore=((Double)scores.elementAt(0)).doubleValue();
currentbestvalue=0;
for (i=1; i
if (sc>currentbestscore) {
currentbestscore=sc;
currentbestvalue=i;
}
}
/* on garde uniquement les elements de l'ensemble */
ordervalues.setSize(currentbestvalue+1);
bestsubset=new Vector();
for (i=0; i
// System.out.println(name + " " + values.toString() + " " + bestsubset.toString());
lastbestscore=currentbestscore;
return currentbestscore;
}
public Partition bestpartition(ObjectSet os, SymbAtt goal) {
TestSymb t=new TestSymb(this, bestsubset);
Vector v=os.splitOn(t);
return new Partition(t,v);
}
/*
public static void printtab(int[][] tab,int size) {
System.out.print("[[");
for (int i=0; i
}
System.out.println("]");
System.out.print("[");
for (int i=0; i
}
System.out.println("]]");
}
*/
}
-------------------
/*
* Test.java
* Copyright (C) 1999 Pierre Geurts
*
* This program is free software; you can redistribute it and/or modify
* it under the terms of the GNU General Public License as published by
* the Free Software Foundation; either version 2 of the License, or
* (at your option) any later version.
*
* This program is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
* GNU General Public License for more details.
*
* You should have received a copy of the GNU General Public License
* along with this program; if not, write to the Free Software
* Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
*/
import java.util.*;
/* a test should also be an extension of a Symbolic Attribute
* so that we could use it later
*/
abstract class Test {
/* a description of the test */
String TestDescription;
/* the attribute */
Attribute Att;
/* the number of issues of this test */
int nbIssues;
/* the vector of the values corresponding to each issues */
Vector valuesIssues;
/* TestObject gives the value associated to this object */
abstract String TestObject(Obj o);
/* return a description of the nth value of this test */
abstract String testDescription(int value);
/* TestIndex gives the index of this values in valuesissues */
public int TestIndex(Obj o) {
return valuesIssues.indexOf(TestObject(o));
}
}
----------------------------
/*
* Test.java
* Copyright (C) 1999 Pierre Geurts
*
* This program is free software; you can redistribute it and/or modify
* it under the terms of the GNU General Public License as published by
* the Free Software Foundation; either version 2 of the License, or
* (at your option) any later version.
*
* This program is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
* GNU General Public License for more details.
*
* You should have received a copy of the GNU General Public License
* along with this program; if not, write to the Free Software
* Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
*/
import java.util.*;
/* a test should also be an extension of a Symbolic Attribute
* so that we could use it later
*/
abstract class Test {
/* a description of the test */
String TestDescription;
/* the attribute */
Attribute Att;
/* the number of issues of this test */
int nbIssues;
/* the vector of the values corresponding to each issues */
Vector valuesIssues;
/* TestObject gives the value associated to this object */
abstract String TestObject(Obj o);
/* return a description of the nth value of this test */
abstract String testDescription(int value);
/* TestIndex gives the index of this values in valuesissues */
public int TestIndex(Obj o) {
return valuesIssues.indexOf(TestObject(o));
}
}
----------------------
/*
* Test.java
* Copyright (C) 1999 Pierre Geurts
*
* This program is free software; you can redistribute it and/or modify
* it under the terms of the GNU General Public License as published by
* the Free Software Foundation; either version 2 of the License, or
* (at your option) any later version.
*
* This program is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
* GNU General Public License for more details.
*
* You should have received a copy of the GNU General Public License
* along with this program; if not, write to the Free Software
* Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
*/
import java.util.*;
/* a test should also be an extension of a Symbolic Attribute
* so that we could use it later
*/
abstract class Test {
/* a description of the test */
String TestDescription;
/* the attribute */
Attribute Att;
/* the number of issues of this test */
int nbIssues;
/* the vector of the values corresponding to each issues */
Vector valuesIssues;
/* TestObject gives the value associated to this object */
abstract String TestObject(Obj o);
/* return a description of the nth value of this test */
abstract String testDescription(int value);
/* TestIndex gives the index of this values in valuesissues */
public int TestIndex(Obj o) {
return valuesIssues.indexOf(TestObject(o));
}
}
--------------------
import java.awt.*;
/**
* "There flowered a White Tree, and that was for Gondor; but Seven Stars
* were about it, and a high crown above it, the signs of Elendil that no
* lord had borne for years beyond count. And the stars flamed in the
* sunlight, for they were wrought of gems by Arwen daughter of Elrond;
* and the crown was bright in the morning, for it was wrought of mithril
* and gold." - J. R. R. Tolkien, _The Return of the King_
*
* Basic canvas for creating and displaying a WalTree.
*/
public class WalTreeCanvas extends Canvas {
int default_border;
WTFactory wt_factory; // contain functions to draw a tree
NodeDrawer nd; // contain functions to draw a node
WNode t;
boolean dirty; // tell us if the node positions should be computed again
int root_x;
/**
* Constructs new WalTreeCanvas, an associated WTFactory, and inits state.
*/
public WalTreeCanvas() {
super();
wt_factory = new WTFactory();
t = null;
default_border = 5;
root_x = 8;
dirty = false;
}
public Dimension getPreferredSize() {
return new Dimension(2000, 2000);
}
public Dimension getMiminimumSize() {
return new Dimension(40, 40);
}
/**
* Set the tree to be displayed by this canvas.
*/
public void setTree(WNode t) {
this.t = t;
dirty = true;
}
/**
* Set the default border size for nodes
*/
public void setDefaultBorder(int b) {
default_border = b;
}
/**
* Set the distance between parent nodes.
*/
public void setParentDistance(int val) {
wt_factory.setParentDistance(val);
}
/**
* Set the horizontal offset between edge of canvas and root node.
*/
public void setRootOffset(int val) {
root_x = val;
}
/**
* Draw the tree associated with this canvas.
*/
public void paint(Graphics g) {
super.paint(g);
Dimension d = getSize();
/* Wipe background */
g.setColor(Color.white);
g.fillRect(0, 0, d.width, d.height);
if(t == null) {
return;
}
if(dirty == true) {
/* Calculate node offsets */
wt_factory.layout(t);
/* Calculate absolute node positions */
wt_factory.plantTree(t, root_x, root_x-wt_factory.computeMaxOffset(t,0));
dirty = false;
}
/* Paint the beastie */
wt_factory.paintFullTree(g, t, nd);
}
};
------------------------
import java.awt.Point;
/**
* Represents a node (or tree) in the WalTree.
*/
public class WNode {
String label; // the label of the node (test)
String arclabel; // the label of the arc leading to this node
WNode parent, child, sibling;
int width, height, border; // the width, height and border of this node
Point pos, offset;
Polygon contour;
int colour=0; // a colour number
DtNode dtnode; // the associated DtNode
boolean selected=false; // tell us if this node is the current node
public WNode(String l, String a, WNode p, WNode c, WNode s, int w, int h, int b, DtNode dtn) {
label = l;
arclabel=a;
parent = p;
child = c;
sibling = s;
width = w;
height = h;
border = b;
pos = new Point(0, 0);
offset = new Point(0, 0);
contour = new Polygon();
dtnode=dtn;
}
public boolean containsPoint(int x, int y) {
return (((y>=pos.x) && (y<=pos.x+width)) && ((x>=pos.y) && (x<=pos.y+height)));
}
public DtNode getPointedNode(int x,int y) {
if (containsPoint(x,y))
return dtnode;
if (child!=null && y>pos.x) {
// not worth going further down if y
if (dtchild!=null)
return dtchild;
}
if (sibling!=null)
return sibling.getPointedNode(x,y);
return null;
}
}
-------------------------
/**
* A direct port from Sven Moen's "Drawing Dynamic Trees" article in
* IEEE Software, July 1990. Thanks to Allan Brighton for commenting the
* Brighton Tree Widget source code with the aforementioned reference.
*
* mai 1999 : modified by Pierre Geurts to display decision trees
*
*/
import java.awt.*;
import java.util.*;
/**
* Encapsulates all operations performed on a WalTree.
*/
public class WTFactory {
int parent_dist = 30;
/**
* Allows setting of the distance between levels in the tree.
*/
public void setParentDistance(int val) {
parent_dist = val;
}
/**
* Lays out the tree node spacing in typical tidy fashion.
*/
void layout(WNode t) {
WNode c;
if(t == null) {
return;
}
c = t.child;
while(c != null) {
layout(c);
c = c.sibling;
}
if(t.child != null) {
attachParent(t, join(t));
} else {
layoutLeaf(t);
}
}
/**
* Attaches the specified node to its children, setting offsets.
*/
void attachParent(WNode t, int h) {
int x, y1, y2;
x = t.border + parent_dist;
y2 = (h - t.height) / 2 - t.border;
y1 = y2 + t.height + 2 * t.border - h;
t.child.offset.x = x + t.width;
t.child.offset.y = y1;
t.contour.upper_head = new PolyLine(t.width, 0, new PolyLine(x, y1,
t.contour.upper_head));
t.contour.lower_head = new PolyLine(t.width, 0, new PolyLine(x, y2,
t.contour.lower_head));
}
/**
* Arranges contour for leaf node appropriately.
*/
void layoutLeaf(WNode t) {
t.contour.upper_tail = new PolyLine(t.width + 2 * t.border, 0, null);
t.contour.upper_head = t.contour.upper_tail;
t.contour.lower_tail = new PolyLine(0, -t.height - 2 * t.border, null);
t.contour.lower_head = new PolyLine(t.width + 2 * t.border, 0,
t.contour.lower_tail);
}
/**
* Joins children/siblings together, merging contours.
*/
int join(WNode t) {
WNode c;
int d, h, sum;
c = t.child;
t.contour = c.contour;
sum = h = c.height + 2 * c.border;
c = c.sibling;
while(c != null) {
d = merge(t.contour, c.contour);
c.offset.y = d + h;
c.offset.x = 0;
h = c.height + 2 * c.border;
sum += d + h;
c = c.sibling;
}
return sum;
}
/**
* Merges two polygons together. Returns total height of final polygon.
*/
int merge(Polygon c1, Polygon c2) {
int x, y, total, d;
PolyLine lower, upper, b;
x = y = total = 0;
upper = c1.lower_head;
lower = c2.upper_head;
while(lower != null && upper != null) { /* compute offset total */
d = offset(x, y, lower.dx, lower.dy, upper.dx, upper.dy);
y += d;
total += d;
if(x + lower.dx <= upper.dx) {
y += lower.dy;
x += lower.dx;
lower = lower.link;
} else {
y -= upper.dy;
x -= upper.dx;
upper = upper.link;
}
}
/* store result in c1 */
if(lower != null) {
b = bridge(c1.upper_tail, 0, 0, lower, x, y);
c1.upper_tail = (b.link != null) ? c2.upper_tail : b;
c1.lower_tail = c2.lower_tail;
} else { /* (upper) */
b = bridge(c2.lower_tail, x, y, upper, 0, 0);
if(b.link == null) {
c1.lower_tail = b;
}
}
c1.lower_head = c2.lower_head;
return total;
}
/**
* Calculates the offset for specified points.
*/
int offset(int p1, int p2, int a1, int a2, int b1, int b2) {
int d, s, t;
if(b1 <= p1 || p1 + a1 <= 0) {
return 0;
}
t = b1 * a2 - a1 * b2;
if(t > 0) {
if(p1 < 0) {
s = p1 * a2;
d = s / a1 - p2;
} else if(p1 > 0) {
s = p1 * b2;
d = s / b1 - p2;
} else {
d = -p2;
}
} else if(b1 < p1 + a1) {
s = (b1 - p1) * a2;
d = b2 - (p2 + s / a1);
} else if(b1 > p1 + a1) {
s = (a1 + p1) * b2;
d = s / b1 - (p2 + a2);
} else {
d = b2 - (p2 + a2);
}
if(d > 0) {
return d;
} else {
return 0;
}
}
/**
* bridge
*/
PolyLine bridge(PolyLine line1, int x1, int y1, PolyLine line2, int x2,
int y2) {
int dy, dx, s;
PolyLine r;
dx = x2 + line2.dx - x1;
if(line2.dx == 0) {
dy = line2.dy;
} else {
s = dx * line2.dy;
dy = s / line2.dx;
}
r = new PolyLine(dx, dy, line2.link);
line1.link = new PolyLine(0, y2 + line2.dy - dy - y1, r);
return r;
}
void plantTree(WNode t, int off_x, int off_y) {
WNode c, s;
int cur_y;
t.pos.x = off_x + t.offset.x;
t.pos.y = off_y + t.offset.y;
/* Plant child node */
c = t.child;
if(c != null) {
plantTree(c, t.pos.x, t.pos.y);
/* Plant sibling nodes */
s = c.sibling;
cur_y = t.pos.y + c.offset.y;
while(s != null) {
plantTree(s, t.pos.x + c.offset.x, cur_y);
cur_y += s.offset.y;
s = s.sibling;
}
}
}
/**
* PG 05/1999 : compute the maximum y offset to the right (or bottom)
* of the tree (to put the tree at the most left part (we go down
* along the first branch).
*/
int computeMaxOffset(WNode t, int y) {
WNode c, s;
int cur_y;
int current_pos_y;
current_pos_y = y + t.offset.y;
c = t.child;
if(c != null) {
int min=computeMaxOffset(c, current_pos_y), newmin=min;
/* Plant sibling nodes */
s = c.sibling;
cur_y = current_pos_y + c.offset.y;
while(s != null) {
newmin=computeMaxOffset(s, cur_y);
if (newmin
cur_y += s.offset.y;
s = s.sibling;
}
return min;
} else
return current_pos_y;
}
void paintFullTree(Graphics g, WNode t, NodeDrawer nd) {
if(t == null) {
System.out.println("paintFullTree::null tree.");
return;
}
g.setColor(Color.black);
paintTree(g, t, nd);
}
void paintTree(Graphics g, WNode t, NodeDrawer nd) {
nd.drawNode(g,t);
if(t.parent != null) {
int x1 = t.pos.y + t.height / 2;
int y1 = t.pos.x;
int x2 = t.parent.pos.y + t.parent.height / 2;
int y2 = t.parent.pos.x + t.parent.width;
nd.drawArc(g,x1,y1,x2,y2,t.arclabel);
}
/* Draw siblings, using the main child's x-offset. */
if(t.sibling != null) {
paintTree(g, t.sibling, nd);
}
/* Draw children */
if(t.child != null) {
paintTree(g, t.child, nd);
}
}
}
-------------
