Data-dependent dissimilarity measure: an effective alternative to geometric distance measures

Sunil Aryal, Kai Ming Ting, Takashi Washio, Gholamreza Haffari

    Research output: Contribution to journalArticleResearchpeer-review

    22 Citations (Scopus)

    Abstract

    Nearest neighbor search is a core process in many data mining algorithms. Finding reliable closest matches of a test instance is still a challenging task as the effectiveness of many general-purpose distance measures such as ℓp-norm decreases as the number of dimensions increases. Their performances vary significantly in different data distributions. This is mainly because they compute the distance between two instances solely based on their geometric positions in the feature space, and data distribution has no influence on the distance measure. This paper presents a simple data-dependent general-purpose dissimilarity measure called ‘mp-dissimilarity’. Rather than relying on geometric distance, it measures the dissimilarity between two instances as a probability mass in a region that encloses the two instances in every dimension. It deems two instances in a sparse region to be more similar than two instances of equal inter-point geometric distance in a dense region. Our empirical results in k-NN classification and content-based multimedia information retrieval tasks show that the proposed mp-dissimilarity measure produces better task-specific performance than existing widely used general-purpose distance measures such as ℓp-norm and cosine distance across a wide range of moderate- to high-dimensional data sets with continuous only, discrete only, and mixed attributes.

    Original languageEnglish
    Pages (from-to)479-506
    Number of pages28
    JournalKnowledge and Information Systems
    Volume53
    Issue number2
    DOIs
    Publication statusPublished - 1 Nov 2017

    Keywords

    • Cosine distance
    • Distance measure
    • m-dissimilarity
    • ℓ-norm

    Cite this