THE LUCS-KDD IMPLEMENTATIONS OF THE CBA ALGORITHM

1. INTRODUCTION

2. DOWNLOADING THE SOFTWARE

3. RUNNING THE SOFTWARE

4. THE CBA ALGORITHM IN MORE DETAIL

Given the data set:

a b e
a e
b e
c d f
c f
d f
b c e
a d f

where e and f are class attributes. This would give a distribution array of [4,4] (the first element representing the class e and the second the class f). Using this dataset the following ordered rule list (with confidence and support values given in parenthesise) may be generated:

b -> e (100%, 3)
d -> f (100%, 3)
b c -> e (100%, 1)
a d -> f (100%, 1)
a -> e (67%, 2)
c -> f (67%, 2)
c -> e (33%, 1)
a -> f (33%, 1)

Note that the list (R) is ordered according to the above schema.

The rule list is then processes to identify the DefaultClass and Terr value for each rule. This processing is illustrated in the following table (processing is stopped after rule 4 because there are no more records to consider):

The first rule with the lowest total error rate (Terr) is b c -> e so the final classifier becomes:

b -> e
d -> f
b c -> e
default f

In this sub-section the CBA algorithm will be considered in further detail. It is difficult to contrive a simple example (such as that presented in Sub-section 4.1) that serves to demonstrate all the features of CBA so the example given here uses a discretized/ normalised version of Pima Indians set (also available from this site, the raw data can be obtained from the UCI Machine learning Repository (Blake and Merz 1998)). The data was discretized/ normalised using the LUCS-KDD DN software. For the example a confidence threshold of 75% and a support threshold of 1% is used. The data is split so that the first half was used as the training set and the second half the test set. A maximum size of antecedent of 5 attributes was also used. In the example 708 CARs (Classification Association Rules) are generated by Apriori-TFP before the antecedent size limit is reached. The ordered list of CARs is presented in Table 1.

The process of generating the local distribution arrays and producing the final classifier is carried out in three stages:

1. C AND W RULE IDENTIFICATION: Identify all cRules (correct rules) and wRules (wrinfg rules) in the rule list. Record in the appropriate distribution arrays the number of records covered by strong cRules. Where the wRule has higher precedence than the corresponding cRule store details in a set of records (the set A). A "strong" cRule is one with a higher precedence than the corresponding wRule.
2. CONSIDER WRONGLY CLASSIFIED RECORDS: Process the set A (the list of records that are wrongly classified). If the "offending" wRule can safely be removed from R identify other rules that override (have higher precedence) than the desired cRule correspomding to the wRule. If the offending wRule cannot be removed then adjust local distribution array for the wRule accordingly.
3. DETERMINE DEFAULT CLASSES AND TOTAL ERROR COUNTS: Adjust local distribution arrays with respect to overridden rules identified in Stage 2. Then for each "strong" cRule determine the deafault class and the total error count (Terr).
4. GENERATE CLASSIFIER: Create classifier.

Each stage is described in greater detail below.

During Stage 1 the training set is processed and appropriate c and w rules identified for each record. For every identified c rule the appropriate element in the local distribution array is incremented so that the the sum of all the local distribution arrays will be equivalent to the number of records in the training set (384 in this case). For those records where the wRule has higher precedence than the associated cRule the record is stored in a struture (SetA) with the following fields:

1. tid: The TID (Transaction ID) number of the record
2. cRule: The corresponding cRule.
3. wRule:The corresponding wRule.
4. next: Link to the next structure if any.

At the same time every rule (r) which is a cRule for at least one record is marked (r.isAcRule <-- true), and every rule r) which is a "strong" cRule is marked (r.isAstrongCrule <-- true). Thus for each record if:

1. No cRule, do nothing
2. cRule exits but no wRule, mark cRule as a "Strong" cRule
3. cRule and wRule exist, and cRule has greater precedence than wRule, mark cRule as a "Strong" cRule.
4. cRule and wRule exist, and wRule has greater precedence than cRule, create a SetA structure and add to linked list of SetA structures.

On completion of stage 1: (i) all records which are wrongly classified (but for which there is a corresponding cRule) will be collated into a linked list of SetA structures ready for further consideration, (ii) all rules which are "strong" cRules with respect to at least one record will be identified, and (iii) for each cRule the number of records classified correctly will be known.

Some sections of the rule linked list, with cRules and strong cRules marked, as of the end of Stage 1, are presented in Table 2. The sum of the distribution array elements ("class cases discovered") should equal the number of records for which a cRule was identified --- 326 in this case.

The last field shown in Table 2 represents the local distribution array for the rule (L). Thus rule 1 satisfies 0 records with class 41 and 6 records with class 42. Some rulers, such as rule 1 are strong cRules; others, such as rule 330, are simply cRules because there exists a corresponding wRule for a given record which has higher precedence (in the case of rule 330 the higher precedence rule is rule 249 with respect to record 166). This can be confirmed from the set A (containing details of all miss-classified records such a record no 166) some sections of which are given in Table 3. Note also that many rules are are not cRules with respect to any record.

1. TID = 358, Itemset =  {1 2 3 4 6 7 8 14 38} 
cRule =  {6 7 14} -> {38}  
wRule =  {1 2 3 6 8} -> {37}  
2. TID = 330, Itemset =  {1 2 3 4 6 7 8 14 38} 
cRule =  {6 7 14} -> {38}
wRule =  {1 2 3 6 8} -> {37}
3. TID = 324, Itemset =  {1 2 3 4 6 7 8 14 38} 
cRule =  {6 7 14} -> {38}  
wRule =  {1 2 3 6 8} -> {37}  
4. TID = 313, Itemset =  {1 2 3 4 5 6 8 13 38} 
cRule =  {5 6 13} -> {38}  
wRule =  {1 2 5 6 8} -> {37}
5. TID = 241, Itemset =  {1 4 5 7 8 12 20 28 38} 
cRule =  {4 20} -> {38}
wRule =  {5 7 8} -> {37}
6. TID = 224, Itemset =  {1 2 3 4 5 6 8 13 38} 
cRule =  {5 6 13} -> {38}
wRule =  {1 2 5 6 8} -> {37}
7. TID = 219, Itemset =  {2 3 5 6 7 9 21 22 37} 
cRule =  {6 22} -> {37}
wRule =  {6 21} -> {38}
8. TID = 194, Itemset =  {1 2 3 4 6 7 9 17 37} 
cRule =  {7 17} -> {37}
wRule =  {1 2 6 9} -> {38}
9. TID = 182, Itemset =  {1 2 3 4 7 8 12 16 37} 
cRule =  {1 2 3 4 8} -> {37}
wRule =  {1 16} -> {38}
10. TID = 166, Itemset =  {1 2 3 4 5 6 9 10 37} 
cRule =  {1 4 5 10} -> {37}
wRule =  {1 2 5 6 9} -> {38}
11. TID = 118, Itemset =  {1 2 3 4 6 7 8 14 38} 
cRule =  {6 7 14} -> {38}
wRule =  {1 2 3 6 8} -> {37}
12. TID = 116, Itemset =  {1 2 3 4 5 6 8 13 38} 
cRule =  {5 6 13} -> {38}
wRule =  {1 2 5 6 8} -> {37}
13. TID = 79, Itemset =  {1 3 4 5 6 9 10 19 37} 
cRule =  {1 4 5 10} -> {37}
wRule =  {1 6 9} -> {38}
14. TID = 74, Itemset =  {1 2 3 4 6 7 8 16 37} 
cRule =  {1 2 3 6 8} -> {37
wRule =  {1 6 16} -> {38}
15. TID = 22, Itemset =  {1 2 3 4 5 6 8 34 37} 
cRule =  {1 2 5 6 8} -> {37}
wRule =  {34} -> {38}

It may be the case that there are some records which are not satisfied by any rules, or which have only a cRule or a wRule. In the example given here there are 134 records that do not have an associated cRule (i.e. cannot be correctly satisfied by any rules in the rule list). To increase the likelyhood of every record having a cRule a low support threshold is recommended, however this will result in the generation of many more CARS.

In stage 2 we process the set A, the set of records that are not classified correctly. Note that for each "unreachable" cRule referenced in the set A the associated local distribution array has already been incremented accordingly. For each record in A there are two posiblilities:

1. Option 1: The wRule is a "strong" cRule for some other record, and thus the wRule cannot be omiited from the desired classifier. The appropriate element in the distribution array associated with the wRule must therefore be incremented, and that for the cRule decremented. One example of this is the case for TID 22 in the set A (klast entry given in table 3) whose wRule {34} -> {38} (rule number 344) is a "strong" cRule for another record. Thus the class record array for this wRule will be increased by 1 and the classRecord for the cRule reduced by 1.
2. Option 2: The wRule associated with the set A record is not marked as a cRule for any other record and thus will be left out of the final classifier (TIDS 182, 219 and 241 in the above example). In this case:
   1. If there are no intervening "stong" cRules between the wRule and the desired cRule, make the cRule a "strong" cRule (it may already be marked as such). TIDs 241 and 182 are examples of this.

2. If there are intervening "strong" cRules, increment the appropriate element in the local distribution array for the intervening "strong" cRule with the higest precedence, and decrement the cRule local distribution array accordingly. TID 219 is an example of this where the intervening strong c rule is rule 463, {2 3 9} -> {38} (the w rule in this case, {6 21} -> {38}; is number 252 and the c rule, {6 22} -> {37}, is number 664.

At the end of stage 2 we should have the sum of the counts in the local distribution arrays for each rule, this will be equivalent to the number of records in the training set.

Note that the intervening rules, if identified, are stored in an Overides structure which has the following four fields:

1. cRule: The overriden cRule
2. tid: The record TID number in the training set which is correctly classified by the cRule.
3. classLabel: The associated class label.
4. next: Link to next record

Some sections of the rule linked list as of the end of stage 2 are presented in Table 4 below. Note that some rules have list of rules they overide. For example rule 463 overides rule 664 with respect to TID 219. Note also that "strong" cRules are the only rules that may potentially be included in the final classifier. For example rule 565 which is a cRule, but not a "strong" cRule, will not be included.

During stage 3 the final list classification rules is generated by processesing the CBA rule list so far. Note that default rule for the classifier is the last rule selected to be included.

For each "strong" cRule in the list that correctly classifies at least one record (as a result of stage 2 a strong c rule may no longer correctly classify any records) the rule is processed as follows:

1. If there are any overriding rules these are processed first. If the TID referenced by the current overridiing rule is already satisfied by a previous rule decrement the current rule distribution array, otherwise decrement overriding rule's distribution array.
2. Calculate the accumulated number of miss-classifications (ruleErrors) that will result if the current rule were the last rule in the classifier .
3. Adjust the distribution array so that it no longer includes the number of records covered by the current rule.
4. Select a default class, the majority class displayed by the distribution array so far, an place it in the defaultClass field for the current rule.
5. Determine the number of errors defaultError, from the distribution array, that will result if all unsatisfied records are allocated to the default class.
6. Determine the total number of errors totalErrors:

   totalErrors = ruleErrors+defaultErrors
   

   
   and place in the totalErrors field for the currentrule.

The process commences with the generation of a global class distribution array which contains the number of training cases for each class. 250 Records for class 37, and 134 for class 38 in this case.

A number of sections from the rule list after stage 3 of processing are given in Table 5 below. Note that the total number of errors decreases as the number of potential rules in the classifier increases.

The final classifier (Table 6) is then constructed by finding the first strong c rule (that satisfies at least one record) with the lowest total error in the CBA rule list. In the example Rule 552 is the first rule with the minimum total errors of 34. The final classifier then comprises all the rules up to and including the identified rule pluss a default rule that produces the default class associated with the identified rule. The given classifier produces an overall accuracy of 73.44%.

(1) {9 15} -> {38}  100.0%
(2) {6 9 13} -> {38}  100.0%
(3) {30} -> {37}  100.0%
(4) {10 11} -> {37}  100.0%
(5) {9 16} -> {38}  100.0%
(6) {4 6 21} -> {38}  100.0%
(7) {4 5 8 10} -> {37}  92.3%
(8) {9 13} -> {38}  87.5%
(9) {1 3 18} -> {37}  87.5%
(10) {1 6 16} -> {38}  87.5%
(11) {6 8 10} -> {37}  86.66%
(12) {1 2 5 6 9} -> {38}  84.09%
(13) {1 2 6 9} -> {38}  83.67%
(14) {8 17} -> {37}  83.33%
(15) {6 8 22} -> {37}  83.33%
(16) {1 6 9} -> {38}  83.01%
(17) {1 3 5 7 9} -> {38}  82.85%
(18) {1 2 9} -> {38}  82.14%
(19) {23} -> {37}  80.0%
(20) {34} -> {38}  80.0%
(21) {2 4 20} -> {38}  80.0%
(22) {5 6 7 19} -> {37}  80.0%
(23) {4 5 6 7 8} -> {37}  79.5%
(24) {1 2 5 6 8} -> {37}  79.39%
(25) {2 3 9} -> {38}  79.36%
(26) {3 5 7 8} -> {37}  78.38%
(27) {2 5 7 8} -> {37}  77.96%
(28) {1 2 3 6 8} -> {37}  77.95%
(29) {2 3 6 7 8} -> {37}  77.92%
(30) {1 3 6 8} -> {37}  77.64%
(31)  null -> {38}  0.0%

5. CONCUSSIONS

REFERENCES