1 Обнаружение логических закономерностей в данных Saint Petersburg State University of Aerospace Instrumentation Logo/Photo of your research organization Key words: System analyse Vladimir Perliouk,

Young Scientist Day, St. Petersburg April 29-30, 2003 Постановка задачи Посмотрим на рисунок. На нем схематично изображены лица людей. Эти лица по каким- то причинам разделены на два класса. Ставится задача найти закономерности проведенного разделения. Попробуйте визуально определить, чем лица разных классов отличаются друг от друга и что объединяет лица одного класса. И, хотя решение существует, человеческий разум не в состоянии решить даже такую, на первый взгляд простую задачу обнаружения скрытых закономерностей. Здесь необходимо применение компьютерных методов анализа данных

Young Scientist Day, St. Petersburg April 29-30, 2003 Формализация задачи Выделим признаки, характеризующие изображение лица X1 (голова)- круглая -1, овальная -0 X2 (уши) – оттопыренные -1, прижатые -0 X3 (нос) – круглый -1, длинный – 0 X4 (глаза) – круглые -1, узкие -0 X5 (лоб) – c морщинами -1, без морщин – 0 X6 (носогубная складка) – есть-1, нет -0 X7 (губы) – толстые -1, тонкие -0 X8 (волосы) – есть -1,нет -0 X9 (усы) – есть -1, нет – 0 X10 (борода) –есть -1, нет -0 X11 (очки) –есть -1, нет -0 X12 (родинка на щеке) – есть -1, нет – 0 X13 (бабочка) – есть -1, нет – 0 X14 (брови) – подняты кверху -1, опущены книзу -0 X15 (серьга) – есть -1, нет- 0 X16 (курительная трубка) есть – 1, нет - 0

Young Scientist Day, St. Petersburg April 29-30, 2003 Исходная матрица данных Nп/пNп/п x1x2x3x4x5x6x7x8x9x10x11x12x13x14x15x16class

Young Scientist Day, St. Petersburg April 29-30, 2003 Дискриминантный анализ В этом случае объекты в соответствии с внешним критерием разбиваются на группы (классы) и пространство признаков рассматривается под углом зрения способности разделять (дискриминировать) выделенные классы. Большая группа этих методов основана на байесовском подходе, базирующимся на предположении, что задача сформулирована в терминах теории вероятностей и известны все представляющие интерес величины: Априорные вероятности P(wi) для всех классов wi (i=1,K) Условные плотности распределения значений вектора признаков P(x,wi) По правилу Байеса находится апостериорная вероятность P(wi/x)

Young Scientist Day, St. Petersburg April 29-30, 2003 Решение о принадлежности объекта xk к классу wj принимается при выполнении условия, обеспечивающего минимум средней вероятности ошибки классификации Для бинарных признаков, принимающих значения 0 или 1 P-мерный вектор признаков х может принимать одно из 2^n дискретных значений v1,…vn. Функция P(x/wi) становится сингулярной и заменяется на P(vk/wi)- условную вероятность того, что x=vk при условии класса wi. Использование принципа Байеса

Young Scientist Day, St. Petersburg April 29-30, 2003 Геометрические представления о разделении классов в пространстве признаков Совокупность объектов, относящихся к одному классу, образует «облако» в p-мерном пространстве, задаваемом исходными признаками. Для успешной классификации необходимо: 1.«Облако» из wi в основном должно быть сконцентрировано в некоторой области Di пространства признаков 2. В область Di должна попадать только незначительная часть «облаков» из других классов Построение решающего правила рассматривают как задачу поиска К непересекающихся областей Di(i=1,K), удовлетворяющим условиям 1 и 2. Дискриминантные функции (ДФ) определяют эти области посредством описания их границ в пространстве признаков.

Young Scientist Day, St. Petersburg April 29-30, 2003 Критерий средней вероятности ошибочной классификации Если какой- либо объект попадает в область Di, то будем считать, что принимается решение о его принадлежности к классу wi. Обозначим P(wi/wj) – вероятность того, что объект из класса wj ошибочно попадает в область D. Тогда критерием правильного определения областей Di будет Где P(wi) – априорная вероятность появления объекта из wi Минимум этого критерия достигается, в частности, при использовании рассмотренного выше байесовского подхода, который реализуется однако лишь при невысоких размерностях пространства признаков

Young Scientist Day, St. Petersburg April 29-30, 2003 Процедуры построения линейных дискриминантных функций Для случая двух классов w1 и w2 методы ЛДФ опираются на два предположения Области D1 и D2, в которых концентрируются объекты из двух классов могут быть разделены p-1 мерной гиперплоскостью Разделение областей D1 и D2 будет тем лучше, чем дальше отстоят друг от друга средние значения случайных величин Где Е{?} – оператор усреднения В простейшем случае классы w1 иw2 имеют одинаковые ковариационные матрицы S1=S2=S тогда вектор оптимальных весовых коэффициентов

Young Scientist Day, St. Petersburg April 29-30, 2003 Результат дискриминантного анализа в пространстве признаков x1…x16 дискриминантная функция, обеспечивающая 100 % правильной классификации исследуемых объектов: F = -40,1 - 11,0 х ,7 х 2 + 6,8 х 4 - 7,0 х 5 - 6,3 х ,2 х ,0 x8 - 6,4 х ,3 х ,1 х 13. Гистограмма распределения значений дискриминантной функции

Young Scientist Day, St. Petersburg April 29-30, 2003 Ограничения дискриминантного анализа Построенное правило классификации формально и не дает нового знания. Оно может лишь перечислить признаки, вошедшие в дискриминантную функцию, и сказать, что данные признаки необходимы для разделения двух классов объектов. Попытка дать интерпретацию весовым коэффициентам в дискриминантной функции вообще приводит к нелепым результатам. Непонятно, например, почему вес ушей (признак х 2) более чем в три раза превышает вес носа (признак х 3), и т. д. Отсюда возникает недоверие к построенной дискриминантной функции и растет подозрение, что используемый математический аппарат многомерного анализа «подгоняет» результат. Так, собственно говоря, и есть. Классическая теория многомерного анализа, являющаяся разделом математической статистики, никогда не претендовала на решение задач, подобных рассмотренной. Но именно такие и гораздо более сложные задачи часто ставит перед нами жизнь.

Young Scientist Day, St. Petersburg April 29-30, 2003 Логические правила Правила, выражающие найденные закономерности, должны формулироваться на простом и понятном человеку языке логических высказываний. Например, ЕСЛИ {(событие 1) и (событие 2) и... и (событие N)} ТО... Иными словами, это должны быть логические правила. Так, классификация лиц в рассмотренном примере может быть произведена с помощью четырех логических правил: 1. ЕСЛИ {(голова овальная) и (есть носогубная складка) и (есть очки) и (есть трубка)} ТО (Класс 1). 1. ЕСЛИ {(глаза круглые) и (лоб без морщин) и (есть борода) и (есть серьга)} ТО (Класс 1). 1. ЕСЛИ {(нос круглый) и (лысый) и (есть усы) и (брови приподняты кверху)} ТО (Класс 2). 1. ЕСЛИ {(оттопыренные уши) и (толстые губы) и (нет родинки на щеке) и (есть бабочка)} ТО (Класс 2).

Young Scientist Day, St. Petersburg April 29-30, 2003 Традиционные методы обнаружения логических закономерностей Методы поиска логических закономерностей в данных апеллируют к информации, заключенной не только в отдельных признаках, но и в сочетаниях значений признаков. Это одна из причин, по которой классические методы многомерного анализа в ряде случаев, аналогичных рассмотренному выше, не могут конкурировать с логическими методами. В методах поиска логических закономерностей значения какого- либо признака Xi рассматриваются как элементарные события T. Например, для признаков, измеренных в номинальных шкалах, элементарными событиями называют события Xi=a или Xi#a, где a – одно из возможных значений Xi. Если же шкала порядковая или количественная, то элементарными событиями могут служить события вида a a.

Young Scientist Day, St. Petersburg April 29-30, 2003 Алгоритм Кора Алгоритм был предложен в книге М.М.Бонгард Проблема узнавания.- М.: Наука, 1967 В нем анализируются все возможные конъюнкции вида Ti 1 ^Ti 2 ^…^Ti l (l<l 0 ), Где Т-элементарные события, а l 0 –некоторое наперед заданное число (первоначально предлагалось равное трем)

Young Scientist Day, St. Petersburg April 29-30, 2003 Алгоритм Кора Среди конъюнкций выделяются те, которые характерны (верны на обучающей выборке чаще, чем некоторый порог 1-e 1 ) для одного из классов и не характерны для другого (верны реже, чем в доле случаев е 2 ). Если коэффициент корреляции между какими- либо двумя выделенными конъюнкциями по модулю более 1-е 3, то оставляется наилучшая из них с точки зрения различения классов, а если конъюнкции эквивалентны, то более короткая (имеющая меньшее l) или просто отобранная ранее.

Young Scientist Day, St. Petersburg April 29-30, 2003 Алгоритм Кора Параметры e 1,e 2 и e 3 подбираются так, чтобы общее число отобранных (информативных) конъюнкций не превосходило некоторого числа n. Чтобы классифицировать новое наблюдение x, для него подсчитывается n i - число характерных для i-го класса отобранных конъюнкций, которые верны в точке x. Если n i является максимальным из всех, то принимается решение о принадлежности объекта i- му классу. При распознавании лиц людей lo=4 и e1>0,5 Алгоритм хорошо работает только при сравнительно небольших размерностях пространства признаков и невысоких значениях lo.

Young Scientist Day, St. Petersburg April 29-30, 2003 Деревья решений (decision trees) Этот метод является самым распространенным в настоящее время подходом к выявлению и изображению логических закономерностей в данных. Видные представители этого подхода: CHAID (chi square automatic interaction detection) CART ( classification and regression trees) ID3 (Intrtactive Dichotomizer – интерактивный дихотомайзер)

Young Scientist Day, St. Petersburg April 29-30, 2003 ID3 с алгоритмом CLS См. Экспертные системы. Принципы работы и примеры. Под ред. Р.Форсайта.- М.: Радио и связь, Этот алгоритм циклически разбивает обучающие примеры на классы в соответствии с переменной, имеющей наибошльшую классифицирующую силу. Каждое подмножество примеров (объектов), выделяемое такой переменной, вновь разбивается на классы с использованием следующей переменной с наибольшей классифицирующей способностю и т.д.

Young Scientist Day, St. Petersburg April 29-30, 2003 ID3 с алгоритмом CLS Разбиение заканчивается, когда в подмножестве оказываются объекты лишь одного класса. В ходе процесса образуется дерево решений. Пути движения по этому дереву с верхнего уровня на самые нижние определяют логические правила в виде цепочек конъюнкций.

Young Scientist Day, St. Petersburg April 29-30, 2003 Первый шаг алгоритма Определяем признак с наибольшей дискриминирующей силой При- знаки x1x2x3x4x5x6x7X8 Класс 1/ Класс 2 3/34/6 5/53/36/44/63/3 Приз- наки X9x10x11x12x13x14x15X16 Класс 1/ Класс 2 5/56/4 3/35/54/6 5/5 В нашем случае одинаковой и максимальной силой обладают сразу 7 признаков –x2,x3,x6,x7,x10,x11,x14,x15. Сами назначим например первым признаком x6. От этого признака отходят две ветки (x6=0 и x6=1)

Young Scientist Day, St. Petersburg April 29-30, 2003 Таблица данных, соответствующая ветви x6=0 Nп/пNп/п x1x2x3x4x5x7x8x9x10x11x12x13x14x15x16class C1/ C2 2/21/3 2/30/21/41/21/32/01/31/11/2 2/31/3

Young Scientist Day, St. Petersburg April 29-30, 2003 Таблица данных, соответствующая ветви x10=1 Nп/пNп/п x1x2x3x4x5x7x8x9x11x12x13x14x15x16class C1/ C2 2/21/3 2/30/21/41/21/3 1/11/2 2/31/3 Таблица данных, соответствующая ветви x10=0 Nп/пNп/п x1x2x3x4x5x7x8x9x11x12x13x14x15x16class C1/ C2 2/21/3 2/30/21/41/21/3 1/11/2 2/31/3

Young Scientist Day, St. Petersburg April 29-30, 2003 Таблица данных, соответствующая ветви x6=1 Nп/пNп/п x1x2x3x4x5x7x8x9x10x11x12x13x14x15x16class C1/ C2 1/13/3 3/23/13/22/14/24/45/12/24/33/44/14/2

Young Scientist Day, St. Petersburg April 29-30, 2003 Таблица данных, соответствующая ветви x11=0 Nп/пNп/п x1x2x3x4x5x7x8x9x10x12x13x14x15x16class C1/ C2 1/11/20/21/20/1 1/10/21/31/20/21/31/00/2 Таблица данных, соответствующая ветви x11=1 Nп/пNп/п x1x2x3x4x5x7x8x9x10x12x13x14x15x16class C1/ C2 0/02/13/12/03/03/11/04/03/11/04/12/13/14/0

Young Scientist Day, St. Petersburg April 29-30, 2003 Таблица данных, соответствующая ветви x15=0 Nп/пNп/п x1x2x3x4x5x7x8x9x10x12x13x14x16class Nп/пNп/п x1x2x3x4x5x7x8x9x10x12x13x14x16class Таблица данных, соответствующая ветви x15=1

Young Scientist Day, St. Petersburg April 29-30, 2003 Таблица данных, соответствующая ветви x16=0 Таблица данных, соответствующая ветви x16=1 Nп/пNп/п x1x2x3x4x5x7x8x9x10x12x13x14x15class C1/ C2 0/02/13/12/03/03/11/04/03/11/04/12/13/1 Nп/пNп/п x1x2x3x4x5x7x8x9x10x12x13x14x15class C1/ C2 0/00/11/11/00/01/10/01/01/10/01/10/11/1

Young Scientist Day, St. Petersburg April 29-30, 2003 Таблица данных, соответствующая ветви x2=0 Таблица данных, соответствующая ветви x2=1 Nп/пNп/п x1x3x4x5x7x8x9x10x12x13x14x15class C1/ C2 0/01/11/00/01/10/01/01/10/01/10/11/1 Nп/пNп/п x1x3x4x5x7x8x9x10x12x13x14x15class C1/ C2 0/01/11/00/01/10/01/01/10/01/10/11/1

Young Scientist Day, St. Petersburg April 29-30, 2003 Дерево логического вывода

Young Scientist Day, St. Petersburg April 29-30, 2003 Эталонные правила 1. ЕСЛИ {(голова овальная) и (есть носогубная складка) и (есть очки) и (есть трубка)} ТО (Класс 1). 2. ЕСЛИ {(глаза круглые) и (лоб без морщин) и (есть борода) и (есть серьга)} ТО (Класс 1). 3. ЕСЛИ {(нос круглый) и (лысый) и (есть усы) и (брови приподняты кверху)} ТО (Класс 2). 4. ЕСЛИ {(оттопыренные уши) и (толстые губы) и (нет родинки на щеке) и (есть бабочка)} ТО (Класс 2). Найденные правила 1. ЕСЛИ {((нет носогубной складки) и (есть борода) )} ТО (Класс 1). 2. ЕСЛИ {((нет носогубной складки) и (нет бороды) )} ТО (Класс 2). 3. ЕСЛИ {(есть носогубная складка) и (нет очков) и (нет серьги))} ТО (Класс 1). 4. ЕСЛИ {(есть носогубная складка) и (нет очков) и (есть серьга))} ТО (Класс 2). 5. ЕСЛИ {(есть носогубная складка) и (есть очки) и (есть трубка))} ТО (Класс 1). 6. ЕСЛИ {(есть носогубная складка) и (есть очки) и (нет трубки)и (оттопыренные уши))} ТО (Класс 1). 7. ЕСЛИ {(есть носогубная складка) и (есть очки) и (нет трубки)и (прижатые уши))} ТО (Класс 2).

Young Scientist Day, St. Petersburg April 29-30, 2003 Случайный поиск с адаптацией Этот алгоритм был предложен Г.С.Лобовым для работы в условиях зависимых признаков в 1965 году. Лобов Г.С. Выбор эффективной системы зависимых признаков// Тр. Сиб.отд. АН СССР. Он заключается в следующем: Имеется множество возможных событий Из этого множества требуется отобрать цепочки конъюнкций заданной длины l, максимизирующие некоторый критерий J

Young Scientist Day, St. Petersburg April 29-30, 2003 Случайный поиск с адаптацией Прежде всего проводится серия опытов по случайному определению состава цепочек конъюнкций. Затем для этих цепочек вычисляются значения критерия J. Цепочка с максимальным значением критерия поощряется увеличением вероятности выбора вошедших в нее событий в следующих опытах. Цепочка с наименьшей величиной критерия наказывается соответствующим образом. Вся процедура повторяется до тех пор, пока события отчетливо не поляризуются по вероятности их выбора для испытаний. Алгоритм СПА избегает полного перебора событий, требующего просмотра И их комбинаций по цепочке

Young Scientist Day, St. Petersburg April 29-30, 2003 Случайный поиск с адаптацией Его трудоемкость, однако, зависит от задаваемых условий: Количества испытаний, Мер поощрения и наказания событий, которые существенно влияют на скорость сходимости алгоритма. Экспериментально на одних и тех же данных показано, что алгоритм СПА давал оптимальное либо близкое к оптимальному решение за число шагов, сравнимое с величиной Пример с изображениями лиц может быть решен с помощью алгоритма СПА если задать l=4

Young Scientist Day, St. Petersburg April 29-30, 2003 Инструментальные средства обнаружения знаний в данных Построение деревьев решений с помощью системы See5/C5.0