Introduction
Case-Based Reasoning (CBR) systems solve novel problems by retrieving and adapting solutions from a repository of past experiences, known as a case base. As these systems accumulate data, they often encounter the "utility problem," where the computational overhead of searching a massive case base diminishes the efficiency gains of the system. Case Base Maintenance (CBM) aims to mitigate this by selectively pruning the case base to retain only the most valuable cases while preserving overall system competence.
Traditional CBM strategies typically assume that adaptation knowledge—the rules used to modify a retrieved case to fit a new problem—is static and independent of the case base itself. However, in many modern CBR implementations, adaptation rules are derived dynamically from the existing cases. This paper introduces Adaptation-Guided Case Base Maintenance (AGCBM), a novel framework that recognizes the dual role of cases: as potential solutions and as the foundational data for generating adaptation knowledge.
The AGCBM Framework
The core innovation of AGCBM lies in its evaluation of a case's contribution to system competence. Unlike previous methods that focus solely on a case's coverage (the range of problems it can solve as a source), AGCBM considers two distinct components:
- Source Case Contribution ($CaseComp$): The effectiveness of a case when used as the starting point for solving other problems.
- Adaptation Knowledge Contribution ($AdaptComp$): The utility of a case in generating accurate adaptation rules, specifically through the "case difference heuristic."
By integrating these two metrics, AGCBM ensures that cases essential for deriving powerful adaptation rules are preserved, even if they are not frequently retrieved as primary solutions.
The AGCBM1 Algorithm
The authors present AGCBM1, an implementation tailored for regression tasks. The algorithm employs a leave-one-out evaluation on the initial case base to track the performance of cases in both source and adaptation roles. Cases are then ranked using a weighted formula: $$Comp(C) = \alpha \times CaseComp(C) + (1 - \alpha) \times AdaptComp(C)$$ Experimental results suggest that low values of $\alpha$ often yield the best performance, indicating that a case's role in the adaptation library is frequently more critical than its role as a source solution. Following ranking, a Condensed Nearest Neighbor (CNN) approach is used to select the final subset of cases.
Experimental Results
AGCBM1 was evaluated against five standard maintenance methods—Random Deletion, CNN, Coverage-Based, Reachability-Based, and Relative Coverage—across four UCI regression datasets: Automobile, Auto MPG, Housing, and Computer Hardware.
As shown in Figure 1, AGCBM1 consistently outperformed competing methods across all domains. The performance gap is most significant at high compression rates (small case base sizes), where AGCBM1 maintains high accuracy while other methods' performance degrades.
In the Hardware domain (Figure 6), AGCBM1 demonstrated an improvement of over 38% compared to random deletion when only 10 cases were maintained. This highlights the algorithm's ability to identify "bridge" cases that facilitate broad system competence through effective adaptation, even in sparse problem spaces.
Conclusion
AGCBM represents a significant shift in case base maintenance by acknowledging that adaptation knowledge is often intrinsically linked to the cases themselves. By prioritizing cases that support accurate adaptation, AGCBM1 achieves superior accuracy and stability compared to traditional footprint-based methods. Future work will focus on scaling the $O(N^2)$ leave-one-out process for larger datasets and extending the framework to classification and symbolic domains.
Summary updated