МОЭВМ Вики [se.moevm.info]

Эта страница только для чтения. Вы можете посмотреть её исходный текст, но не можете его изменить. Сообщите администратору, если считаете, что это неправильно.
====== Практическая работа №6: Кластерный анализ. Метод k-средних ======
===== Цель работы =====
Освоение основных понятий и некоторых методов кластерного анализа, в частности, метода k-средних.

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

===== Порядок выполнения работы =====
  - Нормализовать множество точек из предыдущего раздела, отобразить полученное множество.
  - Определить <<грубую>> верхнюю оценку количества кластеров: $ \tilde k = \lfloor\sqrt{N/2}\rfloor $, где $ N $ -- число точек.
  - Реализовать алгоритм k-means в двух вариантах: 
    - пересчет центра кластера осуществляется после каждого изменения его состава;
    - пересчет центра кластера осуществляется лишь после того, как будет завершен просмотр всех данных (шаг процедуры).
  - На каждом шаге процедуры разбиения методом k-means вычислять функционалы качества полученного разбиения:
    - $ F_1 $ -- сумма по всем кластерам квадратов расстояний элементов кластеров до центров соответствующих кластеров;
    - $ F_2 $ -- сумма по всем кластерам внутрикластерных расстояний между элементами кластеров;
    - $ F_3 $ -- сумма по всем кластерам внутрикластерных дисперсий (относительно центров кластеров).
  - Отобразить полученные кластеры, выделить каждый кластер разным цветом, отметить центроиды.
  - Содержательно проинтерпретировать полученные результаты.
  - //Дополнительные необязательные задания://
    - //Реализовать алгоритмы [[https://en.wikipedia.org/wiki/K-medians_clustering|k-medians]] и [[https://en.wikipedia.org/wiki/K-medoids|k-medoids]]. Отобразить полученные кластеры, выделить каждый кластер разным цветом, отметить центроиды. Провести оценку методов, сделать выводы.//
    - //С помощью [[https://en.wikipedia.org/wiki/Elbow_method_(clustering)|метода локтя]] и [[https://en.wikipedia.org/wiki/Silhouette_(clustering)|метода силуэтов]] выявить для каждого метода оптимальное количество кластеров.//
    - //Реализовать модификацию [[https://en.wikipedia.org/wiki/K-means%2B%2B|k-means++]]. Объяснить её приемущества. Сравнить с обычным методом k-means.//

===== Содержание отчёта =====
  - Цель работы.
  - Краткое изложение основных теоретических понятий.
  - Постановка задачи с кратким описанием порядка выполнения работы.
  - Необходимые формулы, рисунки и таблицы.
  - Краткие выводы по полученным результатам.
  - Общий вывод по проделанной работе.
  - Код программы (если имеется).

===== Вопросы для самоконтроля =====
  - Сформулировать основные задачи кластерного анализа.
  - Дать классификацию и охарактеризовать основные методы кластерного анализа.
  - Критерии качества кластерных разбиений.
  - Описать и прокомментировать метод k-means кластерного анализа.