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

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

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

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

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

Переход в спрямляющее пространство объясняется с позиций обобщающей способности алгоритмов распознавания. Теоретически такой подход приемлем, так как повышает меру статистического разнообразия (емкость) класса линейных решающих функций. Доказательство этого факта можно найти в работе В.Н. Вапни-ка [1]. Утверждается, что выборку из m объектов в пространстве из n признаков при n ≥m всегда можно с помощью ЛДФ разделить на два класса 2 ^m способами. В реальных прикладных задачах отношения между объектами выборок данных определяется скрытыми закономерностями и нет смысла рассматривать все возможные варианты разбиения на классы.

Обучение ЛДФ сводится к вычислению вектора весовых коэффициентов. Среди вычислительных методов безусловным лидером является линейный дискриминант Фишера. Лидерские качества демонстрируются в виде высоких относительно других методов показателях обобщающей способности к распознаванию.

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

Исследователи искали ответ на вопрос: с помощью каких нелинейных преобразований строить спрямляющее пространство? В методе SVM[2] такой выбор был сделан на использование ядерных функций. Несмотря на наличие теоретического обоснование метода никаких рекомендаций по выбору ядерных функций не разработано.

В [2] предлагалось решение проблемы линейной разделимости с помощью матриц попарного сходства объектов. Использование этих матриц рассматривалось в качестве одной разновидностей без признакового распознавания. Принцип без признакового распознавания распространяется на такие известные методы как ближайший сосед, к ближайших соседей, базовым свойством которых является локальная компактность по мере близости.

Проблемы поиска информативных признаков как в исходном, так и в расширенном (спрямляющем) пространстве оставалось открытой. Целью отбора была адаптация к той структуре признакового пространства, для которой существует линейная разделимость объектов классов.

Логические закономерности в форме полуплоскостей применяются в интеллектуальном анализе данных. Целью анализа является поиск скрытых закономерностей (новых знаний) из баз (хранилищ) данных.Результаты анализа востребованы при принятии решений в трудно формализуемых задачах.

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

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

ПОСТАНОВКА ЗАДАЧИ

Рассматривается двухклассовая задача распознавания в стандартной постановке. Каждый из объектов выборки E ₀ ={ S 1 ,...,S m } принадлежат одному из классов К 1 или К 2 ( E ₀ = К 1 U К 2 ) и описываются с помощью n количественных признаков X ( n ) = ( x 1 ,..., x_n ). Для распознавания объектов на E ₀ используется обобщенные линейные решающие функции вида d ( S )= w₁y₁+.+w_ry_r , где y c = f c ( S ), f ( S ) е { x a x^ ... x t } , a_y е { 0,1 } , j=1, ..., t, t>1.

Считается, что для оценки выбора информативного набора признаков Y ( p )=( y 1 , ..., y p ) используется функционал F ( E 0 , Y ( p )). Требуется определить:

• -    критерии для оценки закономерностей в форме полуплоскостей;

• -    информативный набор признаков

2. КРИТЕРИИ ДЛЯ ОЦЕНКИ ЗАКОНОМЕРНОСТЕЙ В ФОРМЕ ПОЛУПЛОСКОСТЕЙ

Y (P) = arg max F (E0, Y(P)), Л(8)еП‘ где Qt - множество обобщенных функций степени не выше t.

Закономерности в форме полуплоскостей представляют предикат вида

P (x)

n

£ wx ^{- w} 0

£ { 0,1 } .

Геометрическим

ме-

стом точек, равноудаленным от двух эталонов из разных классов, является гиперплоскость, значения весовых коэффициентов которой вычисляются через координаты эталонов [4]. В качестве таких эталонов в данной работе предлагается рассматривать векторы математических ожиданий M 1 , M 2 значений признаков объектов по каждому из классов К₁ и К₂ .

Пусть m 1 е M 1 , m 2 е M ₂ - математическое ожидание (среднее-арифметическое) значений признака y_r е Q ‘ соответственно в классах К 1 и К₂ . Внутриклассовое сходство и межклассовое различие признака y r е Q ‘ по объектам S i е E ₀ ( S i =( y_u,.,y_ip )), p>1 вычислим соответственно как

2                          2                 2                            2

0r = £ £ (yr-mi) и уr = £ £ (yr-mVj) ■ j=1 S, eKi                                  j=1 Si eKi ij                ij

Для оценки веса (разделяющей способности) w_r признака y r е Q ‘ по значениям 9 _r , y _r предлагается использовать функционал из [5]

£ w ^ i

J ( w ) = -- > min.                (1)

£ wYi

При ограничении на веса в (1) £ w = 1 , w>0 функция Лагранжа для решения задачи условной оптимизации имела вид

. . ² «-- б -     / х

L ( « ) = х      + ^ | 2 « - ¹ I ’

2 wy .    I -       )

а значения весов вычислялись как w

Y , - ⁹ , 2 ⁽ Y j ^- j

Согласно доказанной в [5] теоремы, необходимым и достаточным условием выбора признака yj e Y (p) кандидатом на удаление из набора Y())=(ур™,У)) при ограничении E« = 1, 9,            „                   ‘ w. > 0 является — = max . Соотношение

^-                         у . У ^ y ( p )

жение в левых скобках (5) представляет внутриклассовое сходство, в правых – межклассовое различие.

Значение w_r = w ( y_r ) рассматривается как вес признака y r e Y ( p ) , а границы интервалов могут используются для нормирования значений признака объекта S_i =( y_i1,…,y_ip ) по формуле y ^- c i y r                .

c 3 ^- c i

3. ОТБОР ИНФОРМАТИВНЫХ НАБОРОВ ПРИЗНАКОВ

9 j

дает возможность оценивать и упорядочивать

признаки по плотности их распределения вокруг математических ожиданий классов. Чем выше плотность, тем меньше значение (2).

Также как и в (2) вычисление внутриклассо-

вого сходства по отдельному признаку исполь-

зуется в критерии Фишера [3] | m1 - m 2|2

, s, + s 2

в котором сумма внутриклассового разброса s + s ₂ = 9 r , а m 1 -m₂ естьразность математических ожиданий классов K₁ и K₂ на числовой оси.

Отличный от (2) и (3) критерий рассчитан на анализ порядка расположения объектов классов на числовой оси [6]. Пусть

S , S ,..., S (4) r ₁ r ₂ r_m

Задача поиска информативных наборов признаков для линейной разделимости объектов классов K₁ и K₂ является NP полной. Из этого следует вывод, что кроме полного перебора других способов решить задачу поиска глобального экстремума функционала F ( E₀ ,Y ( p )) не существует. Используя некоторые эвристики, можно получить локальный экстремум функционала.

Смысл использования эвристик для решения проблемы линейной разделимости сводится к следующему. Пусть Ω^t – множество обобщенных функций степени не выше t . На множестве пар ( y , , y j ) c Y ( p ) рассматривается сокращенный перебор с целью поиска экстремума по критерию Фишера

Ф ( w ) = * m l m 2! ^ max. (6)

*s i + S 2

последовательность объектов, упорядоченная по невозрастанию значений признака y r e Y ( p ) . Упорядоченное множество значений (4) разделяется на два непересекающихся интервала [ c₁,c₂ ], ( c₂,c₃ ], каждый из которых рассматривается как градация номинального признака. Критерий для определения границы c₂ основывается на проверке гипотезы (утверждения) о том, что каждый из двух интервалов содержит значения количественного признака объектов только одного класса.

Пусть u ¹, u ² – количество значений (4) некоторого количественного признака y e Y ( p ) класса K_i , i =1,2 соответственно в интервалах [ c 1 ,c₂ ], ( c₂,c₃ ], K, | >  1 , v - порядковый номер элемента упорядоченной по возрастанию последовательности (4) из E₀ определяющий границы интервалов как c 1 = S r , c ₂ = S r , c 3 = S m . Критерий

Критерий (6) отличается от (3) тем, что для линейной проекции описаний объектов на числовую ось необходимо вычислять значения вектора весов w .Приемлемым считается результат, при котором точность распознавания на обучении по ( y , , y j ) c Y ( p ) не ниже чем на исходном наборе X ( n ).

Для вычисления коэффициентов дискриминантной функции d(y)=w₁y_i+w₂y_j+w₀ по паре ( y , , y j ) c Y ( p ) сформируем матрицу ковариаций Z =| ^{Z 11 Z} 1 ² I и вектор-столбец разностей

V z 21 z 22 7

[ m¹ - m ² 1              1 1 _{2 2}

, где ^{m , m} j ^{, m , m} j математические m j - m 22 7

ожидания по признакам y_i , y_j соответственно в классе K₁ и K₂ . Решение системы линейных алгебраических уравнений

^{w (} y ) =

EEU (U -1)

d = 1 - = 1 ___________________

El K-I(l Kl-1)

V , = 1                      7

[ EE и (i K 37- u l d = 1 ' - '

²I К J K ₂|

V

1          2

^W 1 z 11 ^{+ W} 2 ^Z 12 = mi ^- mi

1         2

« 1 z 21 + w 2 z 22 = mj - mj

^ max c! < c 2 < c3

позволяет вычислять оптимальное значение границы между интервалами [ c₁,c₂ ], ( c₂,c₃ ]. Выра-

дает искомые значения весов w₁ , w₂ дискриминантной функции.

Выбор коэффициентов линейного дискриминанта Фишера по (7) связан с предположением, что выборка данных распределена по

нормальному закону. Исходя из этого предположения выбор порога дискриминантный функции d ( y ) производится как

^W 0 = ^{- (} w ⁽ m i I K 1 1 + m i I K ₂1) + w 2 ⁽ m ' I K 1 1 + m² K 2 1)) / m . (8)

Способ выбора порога без всяких предположений о природе среды впервые был предложен в [7]. Значение порога вычислялось по границе c2 интервалов [c1,c2], (c2,c3] по (5) как c 2 + u (S) w = —2—’

где u ( S )= wy + wy , , S =( у₁,™,У р ), u ( S e ( c 2 , c 3 ] - бли-жайщий к c₂ объект E₀ на числовой оси.

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

Для вычислительного эксперимента были взяты 4 выборки данных из [6, 8, 9], содержащих представителей двух непересекающихся классов. Для описания объектов использовались признаки, измеренные в интервальных шкалах. Параметры выборок представлены в табл. 1.

Вычислительный эксперимент проводился на объектах выборок с описанием как в исходном так и в спрямляющем пространстве. Спрямляющее пространство было представлено обобщенными функциями степени не выше 2. Сравнительный анализ данных на выборке Chelust по критериям (2),(3),(5) представлен в табл. 2.

Нетрудно заметить, что между значениями критериев (см. табл. 2) нет линейной или квазилинейной зависимости. Многообразие отношений на множестве значений свидетельствует как о сложности структуры данных так сложности принятия решения по ним.

Значения 0,8001 по критерию (5)на признаках x₄ x₅ , x₅ x₆ и x₆ указывает на то, что порядок

Таблица 1. Параметры выборок данных

№	Выборка данных	Количество
		Объектов	признаков
1	Australian	690	14
2	Chelust	42	6
3	Gipertaniya	147	29
4	Seeds	140	7

Таблица 2. Сравнительный анализ данных Chelust по критериям (2), (3), (5)

Признаки (обобщенные функции) Значения по критериям (3) (5) (2) x1 0,0074 0,3781 0,7617 x1x2 0,0106 0,3781 0,6910 x1x3 0,0090 0,3620 0,7258 x1x4 0,0679 0,5757 0,2596 x1x5 0,0341 0,4196 0,4113 x1x6 0,0398 0,4355 0,3740 x2 0,0134 0,3892 0,6391 x2x3 0,0158 0,3892 0,6014 x2x4 0,0811 0,6241 0,2270 x2x5 0,0439 0,4905 0,3517 x2x6 0,0499 0,4683 0,3230 x3 0,0048 0,2884 0,8320 x3x4 0,0806 0,5312 0,2281 x3x5 0,0412 0,5180 0,3664 x3x6 0,0457 0,4743 0,3424 x4 0,2669 0,8965 0,0819 x4x5 0,2278 0,9107 0,0946 x4x6 0,1797 0,8001 0,1170 x5 0,1108 0,6254 0,1769 x5x6 0,1108 0,8001 0,1769 x6 0,0787 0,8001 0,2322 расположения объектов одного класса относительно другого не изменился. Изменения есть у показателей плотности распределения объектов относительно математических ожиданий (центров) классов, вычисляемых по критериям(2) и (3).

Из максимального значения 0,9107 по критерию (5) следует вывод, что свойство линейной разделимости среди всех признаков из табл. 2 наиболее выражено у x₄ x₅ . Несмотря на менее выраженное свойство линейной разделимости, показатель плотности распределения (среднеквадратичное отклонение от математических ожиданий классов) у x₄ по (2) выше чем у x₄ x₅ . Относительно малое значение отклонения (0,0819 относительно 0,0946) указывает на более высокую плотность распределения.

Влияние выбора порога дискриминантной функции w₀ с предположением о нормальности распределения выборки по критерию Фишера [3] и по критерию (5) по аналогии соответственно с (8) и (9) на исходных наборах признаков приводится в табл. 3.

Значение критерия (5), равное 1,0, по определению означает, что представители классов на числовой осине пересекаются между собой. Корректное (без ошибок) распознавание объ- ектов на выборках Chelust и Seeds служат подтверждением этому определению.

Эффект от выбора значения порога по (8) или (9) в спрямляющем пространстве на данных Chelust демонстрируется в табл. 4 и рис. 1.

На рис. 1.a и 1.b показана последовательность расположения объектов классов по первой и второй паре признаков из табл. 4. В границах интервалов [ c₁ ,c₂ ], ( c₂ ,c₃ ] по (5) содержатся представители соответственно классов K₂ и K₁ . При пороге, вычисленном по (8) (на рис. 1 указан жирной чертой), число ошибок равно соответственно 2 и 4.

Сравнивая результаты по данным Chelust из табл. 3 и табл. 4 отметим, что корректное распознавание в спрямляющем пространстве достигнуто за счет использования обобщенных функций не выше 2 степени. Для вычисления этих функций будет достаточно задать значения исходных признаков x₁ , x₄ , x₅ или x₂ , x₄ , x₅ , x₆ .

ЗАКЛЮЧЕНИЕ

В работе рассмотрена проблема выбора решений в трудно формализуемых задачах путем анализа закономерностей в форме полуплоско-

Таблица 3. Точность распознавания в исходном пространстве признаков

№	Выборка данных	Значение критерия		Число ошибок при выборе порога по критерию
		(3)	(5)	(6)	(5)
1	Australian	0,0088	0,6176	96	84
2	Chelust	0,5446	1,0000	3	0
3	Gipertaniya	0,2180	0,672	8	1
4	Seeds	0,1616	1,0000	2	0

Таблица 4. Точность распознавания в спрямляющем пространстве

№	Комбинации из пар признаков	Значение критерия		Число ошибок при выборе порога по критерию
		(3)	(5)	(8)	(9)
1	x 1 x 5 , x 4 x 5	0,5426	1,0	2	0
2	x 2 x 6 , x 4 x 5	0,2870	1,0	4	0

X	Ж	XX	X	X	X X	X	О	о	|> о ш	О® (ПО ООО ОО О	о аю
-4.7						-1.45			0		2.3

a )

Ж	X	X	X X	X X X	о ар | о о оо ер ® оаро ар	О ООО®
-4.58				1 -1.31	0	'"2.48

b)

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