THE LUCS-KDD IMPLEMENTATIONS OF THE CMAR ALGORITHM (VERSION 2)

CMAR (Classification based on Multiple Association Rules) is a Classification Association Rule Mining (CARM) algorithm developed by Wenmin Li, Jiawei Han and Jian Pei (Li et al. 2001). CMAR operates using a two stage approach to generating a classifier:

1. Generating the complete set of CARs according to a user supplied:
   1. Support threshold to determine frequent (large) item sets, and
   2. Confidence threshold to confirm CRs.
2. Prune this set to produce a classifier.

The two stage approach is a fairly common approach used by many CARM algorithms, for example the CBA (Classification Based on Associations) algorithm (Liu et al 1998).

1.1. Overview of CMAR

The CMAR algorithm (as described in Li et al 2001) uses an FP-growth algorithm (Han et al. 2000) to produce a set of CARs which are stored in data structure referred to as a CR tree. CARs are inserted into the CR tree if:

1. The Chi-Squared value is above a user specified critical threshold (Li et al. suggest a 5% significance level; assuming a degree of freedom equivalent to 1, this will equate to a threshold of 3.8415), and
2. The CR tree does not contain a more general rule with a higher priority.

Given two CARs, R1 and R2, R1 is said to be a more general rule than R2 if the antecedent for R1 is a subset of the antecedent for R2. In CMAR CARS are prioritised using the following ordering:

1. Confidence: A rule r1 has priority over a rule r2 if confidence(r1) > confidence(r2).
2. Support: A rule r1 has priority over a rule r2 if confidence(r1)==confidence(r2) && support(r1)>support(r2).
3. Size of antecedent: A rule r1 has priority over a rule r2 if confidence(r1)==confidence(r2) && support(r1)==support(r2) && |A_r1|<|A_r2|.

(A similar ordering to that used in CBA).

T set of training records
C array of length |T| with value of elements set to 0
R The prioritised rule list
R' empty rule list
For each r in R
    if (T=null) break;
    coverFlag <-- false
    for each ti in T Loop (1 <= i <= [T|)
    	if (r.antecedent subset ti) rule satisfies record
    	    C[i] <-- C[i]+1
    	    coverFlag <-- true
    End loop
    if (coverFlag=true) rule satisfies at least one record
        R' <-- R' union r
    Loop from i<--1 to i<--|c| in steps of 1
        if ci> MIN_COVER remove ti from T
   End loop

R' is then the resulting classifier. In their experiments Li et al. used a MIN_COVER value of 3, i.e. each record had to be satisfied (covered) by at least three rules before it is no longer to be considered in the generation process and removed from the training set.

To test the resulting classifier Li et al. propose the following process. Given a record r in the test set:

1. Collect all rules that satisfy r, and
   1. If consequents of all rules are all identical, or only one rule, classify record according to the consequents.
   2. Else group rules according to classifier and determine the combined effect of the rules in each group, the classifier associated with the "strongest group" is then selected.

The strength of a group is calculate using a Weighted Chi Squared (WCS) measure. This is done by first defining a Maximum Chi Squared (MCS) value for each rule A->c:

MCS = (min(sup(A),sup(c)) - sup(A)sup(c)/N)^2 * N * e

Where:

1. sup(P) = support for antecedent.
2. sup(c) = support for consequent.
3. N = Number of records in test set.
4. e is calculated as follows:

e = 1/sup(A)sup(c) + 1/sup(A)N-sup(c) + 1/N-sup(A)sup(c) +
	1/(N-sup(A))(N-sup(c))

For each group of rules the Weighted Chi Squared value is defined as:

WCS = The sum of (Chi-Squared * Chi-Squared)/(MCS)

1.2. Overview of LUCS-KDD implementation of CMAR

The LUCS KDD CMAR software comprises nine source files. These are provided from this WWW page together with three application classes. The source files are as follows:

2.1. Compiling

The LUCS-KDD CMAR 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 hierarchy of WWW pages contained in the Document directory.

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

java APPLICATION_CLASS_FILE_NAME -F FILE_NAME -N NUMBER_OF_CLASSES

For example:

java ClassCMAR_App -FpimaIndians.D42.N768.C2.num -N2

The -F flag is used to input the name of the data file to be used, and the -N flag to input the number of classes represented within the input data.

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

java -Xms600m -Xmx600m APPLICATION_CLASS_FILE_NAME -F FILE_NAME
				-N NUMBER_OF_CLASSES

For example:

java -Xms600m -Xmx600m ClassCMAR_App10 -FpimaIndians.D42.N768.C2.num -N2

In the case of ClassCMARfull_App10 the output can be extensive so it is a good idea the direct the output to a file. For example:

java ClassCMAR_App10 -FpimaIndians.D42.N768.C2.num -N2 > myFile

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

T  = {t | t = subset A}

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

D = |A|

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, 6, 7} of which 6 and 7 represent the possible classes (the class attributes). Note that attribute numbers are ordered sequentially commencing with the number 1 (the value 0 has a special meaning). This includes the class attributes which should follow on from the last attribute number as in the above example. It is not a good idea to assign some very high value to the class attributes that guarantees that they are numerically after the last attribute number as this introduces inefficiencies into the code. For example, if in the above case, the class numbers are 1001 and 1002 (instead of 6 and 7 respectively) the algorithm will assume that there are 1002 attributes in total in which case there will be 2^1002 - 1 candidate frequent item sets (instead of only 2^7 - 1 candidate sets).

The program assumes support and confidence default threshold values of 20% and 80% respectively. However the user may enter their own thresholds using the -S and -C flags. Thresholds are expressed as percentages.

By default the program reorders the input according to frequency (this makes the software much more efficient), however this can be stopped by commenting out the lines:

newClassification.idInputDataOrdering();  // ClassificationAprioriT
newClassification.recastInputData();      // AssocRuleMining

The LUCS-KDD implementation of the CMAR algorithm described here has been used successfully by the LUCS-KDD research group to contrast and compare a variety of classification algorithms and techniques. The software is available for free, however the author would appreciate appropriate acknowledgment. The following reference format for referring to the LUCS-KDD implementation of CMAR, available from this WWW page, is suggested:

1. Coenen, F. (2004). LUCS KDD implementation of CMAR (Classification based on Multiple Association Rules). http://www.csc.liv.ac.uk/~frans/KDD/Software/CMAR/cmar.html, 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. 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.
2. Coenen, F., Goulbourne, G. and Leng, P. (2001). Computing Association Rules Using Partial Totals. In de Raedt, L. and Siebes, A. (Eds), Principles of Data Mining and Knowledge Discovery, Proc PKDD 2001, Spring Verlag LNAI 2168, pp 54-66.
3. Coenen and Leng (2004). Data Structures for Association Rule Mining: T-trees and P-trees To appear in IEEE Transaction in Knowledge and Data Engineering.
4. Coenen, F., Leng, P., Goulbourne, G. (2004). Tree Structures for Mining Association Rules. Journal of Data Mining and Knowledge Discovery, Vol 15 (7), pp391-398.
5. Han, J., Pei, J. and Yiwen, Y. (2000). Mining Frequent Patterns Without Candidate Generation. Proceedings ACM-SIGMOD International Conference on Management of Data, ACM Press, pp1-12.
6. Liu, B. Hsu, W. and Ma, Y (1998). Integrating Classification and Association Rule Mining. Proceedings KDD-98, New York, 27-31 August. AAAI. pp80-86.
7. Li W., Han, J. and Pei, J. (2001). CMAR: Accurate and Efficient Classification Based on Multiple Class-Association Rules. Proc ICDM 2001, pp369-376.