Method for identifying outliers in large data sets

[0002] The present invention relates to data sets, and more particularly to a method for identifying particular data points of interest in a large data set.

[0003] The ability to identify particular data points in a data set that are dissimilar from the remaining points in the set has useful applications in the scientific and financial fields. For example, identifying such dissimilar points, which are commonly referred to as outliers, can be used to identify abnormal usage patterns for a credit card to detect a stolen card. The points in the abnormal usage pattern associated with the unauthorized use of the stolen card are deemed outliers with respect to the normal usage pattern of the cardholder.

[0004] Conventional methods employed for identifying outliers typically use an algorithm which relies upon a distance-based definition for outliers in which a point p in a data set is an outlier if no more than k points in the data set are at a distance of d or less from the point p. The distance d function can be measured using any conventional metric.

[0005] Although, methods which employ the aforementioned conventional distance-based definition of outliers can be used to identify such points in large data sets, they suffer from a significant drawback. Specifically, they are computationally expensive since they identify all outliers rather than ranking and thus identifying only particular outliers that are of interest. In addition, as the size of a data set increases, conventional methods require increasing amounts of time and hardware to identify the outliers.

[0006] A new method for identifying a predetermined number of outliers of interest in a large data set. The method uses a new definition of outliers in which such points are ranked in relation to their neighboring points. The method also employs new 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 identify and eliminate those partitions that cannot possibly contain the predetermined number of outliers of interest. Outliers are then computed from the remaining points residing in the partitions that were not eliminated. The present method eliminates a significant number of data points from consideration as outliers, thereby resulting in substantial savings in computational expense compared to conventional methods employed to identify such points.

[0007] FIG. 1 shows a flow chart depicting the steps in an exemplary embodiment of a method for identifying a predetermined number of outliers of interest in a data set according to the present invention.

[0008] FIG. 2 shows a general block diagram of the computer for carrying out the method of the present invention.

[0009] FIG. 3 shows a general flowchart of the partitioning algorithm in accordance with the present invention.

[0010] FIGS. 4A-4D show a general flowchart of the algorithm to compute lower and upper bounds in accordance with the present invention.

[0011] FIGS. 5A-5C show a general flowchart of the algorithm to compute candidate partitions in accordance with the present invention.

[0012] FIG. 6 shows a general flowchart of the algorithm to generate batch partitions in accordance with the present invention.

[0013] FIGS. 7A-7C show a general flowchart of the algorithm to compute outliers in accordance with the present invention.

[0014] The following detailed description relates to an exemplary embodiment of a method for identifying a predetermined number of outliers of interest in a large data set according to the present invention. The method utilizes both a new definition of outliers and new algorithms to identify such data points. The following terms will aid in understanding both the new definition and the new algorithms: k represents the number of neighbors of a data point p that is of interest; D^k(p) represents the distance of point p to its k^thnearest neighbor; n represents the total number of outliers of interest; N represents the total number of data points in a data set; δ represents the dimensionality of data points N; M represents the amount of memory available; MINDIST represents the minimum distance between a point or a minimum bounding rectangle (MBR) and another MBR; and MAXDIST represents the maximum distance between a point or an MBR and another MBR.

[0015] The new definition of outliers is based on determining the distance D^k(p) of a point p to its k^thnearest neighbor and then determining top n outliers, such that for a given a data set with N points and parameters n and k, an outlier can be defined as follows: a point p is a D^k_n, pronounced “dee-kay-en”, outlier if no more than an n−1 other points in the data set have a higher value for D^kthan p. Thus, the top n points with the maximum D^kvalues are deemed outliers. For example, points with larger values for D^k(p) reside in more sparsely populated clusters, i.e., neighborhoods, of points and are thus more likely to be stronger outliers than points residing in more densely populated neighborhoods which have smaller values for D^k(p).

[0016] The distance D^k(p) can be measured using any metric or non-metric distance function. The new definition of outliers is not effected by k so long as n is selected to be a small in relation to N. As the value of n increases, so does the time and expense required to identify such outliers since more points must be evaluated. By ranking outliers, the present invention can discriminate between data points p of interest. For example, outliers with similar D^k(p) distances which are ranked at the bottom of a grouping may not be true outliers and may thus be ignored. As described in more detail below, this new definition also enables the performance of conventional index-based and nested-loop algorithms 600 and 700 to be optimized to identify the top n outliers rather than just identifying all of the outliers.

[0017] A key technical tool employed in the present invention for determining which data points are outliers is the approximation of a set of points using their MBR. By computing lower and upper bounds on D^k(p) for points in each MBR, MBRs can be identified and eliminated that cannot possibly contain D^k(p) outliers. The computation of bounds for MBRs requires that the minimum and maximum distance between a point and an MBR and between two MBRs be defined.

[0018] In determining these upper and lower bounds, the square of the euclidean distance between a point or MBR and another MBR, rather than the euclidean distance itself, is used as the distance metric, thereby requiring fewer and thus less expensive computations. A point p in δ-dimensional space is denoted by [p₁, p₂, . . . , p_δ] and a δ-dimensional rectangle R is denoted by the two endpoints of its major diagonal: r=[r₁, r₂, . . . , r_δ] and r′=[r′₁, r′₂, . . . , r′_δ] such that r_i≦r′_ifor 1≦i≦n. The minimum distance between point p and rectangle R is denoted by MINDIST (p, R) such that every point in R is at a distance of at least MINDIST (p, R) from p. MINDIST (p, R) is defined as:

[0019] MINDIST (p, R)=Σ^δ_i=1x²_i,

[0020] where $\begin{array}{cc}{x}_i=\{\begin{array}{cc}{r}_i-p_i& \mathrm{if}{p}_i<r_i\\ p_i-r_i& \mathrm{if}{r}_i^{\prime }<p_i\\ 0& \mathrm{otherwise}\end{array}& \left(1\right)\end{array}$

[0021] The maximum distance between point p and rectangle R is denoted by MAXDIST (p, R), such that no point in R is at a distance that exceeds MAXDIST (p, R) from point p. MAXDIST (p, R) is defined as:

[0022] MAXDIST (p, R)=Σ^δ_i=1x²_i,

[0023] where $\begin{array}{cc}{x}_i=\{\begin{array}{cc}{r}_i^{\prime }-p_i& \mathrm{if}{p}_i<r_i+r_i^{\prime }/2\\ p_i-r_i& \mathrm{otherwise}\end{array}& \left(2\right)\end{array}$

[0024] The minimum and maximum distance between two MBRs R and S is defined by the endpoints of their major diagonals, r, r′ and s, s′, respectively. The minimum distance between MBRs R and S is denoted by MINDIST(R, S), wherein every point in R is at a distance of at least MINDIST(R, S) from any point in S and vice-versa. Similarly, the maximum distance between MBRs R and S is denoted by MAXDIST(R, S). MINDIST(R, S) and MAXDIST(R, S) are defined using the following two equations:

[0025] MINDIST (R, S)=Σ^δ_i=1x²_i,

[0026] where $\begin{array}{cc}{x}_i=\{\begin{array}{cc}{r}_i-s_I^{\prime }& \mathrm{if}{s}_i^{\prime }<r_i\\ p_i-r_i^{\prime }& \mathrm{if}{r}_i^{\prime }<p_i\\ 0& \mathrm{otherwise}\end{array}& \left(3\right)\end{array}$  MAXDIST (R, S)=Σ^δ_i=1x²_i,

[0027] where

[0028] x_i=max {|s′_i−r_i|,|r′_i−s_i|}  (4)

[0029] The partition-based algorithms used in the present invention eliminate points whose distances from their k^thnearest neighbors are so small that they are not in the top n outliers. Such pruning results in substantial improvements in performance speed due to savings in both computation time and required memory compared to conventional methods which calculate D^k_nfor all points p in N.

[0030] FIG. 1 shows a flowchart depicting the steps in an exemplary embodiment of the method for identifying a predetermined number of outliers of interest in a data set according to the present invention. At step 1, the points in a data set are partitioned using a clustering algorithm 150. At step 2, upper and lower bounds are calculated for the partitions. At step 3, candidate partitions which possibly contain outliers of interest are identified. At step 4, the top n outliers are identified from the points in the candidate partitions. These four steps are implemented using software which is stored on a single computer 10, or stored on a server on a network. Each of these four steps are described in greater detail below.

[0031] 1. Partition Data Points

[0032] A clustering algorithm 150 is used to partition the data points. Any one of a number of conventional clustering algorithms 150 can be used. Since N can be large, it is desirable to use clustering algorithms 150 that can process large data sets. One such algorithm 150 is the BIRCH algorithm. See Tian Zhang, Raghu Ramakrishnan and Miron Livny, BIRCH: An Efficient Data Clustering Method For Very Large Databases, Proceedings of the ACM SIGMOD Conference on Management of Data,pages 103-114, Montreal, Canada, June 1996. The clustering algorithms 150 then eliminate the partitions that it determines do not contain outliers. To enable such partitions to be effectively eliminated, it is desirable to partition the data set such that points which are close together are assigned to the same partition.

[0033] Since the number of partitions created is usually smaller than the number of points n, pruning the partitions, which is performed at the granularity of partitions rather than points, eliminates a significant number of points as outlier candidates. Consequently, the k^thnearest neighbor computations are performed for very few points, thereby speeding up the computation of outliers.

[0034] Referring now to FIG. 3, the partitioning algorithm 100 for partitioning the data points is shown. The main memory size M and the points in the data set are given as inputs to the BIRCH algorithm at Step S11 which generates a set of clusters, i.e. partitions, of generally uniform size at Step S12 that are smaller than and can thus be stored in main memory 20 at Step S14. By controlling the memory size M input to the BIRCH algorithm, the number of partitions generated can be controlled. Each partition is represented by the MBR at Step S13 for its points. The MBRs for partitions may overlap.

[0035] 2. Compute Upper and Lower Bounds for Partitions

[0036] Referring now to FIGS. 4A-4D, the algorithm computeLowerUpper 200 which is set forth below is used to compute lower and upper bounds, stored in P.lower and P.upper, respectively, on D^kfor points p in each partition P, wherein for every point p ε P, P.lower≦D^k(p)≦P.upper.

[0037] The lower and upper bounds for a particular partition P are determined by finding the l partitions closest to P with respect to MINDIST and MAXDIST such that the number of points in P₁, . . . , P_lis at least k, at Steps S28, S29, S30, S31, S32, S33 and Steps S34, S35, S36, S37, S38A, S38B. Since the partitions can be stored in main memory 20, a main memory index can be used to find the l partitions closest to P. For each partition, its MBR is stored in the main memory index 22.

[0038] The algorithm computeCandidatePartitions 300, which identifies candidate partitions and is set forth and described below, keeps track of minD^kDist which is a lower bound on D^kfor an outlier, and passes this value to the algorithm computeLowerUpper 200 to optimize the computation of the bounds for a partition P. If P.upper for partition P is less than minD^kDist, then it cannot contain outliers and computation of its bounds is terminated, at Steps S39 and continues with Steps S43, S44 and S45. At Step S44, the node's childer are appended to the nodelist. At Step S45, the nodelist is sorted by mindist.

[0039] The algorithm computeCandidatePartitions 300 uses three data structures to compute lower and upper bounds: a list nodeList of nodes in the main memory index 22 containing partitions that still need to be searched, at Steps S24, S25, S26, S41, S48, S49 and S50; and two heaps, each containing the closest partitions to P such that the total number of points in them is at least k. This algorithm stores partitions in two heaps, lowerHeap and upperHeap in the decreasing order of MINDIST and MAXDIST from P, respectively, such that partitions with the largest values of MINDIST and MAXDIST appear at the top of the heaps, at Steps S30, S31 and S36, S37.

[0040] Referring still to FIGS. 4A-4D, at Step S21 nodelist is set to root. Step S21 is followed by Step S22 where P.lower and P.upper are set to infinity. Step S23 sets lowerheap and upperheap to null.

[0041] 3. Identify Candidate Partitions

[0042] The algorithm computeCandidatePartitions 300, which is set forth below, is used to identify the candidate partitions that can potentially contain outliers from among the set of all partitions Pset, and to then eliminate the remaining partitions.

[0043] Referring now to FIGS. 5A-5C, the lower and upper bounds that were previously computed are used to first estimate the lower bound minD^kDist and then a partition P is a candidate only if P.upper≧minD^kDist, as determined at Steps S66, S67. The lower bound minD^kDist can be computed using the P.lower values for the partitions, wherein if P₁, . . . , P_lrepresents the partitions with the maximum values for P.lower that contain at least n points, then minD^kDist=min {P_i.lower:≦i<1}.

[0044] The algorithm computeCandidatePartitions 300 inserts each partition in Pset into memory index 22 at Steps S51 and S52. Furthermore, the algorithm computeCandidatePartitions 300 sets partHeap to null and the minD^kDist equal to 0, at Steps S53 and S54.

[0045] The algorithm computeCandidatePartitions 300 stores the partitions with the largest P.lower values and containing at least n points in the heap partHeap. These partitions are stored in increasing order of P.lower in partHeap and minD^kDist is thus equal to P.lower for the partition P at the top of partHeap. By maintaining minD^kDist, it can be passed as a parameter to computeLowerUpper algorithm 200 at Step S56 of this algorithm and the computation of bounds for a partition P can be terminated if P.upper for that partition falls below minD^kDist. If, for a partition P, P.lower is greater than the current value of minD^kDist, then P.lower is inserted into partHeap and the value of minD^kDist is appropriately adjusted at Steps S57, S58, S59, S60, S61A, S61B and S63 of this algorithm.

[0046] At Step S64, candset is set to null. In the for loop at Steps S66, S67, S68 and S69 of this algorithm, the set of candidate partitions candSet is identified, and for each candidate partition P, partitions Q that can potentially contain the k^thnearest neighbor for a point in P are added to P .neighbors which contain P. At Step S70, the candset is returned.

[0047] 4. Identify n Outliers of Interest

[0048] The top D^k_noutliers are computed from the points in the candidate partitions candSet. If the points in all the candidate partitions and their neighbors are smaller than main memory size M, then all the points are stored in a main memory spatial index 22. A conventional index-based algorithm 600 is then used to compute the n outliers by probing the index to compute D^kvalues only for points belonging to the candidate partitions. Since both the size of the index and the number of candidate points will typically be smaller than the total number of points in the data set, then the outliers of interest will be identified more quickly by probing the candidate partitions rather than by executing the index-based algorithm 600 for the entire data set of points.

[0049] If all of the candidate partitions and their neighbors exceed the main memory size M, then the candidate partitions must be processed in batches. In each batch, a subset of the remaining candidate partitions that along with their neighbors are smaller than main memory size M is selected for processing. The selection of candidate partitions for a batch is performed by the algorithm genBatchPartitions 500 which is set forth below.

[0050] For each candidate partition P, P.neighbors denotes the neighboring partitions of P, which are all the partitions within distance P.upper from P. Points belonging to neighboring partitions of P are the only points that need to be examined to identify D^kfor each point in P. The set of candidate partitions is an input parameter to the algorithm, while the candidate partitions for a batch and their neighbors are returned in candBatch and neighborBatch, respectively.

[0051] At Step S81, the algorithm genBatchPartitions 500 sets the candbatch and the neighborbatch equal to null. At Step S83, candbatch is set equal to candbatch union partition P. At Step S84, neighborbatch is set equal to neighborbatch union P.neighbors.

[0052] To identify the D^k_noutliers, the candidate partition with the maximum value for P.lower must first be selected at Step S82 of the algorithm genBatchPartitions 500. This candidate partition is then used to select subsequent partitions at Steps S85, S86, S88, and S89 of the algorithm 500. For successive partitions, partitions are selected which have a large overlap with the previously selected partitions. The rationale for doing so is that it minimizes the number of batches in which a partition participates. Since processing a partition in a batch requires that all of the points in the batch to be first read from disk and then to be inserted into the main memory index 22, both of which can be expensive, reducing the number of times these steps are performed for a partition results in substantial performance improvements. In addition, processing partitions with large overlaps in a batch guarantees that the points processed in a single batch are relatively close to each other. As a result, computation of D^kfor candidate points becomes more efficient. The process of adding candidate partitions to the batch is repeated until the number of points in the selected partitions exceeds M.

[0053] The algorithm computeOutliers 400 which is set forth below is then used to identify the D^k_noutliers from the candidate partitions in candSet computed by the algorithm computeCandidatePartitions 300.

[0054] The algorithm computeOutliers 400 uses a conventional index-based algorithm 600 and has as an input parameter the minD^kDist value computed by the algorithm computeCandidatePartitions 300 to identify the candidate partitions. While being executing, the algorithm computeOutliers 400 keeps track of the top n outliers in outHeap and minD^kDist.

[0055] At Step S91, outheap is set equal to null.

[0056] Once the candidate partitions and their neighbors for a batch have been identified at Steps S93 and S92 of the algorithm computeOutliers 400, the points from neighborBatch are inserted into a main memory index at Steps S94 and S95. The while loop spanning Steps S96, S97, S98, S99, S101, S102, S103A, S103B, S104A, S104B and S106 executes the index-based algorithm 600 for points in the candidate partitions. The candidate partitions are evaluated in decreasing order of their P.lower values so that if the points with the highest D^kvalues are found early, then more points can be eliminated later since minD^kDist will converge earlier to the D^kvalue for the nth outlier.

[0057] Since the value of minD^kDist is continuously refined during the procedure, partitions whose P.upper value drops below minD^kDist cannot contain any outliers and can thus be ignored at Steps S98 and S108. At Steps S99, S101, S102, S103A, S103B, S104A, S104B and S106, for every point in p, the procedure getK^thNeighborDist is used to compute D^k(p) and p is inserted into the outlier heap if it is a stronger outlier than the current nth outlier in outHeap. At Step S110, the outlier heap is returned.

[0058] Alternatively, a conventional block nested-loop algorithm can be used in place of an index-based algorithm 600 to compute the to compute the D^k_noutliers from the candidate partitions in candSet generated by the algorithm computeCandidatePartitions 300. In a block nested-loop algorithm 700, if the points in candSet fit in memory, then they are loaded into memory and a single pass is made over their neighboring partitions. Otherwise, genBatchPartitions 500 is used to generate candBatch. The candidate points that are processed during a batch. The only difference is that instead of requiring neighborBatch to fit in main memory, only the c points in candBatch and c heaps are required, one heap for each point p in candBatch containing the distances of p's k nearest neighbors, to fit in memory.

[0059] Points in candBatch and their heaps are stored in memory, and a single pass is made over neighborBatch which is disk-resident. For each point q in neighborBatch, if the distance between a point p in candBatch and q is smaller than p's distance from its current k^thnearest neighbor, then q replaces p's k^thneighbor. Also, minD^kDist, the lower bound on D^kfor an outlier, is maintained during execution and used to eliminate points and partitions whose k^thnearest neighbor is known to be at a distance of less than minD^kDist as for the index-based algorithm 600.

[0060] The partition-based algorithms of the present invention scale well with respect to both data set size and data set dimensionality. They also perform more than an order of magnitude better than conventional index-based and nested-loop algorithms.

[0061] Numerous modifications to and alternative embodiments of the present invention will be apparent to those skilled in the art in view of the foregoing description. Accordingly, this description is to be construed as illustrative only and is for the purpose of teaching those skilled in the art the best mode of carrying out the invention. Details of the structure may be varied substantially without departing from the spirit of the invention and the exclusive use of all modifications which come within the scope of the appended claims is reserved.