THE LUCS-KDD IMPLEMENTATIONS OF THE FOIL, PRM AND CPAR ALGORITHMS

FOIL (First Order Inductive Learner) is an inductive learning algorithm for generating Classification Association Rules (CARs) developed by Ross Quinlan and Mike Cameron-Jones (Quinlan and Cameron-Jones 1993). This algorithum was later further developed by Xiaoxin Yin and Jiawei Han to produce the PRM (Predictive Rule Mining) CAR generation algorithm (Yin and Han 2003). PRM was then further developped, by Xiaoxin Yin and Jiawei Han, to produce CPAR (Classification based on Predictive Association Rules).

There are six source files and a six application files available here. The source files are as follows:

2.1. Compiling

The software has been implemented in Java using the Java2 SDK (Software Development Kit) Version 1.4.0, which should therefore make it highly portable. The code does not require any special packages and thus can be compiled using the standard Java compiler:

javac *.java

2.2. Documentation

The code can be documented using Java Doc. First create a directory Documentation in which to place the resulting HTML pages and then type:

javadoc -d Documentation/ *.java

This will produce a hierrachy of WWW pages contained in the Document directory.

When compiled the software can be invoked in the normal manner using the Java interpreter:

java FILE_NAME

If you are planning to process a very large data set it is a good idea to grab some extra memory. For example:

java -Xms600m -Xmx600m FILE_NAME

The input to the software, in all cases is a (space separated) binary valued data set R. The set R comprises a set of N records such that each record (R) comprises a set of attributes and a class. Thus:

R  = {r | r = {{subset A} + one member of C}}

Where A is the set of available attributes, and C is the set of available classes. The value D is then defined as:

D = |A| + |C|

We then say that a particular data set has D columns and N rows. A small example data sets might be as follows:

1 2 3 6
1 4 5 7
1 3 4 6
1 2 6
1 2 3 4 5 7

where, in this case, A = {1, 2, 3, 4, 5}, C = {6, 7}, D = 7 and N = 5. Note that attribute numbers are ordered sequentially commencing with the number 1 (the value 0 has a special meaning). Note also that the class is always the last item listed in each record. The input file is included using a -F flag.

The programs also require information regrding the number of classes. This is input using a -N flag.

FOIL, PRM and CPAR Applications classes all have the following basic form:

public class < CLASS_NAME >  {

    /** Main method */

    public static void main(String[] args) throws IOException {

	// Create instance of class CPAR_CARgen, PRM_CARgen or FOIL_CARgen	
	// as desired, using the appropriate constructor.
	< OBJECT > < INSTANCE_NAME > = new < CONSTRUCTOR > ;	
			
	// Read data to be mined from file using the inputDataSet() method
	// found in the AssocRuleMining parent class which is inheritted by
	// the CPAR_CARgen, PRM_CARgen and FOIL_CARgen classes.
	< INSTANCE_NAME > .inputDataSet();
	
	// Create training and test data sets. Two options: (1) if requiring
	// a 50:50 training/test data split use the
	// createTrainingAndTestDataSets() method , (2) if requiring Ten
	// Cross Validation (TCV) use the createTenthsDataSets() method. Both
	// are contained in the Classification class (and are inheritted by
	// the CPAR_CARgen, PRM_CARgen and FOIL_CARgen classes).
	< INSTANCE_NAME > .createTrainingAndTestDataSets();
	//  or
	< INSTANCE_NAME > .newClassification.createTenthsDataSets();
	
	// Mine data and generate CARs using a call to either: (1) the
	// startClassification() if not requiring TCV, (2) commenceTCV()
	// if requiring TCV, or (3) commenceTCVwithOutput() if (for dignostic
	// or monitoring purposes) output is required during the TCV process.
	// Each of these methods returns an accuracy value which van be
	// "captured" and output
	< INSTANCE_NAME > .startClassification();
	< INSTANCE_NAME > .commenceTCV();
	//  or
	< INSTANCE_NAME > .commenceTCVwithOutput();
	
	// Output as deired using the many output methods that are available
	// (see below for further details)
	
	// End
	System.exit(0);
	}

Some output is always generated such as: (1) the input parameters and start settings and (2) "mile stones" during processing. Additional output statements can be included in application classes. The availanle additional output options are as follows:

1. outputDataArray(): Outputs the input data.
2. outputDataArraySize(): Outputs the size of the input data (number of records and columns, number of elements and overall density).
3. outputDuration(double time1, double time2): The elapswed time, in seconds between time1 and time2. Typically used to measure processing time:

   double time1 = (double) System.currentTimeMillis();
   
   // Program statements
   
   < INSTANCE_NAME > .outputDuration(time1,
   				(double) System.currentTimeMillis());
   

4. outputNumRules(): The number of rules in the resulting classifier
5. outputRules(): The classifier expressed as a set of rules each with its expected Laplace accuracy value.

Note that the first three of the above output methods are instance methods contained in the AssocRuleMining class which are therefore inheritted by the CPAR_CARgen, PRM_CARgen and FOIL_CARgen classes. The last two of the above are instance methods of the RuleList class and thus must be called using an instance of that class. An instance of the RuleList class is created during processing and may be accessed using the getCurrentRuleListObject() public method found in the Classification class. Thus, for example, the outputRules() method would be invoked as follows:

< INSTANCE_NAME > .getCurrentRuleListObject().outputRules();

When using TCV it makes little sence to use the outputNumRules() and outputRules() methods as this will only serve to output the last 10th of the TCV process. If output is required then the commenceTCVwithOutput() method should be used.

More information on the:

The LUCS-KDD implementations of FOIL, PRM and CPAR described here have been use successfully by the LUCS-KDD reseach group to contrast and compare various CARM algorithms and techniques. The software is available for free, however the author would appreciate appropriate acknowledgement. The following reference format for referring to the FOIL, PRm and CPAR implementations aresuggested:

1. Coenen, F. (2004), LUCS-KDD implementations of FOIL (First Order Inductive Learner), http://www.cxc.liv.ac.uk/~frans/KDD/Software/FOIL_PRM_CPAR/foil.html, Department of Computer Science, The University of Liverpool, UK.
2. Coenen, F. (2004), LUCS-KDD implementations of PRM (Predictive Rule Mining), http://www.cxc.liv.ac.uk/~frans/KDD/Software/FOIL_PRM_CPAR/prm.html, Department of Computer Science, The University of Liverpool, UK.
3. Coenen, F. (2004), LUCS-KDD implementations of CPR (Classification based on Predictive Association Rules), http://www.cxc.liv.ac.uk/~frans/KDD/Software/FOIL_PRM_CPAR/cpar.html, Department of Computer Science, The University of Liverpool, UK.

Should you wish to refer to this WWW page the following reference format is suggested.

Coenen, F. (2004), LUCS-KDD implementations of the FOIL, PTM and CPAR algorithms, http://www.cxc.liv.ac.uk/~frans/KDD/Software/FOIL_PRM_CPAR/, Department of Computer Science, The University of Liverpool, UK.

Should you discover any "bugs" or other problems within the software (or this documentation), do not hesitate to contact the author.

1. Bing, L., Hse, W and Ma, Y. (1998). Integrating Classification and association Rule Mining. Proc. KDD-98.
2. Blake, C.L. and Merz, C.J. (1998). UCI Repository of machine learning databases http://www.ics.uci.edu/~mlearn/MLRepository.html, Irvine, CA: University of California, Department of Information and Computer Science.
3. Li W., Han, J. and Pei, J. (2001). CMAR: Accurate and Efficient Classification Based on Multiple Class-Association Rules. Proc ICDM 2001, pp369-376.
4. Quinlan, J. R. and Cameron-Jones, R. M. (1993). FOIL: A Midterm Report. Proc. ECML, Vienna, Austria, pp3-20.
5. Yin, X. and Han, J. (2003). CPAR: Classification based on Predictive Association Rules. Proc. SIAM Int. Conf. on Data Mining (SDM'03), San Fransisco, CA, pp. 331-335.