# Efficient Rule Generation for Associative Classification
## 4 The Proposed Algorithm  
In this section, a new algorithm, called the Efficient Class Association Rule Generation (ECARG) algorithm, is presented. The pseudo code of the proposed algorithm is shown in Algorithm 1. ```
Input: dataset, minisup Output: classifier
1\(\mathit{ruleItems}\) = 1-ruleitem generation from dataset whileat least one rule's support meet minsup do
2\(R\) = maximum confidence rule from ruleItems // ruleitem's support \(\geq\) minsup
3 if\(R\)'s confidence \(<\) 100 and \(R\) is not nullthen
4\(R\) = extend \(R\) with the other ruleitems
5 if\(R\) is not nullthen
6 insert \(R\) to classifier redundant rule removal
7 update support and confidence for each ruleItems
8 else
9 exit while loop
10
11 finding the default class return\(classifier\)
```  
**Algorithm 1**Efficient Class Association Rule Generation (ECARG) algorithm main process  
First, 1-frequent ruleitems are generated (line 1). To quickly find 1-frequent ruleitems, the proposed algorithm takes the advantage of a vertical data format to calculate the support ofthe ruleitems. The support of the ruleitems can be obtained from \(|g(itemset)\cap g(c_{k})|\). If any 1-ruleitem does not meet the minimum support threshold, it will not be extended with the other ruleitems. Moreover, the confidence of the frequent ruleitems can be calculated from Equation (2) by using the vertical data format. If the confidence of the ruleitem is 100%, the ruleitems will be added to the classifier directly (line 7); otherwise, it will be considered extended with the others (line 5). After discovering the most effective CAR with 100% confidence, the transaction IDs associated with the CAR will be removed to avoid redundant CARs (line 8). To remove the transaction IDs, a set difference plays an important role in our algorithm. Let \(r_{i}\) be a CAR with 100% confidence and \(T\) be a set of ruleitems in the same class of \(r_{i}\). For all \(r_{j}\in T\), the new transaction IDs of \(r_{j}\) is \(g(r_{j})=g(r_{j})-g(r_{i})\). Then, the new transaction IDs, support, and confidence values of all rules are updated (line 9). In each iteration, if there is no CAR with 100% confidence, the ruleitem \(r\) with the highest confidence will be first to be considered extended in a breadth-first search manner. It will be combined with other ruleitems in the same class until the new CAR has 100% confidence (line 5). If \(r_{i}\) is extended with \(r_{j}\) to be \(r_{new}\) and \(g(r_{j})\subseteq g(r_{i})\), then \(conf(r_{new})=100\%\). After the extended CAR is added to the classifier, the transaction IDs associated with the CAR will be removed. Finally, if no ruleitem satisfies the minimum support threshold, the CAR generation will be stopped. The proposed algorithm continues to find a default class in order to insert it to the classifier. The class with the most remaining transaction IDs is selected as the default class (line 12). To demonstrate the examples, the dataset in Table 2 is used as example data. The minimum support and confidence thresholds are set to 2 and 50%, respectively. The vertical data format represents associated transaction IDs of 1-ruleitem, as shown in Table 3. The last 2 columns of Table 3 show the support and confidence of ruleitems that are calculated. From Table 2, the \(a_{2}\) value in \(atr1\) occurs in transaction IDs 5, 6, 7, and 9, denoted as \(g(\langle atr1,a_{2}\rangle)=\{5,6,7,9\}\). Class \(A\) is in transaction IDs 1, 2, 3, 4, 8, and 9, denoted as \(g(A)=\{1,2,3,4,8,9\}\), while class \(B\) is in transaction IDs 5, 6, and 7, denoted as \(g(B)=\{5,6,7\}\). The transaction IDs containing \(\langle atr1,a_{2}\rangle\to A\) are \(g(\langle atr1,a_{2}\rangle)\cap g(A)=\{5,6,7,9\}\cap\{1,2,3,4,8,9\}=\{9\}\), so the supports of \(\langle atr1,a_{2}\rangle\to A\) are 1. The rule \(\langle atr1,a_{2}\rangle\to A\) will not be extended because its support is less than the minimum support threshold.