An Algorithm for Interpolation over Nominal Values Where a Distance Metric is Defined

Abstract

In this paper we propose a generalisation of the k-nearest neighbour retrieval method that allows for the specification of a distance metric in the solution space. It is an interpolative method which is proposed to be effective for sparse case bases. The method relies on the definition of an error function in terms of distance metrics in the solution and problem space. The retrieved solution is taken to minimise this error function. The method applies equally to nominal, continuous and mixed domains, and does not depend upon an embedding n-dimensional space. In continuous Euclidean problem domains, the method is shown to be a generalisation of Shepard's Interpolation method. We refer the retrieval algorithm to as the Generalised Shepard Nearest Neighbour (GSNN) method. A novel aspect of GSNN is that it provides a general method for interpolation over nominal solution domains. The performance of the retrieval method is examined with reference to the irises classification problem, and to a simulated sparse nominal value test problem. The introduction of a metric over the iris classes is shown to give an improved classification performance for sparse case bases. The algorithm is also shown to out-perform conventional nearest neighbour methods on a simulated sparse problem.