# Efficient Rule Generation for Associative Classification
## 4 The Proposed Algorithm
Transaction IDs containing \(\langle atr1,a_{2}\rangle\to B\) are \(g(\langle atr1,a_{2}\rangle)\cap g(B)=\{5,6,7,9\}\cap\{5,6,7\}=\{5,6,7\}\), so the supports of \(\langle atr1,a_{2}\rangle\to B\) are 3. Hence, this rule is a frequent ruleitem. The confidence of \(\langle atr1,a_{2}\rangle\to B\) can be obtained from \(\frac{|g(5,6,7)|}{|g(5,6,7,9)|}\times 100=\frac{3}{4}\times 100=75\%\). The confidence of \(\langle atr1,a_{2}\rangle\to B\) is not 100% so it will be extended, whereas the confidence of \(\langle atr1,a_{1}\rangle\to A\) is \(\frac{|g(1,2,3,4)|}{|g(1,2,3,4)|}\times 100=\frac{4}{4}\times 100=100\%\), so it is the first CAR added to the classifier. \begin{table}
\begin{tabular}{c c c c c} \hline \hline
**TID** & **atr1** & **atr2** & **atr3** & **Class Label** \\ \hline
1 & \(a_{1}\) & \(b_{1}\) & \(c_{1}\) & A \\
2 & \(a_{1}\) & \(b_{1}\) & \(c_{2}\) & A \\
3 & \(a_{1}\) & \(b_{2}\) & \(c_{1}\) & A \\
4 & \(a_{1}\) & \(b_{3}\) & \(c_{1}\) & A \\
5 & \(a_{2}\) & \(b_{1}\) & \(c_{2}\) & B \\
6 & \(a_{2}\) & \(b_{2}\) & \(c_{2}\) & B \\
7 & \(a_{2}\) & \(b_{3}\) & \(c_{1}\) & B \\
8 & \(a_{3}\) & \(b_{2}\) & \(c_{2}\) & A \\
9 & \(a_{2}\) & \(b_{3}\) & \(c_{1}\) & A \\ \hline \hline \end{tabular}
\end{table} 
Table 2: A sample dataset. After discovering the first CAR, the transaction IDs associated with the CAR will be removed. From Table 3, if \(\langle attr1,a_{1}\rangle\) is found, the class will absolutely be \(A\). Hence, \(\langle attr1,a_{1}\rangle\to A\) does not need to be extended with the other attribute values and transaction IDs 1, 2, 3, and 4 should be removed. The ECARG algorithm adopts a set difference, which can help to remove transaction IDs more conveniently. For example, \(g(\langle attr1,a_{1}\rangle\to A)=\{1,2,3,4\}\) and \(g(\langle attr3,c_{1}\rangle\to A)=\{1,3,4,9\}\). The new transaction IDs of \(g(\langle attr3,c_{1}\rangle\to A)=g(\langle attr3,c_{1}\rangle\to A)-g(\langle attr1, a_{1}\rangle\to A)=\{1,3,4,9\}-\{1,2,3,4\}=\{9\}\). Then, the new transaction IDs, support, and confidence values of all rules are updated as shown in Table 4.  
From Table 4, there is no CAR with 100% confidence. \(\langle attr1,a_{2}\rangle\to B\) has the maximum confidence, and \(\langle attr3,c_{2}\rangle\to B=\{5,6\}\) is a subset of \(g(\langle attr1,a_{2}\rangle\to B)=\{5,6,7\}\). Hence, the new rule \(\langle( attr1,a_{2}),( attr3,c_{2})\rangle\to B\) is found with 100% confidence. Then the extension of \(\langle( attr1,a_{2}),( attr3,c_{2})\rangle\to B\) is stopped. For 2-ruleitem extended from \(\langle attr1,a_{2}\rangle\to B\), there is only one rule with 100% confidence and it is added to the classifier as the second CAR. \begin{table}
\begin{tabular}{l l l l} \hline \hline
**Ruleitem** & **TIDs** & **Sup** & **Conf (\%)** \\ \hline \(\langle attr1,a_{2}\rangle\to A\) & 9 & 1 & - \\ \hline \(\langle attr1,a_{2}\rangle\to B\) & 5, 6, 7 & 3 & 75 \\ \hline \(\langle attr1,a_{3}\rangle\to A\) & 8 & 1 & - \\ \hline \(\langle attr2,b_{1}\rangle\to B\) & 5 & 1 & - \\ \hline \(\langle attr2,b_{2}\rangle\to B\) & 6 & 1 & - \\ \hline \(\langle attr2,b_{3}\rangle\to A\) & 8, 9 & 2 & 66.67 \\ \hline \(\langle attr2,b_{3}\rangle\to B\) & 7 & 1 & - \\ \hline \(\langle attr3,c_{1}\rangle\to A\) & 9 & 1 & - \\ \hline \(\langle attr3,c_{1}\rangle\to B\) & 7 & 1 & - \\ \hline \(\langle attr3,c_{2}\rangle\to A\) & 8 & 1 & - \\ \hline \(\langle attr3,c_{2}\rangle\to B\) & 5, 6 & 2 & 66.67 \\ \hline \hline \end{tabular}
\end{table} 
Table 4: The remained transaction IDs after generating the first Class Association Rule (CAR).