В наше время все чаще возникает необходимость анализа больших данных, который может быть проведен вручную, а может быть проделан с помощью машинного обучения. Одна из областей применения средств машинного обучения – медицина.
Кластерный анализ — это семейство алгоритмов, предназначенных для формирования групп, где члены этих групп похожи друг на друга сильнее, чем на тех, кто в этой группе не состоит [2].В статье применяется метод кластеризации k-means (к-средних).
Метод k-means разделяет набор данных на количество групп k таким образом, чтобы группы были различны между собой, а объекты в них очень похожи. Алгоритм k-средних разделяет объектов на кластеры, при котором различия («расстояния») между объектами одного и того же кластера минимизируется, а расстояние между объектами разных кластеров максимизируются.
Алгоритм метода k-средних:
Самостоятельно выбираем число кластеров k.
Выбирается рандомно k записей из набора данных, которые изначально будут центрами кластеров.
Для всех записей определяется ближний к нему центр кластера. Записи, которые приближены к определенному центру, образуют группы - начальные кластеры.
Вычисляются центроиды, векторы, элементы которых являются средними значениями признаков, вычисленные по всем записям кластера. Затем центр группы перемещается в центроид.
Последние 2 пункта процедуры повторяются, на каждом повторении шага происходит изменение границы группы, а их центры смещаются. В результате расстояние между элементами внутри кластеров становятся минимальными.
Алгоритм останавливается, когда границы кластеров и центроиды перестают изменяться, т.е. на каждой итерации в каждом кластере будет оставаться один и тот же набор записей. На практике алгоритм обычно находит набор стабильных кластеров за несколько десятков итераций [3].
Постановка задачи:
Пусть Х — множество объектов, Y — множество номеров (имён, меток) кластеров.
Дана обучающая выборка объектов Xm { x1, x2, ... xm }. Необходимо разбить данные на кластеры.
Цель метода k-средних состоит в минимизации суммарного квадратичного отклонения точек кластеров от центров этих кластеров:
Si – кластер, µi – центроид для кластера Si.
Применение метода k-средних для диагностики рака молочных желез.
Имеется набор данных рака молочных желез, который находится в открытом доступе [6]. Данные представляют собой 369 примеров, состоящих из 10 признаков:
Пример номер кода: идентификационный номер
Толщина: 1 - 10
Однородность ячейки: 1 - 10
Однородность клетки: 1 - 10
Адгезия: 1 - 10
Размер эпителиальной клетки : 1 - 10
Ядра: 1 - 10
Хроматин: 1 - 10
Нормальные ядрышки: 1 - 10
Митозы: 1 - 10
Класс: (2 для доброкачественной, 4 для злокачественных)
Набор данных записан в следующем виде:
1000025,5,1,1,1,2,1,3,1,1,2
1002945,5,4,4,5,7,10,3,2,1,2
1015425,3,1,1,1,2,2,3,1,1,2
1016277,6,8,8,1,3,4,3,7,1,2
1017023,4,1,1,3,2,1,3,1,1,2
1017122,8,10,10,8,7,10,9,7,1,4
1018099,1,1,1,1,2,10,3,1,1,2
1018561,2,1,2,1,2,1,3,1,1,2
1033078,2,1,1,1,2,1,1,1,5,2
1033078,4,2,1,1,2,1,2,1,1,2
1035283,1,1,1,1,1,1,3,1,1,2
1036172,2,1,1,1,2,1,2,1,1,2
1041801,5,3,3,3,2,3,4,4,1,4
1043999,1,1,1,1,2,3,3,1,1,2
1044572,8,7,5,10,7,9,5,5,4,4
1047630,7,4,6,4,6,1,4,3,1,4
1048672,4,1,1,1,2,1,2,1,1,2
1049815,4,1,1,1,2,1,3,1,1,2
1050670,10,7,7,6,4,10,4,1,2,4
1050718,6,1,1,1,2,1,3,1,1,2
1054590,7,3,2,10,5,10,5,4,4,4
1054593,10,5,5,3,6,7,7,10,1,4
1056784,3,1,1,1,2,1,2,1,1,2
Требуется кластеризовать опухоли на доброкачественные и злокачественные при помощи программного обеспечения GNU Octave [7], также, можно воспользоваться его аналогом, программным пакетом - MATLAB.
В программировании использовались следующие отрывки кода [7,11]:
## Генерируем 2 центроиды
C1 = randn (100, 2) + 1;
C2 = randn (100, 2) - 1;
data = [C1; C2];
## Выполняем кластеризацию
[idx, centers] = kmeans (data, 2);
## График результатов
figure;
plot (data (idx==1, 1), data (idx==1, 2), 'ro');
hold on;
plot (data (idx==2, 1), data (idx==2, 2), 'bs');
plot (centers (:, 1), centers (:, 2), 'kv', 'markersize', 10);
hold off;
Графики, отображающие работу программы:
Рис 1. – Отображение набора данных
Рис 2. – Кластеризация набора данных на 2 кластера
На осях графика отложены величины признаков объектов, а также на графике показаны центроиды каждого кластера. В результате применения метода k-средних опухоли были разделены на доброкачественные (красные) и злокачественные (синие).
Выводы:
В статье рассмотрен метод кластеризации k-средних и показана эффективность работы алгоритма для диагностики опухоли молочных желез. Код программа был написан с помощью программы Octave. Благодаря выполненной работе в дальнейшем можем прогнозировать новые опухоли молочных желез пациентов на злокачественность.
Список источников литературы:
Кокорева Я. В., Макаров А. А. Поэтапный процесс кластерного анализа данных на основе алгоритма кластеризации k-means // Молодой ученый. — 2015. — №13. — С. 126-128.
Алгоритмы интеллектуального анализа данных: https://tproger.ru/translations/top-10-data-mining-algorithms/
Технологии анализа данных: https://basegroup.ru/community/glossary/k-means
С.А. Батуркин, Е.Ю. Батуркина, В.А. Зименко, И.В. Сигинов Статистические алгоритмы кластеризации данных в адаптивных обучающих системах // Вестник РГРТУ. № 1 (выпуск 31). Рязань, 2010
Официальный сайт Национального открытого университета: http://www.intuit.ru
Центр машинного обучения и интеллектуальных систем UCI: http://archive.ics.uci.edu/ml/datasets/Breast+Cancer+Wisconsin+%28Original%29
Официальный сайт Octave: https://octave.sourceforge.io/statistics/function/kmeans.html
К. В. Воронцов, курс лекций Машинное обучение
Википедия: https://ru.wikipedia.org/wiki/K-means
Глобальный интеллектуальный ресурс: http://statistica.ru/theory/klasterizatsiya-metod-k-srednikh/#
Программирование: https://www.mathworks.com/help/stats/kmeans.html
J. B. MacQueen (1967): "Some Methods for classification and Analysis of Multivariate Observations, Proceedings of 5-th Berkeley Symposium on Mathematical Statistics and Probability", Berkeley, University of California Press, 1:281-297