具時間和空間感知之資料叢集技術

Abstract

資料叢集分析是資料探勘領域中一項非常重要的技術。很多資料叢集演算法採用以密度為 考量的方式去挖掘資料叢集:它們將資料叢集視為空間中密度很高的區域。然而，我們發現 了兩個很重要但尚未被充分解決的問題: 如何挖掘隱藏在時間裡的資料叢集，如何挖掘隱 藏在空間裡的資料叢集。我們將依序探討這兩個問題並設計相關的資料叢集技術。 首先，我們研究具時間感知之資料叢集技術。我們發現之前的資料叢集演算法大多是 在全部的資料下找尋資料叢集，然而資料的特性會隨著時間做改變，有些資料叢集只會存 在於某個時間區間裡，而當我們是在整體資料下挖掘資料叢集時這些隱藏在時間區間裡的 資料叢集反而不會被挖掘出來。因此，能讓使用者可以指定不同的時間區間來挖掘資料叢 集是非常重要的。有鑒於此，我們設計了Temporal cluster query 這個問題來讓使用者在不 同時間區間找尋資料叢集。然而，因為欲挖掘資料叢集的時段無法事先知道，若要使用之 前的演算法就只能等到使用者提出查詢後再執行這些演算法，這樣的方法非常沒效率且不 適合即時互動式的查詢環境。因此，我們再提出了一個新穎的QEC 架構來有效率的執行 Temporal cluster query。 接下來，我們研究具空間感知之資料叢集技術。對於高維度資料，歷史文獻中的研究 轉而去找隱藏在子空間的資料叢集。然而我們發現到之前的子空間叢集挖掘演算法會找出 大量的子空間資料叢集，但這些叢集有很嚴重的資訊重複的問題。而且因為有些存在於低 維度叢集的資料並沒有被包含在任何高維度資料叢集內，因此若直接刪除那些與高維度叢 集有很大資訊重複的低維度叢集，將可能導致遺失了那些存在於被刪除的叢集中但卻沒有 被包含在高維度叢集中的資料的資訊。為了解決這個問題，我們提出了NORSC演算法來自 動的找出一組精簡的子空間資料叢集但同時又可以維持一定的資料涵蓋程度。 最後，我們更進一步的提出一個新的子空間資料叢集探勘模型。因為我們發現到之前 的子空間叢集挖掘演算法對於不同子空間維度下的資料叢集無法同時得到很好的品質，主 要的原因是因為他們忽略了一個很重要的現象:不同子空間維度裡的資料叢集會有不同的 密度。因此我們設計了一個新的子空間資料叢集探勘模型，我們將採用不同的密度參數來 找不同子空間維度裡的資料叢集。但是這新模型定義下的資料叢集將不再滿足單一性特性 (Monotonicity property)，因此我們無法直接利用之前演算法根據單一性特性所設計的類 Apriori技術來找新模性定義下的資料叢集。有鑒於此，我們更進一步的設計了DENCOS演 算法來有效率的挖掘新模型定義下的資料叢集。

Data clustering has been recognized as an important and valuable technique in data mining field. Most of clustering works adopt density-based approach to discover the clusters, where clusters are regarded as high-density regions in the space. In this dissertation, we explore two important but not well solved topics in data clustering, i.e. discovering time-aware clusters and discovering space-aware clusters, and devise innovative clustering techniques to deal with these topics. We first devise time-aware clustering techniques. We note that most of previous clustering works treat all data as one large segment and execute the clustering task over the entire database. However, the characteristics of the data may change over time. Some dense regions (clusters) may only exist in certain time intervals but will not be discovered if taking all data records into account. Thus, discovering clusters over different time intervals is very important for users to get the interesting patterns hidden in data. In view of this, we explore in this dissertation a novel problem, called temporal cluster query, to address the cluster discovery in constrained time intervals, where users can specify varying time intervals to discover the clusters. Since the queried time intervals are unknown in advance, the direct extension of previous clustering works would be to delay the cluster discovery until the user queries the data set, which is, however, inefficient for an interactive query environment. Thus, we also devise an innovative framework, called QEC, to efficiently execute temporal cluster queries. After that, we devise space-aware clustering techniques. For high-dimensional data, research advance in the literature turns to discover the clusters hidden in subspaces. However, we find that previous subspace clustering works will discover a large amount of subspace clusters but there exists large information redundancy in the clustering result. In addition, since some data points in a lower-dimensional cluster may not be members of any higher-dimensional cluster, directly removing a cluster having large information overlapping with higher-dimensional clusters may cause the loss of information of those data points which are contained in this cluster but cannot be found in higher-dimensional clusters. To remedy this, we devise the NORSC algorithm to automatically discover a succinct collection of subspace clusters while also maintaining the required degree of data coverage. Furthermore, we devise a novel subspace clustering model to discover the subspace clusters. We explore that previous works are difficult to discover high qualities of the clusters in all subspaces since they lack of considering a critical problem, which is that densities vary in different subspace cardinalities. Thus, we devise a new subspace clustering model, where different density thresholds will be utilized to discover the dense regions (clusters) in different subspace cardinalities. However, since the monotonicity property of the dense regions no longer exists in our subspace clustering model, the Apriori-like generate-and-test scheme adopted in most previous works to constrain the searching of dense regions is infeasible in our subspace clustering model. For this challenge, we also devise the algorithm DENCOS to efficiently discover the clusters based on this novel clustering model.