Anomaly recognition method for data streams

• US 7,546,236 B2
• Filed: 03/24/2003
• Issued: 06/09/2009
• 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: Stentiford, Frederick W M
• Primary Examiner(s): Vo; Huyen X.
• Application Number:
  US10/506,181
• Publication Number:
  US 20050143976A1
• Time in Patent Office: 2,269 Days
• Field of Search: 704/236, 704/238, 704/239, 704/243, 704/244, 704/247, 704/270, 704/270.1, 704/211, 704/213, 704/216, 704/219, 704/220, 704/200, 704/201, 704/217, 704/218
• US Class Current: 704/201
• 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 neighborhoods 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 computer implemented method of recognizing anomalies in acoustic data representative of an analog waveform, the analog waveform varying in value as a function of time and having a plurality of cycles, the acoustic data comprising a one-dimensional ordered sequence of data elements, each element being representative of a respective analog value, the method comprising:

using at least one computer with accessible input/output and at least one data store to perform the following steps;

(i) selecting a test group of test elements from the acoustic data;

(ii) selecting a comparison group of comparison elements from the acoustic data;

(iii) performing a comparison between the analog values of the test group and the analog values of 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 mismatch between the analog values of the test group and the analog values of 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 mismatch counter value and being produced in said at least one data store.

2. The 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. The method as claimed in claim 1, wherein the anomaly measure is the value of the mismatch counter.

4. The 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. The 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. The method as claimed in claim 1, wherein steps (ii), (iii) and (iv) are repeated a predetermined number of times.

7. The 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

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. The 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 neighborhood range relative to the reference test element, and/or wherein the position of the reference comparison element is selected randomly within a predetermined comparison range relative to the reference test element.

9. The 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 neighborhood range is repeated.

10. The 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. The 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.

12. The method as claimed in claim 1, wherein a 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 the comparison group.

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

14. The 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. The 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. The method as claimed in claim 14, 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. The method as claimed in claim 1, including the further step of identifying cycles in a 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. The 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. The method as claimed in claim 18, wherein the combination is a sum.

20. The method as claimed in claim 1, wherein the acoustic source data is audio data.

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

22. A computer program product stored in a computer memory device, the computer program product being configured for, in use, recognizing anomalies in acoustic data representative of an analog waveform varying in value as a function of time and having a plurality of cycles, the acoustic data comprising a one-dimensional ordered sequence of data elements, each element being representative of a respective analog value, the computer program product having:

computer-readable program means adopted for use with at least one computer with accessible input/output and at least one data store for;

selecting a test group of test elements from the acoustic data;

selecting a comparison group of comparison elements from the acoustic data;

performing a comparison between the analog values of the test group and the analog values of 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;

determining as a result of the comparison whether there is a match or a mismatch between the analog values of the test group and the analog values of the comparison group; and

determining an anomaly measure representative of the anomaly of one or more of the test elements, the anomaly measure being dependent on mismatch counter value and being produced in said at least one data store.

23. The computer readable media as claimed in claim 22, wherein the acoustic source data is audio data.

24. A computer implemented apparatus for recognizing anomalies in acoustic data representative of an analog waveform varying in value as a function of time and having a plurality of cycles, the acoustic data comprising a one-dimensional ordered sequence of data elements, each element being representative of a respective analog value, the apparatus including:

at least one computer accessible to input/output and at least one data store;

means for selecting a test group of test elements from the acoustic data;

means for selecting a comparison group of comparison elements from the acoustic data;

means for performing a comparison between the analog values of the test group and the analog values of 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 mismatch between the analog values of the test group and the analog values of 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 mismatch counter value and being produced in said at least one data store.

25. The apparatus as claimed in claim 24, wherein the acoustic source data is audio data.