Most of fuzzy clustering algorithms have some
discrepancies, e.g. they are not able to detect clusters with convex
shapes, the number of the clusters should be a priori known, they
suffer from numerical problems, like sensitiveness to the
initialization, etc. This paper studies the synergistic combination of
the hierarchical and graph theoretic minimal spanning tree based
clustering algorithm with the partitional Gath-Geva fuzzy clustering
algorithm. The aim of this hybridization is to increase the robustness
and consistency of the clustering results and to decrease the number
of the heuristically defined parameters of these algorithms to
decrease the influence of the user on the clustering results. For the
analysis of the resulted fuzzy clusters a new fuzzy similarity measure
based tool has been presented. The calculated similarities of the
clusters can be used for the hierarchical clustering of the resulted
fuzzy clusters, which information is useful for cluster merging and
for the visualization of the clustering results. As the examples used
for the illustration of the operation of the new algorithm will show,
the proposed algorithm can detect clusters from data with arbitrary
shape and does not suffer from the numerical problems of the
classical Gath-Geva fuzzy clustering algorithm.
[1] Augustson J.G., Minker J., "An analysis of some graph theoretical
clustering techniques", J. ACM Vol.17, 4, pp. 571-588., 1970.
[2] Backer F.B., Hubert L.J., "A graph-theoretic approach to goodness-of-fit
in complete-link hierarchical clustering" J. Am. Stat. Assoc. Vol. 71, pp.
870-878., 1976.
[3] Barrow, J.D., Bhavsar, S.P., Sonoda, D.H., "Minimal spanning trees,
filaments and galaxy clustering" In Monthly Notices of the Royal
Astronomical Society, 216:17-35., 1985.
[4] Bezdek, J.C, Ehrlich, R., Full, W., "FCM:Fuzzy C-Means Algorithm",
Computers and Geoscience, 1984.
[5] Bezdek, J.C., Clarke, L.P., Silbiger, M.L., Arrington, J.A., Bensaid,
A.M., Hall, L.O., Murtagh, R.F., "Validity-guided (re)clustering with
applications to image segmentation" IEEE Transactions on Fuzzy
Systems, 4:112-123., 1996.
[6] Dunn, J.C., "Well separated clusters and optimal fuzzy partitions",
Journal Cybernetics, 4: 95-104., 1974.
[7] Forina, M., Oliveros, C., Concepcin M., Casolino, C., Casale, M.,
"Minimum spanning tree: ordering edges to identify clustering structure"
In Analytica Chimica Acta, 515: 43-53., 2004.
[8] Gath I., Geva, A.B. "Unsupervised optimal fuzzy clustering", IEEE
Transactions on Pattern Analysis and Machine Intelligence, Vol. 11(7),
1989.
[9] Gonzales-Barrios, J.M., Quiroz, A.J., "A clustering procedure based on
the comparison between the k nearest neighbors graph and the minimal
spanning tree" In Statistics & Probability Letter, 62: 23-34., 2003.
[10] Gower J.C., Ross G.J.S., "Minimal Spanning Trees and Single Linkage
Cluster Analysis", Applied Statistics, Vol. 18, pp. 54-64., 1969.
[11] Jain, A.K., Dubes, R.C., "Algorithms for Clustering Data", Prentice-
Hall advanced reference series, Prentice-Hall, Inc., Upper Saddle River,
NJ., 1988.
[12] Kruskal, J.B., "On the shortest spanning subtree of a graph and the
traveling salesman problem" In American Mathematical Society, 7: 48-
50., 1956.
[13] Päivinen, N., "Clustering with a minimum spanning tree of scale-freelike
structure", In Pattern Recognition Letters, 26(7): 921-930., 2005.
[14] Prim, R., "Shortest connection networks and some generalizations" Bell
System Technical Journal, Vol. 36, pp. 1389-1401., 1957.
[15] Raghavan V.V., YU C.T., "A comparison of the stability characteristics
of some graph theoretic clustering methods", IEEE Trans. Pattern Anal.
Mach. Intell. 3, pp. 3-402., 1981.
[16] Varma, S., Simon, R., "Iterative class discovery and feature selection
using Minimal Spanning Trees" BMC Bioinformatics, Vol. 5, pp. 126-
134., 2004.
[17] Zahn, C.T., "Graph-theoretical methods for detecting and describing
gestalt clusters" IEEE Transaction on Computers, C20: 68-86., 1971.
[1] Augustson J.G., Minker J., "An analysis of some graph theoretical
clustering techniques", J. ACM Vol.17, 4, pp. 571-588., 1970.
[2] Backer F.B., Hubert L.J., "A graph-theoretic approach to goodness-of-fit
in complete-link hierarchical clustering" J. Am. Stat. Assoc. Vol. 71, pp.
870-878., 1976.
[3] Barrow, J.D., Bhavsar, S.P., Sonoda, D.H., "Minimal spanning trees,
filaments and galaxy clustering" In Monthly Notices of the Royal
Astronomical Society, 216:17-35., 1985.
[4] Bezdek, J.C, Ehrlich, R., Full, W., "FCM:Fuzzy C-Means Algorithm",
Computers and Geoscience, 1984.
[5] Bezdek, J.C., Clarke, L.P., Silbiger, M.L., Arrington, J.A., Bensaid,
A.M., Hall, L.O., Murtagh, R.F., "Validity-guided (re)clustering with
applications to image segmentation" IEEE Transactions on Fuzzy
Systems, 4:112-123., 1996.
[6] Dunn, J.C., "Well separated clusters and optimal fuzzy partitions",
Journal Cybernetics, 4: 95-104., 1974.
[7] Forina, M., Oliveros, C., Concepcin M., Casolino, C., Casale, M.,
"Minimum spanning tree: ordering edges to identify clustering structure"
In Analytica Chimica Acta, 515: 43-53., 2004.
[8] Gath I., Geva, A.B. "Unsupervised optimal fuzzy clustering", IEEE
Transactions on Pattern Analysis and Machine Intelligence, Vol. 11(7),
1989.
[9] Gonzales-Barrios, J.M., Quiroz, A.J., "A clustering procedure based on
the comparison between the k nearest neighbors graph and the minimal
spanning tree" In Statistics & Probability Letter, 62: 23-34., 2003.
[10] Gower J.C., Ross G.J.S., "Minimal Spanning Trees and Single Linkage
Cluster Analysis", Applied Statistics, Vol. 18, pp. 54-64., 1969.
[11] Jain, A.K., Dubes, R.C., "Algorithms for Clustering Data", Prentice-
Hall advanced reference series, Prentice-Hall, Inc., Upper Saddle River,
NJ., 1988.
[12] Kruskal, J.B., "On the shortest spanning subtree of a graph and the
traveling salesman problem" In American Mathematical Society, 7: 48-
50., 1956.
[13] Päivinen, N., "Clustering with a minimum spanning tree of scale-freelike
structure", In Pattern Recognition Letters, 26(7): 921-930., 2005.
[14] Prim, R., "Shortest connection networks and some generalizations" Bell
System Technical Journal, Vol. 36, pp. 1389-1401., 1957.
[15] Raghavan V.V., YU C.T., "A comparison of the stability characteristics
of some graph theoretic clustering methods", IEEE Trans. Pattern Anal.
Mach. Intell. 3, pp. 3-402., 1981.
[16] Varma, S., Simon, R., "Iterative class discovery and feature selection
using Minimal Spanning Trees" BMC Bioinformatics, Vol. 5, pp. 126-
134., 2004.
[17] Zahn, C.T., "Graph-theoretical methods for detecting and describing
gestalt clusters" IEEE Transaction on Computers, C20: 68-86., 1971.
@article{"International Journal of Information, Control and Computer Sciences:50958", author = "Ágnes Vathy-Fogarassy and Balázs Feil and János Abonyi", title = "Minimal Spanning Tree based Fuzzy Clustering", abstract = "Most of fuzzy clustering algorithms have some
discrepancies, e.g. they are not able to detect clusters with convex
shapes, the number of the clusters should be a priori known, they
suffer from numerical problems, like sensitiveness to the
initialization, etc. This paper studies the synergistic combination of
the hierarchical and graph theoretic minimal spanning tree based
clustering algorithm with the partitional Gath-Geva fuzzy clustering
algorithm. The aim of this hybridization is to increase the robustness
and consistency of the clustering results and to decrease the number
of the heuristically defined parameters of these algorithms to
decrease the influence of the user on the clustering results. For the
analysis of the resulted fuzzy clusters a new fuzzy similarity measure
based tool has been presented. The calculated similarities of the
clusters can be used for the hierarchical clustering of the resulted
fuzzy clusters, which information is useful for cluster merging and
for the visualization of the clustering results. As the examples used
for the illustration of the operation of the new algorithm will show,
the proposed algorithm can detect clusters from data with arbitrary
shape and does not suffer from the numerical problems of the
classical Gath-Geva fuzzy clustering algorithm.", keywords = "Clustering, fuzzy clustering, minimal spanning tree,cluster validity, fuzzy similarity.", volume = "1", number = "8", pages = "2326-6", }