A fast branch & bound nearest neighbour classifier in metric spaces

被引：73

作者：

Mico, L

Oncina, J

Carrasco, RC

机构：

[1] Depto. Lenguajes Sist. Informaticos, Universidad de Alicante, E-03080 Alicante

来源：

PATTERN RECOGNITION LETTERS | 1996年 / 17卷 / 07期

关键词：

metric spaces; nearest-neighbour; pattern recognition;

D O I：

10.1016/0167-8655(96)00032-3

中图分类号：

TP18 [人工智能理论];

学科分类号：

081104 ; 0812 ; 0835 ; 1405 ;

摘要：

The recently introduced algorithm LAESA finds the nearest neighbour prototype in a metric space. The average number of distances computed in the algorithm does not depend on the number of prototypes but it shows linear space and time complexities. In this paper, a new algorithm (TLAESA) is proposed which has a sublinear time complexity and keeps the other features unchanged.

引用

页码：731 / 739

页数：9

共 12 条

[1]

Dasarathy B.V., 1991, Nearest Neighbour (NN) Norms: NN Pattern Classification Techniques., V17, P441

[2]

Duda R. O., 1973, PATTERN CLASSIFICATI, V3

[3]

Friedman J. H., 1977, ACM Transactions on Mathematical Software, V3, P209, DOI 10.1145/355744.355745

[4] BRANCH AND BOUND ALGORITHM FOR COMPUTING K-NEAREST NEIGHBORS [J].