封閉性多維區間樣式之資料探勘

Abstract

目前，已有許多學者提出探勘頻繁一維區間樣式的方法。但是，在實務上，有許多的資料是多維度的區間，如醫學療程分析中的收縮壓、舒張壓、脈博等等。因此，在本篇論文中，我們提出一個名為「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, such as systolic pressure, diastolic pressure, and pulse in medical treatment analysis, where each index during a certain period of time may be represented by a 1-D interval. Therefore, in this thesis, 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 frequent patterns and generates the patterns in a depth-first search manner. In the mining process, we employ several effective pruning strategies to remove impossible patterns 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.