takya.ru страница 1
скачать файл
Лабораторная работа №3 (это пример выполнения лаб.работы, индивидуальное задание находится в пункте 4)

 

1. Тема лабораторной работы:



 

Исследование алгоритма нечеткой кластеризации.

 

2. Цель лабораторной работы



 

Изучить алгоритм нечеткой кластеризации, получить практические навыки решения задач кластеризации методами нечеткой логики.

 

3. Краткие сведения из теории



 

FCM-алгоритм кластеризации. Алгоритм нечеткой кластеризации называют FCM-алгоритмом (Fuzzy Classifier Means, Fuzzy C-Means). Целью FCM-алгоритма кластеризации является автоматическая классификация множества объектов, которые задаются векторами признаков в пространстве признаков. Другими словами, такой алгоритм определяет кластеры и соответственно классифицирует объекты. Кластеры представляются нечеткими множествами, и, кроме того, границы между кластерами также являются нечеткими.

FCM-алгоритм кластеризации предполагает, что объекты принадлежат всем кластерам с определенной ФП. Степень принадлежности определяется расстоянием от объекта до соответствующих кластерных центров. Данный алгоритм итерационно вычисляет центры кластеров и новые степени принадлежности объектов.

Для заданного множества К входных векторов хk и N выделяемых кластеров сj предполагается, что любой хк принадлежит любому сj с принадлежностью µjk http://cde.kpi.kharkov.ua/courses/course_270/lr3.files/image002.gif [0,1], где j – номер кластера, а k – номер входного вектора.

Принимаются во внимание следующие условия нормирования для µjk:



http://cde.kpi.kharkov.ua/courses/course_270/lr3.files/image004.gif

Цель алгоритма – минимизация суммы всех взвешенных расстояний http://cde.kpi.kharkov.ua/courses/course_270/lr3.files/image006.gif:



http://cde.kpi.kharkov.ua/courses/course_270/lr3.files/image008.gif,

где q фиксированный параметр, задаваемый перед итерациями.

Для достижения вышеуказанной цели необходимо решить следующую систему уравнений:

http://cde.kpi.kharkov.ua/courses/course_270/lr3.files/image010.gif

Совместно с условиями нормирования µjk данная система дифференциальных уравнений имеет следующее решение:



http://cde.kpi.kharkov.ua/courses/course_270/lr3.files/image012.gif

(взвешенный центр гравитации) и



http://cde.kpi.kharkov.ua/courses/course_270/lr3.files/image014.gif

Алгоритм нечеткой кластеризации выполняется по шагам.



Шаг 1. Инициализация.

Выбираются следующие параметры:

• необходимое количество кластеров N, 2 < N < К;

• мера расстояний, как Евклидово расстояние;

• фиксированный параметр q (обычно 1,5);

• начальная (на нулевой итерации) матрица принадлежности http://cde.kpi.kharkov.ua/courses/course_270/lr3.files/image016.gif объектов хk с учетом заданных начальных центров кластеров сj.



Шаг 2. Регулирование позиций http://cde.kpi.kharkov.ua/courses/course_270/lr3.files/image018.gif центров кластеров.

На t-м итерационном шаге при известной матрице http://cde.kpi.kharkov.ua/courses/course_270/lr3.files/image020.gif вычисляется http://cde.kpi.kharkov.ua/courses/course_270/lr3.files/image018.gif в соответствии с вышеприведенным решением системы дифференциальных уравнений.



Шаг 3. Корректировка значений принадлежности µjk.

Учитывая известные http://cde.kpi.kharkov.ua/courses/course_270/lr3.files/image018.gif, вычисляются http://cde.kpi.kharkov.ua/courses/course_270/lr3.files/image020.gif, если http://cde.kpi.kharkov.ua/courses/course_270/lr3.files/image022.gif, в противном случае:



http://cde.kpi.kharkov.ua/courses/course_270/lr3.files/image024.gif

Шаг 4. Остановка алгоритма.

Алгоритм нечеткой кластеризации останавливается при выполнении следующего условия:



http://cde.kpi.kharkov.ua/courses/course_270/lr3.files/image026.gif

где || || – матричная норма (например, Евклидова норма);



http://cde.kpi.kharkov.ua/courses/course_270/lr3.files/image028.gif – заранее задаваемый уровень точности.

 

Решение задач кластеризации. Существуют два способа решения задач кластеризации в Matlab: с использованием командной строки или графического интерфейса пользователя. Рассмотрим первый из указанных способов.

Для нахождения центров кластеров в Matlab имеется, встроенная функция fcm, описание которой представлено ниже.

Описание функции:



http://cde.kpi.kharkov.ua/courses/course_270/lr3.files/image030.gif

Аргументами данной функции являются:

1) data – множество данных, подлежащих кластеризации, каждая строка описывает точку в многомерном пространстве характеристик;

2) cluster_n — количество кластеров (более одного).

Функцией возвращаются следующие параметры:

1) center матрица центров кластеров, каждая строка которой содержит координаты центра отдельного кластера;

2) U результирующая матрица ФП;

3) obj_fcn – значение целевой функции на каждой итерации.

 

Пример П11. Программа нечеткой кластеризации.

// загрузка данных, подлежащих кластеризации, из файла

load fcmdata.dat;

// определение центра кластеризации (два кластера)

[center, U, obj_fcm] = fcm( fсmdata, 2);

// определение максимальной степени принадлежности

// отдельного элемента данных кластеру

maxU = max(U);

// распределение строк матрицы данных между соответствующими

// кластерами

index1 = find (U(1, :) == maxU);

index2 = find(U(2, :) = maxU);

// построение данных, соответствующих первому кластеру

plot (fcmdata (index1, 1), fcmdata (index1, 2),' ko', 'markersize', 5, 'LineWidth' ,1);

hold on

// построение данных, соответствующих второму кластеру

plot(fcmdata (index2, 1), fcmdata(index2, 2), 'kx', 'markersize', 5, 'LineWidth', 1);

// построение кластерных центров

plot(center(1, 1), center(1, 2), 'ko', 'markersize', 15, 'LineWidth', 2)

plot (center (2, 1), center (2, 2), 'kx', 'markersize', 15, 'LineWidth', 2)

На рис. П15 представлено множество данных, подлежащих кластеризации и найденные центры кластеров для примера П.11.

 

http://cde.kpi.kharkov.ua/courses/course_270/lr3.files/image032.jpg

Рис. П15. Множество анализируемых данных и центры кластеров

 

Функция fcm выполняется итерационно до тех пор, пока изменения целевой функции превышают некоторый заданный порог. На каждом шаге в командном окне Маtlab выводятся порядковый номер итерации и соответствующее текущее значение целевой функции.



Номер итерации

Значения целевой функции

Номер итерации

Значения целевой функции

1

8,94

7

3,81

2

7,31

8

3,8

3

6,9

9

3,79

4

5,41

10

3,79

5

4,08

11

3,79

6

3,83

12

3,78

 

Для оценки динамики изменения значений целевой функции используется команда построения графика plot(obj_fcn). Результаты примера П11 показаны на рис. П16.

 

http://cde.kpi.kharkov.ua/courses/course_270/lr3.files/image034.jpg

Рис. П16. График изменения значений целевой функции

 

Функцию кластеризации можно вызвать с дополнительным набором параметров: fcm (data, cluster_n, options). Дополнительные аргументы используются для управления процессом кластеризации:



• options(1) – показатель степени для матрицы U (по умолчанию 2.0);

• options(2) – максимальное количество итераций (по умолчанию 100);

• options(3) – предельное изменение значений целевой функции (по умолчанию 1е-5);

• options(4) – отображение информации на каждом шаге (по умолчанию 1).

Пример определения функции fcm с дополнительными параметрами:

[center, U, obj_fcn] = fсm(fcmdata, 2, [2,100,le-5,1]).

Второй способ решения задач кластеризации в Matlab основан на использовании ГИП, который вызывается командой findcluster. Главное окно инструмента кластеризации показано на рис. П17.

Кнопка используется для загрузки подлежащих кластеризации исходных данных следующего формата: каждая строка представляет собой точку в многомерном пространстве характеристик, количество строк соответствует количеству точек (элементов данных). Графическую интерпретацию исходных данных можно наблюдать в одноименном окне главного окна инструмента.

Выбор типа алгоритма кластеризации осуществляется с использованием ниспадающего меню Methods (пункт меню fcm). Далее определяются параметры алгоритма кластеризации:

• количество кластеров (строка ввода Cluster Num);

• максимальное количество итераций (строка ввода — Мах Iteration#);

• минимальное значение улучшения целевой функции (строка ввода — Min. Improvement);

• показатель степени при матрице ФП (строка ввода — Exponent).

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

http://cde.kpi.kharkov.ua/courses/course_270/lr3.files/image036.jpg

Рис. П17. Главное окно кластеризации в Matlab

 

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



 

4. Индивидуальные задания

4.1. Необходимо сформулировать задачу, из области вычислительной техники или программирования, для которой была бы необходима автоматическая классификация множества объектов, которые задаются векторами признаков в пространстве признаков.

4.2. Решить в Matlab сформулированную задачу с использованием механизма кластеризации методами нечеткой логики, при этом используя командную строку и графический интерфейс пользователя. При использовании командной строки функцию кластеризации необходимо вызвать с дополнительным набором параметров.

4.3. Найти центры кластеров и построить график изменения значений целевой функции.

 

5. Содержание отчета



5.1. Тема лабораторной работы.

5.2. Цель лабораторной работы.

5.3. Индивидуальное задание.

5.4. Результаты выполнения пунктов 4.1  4.3 индивидуального задания.



5.5. Выводы по лабораторной работе.
скачать файл



Смотрите также:
Лабораторная работа №3 (это пример выполнения лаб работы, индивидуальное задание находится в пункте 4) Тема лабораторной работы: Исследование алгоритма нечеткой кластеризации
95.48kb.
Автоматизированный корреляционно-регрессионный анализ взаимосвязи статистических данных в среде ms excel
428.65kb.
Требования к выполнению лабораторной работы №1 Срок выполнения: I – II недели. Цель
12.14kb.
Лабораторная работа №7 Тема «Исследование счетчиков»
14.21kb.
Лабораторная работа №2. Синтез и исследование комбинационных схем
55.89kb.
Тематический контроль 7 класс самостоятельная работа тексты вариантов самостоятельной работы по алгоритмизации
21.89kb.
Лабораторная работа №3 по сппо «Дочерние окна в Windows»
19.75kb.
Лабораторная работа №3 по микроэлектронике «Исследование схем усилителя с общим эммитером»
14.29kb.
Методические указания к лабораторной работе
230.07kb.
И. О. по лабораторной работе №9 «Иcследование цепей несинусоидального тока» Цель работы: Исследование
27.53kb.
Лабораторная работа по общей физике №31. Некоторые законы случайных событий
132.09kb.
Исследование счетчиков. Лабораторная работа №7
62.22kb.