On exploiting the power of time in data mining

ABSTRACT

We introduce the new paradigm of Change Mining as data mining over a volatile, evolving world with the objective of understanding change. While there is much work on incremental mining and stream mining, both focussing on the adaptation of patterns to a changing data distribution, Change Mining concentrates on understanding the changes themselves. This includes detecting when change occurs in the population under observation, describing the change, predicting change and pro-acting towards it. We identify the main tasks of Change Mining and discuss to what extent they are already present in related research areas. We elaborate on research results that can contribute to these tasks, giving a brief overview of the current state of the art and identifying open areas and challenges for the new research area.

REFERENCES

• 1: Charu C. Aggarwal, On Change Diagnosis in Evolving Data Streams, IEEE Transactions on Knowledge and Data Engineering, v.17 n.5, p.587-600, May 2005 [doi>10.1109/TKDE.2005.78]
• 2: Charu C. Aggarwal , Jiawei Han , Jianyong Wang , Philip S. Yu, A framework for clustering evolving data streams, Proceedings of the 29th international conference on Very large data bases, p.81-92, September 09-12, 2003, Berlin, Germany
• 3: C.C. Aggarwal and P.S. Yu. A Framework for Clustering Massive Text and Categorical Data Streams. In Proceedings of the SIAM conference on Data Mining 2006, April 2006.
• 4: R. Agrawal and G. Psaila. Active data mining. In M. Fayyad, Usama and R. Uthurusamy, editors, Proceedings of the 1st ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pages 3--8, Montreal, Quebec, Canada, 1995. AAAI Press, Menlo Park, CA, USA.
• 5: S. Baron, M. Spiliopoulou, and O. Günther. Efficient monitoring of patterns in data mining environments. In Proc. of 7th East-European Conf. on Advances in Databases and Inf. Sys. (ADBIS'03), LNCS, pages 253--265. Springer, Sept. 2003.
• 6: Ilaria Bartolini , Paolo Ciaccia , Irene Ntoutsi , Marco Patella , Yannis Theodoridis, A unified and flexible framework for comparing simple and complex patterns, Proceedings of the 8th European Conference on Principles and Practice of Knowledge Discovery in Databases, p.496-499, September 20-24, 2004, Pisa, Italy
• 7: Philip Bille, A survey on tree edit distance and related problems, Theoretical Computer Science, v.337 n.1-3, p.217-239, 9 June 2005 [doi>10.1016/j.tcs.2004.12.030]
• 8: M. Boettcher, D. Nauck, D. Ruta, and M. Spott. Towards a framework for change detection in datasets. In Proceedings of the 26th SGAI International Conference on Innovative Techniques and Applications of Artificial Intelligence, pages 115--128. Springer, 2006.
• 9: M. Boettcher, D. Nauck, D. Ruta, and M. Spott. A framework for discovering and analyzing changing customer segments. In Proceedings of the 7th Industrial Conference on Data Mining (ICDM2007), LNAI 4597, pages 255--268. Springer, 2007.
• 10: L. Breiman. The heuristics of instability in model selection. Annals of Statistics, 24:2350--2383, 1996.
• 11: F. Cao, M. Ester, W. Qian, and A. Zhou. Density-Based Clustering over an Evolving Data Stream with Noise. In Proc. SIAM Conf. Data Mining, 2006.
• 12: Soumen Chakrabarti , Sunita Sarawagi , Byron Dom, Mining Surprising Patterns Using Temporal Description Length, Proceedings of the 24rd International Conference on Very Large Data Bases, p.606-617, August 24-27, 1998
• 13: Soumen Chakrabarti , Sunita Sarawagi , Byron Dom, Mining Surprising Patterns Using Temporal Description Length, Proceedings of the 24rd International Conference on Very Large Data Bases, p.606-617, August 24-27, 1998
• 14: M.-C. Chen, A.-L. Chiu, and H.-H. Chang. Mining changes in customer behavior in retail marketing. Expert Systems with Applications, 28(4):773--781, 2005.
• 15: G. Dong, J. Han, and L. Lakshmanan. Online mining of changes from data streams - research problems and preliminary results. In Proceedings of the ACM SIGMOD Workshop on Management and Processing of Data Streams, June 2003.
• 16: Guozhu Dong , Jinyan Li, Efficient mining of emerging patterns: discovering trends and differences, Proceedings of the fifth ACM SIGKDD international conference on Knowledge discovery and data mining, p.43-52, August 15-18, 1999, San Diego, California, United States [doi>10.1145/312129.312191]
• 17: Martin Ester , Hans-Peter Kriegel , Jörg Sander , Michael Wimmer , Xiaowei Xu, Incremental Clustering for Mining in a Data Warehousing Environment, Proceedings of the 24rd International Conference on Very Large Data Bases, p.323-333, August 24-27, 1998
• 18: Venkatesh Ganti , Johannes Gehrke , Raghu Ramakrishnan, A framework for measuring changes in data characteristics, Proceedings of the eighteenth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.126-137, May 31-June 03, 1999, Philadelphia, Pennsylvania, United States [doi>10.1145/303976.303989]
• 19: Venkatesh Ganti , Johannes Gehrke , Raghu Ramakrishnan, CACTUS—clustering categorical data using summaries, Proceedings of the fifth ACM SIGKDD international conference on Knowledge discovery and data mining, p.73-83, August 15-18, 1999, San Diego, California, United States [doi>10.1145/312129.312201]
• 20: DEMON: Mining and Monitoring Evolving Data, Proceedings of the 16th International Conference on Data Engineering, p.439, February 28-March 03, 2000
• 21: Valery Guralnik , Jaideep Srivastava, Event detection from time series data, Proceedings of the fifth ACM SIGKDD international conference on Knowledge discovery and data mining, p.33-42, August 15-18, 1999, San Diego, California, United States [doi>10.1145/312129.312190]
• 22: Frank Höppner , Mirko Böttcher, Matching Partitions over Time to Reliably Capture Local Clusters in Noisy Domains, Proceedings of the 11th European conference on Principles and Practice of Knowledge Discovery in Databases, September 17-21, 2007, Warsaw, Poland [doi>10.1007/978-3-540-74976-9_49]
• 23: P. Kalnis, N. Mamoulis, and S. Bakiras. On Discovering Moving Clusters in Spatio-temporal Data. In Proc. of 9th Int. Symposium on Advances in Spatial and Temporal Databases (SSTD'2005), number 3633 in LNCS, pages 364--381, Angra dos Reis, Brazil, Aug. 2005. Springer.
• 24: Eamonn Keogh , Stefano Lonardi , Bill 'Yuan-chi' Chiu, Finding surprising patterns in a time series database in linear time and space, Proceedings of the eighth ACM SIGKDD international conference on Knowledge discovery and data mining, July 23-26, 2002, Edmonton, Alberta, Canada [doi>10.1145/775047.775128]
• 25: J.K. Kim, H.S. Song, T.S. Kim, and H.K. Kim. Detecting the change of customer behavior based on decision tree analysis. Expert Systems, 22(4):193--205, 2005.
• 26: Ruey-Hsia Li , Geneva G. Belford, Instability of decision tree classification algorithms, Proceedings of the eighth ACM SIGKDD international conference on Knowledge discovery and data mining, July 23-26, 2002, Edmonton, Alberta, Canada [doi>10.1145/775047.775131]
• 27: Bing Liu , Wynne Hsu , Heng-Siew Han , Yiyuan Xia, Mining Changes for Real-Life Applications, Proceedings of the Second International Conference on Data Warehousing and Knowledge Discovery, p.337-346, September 04-06, 2000
• 28: Bing Liu , Wynne Hsu , Yiming Ma, Discovering the set of fundamental rule changes, Proceedings of the seventh ACM SIGKDD international conference on Knowledge discovery and data mining, p.335-340, August 26-29, 2001, San Francisco, California [doi>10.1145/502512.502561]
• 29: Bing Liu , Yiming Ma , Ronnie Lee, Analyzing the Interestingness of Association Rules from the Temporal Dimension, Proceedings of the 2001 IEEE International Conference on Data Mining, p.377-384, November 29-December 02, 2001
• 30: Bing Liu , Alexander Tuzhilin, Managing large collections of data mining models, Communications of the ACM, v.51 n.2, p.85-89, February 2008 [doi>10.1145/1314215.1314230]
• 31: Junshui Ma , Simon Perkins, Online novelty detection on temporal sequences, Proceedings of the ninth ACM SIGKDD international conference on Knowledge discovery and data mining, August 24-27, 2003, Washington, D.C. [doi>10.1145/956750.956828]
• 32: A. Maddalena and B. Catania. Towards an interoperable solution for pattern management. In 3rd Int. Workshop on Database Interoperability INTERDB'07 (in conjunction with VLDB'07), Vienna, Austria, Sept. 2007.
• 33: Qiaozhu Mei , ChengXiang Zhai, Discovering evolutionary theme patterns from text: an exploration of temporal text mining, Proceedings of the eleventh ACM SIGKDD international conference on Knowledge discovery in data mining, August 21-24, 2005, Chicago, Illinois, USA [doi>10.1145/1081870.1081895]
• 34: Olfa Nasraoui , Cesar Cardona Uribe , Carlos Rojas Coronel , Fabio Gonzalez, TECNO-STREAMS: Tracking Evolving Clusters in Noisy Data Streams with a Scalable Immune System Learning Model, Proceedings of the Third IEEE International Conference on Data Mining, p.235, November 19-22, 2003
• 35: Michal Pechoucek , Olga Stepánková , Petr Miksovský, Maintenance of Discovered Knowledge, Proceedings of the Third European Conference on Principles of Data Mining and Knowledge Discovery, p.476-483, September 15-18, 1999
• 36: Edwina L. Rissland , M. Timur Friedman, Detecting change in legal concepts, Proceedings of the 5th international conference on Artificial intelligence and law, p.127-136, May 21-24, 1995, College Park, Maryland, United States [doi>10.1145/222092.222209]
• 37: J.F. Roddick, M. Spiliopoulou, D. Lister, and A. Ceglar. Higher order mining. submitted for publication, 2007.
• 38: R. Schult and M. Spiliopoulou. Discovering emerging topics in unlabelled text collections. In Proc. of AD-BIS'2006, Thessaloniki, Greece, Sept. 2006. Springer.
• 39: S. Schulz, M. Spiliopoulou, and R. Schult. Topic and cluster evolution over noisy document streams. In F. Masseglia, P. Poncelet, and M. Teisseire, editors, Data Mining Patterns: New Methods and Applications. Idea Group, 2007.
• 40: Myra Spiliopoulou , Irene Ntoutsi , Yannis Theodoridis , Rene Schult, MONIC: modeling and monitoring cluster transitions, Proceedings of the 12th ACM SIGKDD international conference on Knowledge discovery and data mining, August 20-23, 2006, Philadelphia, PA, USA [doi>10.1145/1150402.1150491]
• 41: Michalis Vazirgiannis , Maria Halkidi , Dimitrios Gunopulos, Uncertainty Handling and Quality Assesment in Data Mining, Springer-Verlag New York, Inc., Secaucus, NJ, 2003
• 42: Hui Yang , Srinivasan Parthasarathy , Sameep Mehta, A generalized framework for mining spatio-temporal patterns in scientific data, Proceedings of the eleventh ACM SIGKDD international conference on Knowledge discovery in data mining, August 21-24, 2005, Chicago, Illinois, USA [doi>10.1145/1081870.1081962]
• 43: K. Zhang, J.T.L. Wang, and D. Shasha. On the editing distance between undirected acyclic graphs and related problems. In Z. Galil and E. Ukkonen, editors, Proceedings of the 6th Annual Symposium on Combinatorial Pattern Matching, pages 395--407. Springer-Verlag, Berlin, 1995.
• 44: Xiuzhen Zhang , Guozu Dong , Ramamohanarao Kotagiri, Exploring constraints to efficiently mine emerging patterns from large high-dimensional datasets, Proceedings of the sixth ACM SIGKDD international conference on Knowledge discovery and data mining, p.310-314, August 20-23, 2000, Boston, Massachusetts, United States [doi>10.1145/347090.347158]
• 45: Aoying Zhou , Feng Cao , Weining Qian , Cheqing Jin, Tracking clusters in evolving data streams over sliding windows, Knowledge and Information Systems, v.15 n.2, p.181-214, May 2008 [doi>10.1007/s10115-007-0070-x]

INDEX TERMS

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

Additional Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.4 Knowledge Representation Formalisms and Methods

General Terms:
Algorithms, Design, Experimentation, Measurement, Performance, Theory