# C-MWCAR: Classification Based on Multiple Weighted Class Association Rules
## 3 Materials and Methods
### Implementation of the Proposed C-MWCAR
#### 3.2.3 Branch-Based CAR Selection Algorithm (BCSA)  
By now, we have obtained a large number of CARs (denoted as _RuleSet_); however, we should not include all of them in the final classifier because they contain much redundant and noisy information. However, we also cannot discard any of the CARs arbitrarily since each has a certain classification ability. Intuitively, for a given CAR, greater confidence and greater support usually mean that the CAR is more reliable and more useful, and hence should be included into the final classifier. Nevertheless, based on extensive experimental results on our dataset, we notice that similar CARs, i.e., CARs that contain many same items, often have similar confidence and support. Therefore, if we directly select CARs based on their confidence and support, the selected CARs are likely to be similar to each other. That is, the selected CARs will belong to the same part of the _RuleSet_, which makes them unrepresentative and redundant. To solve this issue, we propose the BCSA, i.e., Algorithm 2, which consists of two stages. In particular, the first stage is to preliminarily select a set of representative CARs from the different parts of the _RuleSet_, from which the second stage then picks out a smaller but more concise set of CARs. ```
1:User-specified support (_userSup_), user-specified confidence (_userConf_). All the frequent 1-items, i.e., \(L_{1}\). 2:The complete set of CARs, which is denoted as _RuleSet_. 3:\(RuleSet=\mathcal{O}\); \(CCAR_{k}=\mathcal{O}\); \(ICCAR_{k}=\mathcal{O}\); \(CAR_{k}=\mathcal{O}\); \(C_{k}=\mathcal{O}\); // initialization
4:for(k = 2; \(L_{k-1}\
eq\mathcal{O}\); k++) do
5: If delete frequent (\(k-1\))-itemSets that cannot generate frequent k-itemSets
6:for(l = 1; l \(\leq L_{k-1}\).size(); i++) do
7:numTemp = the number of k-supersequence of \(L_{1}^{i}\) in \(L_{k-1}\)
8:if(numTemp \(<\) k - 1) then
9: delete all the k-supersequence of \(L_{1}^{k}\) from \(L_{k-1}\)
10:endif
11:endif
12:endfor
13:// optimized connection of frequent (\(k-1\))-itemSets
14:for(l = 1; l \(<L_{k-1}\).size(), i++) do
15:for(j = 2; j = \(L_{k-1}\).size(); j++)do
16:if(L_{k}^{i}\) and \(L_{k}^{j}\) are connectable) then
17:\(C_{k}=C_{k}+L_{1}^{i}\bowtie L_{1}^{i}\)
18:else
19:break;
20:endif
21:endfor
22:endfor
23:endfor
24:// select the \(CCAR_{k}\) in current pass
25:\(CCAR_{k}=[c\in C_{k}\ |\ \ \mathrm{c}\) has only one item derived from class attribute]
26:\(//\) optimized pruning of \(ICCAR_{k}\)
27:for(l = 1; l \(\leq CCAR_{k}\).size(); i++) do
28:for(j = 1; j \(\leq CCAR_{k}^{j}\). (k - 1)-subsequence.size(); j++)do
29:if(the \(jj_{th}\) (k - 1)-subsequence of \(CCAR_{k}^{j}\) is not in \(L_{k-1}\)) then
30:\(ICCAR_{k}=ICCAR_{k}+CCR_{i}\)
31:break;
32:endif
33:endfor
34:// remove some \(ICCARs\) from \(CCAR_{k}\) in advance
35:\(FCCAR_{k}=CCAR_{k}-ICCAR_{k}\)
36:// select the \(CAR_{k}\) in current pass based the values of sup and conf
37:for(l = 1; i\(\leq CCAR_{k}\).size(); i++) do
38:if(\(FCCAR_{k}^{i}\).sup \(\geq\) userSup && CCAR\({}_{k}^{i}\).conf \(\geq\) userConf) then
39:\(CAR_{k}=CAR_{k}+FCCAR_{k}^{i}\)
40:endif
41:endfor
42:\(RuleSet=RuleSet\cup CAR_{k}\)
43:endfor
```  
**Algorithm 1**Dictionary order-based CAR mining algorithm (DOCMA)  
In the first stage (lines 1-6), we first divide the _RuleSet_ into a set of non-overlapping branches according to the items of each CAR. Here, the branch is defined as a set of CARs that have the same prefixes, i.e., the first few items. In particular, if the first \(k\) items of these CARs are same, we say that these CARs are in the same k-branch. In this study, we first divide the _RuleSet_ into several k-branches, from each of which we then pick out the CARs that correspond to the maximal confidence or maximal support, respectively, as the representative CARs.