Method for segmentation and identification of nonstationary time series

• US 6,915,241 B2
• Filed: 04/19/2002
• Issued: 07/05/2005
• Est. Priority Date: 04/20/2001
• Status: Expired due to Fees

• Current Assignee: Fraunhofer Gesellschaft Zur Foerderung Der Angewandten Forsching E.V.
• Original Assignee: Fraunhofer Gesellschaft Zur Foerderung Der Angewandten Forsching E.V.
• Inventors: Lemm, Steven, Kohlmorgen, Jens
• Primary Examiner(s): Hoff, Marc S.
• Assistant Examiner(s): Desta, Elias
• Application Number:
  US10/126,436
• Publication Number:
  US 20030046018A1
• Time in Patent Office: 1,173 Days
• Field of Search: 702/32, 702/41, 702/45, 702179-183, 702/189, 702/190, 702/50, 702/57, 702/127, 702/194, 702/FOR.103, 702/104, 702/139, 702/157, 702/159, 702/160, 702/163, 702/170, 702/171, 701/92, 701/97, 701/107, 701/37, 701/39, 701/40, 701/43, 701/62, 701/76, 700/102, 700/103, 704/260, 704/500, 704/240, 704/256, 704/232, 704/254, 704/242, 704/503, 714/51
• US Class Current: 702/189
• CPC Class Codes: A61B 5/374 Detecting the frequency distribution of signals, e.g. detecting delta, theta, alpha, beta or gamma waves
• CPC Class Codes: A61B 5/7264 Classification of physiological signals or data, e.g. using neural networks, statistical classifiers, expert systems or fuzzy systems neural networks per se G06N3/00; expert systems per se G06N5/00
• CPC Class Codes: G06F 18/211 Selection of the most significant subset of features
• CPC Class Codes: G06F 18/213 Feature extraction, e.g. by transforming the feature space; Summarisation; Mappings, e.g. subspace methods
• CPC Class Codes: G06F 18/295 Markov models or related models, e.g. semi-Markov models; Markov random fields; Networks embedding Markov models

Abstract

A method, implemented on a computer having a fixed amount of memory and CPU resources, for analyzing a sequence of data units derived from a dynamic system to which new data units may be added by classifying the data units, is disclosed. The method comprises determining the similarity of the data units being part of the sequence of data units by calculating the distance between all pairs of data units in a data space. The method further comprises classifying the data units by assigning labels to the data units such that, if the distance of a data unit which is to be classified to any other data unit exceeds a threshold, a new label is assigned to the data unit to be classified. Also, if the threshold is not exceeded, the label of the data unit being closest to the data unit to be classified is assigned to the data unit to be classified.

Claims

1. A method, implemented on a computer having a fixed amount of memory and CPU resources, for analyzing a sequence of measured or output data from a dynamic system, such as a machine, to categorize various parts of the sequence, said method comprising:

generating a partial data sequence, which comprises a plurality of successive data from an original sequence of said measured or output data, and which defines a data window;

shifting the data window from data to data over the original sequence, wherein one data point of the partial data sequence forming the data window at its respective position is used as a reference point characterizing each individual respective position of the data window in relation to the original sequence of data, whereby the partial data sequence forming the data window at the respective position comprises the reference point and neighboring data;

determining a characteristic function for each position of the data window such that the characteristic function is characteristic for the partial data sequence forming the data window at the respective position, and assigning each characteristic function to a respective position of the data window and to the original sequence of data by the way of the respective reference point; and

forming thereby a sequence of characteristic functions which is related to the original sequence of data by way of each individual reference point.

2. The method according to claim 1, wherein the determination of the characteristic function for every data window is done through estimation of a probability density function forming the characteristic function for each position of the data window.

3. The method according to claim 1, wherein the distance between each two functions from the sequence of functions is determined, so that a matrix of distances between the functions is obtained.

4. The method according to claim 3, wherein the matrix of distances is being analyzed by applying a Viterbi-like algorithm.

5. The method according to claim 4, wherein the application of the Viterbi-like algorithm yields an extracted sequence of prototype functions, each is associated to at least one characteristic function.

6. The method of claim 5, wherein a label is assigned to each prototype function dependent upon a similarity of the functions, so that similar functions are labeled with the same label.

7. The method according to claim 6, wherein the similarity of prototype functions is determined by the distance between the prototype functions.

8. The method according to claim 7, wherein the label of the prototype function is assigned to all associated characteristic functions.

9. The method according to claim 8, wherein the labels are used for the segmentation of the original sequence of data, by assigning the labels to the data points of the original sequence of data via the reference points, so that every segment of the original sequence of data is defined by a common label.

16. The method of claim 2, wherein the distance between each two functions from the sequence of functions is determined, so that a matrix of distances between the functions is obtained.

10. A method, implemented on a computer having a fixed amount of memory and CPU resources, for analyzing a sequence of data units derived from a dynamic system, such as a machine, to which new data units may be added by classifying the data units, said method comprising:

determining the similarity of the data units being part of the sequence of data units by calculating the distance between all pairs of data units in a data space; and

classifying the data units by assigning labels to the data units such that, if the distance of a data unit which is to be classified to any other data unit exceeds a threshold, a new label is assigned to the data unit to be classified and, if the threshold is not exceeded, the label of the data unit being closest to the data unit to be classified is assigned to the data unit to be classified.

11. The method as defined in claim 10, wherein the data units are features being generated from a sequence of original data, especially data points or vectors, by the following steps:

generating a partial data sequence, which comprises a plurality of successive data from the sequence of original data and which defines a data window,

shifting the data window from data to data over the sequence of original data, wherein one data point of the partial data sequence forming the data window at its respective position is used as a reference point characterizing each individual respective position of the data window in relation to the sequence of original data, whereby the partial data sequence forming the data window at the respective position comprising the reference point and neighboring data,

determining a characteristic function for each position of the data window such, that the characteristic function is characteristic for the partial data sequence forming the data window at the respective position of the data window and to the original sequence of data by way of the respective reference point, and

forming thereby a sequence of features with the features being the characteristic functions which is related to the sequence of original data by way of each individual reference point.

12. The method as defined in claim 11, wherein the data units are prototype features, being selected from features of the sequence of features, each prototype feature representing a segment of the sequence of features.

13. The method as defined in claim 12, wherein the segments and the prototype features are determined by calculating the segmentation of the sequence of features which minimizes the distance between the features and the prototype features together with the number of prototype changes.

14. The method of claim 13, wherein the features are probability density functions.

15. The method as defined in claim 14, wherein the sequence of features is processed on-line and/or in real time, i.e. the segmentation is updated incrementally for each subsequent feature in the sequence.

17. The method of claim 11, wherein the features are probability density functions.

18. The method of claim 12, wherein the features are probability density functions.

19. The method of claim 12, wherein the sequence of features is processed on-line and/or in real time, i.e. the segmentation is updated incrementally for each subsequent feature in the sequence.

20. The method of claim 13, wherein the sequence of features is processed on-line and/or in real time, i.e. the segmentation is updated incrementally for each subsequent feature in the sequence.

21. The method of claim 17, wherein the sequence of features is processed on-line and/or in real time, i.e. the segmentation is updated incrementally for each subsequent feature in the sequence.

22. The method of claim 18, wherein the sequence of features is processed on-line and/or in real time, i.e. the segmentation is updated incrementally for each subsequent feature in the sequence.