Search

In this paper, we first study an important but unsolved dilemma in the literature of subspace clustering, which is referred to as ldquoinformation overlapping-data coveragerdquo challenge. Current solutions of subspace clustering usually invoke a grid-based apriori-like procedure to identify dense regions and construct subspace clusters afterward. Due to the nature of monotonicity property in apriori-like procedures, it is inherent that if a region is identified as dense, all its projected regions are also identified as dense, causing overlapping/redundant clustering information to be inevitably reported to users when generating clusters from such highly correlated regions. However, naive methods to filter redundant clusters will incur a challenging problem in the other side of the dilemma, called the ldquodata coveragerdquo issue. Note that two clusters may have highly correlated dense regions but their data members could be highly different to each other. Arbitrarily removing one of them may lose the coverage of data with clustering information, thus likely reporting an incomplete and biased clustering result. In this paper, therefore, we further propose an innovative algorithm, called "nonredundant subspace cluster miningrdquo (NORSC), to efficiently discover a succinct collection of subspace clusters while also maintaining the required degree of data coverage. NORSC not only avoids generating the redundant clusters with most of the contained data covered by higher dimensional clusters to resolve the information overlapping problem but also limits the information loss to cope with the data coverage problem. As shown by our experimental results, NORSC is very effective in identifying a concise and small set of subspace clusters, while incurring time complexity in orders of magnitude better than that of previous works.

In this paper, we study the quality issue of subspace clusters, which is an important but unsolved challenge in the literature of subspace clustering. After binning the data set into disjoint grids/regions, current solutions of subspace clustering usually invoke a grid-based apriori-like procedure to efficiently identify dense regions level by level according to the monotonic property in so defined subspace regions. A cluster in a subspace is intuitively considered as a set of dense regions that each one is connected to another dense region in the cluster. The measure of what is a dense region is successfully studied in recent years. However, the rigid definition of subspace clusters as connected regions still needs further justification in terms of the two principal measures of clustering quality, i.e., the intra-cluster similarity and the inter-cluster dissimilarity. A true cluster is likely to be separated into two or more clusters, whereas many true clusters may be merged into a fat cluster. In this paper, we propose an innovative algorithm, called the QASC algorithm (standing for Quality-Aware Subspace Clustering) to effectively discover accurate clusters. The QASC algorithm is devised as a general solution to partition dense regions into clusters and can be easily integrated into most of grid-based subspace clustering algorithms. By conducting on extensive synthetic data sets, the experimental results reveal that QASC is effective in identifying true subspace clusters.

In this paper, we explore a new problem of ”temporal dense region query” to discover the dense regions in the constrainted time intervals which can be separated or not. A Querying tEmporal Dense Region framework (abbreviated as QED) proposed to deal with this problem consists of two phases: (1) an offline maintaining phase, to maintain the statistics of data by constructing a number of summarized structures, RF-trees; (2) an online query processing phase, to provide an efficient algorithm to execute queries on the RF-trees. The QED framework has the advantage that by using the summarized structures, RF-trees, the queries can be executed efficiently without accessing the raw data. In addition, a number of RF-trees can be merged with one another efficiently such that the queries will be executed efficiently on the combined RF-tree. As validated by our empirical studies, the QED framework performs very efficiently while producing the results of high quality.