METHOD AND APPARATUS FOR DISTRIBUTION-INDEPENDENT OUTLIER DETECTION IN STREAMING DATA

• US 20110022354A1
• Filed: 07/27/2009
• Published: 01/27/2011
• Est. Priority Date: 07/27/2009
• Status: Active Grant

• Current Assignee: Telefonaktiebolaget LM Ericsson
• Original Assignee: Telefonaktiebolaget LM Ericsson
• Inventors: Kumar, N. Hari
• Granted Patent: US 8,224,622 B2
• Time in Patent Office: Days
• US Class Current: 702/179
• CPC Class Codes: G06F 18/23213 with fixed number of clusters, e.g. K-means clustering
• CPC Class Codes: G06F 18/2433 Single-class perspective, e.g. one-against-all classification; Novelty detection; Outlier detection

Abstract

The present invention relates to an iterative method and an apparatus for distribution-independent detection of intermediate outliers and outliers in the distribution tail of streamed data. A considerable sequence of streamed data is sequentially read and subsequently assigned to matching bins. The bins are adaptively allocated when, where and if they are needed. Each bin range expands concurrently with the distribution range of the accumulating items assigned to the bin, adding a margin. For every N'"'"'th read item, overlapping or adjoining bins are merged, whereupon the bins are assessed for insider preclusion. Information regarding outliers is extracted from the remaining outlier bins when the entire data sequence has been processed.

Claims

1. A distribution-independent method for iteratively detecting outliers in streamed data comprising the data sequence X_W, being sequentially assigned to adaptive bins having expanding range, the method comprising the steps:

reading each item x of X_W;

assigning each item x to a bin having a range that comprises item x;

for every N'"'"'th read item,

merging all bins with overlapping or adjoining ranges;

assessing a bin for insider preclusion;

extracting outlier information when X_W has been processed; and

delivering output.

2. The method according to claim 1, the step of assigning further comprising the steps:

matching x against existing bins'"'"' range; and

if there is a match,

a bin weight counter C of the matching bin is being incremented;

if x lies within a predefined margin |M| from an expanding bound of the bin to which it has been assigned, the expanding bound is being expanded to x+M;

if there is no match, a new bin is being created, having a fix bound=x, and an expanding bound=x+M, and an associated bin weight counter C is set to one.

3. The method according to claim 1, where the merging step is comprising the further steps:

determining, for each bin, if its expanding bound is overlapping or immediately adjoining a neighboring bin'"'"'s fix bound; and

if so;

creating a merged bin having a fix bound identical to the original bin'"'"'s fix bound, and an expanding bound identical to the neighboring bin'"'"'s expanding bound;

setting a weight counter C of the merged bin equal to the sum of the original and neighboring bins'"'"' C'"'"'s.

4. The method according to claim 1 where the assessing step is comprising the further step:

comparing a weight counter C of the bin to a predefined insider threshold T;

if C≧

T,

the bin is being identified as an insider bin.

5. The method according to claim 1, where the extracting step is comprising determining whether the entire X_W has been processed;

and if so;

identifying as outlier bins all bins not previously identified as insider bins;

extracting from identified outlier bins their respective bin bounds.

6. An apparatus (100) for distribution-independent iterative detection of outliers in streamed data comprising the data sequence X_W sequentially assigned to adaptive bins having expanding range, said apparatus (100) comprising an input unit (120), a processing unit (140), a cache memory (160) and an output unit (180), where said cache memory (160) is adapted to store and alter data posts representing bins upon request, and where said processing unit (140) is adapted to send such requests to the cache memory (160);

read via the input unit (120) each item x of X_W;

assign each item x to a bin having a range that comprises item x;

merge bins with overlapping or adjoining bounds for every N'"'"'th read item;

assess bins for insider preclusion;

extract outlier information when the entire X_W has been processed; and

deliver the outlier information to the output unit (180).

7. The apparatus according to claim 6 where the processing unit (140) is further adapted to:

match x against existing bins'"'"' ranges; and

if there is a match,

increment a bin weight counter C of the matching bin;

if x lies within a margin |M| from the expanding bound of the bin to

which it has been assigned, expand the expanding bound to x+M;

if there is no match,

create a new bin with fix bound=x, and expanding bound=x+M; and

set a bin weight counter C to one.

8. The apparatus according to claim 6, where processing unit (140) is further adapted to:

compare, for each bin, if its expanding bound is overlapping or immediately adjoining a neighboring bin'"'"'s fix bound; and

if so;

create, and store in the cache memory (160), a merged bin with a fix bound identical to the original bin'"'"'s fix bound, and an expanding bound identical to the neighboring bin'"'"'s expanding bound;

set a weight counter C associated to the merged bin equal to the sum of the original and neighboring bins'"'"' C'"'"'s.

9. The apparatus according to claim 6 where the processing unit (140) is further adapted to assess the bin through comparing a weight counter C to a predefined insider threshold T;

and if C≧

T, identify the bin as an insider bin.

10. The apparatus according to claim 6, in which the processing unit (140) is adapted to determine when the entire X_W has been processed;

identify as outlier bins all bins not previously identified as insider bins; and

extract and compile an outlier information data file.

11. A computer readable media product including program instructions which when executed by a processor cause the processor to perform a distribution-independent method for iteratively detecting outliers in streamed data comprising the data sequence X_W, being sequentially assigned to adaptive bins having expanding range, the method comprising the steps:

reading each item x of X_W;

assigning each item x to a bin having a range that comprises item x;

for every N'"'"'th read item,

merging all bins with overlapping or adjoining ranges;

assessing a bin for insider preclusion;

extracting outlier information when X_W has been processed; and

delivering output.

12. The computer readable media product and program instructions according to claim 11 further causing:

matching x against existing bins'"'"' range; and

if there is a match,

a bin weight counter C of the matching bin is being incremented;

if x lies within a predefined margin |M| from an expanding bound of the bin to which it has been assigned, the expanding bound is being expanded to x+M;

if there is no match, a new bin is being created, having a fix bound=x, and an

expanding bound=x+M, and an associated bin weight counter C is set to one.

13. The computer readable product and program instructions according to claim 11 further causing:

determining, for each bin, if its expanding bound is overlapping or immediately adjoining a neighboring bin'"'"'s fix bound; and

if so;

creating a merged bin having a fix bound identical to the original bin'"'"'s fix bound, and an expanding bound identical to the neighboring bin'"'"'s expanding bound;

setting a weight counter C of the merged bin equal to the sum of the original and neighboring bins'"'"' C'"'"'s.

14. The computer readable product and program instructions according to claim 11 further causing:

comparing a weight counter C of the bin to a predefined insider threshold T, and if C≧

T, the bin is being identified as an insider bin.

15. The computer readable product and program instructions according to claim 11 further causing:

determining whether the entire X_W has been processed; and

if so;

identifying as outlier bins all bins not previously identified as insider bins;

extracting from identified outlier bins their respective bin bounds.