System and method for performing k-nearest neighbor search based on minimax distance measure and efficient outlier detection

Abstract

A system and method enable a set of dataset objects that are K-nearest neighbors (K-NN), based on their Minimax distances to a test object, to be identified without computing the all-pair Minimax distances directly. A pairwise distance between the test object and each dataset object is computed. Iteratively, one of the dataset objects is selected to add to a K-NN set until the K-NN set includes a predefined number of nearest neighbors. The selected dataset object at each iteration is the one for which there is no other unselected dataset object which has a smaller pairwise distance to any of a current subset of objects than the selected dataset object. The current subset of objects includes the test object and the dataset objects currently in the K-NN set. After the K-NN set is identified it may be output or used to generate other information, such as a test object label.

Description

BACKGROUND[0001]The exemplary embodiment relates to graphical representations of data and finds particular application in connection with the identification of nearest neighbors to a given data point, based on Minimax distances and for detection of whether the data point is an outlier.[0002]Identifying the appropriate data representation plays a key role in machine learning tasks, both in supervised and unsupervised learning methods. Different data representations can be generated, depending on the choice of distance measure. Examples of distance measures that are commonly used include the (squared) Euclidean distance, Mahalanobis distance, cosine similarity, Pearson correlation, and Hamming and edit distances. Such distances often make explicit or implicit assumptions about the underlying structure in the data. For example, squared Euclidean distance assumes that the data stays inside a (multidimensional) sphere, while the Pearson correlation is only suitable for temporal and seque...

AI Technical Summary

Benefits of technology

The patent describes a method and system for identifying a set of closest neighbors for a test object using a graph representation. The system receives a test object and calculates the pairwise distance between the test object and each dataset object in a set of dataset objects. The closest neighbors are then iteratively selected and added to the set of closest neighbors until a predefined number of closest neighbors is reached. The selected closest neighbors are the ones that have the smallest distance to the test object. The set of closest neighbors and information based on them are output. This method and system can be implemented with a processor and can be useful in identifying abnormal objects in a set of drawings or images.

Problems solved by technology

However, in many applications, the structure of the data is often very complex, folded and a priori unknown.

Therefore, any fixed assumption about the data can easily fail, which means there is a high potential for model mismatch, under-fitting or over-fitting.

However, the choice of an appropriate kernel as well as its computational complexity, restrict the use of this approach.

It is thus not suited to large-scale datasets.

However, this method is limited to Euclidean spaces and assumes the graph is sparse.

Images