Evaluating Case-Base Maintenance algorithms

The success of a Case-Based Reasoning (CBR) system closely depends on its knowledge-base, named the case-base. The life cycle of CBR systems usually implies updating the case-base with new cases. However, it also implies removing useless cases for reasons of efficiency. This process is known as Case-Base Maintenance (CBM) and, in recent decades, great efforts have been made to automatise this process using different kind of algorithms (deterministic and non-deterministic). Indeed, CBR system designers find it difficult to choose from the wealth of algorithms available to maintain the case-base. Despite the importance of such a key decision, little attention has been paid to evaluating these algorithms. Although classical validation methods have been used, such as Cross-Validation and Hold-Out, they are not always valid for non-deterministic algorithms. In this work, we analyse this problem from a methodological point of view, providing an exhaustive review of these evaluation methods supported by experimentation. We also propose a specific methodology for evaluating Case-Base Maintenance algorithms (the αβαβ evaluation). Experiment results show that this method is the most suitable for evaluating most of the algorithms and datasets studied.