A general state-based temporal pattern recognition

Doctoral thesis English OPEN
Zheng, Aihua (2012)
  • Subject: QA

Time-series and state-sequences are ubiquitous patterns in temporal logic and are widely used to present temporal data in data mining. Generally speaking, there are three known choices for the time primitive: points, intervals, points and intervals. In this thesis, a formal characterization of time-series and state-sequences is presented for both complete and incomplete situations, where a state-sequence is defined as a list of sequential data validated on the corresponding time-series. In addition, subsequence matching is addressed to associate the state-sequences, where both non-temporal aspects as well as rich temporal aspects including temporal order, temporal duration and temporal gap should be taken into account.\ud \ud Firstly, based on the typed point based time-elements and time-series, a formal characterization of time-series and state-sequences is introduced for both complete and incomplete situations, where a state-sequence is defined as a list of sequential data validated on the corresponding time-series. A time-series is formalized as a tetrad (T, R, Tdur, Tgap), which denotes: the temporal order of time- elements; the temporal relationship between time-elements; the temporal duration of each time-element and the temporal gap between each adjacent pair of time-elements respectively.\ud \ud Secondly, benefiting from the formal characterization of time-series and state-sequences, a general similarity measurement (GSM) that takes into account both non-temporal and rich temporal information, including temporal order as well as temporal duration and temporal gap, is introduced for subsequence matching. This measurement is general enough to subsume most of the popular existing measurements as special cases. In particular, a new conception of temporal common subsequence is proposed. Furthermore, a new LCS-based algorithm named Optimal Temporal Common Subsequence (OTCS), which takes into account rich temporal information, is designed. The experimental results on 6 benchmark datasets demonstrate the effectiveness and robustness of GSM and its new case OTCS. Compared with binary-value distance measurements, GSM can distinguish between the distance caused by different states in the same operation; compared with the real-penalty distance measurements, it can filter out the noise that may push the similarity into abnormal levels.\ud \ud Finally, two case studies are investigated for temporal pattern recognition: basketball zone-defence detection and video copy detection.\ud \ud In the case of basketball zone-defence detection, the computational technique and algorithm for detecting zone-defence patterns from basketball videos is introduced, where the Laplacian Matrix-based algorithm is extended to take into account the effects from zoom and single defender‘s translation in zone-defence graph matching and a set of character-angle based features was proposed to describe the zone-defence graph. The experimental results show that the approach explored is useful in helping the coach of the defensive side check whether the players are keeping to the correct zone-defence strategy, as well as detecting the strategy of the opponent side. It can describe the structure relationship between defender-lines for basketball zone-defence, and has a robust performance in both simulation and real-life applications, especially when disturbances exist.\ud \ud In the case of video copy detection, a framework for subsequence matching is introduced. A hybrid similarity framework addressing both non-temporal and temporal relationships between state-sequences, represented by bipartite graphs, is proposed. The experimental results using real-life video databases demonstrated that the proposed similarity framework is robust to states alignment with different numbers and different values, and various reordering including inversion and crossover.
  • References (18)
    18 references, page 1 of 2

    [1] Adjeroh D, Lee M & King I.: A distance measure for video sequences. Computer Vision and Image Understanding. 75(1-2), 1999, pp: 25-45.

    [2] Agrawal R, Faloutsos C, & Swami A.: Efficient similarity search in sequence databases. In Proc. of the 4th Int'l Conf. on Foundations of Data Organization and Algorithms, Chicago, Illinois, USA , Oct 13-15, 1993, pp:69-84.

    [3] Allen J.: Towards a General Theory of Action and Time. Artificial Intelligence 23, 1984, pp:123-154.

    [4] Beckmann N, Kriegel H, Schneider R & Seeger B.: The r*-tree: An efficient and robust access method for points and rectangles. In Proc. of the 1990 ACM SIGMOD Int'l Conf. on Management of Data, Atlantic City, NJ, May 23-25, 1990. pp:322-331.

    [5] http://kdd.ics.uci.edu/databases/synthetic_control/synthetic_control.html

    [6] Keogh E.: Exact indexing of dynamic time warping. in Proc. of the 28th Int'l Conf. on Very Large Data Bases, Hong Kong, China, Aug20-23, 2002, pp:406-417.

    [7] Ma J & Hayes P.: Primitive Intervals Vs Point-Based Intervals: Rivals Or Allies?. the Computer Journal, 49(1), 2006, pp:32-41.

    [8] Ma J, Bie R, Zhao G.: An ontological Characterization of Time-series and State-sequences for Data Mining. Proc. of the 5th International Conference on Fuzzy Systems and Knowledge Discovery, Jinan, Shandong, Oct 18-20, 2008, pp:325-329.

    [9] Moon Y, Whang K & Han W.: General Match A Subsequence Matching Method in Time-Series Databases Based on Generalized Windows. In Proc. of the 8th ACM SIGMOD Int'l Conf. on Management of data, Madison, Wisconsin, USA, Jun 4-6, 2002, pp:382 - 393.

    [10] Moon Y, Whang K & Loh W.: Duality-based subsequence matching in time-series databases. In Proc. of the 17th Int'l Conf. on Data Engineering, Santa Barbara, California, May 21-24, 2001, pp: 263-272.

  • Similar Research Results (1)
  • Metrics
    views in OpenAIRE
    views in local repository
    downloads in local repository

    The information is available from the following content providers:

    From Number Of Views Number Of Downloads
    Greenwich Academic Literature Archive - IRUS-UK 0 31
Share - Bookmark