Анализ основных индексов оценки качества алгоритмов кластеризации
ВВЕДЕНИЕ
Кластеризация (кластерный анализ) – совокупность методов, выполняющих выделение групп объектов, называемых кластерами, таким образом, чтобы объекты одного кластера были похожи, а объекты разных кластеров существенно различались. Иллюстрация работы алгоритма представлена на рисунке 1 (рис.1).
В решении задачи кластеризации требуется определить количество кластеров будет распределяться исходное множество набора данных. Таким образом, могут быть получены различные результаты. Рассмотрим пример кластеризации определенного набора данных на 3, 4 и 5 кластеров (рис.2).
Литература
- Н. Паклин, В. Орешков Бизнес-аналитика: от данных к знаниям. Учебное пособие. 2-е издание, исправленное, 2013. – 693 с.
- Сивоголовко Е.В. Методы оценки качества четкой кластеризации. // Компьютерные инструменты в образовании. - Тверь, 2011 - Вып. 4 (96) - С. 14-31
- Загоруйко Н.Г. Прикладные методы анализа данных и знаний. - Новосибирск: ИМ СО РАН, 1999. - 270 с.
- M. Halkidi, M. Vazirgiannis, I. Batistakis. Оценка схемы качества в процессе кластеризации //Proceedings of PKDD, 2000.
- Michael J. A. Berry, Gordon Linoff. Методы добычи данных для маркетинга, продаж и поддержки клиентов. John Willey & Sons, Inc, 1996.
- Rajesh N. Dave. «Проверка нечетких разделов, полученных с помощью кластеризации c-shells», Pattern Recognition Letters, Vol .17, 1996 – 613-623 c.
- J. C. Dunn. «Хорошо разделенные кластеры и оптимальные нечеткие разделы», J. Cybern. Vol.4, 1974 – 95-104 c.
- 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.
- Gath, B. Geva. «Unsupervised Optimal Fuzzy Clustering». IEEE Transactions on Pattern Analysis and Machine Intelligence, Vol 11, No7, July 1989.
- Alexander Hinneburg, Daniel Keim. «An Efficient Approach to Clustering in Large Multimedia Databases with Noise». Proceeding of KDD ’98, 1998.
- Zhexue Huang. «A Fast Clustering Algorithm to Cluster very Large Categorical Data Sets in Data Mining», DMKD, 1997.
- 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.
- Padhraic Smyth. «Clustering using Monte Carlo Cross-Validation». KDD 1996, 126-133 c.
- 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.
- S. Theodoridis, K. Koutroubas. Pattern recognition, Academic Press, 1999.
- Xunali Lisa Xie, Genardo Beni. «A Validity measure for Fuzzy Clustering», IEEE Transactions on Pattern Analysis and machine Intelligence, Vol13, No4, August 1991.
Схема процесса кластеризации данных включает следующие этапы:
- выделение существенных характеристик исследуемых объектов;
- определение меры сходства;
- разбиение набора данных на кластеры;
- оценка качества кластеризации;
- представление результатов.
На первых трех этапах могут быть допущены существенные ошибки, которые могут исказить результат. По этой причине этап – оценка качества кластеризации – является наиболее значимым.
Кластеризация не может быть «абсолютно объективной». Большинство реальных объектов имеют число свойств, стремящееся к бесконечности, и выделение конечного набора этих свойств субъективно. Методы оценки качества разбиения также выбираются субъективно. Если известна цель, для достижения которой строится разбиение, то качество проверяется тем, хорошо ли кластеризация способствует достижению этой цели.