Mining Closed Multi-Dimensional Interval Patterns

探勘封閉性多維度區間樣式

10.6382/JIM.201201.0161

李瑞庭(Anthony J. T. Lee)；楊富丞(Fu-Chen Yang)；李偉誠(Wei-Cheng Lee)

多維區間樣式 ； 一維區間樣式 ； 頻繁樣式 ； 封閉性樣式 ； 資料探勘 ； multi-dimension interval pattern ； 1-dimension interval pattern ； frequent pattern ； closed pattern ； data mining

資訊管理學報

19卷1期（2012 / 01 / 01）

161 - 184

英文

目前，已有許多學者提出探勘頻繁一維區間樣式的方法。但是，在實務上有許多應用包括多維度區間的資料。因此，在本篇論文中，我們提出「MIAMI」演算法，它利用頻繁樣式樹，以深度優先法遞迴產生所有的封閉性多維度區間樣式。在探勘的過程中，我們設計三個有效的修剪策略，以刪除不可能的候選樣式，以及使用封閉性測試移除非封閉性樣式。實驗結果顯示，MIAMI 演算法比改良式Apriori 演算法更有效率，也更具擴充性。

Many methods have been proposed to find frequent one-dimensional (1-D) interval patterns, where each event in the database is realized by a 1-D interval. However, the events in many applications are in nature realized by multi-dimensional intervals. Therefore, in this paper, we propose an efficient algorithm, called MIAMI, to mine closed multi-dimensional interval patterns from a database. The MIAMI algorithm employs a pattern tree to enumerate all closed patterns in a depth-first search manner. In the mining process, we devisethree effective pruning strategies to remove impossible candidates and perform a closure checking scheme to eliminate non-closed patterns. The experimental results show that the MIAMI algorithm is more efficient and scalable than the modified Apriori algorithm.

1. Agrawal, R.,Srikant, R.(1994).Fast algorithms for mining association rules.Proceedings of the International Conference on Very Large Data Bases,1215,487-499.
2. Agrawal, R.,Srikant, R.(1995).Mining sequential patterns.Proceedings of the International Conference on Data Engineering,Taipei, Taiwan:
3. Allen, J. F.(1983).Maintaining knowledge about temporal intervals.Communications of the ACM,26(11),832-843.
4. de Amo, S.,Junior, W. P.,Giacometti, A.(2008).MILPRIT*: A constraint-based algorithm for mining temporal relational patterns.International Journal of Data Warehousing and Mining,4(4),42-61.
5. Guyer, T.,Quiniou, R.(2008).Mining temporal patterns with quantitative intervals.Proceedings of International Conference on Data Mining
6. Han, J.,Pei, J.,Mortazavi-Asl, B.,Chen, Q.,Dayal, U.,Hsu, M. C.(2000).FreeSpan: Frequent pattern-projected sequential pattern mining.Proceedings of International Conference on Knowledge Discovery and Data Mining,Boston, USA:
7. Han, J.,Pei, J.,Yin, Y.(2000).Mining frequent patterns without candidate generation.Proceedings of the ACM SIGMOD International Conference on Management of Data,29(2),1-12.
8. Höppner, F.(2001).Learning temporal rules from state sequences.Proceedings of International Joint Conferences on Artificial Intelligence Workshop on Learning from Temporal and Spatial Data,Seattle, USA:
9. Kam, P.-S.,Fu, A. W.-C.(2000).Discovering temporal patterns for interval-basedevents.Proceedings of Second International Conference on Data Warehousingand Knowledge Discovery,London, UK:
10. Kong, X.,Wei, Q.,Chen, G.(2010).An approach to discovering multi-temporal patterns and its application to financial databases.Information Sciences,180(6),873-885.
11. Lee, Y. J.,Lee, J. W.,Chai, D. J.,Hwang, B. H.,Ryu, K. H.(2009).Mining temporal interval relational rules from temporal data.The Journal of Systems and Software,82(1),155-167.
12. Papapetrou, P.,Kollios, G.,Sclaroff, S.,Gunopulos, D.(2009).Mining frequent arrangements of temporal intervals.Knowledge and Information Systems,21(2),133-171.
13. Patel, D.,Hsu, W.,Lee, M.(2008).Mining relationships among interval-based events for classification.Proceedings of the ACM SIGMOD International Conference on Management of Data,Vancouver, Canada:
14. Pei, J.,Han, J.,Mao, R.(2000).CLOSET: An efficient algorithm for mining frequent closed itemsets.Proceedings of the 5th ACM-SIGMOD Workshop on Research Issues in Data Mining and Knowledge Discovery,Dallas, USA:
15. Pei, J.,Han, J.,Mortazavi-Asl, B.,Pinto, H.(2001).PrefixSpan: Mining sequential patterns efficiently by prefix-projected pattern growth.Proceedings of the 17th International Conference on Data Engineering,Heidelberg, Germany:
16. Winarko, E.,Roddick, J. F.(2007).ARMADA-An algorithm for discovering richer relative temporal association rules from interval-based data.Data and Knowledge Engineering,63(1),76-90.
17. Wu, S.-Y.,Chen, Y.-L.(2007).Mining nonambiguoustemporalpatterns for interval-based events.IEEE Transactions on Knowledge and Data Engineering,19(6),742-758.
18. Wu, S.-Y.,Chen, Y.-L.(2009).Discovering hybrid temporal patterns from sequences consisting of point- and interval-based events.Data and Knowledge Engineering,68(11),1309-1330.
19. Zaki, M. J.(2001).SPADE: An efficient algorithm for mining frequent sequences.Machine Learning,42(1-2),31-60.
20. Zaki, M. J.,Hsiao, C.-J.(2005).Efficient algorithms for mining closed itemsets and their lattice structure.IEEE Transactions on Knowledge and Data Engineering,17(4),462-478.

1. 楊亞澄、翁政雄、胡雅涵(2016)。運用關聯規則及改變探勘技術於防火牆政策規則優化。資訊管理學報，23(3)，277-304。