Journal of KIISE:Databases (한국정보과학회논문지:데이타베이스)

Korean Institute of Information Scientists and Engineers (한국정보과학회)
권호 표지

Discovering Temporal Relation Rules from Temporal Interval Data

시간간격을 고려한 시간관계 규칙 탐사 기법

  • 이용준 (한국전자통신연구원 우정기술연구부) ;
  • 서성보 (충북대학교 전산학과) ;
  • 류근호 (충북대학교 전기전자컴퓨터공학부) ;
  • 김혜규 (한국전자통신연구원 우정기술연구부)
  • Published : 2001.09.01
Download PDF
⟨ Previous Next ⟩

Abstract

Data mining refers to a set of techniques for discovering implicit and useful knowledge from large database. Many studies on data mining have been pursued and some of them have involved issues of temporal data mining for discovering knowledge from temporal database, such as sequential pattern, similar time sequence, cyclic and temporal association rules, etc. However, all of the works treat problems for discovering temporal pattern from data which are stamped with time points and do not consider problems for discovering knowledge from temporal interval data. For example, there are many examples of temporal interval data that it can discover useful knowledge from. These include patient histories, purchaser histories, web log, and so on. Allen introduces relationships between intervals and operators for reasoning about relations between intervals. We present a new data mining technique that can discover temporal relation rules in temporal interval data by using the Allen's theory. In this paper, we present two new algorithms for discovering algorithm for generating temporal relation rules, discovers rules from temporal interval data. This technique can discover more useful knowledge in compared with conventional data mining techniques.

데이터마이닝은 대용량 데이터베이스에 내재된 유용한 지식을 탐사하는 기술로 정의된다. 데이터마이닝에 대한 연구가 진행되면서 순차 패턴, 유사 시계열 탐사, 시간 연관규칙 탐사 등과 같이 시간 값을 가진 데이터로부터 지식을 탐사하고자 하는 시간 데이터마이닝에 대한 연구가 수행되었다. 그러나 기존 연구는 트랜잭션의 발생 시점만을 가진 데이터를 다루고 있으며 시간 간격을 가진 데이터는 거의 고려하고 있지 않다. 실세계에서는 환자의 병력, 상품 구매 이력, 웹 로그 등과 같은 시간간격을 가진 다양한 데이터가 존재하며 이로부터 여러 유용한 지식을 찾아낼 수 있다. Allen은 시간간격 데이터 사이에 발생할 수 있는 시간 관계와 시간 관계를 구할 수 있는 시간간격 연산자를 정의하였다. 본 논문에서는 Allen의 정의를 기반으로 시간간격 데이터로부터 시간관계 규칙을 효율적으로 탐사하기 위한 새로운 데이터마이닝 기법을 제안하였다. 이 기법은 발생 시점을 가진 시간 데이터를 시간간격 데이터로 요약하여 일반화하는 전처리 알고리즘과 시간간격 데이터로부터 시간관계 규칙을 생성하는 규clr 탐사 알고리즘으로 구성된다. 이 기법은 기존 데이터마이닝 기법에서 찾지 못하는 유용한 시간 규칙을 탐사할 수 있다.

Keywords

References

  1. J. F. Roddick, K. Hornsby and M. Spiliopoulou, Temporal, Spatial and Spatio-Temporal Data Mining and Knowledge Discovery Research Bibliography , http://www.cs.flinders.edu.au, 2000
  2. J. F. Roddick and M. Spiliopoulou, 'Temporal data mining: survey and issues,' Research Report ACRC-99-007, University of South Australia, 1999
  3. J. Allen, 'Maintaining Knowledge about Temporal Intervals,' Comm. Of the ACM, Vol.26, No.11, Nov. 1983 https://doi.org/10.1145/182.358434
  4. J.Y. Lee, K.J. Oh, K.H. Ryu, 'Integration with Spatiotemporal Relationship Operators in SQL,' ACM-GIS, 1998 https://doi.org/10.1145/288692.288724
  5. K.W. Nam, D.H. Kim, K.H. Ryu, 'The Spatiotemporal Relationship Operator,' ITC-CSCC, 1996
  6. R. Agrawal and R. Srikant, 'Mining sequential patterns,' 11th International Conference on Data Engineering, Taipei, Taiwan, Mar. 1995 https://doi.org/10.1109/ICDE.1995.380415
  7. X. Chen and I. Petrounias, 'A framework for temporal data mining,' 9th International Conference on Database and Expert Systems Applications, 1998
  8. C. Rainsford and J. F. Roddick, 'Temporal data mining in information systems: a model,' 7th Australasian Conference on Information Systems, 1996
  9. M. H. Saraee and B. Theodoulidis, 'Knowledge discovery in temporal databases,' IEEE Colloquium on Knowledge Discovery in Databases, 1995
  10. S. Ye and J.A Keane, 'Mining association rules in temporal databases,' International Conference on Systems, Man and Cybernetics, 1998 https://doi.org/10.1109/ICSMC.1998.725086
  11. R. Agrawal and R. Srikant, 'Fast algorithms for mining association rules,' the VLDB Conference, Santiago, Chile, September 1994
  12. R. Srikant and R. Agrawal, 'Mining sequential patterns: generalisations and performance improvements,' In Proc. International Conference on Extending Database Technology, Avignon, France, Springer-Verlag, 1996 https://doi.org/10.1007/BFb0014140
  13. Minons N. Garofalakis, Rajeev Rastogi and Kyuseok Shim, 'SPIRIT: Sequential Pattern Mining with Reqular Expression Constraints,' the VLDB Conference, Edinburgh, Scotland, UK, 1999
  14. H. Mannila and H. Toivonen, 'Discovering generalized episodes using minimal occurrences,' Int'l Conference on Knowledge Discovery in Databases and Data Mining (KDD-96), Portland, USA, Aug. 1996
  15. H. Mannila, H. Toivonen, and A. I. Verkamo, 'Discovery of frequent episodes in event sequences,' Data Mining and Knowledge Discovery, Vol.1, No.3, Nov. 1997 https://doi.org/10.1023/A:1009748302351
  16. G. Berger and A. Tuzhilin, 'Discovering unexpected patterns in temporal data using temporal logic,' Temporal Databases - Research and Practice, Springer-Verlag, 1998
  17. S. Chakrabarti, S. Sarawagi, and B. Dom., 'Mining surprising patterns using temporal description length,' the VLDB Conference, New York City, USA, Aug. 1998
  18. J. Han, G. Dong, and Y. Yin, 'Efficient Mining of Partial Periodic Patterns in Time Series Database,' 15th International Conference on Data Engineering, Sydney, Australia, 1999
  19. R. Agrawal, G. Psaila, E. Wimmers, M. Zaot, 'Querying shapes of histories,' the VLDB Conference, Zurich, Switzerland, Sept. 1995
  20. R. Agrawal, King-Ip Lin, Harpreet S. Sawhney, and Kyuseok Shim, 'Fast similarity search in the presence of noise scaling, and translation in time series databases,' the VLDB Conference, Zurich, Switzerland, Sept. 1995
  21. C. Faloutsos, M. Ranganathan, and Y. Manolopoulos, 'Fast subsequence matching in time-series databases,' the ACM SIGMOD Conference on Management of Data, Minneapolis, USA, May. 1994 https://doi.org/10.1145/191843.191925
  22. Kyuseok Shim, R. Srikant and R. Agrawal, 'High-dimensional similarity joins,' the 13th International Conference on Data Engineering, Brmingham, U.K., Apr. 1997 https://doi.org/10.1109/ICDE.1997.581814
  23. B. Ozden, S. Ramaswamy, and A. Silberschatz, 'Cyclic association rules,' the 14th International Conference on Data Engineering, Orlando, USA, 1998 https://doi.org/10.1109/ICDE.1998.655804
  24. X. Chen, I. Petrounias and H. Heathfield, 'Discovering temporal association rules in temporal databases,' International Workshop on Issues and Applications of Database Technology, 1998
  25. S. Ramaswamy, S. Mahajan and A. Silberschatz, 'On the discovery of interesting patterns in association rules,' the VLDB Conference, New York City, USA, Sept. 1998
  26. J. M. Ale, G. H. Rossi, 'An Approach to Discovering Temporal Association Rules,' SAC'00, Italy, 2000 https://doi.org/10.1145/335603.335770
  27. C. Rainsford, Accommodating Temporal Semantics in Knowledge Discovery and Data Mining, PhD Thesis, University of South Australia, 1998
  28. C. S. Jensen, et al, 'A Glossary of Temporal Database Concepts,' ACM SIGMOD Record, Vol.23, No.1, 1994
  29. R. Snodgrass, 'The Temporal Query Language TQuel,' ACM TODS, Vol.12, No.2, 1987 https://doi.org/10.1145/22952.22956