Практическая работа №6: Кластерный анализ. Метод k-средних

Цель работы

Освоение основных понятий и некоторых методов кластерного анализа, в частности, метода k-means.

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

Дано конечное множество из объектов, представленных двумя признаками (в качестве этого множества принимаем исходную двумерную выборку, сформированную ранее в лабораторной работе №4). Выполнить разбиение исходного множества объектов на конечное число подмножеств (кластеров) с использованием метода k-means. Полученные результаты содержательно проинтерпретировать.

Порядок выполнения работы

Нормализовать множество точек из предыдущего раздела, отобразить полученное множество.

Определить «грубую» верхнюю оценку количества кластеров: , где – число точек.

Реализовать алгоритм k-means в двух вариантах:

пересчет центра кластера осуществляется после каждого изменения его состава;

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

На каждом шаге процедуры разбиения методом k-means вычислять функционалы качества полученного разбиения:

– сумма по всем кластерам квадратов расстояний элементов кластеров до центров соответствующих кластеров;

– сумма по всем кластерам внутрикластерных расстояний между элементами кластеров;

– сумма по всем кластерам внутрикластерных дисперсий (относительно центров кластеров).

Отобразить полученные кластеры, выделить каждый кластер разным цветом, отметить центроиды.

Содержательно проинтерпретировать полученные результаты.

Дополнительные необязательные задания:

Реализовать алгоритмы k-medians и k-medoids. Отобразить полученные кластеры, выделить каждый кластер разным цветом, отметить центроиды. Провести оценку методов, сделать выводы.

С помощью метода локтя и/или метода силуэтов выявить для каждого метода оптимальное количество кластеров.

Реализовать модификацию k-means++. Объяснить её приемущества. Сравнить с обычным методом k-means.

Содержание отчёта

Цель работы.

Краткое изложение основных теоретических понятий.

Постановка задачи с кратким описанием порядка выполнения работы.

Необходимые формулы, рисунки и таблицы.

Краткие выводы по полученным результатам.

Общий вывод по проделанной работе.

Код программы (если имеется).

Вопросы для самоконтроля

Сформулировать основные задачи кластерного анализа.

Дать классификацию и охарактеризовать основные методы кластерного анализа.

Критерии качества кластерных разбиений.

Описать и прокомментировать метод k-means кластерного анализа.