Case Base Adaptation Using Solution-Space Metrics

1 Introduction

We present in this study a Case-Based Reasoning (CBR) retrieval method that utilises a distance metric imposed on solution space. The motivation for such a method is to extend a powerful interpolative method, already proven in the real domain, so that it applies equally in the do­ main of nominal values. Interpolative methods are well studied in the real domain, and can give good results from relatively sparse datasets. However, no general in­ terpolative method exists for nominal (discrete) solution domains.

' The support by the University of Greenwich and Tunku Ab­ dul Rahman College (TARC) is acknowledged.

Fei Ling Woon Tunku Abdul Rahman College School of Arts & Science Kuala Lumpur, Malaysia f.woon@gre.ac.uk

2 An Error Function

The GSNN method will be applied to a general class of problem and solution domains. A distance metric dx (x, x;) is here defined on the problem domain X and dr (y,y;) on the solution domain Y. For the problem space, the term II x-x; II in the Shepard's method [1968] is generalised to dx(x,xJ over X. For the solution space Y, dy(y,yJ is used where y=f(x) is the value of y which minimizes the error function:

That this is a minimum follows from the positive definite

The function l(y) depends only upon the Euclidean dis­ tance over Y = R and X = Rd. In order to generalise the method completely, we propose the error function:

Here, the set {x1,x2, ... ,xk} are the k nearest neighbours in the problem space to the point x. dx(x,xJ and dy(y,yJ are distance on domains xe X ,ye Y. The retrieved value y is the value y e Y which minimizes the error function I. The GSNN algorithm is given as follows:

3 Illustrative Example

In this example we illustrate in detail how the method works. We choose the Iris data set [Fisher, 1936]. The problem space is X and x = (x1, x2, x3, x4) is a point in X. The solution space Y = {setosa, versicolour, virginica}. For the problem space we define distance according to a weighted sum of attributes. For the Y space, we define dy(y,y ') by using the distances between cluster centres to represent the distance between the classes. These dis­ tances are shown in the following matrix:

We take two cases, one from setosa and one from virginica:

xi= (4.4, 2. 9, 1.4, 0.2), y i= setosa

x2 = (7.2, 3.2, 6, 1.8), y2 = virginica

We take as target the versicolour iris:

X= (5.5, 2.3, 4, 1.3), y =?

Taking p=1 and k = 2, the function 1(y) is:

= (0.36F 1 dy( y,setosa/ +(0.35F 1 dy( y, virginica/ /(0.36F 1 + (0.35F 1

Since 1(versicolour) is minimum, we take y=versicolour as the estimated value. This example shows an advantage of the interpolation method in situations where cases are sparse, in that it can correctly predict nominal values not represented in the case base itself.

4 Test on a Simulated Case Base

To examine how the GSNN method might work on real case bases, we simulated case bases of varying density and structure, and used the method to estimate simulated target sets. As a basis for the simulation, we adapted the function used by Ramos and Enright [2001] (i.e. y = Int(lO sin 271X 1 *sin 271X 2 ) ) to give 21 nominal values, y1 .... . y21. These 21 nominal values inherited a distance met­ ricfrom the numeric values: d(y;.Yj) = I Y; - Yj 1.

Test 6.1 uses regularly spaced cases at various case densi­ ties. This might represent a well organised case base. Test 6.2 uses randomly selected cases, and is intended to repre­ sent disorganised sparse case bases. Cases (xi. x2, y) are con­ structed in the domain: 0 5 x1,x2 5 1, over a regular square lattice, with 10 2 ,20 2 ,30 2 points.

Table 1 shows the result of Test 6.1. These results confirm that GSNN with k > 1 can out-perform both k-NN and DWNN [Mitchell, 1997] for case bases with regular struc­ ture. Table 2 shows the results of Test 6.2. The results show that more errors are recorded for random case bases than for

Table 2. Errors in estimating a test set of 1000 targets, for random case bases.

5 Conclusion

In this paper, we have proposed a method for interpolation over nominal values. The method generalises the Shepard's interpolation method by expressing it in terms of the mini­ mization of a function I(y). This function relies only on dis­ tance metrics defined over problem and solution spaces. The method has an advantage for CBR in that it is applica­ ble to case bases with nominal values in the problem and solution domain where no natural ordering exists. The ex­ amples studied indicate that GSNN could be useful in CBR with a sparse set of cases, and particularly where the cases can be organised. Tests show that GSNN is more efficient as a retrieval engine than other nearest neighbour methods. The inclusion of a solution space metric in the GSNN tech­ nique could be useful in two areas of CBR: (i) The selection of an optimum case base, (ii) Case based model building, from experimental or numerical modeling exercises. Inves­ tigations using numerical models indicate at GSNN would appear to be a promising approach for the construction of efficient case-based models.