Detection of unique temporal segments by information theoretic meta-clustering

ABSTRACT

The central challenge in temporal data analysis is to obtain knowledge about its underlying dynamics. In this paper, we address the observation of noisy, stochastic processes and attempt to detect temporal segments that are related to inconsistencies and irregularities in its dynamics. Many conventional anomaly detection approaches detect anomalies based on the distance between patterns, and often provide only limited intuition about the generative process of the anomalies. Meanwhile, model-based approaches have difficulty in identifying a small, clustered set of anomalies.

We propose Information-theoretic Meta-clustering (ITMC), a formalization of model-based clustering principled by the theory of lossy data compression. ITMC identifies a 'unique' cluster whose distribution diverges significantly from the entire dataset. Furthermore, ITMC employs a regularization term derived from the preference for high compression rate, which is critical to the precision of detection.

For empirical evaluation, we apply ITMC to two temporal anomaly detection tasks. Datasets are taken from generative processes involving heterogeneous and inconsistent dynamics. A comparison to baseline methods shows that the proposed algorithm detects segments from irregular states with significantly high precision and recall.

REFERENCES

• 1: Shin Ando, Clustering Needles in a Haystack: An Information Theoretic Analysis of Minority and Outlier Detection, Proceedings of the 2007 Seventh IEEE International Conference on Data Mining, p.13-22, October 28-31, 2007 [doi>10.1109/ICDM.2007.53]
• 2: Shin Ando , Einoshin Suzuki, An Information Theoretic Approach to Detection of Minority Subsets in Database, Proceedings of the Sixth International Conference on Data Mining, p.11-20, December 18-22, 2006 [doi>10.1109/ICDM.2006.19]
• 3: Andrew Arnold , Yan Liu , Naoki Abe, Temporal causal modeling with graphical granger methods, Proceedings of the 13th ACM SIGKDD international conference on Knowledge discovery and data mining, August 12-15, 2007, San Jose, California, USA [doi>10.1145/1281192.1281203]
• 4: Anthony Bagnall , Gareth Janacek, Clustering Time Series with Clipped Data, Machine Learning, v.58 n.2-3, p.151-178, February 2005 [doi>10.1007/s10994-005-5825-6]
• 5: Ziv Bar-Joseph, Analyzing time series gene expression data, Bioinformatics, v.20 n.16, p.2493-2503, November 2004 [doi>10.1093/bioinformatics/bth283]
• 6: Igor V. Cadez , Scott Gaffney , Padhraic Smyth, A general probabilistic framework for clustering individuals and objects, Proceedings of the sixth ACM SIGKDD international conference on Knowledge discovery and data mining, p.140-149, August 20-23, 2000, Boston, Massachusetts, United States [doi>10.1145/347090.347119]
• 7: Xiao-yun Chen , Yan-yan Zhan, Multi-scale anomaly detection algorithm based on infrequent pattern of time series, Journal of Computational and Applied Mathematics, v.214 n.1, p.227-237, April, 2008 [doi>10.1016/j.cam.2007.02.027]
• 8: Dong-Yeon Cho , Kwang-Hyun Cho , Byoung-Tak Zhang, Identification of biochemical networks by S-tree based genetic programming, Bioinformatics, v.22 n.13, p.1631-1640, July 2006 [doi>10.1093/bioinformatics/btl122]
• 9: Tianjiao Chu , Clark Glymour, Search for Additive Nonlinear Time Series Causal Models, The Journal of Machine Learning Research, 9, p.967-991, 6/1/2008
• 10: Marcella Corduas , Domenico Piccolo, Time series clustering and classification by the autoregressive metric, Computational Statistics & Data Analysis, v.52 n.4, p.1860-1872, January, 2008 [doi>10.1016/j.csda.2007.06.001]
• 11: Eamonn Keogh , Jessica Lin , Ada Fu, HOT SAX: Efficiently Finding the Most Unusual Time Series Subsequence, Proceedings of the Fifth IEEE International Conference on Data Mining, p.226-233, November 27-30, 2005 [doi>10.1109/ICDM.2005.79]
• 12: S. Kimura, K. Sonoda, S. Yamane, H. Maeda, K. Matsumura, and M. Hatakeyama. Function approximation approach to the inference of reduced NGnet models of genetic networks. BMC Bioinformatics, 9(1):23, 2008.
• 13: Pedro Pereira Rodrigues , João Gama , Joao Pedroso, Hierarchical Clustering of Time-Series Data Streams, IEEE Transactions on Knowledge and Data Engineering, v.20 n.5, p.615-627, May 2008 [doi>10.1109/TKDE.2007.190727]
• 14: M. Ronen, R. Rosenberg, B. I. Shraiman, and U. Alon. Assigning numbers to the arrows: Parameterizing a gene regulation network by using accurate expression kinetics. Proceedings of the National Academy of Sciences of the United States of America, 99(16):10555--10560, 2002.
• 15: Sam Roweis , Zoubin Ghahramani, A unifying review of linear Gaussian models, Neural Computation, v.11 n.2, p.305-345, Feb. 15, 1999 [doi>10.1162/089976699300016674]
• 16: A. Schliep, A. Schonhuth, and C. Steinhoff. Using hidden Markov models to analyze gene expression time course data. Bioinformatics, 19:i255--263, 2003.
• 17: N. Tishby, F. C. Pereira, and W. Bialek. The Information Bottleneck Method. In Computing Research Repository(CoRR). physics/0004057, 2000.
• 18: Dragomir Yankov , Eamonn Keogh , Umaa Rebbapragada, Disk aware discord discovery: finding unusual time series in terabyte sized datasets, Knowledge and Information Systems, v.17 n.2, p.241-262, November 2008 [doi>10.1007/s10115-008-0131-9]
• 19: Jie Yin , Mohamed Medhat Gaber, Clustering Distributed Time Series in Sensor Networks, Proceedings of the 2008 Eighth IEEE International Conference on Data Mining, p.678-687, December 15-19, 2008 [doi>10.1109/ICDM.2008.58]

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.8 Database applications
          Subjects: Data mining

Additional Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.3 Information Search and Retrieval
          Subjects: Clustering

General Terms:
Algorithms, Design, Experimentation

Keywords:
information-theoretic meta-clustering, temporal data mining