Лабораторная работа 4: ИТИБ. Алгоритмы кластерного анализа данных вариант 227

Цель работы

Исследовать применение основных алгоритмов кластерного анализа, включая их модификации, на примере различных типов данных.

Постановка задачи

Кластерный анализ – процедура, выполняющая сбор данных, содержащих информацию о выборке объектов, и затем упорядочивающая объекты в сравнительно однородные группы на основе какого-либо признака(-ов). Формально: Пусть – X множество объектов, Y– множество кластеров. Задана функция расстояния между объектами . Имеется конечная обучающая выборка объектов . Требуется разбить выборку на непересекающиеся подмножества, называемые кластерами, так, чтобы каждый кластер состоял из объектов, близких по метрике , а объекты разных кластеров существенно отличались. При этом каждому объекту приписывается номер кластера . Алгоритм кластеризации – это функция , которая любому объекту ставит в соответствие номер кластера . Множество Y в некоторых случаях известно заранее, однако чаще ставится задача определить оптимальное число кластеров, с точки зрения того или иного критерия качества кластеризации.

Существует множество методов кластерного анализа, наиболее известные из них:

• вероятностные алгоритмы (k-средних),
• подходы на основе применения искусственного интеллекта (нейронная сеть Кохонена),
• теоретико-графовый подход и др.

Алгоритм k-средних (k-means) стремится минимизировать суммарное квадратичное отклонение точек кластеров от центров этих кластеров:

,

где k – количество кластеров (задано заранее), – полученные кластеры, i = 1, …, k и – центры масс . Суть алгоритма заключается в следующем: на каждой итерации перевычисляется центр масс для каждого кластера, полученного на предыдущем шаге, затем кластеризуемые точки разбиваются на кластеры вновь в соответствии с тем, какой из новых центров оказался ближе по выбранной метрике. Алгоритм завершается, когда на l-той итерации не происходит изменения центра масс кластеров. Это происходит за конечное число итераций, так как количество возможных разбиений конечного множества конечно, и на каждом шаге суммарное квадратичное отклонение S не увеличивается, поэтому зацикливание невозможно.

Нейронные сети Кохонена – класс нейронных сетей, основным элементом которых является слой Кохонена, состоящий из k адаптивных линейных сумматоров. Они имеют одинаковое число входов m и получают на свои входы вектор входных сигналов . На выходе j-го линейного элемента получаем сигнал

где j – номер нейрона, – пороговый коэффициент, i – номер входа, – весовой коэффициент i-го входа j-го нейрона.

Выходные сигналы слоя Кохонена обрабатываются по правилу «победитель получает всё»: наибольший сигнал превращается в единичный, остальные обращаются в ноль. Таким образом, применительно к задаче кластеризации каждому j-му нейрону ставятся в соответствие точки-центры кластеров, для входного вектора вычисляются расстояния , и тот нейрон, до которого это расстояние минимально, выдает единицу, остальные – ноль.

Алгоритм: НС Кохонена;

Исходные кластеризуемые данные: Выборка колледжей г.Москвы, http://data.mos.ru/datasets/546 координаты местоположения (X,Y);

: Принадлежность округу Москвы (Евклидово расстояние до координат () центра округа)