# C-MWCAR: Classification Based on Multiple Weighted Class Association Rules
## 3 Materials and Methods
### Implementation of the Proposed C-MWCAR
#### 3.2.2. Dictionary Order-Based CAR Mining Algorithm (DOCMA)
When k > 2, if the (k\(-1\))-itemSets in \(L_{k-1}\) are already in dictionary order, as only the last items of two connectable (k - 1)-itemSets are different, the final obtained frequent k-itemSets are also in dictionary order. To sum up, Theorem 2 is established. \(\square\)  
**Theorem 2. ** _Given three k-itemSets \(l_{1}\), \(l_{2}\), and \(l_{3}\) (\(l_{1}<l_{2}<l_{3}\)), if (\(l_{1}[1]=l2[1])\)\(\wedge\)\(\ldots\)\(\wedge\)\((l_{1}[l-1]=l_{2}[1])\)\(\wedge\)\((l_{1}[i]<l_{2}[i])\), (\(1\leq l\leq k\)) is true, there must exist a \(j\) (\(1\leq j\leq i\)) that makes \(l_{1}[j]<l_{3}[j]\) valid._  
**Proof. ** In the first case, i.e., \(l_{2}[i]\leq l_{3}[i]\): since \(l_{1}[i]<l_{2}[i]\), there exists a \(j=I\) that makes \(l_{1}[j]<l_{3}[j]\) valid. In the second case, i.e., \(l_{2}[i]>l_{3}[i]\): since \(l_{2}<l_{3}\), there must exist a \(j\) (\(1\leq j\leq i\)) that makes \(l_{2}[j]<l_{3}[j]\) true. Moreover, considering that \(l_{1}[j]=l_{2}[j]\) (\(1\leq j\leq i\)), we obtain \(l_{1}[j]<l_{3}[j]\). To sum up, Theorem 1 is correct. \(\square\)  
Figure 1: Workflow of the proposed C-MWCAR. **Corollary 1**. : _Given two frequent k-itemSets \(l_{1}\) and \(l_{2}\) in \(L_{k}\), if \(l_{1}<l_{2}\) and they are not connectable, then \(l_{1}\) and any frequent k-itemSet that is behind \(l_{2}\) are also not connectable._  
Proof. : Assume that \(l_{x}\) is a k-itemSet in \(L_{k}\) which is behind \(l_{2}\), i.e., \(l_{1}<l_{2}<l_{x}\) is true. Since \(l_{1}\) and \(l_{2}\) are not connectable, the largest \(l\) making (_ll[1]_ = _l2[1]_) \(\wedge\)... \(\wedge\) (\(l_{1}[l-1]\) = \(l_{2}[l-1]\)) \(\wedge\) (\(l_{1}[i]<l_{2}[i]\)) true is \(k-1\). Meanwhile, in the first \(k-1\) items of \(L_{x}\), there must be a \(j\) that makes \(l_{1}[j]<l_{x}[j]\) true according to Theorem 2. Therefore, \(l_{1}\) and \(l_{x}\) are not connectable. **Theorem 3**. : _In \(L_{k}\), if the number of frequent k-itemSets that contain a given frequent 1-itemSet is smaller than \(k\), then, the generated candidate (\(k+1\))-itemSets that contain the frequent 1-itemSet cannot be frequent._  
Proof. : According to the characteristics of the Apriori algorithm, we know that for a candidate (k + 1)-itemSet (denoted as \(l_{k+1}^{i}\)), if \(l_{k+1}^{i}\) is frequent and contains a frequent 1-itemSet denoted as \(l_{1}^{i}\), then \(l_{k+1}^{i}\) should have k k-subsequences (i.e., k-itemSets) containing \(l_{1}^{i}\) and all of them are frequent and in \(L_{k}\). Therefore, in \(L_{k}\), if the number of k-itemSets containing a given frequent 1-itemSet is smaller than k, then the candidate (k + 1)-itemSets generated by connecting those k-itemSets cannot be frequent. Algorithm 1 shows how the proposed DOCMA works. Based on Corollary 1, the optimized connection strategy is as follows (lines 10-19). When connecting two frequent k-itemSets \(l_{1}\) and \(l_{2}\), if \(l_{1}\) and \(l_{2}\) are not connectable, then \(l_{1}\) can give up comparing with all the k-itemSets that are behind \(l_{2}\). Moreover, the optimized pruning strategy is described as follows (lines 22-30). Given an arbitrary (k - 1)-subsequence of a candidate k-itemSet and a (k - 1)-itemSet in \(L_{k-1}\), denoted as \(c\) and \(l\), respectively, if \(c<l\), it is impossible for \(c\) to be the same as the (k - 1)-itemSets behind \(l\) in \(L_{k-1}\). Hence, the candidate k-itemSet cannot be frequent, so that we can prune it now. Based on Theorem 3, we can design a pre-pruning strategy to further reduce the number of connection operations required as follows (_lines 3-9). We first count the number of k-supersequences (i.e., k-itemSets) of each frequent 1-itemSet in \(L_{k}\). If the number is smaller than k, we can then delete the corresponding k-itemSets from \(L_{k}\) before connecting frequent k-itemSets, as the generated candidate (k + 1)-itemSets containing the deleted k-itemSets cannot be frequent.