# 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)  
The Apriori algorithm [26] is usually employed to extract the association relationship among items due to its simplicity and intelligibility. Thus, in this paper, we exploit the Apriori algorithm to mine the CARs, which will traverse the dataset repeatedly. Roughly, in the 1 st pass, it picks out all the frequent 1-itemSets. In the (k + 1)th pass, it first generates candidate (k + 1)-itemSets based on the frequent k-itemSets obtained in the \(k_{th}\) pass. Next, it picks out all the CCARs from the obtained candidate (k + 1)-itemSets. At the end of the current pass, CARs are picked out from the obtained CCARs based on the values of the _sup_ and _conf_. Finally, the CARs extracted from each pass conjointly make up the final CAR set. However, this procedure needs to repeatedly connect frequent k-itemSets into candidate (k + 1)-itemSets and prune ICCARs from CCARs in each pass, which is very time-consuming and severely limits the practicability of the method. To this end, we propose the DOCMA by designing and proving a set of definitions, theorems, and \begin{table}
\begin{tabular}{c c} \hline \hline
**Symbols** & **Definition** \\ \hline \(l_{i}[j]\) & The \(j_{th}\) item of the \(i_{th}\) itemSet \\ \(L_{k}\) & The set of all the frequent k-itemSets \\ \(L_{k}^{i}\) & The \(i_{th}\) element of the \(L_{k}\) \\ \(C_{k}\) & The set of the candidate k-itemSets \\ \(l_{k}^{i}\) & The \(i_{th}\) element of the set of the \(C_{k}\) \\ \(CCAR_{k}\) & The set made up of all the CCARs that contain \(k\) items \\ \(ICCAR_{k}\) & The set made up of all the CCARs that contain \(k\) items. \\ \(CAR_{k}\) & The set made up of all the CARs that contain k items. \\ _RuleSet_ & The complete set of the extracted CARs \\ \(D\) & The dataset, with \(D_{i}\) representing the \(i_{th}\) instance in \(D\) \\ \(Y\) & The class label set, with \(Y_{i}\) representing the \(i_{th}\) label in \(Y\) \\ \(I\) & The set of the items, with \(I_{i}\) representing the \(i_{th}\) items in \(I\) \\ \hline \hline \end{tabular}
\end{table} 
Table 1: Frequently used symbols and their definitions. corollaries, by which the time cost of the connection of frequent k-itemSets and the pruning of ICCARs from CCARs can be significantly reduced. **Definition 1. ** (_The connectivity of two k-itemSets): Given two k-itemSets \(l_{1}\) and \(l_{2}\), we say they are connectable only if \((l_{1}[1]=l_{2}[1])\)\(\wedge\)\(\ldots\)\(\wedge\)\((l_{1}[k-1]=l_{2}[k-1])\)\(\wedge\)\((l_{1}[k]\
eq l_{2}[k])\) is valid and \(l_{1}[k]\) and \(l_{2}[k]\) are derived from different features, where \(l_{i}[k]\) is the \(k_{th}\) item of the \(i_{th}\) frequent k-itemSets. In particular, they produce only one candidate (\(k+1\))-itemSet, i.e., \(<\)1\(l[1]\), \(l_{2}[2]\), \(\ldots\), \(l_{1}[k]\), \(l_{2}[k]\), as the connection result which is denoted as \(l_{1}\bowtie l_{2}\)._  
**Definition 2. ** (_The dictionary order of two k-itemSets): Given two k-itemSets \(l_{1}\) and \(l_{2}\), they meet the dictionary order with \(l_{1}\) preceding \(l_{2}\) if \((l_{1}[1]=l_{2}[1])\)\(\wedge\)\(\ldots\)\(\wedge\)\((l_{1}[l-1]=l_{2}[l-1])\)\(\wedge\)\((l_{1}[i]<l_{2}[i])\), (\(1\leq l\leq k\)) is true, which is denoted as \(l_{1}<l_{2}\)._  
**Theorem 1**. _The k-itemSets in \(L_{k}\) follow the dictionary order_. **Proof. ** Assume that there are \(m\) (k\(-1\))-itemSets in \(L_{k-1}\). I Apriori algorithm will sequentially judge if each of the binary tuples, i.e., \((l_{1}l_{2})\), \(\ldots\), \((l_{1}l_{m})\), \(\ldots\), \((l_{2}l_{3})\), \(\ldots\), \((l_{2}l_{m})\), \(\ldots\), \((l_{m-1}l_{m})\) is connectable and if the corresponding connection result is frequent. Here, mathematical induction is employed to prove Theorem 2. When k = 2, the 1-itemSets in \(L_{1}\) are already in dictionary order, hence, it is obvious that the above binary tuples are in dictionary order.