Методы группировки объектов. 
Алгоритм K-средних

Государственное образовательное учреждение высшего профессионального образования «Санкт-Петербургский государственный электротехнический университет „ЛЭТИ“ им. В. И. Ульянова (Ленина)»

Кафедра БТС Практическая работа по дисциплине

Автоматизация биомедицинских исследований тема: «Методы группировки объектов. Алгоритм K-средних»

г. Санкт-Петербург 2011 г.

Задание

Используя рандомизацию исходных данных (объединенной центрированной матрицы наблюдений) провести группировку объектов на основе алгоритма K-средних. При этом:

1) число кластеров K задать равным числу исходных классов наблюдений (2 или 3);

2) в качестве первоначальных центров кластеров z₁(1), z₂(1) [и z₃(1), если K=3] выбрать наиболее удаленные друг от друга объекты;

3) порядок выбора объектов из объединенной таблицы д.б. случайным;

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

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

Рандомизация строк матрицы центрированных значений

Путем перемешивания строк матрицы центрированных значений создадим новую матрицу X. Для удобства сформируем матрицу N, значения которой соответствуют тому, к какому классу принадлежит каждый из объектов новой матрицы Х.

Первая итерация.

А) Выбор начальных центров кластеров.

В качестве начальных центров кластеров выбираются наиболее удаленные друг от друга объекты.

Б) Расчет расстояния от объектов до начальных центров кластеров.

В) Сравниваем расстояния и определяем, к какому кластеру относится объект.

Объединим матрицы Х, N и S. В общей матрице можно будет увидеть, какие объекты попали в другой класс после первой итерации.

Вторая итерация.

А) Сортируем строки матрицы Х1 по возрастанию элементов последнего столбца.

Б) Определяем новые центры кластеров (выборочное среднее).

В) Рассчитываем расстояние от объектов до новых центров кластеров.

Г) Сравниваем расстояния и определяем, к какому кластеру относится объект.

Объединим матрицы Х, N и S2. В общей матрице можно будет увидеть, какие объекты попали в другой класс после второй итерации.

Третья итерация.

А) Сортируем строки матрицы Х2 по возрастанию элементов последнего столбца.

Б) Определяем новые центры кластеров (выборочное среднее).

Как мы видим центры кластеров на второй и третьей итерациях достаточно приближены друг к другу.

В) Рассчитываем расстояние от объектов до новых центров кластеров.

Г) Сравниваем расстояния и определяем, к какому кластеру относится объект.

Объединим матрицы Х, N и S3. В общей матрице можно будет увидеть, какие объекты попали в другой класс после третьей итерации.

Четвертая итерация.

А) Сортируем строки матрицы Х3 по возрастанию элементов последнего столбца.

Б) Определяем новые центры кластеров (выборочное среднее).

Как мы видим в третьей и четвертой итерациях значения центров совпали, значит можно закончить кластеризацию на этом этапе.

Вывод

матрица алгоритм итерация кластер Сортируем строки матрицы Х3 по возрастанию элементов предпоследнего столбца.

Как мы видим, некоторые объекты второго класса попали в первый и третий кластеры. Это связано с тем, что объекты второго класса имели большой разброс. Так же мы определили, что для кластеризации достаточно трех итераций.