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

Цель работы

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

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

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

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

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

Определить верхнюю оценку количества кластеров по формуле: , где -- число точек.

Реализовать алгоритм k-means в двух вариантах: пересчет центра кластера осуществляется после каждого изменения его состава и пересчет центра кластера осуществляется лишь после того, как будет завершен просмотр всех данных (шаг процедуры). Отобразить полученные кластеры, выделить каждый кластер разным цветом, отметить центроиды.

Провести оценку качества разбиения для различных разбиений.

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

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

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

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

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

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

Цель работы.

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

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

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

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

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

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

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

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

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

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

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