Термин "cluster" буквально переводится на русский язык как "скопление". Он является многозначным и применяется в самых различных областях от музыки до ядерной физики. В интеллектуальном анализе данных используют следующее определение: кластер – это группа элементов, характеризуемых общим свойством. Сама же задача кластеризации может быть сформулирована следующим образом: разбиение множества на однородные группы так, чтобы элементы в одной группе были максимально схожи друг с другом, а элементы из разных групп значительно отличались. Кластеризация помогает обнаружить или подтвердить имеющиеся во множестве закономерности и успешно используется как в естественно-научных, так и в гуманитарных и экономических областях. Кластерные структуры разделяют на четкие (crisp) и нечеткие (fuzzy) в зависимости от того, допускается ли в них пересечение кластеров. В четких структурах кластеры не пересекаются, и каждый элемент принадлежит одному единственному кластеру. В нечетких структурах кластеры пересекаются, и элемент может принадлежать любому числу кластеров с разной степенью принадлежности.

Оценка качества полученной структуры кластеров, несомненно, является важным этапом в процессе кластеризации, однако ей зачастую уделяется гораздо меньше внимания, чем подбору векторного представления данных, метрики схожести и собственно алгоритму кластеризации, а то и не уделяется вовсе. Несмотря на огромное разнообразие предметных областей, типов и структур данных, применение алгоритмов нахождения кластерной структуры предполагает представление кластеризуемого множества в виде набора многомерных векторов. Это дает методам оценки качества основание для того, чтобы в некотором роде абстрагироваться от конкретной предметной области или же от типа данных, хотя, безусловно, эти особенности влияют как на выбор алгоритмов, так и на последующую интерпретацию результатов кластеризации. Как правило, для оценки качества используются интегральные количественные показатели, часто называемые индексами или метриками. Наиболее широко используемые индексы оценки качества рассматривают свойства кластерной структуры как таковой без ее связи с предметной областью. Этими свойствами обычно являются компактность кластеров, отделимость кластеров, их диаметр, плотность, межкластерное расстояние и так далее.

В докладе приводится обзор наиболее популярных индексов оценки качества четкой кластеризации, обсуждаются их свойства, применимость в различных контекстах и соотношение с алгоритмами кластеризации. Рассматривается эффективность индексов качества для множеств с различной структурой: случайное распределение данных, гауссово распределение данных, вложенные кластеры, плохо отделимые кластеры. Делаются выводы о том, индексы с какими свойствами наиболее точны при оценке разбивающих (partitional) или плотностных (density-based) алгоритмов кластеризации.

Слайды к докладу в формате PDF: sivogolovko20111124.pdf

Литература:

1. M. Halkidi, Y. Batistakis, M. Vazirgiannis. On clustering validation techniques. Intelligent Information Systems Journal 17(2-3), 107-145, 2001.
2. S. Theodoridis, K. Koutroumbas. Pattern recognition, Academic Press, San Diego, CA, pp 740-742, 1999.
3. R.B. Calinski, J. Harabasz. A Dendrite Method for Cluster Analysis. Comm. in Statistics, vol. 3, pp. 1-27, 1974.
4. J.C. Dunn. Well separated clusters and optimal fuzzy partitions. J. Cybern.Vol.4, pp. 95-104, 1974.
5. N. R. Pal, J. Biswas. Cluster Validation using graph theoretic concepts. Pattern Recognition, Vol. 30(6), 1997.
6. D. L. Davies, D. W. Bouldin. A cluster separation measure. IEEE Transactions on Pattern Analysis and Machine Intelligence, Vol. 1, No2, 1979.
7. G.W. Milligan, M.C. Cooper. An Examination of Procedures for Determining the Number of Clusters in a Data Set. Psychometrika, Vol.50, pp 159-179, 1985.
8. C.H. Chow, M.C. Su, Lai Eugene. A new Validity Measure for Clusters with Different Densities. Pattern Anal. Applications, vol. 7, 2004.
9. C.H. Chow, M.C. Su, Lai Eugene. Symmetry as A new measure for Cluster Validity. 2nd WSEAS Int. Conf. Scientific Computation and Soft Computing, pp. 209-213, 2002.
10. M. Halkidi, M. Vazirgiannis, I. Batistakis. Quality scheme assessment in the clustering process. Proceedings of PKDD, Lyon, France, 2000.
11. M. Halkidi, M. Vazirgiannis. Clustering Validity Assessment: Finding the optimal partitioning of a data set. Proc. of ICDM, 2001.
12. Subhash Sharma: Applied multivariate techniques, John Wiley and Sons, Inc., 1996
13. L. Kaufman and P. Rousseeuw, Finding Groups in Data. An Introduction to Cluster Analysis, Wiley, pp. 87-88, 2005.
14. U. Maulik, S. Bandyopadhyay: Performance evaluation of some clustering algorithms and validity indices. IEEE Transactions Pattern Analysis Machine Intelligence, vol. 24(12), pp 1650–1654, 2002.
15. M. K. Pakhira, S. Bandyopadhyay, U. Maulik. Validity index for crisp and fuzzy clusters. Pattern Recognition, 37(3) pp 487 – 501, 2004.
16. E. R. Hruschka, L. Vendramin, R. J. G. B. Campello. On the Comparison of Relative Clustering Validity Criteria. In: 2009 SIAM International Conference on Data Mining (SDM 09), v. 1. p. 733-744, 2009.
17. S. Saitta, B. Raphael, I. F.C. Smit. A Bounded Index for Cluster Validity. On Proc. of the 5th Int. Conf. on Machine Learning and Data Mining in Pattern Recognition, 2007.
18. M. Halkidi, M. Vazirgiannis. A density-based cluster validity approach using multi-representatives. Pattern Recognition Letters, vol. 29(6), pp 773-786, 2008.
19. F. Kovacs, R. Ivancsy. Cluster Validity Measurement for Arbitrary Shaped Clusters. Proc. of the 5th WSEAS Int. Conf. on Art. Intelligence, Knowledge Engineering and DB, 2008.
20. E. Rendon, R. Garcia, I. Abundez, C. Gutierrez, E. Gasca, F. D. Razo, A. Gonzalez. NIVA: A Robust Cluster Validity. 12th WSEAS Int. Conf. on Communications.
21. D.-J. Kim, Y.-W. Park, D.-J. Park. A novel validity index for determination of the optimal number of clusters. IEICE Trans. Inform. Syst. vol. E84-D (2), pp. 281–285, 2001.
22. J. Hartigan. Clustering Algorithms. John Wiley & Sons, New York, NY, 1975.
23. J. Hartigan, M. Wong. Algorithm AS136: A k-means clustering algorithm. Applied Statistics, vol. 28, pp. 100-108, 1979.
24. M. Ester, H-P Kriegel, J. Sander, X. Xu. A density-based algorithm for discovering clusters in large spatial databases with noise. In Proc. of the 2nd ACM SIGKDD, pp 226-231, 1996.
25. R. A. Fisher. The Use of Multiple Measurements in Taxonomic Problems. Annals of Eugenics vol. 7(2), pp. 179–188, 1936.
26. I. Mierswa, M. Wurst, R. Klinkenberg, M. Scholz, T. Euler: YALE: Rapid Prototyping for Complex Data Mining Tasks, in Proceedings of the 12th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD-06), 2006.