Технологии интеллектуального анализа данных : учебное пособие

162 На каждом последующем шаге элемент в кластере С 1 , для ко- торого разница между средним расстоянием до элементов, находя- щихся в С 2 и средним расстоянием до элементов, остающихся в С 1 , наибольшая, переносится в С 2 . Переносы элементов из С 1 в С 2 продолжаются до тех пop, по- ка соответствующие разницы средних не станут отрицательными, т.е. пока существуют элементы, расположенные к элементам кла- стера С 2 ближе, чем к элементам кластера С 1 . В результате один кластер делится на два дочерних, один из которых расщепляется на следующем уровне иерархии. Каждый последующий уровень применяет процедуру разделения к одному из кластеров, полученных на предыдущем уровне. Рекурсивное разделение кластеров продолжается, пока все кластеры или не станут сиглетонами (т.е. состоящими из одного объекта), или пока все члены одного кластера не будут иметь нуле- вое отличие друг от друга. Неиерархические алгоритмы. Большую популярность при решении задач кластеризации приобрели алгоритмы, основанные на поиске оптимального в определенном смысле разбиения множе- ства данных на кластеры (группы). Во многих задачах в силу своих достоинств используются именно алгоритмы построения разбие- ния. Данные алгоритмы пытаются сгруппировать данные в класте- ры таким образом, чтобы целевая функция алгоритма разбиения достигала экстремума (минимума). Рассмотрим алгоритмы класте- ризации, основанные на данных методах. Алгоритм k -means (Hard-c-means). Рассмотрим более подроб- но алгоритм на примере данных из табл. 3.14. Для большей нагляд- ности ограничимся двумя параметрами – длиной и шириной чаше- листника. Это позволит представить данные в двумерном простран- стве (рис. 3.15). Точки отмечены номерами объектов.