US 6,643,629 B2Granted

Method for identifying outliers in large data sets

AssigneeLucent Technologies Inc.

InventorsSridhar Ramaswamy, Rajeev Rastogi, Kyuseok Shim

Life of this patent

Estimating the term…

Loading patent…

Abstract

A new method for identifying a predetermined number of data points of interest in a large data set. The data points of interest are ranked in relation to the distance to their neighboring points. The method employs partition-based detection algorithms to partition the data points and then compute upper and lower bounds for each partition. These bounds are then used to eliminate those partitions that do contain the predetermined number of data points of interest. The data points of interest are then computed from the remaining partitions that were not eliminated. The present method eliminates a significant number of data points from consideration as the points of interest, thereby resulting in substantial savings in computational expense compared to conventional methods employed to identify such points.

Claims20

Dependent claims

A computer implemented method embedded in a recordable media for identifying a predetermined number of outliers of interest in a data set, comprising the steps of:

partitioning a plurality of data points in the data set into a plurality of partitions;
computing lower and upper bounds for each one of the plurality of partitions to identify those partitions that cannot possibly contain the predetermined number of outliers of interest;
identifying a plurality of candidate partitions from the plurality of partitions, wherein each one of the plurality of candidate partitions possibly contains at least one of a predetermined number of outliers of interest, wherein the predetermined number of outliers of interest are included within the plurality of data points in the data set;
and
identifying the predetermined number of outliers of interest from the plurality of candidate partitions wherein the data set has N data points and the predetermined number of outliers of interest is n which each have k neighboring data points, a data point p is one of the predetermined number of outliers of interest n if no more than n−1 other points in the data set reside at greater distances from the k neighboring data point than data point p.

2 more elements

A computer implemented method embedded in a recordable media for determining the top n outliers in a data set, comprising the steps of:

partitioning a plurality of data points in the data set into a plurality of partitions;
computing lower and upper bounds for each one of the plurality of partitions to identify those partitions that cannot possibly contain a predetermined number of outliers of interest;
identifying a plurality of candidate partitions from the plurality of partitions, wherein each one of the plurality of candidate partitions possibly includes at least one of n number of outliers of interest, wherein the outliers are included within the plurality of data points in the data set;
and
identifying the outliers from the plurality of candidate partitions wherein given the data set has N data points and the n number of outliers of interest which each have k neighbors, a data point p is one of the n outliers of interest if no more than n−1 other points in the data set have a higher value for Dl(p) than data point p wherein Dk(p) represents the distance of the point p to its kth nearest neighbor.

2 more elements

Dependencies are inferred from the claim text.

Facts

Application: 09/442,912Filed 18 Nov 1999
Published: US 2003/0061249 A127 Mar 2003
Granted: 4 Nov 2003
Term ends: Not estimatedThe source records don’t support an estimate.

Classification5 codes

G06F 16/30
Information retrieval; Database structures therefor; File system structures therefor: of unstructured textual data
G06F 2216/03
Indexing scheme relating to additional aspects of information retrieval not explicitly covered by G06F16/00 and subgroups: data mining
Y10S 706/925
Application using ai with detail of the ai system: business
G06F
Computing and data processing