Efficient and Effective Clustering Methods for Spatial Data Mining

R. NgJiawei Han

article1994VLDB2,098 citations

clustering methods spatial data mining spatial database Data Spatial CLARANS

Ng et al (1994).pdf

Cover for Efficient and Effective Clustering Methods for Spatial Data Mining

Topics

clustering methods spatial data mining spatial database association rules knowledge discovery in database

Keywords

Data Spatial CLARANS Spatial Data Data Mining Spatial Data Mining Clustering Clusters Cluster CLARA

1 Introduction
2 Clustering Algorithms based on Partitioning
2.1 PAM
2.2 CLARA
3 A Clustering Algorithm based on Randomized Search
3.1 Motivation of CLARANS: a Graph Abstraction
3.2 CLARANS
3.3 Experimental Results: CLARANS vs PAM
3.4 Experimental Results: CLARANS vs CLARA
4 Spatial Data Mining based on Clustering Algorithms
4.1 Spatial Dominant Approach: SD(CLARANS)
4.2 Determining knot for CLARANS
4.3 Non-Spatial Dominant Approach: NSD(CLARANS)
5 Evaluation of SD(CLARANS) and NSD(CLARANS)
5.1 A Real Estate Data Set
5.2 Effectiveness of SD( CLARANS)
5.3 Effectiveness of NSD(CLARANS)
5.4 summary
6 Discussions
6.1 Exploring Spatial Relationships
6.2 Towards Building a More General and Efficient Spatial Data Mining Framework
7 Conclusions
Acknowledgements
References

Knowls

Knowl 1 — CLARANS Algorithm
algorithm
CLARANS (Clustering Large Applications based on RANdomized Search) is a $k$ -medoid clustering algorithm that searches for optimal medoids by exploring the graph $G_{n,k}$ of medoid sets via randomized local search.
Input: Number of objects $n$ , number of clusters $k$ , parameters numlocal, maxneighbor
Output: A set of $k$ medoids bestnode
Initialize i = 1
Initialize mincost to a very large number
while i <= numlocal do
    Set current to an arbitrarily selected node in $G_{n,k}$
    Set j = 1
    while j <= maxneighbor do
        Select a random neighbor S of current
        Calculate the cost differential delta_cost = cost(S) - cost(current)
        if delta_cost < 0 then
            current = S
            j = 1
        else
            j = j + 1
    if cost(current) < mincost then
        mincost = cost(current)
        bestnode = current
    i = i + 1
return bestnode
CLARANS performs numlocal independent local searches. In each search, it samples up to maxneighbor random neighbors of the current medoid configuration. If a neighbor provides a lower total distance cost, it transitions immediately to that neighbor and resets the neighbor counter. If maxneighbor consecutive random neighbors fail to improve the objective, the current node is declared a local minimum. After completing numlocal local searches, CLARANS returns the best local minimum found.
Knowl 2 — Graph Abstraction of k-Medoid Clustering
model/method
The problem of finding $k$ medoids from a dataset of $n$ objects is modeled as searching for a minimum-cost node in an undirected graph $G_{n,k} = (V, E)$ :
1. Nodes ( $V$ ): Each node represents a distinct subset of $k$ objects chosen from the $n$ dataset objects, $S = \{O_{m_1}, \dots, O_{m_k}\}$ . The total number of nodes is $\binom{n}{k}$ .
2. Edges ( $E$ ): Two nodes $S_1, S_2 \in V$ are neighbors connected by an edge if and only if they differ by exactly one medoid, i.e., $|S_1 \cap S_2| = k - 1$ . Every node has exactly $k(n - k)$ neighbors.
3. Node Cost: The cost of a node $S$ is the sum of dissimilarities of each object $O_j$ in the dataset to its nearest medoid in $S$ : $\text{cost}(S) = \sum_{j=1}^n \min_{O_m \in S} d(O_j, O_m)$ where $d(O_a, O_b)$ is the distance or dissimilarity between objects $O_a$ and $O_b$ .
In this framework, the standard PAM algorithm searches $G_{n,k}$ by exhaustively evaluating all $k(n - k)$ neighbors at each step and moving in the direction of steepest descent. CLARA restricts the search to a fixed subgraph $G_{S_a, k}$ induced by an initial random sample $S_a \subset \{O_1, \dots, O_n\}$ . In contrast, CLARANS dynamically samples neighbors on the full graph $G_{n,k}$ without restricting the search to a static subgraph.
Knowl 3 — Medoid Swap Cost Differential Equations
equation
When evaluating a neighbor node in $G_{n,k}$ formed by replacing an active medoid $O_i$ with a non-medoid object $O_h$ , the total cost change is given by: $TC_{ih} = \sum_{j=1}^n C_{jih}$ where $C_{jih}$ is the cost contribution for object $O_j$ , categorized into four mutually exclusive cases based on whether $O_j$ is currently assigned to $O_i$ and its distance to the second-nearest medoid $O_{j,2}$ relative to candidate medoid $O_h$ :
1. Case 1: $O_j$ is currently assigned to medoid $O_i$ , and $d(O_j, O_h) \ge d(O_j, O_{j,2})$ . Object $O_j$ reassings to $O_{j,2}$ : $C_{jih} = d(O_j, O_{j,2}) - d(O_j, O_i) \ge 0$
2. Case 2: $O_j$ is currently assigned to medoid $O_i$ , and $d(O_j, O_h) < d(O_j, O_{j,2})$ . Object $O_j$ reassigns to $O_h$ : $C_{jih} = d(O_j, O_h) - d(O_j, O_i)$
3. Case 3: $O_j$ is currently assigned to a medoid other than $O_i$ (with closest medoid $O_{j,2}$ ), and $d(O_j, O_h) \ge d(O_j, O_{j,2})$ . Object $O_j$ remains assigned to $O_{j,2}$ : $C_{jih} = 0$
4. Case 4: $O_j$ is currently assigned to a medoid other than $O_i$ (with closest medoid $O_{j,2}$ ), and $d(O_j, O_h) < d(O_j, O_{j,2})$ . Object $O_j$ reassigns to $O_h$ : $C_{jih} = d(O_j, O_h) - d(O_j, O_{j,2}) < 0$
Knowl 4 — Spatial Dominant Spatial Data Mining: SD(CLARANS)
algorithm
SD(CLARANS) is a spatial-dominant data mining algorithm that first partitions spatial data into natural clusters and then characterizes the non-spatial attributes of each discovered cluster.
Input: Relational database with spatial and non-spatial attributes, learning query
Output: High-level descriptive rules for each spatial cluster
Execute SQL query to retrieve relevant tuples matching the learning query
Run CLARANS on the spatial attributes to determine the natural number of clusters k_nat
for each cluster c from 1 to k_nat do
    Collect non-spatial attribute components of all tuples assigned to cluster c
    Apply attribute-oriented induction (DBLEARN) to these non-spatial components
    Output the resulting generalized characterization for cluster c
By executing spatial clustering directly on the coordinates before applying non-spatial concept hierarchies, SD(CLARANS) dynamically determines spatial boundaries without requiring predefined spatial concept hierarchies.
Knowl 5 — Non-Spatial Dominant Spatial Data Mining: NSD(CLARANS)
algorithm
NSD(CLARANS) is a non-spatial dominant data mining algorithm that groups data by generalized non-spatial attribute values first and subsequently discovers spatial clusters within each group.
Input: Relational database with spatial and non-spatial attributes, learning query, generalization threshold
Output: Generalized descriptions associated with spatial clusters
Execute SQL query to retrieve relevant tuples matching the learning query
Apply DBLEARN to non-spatial attributes until the number of generalized tuples falls below the threshold
for each generalized tuple t do
Collect spatial coordinates of all base tuples represented by t
Run CLARANS with the k_nat heuristic on these spatial coordinates
Identify all spatial clusters across different generalized tuples that overlap or intersect
Merge overlapping spatial clusters and combine their corresponding generalized non-spatial tuples
return merged spatial clusters and generalized descriptions
Merging intersecting spatial clusters in the final step combines non-spatial classes that occupy identical or contiguous geographic regions.
Knowl 6 — Heuristic for Determining the Natural Number of Clusters and Filtering Outliers
algorithm
To automatically determine the natural number of clusters $k_{nat}$ and filter spatial noise/outliers, a silhouette-based heuristic is applied:
Input: Dataset of spatial points, outlier threshold percentage (default 25%)
Output: Natural cluster count k_nat, filtered clustering
Compute silhouette coefficient for candidate values k >= 2
Find k with the highest average silhouette coefficient
if all k clusters have individual silhouette widths >= 0.51 then
    k_nat = k
    return k_nat
else
    Identify clusters with silhouette width < 0.50
    if total objects in these low-width clusters < outlier threshold then
        Remove all objects in low-width clusters as noise/outliers
        Re-run the heuristic on the remaining dataset
    else
        k_nat = 1 (no natural clustering structure exists)
        return k_nat
A cluster with silhouette width $\ge 0.71$ is classified as a strong cluster, $[0.51, 0.70]$ as a reasonable cluster, $[0.26, 0.50]$ as weak or artificial, and $\le 0.25$ as lacking cluster structure.
Knowl 7 — Default Hyperparameter Configuration for CLARANS
model/method
CLARANS requires two user-defined parameters: numlocal (the number of local minima to discover) and maxneighbor (the number of random neighbors evaluated before concluding that a current node is a local minimum).

The established default heuristic setting for CLARANS is: $\text{numlocal} = 2$ $\text{maxneighbor} = \max(0.0125 \times k(n - k), 250)$ where $n$ is the total number of objects and $k$ is the specified number of medoids/clusters.

Higher values of maxneighbor cause CLARANS to behave more similarly to exhaustive PAM at the cost of increased runtime per local search, whereas lower values find local minima more quickly but may require a higher numlocal to discover a high-quality minimum.
Knowl 8 — Clustering Quality Comparison of CLARANS vs CLARA Under Fixed Time
empirical result
When allocated equal execution time, CLARANS consistently achieves higher clustering quality (lower average dissimilarity) than CLARA across datasets with $n \in [1000, 3000]$ and cluster counts $k \in \{5, 10, 20\}$ :
1. Effect of Cluster Count ( $k$ ): The quality gap between CLARANS and CLARA widens as $k$ grows. At $k = 5$ , CLARANS produces average dissimilarity values approximately 4% lower than CLARA, widening to an advantage of approximately 20% at $k = 20$ . This occurs because CLARA's sample-based PAM search incurs an $O(k^3 + nk)$ per-iteration cost that scales unfavorably with $k$ , whereas CLARANS neighbor evaluation cost scales linearly with $n$ .
2. Effect of Dataset Size ( $n$ ): For a fixed $k$ , increasing $n$ narrows the relative performance gap (e.g., at $k = 20$ , CLARANS outperforms CLARA by ~30% at $n = 1000$ , narrowing to ~20% at $n = 2000$ ) because the $O(n)$ cost of CLARANS neighbor evaluation becomes relatively more demanding with larger $n$ , while CLARA's $k^3$ term dominates its sample phase.
Knowl 9 — Efficiency Comparison of CLARANS vs PAM on Small Datasets
empirical result
On small synthetic datasets with $n \in \{40, 60, 80, 100\}$ objects and $k = 5$ clusters, CLARANS and PAM find clusterings of identical quality (identical average distance to medoids). However, CLARANS achieves significantly lower execution time:
1. At $n = 40$ , PAM takes ~1.5 seconds while CLARANS takes ~0.5 seconds.
2. At $n = 100$ , PAM takes ~10 seconds while CLARANS takes ~1.3 seconds.
The runtime divergence increases rapidly with $n$ due to PAM's per-iteration complexity of $O(k(n - k)^2)$ , compared to CLARANS's randomized sampling of at most maxneighbor neighbors per step.

Coverage note — Omitted the high-level qualitative discussion in Section 6 regarding hypothetical integration with multi-thematic GIS maps and line-type data, as these are future research suggestions rather than concrete contributions of the paper.

References

1.R. Agrawal, S. Ghosh, T. Imielinski, B. Iyer, and A. Swami. (1992) An Interval Classifier for Database Mining Applications, Proc. 18th VLDB, pp 560-573.
2.R. Agrawal, T. Imielinski, and A. Swami. (1993) Mining Association Rules between Sets of Items in Large Databases, Proc. 1993 SIGMOD, pp 207-216.
3.W. G. Aref and H. Samet. (1991) Optimization Strategies for Spatial Query Processing, Proc. 17th VLDB, pp. 81-90.
4.A. Borgida and R. J. Brachman. (1993) Loading Data into Description Reasoners, Proc. 1993 SIGMOD, pp 217-226.
5.T. Brinkhoff and H.-P. Kriegel and B. Seeger. (1993) Efficient Processing of Spatial Joins Using R-trees, Proc. 1993 SIGMOD, pp 237-246.
6.O. Günther. (1993) Efficient Computation of Spatial Joins, Proc. 9th Data Engineering, pp 50-60.
7.J. Han, Y. Cai and N. Cercone. (1992) Knowledge Discovery in Databases: an Attribute-Oriented Approach, Proc. 18th VLDB, pp. 547-559.
8.Y. Ioannidis and Y. Kang. (1990) Randomized Algorithms for Optimizing Large Join Queries, Proc. 1990 SIGMOD, pp. 312-321.
9.Y. Ioannidis and E. Wong. (1987) Query Optimization by Simulated Annealing, Proc. 1987 SIGMOD, pp. 9-22.
10.L. Kaufman and P.J. Rousseeuw. (1990) Finding Groups in Data: an Introduction to Cluster Analysis, John Wiley & Sons.
11.D. Keim and H. Kriegel and T. Seidl. (1994) Supporting Data Mining of Large Databases by Visual Feedback Queries, Proc. 10th Data Engineering, pp 302-313.
12.R. Laurini and D. Thompson. (1992) Fundamentals of Spatial Information Systems, Academic Press.
13.W. Lu, J. Han and B. C. Ooi. (1993) Discovery of General Knowledge in Large Spatial Databases, Proc. Far East Workshop on Geographic Information Systems, Singapore, pp. 275-289.
14.G. Milligan and M. Cooper. (1985) An Examination of Procedures for Determining the Number of Clusters in a Data Set, Psychometrika, 50, pp. 159-179.
15.R. Ng and J. Han. (1994) Effective and Effective Clustering Methods for Spatial Data Mining, Technical Report 94-13, University of British Columbia.
16.G. Piatetsky-Shapiro and W. J. Frawley. (1991) Knowledge Discovery in Databases, AAAI/MIT Press.
17.H. Samet. (1990) The Design and Analysis of Spatial Data Structures, Addison-Wesley.
18.H. Spath. (1985) Cluster Dissection and Analysis: Theory, FORTRAN programs, Examples, Ellis Horwood Ltd.

Citation

MLA

Ng, R. T., and J. Han. “Efficient and Effective Clustering Methods for Spatial Data Mining”. Very Large Data Bases, 1994, pp. 144–55, http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.13.4395.

APA

Ng, R. T., & Han, J. (1994). Efficient and Effective Clustering Methods for Spatial Data Mining. Very Large Data Bases, 144–155. http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.13.4395

Chicago

Ng, R. T., and J. Han. 1994. “Efficient and Effective Clustering Methods for Spatial Data Mining”. Very Large Data Bases, 144–55. http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.13.4395.

Harvard

Ng, R.T. and Han, J. (1994) “Efficient and Effective Clustering Methods for Spatial Data Mining”, Very Large Data Bases, pp. 144–155. Available at: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.13.4395.

Vancouver

1. Ng RT, Han J (1994) Efficient and Effective Clustering Methods for Spatial Data Mining. Very Large Data Bases 144–155

BibTeX

@article{ng1994efficient,
  title = {Efficient and Effective Clustering Methods for Spatial Data Mining},
  author = {Ng, Raymond T. and Han, Jiawei},
  year = {1994},
  journal = {Very Large Data Bases},
  pages = {144-155},
  url = {http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.13.4395}
}

Metadata:DOI registry

Access the Paper

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

Open PDF

Efficient and Effective Clustering Methods for Spatial Data Mining

Topics

Keywords

Table of Contents

Knowls

Knowl 1 — CLARANS Algorithm

Knowl 2 — Graph Abstraction of k-Medoid Clustering

Knowl 3 — Medoid Swap Cost Differential Equations

Knowl 4 — Spatial Dominant Spatial Data Mining: SD(CLARANS)

Knowl 5 — Non-Spatial Dominant Spatial Data Mining: NSD(CLARANS)

Knowl 6 — Heuristic for Determining the Natural Number of Clusters and Filtering Outliers

Knowl 7 — Default Hyperparameter Configuration for CLARANS

Knowl 8 — Clustering Quality Comparison of CLARANS vs CLARA Under Fixed Time

Knowl 9 — Efficiency Comparison of CLARANS vs PAM on Small Datasets

References

Citation

BibTeX

Access the Paper