資料串流上複雜樣式探勘、互動式探勘與串流變化探勘之研究

Abstract

（一）計畫中文摘要 近來由於資料串流本身獨特的資料特性，再加上有許多可產生串流式資料的實 務應用的大量崛起，使得資料串流探勘成為資料探勘研究中的一個新興的熱門研究 方向。樣式探勘是資料串流探勘中一個核心技術，為了滿足不同應用的實際需求， 並探討與解決現存資料串流探勘技術所遇到的問題與技術瓶頸；本計劃將研究資料 串流探勘的核心問題－樣式探勘，其內容分述如下： 1. 複雜頻繁樣式探勘 目前資料串流探勘中的一個極度熱門的研究方向是頻繁項目集合（frequent itemset）探勘；但是到目前為止，此類的研究多著重於在標的物視窗模型（landmark window）、滑動視窗模型（sliding window）以及衰變視窗模型（decayed window）中 漸進式地探勘（incremental mining）頻繁資料項目（frequent items）或是頻繁資料項 目集（frequent itemsets）。而對於封閉頻繁項目集合（closed frequent itemsets）與最 大頻繁項目集合（maximal frequent itemsets）以及內含複雜結構的資料串流（如項目 集合序列型資料（itemset-sequence data streams）以及XML 資料串流）的研究著墨不 多；因此，本計劃將分三年依序分別於標的物視窗模型、滑動視窗模型以及衰變視 窗模型中，探討封閉頻繁項目集合探勘與最大頻繁項目集合探勘、循序樣式 （sequential pattern mining）探勘、頻繁樹狀結構（frequent tree structure mining）以 及頻繁圖形結構探勘（frequent graph structure mining）等問題。 2. 互動式探勘 在上述的資料串流的頻繁樣式探勘中，其目的是在目前已出現過的串流資料 中，發掘出出現比例高出某些特定門檻值（thresholds）的頻繁樣式，但是要選擇一 個適合的最小支持度門檻值是一件很困難的事，因為資料串流具有快速改變更新其 資料樣式分佈的特性，所以設計一個能讓使用者在探勘過程中可以任意去修改最小 支持度門檻值的單次掃瞄演算法就變得十分的重要了，此類型的樣式探勘稱為資料 串流的互動式探勘（interactive mining）。 除此之外，除了讓使用者自行制定最小支持度門檻值來執行樣式探勘之外，還 有一種方式可以讓使用者在不具有專業知識（即根據不同的資料分佈來決定使用何 種最小支持度門檻值的大小），這種方式就是在資料串流中只輸出前K 個的（Top-K） 頻繁樣式（此時，使用者只需要選擇他想要檢視多少組探勘出來的結果；這對使用 者來說是一件較為容易的事）。因此，本計劃將分三年依序分別於標的物視窗模型、 滑動視窗模型以及衰變視窗模型中，探討頻繁樣式的互動式探勘以及前K 個頻繁樣 式等問題。 3. 串流變化探勘 在資料串流探勘中除了頻繁樣式的探勘之外，資料串流變化的探勘也是一個極 為重要的新興研究方向。一般來說，除了資料串流本身的資料會不定時產生劇烈變 化，又可稱為激變（burst）特性，之外，樣式的變化可能是一個更重要且更具挑戰 性的研究題目。舉例說明，使用者可能會想要知道下列查詢的結果：「跟過去的資料串流相比較，目前的串流資料有哪些不同的特性呢？」或者是「從串流資料一開始 產生之後到現在為止，有哪些樣式是長期穩定出現的樣式呢？」。所以，在與傳統的 靜態資料庫相比較，資料串流因為具有不定期更新以及快速變化的特性，所以資料 串流的變化探勘（online mining of changes）可以被稱為是因為資料串流本身的特性 所衍生出來的一個新興的重要研究方向。有鑑於此，本計劃的第三個研究主題即在 於研究資料串流的變化探勘的相關技術，並分三年依序探討資料串流的激變偵測 （burst detection）、單一資料串流（single data stream）的樣式變化探勘、多資料串流 （multiple data streams）的樣式變化探勘等問題。

Nowadays, many data-intensive applications like tele-communication networks, power sensor networks, traffic sensor networks, generate large amount of streaming data continuously in real time. The unique characteristic of data streams is 「you only get one look」. Due to the unique characteristic of streaming data, this project will focus on the core technique of mining data streams: pattern discovery, and develop the key techniques , which are described respectively as follows. 1. Conplex Pattern Mining of Data Streams One of the most important research topics of data stream mining is the single-pass mining of frequent itemsets from data streams. Three popular streaming window models are used in this problem, i.e., landmark window model, sliding window model, and decayed window model. However, there are less work on the problems of mining closed frequent itemsets, maximal frequent itemsets, itemset-based sequential patterns, and frequent tree-structure patterns over landmark windows, sliding widnows, and decayed windows. As a result, this project will respectively study the issues of closed frequent itemsets, maximal frequent itemsets, itemset-based sequential patterns, and frequent tree structure patterns of complex pattern mining in three years. 2. Interactive Mining of Data Streams Due to the fast changing characteristic of data streams, dynamic set-up of a user-specified minimum support threshold is an important issue in the process of mining data streams. The technique is called interactive mining. Another technique, called Top-K pattern mining, can help the users find the userful patterns from data streams. In Top-K pattern mining, users specify the number of patterns they want, rather than specify the value of minimum support threshold. As a result, this project will respectively study the issues of interactive mining and Top-K pattern mining of complex patterns in three years. 3. Online Mining of Changes of Data Streams One of the key reseach topics in mining data streams is online mining of changes. With data streams, people are often interested in mining queries like 「compared to the history, what are the distinct features of the current status?」 and 「what are the relatively stable factors over time」 Clearly, to answer the above queries, we have to examine the changes of data streams. As a result, the project will respectively study the issues of burst detection, online mining of changes of single data stream, and online mining of changes of multiple data streams in three years.