2047

Рассмотрим решение перечисленных проблем с точки зрения возможных операций над исходным графом для построения СПП.

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

Решение проблем:

1.Удаление единожды встретившихся ассоциаций:

Обозначим An {v|v AM &| P(u0,v)| 1&l((u,v)) 1} – «грубый шум», где u0,u TMV , u0 – корень TM . Исключая множество вершин

An из графа GM , получаем граф
		GM	(GMV,GM E), в котором
				u,v		v An .
GM V GMV	An , GM E GMV En , где En

2.Нормирование количества респондентов в группах: определение группы с максимальным количеством респондентов, которой присваивается коэффициент равный единице, остальным пропорционально отношению количества человек в рассматриваемой группе к определенному максимальному количеству респондентов:

Пусть дуга eMax TM E	такая, что l(eMax ) max l(e),	где
	e EL
EL TM E – множество дуг, инцидентных листьям. Тогда e EL		за-

меним l(e) на l(e) .

l(eMax )

Рассмотрим обозначенные проблемы с точки зрения осуществления плана ЛПР, аналитика формирующего анкету, и их возможное разрешение.

Анализ возможных операций и исходов при выборе итогового множества СПЗ с разрешением противоречий по подграфу с множеством уникальных характерных ассоциаций для групп:

1.Выбор характерных ассоциаций, уникально характеризующих определенную группу.

Решение проблемы осуществляется путем исключения из GM не-

характерных ассоциаций и построение ориентированного дерева GMch , в котором корень связан с любой ассоциацией единственной простой цепью:

Обозначим	Ach,i {a|a АM		E&| P(u0,a)| 1}	–
		&(vi,a) GM

множеств характерных ассоциаций, где u0 – корень TM . Исключая множества вершин Аch,i из графа GM , получаем граф GMch .

2.Все множества характерных ассоциаций пусты.

50

Решение проблемы осуществляется путем изменения структуры дерева GMch исключением всего предпоследнего уровня иерархии дерева TM :

Пусть k (Ach,k ), тогда w TMV из второго снизу уровня иерархии ( v VL(d(w,v) 2)):

выделим множество U {u|u TMV &(w,u) TM E};

добавим к TMV вершины uG и uB ;

добавим к TM E		дуги (w,uG ) и (w,uB )	такие, что
l((w,uG )) l((u,vG ))	и l((w,uB )) l((u,vB)), где vG		и vB – листья,
u U		u U

соответствующие «хорошей» и «плохой» кредитной истории;

u U удалим из TMV вершины vG ,vB ,u.

3.Некоторые множества характерных ассоциаций пусты. Решение проблемы осуществляется путем изменения структуры

дерева GMch исключением всего предпоследнего уровня иерархии дерева TM :

Пусть k (Ach,k ), тогда w TMV из второго снизу уровня иерархии ( v VL(d(w,v) 2)):

выделим множество U {u|u TMV &(w,u) TM E};

добавим к TMV вершины uG и uB ;

добавим			к	TM E дуги (w,uG )			и	(w,uB )		такие,	что
l((w,uG )) l((u,vG )) и l((w,uB )) l((u,vB)), где vG										и vB – листья,
u U					u U
соответствующие «хорошей» и «плохой» кредитной истории;
построим			множества		вершин	A	{a|(v		G	,a) GchE}	и
						G	u U			M
		,a) GchE};
A {a|(v	B
B				M
u U				TM E
добавим			к		множество		дуг	{(uG ,a)|a AG}			и
{(uB ,a)|a AB},				где	l((uG ,a))			l((vi ,a))			и
l((uB ,a))	l((vi ,a));							u U,a AG
u U,a AB
u U удалим из TMV вершины AG ,AB ,								vG ,vB ,u.

4.Все множества характерных ассоциаций не пусты, но количество ассоциаций неодинаково в группах.

51

|VL|

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

группах не станет равным:
­ упорядочим вершины из Ach,i					по убыванию весов инцидентных
им дуг. Найдем c	min	min	| A	|,	затем i 1,2, ,|V	L	| из	A	уда-
		1 i |V |	ch,i					ch,i
		L

ляем | Ach,i | сmin вершин, инцидентных дугам с наименьшими весами.

5.Совокупное количество выявленных ассоциаций больше заданного ЛПР.

Решение проблемы осуществляется путем приведения совокупного количества ассоциаций к указанному ЛПР: построим множество

ассоциаций Ach Ach,i , упорядочим его элементы по убыванию ве-

i 1

сового коэффициента (a) l((vi ,a)). Из множества Ach удалим

1 i |VL|, a Ach,i

| Ach | cЛПР ассоциации с наименьшими весовыми коэффициентами, где сЛПР – ограничение на количество ассоциаций, заданное ЛПР. Из дерева GMCH (СH – credit history) удалим вершины, соответствующие удаленным ассоциациям.

Далее представлен анализ возможных операций и исходов при выборе итогового множества СПЗ с разрешением противоречий по подграфу с множеством смежных характерных ассоциаций (для групп с различиями по кредитной истории).

1.Выбор ассоциаций со значимым различием, характеризующих группы с одинаковым набором социально-демографических признаков, но отличные по признаку «хорошая»/«плохая» кредитная история.

Решение проблемы осуществляется путем поиска смежных вершин в ориентированных подграфах, полученных из исходного GM , далее путем выбора, где пути к узлам с «хорошей» и «плохой» кредитной историей равны и содержат один и тот же набор вершин. Найденные смежные вершины должны принадлежать только одному из подграфов.

Пусть VL – множество листьев TM . vi VL,i 1,2, |VL | построим

AchСH,i {a | a A&(vi,a) G'M E &

52

l((vi,a)

& u ((u,v ),(u,v

j

),(v

j

,a) G'

M

E)&

0.5 }

– множества ассо-

i

l((v

j

,a)

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

Таким образом, получим новый граф GMCH , являющийся деревом,

листьями которого будут ассоциации из множеств AchCH,i , инцидентные

vi VL,i 1,2, |VL |.

2.Все множества ассоциаций, характеризующих группы с одинаковым набором социально-демографических признаков, но отличные по «хорошая»/«плохая» кредитная история, пусты.

Решение проблемы осуществляется путем изменения структуры дерева GMCH исключением всего предпоследнего уровня иерархии де-

рева TM :

Пусть k (AchCH,k ), тогда w TMV из второго снизу уровня иерархии ( v VL(d(w,v) 2)):

выделим множество U {u|u TMV &(w,u) TM E};

добавим к TMV вершины uG и uB ;

добавим к TM E ребра		(w,uG ) и (w,uB )	такие, что
l((w,uG )) l((u,vG ))	и l((w,uB ))	l((u,vB)), где vG	и vB – листья,
u U		u U

соответствующие «хорошей» и «плохой» кредитной истории;удалим из TMV множество вершин U.

3.Некоторые множества ассоциаций, характеризующих группы с одинаковым набором социально-демографических признаков, но отличные по «хорошая»/«плохая» кредитная история, пусты.

Решение проблемы осуществляется путем изменения структуры дерева GMСН исключением всего предпоследнего уровня иерархии дерева TM :

Пусть k (AchCH,k ), тогда w TMV из второго снизу уровня иерархии ( v VL(d(w,v) 2)):

выделим множество U {u|u TMV &(w,u) TM E};

добавим к TMV вершины uG и uB ;

53

добавим			к	TM E	дуги (w,uG )			и	(w,uB )	такие,	что
l((w,uG )) l((u,vG )) и l((w,uB )) l((u,vB)), где vG										и vB – листья,
u U						u U
соответствующие «хорошей» и «плохой» кредитной истории;
построим			множества			вершин	A	{a|(v ,a) GCH E}			и
							G		G	M
		,a) GCH E}						u U
A {a|(v	B				;
B				M
u U				TM E
добавим			к			множество		дуг	{(uG ,a)|a AG}		и
{(uB ,a)|a AB},				где		l((uG,a))			l((vi,a))		и
l((uB ,a))	l((vi ,a));								u U,a AG
u U,a AB
u U удалим из TMV вершины AG ,AB ,									vG ,vB ,u.

4.Все множества ассоциаций, характеризующих группы с одинаковым набором социально-демографических признаков, но отличные по «хорошая»/«плохая» кредитная история, не пусты, но количество ассоциаций неодинаково в группах.

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

Упорядочим вершины из AchCH,i по убыванию весов инцидентных

им дуг. Найдем c		min	| ACH	|, затем i 1,2, ,|V	L	| из ACH	уда-
	min	1 i |VL|	ch,i			ch,i

ляем | AchCH,i | сmin вершин, инцидентных дугам с наименьшими веса-

ми.

5.Совокупное количество выявленных ассоциаций больше заданного ЛПР.

Решение проблемы осуществляется путем приведения совокупного количества ассоциаций к указанному ЛПР:

|VL|

Построим множество ассоциаций AchCH AchCH,i , упорядочим его

				i 1
элементы	по	убыванию	весового		коэффициента
(a)	l((v ,a)). Из множества		ACH	удалим	| ACH | c	ЛПР	ассо-
	i		ch		ch

1 i |VL |,a AchCH,i

циации с наименьшими весовыми коэффициентами, где сЛПР – ограничение на количество ассоциаций, заданное ЛПР. Из дерева GMCH удалим вершины, соответствующие удаленным ассоциациям.

54

Аналогичное решение проблем осуществляется для GWm. Алгоритм формирования анкеты КЗ использует БП, то есть набор

разработанных решающих правил и критериев, представленных в табл. 3.1, 3.2. Правила составляют БП для определения СЗП, формирующих СПП кредитного заемщика, и разработаны для двух задач: определения СЗП, являющихся уникальными ассоциациями для определенного типа КЗ (см. табл. 3.1) и являющихся смежными ассоциациями для нескольких типов КЗ, но с характерными значимыми отличиями (см. табл. 3.2).

Таблица 3.1

Правила для определения СЗП, являющихся уникальными ассоциациями для определенного типа КЗ

							Значение
							по
							умолчанию	Тип
							(True – ис-		Настраи-
	Условное		Правило					правила
							тина,		вается
	обозначение							(H-заголовок,
							False –		ЛПР
								B-тело)
							ложь,
							Null – не
							задано)
	1		2				3	4	5
		Множество		уникаль-
	G	ных ассоциаций пус-					NULL	H	Нет
		тое
	A	Есть	уникальные			ас-	NULL	H	Нет
		социации		для	всех
		групп
	B	Количество		ассоциа-			NULL	H	Нет
		ций	одинаково			во
		всех группах
		Выполнить перегруп-
	C	пировку для			поиска		False	H	Да
		уникальных		ассоциа-
		ций во всех группах
		Есть	ограничение			на
	D	количество		ассоциа-			False	H	Да
		ций для СПП

55

Продолжение табл. 3.1

	1			2				3	4	5
		Количество			найден-
	E	ных	ассоциаций				рав-	NULL	H	Нет
		но	количеству				для
		СЗП
		Количество			найден-
	F	ных		ассоциаций				NULL	H	Нет
		меньше		количества
		СЗП
		Выполнить перегруп-
	H	пировку пока множе-						True	H	Да
		ство	уникальных				ас-
		социаций пустое
		Усечь список				ассо-
	K	циаций		до	равного			False	H	Нет
		количества их в каж-
		дой группе
		Определить			количе-
	S1	ство	уникальных				ас-	NULL	B	Нет
		социаций		в		каждой
		группе
	S2	Определить				общее		NULL	B	Нет
		количество			ассоциа-
		ций
		Передать все найден-
	S3	ные ассоциации в ре-						NULL	B	Нет
		зультат		формирова-
		ния СПП
		Сортировать			найден-
		ные	ассоциации				по
	S4	весу, оставить по од-						NULL	B	Нет
		ной на группу с мак-
		симальным				весом,
		поместить в результат
		Сортировать			найден-
		ные	ассоциации				по
		весу	внутри			групп,
		отбрасывать по одной
	S5	из группы, пока ко-						NULL	B	Нет
		личество больше тре-
		буемого, затем по-
		местить			итоговое
		множество в				резуль-
		тат

56

Окончание табл. 3.1

	1			2					3	4	5
		Выполнить перегруп-
		пировку, пока не бу-
	S6	дут	найдены				уни-		NULL	B	Нет
		кальные ассоциации
		для каждой группы
		Передать					пустое
	S7	множество				ассоциа-			NULL	B	Нет
		ций в результат
		Выполнить перегруп-
	S8	пировку, пока множе-							NULL	B	Нет
		ство	уникальных					ас-
		социаций пустое
		Сортировать				найден-
		ные	ассоциации					по
		весу внутри перефор-
		мированных					групп,
		отбрасывать по одной
	S9	из группы,				пока		ко-	NULL	B	Нет
		личество больше тре-
		буемого, затем по-
		местить				итоговое
		множество			в		резуль-
		тат
		Сортировать				найден-
		ные	ассоциации					в
		группе		по	убыванию
	S10	веса	и	отбросить				ас-	NULL	B	Нет
		социации			снизу			по
		минимальному					коли-
		честву в группе
	X	Пустое тело правила							NULL	B	Нет

Разработанные правила представлены в виде древовидной структуры с иерархической проверкой символов (заголовков правил), где в квадрате указан заголовок правила, в круге – тело правила, Х в круге

– отсутствие тела правила, T на связи – заголовок принял значение «истина», F на связи – «ложь».

На рис. 3.3, 3.4 показана логическая структура поиска решения на основе разработанной БП.

57

Таблица 3.2

Правила для определения СЗП, являющихся смежными ассоциациями для нескольких типов КЗ, но с характерными значимыми отличиями

	Условное							Значение	Тип	Настраи-
			Правило					по умолча-		вается
	обозначение								правила
								нию		ЛПР
	1			2				3	4	5
	AB	Подмножество				смежных		NULL	H	Нет
		вершин пустое
		Выполнить			перегруппи-
	BC	ровку для поиска смежных						TRUE	H	Да
		ассоциаций
	CD	Есть смежные ассоциации						NULL	H	Нет
		для каждой группы
		Выполнить			перегруппи-
	DE	ровку для поиска смежных						False	H	Да
		ассоциаций		для		каждой
		группы
		Есть ограничение на коли-
	EF	чество	смежных			ассоциа-		False	H	Да
		ций	для	формирования
		пространства
	FG	Количество смежных ассо-						NULL	H	Нет
		циаций больше заданного
		Задан уровень			значимости
	HI	различий, меньше которого						False	H	Да
		в результирующем					СПП
		быть не должно
	S20	Передать пустое множест-						NULL	B	Нет
		во в результат
		Выполнять			перегруппи-
	S21	ровку,	пока		множество			NULL	B	Нет
		смежных ассоциаций					пус-
		тое
	S22	Передать полученное мно-						NULL	B	Нет
		жество в результат
		Отсортировать				смежные
		ассоциации		по убыванию
		веса, отбросить ассоциации
	S23	с меньшими весами до оп-						NULL	B	Нет
		ределенного		количества и
		передать оставшиеся ассо-
		циации в результат

58

Окончание табл. 3.2

1

2

3

4

5

Отбросить

смежные

ассо-

S24

циации с уровнем значи-

NULL

B

Нет

мости различий меньше

заданного

Выполнять

перегруппи-

S26

ровку, пока не найдены

NULL

B

Нет

смежные ассоциации

для

каждой группы.

Рис. 3.3. Древовидная структура иерархической проверки символов (заголовков правил), являющаяся базой правил для выбора СПП из набора уникальных ассоциаций, где в соответствии с табл. 3.1 в квадрате указан заголовок правила, в круге – тело правила, Х в круге – отсутствие тела правила, T на связи –

заголовок принял значение «истина», F на связи – «ложь»

59