An Algorithm for Interpolation over Nominal Values Where a Distance Metric is Defined
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 f...
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
SAGE Publishing
2007-06-01
|
| Series: | Journal of Algorithms & Computational Technology |
| Online Access: | https://doi.org/10.1260/174830107781389049 |
| _version_ | 1818922946826076160 |
|---|---|
| author | Brian Knight Fei Ling Woon Miltos Petridis |
| author_facet | Brian Knight Fei Ling Woon Miltos Petridis |
| author_sort | Brian Knight |
| collection | DOAJ |
| description | 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. |
| first_indexed | 2024-12-20T02:01:37Z |
| format | Article |
| id | doaj.art-9c5b47c65b14450c8f68390fe3c7f79d |
| institution | Directory Open Access Journal |
| issn | 1748-3018 1748-3026 |
| language | English |
| last_indexed | 2024-12-20T02:01:37Z |
| publishDate | 2007-06-01 |
| publisher | SAGE Publishing |
| record_format | Article |
| series | Journal of Algorithms & Computational Technology |
| spelling | doaj.art-9c5b47c65b14450c8f68390fe3c7f79d2022-12-21T19:57:18ZengSAGE PublishingJournal of Algorithms & Computational Technology1748-30181748-30262007-06-01110.1260/174830107781389049An Algorithm for Interpolation over Nominal Values Where a Distance Metric is DefinedBrian Knight0Fei Ling Woon1Miltos Petridis2 University of Greenwich, School of Computing and Mathematical Sciences 30 Park Row, London SE10 9LS, UK University of Greenwich, School of Computing and Mathematical Sciences 30 Park Row, London SE10 9LS, UK University of Greenwich, School of Computing and Mathematical Sciences 30 Park Row, London SE10 9LS, UKIn 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.https://doi.org/10.1260/174830107781389049 |
| spellingShingle | Brian Knight Fei Ling Woon Miltos Petridis An Algorithm for Interpolation over Nominal Values Where a Distance Metric is Defined Journal of Algorithms & Computational Technology |
| title | An Algorithm for Interpolation over Nominal Values Where a Distance Metric is Defined |
| title_full | An Algorithm for Interpolation over Nominal Values Where a Distance Metric is Defined |
| title_fullStr | An Algorithm for Interpolation over Nominal Values Where a Distance Metric is Defined |
| title_full_unstemmed | An Algorithm for Interpolation over Nominal Values Where a Distance Metric is Defined |
| title_short | An Algorithm for Interpolation over Nominal Values Where a Distance Metric is Defined |
| title_sort | algorithm for interpolation over nominal values where a distance metric is defined |
| url | https://doi.org/10.1260/174830107781389049 |
| work_keys_str_mv | AT brianknight analgorithmforinterpolationovernominalvalueswhereadistancemetricisdefined AT feilingwoon analgorithmforinterpolationovernominalvalueswhereadistancemetricisdefined AT miltospetridis analgorithmforinterpolationovernominalvalueswhereadistancemetricisdefined AT brianknight algorithmforinterpolationovernominalvalueswhereadistancemetricisdefined AT feilingwoon algorithmforinterpolationovernominalvalueswhereadistancemetricisdefined AT miltospetridis algorithmforinterpolationovernominalvalueswhereadistancemetricisdefined |