Similarity Measures in Case-Based Reasoning: A Comprehensive Overview

Similarity measures are one of the core components of Case-Based Reasoning (CBR) systems, used to evaluate how similar a new problem is to stored cases, so that the most matching old cases can be retrieved to assist problem solving. This post is a detailed explanation based on Section 3 of the paper *Case-Based Reasoning – Methods, Techniques, and Applications*, covering the cognitive perspective, mathematical definitions, concrete measures, selection methods, classification, application extensions, and semantics, with formulas, examples, and connections to statistics.

1. The Cognitive Perspective on Similarity

Humans tend to reason with the concept of "similarity" but can rarely define it precisely, because similarity is a highly incoherent concept. From a cognitive science perspective:

• Overall Similarity: two objects are similar at a conceptual level, e.g., a red bicycle and a blue bicycle are both "bicycles".
• Identity: exact sameness.
• Similarity: partial match with differences (e.g., different colors).
• Partial Similarity: similarity only in specific attributes.

In intelligent systems, flexible control strategies are needed to model these types. Particularly in image databases, image content can be viewed from different perspectives (color, shape, etc.). Systems should determine the perspective through conversational strategies and apply the corresponding similarity measure to achieve the goal — e.g., in image retrieval, a user may query by "color" or "object type", and the system must dynamically adjust the similarity computation.

2. Mathematical Perspective and the Minkowski Metric

Mathematically, similarity is usually expressed via distance measures, most commonly the Minkowski metric:

\[d^{(p)}_{i i'} = \left( \frac{1}{J} \sum_{j=1}^{J} |x_{i j} - x_{i' j}|^p \right)^{1/p}\]
• i and i' denote two cases; J is the number of features; x_{ij} is the j-th feature value of case i; p controls how differences are weighted.
• The Minkowski metric satisfies symmetry, identity, and inequality properties.

Choice of p depends on the importance of differences:

• p = 1 (City-Block / Manhattan distance): large and small differences contribute equally.
• p = 2 (Euclidean metric): more sensitive to large differences, suitable when emphasizing large deviations.
• p = ∞ (Max-Norm / Chebyshev distance): ensures no single difference exceeds a predefined threshold.

Example: comparing a real robot axis 1-D path signal with a signal reconstructed from compressed data points:

• p = 2 averages all points but emphasizes large differences, potentially noise-sensitive.
• p = 1 treats all differences equally, suitable for smooth paths.
• p = ∞ guarantees no point deviates beyond a threshold, keeping robot axis motion smooth without step-function jumps.

This shows that domain knowledge can guide the choice of p. Without a-priori knowledge, one tries different measures and observes behavior against quality criteria: error rate for classification problems, category measures (e.g., cluster compactness/separation, analogous to silhouette scores or F1 in machine learning) for clustering.

3. Classification and Invariance

Similarity measures can be classified by data type:

• Numerical data: e.g., Minkowski.
• Symbolical data: e.g., string matching.
• Structural data: e.g., graph matching.
• Mixed data types: combinations of the above.

Other classifications are application-based:

• Time series: e.g., Dynamic Time Warping (DTW).
• Shapes: e.g., Hausdorff distance.
• Graphs: e.g., edit distance.
• Music classification: spectral features.

Invariance (translation, size, scale, rotation) is important in technical systems so measures are unaffected by these transformations.

Real applications usually involve multiple attributes (e.g., sensor values + meta-knowledge categories), forming partial similarities Sim₁, Sim₂, …, Simₙ, each based on a different measure. Overall similarity is a weighted sum:

\[\text{Sim} = w_1 \text{Sim}_1 + w_2 \text{Sim}_2 + \dots + w_n \text{Sim}_n\]

Weights w_i model each part's influence. Examples include meta-learning of image segmentation parameters and medical diagnosis.

4. Learning Similarity Measures

Introducing weights moves similarity from global to local. Attribute weights can be learned to build custom measures via:

• Linear or stochastic optimization
• Heuristic search
• Genetic programming
• Case ordering or query ordering in NN classification

Relevance Feedback: learning the distance function from user feedback, popular in databases and image retrieval. The optimization criterion is system accuracy rather than individual case pairs, favoring learning methods and case descriptions.

New directions: bridging cases and solutions — ranking cases by user preference or similarity relations and learning measures and relevant features. The assumption: similar solutions should have similar descriptions; features and weights are optimized until this holds. Linear feature transformations can also be used to learn distances.

5. The Semantics of Similarity

Similarity values are typically normalized to [0, 1] for comparability:

• 0 = identity (exactly the same)
• 1 = not equal
• 0.5 = neutral; values from 0.5 toward 0 indicate more similar, toward 1 less similar.

A common normalization uses upper and lower bounds of feature values. Incremental system challenge: when the case base starts small, bounds are estimated from limited cases and may be inaccurate. As new cases arrive over time, bounds shift, changing the similarity scale and causing inconsistent decisions — a problem that requires special handling for stability (analogous to normalization issues in online learning).

6. Bridging Statistics and CBR, and Open Problems

Similarity measures bridge CBR and the statistics community, e.g., clustering criteria and MDL/MML learning. CBR's incremental nature makes it suitable for dynamic environments, but normalization in online learning must be addressed. Future work includes more robust measures that handle noise and complex data.