Типы процедур кластер-анализа - Курсовая работа

.3 Подходы к проблеме кластерного анализа2.2 Меры сходства кластеров3.1 Метод k-среднихКластерный анализ - это совокупность методов, позволяющих классифицировать многомерные наблюдения. Термин кластерный анализ, впервые введенный Трионом (Tryon) в 1939 году, включает в себя более 100 различных алгоритмов. В общем, всякий раз, когда необходимо классифицировать «горы» информации к пригодным для дальнейшей обработки группам, кластерный анализ оказывается весьма полезным и эффективным [2, с.78]. Целью кластерного анализа является образование групп схожих между собой объектов, которые называются кластерами. В отличие от задач классификации, кластерный анализ не требует априорных предположений о наборе данных, не накладывает ограничения на представление исследуемых объектов, позволяет анализировать показатели различных типов данных (интервальным данным, частотам, бинарным данным).Кластер имеет следующие математические характеристики: Центр кластера - это среднее геометрическое место точек в пространстве переменных. Объект относится к кластеру, если расстояние от объекта до центра кластера меньше радиуса кластера. Работа кластерного анализа опирается на два предположения: Первое предположение - рассматриваемые признаки объекта в принципе допускают желательное разбиение совокупности объектов на кластеры. Представим себе, что данные признака х в наборе данных А на два порядка больше данных признака у: значения переменной х находятся в диапазоне от 100 до 700, а значения переменной у - в диапазоне от 0 до 1. Стандартизация (standardization) или нормирование (normalization) приводит значения всех преобразованных переменных к единому диапазону значений путем выражения через отношение этих значений к некой величине, отражающей определенные свойства конкретного признака.В начале работы алгоритма все объекты принадлежат одному кластеру, который на последующих шагах делится на меньшие кластеры, в результате образуется последовательность расщепляющих групп. Дендрограмма описывает близость отдельных точек и кластеров друг к другу, представляет в графическом виде последовательность объединения (разделения) кластеров. Этот метод позволяет выделять кластеры сколь угодно сложной формы при условии, что различные части таких кластеров соединены цепочками близких друг к другу элементов. В результате работы этого метода кластеры представляются длинными «цепочками» или «волокнистыми» кластерами, «сцепленными вместе» только отдельными элементами, которые случайно оказались ближе остальных друг к другу. Этот метод следует использовать, если объекты действительно происходят из различных «рощ», в случаях присутствия кластеров «цепочного» типа, при предположении неравных размеров кластеров.Не все итеративные методы требуют первоначального задания числа кластеров, но позволяют используя несколько алгоритмов, меняя либо число образуемых кластеров, либо установленный порог близости для объединения объектов в кластеры добиваться наилучшего разбиения по задаваемому критерию качества [3, с.160]. На первом шаге из оставшихся (n - k) объектов извлекается точка Xi с координатами (xi1, xi2,., xip) и проверяется, к какому из эталонов она находится ближе всего (используется одна из метрик). Эталон заменяется новым, пересчитанным с учетом присоединенной точки, и вес его (количество объектов, входящих в данный кластер) увеличивается на единицу. Таким образом, через (n - k) шагов все объекты окажутся отнесенными к одному из k кластеров, но на этом процесс разбиения не заканчивается. Обычно, когда результаты кластерного анализа методом K средних получены, можно рассчитать средние для каждого кластера по каждому измерению, чтобы оценить, насколько кластеры различаются друг от друга.Кластерный анализ включает в себя набор различных алгоритмов классификации (в качестве примера метода кластерного анализа можно привести метод дендрограмм). Методы кластерного анализа дополняется методами дискриминантного анализа, которые позволяют определить границы между кластерами и использовать их для решения задач анализа и классификации данных. Результаты кластер-анализа чаще всего представляются графически, в виде дендрограммы («дерева»), показывающей порядок объединения объектов в кластеры. При кластеризации «с обучением» результаты могут быть представлены в виде списков объектов, отнесенных к каждому классу. Основными преимуществами кластер-анализа являются отсутствие ограничений на распределение переменных, используемых в анализе; возможность классификации (кластеризации) даже в тех случаях, когда нет никакой априорной информации о количестве и характере классов; универсальность (кластерный анализ может применяться не только к совокупностям объектов, но также к наборам переменных или любых других единиц анализа).

Содержание

Введение

Глава 1. Сущность кластерного анализа

1.1 Понятие, цели и задачи кластерного анализа