×

Connectivity of the mutual \(k\)-nearest-neighbor graph in clustering and outlier detection. (English) Zbl 0898.62077

Summary: For multivariate data sets, we study the relationship between the connectivity of a mutual \(k\)-nearest-neighbor graph, and the presence of clustering structure and outliers in the data. A test for detection of clustering structure and outliers is proposed and its performance is evaluated in simulated data.

MSC:

62H30 Classification and discrimination; cluster analysis (statistical aspects)
62H15 Hypothesis testing in multivariate analysis
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Dudley, R. M., Ecole d’eté de probabilités de St.-Flour, (Lecture Notes in Math., Vol. 1097 (1984), Springer: Springer New York), 1-142
[2] Everitt, B., Cluster Analysis (1974), Heinemann: Heinemann London
[3] González-Barrios, J. M.; Quiroz, A. J., When does the \(k\)-nearest neighbors graph contain the MST?, Comunicación Técnica del CIMAT, No. I-95-06 (1995)
[4] Gowda, K. C.; Krishna, G., Agglomerative clustering using the concept of mutual nearest neighborhood, Pattern Recognition, 10, 105-112 (1978) · Zbl 0379.62051
[5] Harary, F., Graph Theory (1969), Addison-Wesley: Addison-Wesley Reading, MA · Zbl 0797.05064
[6] Hartigan, J., Clustering Algorithms (1975), Wiley: Wiley New York · Zbl 0372.62040
[7] Jain, A. K.; Dubes, R. C., Algorithms for Clustering Data, (Prentice Hall Advanced Reference Series (1988), Prentice Hall: Prentice Hall Englewood Cliffs, NJ) · Zbl 0665.62061
[8] Jarvis, R. A.; Patrick, E. A., Clustering using a similarity measure based on shared near neighbors, IEEE Trans. Comput. C, 22, 1025-1034 (1973)
[9] Knuth, D. E., The Art of Computer Programming (1981), Addison-Wesley: Addison-Wesley Reading, MA · Zbl 0191.17903
[10] Milligan, G. W.; Cooper, M. C., An examination of procedures for determining the number of clusters in a data set, Psychometrica, 50, 159-179 (1985)
[11] Wong, M. A., A hybrid clustering method for identifying high density clusters, J. Amer. Statist. Assoc., 77, 841-847 (1982) · Zbl 0507.62061
[12] Wong, M. A.; Lane, T., A \(k\)-th nearest neighbour clustering procedure, J. Roy. Statist. Soc., Ser. B, 45, 362-368 (1983) · Zbl 0535.62055
[13] Zahn, C. T., Graph-theoretical methods for detecting and describing Gestalt clusters, IEEE Trans. Comput. C, 20, 68-86 (1971) · Zbl 0264.68040
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.