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

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）的樣式變化探勘等問題。