Similarity Measures in Case-Based Reasoning: A Comprehensive Overview

Forum topic · ✨步子哥 · 2025-12-05

Summary

This article provides a detailed explanation of similarity measures, a core component of Case-Based Reasoning (CBR) systems, based on Section 3 of the paper 'Case-Based Reasoning – Methods, Techniques, and Applications'. It covers the cognitive perspective on similarity (overall, identity, and partial similarity), and the mathematical formulation via the Minkowski metric, explaining the choice of parameter p: City-Block (p=1), Euclidean (p=2), and Max-Norm/Chebyshev (p=∞), illustrated with a robot axis signal example. It further classifies measures by data type (numerical, symbolical, structural, mixed) and application (time series, shapes, graphs, music), discusses invariance properties, and shows how partial similarities are combined through weighted sums. The article also reviews methods for learning similarity measures—weight optimization, relevance feedback, and ranking-based approaches—and addresses the semantics of normalized similarity values in [0,1], including stability challenges in incremental case bases. Finally, it bridges CBR with statistics through clustering criteria and MDL/MML learning, and outlines open problems for robust measures in dynamic environments.

Similarity measures are one of the core components of Case-Based Reasoning (CBR) systems. They evaluate how similar a new problem is to stored cases, enabling retrieval of the best-matching old cases to assist problem solving. This article 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.

1. Cognitive Perspective on Similarity

Humans routinely reason with "similarity," yet it is difficult to define precisely because it is a highly incoherent concept. From a cognitive science standpoint, similarity can be viewed from multiple angles:

Overall similarity: two objects are similar in a holistic conceptual sense (e.g., a red bicycle and a blue bicycle are both "bicycles").
Identity: exactly the same.
Similarity: partial match with differences (e.g., different colors).
Partial similarity: similar only in specific attributes.

Intelligent systems need flexible control strategies to model these types. In image databases, image content can be viewed from different perspectives (color, shape, object type); the system should determine the perspective through conversational strategies and apply the corresponding similarity measure to achieve the goal. This demands flexibility and computerized reasoning to emulate the multi-dimensional similarity judgments humans make.

2. Mathematical Perspective and the Minkowski Metric

Mathematically, similarity is typically expressed through distance measures. The most common technique is 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$$ ; and $$p$$ controls how differences are weighted.

The Minkowski metric satisfies standard metric properties: symmetry, identity, and inequality.

Choice of p:

p = 1 (City-Block / Manhattan distance): large and small differences contribute equally—suitable when all pointwise deviations matter uniformly.
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—maximum deviation is controlled.

Example (robot axis signals): For comparing a real robot axis path signal with a signal reconstructed from compressed data points:

p = 2 averages all points but emphasizes large differences, potentially making it noise-sensitive.
p = 1 treats large and small deviations equally, fitting smooth paths.
p = ∞ guarantees no pointwise deviation exceeds the threshold, keeping the axis motion smooth (no step-function-like jumps).

This shows that domain knowledge can guide the choice of p: in robot control, p = ∞ keeps path deviations bounded and avoids extreme cases.

If no a-priori knowledge exists, choose the measure empirically by trial and evaluation against quality criteria:

Classification problems: use the error rate.
Clustering: use category measures, e.g., tightness within groups and separation between groups (analogous to silhouette coefficients or F1 scores in machine learning).

3. Classification and Invariance

Similarity measures can be classified by data type:

Numerical data: e.g., Minkowski metrics.
Symbolical data: e.g., string matching.
Structural data: e.g., graph matching [29].
Mixed data types: combinations of the above.

Other classifications are application-driven:

Time series [54]: e.g., Dynamic Time Warping (DTW).
Shapes [53]: e.g., Hausdorff distance.
Graphs [29]: e.g., edit distance.
Music classification [13]: spectral-feature-based.

Invariance matters in technical systems: translation, size, scale, and rotation invariance ensure the measure is unaffected by these transformations.

Real applications usually involve multiple attribute types (e.g., sensor values plus meta-knowledge categories). These yield partial similarities Sim1, Sim2, ..., Simn, 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

The weights $$w_i$$ model each part's influence. Examples include meta-learning of image segmentation parameters [14] and medical diagnosis [15], demonstrating the effectiveness of this strategy.

4. Learning Similarity Measures

Introducing weights moves similarity from global to local: learning feature weights builds a measure customized to a specific application. Approaches include:

Linear or stochastic optimization [18]
Heuristic search [17]
Genetic programming [25]
Case ordering [20] or query ordering in NN-classification

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

New directions: bridging cases and solutions [23]. Cases are ordered via user preference relations [26] or similarity relations [27] to learn measures and relevant features. The underlying assumption: similar solutions should have similar descriptions. Features and weights are optimized until the assumption holds. Distances can also be learned via linear feature transformations [19].

5. Semantics of Similarity

Similarity values are best normalized to the interval [0,1] for comparability:

0 denotes identity (exactly equal).
1 denotes inequality.
0.5 is neutral; values between 0.5 and 0 are more similar; values between 0.5 and 1 are less similar.

Common normalization uses upper and lower bounds of feature values.

Incremental-system challenge: when a case base starts small, bounds are estimated from few cases and may be inaccurate. As new cases arrive at time $$t_k$$ , the bounds change, shifting the similarity scale and causing inconsistent decisions. Reference [55] first explained this problem; special handling is required for stability (analogous to online-learning standardization in statistics).

6. Bridging Statistics and CBR, and Open Problems

Similarity measures bridge CBR and the statistics community, e.g., clustering criteria [24, 30] and MDL/MML learning. The paper stresses CBR's incremental nature, making it well-suited to dynamic environments—but the normalization problem in online learning must be solved. Future work may explore more robust measures capable of handling noise and complex data.