VIII Международная студенческая научная конференция Студенческий научный форум - 2016
СРАВНИТЕЛЬНЫЙ АНАЛИЗ КАЧЕСТВЕННЫХ И КОЛИЧЕСТВЕННЫХ ХАРАКТЕРИСТИК АЛГОРИТМОВ ЧЕТКОЙ И НЕЧЕТКОЙ КЛАСТЕРИЗАЦИИ
Полная версия работы доступна во вкладке "Файлы работы" в формате PDF
В настоящее время методы кластерного анализа широко используются в различных сферах человеческой деятельности с целью обработки больших массивов многомерных данных. Это вызвано необходимостью проведения разбиения исходного множества объектов на кластеры путём выявления схожих объектов и объединения их в подмножества.
Для решения данной практической задачи применяются как методы четкой кластеризации, предполагающие отнесение объекта строго к одному из кластеров, так и методы нечеткой кластеризации, позволяющие произвести разбиение так, чтобы можно было определить, в какой мере объект принадлежит каждому из кластеров.
Целью данной работы является рассмотрение двух наиболее известных методов кластерного анализа – k-means алгоритма четкой кластеризации и Fuzzy C-means алгоритма нечеткой кластеризации. В рамках экспериментальной части необходимо провести сравнительный анализ качественных и количественных характеристик обоих алгоритмов, протестировав их на реальных априорных данных.
Постановка задачи.
Пусть нам дано множество X, состоящее из N объектов (X = {x1, x2,…,xN}), где каждый из которых характеризуется точкой в N-мерном Евклидовом пространстве. Необходимо разбить исходное множество на C кластеров.
Описание Fuzzy C-means алгоритма.
Кластеры задаются матрицей нечеткого разбиения, имеющей следующий вид[1,2]:
(1),
где μki – степень принадлежности k-ого объекта i-му кластеру; k – номер объекта; i – номер кластера; N – количество объектов; С – число кластеров.
При этом должно строго выполняться следующее условие:
(2)
На начальном этапе алгоритма мы задаём следующие параметры для работы алгоритма:
-
С – число кластеров;
-
m – экспоненциальный вес (или мера нечеткости), определяющий степень размытости кластеров, который, как правило, принимают равным двум (m = 2), так как не существует теоретически обоснованного правила выбора его значения[2];
-
ε – параметр останова алгоритма.
На втором этапе генерируется начальная матрица нечеткого разбиения (1), путем полного отнесения всех объектов первому кластеру.
На третьем этапе осуществляется расчет центров кластеров по следующей формуле[1]:
(3),
где ci – центр i-го кластера; μki – степень принадлежности k-ого объекта i-му кластеру; m – экспоненциальный вес; xk – вектор параметров k-ого объекта.
На четвертом этапе рассчитывается матрица расстояний, имеющая ту же размерность, что и матрица нечеткого разбиения. Каждый элемент данной матрицы равен Евклидову расстоянию от рассматриваемого объекта до центра конкретного кластера и рассчитывается по следующей формуле[1]:
(4),
где ρki – расстояние от k-ого объекта до центра i-го кластера; xk – вектор параметров k-ого объекта; ci – центр i-го кластера.
На пятом этапе осуществляется пересчет матрицы нечеткого разбиения по следующей формуле[1]:
(5),
где μ*ki – пересчитанная степень принадлежности k-ого объекта i-му кластеру.
На шестом шаге мы проверяем условие оптимальности полученного разбиения, согласно которому разности всех соответствующих пар элементов старой и новой матриц нечёткого разбиения по модулю должны быть меньше задаваемого на начальном этапе параметра останова:
(6)
Если условие (6) выполняется, алгоритм завершает свою работу. Иначе осуществляется переход на третий этап[2].
На рисунке 1 представлена блок-схема Fuzzy C-means алгоритма.
Рисунок 1 – Блок-схема Fuzzy C-means алгоритма
Описание k-means алгоритма.
На первом этапе работы алгоритма задаются произвольным образом C кластеров. Чаще всего на практике в качестве начальных положений центров кластеров выбирают любые C элементов исходного множества, подлежащего разбиению.
На втором этапе для каждого объекта рассчитываются Евклидовы расстояния до каждого центроида по формуле (4). Впоследствии объект относится к ближайшему кластеру.
На третьем этапе осуществляется пересчет координат центров кластеров по следующей формуле:
(7),
где ci – центр i-го кластера; Mi – число объектов в i-ом кластере; xki – вектор параметров k-ого объекта, отнесенного к i-ому кластеру.
Второй и третий этапы рекурсивно повторяются до тех пор, пока положения центроидов не перестанут меняться [3].
На рисунке 2 представлена блок-схема k-means алгоритма.
Рисунок 2 – Блок-схема k-means алгоритма
Экспериментальная часть.
Для проведения экспериментальной части Нижегородским научно-исследовательским институтом эпидемиологии и микробиологии им. И.Н. Блохиной (ННИИЭМ) была предоставлена тестовая выборка, состоящая из 170 пациентов в возрасте от 33 до 35 лет. Каждый пациент охарактеризован априорными сведениями в виде набора из 29 проб на предмет анализа состояния микробиоты желудочно-кишечного тракта. Каждый элемент данного набора представляет собой нормированное значение в интервале от 0 до 12 баллов.
Таким образом, в качестве исходных данных имеем множество из 170 объектов, каждому из которых поставлена в соответствие точка в 29-мерном пространстве. Задача сводится к разбиению предложенной выборки на четыре кластера: три степени заболевания и категория здоровых людей. Полученный результат разбиения необходимо сравнить с экспертными оценками, предоставленными ННИИЭМ для каждого пациента с целью оценки качества работы каждого из двух алгоритмов.
Для проведения тестирования алгоритмов на предложенной выборке было разработано приложение на языке C#, визуализирующее полученный результат разбиения на четыре кластера.
Визуализация полученного результата осуществляется в соответствии с таблицей 1.
Таблица 1 – Визуализация результата кластерного анализа
|
Номер кластера |
Назначаемый цвет |
Степень заболевания |
|
1 |
Зеленый |
Пациент здоров |
|
2 |
Синий |
Первая степень заболевания |
|
3 |
Желтый |
Вторая степень заболевания |
|
4 |
Красный |
Третья степень заболевания |
Оценка качества разбиения исходного множества осуществляется по следующей формуле:
(8),
где E – число объектов, отнесённых не в тот кластер, N – размер выборки.
Также в рамках экспериментальной части проводится исследование зависимости числа итераций и времени работы алгоритма от размера выборки.
Для оценки качественных и количественных характеристик проводится для различных выборок, кратных десяти, по десять опытов.
Полученные результаты.
На рисунке 3 представлен визуализированный результат полученного с помощью Fuzzy C-means алгоритма разбиения для предоставленной тестовой выборки в 170 человек. Вдоль оси абсцисс откладываются номера пациентов (k), а вдоль оси ординат – значения степени принадлежности k-ого пациента кластеру здоровых людей (μk1).
Рисунок 3 – Результат работы Fuzzy C-means алгоритма
На рисунке 4 представлен визуализированный результат полученного с помощью k-means алгоритма разбиения для предоставленной тестовой выборки в 170 человек. Для данного алгоритма результат разбиения представлен в трёхмерном пространстве, где вдоль осей откладываются значения наиболее ярких параметров вектора объекта.
В таблицу 2 сведены результаты исследования качественных и количественных показателей работы Fuzzy C-means алгоритма.
На рисунке 5 представлен график зависимости времени работы Fuzzy C-means алгоритма от размера исходного множества.
Кроме того, исследования показали, что количество итераций данного алгоритма не зависит от размера исходной выборки и в среднем колеблется между 10 и 12 итерациями.
Рисунок 4 – Результат работы k-means алгоритма
Таблица 2 – Оценка качественных и количественных показателей Fuzzy C-means алгоритма
|
Размер выборки |
Время выполнения, мс |
Среднее время, мс |
Среднее число E |
Средний уровень Q |
|||||||||
|
t1 |
t2 |
t3 |
t4 |
t5 |
t6 |
t7 |
t8 |
t9 |
t10 |
||||
|
10 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
0 |
100% |
|
20 |
2 |
1 |
1 |
2 |
1 |
1 |
2 |
1 |
1 |
2 |
1.4 |
0 |
100% |
|
30 |
2 |
2 |
1 |
2 |
2 |
1 |
2 |
2 |
2 |
2 |
1.8 |
1 |
96.7% |
|
40 |
2 |
3 |
2 |
4 |
3 |
2 |
3 |
3 |
2 |
3 |
2.4 |
2 |
95% |
|
50 |
3 |
3 |
2 |
3 |
3 |
5 |
3 |
4 |
3 |
3 |
3.2 |
2 |
96% |
|
60 |
4 |
3 |
5 |
3 |
3 |
4 |
3 |
4 |
5 |
4 |
3.8 |
3 |
95% |
|
70 |
4 |
6 |
7 |
4 |
4 |
4 |
3 |
4 |
5 |
6 |
4.7 |
4 |
94.3% |
|
80 |
4 |
8 |
5 |
5 |
4 |
5 |
6 |
4 |
5 |
6 |
5.2 |
4 |
95% |
|
90 |
5 |
4 |
5 |
4 |
6 |
8 |
5 |
5 |
5 |
6 |
5.3 |
4 |
95.6% |
|
100 |
8 |
6 |
7 |
5 |
6 |
5 |
7 |
5 |
6 |
7 |
6.2 |
6 |
94% |
|
110 |
7 |
7 |
5 |
7 |
6 |
5 |
7 |
6 |
7 |
6 |
6.3 |
6 |
94.5% |
|
120 |
6 |
7 |
5 |
6 |
10 |
6 |
7 |
9 |
6 |
8 |
7 |
7 |
94.2% |
|
130 |
8 |
6 |
7 |
7 |
6 |
7 |
9 |
7 |
8 |
9 |
7.4 |
8 |
93.8% |
|
140 |
7 |
8 |
7 |
9 |
6 |
8 |
8 |
9 |
7 |
8 |
7.7 |
8 |
94.3% |
|
150 |
9 |
9 |
7 |
8 |
8 |
7 |
10 |
8 |
8 |
10 |
8.4 |
8 |
94.7% |
|
160 |
10 |
10 |
9 |
8 |
9 |
8 |
9 |
8 |
9 |
10 |
9 |
10 |
93.75% |
|
170 |
8 |
11 |
10 |
11 |
13 |
12 |
9 |
11 |
10 |
12 |
10.7 |
10 |
94.1% |
Рисунок 5 – График зависимости времени работы Fuzzy C-means алгоритма от размера выборки
В таблицу 3 сведены результаты исследования качественных и количественных показателей работы k-means алгоритма.
Таблица 3 – Оценка качественных и количественных показателей k-means алгоритма
|
Размер выборки |
Время выполнения, мс |
Среднее время, мс |
Среднее число E |
Средний уровень Q |
|||||||||
|
t1 |
t2 |
t3 |
t4 |
t5 |
t6 |
t7 |
t8 |
t9 |
t10 |
||||
|
10 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
0 |
100% |
|
20 |
1 |
2 |
2 |
2 |
1 |
2 |
1 |
2 |
1 |
1 |
1.5 |
1 |
95% |
|
30 |
2 |
2 |
3 |
2 |
2 |
2 |
3 |
3 |
2 |
2 |
2.3 |
2 |
93,3% |
|
40 |
3 |
4 |
2 |
4 |
3 |
5 |
3 |
2 |
3 |
4 |
3.3 |
4 |
90% |
|
50 |
4 |
5 |
3 |
3 |
3 |
5 |
3 |
4 |
5 |
4 |
3.9 |
6 |
88% |
|
60 |
5 |
4 |
5 |
4 |
4 |
6 |
3 |
4 |
5 |
5 |
4.5 |
7 |
88.3% |
|
70 |
5 |
6 |
7 |
6 |
5 |
7 |
3 |
6 |
5 |
4 |
5.4 |
7 |
90% |
|
80 |
5 |
8 |
6 |
7 |
8 |
6 |
5 |
5 |
5 |
7 |
6.2 |
8 |
90% |
|
90 |
7 |
6 |
5 |
4 |
6 |
8 |
8 |
8 |
7 |
7 |
6.6 |
8 |
91.1% |
|
100 |
8 |
9 |
9 |
7 |
6 |
7 |
7 |
7 |
8 |
9 |
7.7 |
8 |
92% |
|
110 |
9 |
8 |
9 |
7 |
9 |
8 |
7 |
9 |
7 |
8 |
8.1 |
9 |
91.8% |
|
120 |
8 |
7 |
9 |
9 |
10 |
8 |
7 |
9 |
10 |
8 |
8.5 |
9 |
92.5% |
|
130 |
10 |
8 |
9 |
8 |
9 |
8 |
10 |
10 |
9 |
10 |
9.1 |
9 |
93.1% |
|
140 |
11 |
10 |
9 |
8 |
9 |
9 |
10 |
11 |
8 |
11 |
9.6 |
10 |
92.8% |
|
150 |
9 |
10 |
11 |
11 |
9 |
10 |
10 |
11 |
11 |
10 |
10.2 |
11 |
92.7% |
|
160 |
10 |
10 |
12 |
11 |
12 |
10 |
12 |
12 |
10 |
11 |
11 |
11 |
93.1% |
|
170 |
13 |
11 |
10 |
11 |
12 |
13 |
13 |
12 |
11 |
12 |
11.8 |
13 |
92.3% |
На рисунке 6 представлен график зависимости времени работы k-means алгоритма от размера исходного множества.
Рисунок 6 – График зависимости времени работы k-means алгоритма от размера выборки
Также исследования показали, что количество итераций данного алгоритма от размера исходной выборки не зависит, а зависит исключительно от задания начальных положений центроидов.
Выводы.
В ходе исследований было установлено, что у обоих алгоритмов с ростом размера выборки увеличивается число ошибок (объектов, отнесённых не в тот кластер). При этом Fuzzy C-means оказался эффективней, чем k-means, так как средний уровень качества для первого алгоритма составил 95.35%, а для второго – 92.12%.
Кроме того, в ходе экспериментальной части было выявлено, что число итераций для обоих алгоритмов не зависит от размера исходного множества. У Fuzzy C-means данный параметр лежит в пределах от 10 до 12, а у k-means он зависит лишь от начального выбора положений центроидов.
Также было установлено, что с ростом размера выборки время работы алгоритмов линейно возрастает. Но при этом быстродействие Fuzzy C-means выше, чем у k-means.
Библиографический список
1. Jan Jantzen «Neurofuzzy Modelling». [Электронный ресурс]. – Режим доступа: http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.68.390&rep=rep1&type=pdf
2. Штовба С.Д. Введение в теорию нечетких множеств и нечеткую логику. Винница: Континент-Прим. – 2003. – 198 с.
3. Барсегян, А. А. Анализ данных и процессов: учеб. пособие / А. А. Барсегян, М. С. Куприянов, И. И. Холод, М. Д. Тесс, С. И. Елизаров. – 3-е изд., перераб. и доп. – СПб.: БХВ-Петербург, 2009. – 512 с.