Практическая работа №5 по курсу «Интеллектуальные системы» Алгоритмы кластеризации

Практическая работа №5 по курсу «Интеллектуальные системы»

Алгоритмы кластеризации

[ Задание ]

Реализовать на практике (в виде графической программы) один из известных алгоритмов кластеризации:

·  Иерархические алгоритмы (*)

·  Минимальное покрывающее дерево

·  Алгоритм k-средних (*)

·  Метод ближайшего соседа

·  Алгоритмы нечеткой кластеризации

·  Применение нейронных сетей

·  Генетические алгоритмы

·  Метод закалки

(*) отмечены рекомендуемые для реализации методы (с точки зрения простоты и наглядности), их краткое описание представлено ниже.

В конце документа приведены требования к разрабатываемой программе.

[ Описание алгоритмов ]

Иерархический метод «Single-link»

На каждом шаге объединяет два кластера с наименьшим расстоянием между двумя наиболее близкими представителями.

Подробнее:

1. Объединяем 2 точки с минимальным расстоянием друг-от-друга в кластер.

2. Вычисляем центр масс полученного кластера. (*)

3. Заменяем кластер точкой с координатами в его центре масс.

(виртуально, не удаляя старых точек с изображения кластера)

4. Повторяем действия с шага 1, пока есть хоть одна точка, не включенная в кластер, либо пока не будет получено требуемое кол-во кластеров (в зависимости от условий задачи).

 

(*) Центр масс – условный центр геометрической фигуры (многоугольника), образованной конечным количеством точек; в простейшем виде может быть вычислен так:

,

где (Xc, Yc,) – координаты центра масс,

(xi, yi,) – координаты i-й точки, входящей в состав кластера

Так, для кластера из двух точек, центр масс будет лежать в середине отрезка, объединяющего эти точки.

Примечание: более подробное описание представленных алгоритмов можно найти в Интернете и/или лекционных материалах.

Пример соотв. кластеризации:

Порядок объединения кластеров:

Алгоритм «К средних»

Центры кластеров задаются заранее: далее происходит привязывание «свободных» точек к заданным кластерам.

1.  Следует случайно выбрать k точек, являющихся начальными «центрами масс» кластеров (любые k из n объектов, или вообще k случайных точек).

2.  Отнести каждый объект к кластеру с ближайшим «центром масс».

3.  Пересчитать «центры масс» кластеров согласно текущему членству.

4.  Если критерий остановки (*) алгоритма не удовлетворен, вернуться к шагу 2.

В качестве критерия остановки обычно выбирают один из двух:

·  Отсутствие перехода объектов из кластера в кластер на шаге 2;

·  Минимальное изменение среднеквадратической ошибки.

Алгоритм чувствителен к начальному выбору «центров масс».

[ Требования к программе и отчетности ]

1.  Данные (координаты точек) должны вводиться в программу в удобном виде (например, кликами мышкой), либо генерироваться автоматически случайным образом. Обязательными задаваемыми параметрами являются 2 числа: N – исходное количество точек, K – требуемое конечное количество кластеров, образованных заданными точками.

2.  Следует поэтапно, графически отобразить последовательность шагов кластеризации, выделяя вновь образуемые кластера границами (кругами/прямыми линиями – см. рис. выше), либо раскрашивая точки, образующие кластера, в различные цвета (*)

3.  Язык/среда разработки программы произвольны (допускается консольный вариант, с применением встроенных графических библиотек). Основное требование – результаты должны быть представлены на экране в графическом виде.

4.  Требуется написать небольшой отчет (на 1-2 страницы), по работе с программой, включающий: описание алгоритма вычислений, формат ввода-вывода данных, примеры работы программы (со скриншотами).

5.  Задание можно выполнять индивидуально, либо в группах по 2-3 человека. Каждый участник группы должен быть готов объяснить алгоритм вычислений и пояснить работу произвольного фрагмента программы.

(*) Алгоритм раскраски: изначально все точки должны быть окрашены в один цвет; Далее первая пара точек образует кластер: они перекрашиваются в один цвет (который м. б. задан случайно); далее все точки, присоединяемы к вновь образованному кластеру, окрашиваются в такой же цвет, что и кластер. Т. о., локальные скопления точек будут окрашены в разные цвета.