2012
.pdf5. НЕЧЕТКАЯ КЛАСТЕРИЗАЦИЯ
Кластеризация – это объединение объектов в группы (кластеры) на основе схожести признаков для объектов одной группы и отличий между объектами из разных групп, что соответствует организации процесса обучения без учителя. Большинство алгоритмов кластеризации не опирается на традиционные для статистических методов допущения – они могут использоваться в условиях почти полного отсутствия информации о законах распределения данных. Кластеризацию проводят для объектов с количественными (числовыми), качественными или смешанными признаками. В разделе рассматриваются методы кластеризация для объектов с количественными признаками: алгоритмы четких и нечетких c-средних. В начале рассматриваются ключевые понятия четкой кластеризации алгоритмом c-средних, затем базовый нечеткий алгоритм c- средних.
5.1. Кластеризация с-средних
Четкий алгоритм с-средних. При кластеризации алгоритмом c-средних множество X разбивается на подмножества Ai ,i = 1,c со следующими свойствами:
U Ai = X ; |
(5.1) |
||||||
|
|
|
|
|
|
|
|
i=1,c |
|
||||||
|
|
|
|
|
|
||
Ai ∩ Aj = , i, j = 1, c, i ≠ j; |
(5.2) |
||||||
|
|
|
|
||||
Ai X i = 1, c. |
(5.3) |
Условие (5.1) указывает, что все объекты должны быть распределены по кластерам. При этом каждый объект должен принадлежать только одному кластеру (условие (5.2)) и ни один из кластеров не может быть пустым или содержать все объекты (условие (5.3)). Количество кластеров c {2,3,..., M − 1} задается до начала работы алгоритма. Задачу кластеризации удобно формулировать, используя характеристическую функцию. Характеристическая функция принимает значение 0, если элемент не принадлежит кластеру, и 1, если элемент принадлежит кластеру. С использованием характеристической функции кластеры описываются следующей матрицей разбиения:
|
U = [ϕki ], ϕki {0,1}, k = |
|
|
|
|
|
1, M , |
i = 1, c, |
|||
где |
k–я строчка матрицы U |
указывает на принадлежность объекта |
|||
X k |
= (xk1 , xk 2 ,..., xkn ) кластерам A1,A2,...,Ac. |
||||
|
Матрица U должна обладать еледующими свойствами: |
31
∑ϕki = 1, k = |
|
|
; |
|
|
||||
1, M |
(5.4) |
||||||||
|
|
|
|
|
|
|
|
||
i =1,c |
|
||||||||
0 < ∑ϕki < M , i = |
|
. |
|
||||||
1,c |
(5.5) |
||||||||
|
|
|
|
|
|||||
|
k =1,M |
|
Для оценки качества разбиения используется критерий разброса, показывающий сумму расстояний от объектов до центра своего кластера. Для евклидового пространства этот критерий вида:
|
|
|
|
∑ ∑ |
|
|
|
Vi − X k |
|
|
|
2 , |
|
|
|
|
(5.6) |
|||||
|
|
|
|
|
|
|
|
|
|
|||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||
|
|
|
|
i =1,c X k λi |
|
|
|
|
|
|
|
|
|
|||||||||
где Ai |
= {X p : ϕ pi |
= 1, p = |
|
}– i-й кластер; Vi |
= |
|
|
1 |
|
|
∑ X k центр i-го кластера; |
|||||||||||
1, M |
||||||||||||||||||||||
|
|
Ai |
|
|
||||||||||||||||||
|
|
|||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
X k Ai |
|Ai| – количество объектов кластера Ai .
Кластеризацию объектов X можно сформулировать как следующую задачу оптимизации: найти матрицу U, минимизирующую значение критерия (5.6). Дискретный характер четкого разбиения обуславливает негладкость целевой функции, что усложняет нахождение оптимальной кластеризации.
Базовый алгоритм нечетких c–средних. Нечеткие кластеры опишем сле-
дующей матрицей нечеткого разбиения: |
|
|
|
|
|
F = [µkj ], µkj [0,1], |
|
|
|
|
|
k = 1, M , i = 1, c, |
|||||
в которой k-я строчка содержит |
степени принадлежности объек- |
та X k = (xk1 , xk 2 ,..., xkn ) кластерам A1, A2,..., Ac.Единственным отличием матриц F и U является то, что при нечетком разбиении степень принадлежности объекта к кластеру принимает значения из интервала [0, 1], а при четком — из двухэлементного множества {0, 1}. Аналогичные (2.23)–(2.24) условия для матрицы нечеткого разбиения записываются выражением:
∑µki = 1, k = |
|
|
; |
|
|
||||
1, M |
(5.7) |
||||||||
|
|
|
|
|
|
|
|
||
i =1,c |
|
||||||||
0 < ∑µki < M , i = |
|
. |
|
||||||
1,c |
(5.8) |
||||||||
|
|
|
|
|
|||||
|
k =1,M |
|
Нечеткое разбиение позволяет просто решить проблему объектов, расположенных на границе двух кластеров – им назначают одинаковые степени принадлежностей, например, по 0.5. Недостаток нечеткого разбиения проявляется при работе с объектами, удаленными от центров всех кластеров. Удаленные объекты имеют мало общего с любым из кластеров, поэтому интуитивно хочется назначить им малые степени принадлежности. Однако по условию (5.7) сумма степеней принадлежности равна единице как у удаленных, так и у близких к центрам кластеров объектов. Для устранения этого недостатка можно исполь-
32
зовать разбиение, при котором произвольный объект из X должен принадлежать хотя бы одному кластеру. Для этого ослабляют условие (5.7) следующим образом:
i : µki . > 0, k.
Для оценки качества нечеткого разбиения используется следующий критерий разброса:
∑ ∑(µki )m |
|
|
|
Vi − X k |
|
|
|
2 , |
(5.9) |
||||||||
|
|
|
|
||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|||||||
i =1,c k =1,M i |
|
|
|
||||||||||||||
где |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
|
|
|
|
|
∑(µki )m X k |
|
|
|
|||||||||
|
|
|
|
|
|
|
|
|
|
|
|||||||
Vi = |
k =1,M i |
|
|
|
|
||||||||||||
|
|
∑(µki )m |
|
|
|
k =1,M i
центры нечетких кластеров; m (1, ) – экспоненциальный вес.
Теория алгоритма. Наиболее известный и часто применяемый метод минимизации критерия (5.9) – алгоритм нечетких c–средних. Он базируется на методе неопределенных множителей Лагранжа. Алгоритм находит локальный оптимум, поэтому выполнение его из различных начальных точек может привести к разным результатам.
Алгоритм нечетких c–средних:
Шаг 1. Установить параметры алгоритма: с – количество класте-
ров; т – экспоненциальный вес; ε − параметр останова ал-
горитма.
Шаг 2. Случайным образом сгенерировать матрицу нечеткого раз-
биения F, удовлетворяющую условиям (5.7)–(5.8).
Шаг 3. Рассчитать центры кластеров по формуле:
|
|
|
∑(µ ki )m X k |
|
|
|
|
|
|
|
|||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
k =1, N |
|
|
|
|
|
|
|
|||||||
Vi = |
|
, i = 1, c |
|||||||||||||||
|
|
|
|
|
|
|
|||||||||||
|
|
∑(µ ki )m |
|||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
k =1, N |
|
|
|
|
|
|
|
||||||
Шаг 4. Рассчитать расстояния между объектами из X и центрами |
|||||||||||||||||
кластеров: |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
|
|
|
|
|
|
|
|
|
|
|
|
||||||
D = |
|
|
|
− V |
|
2 , k = |
|
i = |
|
|
|||||||
X |
k |
|
1, M , |
1,c. |
|||||||||||||
kj |
|
|
|
|
i |
|
|
|
|
|
|
|
|
|
|
Шаг 5. Пересчитать элементы матрицы нечеткого разбиения для
всех k = 1, M , и i = 1, c :
если D > 0 , то |
ki |
= |
|
|
|
|
1 |
|
; |
|
|
|
|
|
|
||||
|
2 |
|
|
1 |
1/( m−1) |
||||
ki |
|
|
|
|
|
||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Djk ∑ |
2 |
|
||||
|
|
|
|
j = |
1,c |
D jk |
33
|
|
|
|
|
1, |
если |
j = i |
|
|
|
||||
если |
Dki = 0 , то |
µki |
= |
|
|
|
|
|
j = 1,c. |
|
||||
|
|
|
|
|
0, |
если |
j ≠ i |
|
||||||
Шаг 6. |
Проверить условие |
|
F − F * |
|
|
|
2 |
< ε , где F * |
– матрица нечет- |
|||||
|
|
|
||||||||||||
кого |
разбиения |
на |
предыдущей итерации |
алгоритма. Если |
||||||||||
«Да», то перейти к шагу 7, иначе – к шагу 3. |
||||||||||||||
Шаг 7. |
Конец. |
|
|
|
|
|
|
|
|
|
|
|
|
Пример описания исходных данных. Приводится пример тестовых дан-
ных для разрабатываемого алгоритма нечетких с-средних. Координаты на плоскости представляют точки образного рисунка «Бабочка»1. Координатные данные 2-мерного пространства признаков представлены следующей таблицей:
k |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
1 0 |
1 1 |
1 2 |
1 3 |
1 4 |
1 5 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
x1 |
1 |
1 |
1 |
3 |
3 |
3 |
5 |
7 |
9 |
1 1 |
1 1 |
1 1 |
1 3 |
1 3 |
1 3 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
x2 |
1 |
4 |
7 |
2 |
4 |
6 |
4 |
4 |
4 |
2 |
4 |
6 |
1 |
4 |
7 |
После выполнения нечеткой кластеризации данных должно произойти разбиение координат-объектов на два класса. Если алгоритм работает правильно, то результатом будет разделение на кластеры рисунка пополам − по семь объектов в каждом кластере. Восьмой объект в списке координат будет иметь принадлежность ½ к каждому из кластеров:
к |
1 |
2 |
3 |
4 |
5 |
|
|
6 |
|
7 |
|
8 |
9 |
1 0 |
1 1 |
1 2 |
1 3 |
|
1 4 |
1 5 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
µk1 |
9 |
6 |
9 |
7 |
8 |
|
7 |
|
9 |
|
0 |
|
1 |
3 |
2 |
|
3 |
1 |
|
4 |
1 |
|
0 , 9 0 |
0 , 9 7 |
0 , 9 0 |
0 , 9 4 |
0 , 9 9 |
|
0 , 9 4 |
|
0 , 8 7 |
|
0 , 5 0 |
|
0 , 1 2 |
0 , 0 5 |
0 , 0 0 |
|
0 , 0 5 |
0 , 0 9 |
|
0 , 0 2 |
0 , 0 9 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
µk 2 |
1 |
4 |
1 |
3 |
2 |
|
3 |
|
1 |
|
0 |
|
9 |
7 |
8 |
|
7 |
9 |
|
6 |
9 |
|
0 , 0 9 |
0 , 0 2 |
0 , 0 9 |
0 , 0 5 |
0 , 0 0 |
|
0 , 0 5 |
|
0 , 1 2 |
|
0 , 5 0 |
|
0 , 8 7 |
0 , 9 4 |
0 , 9 9 |
|
0 , 9 4 |
0 , 9 0 |
|
0 , 9 7 |
0 , 9 0 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
|
Пример программы. |
Сначала |
отлаживаем |
одну |
итерацию |
алгоритма |
нечеткой кластеризации с-средних. Представляется блок одной итера-
ции.
Начало блока.
Шаг 1. |
c := 2 c - число |
центров нечетких кластеров, |
может |
отличаться |
|
|
от числа |
координат X, но координатная |
система нечетких |
||
|
кластеров |
совпадает по размерности |
с координатами |
||
|
признака |
объекта (обект-коррдината |
признака |
- это |
сторока Х)
1 Тест «Бабочка» – это специальным образом сформированные исходные координаты признаков для тестов алгоритмов кластеризации. По результату теста нечеткой кластеризации можно продемонстрировать более качественное разделение признаков по сравнению с четкой кластеризацией [7].
34
m := 2 |
ε := 0.01 - Экспоненциальный вес и точность приближения к центр |
|
N := 100 Число объектов |
Value:= 10 |
F - Матрица (начальная) нечеткого разбиения принадлежностей; Fn - Матрица-результат!
Х- 2-мерное координатное пространство признаков
|
|
|
|
|
|
N |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
|
|
|
|
|
|
∑ (Fk, i)m (XT) k |
|
|
|
|
|
|
|
|
|
5.671 |
|
|
|
5.31 |
|
|
||||||||||||||||
|
|
|
|
|
|
k = 0 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||
Шаг 3. |
|
|
V := |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
V = |
|
|
V = |
|
|
|
|
|
|||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||||
|
|
|
|
i |
|
|
|
N |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
0 |
|
5.051 |
|
1 |
|
5.054 |
|
|
|||||
|
|
|
|
|
|
|
|
∑ (Fk, i)m |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||
|
|
|
|
|
|
|
|
k = 0 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
Шаг 4. |
|
|
|
|
|
|
|
|
T) |
k |
T |
T) |
k |
|
|
|
|
D - расстояние |
|
(метрика) до |
||||||||||||||||||
|
|
|
Dk, i := |
|
( |
|
|
|
|
( |
|
− |
|
|
|
|||||||||||||||||||||||
|
|
|
|
|
|
X |
|
|
|
− Vi |
|
X |
|
Vi |
|
центров нечетких |
|
|
|
|||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
кластеров каждого объекта |
||||||||||
Шаг 5. |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
D2 - Квадраты метрик, Dmin - признак присутствия нулевой |
|
|
|
|
|
|
||||||||||||||||||||||||||||||||
метрики к одному из кластеров для k-го объекта |
|
|
|
|
|
|
|
|
|
|
||||||||||||||||||||||||||||
j := i |
D2 |
:= (D |
) |
2 |
|
|
|
|
|
|
|
|
( |
T) k |
|
|
|
|
|
|
|
|
|
|
|
|||||||||||||
|
|
|
|
|
Dmin := min D2 |
|
|
≠ 0 |
|
|
|
|
|
|
|
|
|
|
||||||||||||||||||||
|
|
k, i |
|
|
k, i |
|
|
|
|
|
|
|
k |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
DminT = |
|
0 |
|
1 |
|
2 |
|
3 |
|
4 |
|
5 |
|
6 |
|
|
7 |
|
8 |
|
|
9 |
|
10 |
11 |
12 |
13 |
14 |
15 |
|
|
16 |
17 |
18 |
|
|||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
0 |
1 |
|
1 |
|
1 |
|
|
1 |
|
|
1 |
|
1 |
|
|
1 |
|
|
1 |
|
1 |
|
|
1 |
|
1 |
1 |
1 |
1 |
1 |
1 |
|
|
1 |
1 |
1 |
|
|
|
1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||
Перерасчет |
принадлежности |
к центрам |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Fn |
k, i |
:= if (D2 |
≠ 0) Dmin , |
|
|
|
k, i |
k |
Шаг 6.
Метрика расстояний между матрицами принадлежностей соседних итераций
|
|
|
|
|
1 |
|
|
|
|
|
|
, if(D2 |
|
0, 1, 0) |
||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
|
|
|
|
|
|
|
|
|
|
|
1 |
|
k, i |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
m−1 |
|
|
|||
|
|
|
c−1 |
|
|
|
|
|
|
|
|
|
|
|||
|
|
|
|
|
|
|
|
|
|
|
|
|
||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
|
|
|
∑ |
|
|
1 |
|
|
|
|
|
|
|
|
|
|
D2k , i |
|
|
|
D2 |
|
|
|
|
|
|
|
|||||
|
|
|
s = 0 |
|
(k, s) |
|
|
|
|
|
|
|
||||
δi := ( |
|
F i |
− Fn i |
|
)2 |
|
|
∑δ = 16.425 |
F := Fn |
|||||||
|
|
|
|
|||||||||||||
|
|
|
|
|
|
|
|
|
|
|
35
Проверить условие выхода δ < ε или выполнить следующую итерацию,
начиная с Шага 3.
Конец блока.
Перед написанием полной процедуры итераций можно прибегнуть к отладочному варианту на 3-х итерациях. Смысл его в следующем: сформировать программный модуль, где блок одной итерации повторя- ется не менее трех раз. Корректность работы 3-х итераций проверя- ется по факту уменьшения суммарного расстояний между колонками матриц F и Fn.Описание полной программы выполнения итераций алго- ритма с-средних, выполненной одной функцией FCL(), можно посмот- реть в Приложении 1.
Подготовка параметров функции FCL() алгоритма c-средних:
c := 2 m := 2 ε := 0.1 Iter := 100
MC := FCL(X, c , Iter, ε , m),
где MC − переменная возврата результата кластеризации, представляет собой 2-элементный вектор, присваиваемый поэлементно отдельным пе- ременным:
Fn := MC0 Матрица принадлежностей кластерам
V := MC1 Координаты центров
Функция использует следующие параметры: X – исходное координатное пространство объектов кластеризации; с − число кластеров; Iter −
максимальное число итераций для исключения зацикливания; ε − число точности приближения к центру; m − экспоненциальный вес (обычно m=2).
В качестве теста алгоритма их 3-х итераций можно провести рас- чет с данными кластеризации типа «Бабочка», приведенный в разделе описания исходных данных для двух кластеров (с=2). Результат не- четкой кластеризации должен соответствовать рис. 6. Кластеризация выполнена программой:
N := 100 |
Число объектов (14 - для теста "Бабочка") |
||
c := 2 |
m := 2 |
ε := 0.1 |
Iter := 100 |
MC := FCL(X, c , Iter , ε , m),
Fn := MC0 Матрица принадлежностей кластерам
V := MC1 Координаты центров
36
Рис. 6. Данные типа «Бабочка» — центры кластеров на плоскости и в объеме; каждая из фигур характерно представляет симметричный рисунок «бабочки»; принадлежность точек к классу усиливается на периферии и ослабляется к центру
X1k, i := if (Fn 0 )k > (Fn 1 )k, Xk, i, 0
X2k, i := if (Fn 0 )k ≤ (Fn 1 )k, Xk, i, 0
Результат (рис. 6).
После успешного тестирования генерируем координатное простран-
ство из 100 объектов с двумя центрами
c := 2 |
i := 0.. c − 1 |
|
|
N := 100 |
k := 0.. N |
||||||
Value := 10 |
Xk, i := rnd(Value − 5) |
|
sin(i) + cos (k) |
|
|||||||
|
|
||||||||||
|
|
|
|
|
|||||||
ε := 0.1 |
Iter := 100 |
|
|
|
|
|
|
|
|
||
MC := FCL(X, c , Iter, ε , m) |
|
|
|
|
|
|
|||||
Fn := MC0 |
Матрица принадлежностей кластерам |
||||||||||
|
|
|
|
|
|
|
|
|
|
||
V := MC1 |
Координаты |
центров |
|||||||||
|
|
|
|
|
|
|
|
|
|
||
|
( |
0 ) |
|
|
( |
1 ) |
, Xk, i |
|
|
||
X1k , i := if |
Fn |
k |
> |
|
Fn |
k |
, 0 |
||||
|
( |
0 ) |
|
|
( |
1 ) |
, Xk, i |
|
|
||
X2k , i := if |
Fn |
k |
≤ |
|
Fn |
k |
, 0 |
37
Интерполяция данных на поверхность |
dec := 10 |
|
dec round (V ) |
|
, 1 |
|
||
V := |
|
0 |
0 |
|
|
|
|
|
|
|
|||
0 |
dec round (V0) |
1 |
, 1 |
|
||
|
|
|
|
|
|
Xk , i := dec round (Xk , i, 1)
|
dec round (V ) |
||
V := |
|
1 |
|
|
|
||
1 |
dec round (V1) |
||
|
|
|
|
, 1
0
, 1
1
NN := Value |
dec |
|
ii := 0.. NN |
|
|
jj := ii |
|
|||||
Z1ii, jj := 0 |
|
Z2ii, jj := 0 |
Zc1ii, jj := 0 Zc2ii, jj := 0 |
NN = 100 |
||||||||
|
|
|
|
|
|
|
|
|
||||
Z_ := |
for |
k 0.. N |
|
|
|
|
|
|
||||
|
|
|
Z1X k , 0 , X k , 1 ← Fnk, 0 |
|
|
|
|
|||||
|
|
|
|
|
|
|
||||||
|
|
|
Z2X k , 0 , X k , 1 ← Fnk, 1 |
|
|
|
|
|||||
|
return |
Z1 |
|
|
|
|
|
|
|
|||
|
|
|
|
|
|
|
|
|
||||
|
|
|
|
|
Z2 |
|
|
|
|
|
|
|
V = |
16 |
|
|
|
|
13 |
|
|
|
|
||
|
|
|
V = |
|
|
|
|
|
||||
0 |
7 |
|
|
1 |
|
49 |
|
|
|
|
||
Zc1(V ) |
, (V ) := 1 |
|
Zc2(V ) |
|
, (V ) |
:= 1 |
|
|||||
|
0 |
0 |
|
0 |
1 |
|
|
1 |
0 |
1 |
1 |
|
Наблюдаем результат разделения координат-объектов на классы (рис. 7).
Практическое задание: по результатам одной итерации получить матрицу нечеткого разбиения. По нескольким итерациям отладить сходимость алгоритма к решению.
Содержание задания: генерация 2-мерного пространства координат объектов кластеризации; разработка и отладка алгоритма c-средних на примере одной и трех итераций.
Результат практики: демонстрация работы алгоритма с различными значениями координатных распределений; положительный результат работы − это монотонное уменьшение суммарного расстояния между столбцами матрицы принадлежностей Fn текущей и предыдущей итерации (минимальное число итераций − три).
38
Рис. 7. Разделение объектов на два класса; координаты центров наблюдаются на плоскости; принадлежности к центрам
видны в объеме, как скопления точек в диапазоне [0,1] оси аппликат
Контрольные вопросы
1.Назовите преимущества матрицы нечеткого разбиения перед четкой характеристической функцией кластерного анализа.
2.Какие пункты алгоритма подтверждают, что в качестве исходных данных используются координаты евклидова конечномерного пространства?
3.Перечислите основные трудности выполнения рассматриваемого алгоритма для ЭВМ.
5.2. Нормы кластерного анализа
Теория. В базовом алгоритме нечетких c–средних расстояние между объектом X = (x1 , x2 ,..., xn )и центром кластера V = (v1 , v2 ,..., vn ) рассчитывается че-
рез стандартную евклидову норму: D2 = X − V 2 . В кластерном анализе приме-
няются и другие нормы, среди которых часто используется диагональная норма и норма Махаланобиса. В общем виде норму можно задать через симметричную положительно определенную матрицу В размером
X − V |
|
|
|
2 = ( X − V )T B( X − V ), |
(5.10) |
|
|
||||
|
|
|
|
B |
|
|
|
|
|
|
где Т– операция транспонирования.
Для евклидовой нормы матрица В представляет единичную матрицу:
39
1 |
0 |
... |
0 |
|
|
|
|
B = 0 |
1 |
... |
0 |
M |
M |
O |
M |
|
|
|
|
0 |
0 |
... |
1 |
При евклидовой норме кластеры выделяются в виде гиперсфер. Для диагональной нормы матрица В задается следующим образом:
ω1 |
0 |
... |
0 |
|
||
|
0 |
ω |
|
... |
0 |
|
B = |
|
|
2 |
|
|
|
|
|
|
|
|
|
|
M |
M |
|
O |
M |
||
|
|
|
|
|
|
|
|
0 |
0 |
... |
ωn |
Элементы главной диагонали матрицы интерпретируются как веса координат. Диагональная норма позволяет выделить кластеры в виде гиперэллипсоидов, ориентированных вдоль координатных осей.
Для нормы Махаланобиса матрица В рассчитывается через ковариационную матрицу от X:
B = R −1 ,
где
R = 1 ∑( X k − X )( X k − X )T – ковариационная матрица;
M k =1,M
X = 1 ∑ X k – вектор средних значений данных.
M k =1,M
При норме Махаланобиса кластеры получаются в виде гиперэллипсоидов, оси которых могут быть ориентированы в произвольных направлениях.
Пример программы. В качестве примера используем норму Махалано-
биса. При изменении нормы расстояния центров кластеров производим модификацию программы с отдельными итерациями (или функцию FCL()), включая матрицу задания нормы B в формулу расстояния объект-центр
и добавляя матрицу задания нормы B в качестве нового параметра
FCL().
От предыдущего примера-теста алгоритма «Бабочка» приводимый алгоритм отличается только предварительным построением ковариаци- онной матрицы R. Также обратите внимание на способ центрирования координат относительно их среднего.
40