Data processing: artificial intelligence – Neural network – Learning task
Reexamination Certificate
1999-07-26
2004-04-13
Starks, Jr., Wilbert L. (Department: 2121)
Data processing: artificial intelligence
Neural network
Learning task
C706S048000
Reexamination Certificate
active
06721719
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates generally to systems and methods for classifying time sequences, and particularly, to a system and method for making time-dependant class predictions.
2. Discussion of the Prior Art
Classification of time sequences has great utility in providing important predictability information for time sequences, and particularly, time-series data has great applicability in business. For example, the stock prices at the New York Stock Exchange are based on time-sequence behavior of the corresponding stocks. Such data has great use in providing important predictability information for time sequences.
Methods for mining sequential patterns in time series data have been proposed by Agrawal et al., in the reference “Mining Sequential Patterns,” Proceedings of the Eleventh International Conference on Data Engineering (ICDE 95), pp. 3-14, (1995). These algorithms find the frequent time series which occur in these patterns. The algorithms discussed in this work are related to the large itemset mining methods proposed by Agrawal, Imielinski, and Swami in the reference entitled “Mining Association Rules Between Sets of Items in Large Databases,” Proceedings of the ACM SIGMOD Conference on the Management of Data (SIGMOD 93), 207-216, Washington D.C., USA.
Methods for discovering frequent episodes in event sequences have been discussed in the reference entitled “Discovery of Frequent Episodes in Event Sequences,” Data mining and Knowledge Discovery 1(3), pp. 259-289 by H. Mannila, H. Toivonen, A. I. Verkamo. In this work, frequent patterns of behavior (referred to as episodes) are detected by a computationally efficient data mining algorithm. Other work relating to pattern matching and predicting rare events in time sequences may be found in E. Keogh, and P. Smyth “A Probabilistic Approach to Fast Pattern Matching in Time-Series Databases,” Proceedings of the Knowledge Discovery and Data Mining Conference, 1997, and, in G. M. Weiss and H. Hirsh “Learning to Predict Rare Events in Event Sequences,” Proceedings of the Knowledge Discovery and Data Mining Conference, 1998 pages 359-363. Methods for mining and finding plan failures have been discussed in the reference entitled “PLANMINE: Sequence Mining for Plan Failures,”. Proceedings of the Knowledge Discovery and Data Mining Conference, 1998 pages 369-373 to M. J. Zaki, N. Lesh, M. Ogihara.
The above-mentioned references do not teach how to perform a time-dependant categorization given inputs of both feature variables that are a function of time and correspond to various time-dependant graphs and, time-dependant category variables which may take on one of several categorical values which and correspond to time-dependant graphs.
Thus, it would be highly desirable to provide a system and method for performing a time-dependant categorization, when both the feature variables and the category variables are time-dependant graphs.
SUMMARY OF THE INVENTION
The present invention is directed to a system and method for performing time-dependant classification of sequences which requires a finding of the frequent combinations of shapes which imply a given class variable at a given time-stamp.
According to the invention, there is provided a system and method for generating classification using time sequences comprising: receiving a set of time dependant feature variable graphs and a set of time dependant category variable graphs; finding frequent shapes in the time dependant feature variable graphs; utilizing the frequent shapes to generate combinations of frequent shapes; generating rules relating one or more patterns of combinations of frequent shapes to a category variable; and, performing a categorization utilizing the rules generated.
Advantageously, the present invention is useful for finding predictive relationships between the feature variables found in time dependant feature variable graphs and the class or category variable from corresponding time dependant category variable graphs.
REFERENCES:
patent: 4641355 (1987-02-01), Hongo et al.
patent: 5040214 (1991-08-01), Grossberg et al.
patent: 5056150 (1991-10-01), Yu et al.
patent: 5175793 (1992-12-01), Sakamoto et al.
patent: 5373486 (1994-12-01), Dowla et al.
patent: 5490062 (1996-02-01), Leach et al.
patent: 5832183 (1998-11-01), Shinohara et al.
patent: 6003029 (1999-12-01), Agrawal et al.
patent: 6105149 (2000-08-01), Bonissone et al.
patent: 6236964 (2001-05-01), Tamura et al.
patent: 6370437 (2002-04-01), Carter et al.
patent: 6473084 (2002-10-01), Phillips et al.
patent: 6493637 (2002-12-01), Steeg
patent: 6532456 (2003-03-01), Wang et al.
patent: 6549804 (2003-04-01), Osorio et al.
“PLANMINE: Sequence Mining for Plan Failures”, by Mohammed J. Zaki, et al., Computer Science Department, University of Rochester, Rochester NY, pp. 369-373.
“Rule discovery from time series”, by Gautam Das, et al., 1998 American Association for Artificial Intelligence, pp. 16-22.
“Querying Shapes of Histories”, by Rakesh Agrawal, et al., IBM Almaden Research Center, San Jose, CA, pp. 502-514.
“Mining Sequential Patterns”, by Rakesh Agrawal, et al., IBM Almaden Research Center, San Jose, CA, pp 3-14.
“Mining Association Rules between Sets of Items in Large Databases”, by Rakesh Agrawal, et al., IBM Almaden Research Center, San Jose, CA, pp. 207-216.
“A Probabilistic Approach to Fast Pattern Matching in Time Series Databases”, by Eamonn Keogh, et al., Dept. of Information and computer Science, University of California, Irvine, CA, pp. 24-29.
“Learning to Predict Rare Events in Event Sequences”, by Gary M.Weiss, et al., Department of Computer Science, Rutgers University, New Brunswick, NJ. pp. 359-363.
Aggarwal Charu C.
Yu Philip Shi-lung
No associations
LandOfFree
System and method for classification using time sequences does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with System and method for classification using time sequences, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and System and method for classification using time sequences will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3195686