Deakin University
Browse

Lowest probability mass neighbour algorithms: relaxing the metric constraint in distance-based neighbourhood algorithms

Version 2 2024-06-06, 04:33
Version 1 2018-09-10, 14:51
journal contribution
posted on 2019-02-01, 00:00 authored by K M Ting, Ye ZhuYe Zhu, M Carman, Y Zhu, T Washio, Z H Zhou
The use of distance metrics such as the Euclidean or Manhattan distance for nearest neighbour algorithms allows for interpretation as a geometric model, and it has been widely assumed that the metric axioms are a necessary condition for many data mining tasks. We show that this assumption can in fact be an impediment to producing effective models. We propose to use mass-based dissimilarity, which employs estimates of the probability mass to measure dissimilarity, to replace the distance metric. This substitution effectively converts nearest neighbour (NN) algorithms into lowest probability mass neighbour (LMN) algorithms. Both types of algorithms employ exactly the same algorithmic procedures, except for the substitution of the dissimilarity measure. We show that LMN algorithms overcome key shortcomings of NN algorithms in classification and clustering tasks. Unlike existing generalised data independent metrics (e.g., quasi-metric, meta-metric, semi-metric, peri-metric) and data dependent metrics, the proposed mass-based dissimilarity is unique because its self-dissimilarity is data dependent and non-constant.

History

Journal

Machine learning

Volume

108

Issue

2

Pagination

331 - 376

Publisher

Springer

Location

New York, N.Y.

ISSN

0885-6125

eISSN

1573-0565

Language

eng

Publication classification

C1 Refereed article in a scholarly journal

Copyright notice

2018, The Author(s)