Graph theoretical clustering based on limited neighbourhood sets
Pattern RecognitionPublished 1 January 1982
R.B. Urquhart
Citations173
SJR quartileQ1
SJR score2.06
SNIP2.67
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
The method is locally sensitive, hierarchic and based on the concept of limited neighbourhood sets, which means clusters that are either disjoint or homogeneous and separable by sharp changes in point density may be detected.
Abstract
A method for clustering data according to a visual model of clusters is proposed. The method uses either of two graphs which are defined according to relative distance and based on the Gabriel graph and the relative neighbourhood graph respectively. The method is locally sensitive, hierarchic and based on the concept of limited neighbourhood sets. Clusters that are either disjoint or homogeneous and separable by sharp changes in point density may be detected.
Keywords
Computer Science
Annals of EugenicsTHE USE OF MULTIPLE MEASUREMENTS IN TAXONOMIC PROBLEMS
14,727 Citations1936Ronald Aylmer Fisher
PsychometrikaHierarchical Clustering Schemes
4,891 Citations1967S. C. Johnson
A useful correspondence is developed between any hierarchical system of such clusters, and a particular type of distance measure, that gives rise to two methods of clustering that are computationally rapid and invariant under monotonic transformations of the data.
IEEE Transactions on ComputersGraph-Theoretical Methods for Detecting and Describing Gestalt Clusters
1,741 Citations1971C. T. Zahn
A family of graph-theoretical algorithms based on the minimal spanning tree are capable of detecting several kinds of cluster structure in arbitrary point sets; description of the detected clusters is possible in some cases by extensions of the method.
International Journal of Parallel ProgrammingTwo algorithms for constructing a Delaunay triangulation
1,568 Citations1980D. T. Lee, Bruce J. Schachter
This paper provides a unified discussion of the Delaunay triangulation and two algorithms are presented for constructing the triangulations over a planar set ofN points.
The Computer JournalComputing the n-dimensional Delaunay tessellation with application to Voronoi polytopes
1,459 Citations1981David F. Watson
Systematic ZoologyA New Statistical Approach to Geographic Variation Analysis
1,291 Citations1969K. Ruben Gabriel, Robert R. Sokal
The authors discuss the problems of describing geographic variation data and develop statistical methods for categorizing sets of populations sampled from different localities and describe the approach of the simultaneous test procedures employed with these techniques.
Journal of the Royal Statistical Society Series C (Applied Statistics)Minimum Spanning Trees and Single Linkage Cluster Analysis
1,233 Citations1969J. C. Gower, G. J. Ross
Minimum spanning trees (MST) and single linkage cluster analysis (SLCA) are explained and it is shown that all the information required for the SLCA of a set of points is contained in their MST.
Closest-point problems
1,062 Citations1975Michael Ian Shamos, Dan Hoey
The purpose of this paper is to introduce a single geometric structure, called the Voronoi diagram, which can be constructed rapidly and contains all of the relevant proximity information in only linear space, and is used to obtain O(N log N) algorithms for most of the problems considered.
Pattern RecognitionThe relative neighbourhood graph of a finite planar set
988 Citations1980Godfried T. Toussaint
The ability of the RNG to extract a perceptually meaningful structure from the set of points is briefly discussed and compared to that of two other graph structures: the minimal spanning tree and the Delaunay (Voronoi) triangulation.
IEEE Transactions on ComputersClustering Using a Similarity Measure Based on Shared Near Neighbors
957 Citations1973R.A. Jarvis, Edward A. Patrick
A nonparametric clustering technique incorporating the concept of similarity based on the sharing of near neighbors is presented, which is an essentially paraliel approach and is applicable to a wide class of practical problems involving large sample size and high dimensionality.
Pattern RecognitionAgglomerative clustering using the concept of mutual nearest neighbourhood
413 Citations1978K. Chidananda Gowda, G. Krishna
A method for determining the mutual nearest neighbours (MNN) and mutual neighbourhood value (mnv) of a sample point, using the conventional nearest neighbours, is suggested.
Geographical AnalysisProperties of Gabriel Graphs Relevant to Geographic Variation Research and the Clustering of Points in the Plane
373 Citations1980David W. Matula, Robert R. Sokal
Pattern RecognitionClustering techniques: The user's dilemma
341 Citations1976Richard C. Dubes, Anil K. Jain
This paper examines eight clustering programs which are representative of the various available techniques and compare their performances from several points of view to set some guidelines for a potential user of a clustering technique.
Pattern RecognitionValidity studies in clustering methodologies
300 Citations1979Richard C. Dubes, Anil K. Jain
This paper provides a semi-tutorial review of the state-of-the-art in cluster validity, or the verification of results from clustering algorithms, and covers ways of measuring clustering tendency, the fit of hierarchical and partitional structures and indices of compactness and isolation for individual clusters.
IEEE Transactions on ComputersA Graph-Theoretic Approach to Nonparametric Cluster Analysis
192 Citations1976Koontz, Narendra +1 more
This paper presents a noniterative, graph-theoretic approach to nonparametric cluster analysis that is governed by a single-scalar parameter, requires no starting classification, and is capable of determining the number of clusters.
Mathematical BiosciencesThe structure and construction of taxonomic hierarchies
123 Citations1967C. J. JARDINE, N. Jardine +1 more
A logical model for taxonomic hierarchies is formulated and it is concluded that some widely used techniques fail to satisfy certain obvious requirements, and an alternative approach is outlined.
IEEE Transactions on Pattern Analysis and Machine IntelligenceBicriterion Cluster Analysis
110 Citations1980Michel Delattre, Pierre Hansen
It is shown that the problem of determining a partition into a given number of clusters with minimum diameter or with maximum split can be solved by the classical single-link clustering algorithm and by a graph-theoretic algorithm involving the optimal coloration of a sequence of partial graphs.
IEEE Transactions on ComputersAn Alternative Definition for "Neighborhood of a Point"
61 Citations1975John O'Callaghan
The concept of "neighborhood of a point" has been used in various programs for analyzing spatial dot patterns and an alternative definition is proposed to reflect the intuitive cluster associations of certain points in simple patterns more satisfactorily.
Pattern RecognitionStability of a hierarchical clustering
45 Citations1980Stephen P. Smith, Richard C. Dubes
The stability of a hierarchical structure with a variation on a measure of stability proposed in the literature is studied, appropriate for proximity matrices whose entries are on an ordinal scale.
Electronics LettersAlgorithms for computation of relative neighbourhood graph
32 Citations1980R.B. Urquhart
IEEE Transactions on Pattern Analysis and Machine IntelligenceA Nonparametric Algorithm for Detecting Clusters Using Hierarchical Structure
22 Citations1980Riichiro Mizoguchi, Masamichi Shimura
This paper discusses a nonparametric algorithm for detecting clusters that can be applied to a very wide range of data set and has great ability to detect clusters, which is verified by computer simulation.
PerceptionA Computational View of Perception
14 Citations1973B. G. Rosenberg, D.J. Langridge
A computational approach to visual perception is outlined and it is suggested that a theory which evolves in the manner described has a more unitary aspect than other approaches.
Electronics LettersOptimum aperture distributions in the presence of blockage
1 Citations1978M. Sachidananda, S. Anantha Ramakrishna