СППР

139

Вычислительная часть предложенного алгоритма легко реализуется на матрице значений функций принадлежности, полученной из матрицы знаний путем выполнения операций min и max.

Приведенный алгоритм нахождения дискретных значений {dl,d2,...,dm) выходной переменной у по заданному вектору

фиксированных значений входных переменных X* =^xi*,х2,...<х*п) и

матрице знаний позволяет идентифицировать объект Y= f y(xux2,...,xn) с

дискретным выходом.

1.8.3.3. Методрешения задач нечеткого кластерного анализа

Согласно [89] кластер-анализ - это способ группировки многомерных объектов, основанный на представлении результатов отдельных наблюдений точками подходящего геометрического пространства с последующим выделением групп как “сгустков” этих точек.

Таким образом основная цель анализа - выделить в исходных многомерных данных такие однородные подмножества, чтобы объекты внутри групп были похожи в известном смысле друг на друга, а объекты из разных групп - не похожи, Под “похожестью” понимается близость объектов в многомерном пространстве признаков, и тогда задача сводится к выделению в этом пространстве естественных скоплений (“гроздей”) объектов, которые и считаются однородными группами.

Как указано в [89] неформально проблему разбиения выборочного множества на классы можно, сформулировать следующим образом: “Сгруппировать точки выборочного множ^ггва в подмножества (называемые кластерами) так, чтобы подобные точки относились к одному и тому же подмножеству, а не подобные - к различным подмножествам.

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

Рассмотрим задачу разделения множества S объектов, каждый г-й элемент которого характеризуется вектором Pi = ри, p2i,..., pkl признаков, на области (кластеры), отвечающие компактным группам изображений, при этом вектор признаков характеризуется как качественными, так и количественными признаками.

Методика разбита как бы на две части: в первой части рассматривается пример с проведением процедуры кластеризации как это частично описано в [90], [91], [92], [93] только с количественными признаками; во второй части к данным количественным признакам

140

добавляются качественные и показывается, каким образом происходит объединение признаков и дальнейшая кластеризация данных.

а) Пример выбора оптимальной кластеризации по качественным признакам.

Исходная выборка данных представлена в табл. 1.11

Т а б л и ц а 1.11

Блок I. Нормировка переменных. В [29] приведены наиболее распространенные способы нормирования показателей (переход от исходных значений х к нормированным z).

				141
где х, cr		- соответственно среднее	и среднее квадратическое
отклонение	JC;	X 1 - некоторое эталонное	(нормативное) значение	х ;
х тах, Xmin -	наибольшее и наименьшее значение х .
Пронормируем исходные данные по формуле (1.117). Таблица с
нормированными исходными данными представлена ниже (табл. 1.12).
			Т а б л и ц а	1.12

Блок 2. Получаем матрицу близости D , элементы которой определяем как межточечные расстояния по формуле

(1.118)

где п - количество всех признаков (для нашего примера ft = 5);

г = I, S (для нашего примера J = Il); j = (7 + \ ) , s .

К примеру из табл. 1.12

(1.119)

= 0.4401.

Рассчитывая аналогичным образом остальные межточечные расстояния для нормированных исходных данных, получим таблицу межточечных расстояний между объектами (табл. 1.13).

142

Блок 3. Построение диполей (пар близко расположенных объектов) и разделение данных на подвыборки A f \ В и С П D. Чтобы достичь однозначного выбора (регуляризации) непротиворечивой кластеризации, последние находятся на двух подвыборках данных, на которых требуется совпадение выбора кластеров.

Т а б л и ц а 1.13

Для выбора кластеризации в качестве основного [90] выходного критерия используется критерий непротиворечивости: этот критерий требует, чтобы кластеризация, полученная на половине выборки A(C), возможно меньше (по всем показателям) отличалась от кластеризации, полученной на половине выборки В(D). Поясним правило образования диполей, которое описано в [91], [92]: по матрице близости объектов D (Sj t Sj ) строятся диполи, причем построение диполей продолжается до

тех пор, пока все объекты войдут в множества А и В, при этом, противоположные вершины (объекты) относятся к разным множествам. Наиболее короткие диполи приведены ниже:

1)3 0.0411 8	2)3 0.0789 6	3)4 0.0880 5		4)6 0.0952 8
5)20.1162 7	6)40.1405 11	7)50.1831	11	8)80.2120 9
9) I 0.2240 10	10) 3 0.2400 9	11)3 0.2400 9		12) 4 0.2529 10

В результате получим девять диполей:

Блок 4. Вычисляем таблицы межточечных расстояний для подвыборок А (табл.1.14) и В (табл.1.15).

												143
									Т а б л и ц а			1.14
Подмно­		I	II	III	IV	V	VI		VII	VIII		IX
жество
	А	3	3	4	6	2	4		5	8		1
I	3	0	0	0.4034	0.0789	0.5950	0.4034	0.3626		0.0411		0.4629
Її	3		0	0.4034	0.0789	0.5950	0.4084	0.3626		0.0411		0.4629
III	4			0	0.4617	0.5111	0	0.0880		0.3716		0.3393
IV	6				0	0.5976	0.4617	0.4268		0.0952		0.4818
V	2					0	0.5111	0.5716		0.5734		0.4401
VI	4						0	0.0880		0.3716		0.3393
VII	5								0	0.3341		0.3882
VIII	8									0		0.4298
IX	I											0
									Т а б л и ц а			1.15
Подмно­		I	II	QI	IV	V	VI		VII	VIII		IX
жество
	в	8	б	5	8	. 7	и		11	9		10
I	8	0	0,0952	0.3341	0	0.5004	0.4563	0.4563		0.2120	0.4803
II	6		0	0.4268	0.0952	0.5249	0.5381	0.5381		0.2487	0.5572
III	5			0.	0.3341	0.5214	0.1831	0.1831		0.3489	0.3162
IV	8				0	0.5004	0.4563	0.4563		0.2120	0.4803
V	7					0	0.4692	0.4692		0.3199	0.4539
VI	Il						0		0	0.4095	0.3370
VII	11								0	0.4095	0.3370
VIU	9									0	0.4181
IX	10						" « U		-			0

Блок 5. По таблицам строим два дерева перебора гипотез о числе кластеров (рис. 1.33 ).

Блок 6. Осуществляем перебор кластеризаций по критерию непротиворечивости, которыйрассчитываем по формуле [90]:

	I r _ Klr	(1.120)
	CYab= — ---- > min,
	Л-
где	к - количество кластеров, выделенное на выборках	А и В
(различных и совпадающих);
Ak- количество совпадающих кластеров.
Как	видно из рис.1.33, CYab- 0 при кА=кв = 4, что	и будет

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

когда кл = кв = 1,кл= кв = 9 -	являются	тривиальными и не
рассматриваются:
Запишем объединенные адреса	объектов	при которых CYab = 0
(таблица 1.16).

144

Рис.1.33 Иерархическийперебор гипотез о числе кластеров: а - для подвыборкн А, 6 - для подвыборки В

Блок 7. Доопределение (регуляризация). Как указано в [92] критерию может быть присуща неоднозначность. Он указывает своим минимумом оптимальную модель, а также некоторые ложные модели. Проведем дополнительную проверку разделив множество объектов на подмножества С и D, для этого формирование подмножеств C n D осуществим по следующему правилу [92]: для диполей, имеющих нечетные номера, объекты, принадлежащие А, относятся к С; В - соответственно к D, а для четных номеров диполей - наоборот. Далее осуществляем перебор кластеризаций по суммарному критерию непротиворечивости, выражение которого имеет вид {92]:

( 1. 121)

Таким образом для подмножеств C n D получим следующие диполи:

Адрес диполя	I	II	ΠΙ	IV	V	VI	VII	VIII	IX
С:	3	6	4	8	2	11	5	9	I
D:	8	3	5	6	7	4	11	-8	10

Далее алгоритм идентичен как для подвыборок А и В. Приведем лишь дендограммы для подвыборок С и D для наглядности (рис. 1.34).

В дальнейшем производим те же операции, что и в блоке б. Как видно из рис. 1.34 CYcd = Опри кс = kD - 2 и кс = kD = 4, то есть в данном случае наличие нескольких нулей значений критерия непротиворечивости. Рассчитывая суммарный критерий CYz видно, что CYz = 0 при

145

кл = к в = кс = kD = 4 , что и будет соответствовать оптимальной

кластеризации (табл. 1.16).

Т а б л и ц а 1.16

б) Пример выбора оптимальной кластеризации по качественным и количественным признакам.

Рис. 1.34 Иерархический перебор гипотез о числе кластеров: а - для подвыборки С, б - для подвыборки D

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

представляющий собой нечеткое множество будет представлен

146

следующим образом на конечном универсальном множестве

JC *= { } [55].

Р 1 * Р Л ( Х i ) / * t + МЛ ( * 2 ) / X i + - + H r i ( X i ) Z X j , (1.122)

где aMr^( Xj ) / х/ ' - пара “функция принадлежности/элемент”,

называемые синглтоном, а “+” - обозначает совокупность пар, T - нечеткий терм (к примеру: H - низкий, С - средний, В - высокий).

Дополним исходную выборку данных представленную в табл.1.11 качественными показателями pi r p7 в виде терм-множеств (табл. 1.17).

Т а б л и ц а 1.17

В соответствии с (1.122) пусть качественные признаки представлены в следующем виде:

	147
p f = 0 / у і+ 0 .3/у 2+0 Л / у 3+1 / у 4;	(1.127)
j»f = 0 . 3 / ¾ + 1 / ¾ + 0 . 5 / ^ + 0 . 8 / * ;	0-128)

Блок 1. Нормировка количественных переменных как это описано в предыдущем примере (см. табл.1.12 для количественных признаков).

Блок 2. Получаем матрицу близости D, элементы конторой рассчитываем:

-для качественных оценок находим относительное эвклидово

расстояние ε по степеням принадлежности [55], если А и В - два нечетких подмножества, то

а(1, S ) = ] - Σ (μ Λ(Χ,) - Mt (Xt))1,	(1.129)
VП Ui
где и- количество элементов подмножества и
0<е(А,В)й\.	(1.130)

Таким образом можно рассчитать относительные эвклидовы расстояния для качественных показателей. К примеру‘из табл.1.18:

(0.8-0.2/ + (0.7-0/ + + (0.9-0/ + (0.5-0.6/ +

е( Реб> Р»б) ~	+ (0.6-0.8/+(0.5-0.4/ +	(1.131)
	+ (0.4-1/
= 0.5451;
	(1-0)4(0.5-0.3)2+
ε(ρΖ, ΡΪ·,) = J t [+ (0.5 - 0.7)2 + (0.2 - l)2J ~		(1-132)

=0.6558;

-обобщенное межточечное расстояние M(StlSj ) - Ie находим по следующей формуле:

м(s,·, Sj) = Ig = Д Σ (рік - Pjkf +	Σ £(p I’ p D	I О ■·:133)
VЛ U»i	*-r+i	J

где η - количество всех признаков (для нашего примера я = 7);

148

г - количество количественных признаков (для нашего примера

г = 5).

Рассчитав по формуле (1.133) все межточечные расстояния получим таблицу межточечных расстояний между объектами, имеющую следующий вид (табл. 1.18):

									T а б л и ц а		1.18
Объекты	SI	S2	S3	S4	S5	S6	S7	S8	S9	SlO	SU
SI	0	0.4431	0.4736 0.4971		0.4487 0.5385		0.3437 0.4507 0.4725			0.3599	0.4347
S2		0	0.6182 0.5768 0.5552 0.5668				0.2601	0.6034 0.4406 0.4926			0.5512
S3			0	0.4582 0.5087 0.3746			0.5166 0.0347 0.3149 0.5921				0.4116
S4				0	0.2770 0.5523		0.5648 0.4385 0.3962			0.3419 0.3283
S5					0	0.5207	0.5365 0.4946 0.4828 0.2672				0.4346
S6						0	0.5666 0.3773		0.3494 0.6024 0.5854
S7							0	0.5001	0.4498 0.4908 0.4780
S8								0	03002 0.5741		0.3856
S9									0	0.5206 0.4217
SlO										0	0.4960
S ll											0
Далее как вблоке 3 предыдущего примера строим диполи и разделяем
данные на две подвыборки A n B n C n D .
Приведем наиболее короткие диполи:
1)3 0.0347 8		2)20.2601 7				3)5 0.2672 10			4)4 0.2770 5
5) 8 0.3002 9		6) 3 0.3149 9				7) 4 0.3283 11			8) 4 0.3419 10
9) 1 0.3437 7		10)6 0.3494 9				11) 1 0.3599 10			12)3 0.3746 6
В результате получим десять диполей:
Адрес диполя		I	II	ΠΙ	IV	V	VI	VII	VIII	IX	X
А:		3	2	5	4	8		4	4	1	6
В:		8	7	10	5	9	9	I i	10	7	9
С:		3	7	5	5	8	9	4	10	1	9
D:		8	2	10	4	9	3	II	4	7	6

Вычисляем таблицы межточечных расстояний для подвыборок А и В, CnD, строим деревья перебора гипотез о числе кластеров и рассчитываем критерий непротиворечивости, как это описано в примере для количественных показателей.