Анализ основных индексов оценки качества алгоритмов кластеризации
ВВЕДЕНИЕ
Кластеризация (кластерный анализ) – совокупность методов, выполняющих выделение групп объектов, называемых кластерами, таким образом, чтобы объекты одного кластера были похожи, а объекты разных кластеров существенно различались. Иллюстрация работы алгоритма представлена на рисунке 1 (рис.1).
Рис. SEQ Рис. \* ARABIC 1 Иллюстрация работы алгоритма кластеризации
В решении задачи кластеризации требуется определить количество кластеров будет распределяться исходное множество набора данных. Таким образом, могут быть получены различные результаты. Рассмотрим пример кластеризации определенного набора данных на 3, 4 и 5 кластеров (рис.2).
Рис. SEQ Рис. \* ARABIC 2 Кластеризация на 3, 4 и 5 кластеров
Интуитивно, из данной многомерной диаграммы видно, что разделение на 3 кластера является оптимальным для данной задачи. Разделение на 4 кластера является нерациональным, так как в кластер под номером 2 (зеленый цвет) входят только несколько объектов. Также, как и 5 кластеров
Содержание не найдено
Литература
1. Н. Паклин, В. Орешков Бизнес-аналитика: от данных к знаниям. Учебное пособие. 2-е издание, исправленное, 2013. – 693 с.
2. Сивоголовко Е.В. Методы оценки качества четкой кластеризации. // Компьютерные инструменты в образовании. - Тверь, 2011 - Вып. 4 (96) - С. 14-31
3. Загоруйко Н.Г. Прикладные методы анализа данных и знаний. - Новосибирск: ИМ СО РАН, 1999. - 270 с.
4. M. Halkidi, M. Vazirgiannis, I. Batistakis. Оценка схемы качества в процессе кластеризации //Proceedings of PKDD, 2000.
5. Michael J. A. Berry, Gordon Linoff. Методы добычи данных для маркетинга, продаж и поддержки клиентов. John Willey & Sons, Inc, 1996.
6. Rajesh N. Dave. «Проверка нечетких разделов, полученных с помощью кластеризации c-shells», Pattern Recognition Letters, Vol .17, 1996 – 613-623 c.
7. J. C. Dunn. «Хорошо разделенные кластеры и оптимальные нечеткие разделы», J. Cybern. Vol.4, 1974 – 95-104 c.
8. Martin Ester, Hans-Peter Kriegel, Jorg Sander, Xiaowei Xu. «A Density-Based Algorithm for Discovering Clusters in Large Spatial Databases with Noise», Proceedings of 2nd Int. Conf. On Knowledge Discovery and Data Mining, Portland, OR, 1996 – 226-231 c.
9. Gath, B. Geva. «Unsupervised Optimal Fuzzy Clustering». IEEE Transactions on Pattern Analysis and Machine Intelligence, Vol 11, No7, July 1989.
10. Alexander Hinneburg, Daniel Keim. «An Efficient Approach to Clustering in Large Multimedia Databases with Noise». Proceeding of KDD ’98, 1998.
11. Zhexue Huang. «A Fast Clustering Algorithm to Cluster very Large Categorical Data Sets in Data Mining», DMKD, 1997.
12. Ramze Rezaee, B.P.F. Lelieveldt, J.H.C Reiber. «A new cluster validity index for the fuzzy c-mean», Pattern Recognition Letters, 19, pp237-246, 1998.
13. Padhraic Smyth. «Clustering using Monte Carlo Cross-Validation». KDD 1996, 126-133 c.
14. C. Sheikholeslami, S. Chatterjee, A. Zhang. «WaveCluster: A-MultiResolution Clustering Approach for Very Large Spatial Database». Proceedings of 24th VLDB Conference, New York, USA, 1998.
15. S. Theodoridis, K. Koutroubas. Pattern recognition, Academic Press, 1999.
16. Xunali Lisa Xie, Genardo Beni. «A Validity measure for Fuzzy Clustering», IEEE Transactions on Pattern Analysis and machine Intelligence, Vol
Оценка результатов алгоритма кластеризации производится в величинах, которые включают в себя векторы набора данных (например, матрица близости). Третий подход к оценке качества кластеризации основан на относительных критериях. Основной идеей является оценка кластеризации путем сравнения ее с другими схемами кластеризации, полученными тем же алгоритмом, но с различными значениями параметров.
Итак, два первых подхода основаны на статистических тестах, и их основным недостатком является высокая стоимость вычислений. Более того, индексы, связанные с этими подходами, направлены на вычисление параметров, которые лишь подтверждают первоначально заданную схему.
Третий подход к оценке кластеризации, основан на относительных критериях. В этом подходе для оценки и выбора оптимальной схемы кластеризации предлагается рассмотрения двух критериев [5]:
1.компактность, члены каждого кластера должны находиться как можно ближе друг к другу;