# 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)
In this way, we can guarantee that the selected CARs are made up of the most powerful CARs coming from different parts of the _RuleSet_, so that the selected CARs are of higher diversity and hence are more likely to cover more unknown instances in the future. The second stage aims to extract a smaller but more concise set of CARs from the obtained representative CARs for the final classifier. Ideally, the selected CARs should be able to classify most of the instances in the training set. Meanwhile, the redundant information contained in the selected CARs should be as little as possible. To meet these two requirements, we first rank the representative CARs in descending order (line 7). Given two CARs \(r_{i}\) and \(r_{j}\), \(r_{i}\) is said to have a higher rank than \(r_{j}\), denoted as \(r_{i}>r_{j}\), if and only if (1) \(r_{i}.\textit{conf}>r_{j}.\textit{conf}\); (2) \(r_{i}.\textit{conf}=r_{j}.\textit{conf}\) but \(r_{i}.\textit{sup}>r_{j}.\textit{sup}\); or (3) \(r_{i}.\textit{conf}=r_{j}.\textit{conf}\), \(r_{i}.\textit{sup}=r_{j}.\textit{sup}\), but \(r_{i}\) has more items than \(r_{j}\) does. As a result, CARs that have stronger classification ability are sorted in the front. We then design two metrics, i.e., coverage and redundancy, to respectively measure the generalization ability of the CARs that have already been selected into the final CARs set, with the amount of redundant information contained in a given CAR as follows:  
\[\textit{Coverage}=\frac{NC}{ND} \tag{5}\]  
\[\textit{Redundancy}=\frac{NPC}{NCC} \tag{6}\]  
where \(NC\), \(ND\), \(NCC\), and \(NPC\) stand for the number of instances that can be matched by CARs previously selected, the number of instances in the dataset, the number of instances that can be matched by the current CAR, and the number of instances in \(NCC\) that can be matched by previously selected CARs, respectively. For example, assume that the dataset contains 20 instances and that there are 3 representative CARs, having been in descending order. Assume that these CARs can respectively match 2, 5, and 6 instances; however, they can only match 6 different instances in total due to redundancy, i.e., 4 of these 6 instances that can be matched by the third CAR have been matched by the first or second CAR. In this case, \(NC=6\), \(ND=20\), \(NCC=6\), and \(NPC=4\); _coverage_\(=6/20=30\%\); and _redundancy_\(=4/6=66.7\%\). Finally, we sequentially judge whether each CAR in the sorted representative CARs should be included in the final CAR set. As shown in Algorithm 2 (lines 8-24), for a given CAR \(r_{i}\) in the sorted representative CARs, we first go through the dataset to see if \(r_{i}\) can match at least one instance. If so, we then compute the coverage and redundancy. Only when they are respectively smaller than the given coverage threshold \(C\) and the given redundancy threshold \(R\) will \(r_{i}\) be included in the final CAR set. In this way, the final CAR set used to build the classifier can match as many instances as possible while containing less redundant information.