Data processing: measuring – calibrating – or testing – Measurement system – Statistical measurement
Reexamination Certificate
1999-11-30
2003-07-29
Hoff, Marc S. (Department: 2857)
Data processing: measuring, calibrating, or testing
Measurement system
Statistical measurement
C702S057000, C702S066000, C702S108000, C702S117000, C702S182000, C702S189000
Reexamination Certificate
active
06601014
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates to a method and apparatus for deriving a statistical measure of variation from a decaying mean, and in particular to their use in telecommunications and anomaly detection applications and a system incorporating the same.
BACKGROUND TO THE INVENTION
In recent years there has been a rapid increase in the number of commercially operated telecommunications networks in general and in particular wireless telecommunication networks. Associated with this proliferation of networks is a rise in fraudulent use of such networks the fraud typically taking the form of gaining illicit access to the network, and then using the network in such a way that the fraudulent user hopes subsequently to avoid paying for the resources used. This may for example involve misuse of a third party's account on the network so that the perpetrated fraud becomes apparent only when the third party is charged for resources which he did not use.
Since fraudulent use of single account can cost a network operator a large sum of money within a short space of time it is important that the operator be able to identify and deal with the most costly forms of fraud at the earliest possible time.
One of the steps employed in, but not limited to use in, such fraud detection systems in anomaly detection from event streams.
Pattern recognition for event streams can be achieved by building up profiles of the behaviour of an entity and performing anomaly detection over these profiles. Such profiles may contain statistical information including but not restricted to an average of event values (for example mean) and a measure of the statistical variation from that average (for example variance or standard deviation). It is then possible to compare a newly received event value with the average and a measure of the typical variation from that average and to decide on that basis whether the newly received event value is or is not anomalous. For example in a telephone network the event data may relate to the number of minutes of telephone calls made in a given period (for example one day). In the case of a domestic subscriber who typically makes an average of 10 minutes of calls per day, sudden call record data of 300 or 400 minutes in one day may be indicative not only of an anomaly but of fraudulent use of the telephone system. In such a case it may be appropriate to raise an alarm only where the recently received value lies more than some multiple of standard deviations from the mean. In practice it is impractical to retain all historic values of events. However given a situation where the mean, &mgr;, of n−1 values is known, then this measure can be updated given an additional data value, v
n
, to give a new mean as defined in equation [1]. This provides an exact value for the new mean.
&mgr;
n
=(1−1
)&mgr;
n−1
+(1
)(
V
n
−&mgr;
n−1
) [1]
The calculation of the true statistical variance of the data cannot be made exactly however if the previous values are not retained. This is because all previous deviations from the mean must be recalculated when the mean changes and this cannot be done if previous values have not been retained. However, it is possible to derive approximations to the variance and estimations of the variance. A first approximation to the variance (S) can be made by updating the expression in a manner analogous to the mean update equation [1]. This method simply ignores the strict necessity to recompute all values and treats the previous deviation measure as though it were a mean deviation. This can then be updated using the equation [2].
S
n
=(1−1
)
S
n−1
+(1
)(
V
n
−&mgr;
n−1
)
2
[2]
An alternative approximation which includes a correction for the recalculation of the previous variance is defined in equation [3]. This is a known equation for variance estimation that is used for time series data. This provides a closer approximation to the true variance in the case where n is known.
S
n
=(1−1
)
S
n−1
+(1
−1
n
/2
)(
V
n
−&mgr;
n−1
)
2
The field of variance estimation has been extensively studied. The technique of Kalman Filtering, widely used in the analysis of time series data, employs a similar method for co-variance estimation.
A disadvantage of using the conventional statistical averages and measures of variance such as mean and standard deviation is that all input data values have equal influence on the resulting measures. In situations where the event data may be locally stable but vary significantly over longer time scales (e.g. telephone account usage patterns), it is undesirable that older data values relating to prior (pseudo-)stable states should retain equal influence in measures to be applied to the current (pseudo-)stable state.
This can be dealt with for conventional statistical calculations by selecting a time period and calculating the mean and variance over the period specified. This period can then serve as a moving window for the calculation of statistical measures. However, this method requires that all data values be stored for accurate updating and that a window of appropriate size can be determined. In order to provide a measure of variation that is usable for large multi-dimensional datasets an appropriate method of variance estimation based on the update formulae described must be found
OBJECT OF THE INVENTION
The invention seeks to provide an improved method and apparatus for deriving a statistical measure of variation from a decaying mean.
The invention also seeks to provide an improved method and apparatus for anomaly detection in data streams in general, and for anomaly detection in data streams relating to telecommunications account data in particular.
SUMMARY OF THE INVENTION
The invention provides an application of an adaptation of the calculation of standard deviation outlined below. It results in a specific mathematical formula for maintaining a sequential deviation measure. The method extends to allow for calculation of deviation to be itself decayed where no events of a given type occur in the event stream. This is the same as zero value events occurring and a formula that provides an approximate calculation for this is also provided.
According to a first aspect of the present invention there is provided a method of detecting anomalies in a stream of data values comprising the steps of: receiving a data value on said stream of data; calculating a new weighted average responsive to said data value, a previously stored weighted average associated with said stream of data, and a decay rate in the range of 0 to 1; and calculating a new measure of deviation from said new weighted average responsive to said new weighted average, said data value, a previously stored measure of deviation associated with said stream of data, and said decay rate; storing said new weighted average and said new measure of deviation.
In one preferred embodiment the method additionally comprises the steps of: determining an anomaly threshold responsive to said previously stored weighted average and a previously stored measure of deviation; deciding whether said data value is anomalous responsive to a comparison between said data value and said anomaly threshold
Preferably, said anomaly threshold is a sum of said previously stored weighted average and a multiple of said previously stored measure of deviation therefrom.
Preferably, said multiple is in the range 2 to 10.
Preferably, said new weighted average is a sum of a product of said decay rate and said previously stored weighted average and a product of one minus said decay rate and said data value.
In a preferred embodiment, said new weighted average is d.v+(1−d) h wherein d is said decay rate, v is said data value, and h is said previously stored weighted average.
In one preferred embodiment, said decay rate has a half-life and said measure of deviation is calculated
Cerebrus Solutions Ltd.
Foley & Hoag LLP
Hoff Marc S.
Oliver Kevin A.
Tsai Carol S
LandOfFree
Dynamic deviation does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Dynamic deviation, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Dynamic deviation will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3004764