Time-Aware and Space-Aware Data Clustering Techniques
Date Issued
2009
Date
2009
Author(s)
Chu, Yi-Hong
Abstract
Data clustering has been recognized as an important and valuable technique in data mining field. Mostf clustering works adopt density-based approach to discover the clusters, where clusters are regardeds high-density regions in the space. In this dissertation, we explore two important but not well solvedopics in data clustering, i.e. discovering time-aware clusters and discovering space-aware clusters, andevise innovative clustering techniques to deal with these topics.e first devise time-aware clustering techniques. We note that most of previous clustering worksreat all data as one large segment and execute the clustering task over the entire database. However,he characteristics of the data may change over time. Some dense regions (clusters) may only exist inertain time intervals but will not be discovered if taking all data records into account. Thus, discoveringlusters over different time intervals is very important for users to get the interesting patterns hiddenn data. In view of this, we explore in this dissertation a novel problem, called temporal cluster query,o address the cluster discovery in constrained time intervals, where users can specify varying timentervals to discover the clusters. Since the queried time intervals are unknown in advance, the directxtension of previous clustering works would be to delay the cluster discovery until the user querieshe data set, which is, however, inefficient for an interactive query environment. Thus, we also devisen innovative framework, called QEC, to efficiently execute temporal cluster queries.fter that, we devise space-aware clustering techniques. For high-dimensional data, research advancen the literature turns to discover the clusters hidden in subspaces. However, we find that previousubspace clustering works will discover a large amount of subspace clusters but there exists large informationedundancy in the clustering result. In addition, since some data points in a lower-dimensionalluster may not be members of any higher-dimensional cluster, directly removing a cluster having largenformation overlapping with higher-dimensional clusters may cause the loss of information of thoseata points which are contained in this cluster but cannot be found in higher-dimensional clusters. Toemedy this, we devise the NORSC algorithm to automatically discover a succinct collection of subspacelusters while also maintaining the required degree of data coverage.urthermore, we devise a novel subspace clustering model to discover the subspace clusters. Wexplore that previous works are difficult to discover high qualities of the clusters in all subspaces sincehey lack of considering a critical problem, which is that densities vary in different subspace cardinalities.hus, we devise a new subspace clustering model, where different density thresholds wille utilized to discover the dense regions (clusters) in different subspace cardinalities. However, sincehe monotonicity property of the dense regions no longer exists in our subspace clustering model, thepriori-like generate-and-test scheme adopted in most previous works to constrain the searching ofense regions is infeasible in our subspace clustering model. For this challenge, we also devise thelgorithm DENCOS to efficiently discover the clusters based on this novel clustering model.
Subjects
Data Mining
Data Clustering
Time
Space
Subspace Clustering
Type
thesis
File(s)![Thumbnail Image]()
Loading...
Name
ntu-98-F91921022-1.pdf
Size
23.32 KB
Format
Adobe PDF
Checksum
(MD5):67e5ad92934761d86172efd4e8de254f