Кластерный анализ

Кластерный анализ Это статистическая процедура, выполняющая опытный сбор данных и затем упорядочивающая объекты выборки в однородные группы (кластеры) для решения следующих задач: 1) Разработка типологии и классификации; 2) Исследование концептуальных схем группирования объектов; 3) Выдвижение и проверка статистических гипотез. Цели кластеризации: 1) Понимание поведения данных путём выявления их структуры; 2) Сжатие выборки; 3) Обнаружение нетипичных объектов. На рисунке наглядно представлено разбиение исходного множества объектов на упорядоченные кластеры. Методы кластерного анализа. Общепринятой классификации методов кластеризации не существует, но можно выделить ряд групп подходов (некоторые методы можно отнести сразу к нескольким группам и потому предлагается рассматривать данную типизацию как некоторое приближение к реальной классификации методов кластеризации): • Метод средних. Действие алгоритма таково, что он стремится минимизировать суммарное квадратичное отклонение точек кластеров от центров этих кластеров; • Метод медиан. Это вариация метода средних, где для определения центроида кластера вместо среднего вычисляется медиана; • EM-алгоритм. Это алгоритм, используемый в статистике для нахождения оценок максимального правдоподобия параметров вероятностных моделей, в случае, когда модель зависит от некоторых скрытых переменных. Каждая итерация алгоритма состоит из двух шагов. На E-шаге (expectation) вычисляется ожидаемое значение функции правдоподобия, при этом скрытые переменные рассматриваются как наблюдаемые. На M-шаге (maximization) вычисляется оценка максимального правдоподобия, таким образом увеличивается ожидаемое правдоподобие, вычисляемое на E-шаге. Затем это значение используется для E-шага на следующей итерации. Алгоритм выполняется до сходимости; • Алгоритмы семейства FOREL. Это алгоритм кластеризации, основанный на идее объединения в один кластер объектов в областях их наибольшего сгущения. Выборка разбивается на такое (заранее неизвестное число) таксонов, чтобы сумма расстояний от объектов кластеров до центров кластеров была минимальной по всем кластерам. Задача — выделить группы максимально близких друг к другу объектов, которые в силу гипотезы схожести и будут образовывать кластеры; • Нейронная сеть Кохонена. Это класс нейронных сетей, основным элементом которых является слой Кохонена, который состоит из адаптивных линейных сумматоров («линейных формальных нейронов»). Как правило, выходные сигналы слоя Кохонена обрабатываются по правилу «победитель забирает всё»: наибольший сигнал превращается в единичный, остальные обращаются в ноль; • Генетический алгоритм. Это эвристический алгоритм поиска, используемый для решения задач оптимизации и моделирования путём случайного подбора, комбинирования и вариации искомых параметров с использованием механизмов, аналогичных естественному отбору в природе. Задача формализуется таким образом, чтобы её решение могло быть закодировано в виде вектора («генотипа») генов, где каждый ген может быть битом, числом или неким другим объектом. Некоторым, обычно случайным, образом создаётся множество генотипов начальной популяции. Они оцениваются с использованием «функции приспособленности», в результате чего с каждым генотипом ассоциируется определённое значение («приспособленность»), которое определяет насколько хорошо фенотип, им описываемый, решает поставленную задачу. Из полученного множества решений («поколения») с учётом значения «приспособленности» выбираются решения (обычно лучшие особи имеют большую вероятность быть выбранными), к которым применяются «генетические операторы» (в большинстве случаев «скрещивание» — crossover и «мутация» — mutation), результатом чего является получение новых решений. Для них также вычисляется значение приспособленности, и затем производится отбор («селекция») лучших решений в следующее поколение. Этот набор действий повторяется итеративно, так моделируется «эволюционный процесс», продолжающийся несколько жизненных циклов (поколений), пока не будет выполнен критерий остановки алгоритма. Таким критерием может быть: нахождение глобального, либо субоптимального решения; исчерпание числа поколений, отпущенных на эволюцию; исчерпание времени, отпущенного на эволюцию. Генетические алгоритмы служат, главным образом, для поиска решений в многомерных пространствах поиска. • Иерархическая кластеризация. Это совокупность алгоритмов упорядочивания данных, визуализация которых обеспечивается с помощью графов. Алгоритмы упорядочивания данных указанного типа исходят из того, что некое множество объектов характеризуется определённой степенью связности. Предполагается наличие вложенных групп (кластеров различного порядка). Под дендрограммой обычно понимается дерево, то есть граф без циклов, построенный по матрице мер близости. Дендрограмма позволяет изобразить взаимные связи между объектами из заданного множества. Для создания дендрограммы требуется матрица сходства (или различия), которая определяет уровень сходства между парами объектов, которая может быть обработана следующими методами: 1) Метод одиночной связи («метод ближайшего соседа»); 2) Метод полной связи («метод дальнего соседа»); 3) Метод средней связи; 4) Невзвешенный; 5) Взвешенный (медианный); 6) Центроидный. ПРИМЕР: Провести кластеризацию шести объектов, каждый из которых характеризуется двумя признаками, иерархическим методом «ближайшего соседа». (Замечание: в данной таблице измерение х1 выступает в роли абсциссы точки (координата х), а измерение х2 – в роли ординаты (координата у)). № х1 х2 1 2 8 2 4 10 3 5 7 4 12 6 5 14 6 6 15 4 Решение: 1) В качестве расстояния между объектами принимается наикратчайшее (ближайшее) евклидово расстояние, вычисляемое по формуле длины вектора: В нашем примере расстояние между 1-м и 2-м объектом будет: Расстояние между 1-м и 3-м объектом будет: И так далее вычисляем расстояния по порядку (без повторений, например, между 2-м и 1-м или 3-м и 1-м): 2) Составляем матрицу расстояний и вносим в нее соответствующие найденные расстояния: № 1 2 3 4 5 6 1 2,83 3,16 10,2 12,17 13,6 2 2,83 3,16 8,94 10,77 12,53 3 3,16 3,16 7,07 9,06 10,44 4 10,2 8,94 7,07 2 3,61 5 12,17 10,77 9,06 2 2,24 6 13,6 12,53 10,44 3,61 2,24 Из этой матрицы следует, что объекты № 4 и № 5 наиболее близки по расстоянию (т.к. расстояние между ними наименьшее ), и поэтому они объединяются в один кластер. 3) При формировании матрицы расстояний на следующей итерации объединяем столбцы и строки объектов № 4 и № 5, выбирая и внося в новую матрицу наименьшие расстояния между ними. Остальные значения удаляются: № 1 2 3 4 5 6 1 2,83 3,16 10,2 12,17 13,6 2 2,83 3,16 8,94 10,77 12,53 3 3,16 3,16 7,07 9,06 10,44 4 10,2 8,94 7,07 2 3,61 5 12,17 10,77 9,06 2 2,24 6 13,6 12,53 10,44 3,61 2,24 Получаем следующую матрицу расстояний: № 1 2 3 4;5 6 1 2,83 3,16 10,2 13,6 2 2,83 3,16 8,94 12,53 3 3,16 3,16 7,07 10,44 4;5 10,2 8,94 7,07 2,24 6 13,6 12,53 10,44 2,24 4) Находим следующее наименьшее расстояние: и формируем следующий кластер: № 1 2 3 4;5 6 1 2,83 3,16 10,2 13,6 2 2,83 3,16 8,94 12,53 3 3,16 3,16 7,07 10,44 4;5 10,2 8,94 7,07 2,24 6 13,6 12,53 10,44 2,24 Получается следующая матрица расстояний: № 1 2 3 4;5;6 1 2,83 3,16 10,2 2 2,83 3,16 8,94 3 3,16 3,16 7,07 4;5;6 10,2 8,94 7,07 5) Продолжаем итерации формирования кластеров, пока не получим окончательную матрицу размером 2х2. Но в общем случае итерации останавливаются, если выполняется некоторое заданное условие (например, какое-то определенное расстояние или количество кластеров – на усмотрение эксперта). № 1;2 3 4;5;6 1;2 3,16 8,94 2 3,16 7,07 4;5;6 8,94 7,07 № 1;2;3 4;5;6 1;2;3 7,07 4;5;6 7,07 В итоге мы получили два кластера: первый содержит данные № 1, 2 и 3, второй содержит данные № 4, 5 и 6. Общее расстояние между кластерами равно 7,07. Результаты можно представить в виде дендрограммы (вам это делать необязательно, Excel её не строит): Строим график для наглядности результатов кластерного анализа: Так как в нашем примере очень мало данных, то из графика наглядно видно, что два кластера сформированы правильно. ЗАДАНИЕ: Провести кластеризацию объектов на три кластера: № х1 х2 1 2 3 2 2 5 3 2 7 4 2 8 5 2 9 6 3 6 7 3 8 8 4 7 9 4 9 10 9 2 11 10 6 12 11 1 13 11 4 14 11 7 15 12 2 16 13 3 17 13 5 18 13 7 19 14 6 20 21 5