Automatic subspace clustering of high dimensional data for data mining applications

Rakesh AgrawalJohannes GehrkeDimitrios GunopulosPrabhakar Raghavan

article1998SIGMOD2,924 citations

Introduces CLIQUE, a foundational density-based subspace clustering algorithm that automatically finds clusters embedded in high-dimensional data subspaces and outputs interpretable DNF descriptions with linear scalability.

Listen

CLIQUE is a new clustering algorithm developed to meet the specific needs of data mining on high-dimensional datasets, where clusters often exist only in subspaces formed by subsets of attributes rather than in the full space. Traditional partitional and hierarchical methods, along with recent scalable techniques such as BIRCH and DBSCAN, typically examine all dimensions at once; this approach fails when many attributes contain noise or uniform values, because the average point density becomes too low and distance functions lose effectiveness. The work therefore set out to create an automatic procedure that identifies dense regions in the most relevant subspaces, produces concise and interpretable descriptions of those regions, scales to large data volumes, remains insensitive to input order, and makes no assumptions about the underlying data distribution.

The algorithm proceeds in three main stages. It first partitions each dimension into equal-length intervals and uses a bottom-up, level-wise search—modeled on the monotonicity property that any dense unit in k dimensions must project to dense units in every (k–1)-dimensional subspace—to locate candidate dense units without enumerating every possible subspace. An MDL-based pruning step then discards subspaces whose total coverage of data points falls below an automatically chosen threshold, greatly reducing the number of units examined. Connected dense units within each retained subspace are grouped into clusters via depth-first search, and each cluster is covered by the smallest number of maximal axis-parallel rectangles whose union yields a compact DNF expression.

Experiments on synthetic data with up to 500 000 records and 100 dimensions demonstrated linear scaling with database size and acceptable growth with dimensionality once pruning is applied; the method recovered all embedded clusters while BIRCH and DBSCAN missed most of them once the ambient dimensionality exceeded roughly ten. On four real datasets from insurance, retail, and banking domains, CLIQUE consistently surfaced meaningful clusters lying in subspaces whose dimensionality was far lower than that of the original tables. These results indicate that automatic subspace clustering can be performed at practical cost and with higher accuracy than full-space methods when the data contain the mixture of relevant and irrelevant attributes typical of modern analytical repositories.

The principal limitations are that running time remains exponential in the highest dimensionality of any dense unit and that aggressive MDL pruning can, in principle, discard a subspace containing a cluster. Parameter selection for grid granularity and density threshold still requires user judgment, although the authors note that modest ranges usually suffice. Overall is high for the reported synthetic and real-data regimes, but practitioners should verify results on new domains with a modest pilot before relying on the output for downstream decisions.

Next steps supported by the paper include developing quantitative criteria for ranking subspaces by cluster quality, adding system-level assistance for parameter choice, and exploring maximal-itemset techniques to locate only the highest-dimensional dense units without enumerating all their projections. These extensions would further lower the barrier to routine use of subspace clustering in operational data-mining pipelines.

IBM University of Wisconsin Madison data mining techniques high dimensional data association rules Automatic subspace clustering high-dimensional data cluster descriptions

Agrawal et al (1998).pdf

Paper: BIRCH: an efficient data clustering method for very large databases, Tian Zhang et al. (1996). BIRCH provides foundational techniques for data partitioning and memory-efficient cluster summaries that directly preceded scalable subspace methods like CLIQUE.
Paper: Mining association rules between sets of items in large databases, R. Agrawal et al. (1993). Association rule mining introduces the underlying frequent-itemset discovery principles that CLIQUE adapts to identify dense clusters in high-dimensional subspaces.

Paper: Robust Recovery of Subspace Structures by Low-Rank Representation, Guangcan Liu et al. (2010). Low-rank representation extends subspace analysis beyond grid-based methods by using convex optimization to recover clean linear subspaces from corrupted high-dimensional data.
Paper: Unsupervised Deep Embedding for Clustering Analysis, Junyuan Xie et al. (2015). Deep embedded clustering advances beyond classical subspace and partitioning algorithms by jointly learning non-linear feature representations and cluster assignments via neural networks.

Cover for Automatic subspace clustering of high dimensional data for data mining applications

Abstract

Data mining applications place special requirements on clustering algorithms including: the ability to find clusters embedded in subspaces of high dimensional data, scalability, end-user comprehensibility of the results, non-presumption of any canonical data distribution, and insensitivity to the order of input records. We present CLIQUE, a clustering algorithm that satisfies each of these requirements. CLIQUE identifies dense clusters in subspaces of maximum dimensionality. It generates cluster descriptions in the form of DNF expressions that are minimized for ease of comprehension. It produces identical results irrespective of the order in which input records are presented and does not presume any specific mathematical form for data distribution. Through experiments, we show that CLIQUE efficiently finds accurate clusters in large high dimensional datasets.

Topics

data mining techniques high dimensional data association rules knowledge discovery in database

Keywords

Automatic subspace clustering high-dimensional data cluster descriptions sparse regions large spatial databases

1.1 Desiderata from the data mining perspective
1 Introduction
1.2 Contributions and layout of the paper
2 Subspace Clustering
2.1 Problem Statement
3 Algorithms
3.1 Identification of subspaces that contain clusters
3.1.1 A bottom-up algorithm to find dense units
3.1.2 Making the bottom-up algorithm faster
3.2 Finding clusters
3.3 Generating minimal cluster descriptions
3.3.1 Covering with maximal regions
3.3.2 Minimal Cover
4 Performance Experiments
4.1 Synthetic data generation
4.2 Synthetic data results
4.3 Comparisons with BIRCH, DBSCAN and SVD
4.4 Real data results
5 Conclusions
6 Appendix: Dimensionality reduction
References

Knowls

Knowl 1 — Subspace Clustering and Density-Grid Problem Formulation
definition
Let $\mathcal{A} = \{A_1, A_2, \dots, A_d\}$ be a set of bounded, totally ordered numerical domains defining a $d$ -dimensional space $\mathcal{S} = A_1 \times A_2 \times \dots \times A_d$ . An input dataset $V = \{v_1, v_2, \dots, v_m\}$ consists of $m$ points in $\mathcal{S}$ .

The space $\mathcal{S}$ is partitioned into non-overlapping rectangular units by dividing each dimension $A_j$ into $\xi$ intervals of equal length. A unit $u$ in $\mathcal{S}$ is the intersection of one right-open interval per dimension: $u = \{u_1, \dots, u_d\}$ where $u_j = [l_j, h_j) \subset A_j$ . A data point $v = (v_1, \dots, v_d)$ lies in $u$ if $l_j \le v_j < h_j$ for all $j \in \{1, \dots, d\}$ .

The selectivity of a unit $u$ , denoted $\text{selectivity}(u)$ , is the fraction of data points in $V$ contained in $u$ . For a given density threshold $\tau \in (0, 1)$ , a unit $u$ is dense if $\text{selectivity}(u) > \tau$ . Units and density are analogously defined for any $k$ -dimensional subspace projection $A_{t_1} \times A_{t_2} \times \dots \times A_{t_k}$ ( $k \le d$ ).

Two $k$ -dimensional units $u_1, u_2$ in the same subspace are connected if they share a common $(k-1)$ -dimensional face (differing by adjacent intervals in exactly one dimension and sharing identical intervals in the remaining $k-1$ dimensions) or if there exists an intermediary unit $u_3$ such that $u_1$ is connected to $u_3$ and $u_2$ is connected to $u_3$ .

A cluster $C$ in a $k$ -dimensional subspace is a maximal set of connected dense units. A region is an axis-parallel rectangular union of units, expressible as a conjunction of interval constraints. A minimal description of cluster $C$ is a non-redundant covering of $C$ using a minimal set of maximal regions $\mathcal{R}$ , presented as a Disjunctive Normal Form (DNF) expression over attribute intervals.
Knowl 2 — Monotonicity of Dense Units Across Subspace Projections
theoretical result
Let $V$ be a set of data points in a $d$ -dimensional space partitioned by a uniform grid with interval parameter $\xi$ and density threshold $\tau$ .

If a set of points $S \subseteq V$ forms a cluster in a $k$ -dimensional subspace, then $S$ is also part of a cluster in every $(k-1)$ -dimensional projection of that subspace.

Equivalently, every projection of a $k$ -dimensional dense unit into a $(k-1)$ -dimensional subspace must also be dense (selectivity $> \tau$ ), because the projected unit contains all data points residing in the higher-dimensional unit. Consequently, dense units satisfy a downward-closure property with respect to subspace dimensionality.
Knowl 3 — Bottom-Up Dense Unit Generation Algorithm
algorithm
Dense units across all subspaces are identified level-by-level using an Apriori-style candidate generation approach that exploits the monotonicity of dense units.
Input: Dataset $V$ , number of intervals $\xi$ , density threshold $\tau$
Output: Sets of dense units $D_1, D_2, \dots, D_k$
1. Determine $D_1$ , the set of all 1-dimensional dense units, by counting point frequencies across all 1D intervals in a single pass over $V$ .
2. $k \leftarrow 2$
3. while $D_{k-1} \neq \emptyset$ do
4. $C_k \leftarrow \emptyset$
5. for each pair $u_1, u_2 \in D_{k-1}$ sharing the first $k-2$ dimensions and intervals with $u_1.a_{k-1} < u_2.a_{k-1}$ do
6. $c \leftarrow$ candidate unit formed by joining $u_1$ and $u_2$
7. if all $(k-1)$ -dimensional projections of $c$ are in $D_{k-1}$ then
8. $C_k \leftarrow C_k \cup \{c\}$
9. Scan dataset $V$ to compute the selectivity of each candidate $c \in C_k$
10. $D_k \leftarrow \{c \in C_k \mid \text{selectivity}(c) > \tau\}$
11. $k \leftarrow k + 1$
12. return $\bigcup_j D_j$
For $m$ input points and maximum dense unit dimensionality $k$ , the algorithm requires $k$ database passes and runs in $O(c^k + m \cdot k)$ time for a constant $c$ .
Knowl 4 — MDL-Based Subspace Pruning for Dense Unit Exploration
model/method
To prevent candidate unit explosion in high-dimensional datasets, dense units are pruned prior to candidate generation using the Minimum Description Length (MDL) principle.

For each subspace $S_j \in \{S_1, S_2, \dots, S_n\}$ at a given dimensionality level, its coverage $x_{S_j}$ is defined as the total number of points contained in its dense units:

$x_{S_j} = \sum_{u_i \in S_j} \text{count}(u_i)$

The subspaces are sorted in descending order of coverage: $x_{S_1} \ge x_{S_2} \ge \dots \ge x_{S_n}$ . A cut point $i \in \{1, \dots, n-1\}$ partitions the sorted list into a selected set $I = \{S_1, \dots, S_i\}$ and a pruned set $P = \{S_{i+1}, \dots, S_n\}$ . The integer mean coverages are:

$\mu_I(i) = \left\lceil \frac{1}{i} \sum_{j=1}^i x_{S_j} \right\rceil, \quad \mu_P(i) = \left\lceil \frac{1}{n-i} \sum_{j=i+1}^n x_{S_j} \right\rceil$

The total encoding length $CL(i)$ under this model is:

$CL(i) = \log_2(\mu_I(i)) + \sum_{j=1}^i \log_2(|x_{S_j} - \mu_I(i)|) + \log_2(\mu_P(i)) + \sum_{j=i+1}^n \log_2(|x_{S_j} - \mu_P(i)|)$

The optimal cut point $i^* = \arg\min_{1 \le i < n} CL(i)$ is determined in two linear passes over the sorted subspaces. Subspaces in $P$ and their dense units are discarded, retaining only dense units in $I$ for subsequent candidate generation.
Knowl 5 — Subspace Cluster Identification via Graph Connected Components
algorithm
Given a set of dense units $D$ in a $k$ -dimensional subspace, clusters are identified by computing connected components in an adjacency graph where vertices represent dense units and edges connect pairs of units sharing a $(k-1)$ -dimensional face.
Input: Set of dense units $D$ in subspace $S$ , stored in a hash tree
Output: Partition of $D$ into connected clusters $D^1, D^2, \dots, D^p$
1. Mark all $u \in D$ as unvisited
2. cluster_count $\leftarrow 0$
3. for each unvisited unit $u \in D$ do
4. cluster_count $\leftarrow$ cluster_count $+ 1$
5. queue $Q \leftarrow [u]$
6. mark $u$ as visited with label cluster_count
7. while $Q$ is not empty do
8. $v \leftarrow Q.\text{pop}()$
9. for each of the $2k$ adjacent neighbor positions $v'$ of $v$ do
10. if $v' \in D$ (via hash tree lookup) and $v'$ is unvisited then
11. mark $v'$ as visited with label cluster_count
12. $Q.\text{push}(v')$
13. return clusters grouped by cluster label
For $n = |D|$ dense units in a $k$ -dimensional subspace, the search visits every unit and examines its $2k$ neighbors, executing exactly $2kn$ hash tree accesses.
Knowl 6 — Greedy Growth of Maximal Covering Regions
algorithm
To represent a cluster $C$ of $n$ connected $k$ -dimensional units, maximal hyper-rectangular regions are greedily generated to cover all units in $C$ .
Input: Cluster $C$ of connected dense $k$ -dimensional units in subspace $S$
Output: Set of maximal rectangular regions $\mathcal{R}$ covering $C$
1. $\mathcal{R} \leftarrow \emptyset$
2. while there exists a unit $u \in C$ not covered by any region in $\mathcal{R}$ do
3. $R \leftarrow u$
4. Choose a random permutation of dimensions $(a_1, a_2, \dots, a_k)$ of $S$
5. for $j = 1$ to $k$ do
6. Expand $R$ along dimension $a_j$ in the negative direction as far as possible such that all added units belong to $C$
7. Expand $R$ along dimension $a_j$ in the positive direction as far as possible such that all added units belong to $C$
8. $\mathcal{R} \leftarrow \mathcal{R} \cup \{R\}$
9. return $\mathcal{R}$
Each maximal region $R$ requires $O(|R|)$ unit accesses, with neighbor boundary checks bounded by $2k|R|$ . Across at most $O(n)$ generated regions, the greedy growth algorithm performs $O(n^2)$ total dense unit accesses.
Knowl 7 — Removal Heuristic for Minimal DNF Cluster Descriptions
algorithm
Given a covering set of maximal rectangular regions $\mathcal{R}$ for a cluster $C$ , redundant regions are removed to produce a minimal DNF description.
Input: Set of maximal regions $\mathcal{R}$ covering cluster $C$
Output: Minimal cover $\mathcal{R}_{min} \subseteq \mathcal{R}$
1. Sort the regions in $\mathcal{R}$ in ascending order of size (number of dense units contained): $R_1, R_2, \dots, R_{|\mathcal{R}|}$
2. for $i = 1$ to $|\mathcal{R}|$ do
3. if every unit $u \in R_i$ is contained in at least one region in $\mathcal{R} \setminus \{R_i\}$ then
4. $\mathcal{R} \leftarrow \mathcal{R} \setminus \{R_i\}$
5. return $\mathcal{R}$
Sorting requires $O(|\mathcal{R}| \log |\mathcal{R}|) = O(n \log n)$ time, where $n = |C|$ . Verifying redundancy takes $\sum |R_i| = O(n^2)$ unit accesses. The surviving maximal regions define a minimal DNF expression: each region is a conjunction of intervals across subspace attributes, and their union is a disjunction.
Knowl 8 — Stochastic Approximation Bound for Minimal Cluster Cover
theoretical result
Let each unit in a $d$ -dimensional grid space be independently dense with probability at most $p$ , where:

$p = \frac{1}{2d} - \epsilon$

for any fixed constant $\epsilon > 0$ .

Under this independent density model, there exists a constant $\alpha > 1$ (depending solely on $\epsilon$ ) such that the probability of a cluster containing $i$ dense units is at most $\alpha^{-i}$ . The expected number of maximal rectangles required to cover a cluster of size $i$ is bounded by $\sum_{i} i \alpha^{-i} \le \theta$ for a constant $\theta$ .

Consequently, across $n$ discovered clusters, the total expected number of maximal regions in the cover produced by the greedy removal heuristic satisfies:

$\mathbb{E}[|\mathcal{R}|] \le \sum_{\text{clusters}} \sum_i i \alpha^{-i} \le \theta n$

The expected size of the cover found by the greedy removal heuristic is within a constant factor of the optimal minimal cover.
Knowl 9 — Scalability and Subspace Cluster Recovery Performance of CLIQUE
empirical result
CLIQUE was evaluated on synthetic datasets in $[0, 100]^d$ with grid interval $\xi = 10$ , density threshold $\tau \in [0.1\%, 1.0\%]$ , and $10\%$ added uniform noise.
1. Database Size: Across 100,000 to 500,000 records in 50 dimensions with 5 five-dimensional embedded clusters ( $\tau = 0.5\%$ ), execution time increased linearly from $\approx 4{,}000$ to $\approx 20{,}000$ seconds because the number of data passes remains fixed at $k$ .
2. Data Dimensionality: Increasing data dimensions from 10 to 100 (100,000 records, 5 five-dimensional clusters) exhibited quadratic runtime growth, scaling substantially better than the theoretical $O(d^5)$ subspace explosion due to MDL pruning (which pruned $86\%$ of 2D and $38\%$ of 3D candidate subspaces).
3. Cluster Dimensionality: Increasing embedded cluster dimensionality from 3 to 10 in 50-dimensional space scaled according to $O(m k + c^k)$ .
4. Accuracy: In all synthetic tests, CLIQUE recovered 100% of the true planted subspace clusters without requiring prior specification of relevant subspaces.

Knowl 10 — Inability of Full-Space Clustering and SVD to Identify Subspace Clusters

empirical result

Full-space clustering algorithms (BIRCH, DBSCAN) and dimensionality reduction via Singular Value Decomposition (SVD) were tested on synthetic datasets containing five 5-dimensional clusters embedded in higher-dimensional data spaces ( $d = 5$ to $50$ ):

Method	Data Dim ( $d$ )	Cluster Dim	Clusters Found	True Clusters Identified
BIRCH	5	5	5	5
BIRCH	10	5	5	5
BIRCH	20	5	3, 4, 5	0
BIRCH	30	5	3, 4	0
BIRCH	40	5	3, 4	0
BIRCH	50	5	3	0
DBSCAN	5	5	5	5
DBSCAN	7	5	5	5
DBSCAN	8	5	3	1
DBSCAN	10	5	1	0

BIRCH failed to recover any true embedded clusters once total dimensionality reached 20 or higher, because Euclidean distance across all dimensions is dominated by uniform noise. DBSCAN failed beyond 7 dimensions because noise in non-cluster dimensions reduces overall data point density below required density thresholds.

SVD eigenvalue ratios $r_k = \sum_{i=1}^k \lambda_i / \sum_{i=1}^d \lambda_i$ on 50-dimensional data yielded $r_{d-1} = 0.984$ (the smallest eigenvalue was nearly equal to the largest), demonstrating that variance is uniformly distributed and preventing dimensionality reduction. Furthermore, projected axes formed linear combinations of all original dimensions, rendering original axis subspaces unidentifiable.

Coverage note — None was omitted; all key contributions—including the grid-based subspace clustering definition, monotonicity principle, dense unit candidate generation, MDL subspace pruning, DFS cluster identification, maximal region greedy growth, redundant region removal heuristic, stochastic approximation bound, and empirical comparisons—are fully represented.

References

1.R. Agrawal, H. Mannila, R. Srikant, H. Toivonen, and A. I. Verkamo. Fast Discovery of Association Rules. In U. M. Fayyad, G. Piatetsky-Shapiro, P. Smyth, and R. Uthurusamy, editors, Advances in Knowledge Discovery and Data Mining, chapter 12, pages 307-328. AAAI/MIT Press, 1996.
2.A. Aho, J. Hopcroft, and J. Ullman. The Design and Analysis of Computer Algorithms. Addison-Welsley, 1974.
3.P. Arabie and L. J. Hubert. An overview of combinatorial data analyis. In P. Arabie, L. Hubert, and G. D. Soete, editors, Clustering and Classification, pages 5-63. World Scientific Pub., New Jersey, 1996.
4.Arbor Software Corporation. Application Manager User's Guide, Essbase Version 4.0 edition.
5.R. Bayardo. Efficiently mining long patterns from databases. In Proc. of the ACM SIGMOD Conference on Management of Data, Seattle, Washington, 1998.
6.S. Berchtold, C. Bohm, D. Keim, and H.-P. Kriegel. A cost model for nearest neighbor search in high-dimensional data space. In Proceedings of the 16th Symposium on Principles of Database Systems (PODS), pages 78-86, 1997.
7.M. Berger and I. Regoutsos. An algorithm for point clustering and grid generation. IEEE Transactions on Systems, Man and Cybernetics, 21(5):1278-86, 1991.
8.S. Brin, R. Motwani, J. D. Ullman, and S. Tsur. Dynamic itemset counting and implication rules for market basket data. In Proc. of the ACM SIGMOD Conference on Management of Data, May 1997.
9.P. Cheeseman and J. Stutz. Bayesian classification (autoclass): Theory and results. In U. M. Fayyad, G. Piatetsky-Shapiro, P. Smyth, and R. Uthurusamy, editors, Advances in Knowledge Discovery and Data Mining, chapter 6, pages 153-180. AAAI/MIT Press, 1996.
10.R. Chhikara and D. Register. A numerical classification method for partitioning of a large multidimensional mixed data set. Technometrics, 21:531-537, 1979.
11.R. O. Duda and P. E. Hart. Pattern Classification and Scene Analysis. John Wiley and Sons, 1973.
12.R. J. Earle. Method and apparatus for storing and retrieving multi-dimensional data in computer memory. U.S. Patent No. 5359724, October 1994.
13.M. Ester, H.-P. Kriegel, J. Sander, and X. Xu. A density-based algorithm for discovering clusters in large spatial databases with noise. In Proc. of the 2nd Int'l Conference on Knowledge Discovery in Databases and Data Mining, Portland, Oregon, August 1996.
14.M. Ester, H.-P. Kriegel, and X. Xu. A database interface for clustering in large spatial databases. In Proc. of the 1st Int'l Conference on Knowledge Discovery in Databases and Data Mining, Montreal, Canada, August 1995.
15.U. M. Fayyad, G. Piatetsky-Shapiro, P. Smyth, and R. Uthurusamy, editors. Advances in Knowledge Discovery and Data Mining. AAAI/MIT Press, 1996.
16.U. Feige. A threshold of ln n for approximating set cover. In Proceedings of the Twenty-Eighth Annual ACM Symposium on Theory of Computing, pages 314-318, 1996.
17.D. Franzblau. Performance guarantees on a sweep-line heuristic for covering rectilinear polygons with rectangles. SIAM J. Disc. Math, 2:307-321, 3 (1989).
18.J. Friedman. Optimizing a noisy function of many variables with application to data mining. In UW/MSR Summer Research Institute in Data Mining, July 1997.
19.K. Fukunaga. Introduction to Statistical Pattern Recognition. Academic Press, 1990.
20.D. Gunopulos, R. Khardon, H. Mannila, and S. Saluja. Data mining, hypergraph transversals, and machine learning. In Proc. of the 16th ACM Symp. on Principles of Database Systems, pages 209-216, 1997.
21.C.-T. Ho, R. Agrawal, N. Megiddo, and R. Srikant. Range queries in OLAP data cubes. In Proc. of the ACM SIGMOD Conference on Management of Data, Tucson, Arizona, May 1997.
22.S. J. Hong. MINI: A heuristic algorithm for two-level logic minimization. In R. Newton, editor, Selected Papers on Logic Synthesis for Integrated Circuit Design. IEEE Press, 1987.
23.International Business Machines. IBM Intelligent Miner User's Guide, Version 1 Release 1, SH12-6213-00 edition, July 1996.
24.A. K. Jain and R. C. Dubes. Algorithms for Clustering Data. Prentice Hall, 1988.
25.L. Kaufman and P. Rousseeuw. Finding Groups in Data: An Introduction to Cluster Analysis. John Wiley and Sons, 1990.
26.D.-I. Lin and Z. M. Kedem. Pincer search: A new algorithm for discovering the maximum frequent sets. In Proc. of the 6th Int'l Conference on Extending Database Technology (EDBT), Valencia, Spain, 1998.
27.L. Lovász. On the ratio of the optimal integral and fractional covers. Discrete Mathematics, 13:383-390, 1975.
28.C. Lund and M. Yannakakis. On the hardness of approximating minimization problems. In Proceedings of the ACM Symposium on Theory of Computing, pages 286-293, 1993.
29.W. Masek. Some NP-complete set covering problems. M.S. Thesis, MIT, 1978.
30.M. Mehta, R. Agrawal, and J. Rissanen. SLIQ: A fast scalable classifier for data mining. In Proc. of the Fifth Int'l Conference on Extending Database Technology (EDBT), Avignon, France, March 1996.
31.R. S. Michalski and R. E. Stepp. Learning from observation: Conceptual clustering. In R. S. Michalski, J. G. Carbonell, and T. M. Mitchell, editors, Machine Learning: An Artificial Intelligence Approach, volume I, pages 331-363. Morgan Kaufmann, 1983.
32.R. Miller and Y. Yang. Association rules over interval data. In Proc. ACM SIGMOD International Conf. on Management of Data, pages 452-461, 1997.
33.R. T. Ng and J. Han. Efficient and effective clustering methods for spatial data mining. In Proc. of the VLDB Conference, Santiago, Chile, September 1994.
34.R. A. Reckhow and J. Culberson. Covering simple orthogonal polygon with a minimum number of orthogonally convex polygons. In Proc. of the ACM 3rd Annual Computational Geometry Conference, pages 268-277, 1987.
35.J. Rissanen. Stochastic Complexity in Statistical Inquiry. World Scientific Publ. Co., 1989.
36.P. Schroeter and J. Bigun. Hierarchical image segmentation by multi-dimensional clustering and orientation-adaptive boundary refinement. Pattern Recognition, 25(5):695-709, May 1995.
37.J. Shafer, R. Agrawal, and M. Mehta. SPRINT: A scalable parallel classifier for data mining. In Proc. of the 22nd Int'l Conference on Very Large Databases, Bombay, India, September 1996.
38.A. Shoshani. Personal communication. 1997.
39.P. Sneath and R. Sokal. Numerical Taxonomy. Freeman, 1973.
40.R. Srikant and R. Agrawal. Mining Quantitative Association Rules in Large Relational Tables. In Proc. of the ACM SIGMOD Conference on Management of Data, Montreal, Canada, June 1996.
41.H. Toivonen. Sampling large databases for association rules. In Proc. of the 22nd Int'l Conference on Very Large Databases, pages 134-145, Mumbai (Bombay), India, September 1996.
42.S. Wharton. A generalized histogram clustering for multidimensional image data. Pattern Recognition, 16(2):193-199, 1983.
43.M. Zait and H. Messatfa. A comparative study of clustering methods. Future Generation Computer Systems, 13(2-3):149-159, November 1997.
44.D. Zhang and A. Bowyer. CSG set-theoretic solid modelling and NC machining of blend surfaces. In Proceedings of the Second Annual ACM Symposium on Computational Geometry, pages 314-318, 1986.
45.T. Zhang, R. Ramakrishnan, and M. Livny. BIRCH: An efficient data clustering method for very large databases. In Proc. of the ACM SIGMOD Conference on Management of Data, Montreal, Canada, June 1996.

Citation

MLA

Agrawal, R., et al. “Automatic Subspace Clustering of High Dimensional Data for Data Mining Applications”. Proceedings of the 1998 ACM SIGMOD International Conference on Management of Data, 1998, pp. 94–105, https://doi.org/10.1145/276304.276314.

APA

Agrawal, R., Gehrke, J., Gunopulos, D., & Raghavan, P. (1998). Automatic subspace clustering of high dimensional data for data mining applications. Proceedings of the 1998 ACM SIGMOD International Conference on Management of Data, 94–105. https://doi.org/10.1145/276304.276314

Chicago

Agrawal, R., J. Gehrke, D. Gunopulos, and P. Raghavan. 1998. “Automatic Subspace Clustering of High Dimensional Data for Data Mining Applications”. Proceedings of the 1998 ACM SIGMOD International Conference on Management of Data, 94–105. https://doi.org/10.1145/276304.276314.

Harvard

Agrawal, R. et al. (1998) “Automatic subspace clustering of high dimensional data for data mining applications”, Proceedings of the 1998 ACM SIGMOD international conference on Management of data. ACM, pp. 94–105. Available at: https://doi.org/10.1145/276304.276314.

Vancouver

1. Agrawal R, Gehrke J, Gunopulos D, Raghavan P (1998) Automatic subspace clustering of high dimensional data for data mining applications. In: Proceedings of the 1998 ACM SIGMOD international conference on Management of data. ACM, pp 94–105

BibTeX

@inproceedings{Agrawal_1998, series={SIGMOD/PODS98}, title={Automatic subspace clustering of high dimensional data for data mining applications}, url={http://dx.doi.org/10.1145/276304.276314}, DOI={10.1145/276304.276314}, booktitle={Proceedings of the 1998 ACM SIGMOD international conference on Management of data}, publisher={ACM}, author={Agrawal, Rakesh and Gehrke, Johannes and Gunopulos, Dimitrios and Raghavan, Prabhakar}, year={1998}, month=June, pages={94–105}, collection={SIGMOD/PODS98} }

Metadata:Crossref

Access the Paper

This paper is available from its original source. Click below to access the PDF.

Open PDF

Automatic subspace clustering of high dimensional data for data mining applications

Abstract

Topics

Keywords

Table of Contents

Knowls

Knowl 1 — Subspace Clustering and Density-Grid Problem Formulation

Knowl 2 — Monotonicity of Dense Units Across Subspace Projections

Knowl 3 — Bottom-Up Dense Unit Generation Algorithm

Knowl 4 — MDL-Based Subspace Pruning for Dense Unit Exploration

Knowl 5 — Subspace Cluster Identification via Graph Connected Components

Knowl 6 — Greedy Growth of Maximal Covering Regions

Knowl 7 — Removal Heuristic for Minimal DNF Cluster Descriptions

Knowl 8 — Stochastic Approximation Bound for Minimal Cluster Cover

Knowl 9 — Scalability and Subspace Cluster Recovery Performance of CLIQUE

Knowl 10 — Inability of Full-Space Clustering and SVD to Identify Subspace Clusters

References

Citation

BibTeX

Access the Paper