Anomaly recognition method for data streams

• US 20050143976A1
• Filed: 03/24/2003
• Published: 06/30/2005
• Est. Priority Date: 03/22/2002
• Status: Active Grant

• Current Assignee: British Telecommunications PLC (BT Group PLC)
• Original Assignee: British Telecommunications PLC (BT Group PLC)
• Inventors: Steniford, Frederick W. M.
• Granted Patent: US 7,546,236 B2
• Time in Patent Office: Days
• US Class Current: 704/202
• CPC Class Codes: G10L 21/0208 Noise filtering
• CPC Class Codes: G10L 25/69 for evaluating synthetic or decoded voice signals

Abstract

This invention identifies anomalies in a data stream, without prior training, by measuring the difficulty in finding similarities between neighbourhoods in the ordered sequence of elements. Data elements in an area that is similar to much of the rest of the scene score low mismatches. On the other hand a region that possesses many dissimilarities with other parts of the ordered sequence will attract a high score of mismatches. The invention makes use of a trial and error process to find dissimilarities between parts of the data stream and does not require prior knowledge of the nature of the anomalies that may be present. The method avoids the use of processing dependencies between data elements and is capable of a straightforward parallel implementation for each data element. The invention is of application in searching for anomalous patterns in data streams, which include audio signals, health screening and geographical data. A method of error correction is also described.

Claims

1. A method of recognising anomalies in data representative of an analogue waveform, the analogue waveform having a plurality of cycles, the data comprising an ordered sequence of data elements, each element having a respective value, the method including the steps of:

(i) selecting a test group of test elements;

(ii) selecting a comparison group of comparison elements;

(iii) performing a comparison between the test group and the comparison group, the comparison involving the test elements of the test group on the one hand and the comparison elements of the comparison group on the other hand;

(iv) determining as a result of the comparison whether there is a match or a mismatche between the test group and the comparison group;

(v) repeating steps (ii), (iii), and (iv), incrementing the value of a mismatch counter each time a mismatch is found;

(vi) determining an anomaly measure representative of the anomaly of one or more of the test elements, the anomaly measure being dependent on value of the mismatch counter.

2. A method as claimed in claim 1, wherein a comparison value is generated as a result of the comparison between the test group and the comparison group, a mismatch being determined in dependence on the generated comparison value relative to a threshold value.

3. A method as claimed in claim 1 or claim 2, wherein the anomaly measure is the value of the mismatch counter.

4. A method as claimed in claim 1, wherein the steps (i) to (vi) are repeated so as to generate an anomaly measure for each of the elements in the sequence.

5. A method as claimed in claim 1, wherein steps (ii), (iii) and (iv) are repeated until a match is found between the test group and the comparison group.

6. A method as claimed in claim 1, wherein steps (ii), (iii) and (iv) are repeated a predetermined number of times.

7. A method as claimed in claim 1, wherein the test group includes a reference test element and the comparison group includes a reference comparison element, and wherein the comparison elements are selected such that the respective position of comparison elements in the sequence relative to the reference comparison element is the same as that of the test elements relative to the reference test element, the comparison involving comparing the value of each test element of the test group with the correspondingly positioned comparison element of the comparison group, the mismatch counter being incremented in dependence on the difference between the values of the correspondingly positioned elements in relation to a threshold value.

8. A method as claimed in claim 7, wherein the position in the sequence of the test elements relative to the reference test element is selected randomly from those elements within a predetermined neighbourhood range relative to the reference test element, and/or wherein the position of the reference comparison elements is selected randomly within a predetermined comparison range relative to the reference test element.

9. A method as claimed in claim 8, wherein if a match between the test group and a comparison group is found, the step of randomly selecting test elements within the predetermined neighbourhood range is repeated.

10. A method as claimed in claim 7, wherein the threshold value is dependent on the gradient of the waveform at the point in the waveform which the reference test element represents.

11. A method as claimed in claim 1, wherein the threshold value is dependent on the gradient of the waveform at some or each of the elements being used to perform a comparison between the elements of the test group and those of a comparison group.

12. A method as claimed in claim 7, wherein the difference in value of each pair of correspondingly positioned elements in the respective test group and comparison group are compared to a threshold value, the threshold value for each pair being dependent on the gradient of one or both elements of the pair.

13. A method as claimed in claim 11 or claim 12, wherein the gradient is equal to the difference in value of two adjacent elements.

14. A method as claimed in claim 1, including the further step of (a) determining if the value of the reference comparison element is within a predetermined range of the value of the reference test element, and if the value of the reference comparison is outside the predetermined range, (b) selecting again a reference comparison element.

15. A method as claimed in claim 14, wherein the steps (a), (b) of claim 14 are repeated until one of a plurality of stop conditions is met, the stop conditions including:

(1) that a match is found between the test group and a comparison group; and

(ii) that each element within a test range has been selected as a reference comparison element, the mismatch counter being incremented when a stop condition is met.

16. A method as claimed in claim 15, wherein if a first comparison reference element is selected that is outside the predetermined range, a second comparison reference element is selected that is a predetermined interval away in the ordered sequence from the first selected comparison reference element.

17. A method as claimed in claim 1, including the further step of identifying cycles in the set of data in accordance with predetermined criteria, wherein the test group of test elements is formed by one of the identified cycles, and the comparison group of comparison elements is formed by another of the identified cycles, and wherein the step of performing a comparison between the comparison group and the test group includes determining a respective integration value for the test group and the comparison group, and comparing the integration values of each group.

18. A method as claimed in claim 17, wherein the step of performing a comparison between the comparison group and the test group involves determining a respective combination of the values of the elements of the test group and those of the comparison group, and evaluating the difference in the respective combinations.

19. A method as claimed in claim 18, wherein the combination is a sum.

20. A computer programmed to perform the method of claim 1.

21. A computer program product directly loadable into the memory of a digital computer device, comprising software code portions for performing the steps of claim 1, when the product is run on a computer device.

22. A computer program product stored on a computer-usable medium, the computer program product being configured for, in use, recognising anomalies in data representative of an analogue waveform, the analogue waveform having a plurality of cycles, the data comprising an ordered sequence of data elements, each element having a respective value, the computer program product having:

computer-readable program means for selecting a test group of test elements;

computer-readable program means for selecting a comparison group of comparison elements;

computer-readable program means for performing a comparison between the test group and the comparison group, the comparison involving the test elements of the test group on the one hand and the comparison elements of the comparison group on the other hand;

computer-readable program means for determining as a result of the comparison whether there is a match or a mismatches between the test group and the comparison group;

computer-readable program means for determining as a result of the comparison whether there is a match or a mismatches between the test group and the comparison group; and

,

computer-readable program means for determining an anomaly measure representative of the anomaly of one or more of the test elements, the anomaly measure being dependent on value of the mismatch counter.

23. Apparatus for recognising anomalies in data representative of an analogue waveform, the analogue waveform having a plurality of cycles, the data comprising an ordered sequence of data elements, each elements having a respective value, the apparatus including:

means for selecting a test group of test elements;

means for selecting a comparison group of comparison elements;

means for performing a comparison between the test group and the comparison group, the comparison involving the test elements of the test group on the one hand and the comparison elements of the comparison group on the other hand;

means for determining as a result of the comparison whether there is a match or a mismatches between the test group and the comparison group;

means for determining as a result of the comparison whether there is a match or a mismatches between the test group and the comparison group; and

,

means for determining an anomaly measure representative of the anomaly of one or more of the test elements, the anomaly measure being dependent on value of the mismatch counter.