СРАВНИТЕЛЬНЫЙ АНАЛИЗ КАЧЕСТВЕННЫХ И КОЛИЧЕСТВЕННЫХ ХАРАКТЕРИСТИК АЛГОРИТМОВ ЧЕТКОЙ И НЕЧЕТКОЙ КЛАСТЕРИЗАЦИИ - Студенческий научный форум

VIII Международная студенческая научная конференция Студенческий научный форум - 2016

СРАВНИТЕЛЬНЫЙ АНАЛИЗ КАЧЕСТВЕННЫХ И КОЛИЧЕСТВЕННЫХ ХАРАКТЕРИСТИК АЛГОРИТМОВ ЧЕТКОЙ И НЕЧЕТКОЙ КЛАСТЕРИЗАЦИИ

Канев О.К. 1
1Нижегородский Государственный Технический Университет им. Р.Е. Алексеева
 Комментарии
Текст работы размещён без изображений и формул.
Полная версия работы доступна во вкладке "Файлы работы" в формате 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 с.

Просмотров работы: 907