Устойчивость разбиения данных на интервалы в задачах распознавания и поиск скрытых закономерностей

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

К числу основных проблем построения информационных моделей в слабо структурированных предметных областях относятся выбор описаний допустимых объектов и высокая комбинаторная сложность алгоритмов для поиска логических закономерностей. На решение этих проблем ориентирована разработка методов поиска информативных наборов признаков и подмножества объектов обучения, которые обладают лучшим качеством в смысле решения задач распознавания, чем исходные множества признаков и объектов [1]. На базе методов ИАД разрабатываются информационные модели для объяснения процесса интуитивного принятия решений.

Проблемы имеются в выборе способов предобработки данных с целью уменьшения комбинаторной сложности алгоритмов ИАД, в разработке способов повышения обобщаю- Згуральская Екатерина Николаевна, старший преподаватель кафедры «Самолетостроение».

щей способности алгоритмов распознавания, связанных с выбором оптимальных по мощности наборов признаков в описании допустимых объектов. Отсутствие ограничений на число признаков в наборах может привести к явлению, которое Беллман назвал «проклятие размерности» [2].

Существует потребность в разработке и обосновании новых эвристик и критериев для проверки истинности гипотезы о компактности классов [1] при распознавании образов в рамках информационных моделей, в использовании новых методов визуализации для анализа отношений между объектами. Для удовлетворения такой потребности предлагается использовать интервальные методы анализа данных [3]. Границы интервалов определяются как для исходных и латентных признаков, так и для значений мер близости между объектами и признаками.

Одним из универсальных ограничений на использование интервальных методов является инвариантность к масштабам измерений данных. Важность свойства инвариантности выражается в однозначности интерпретации результатов алгоритмов ИАД в рамках информационной модели предметной области. Свойство инвариантности даёт возможность для:

• -    выбора латентных признаков при моделировании процесса интуитивного принятия решений;

• -    визуализации описаний объектов из разнотипного признакового пространства;

• -    упорядочивания разнотипных признаков по отношению информативности.

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

• 1 . ОПИСАНИЕ МЕТОДА РАЗБИЕНИЯ ЗНАЧЕНИЙ ПРИЗНАКОВ НА ИНТЕРВАЛЫ

И ОЦЕНКИ КАЧЕСТВА РАЗБИЕНИЯ

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

Пусть дано множество M допустимых объектов, разбитое на l непересекающихся подмножеств (классов) K ₁,..., K. Считается, что представители классов заданы через выборку (подмножество M ) объектов 5- = (S ,, 52. . Объекты выборки описываются с помощью n разнотипных признаков, из которых 3 измеряются в интервальных шкалах, а ': — " в номинальных.

Вычисление устойчивости объектов по значениям исходных и латентных признаков производится относительно отдельных классов. Необходимость сведения решения к двухклассовой задачи распознавания с объектами из K_t и CK_t = M\K_t , t =1,..., I связана с тем, что:

• - значение любого количественного признака (исходного и латентного) относительно. Объекты каждого из классов противопоставляются объектам противоположных классов (например, класс заболевших и умерших от сердечно-сосудистых заболеваний противопоставляется классу практически здоровых людей);

• -    отсутствуют наборы аналитических функций для восстановления зависимостей в пространстве разнотипных признаков.

Требуется:

• -    на множестве допустимых значений каждого из количественных признаков определить разбиение на минимальное число непересекаю-щихся интервалов, в границах которых доминируют значения объектов класса Kt или CK_t = M \ Kt , t =1,., l ;

• - вычислить значения меры устойчивости разбиения на интервалы признаков объектов Е ₀ относительно класса K, t =1,., l .

Обозначим через I,J множество номеров соответственно количественных и номинальных (качественных) признаков X = { x₁, ..., x_n } в описании допустимых объектов, | 1 + | J | = n . Для удобства выкладок будем рассматривать два класса объектов K ₁ и K ₂.

Произведём выбор интервалов для каждого количественного признака, в границах которых доминируют значения объектов класса Kt или K3-t, t =1,2. Для этого упорядочим значения ."-го признака (-" 2 /) по возрастанию г .г .... .т

.

Согласно определяемого ниже крите- рия последовательность (1) разбивается на

-_ -_ > 2 ■ непересекающихся интервалов

[г. , г Г - 2 £ 2 2 £ ' £ "2 i = 2, г_. Значе-L см* с nJ                                        с ния, лежащие в интервале [у -у , далее могут рассматриваться как

градация номинального

признака.

Пусть •",        3- ; 3 — количе ство представителей соответственно классов

?".. '.— в интервале [у '- . Для рекурсивной процедуры выбора значений ". ■. используется критерий [4] " '

|^3ил4 dg__f(u,v) I l|E_DUK_t| |E₀UJC_s__tll

Границы первого интервала ■ ■. ■ ■. "на по-L сл С n J следовательности (1) вычисляются по максимуму критерия (2). Аналогичным образом определяются границы для [". " v > 2 на значениях (1), не вошедших в ••. " ". Критерием останова процедуры служит покры- тие всех значений (1) непересекающимися ин- тервалами.

Обозначим через

414 ^ l^u^T^^

dg_t(u,v)

l^o ^ ^3-tl

результаты оптимального разбиения по (2) для каждого интервала , : = 2 ".. Количественно доминирование выражается через значения функции принадлежности 2 : ■ Е 2 2 класса X. : = 2 2.

Значение функции принадлежности с -го признака к /Л по интервалу определим как

/ 1 ^{( i} ) =

Пи

Пи ⁺ n 2 i

.

С учётом того, что f_t(i )=1 - f_3-t ( i ), t =1,2, устойчивость признака по множеству интервалов разбиения вычисляется как

U () = 1 v! f^i ⁾⁽ v - u ^{+ 1 )1 f (} i ) > 0"⁵’    ₍₄₎

^C m { [ Г, , r v J! l^{( 1} - ^{f ( i ))( V} - ^{U +} 1 )’ ^{f ( i} ) <  ⁰"⁵’

Рис. 1. Разбиение упорядоченных значений признака на интервалы

и выражает степень однородности (не переме-шанности) значений c-го признака объектов в границах интервалов доминирования, определяемых по (2,3). Если (в идеале) в границах интервалов лежат значения признака одного класса, то .

Визуальная интерпретация границ интервалов, полученных по (2), показана на рис. 1, где ( u 1, v 1), ( u 2, v 2),… – индексы упорядоченной последовательности (1). Нетрудно заметить, что не существует двух соседних интервалов, в которых доминировали представители одного класса.

Рассмотрим модификацию критерия (4) для случая наличия пропусков в данных. С учётом пропусков в данных критерий (4) примет вид

d t ( и ,v ) d* 3 _t ( u,v )

c

c

3 - p

^ max

,

где T p , T 3 c - p

количество значений признака

x c e X ( n ) без пропусков у объектов E 0 соответственно из классов K_p и K_3-p . Естественным условием для реализации (5) является:

• – число различных значений признака больше или равно 2;

• - значения T p >  0, 7 3 c_p >  0.

С учётом пропусков в данных значение устойчивости (см. (4)) будет выглядеть так

U( \-1 V / f(i)(v-u +1)1 f(i)>0"5,C    ^ Ги , Г, ]'}l(1 - ft(i))(V - U + 1)1 ft(i )< 0-5,

где ^ - Tp + T 3 C _p .

Примером формирования латентного признака из двух исходных, один из которых измеряется в количественной, а другой в номинальной шкале, может быть следующий. Пусть x,,x j e X ( n ), , e J , j e I и признак x_; имеет 2 градации. Тогда для получения латентного признака в виде произведения x_ix_j значения признака x_i нужно выбирать из {-1,1}.

Разбиения на интервалы по (2) и (5) дают возможность для наглядного представления знаний в виде дизъюнкций элементарных конъюнкций. Элементарные конъюнкции нужны для проверки принадлежности значения признака к одному из интервалов. Запись правила для отнесения объекта классу K_t , t =1,2 может иметь вид: а 1 ^ x_; ^ b 1 or a 2 ^ x_; ^ b 2 or ^.or a _{n -1} ^ x_; ^ b _{n -1}, где a j ,b,, j e {1, n } — границы интервалов, n — число непересекающихся интервалов.

Значения устойчивости по (4) или (6) служат индикатором для использования разбиения на

интервалы в качестве нового знания. Рекомендуется считать результаты анализа новым знанием при значении устойчивости из [0.9;1] и числе интервалов не больше 4.

2. ВЫЧИСЛИТЕЛЬНЫЙ ЭКСПЕРИМЕНТ

Для вычислительного эксперимента с целью поиска скрытых закономерностей были использованы данные Statlog [5] из UCI Machine Learning Repository. В Statlog содержатся данные сегментации изображений, которые разделены на семь классов (кирпич, небо, листва, цемент, окно, дорога, трава). Экземпляры (объекты) были случайно отобраны из базы данных открытых изображений. Каждый экземпляр представляет собой область из пикселей размера 3x3, количество экземпляров 2310. Для описания объектов выборки использовались 19 количественных признаков. Часть признаков получена по значениям интенсивности цветов от RGB генератора.

При проведении эксперимента выбирался один класс объектов изображений «кирпич» ( K ₁), все остальные объекты считались принадлежащими классу K ₂. Результаты разбиения на интервалы по (2) и устойчивости по (4) приведены в табл. 1.

По результатам из табл. 1 устойчивость по (4) больше 0.9 у признаков 13, 18, 19. Согласно рекомендациям из п.1, именно эти признаки и границы их интервалов целесообразно использовать в качестве нового знания об объектах класса K ₁ «кирпич», например, при формировании if …then правил в базах знаний. Полученное значение U (3)=0 объясняется тем, что не существует интервалов (для признака region-pixel-count) в которых по (2) доминируют представители одного из двух классов.

Очевидно, что рекомендации из п. 1 не могут быть ограничены исходными признаками в описании объектов классов. Дополнительные возможности для поиска скрытых закономерностей появляются при использовании в качестве исходных данных значений латентных признаков, синтезированных из исходных по правилам иерархической агломеративной группировки [3].

ЗАКЛЮЧЕНИЕ

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

Таблица 1. Результаты разбиения на интервалы при выборе в качестве класса K ₁ изображения «кирпич»

№	Название признака	Границы Интервалов	Значение функции (2) принадлежности к K t	Устойчивость разбиения по (4)
1	region-centroid-col (столбец центрального пикселя области)	[1,151]	0.5987	0.6557
		[152, 254]	0.2539
2	region-centroid-row (строка центрального пикселя области)	[11,50]	0.1533	0.7889
		[51, 149]	0.6607
		[150, 251]	0
3	region-pixel-count (количество пикселей в области = 9)	Нет	0	0
4	short-line-density-5 (результаты алгоритма экстракции линии, контраст, меньше или равный 5)	[0,0]	0.4863	0.5222
		[0.1111,0.3333]	0.5856
5	short-line-density-2 (результаты алгоритма экстракции линии, контраст больше 5)	[0,0]	0.5089	0.5214
		[0.1111,0.2222]	0.1714
6	vedge-mean (измерение контраста по горизонтали используется как детектор вертикального края)	[0,0.2777]	0.1923	0.6116
		[0.2778, 0.6111]	0.750769
		[0.6111,29.2222]	0.4305
7	vegde-sd (см. 6)	[0, 0.0333]	0.2857	0.6181
		[0.0333, 0.4333]	0.6797
		[0.4333,991.718]	0.4102
8	hedge-mean (измеряется контраст вертикально смежных пикселей, используется для определения горизонтальной линии)	[0, 0.3333]	0.1046	0.6259
		[0.3333, 2.9444]	0.5662
		[3, 44.7222]	0.2434
9	hdge-sd (см. 8)	[-1.5e-008, 0.0296]	0	0.5981
		[0.0296, 0.4444]	0.6661
		[0.4554, 1386.33]	0.4406
10	intensity-mean (среднее значение интенсивности: среднее по области (R + G + B)/ 3)	[0, 3.8889]	0.0179	0.8860
		[3.9259, 28.6296]	0.7443
		[28.7407, 143.444]	0
11	rawred-mean (среднее значение по области значения R)	[0,5.3333]	0.0956	0.8903
		[5.4444, 26.1111]	0.7685
		[26.3333, 137.111]	0
12	rawblue-mean (среднее значение по области значения B)	[0, 4.6667]	0.0453	0.8525
		[4.7778, 36.2222]	0.7207
		[36.3333, 150.889]	0.0298
13	rawgreen-mean (среднее значение по области значения G)	[0, 1.6667]	0	0.9103
		[1.7778, 20.6667]	0.7794
		[20.7778, 142.556]	0.0104

Таблица 1. Результаты разбиения на интервалы при выборе в качестве класса K1 изображения «кирпич» (окончание)

14	exred-mean (избыток красного: (2R - (G + В)))	[-49.6667, -5.6667]	0.0790	0.8952
		[-5.5556, 7.2222]	0.8327
		[9.8889,9.8889]	0
15	exblue-mean (избыток синего: (2В -(G + R)))	[-12.4444, 0.5556]	0.0316	0.8365
		[0.6667,23]	0.7494
		[23.1111,82]	0.1342
16	exgreen-mean (избыток зеленого: (2G-(R + B)))	[-33.8889, -19.8889]	0.0933	0.8148
		[-19.7778, -6.3333]	0.6918
		[-6.2222, 24.6667]	0.0441
17	value-mean (среднее значение: трехмерное нелинейное преобразования RGB)	[0,5.3333]	0	0.8588
		[5.4444, 3 6.2222]	0.7230
		[36.3333, 150.889]	0.0298
18	saturatoin-mean (среднее значение насыщенности нелинейного преобразования RGB)	[0, 0.3679]	0.0052	0.9034
		[0.3688,0.6170]	0.8057
		[0.6176, 1]	0.1699
19	hue-mean (среднее значение оттенка нелинейного преобразования RGB)	[-3.0442, -1.8905]	0.0190	0.9825
		[-1.8884, -0.5709]	0.9716
		[-0.0049,2.9125]	0

SUSTAINABILITY OF DIVIDING DATA IN INTERVALS IN THE PROBLEMS OF RECOGNITION AND SEARCHING FOR HIDDEN LAWS

скрытых закономерностей в данных. Обнаруженные закономерности являются источником нового знания в предметных областях.