![]() Главная страница Случайная страница КАТЕГОРИИ: АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника |
Итерационные методы кластерного анализа
Сущность этих методов заключается в том, что процесс классификации начинается с задания некоторых начальных условий (количество образуемых кластеров, порог завершения процесса классификации и т.д.). К итерационным методам кластерного анализа относят метод k -средних (Мак-Куина), метод поиска сгущений, метод взаимного поглощения и др. [12, 43]. Метод k-средних Для реализации данного метода изначально задается число классов, на которые необходимо разбить имеющуюся совокупность из Для начала процедуры классификации задаются р случайно выбранных объектов – эталонов классов (ε). Каждому эталону приписывается порядковый номер, который, одновременно, является номером класса. Из оставшихся n - p объектов извлекается объект и проверяется, к какому из эталонов он находится ближе. Данный объект присоединяется к тому эталону, расстояние до которого наименьшее. Веса и эталоны классов пересчитываются по правилу:
где При этом нулевое приближение строится с помощью случайно выбранных Через n - p итераций все объекты будут отнесены к одному из p кластеров. Для достижения устойчивого разбиения, все n объектов опять разбиваются на p классов. Новое разбиение сравнивается с предыдущим. Если они совпадают, то работа алгоритма завершается, в противном случае алгоритм повторяется.
Метод поиска сгущений Суть данного итерационного алгоритма заключается в применении гиперсферы заданного радиуса, которая перемещается в пространстве классификационных признаков с целью поиска локальных сгущений точек. Метод поиска сгущений требует вычисления матрицы расстояний (матрицы мер сходства) между объектами. Затем выбирается объект, который является первоначальным центром первого кластера. Выбранная точка принимается за центр гиперсферы заданного радиуса Таким образом, работа алгоритма завершается за конечное число шагов, и все точки оказываются распределенными по кластерам. Число образовавшихся кластеров заранее не известно и сильно зависит от выбора радиуса сферы. Некоторые модификации алгоритма позволяют разделить совокупность на заданное число кластеров путем последовательного изменения радиуса сферы. Для оценки устойчивости полученного разбиения целесообразно повторить процесс кластеризации несколько раз для различных значений радиуса сферы, изменяя каждый раз радиус на небольшую величину. Существует несколько способов выбора радиуса сферы. Если Если начинать работу алгоритма с величины
Метод взаимного поглощения Итерационный алгоритм взаимного поглощения также использует идею гиперсферы. Его суть заключается в том, что для каждого i -го объекта определяется свой радиус Сферы с радиусами Изменяя величину Все задачи кластерного анализа в зависимости от назначения можно разделить по следующим критериям:
1. В случае А1 ведется речь о классификации сравнительно небольших по объему совокупностей наблюдений, состоящих как правило из нескольких десятков наблюдений, сюда могут быть отнесены задачи классификации макрообъектов, таких как страны, города, фирмы, предприятия. 2. В случае А2 речь идет о классификации достаточно больших массивов многомерных наблюдений (n – порядка нескольких сотен и тысяч) – классификация индивидуумов, семей, изделий.
Такое разделение задач классификации хотя и условно, но весьма необходимо с точки зрения принципиального различия идей и методов, на основе которых конструируются кластер-процедуры. Так, иерархические кластер-процедуры предназначены в основном для решения задач типа А1Б1, А1Б2, А1Б3, итерационные кластер-процедуры – А2Б1, А2Б2.
|