Логические методы РО.Алгоритмические композиции

ЛЕКЦИЯ 1-УКАЗАНИЯ К ЛР-1. ЛОГИЧЕСКИЕ МЕТОДЫ РО. АЛГОРИТМИЧЕСКИЕ КОМПОЗИЦИИ ТИПЫ ВЫЯВЛЯЕМЫХ ЗАКОНОМЕРНОСТЕЙ. МЕТОДЫ DATA MINING Технологии data mining обеспечивают исследование эмпирических данных и выявление в них скрытых закономерностей различных видов. Ассоциация (идентификация). Если некоторый факт-1 является частью определенного события, то с расчетной вероятностью и другой факт-2, связанный с первым, будет частью того же события. Форма ассоциаций: если {условие}, то {результат}. Система WizWhy (WizSoft) (стоимость системы около $4000) Примеры: 1) мужчины, предпочитающие элитные сорта кофе в три раза чаще покупают импортные сигареты, чем мужчины, покупающие обычный кофе. 2) если взрослый покупатель берет чипсы, то существует 85-ти процентная вероятность, что он приобретет еще пиво; в торговле ассоциативный анализ часто называют анализом рыночной корзины; 3) если человек семейный, то с вероятностью 95 процентов он надежный клиент банка; 4) анализ истории продаж в розничном магазине ⇒ шаблоны покупок (стандартные наборы); 5) абонент, использующий услугу А, будет использовать услугу Б. 2 ТИПЫ ВЫЯВЛЯЕМЫХ ЗАКОНОМЕРНОСТЕЙ. МЕТОДЫ DATA MINING Последовательность (прогнозирование). Если свершилось некоторое событие-1, то с расчетной вероятностью через определенный период времени свершится другое событие-2, связанное с первым (цепочка связанных во времени событий). Примеры: 1) человек, купивший стиральную машину с вероятностью 0.7 купит сушилку для одежды в течение следующих шести месяцев; 2) после покупки дома в 45% случаев в течение месяца приобретается а) новая кухонная плита; б) 60% новоселов обзаводятся холодильником. 3) покупатель приобрел видеокамеру⇒ купит новые батарейки и пленку.... Кластеризация. Наиболее сходные по своим признакам объекты объединяются в группы (кластеры) таким образом, что в разных кластерах оказываются наиболее сильно отличающиеся друг от друга объекты. Кластеры объектов заранее не известны, а формируются в процессе кластеризации. Используют: - алгоритмы нейронных сетей; Предметно-ориентированные аналитические системы, $300 – $1000 - методы статистической обработки; - методы распознавания образов. Качество процесса кластеризации определяется схожестью объектов внутри класса и степенью отличия разных классов между собой; кластеризации и методы кластерного анализа не гарантируют достоверность разбиения на кластеры. Примеры: 1) определение производственного брака; 3 2) выявления групп услуг по кредитным карточкам (для разных групп клиентов). ТИПЫ ВЫЯВЛЯЕМЫХ ЗАКОНОМЕРНОСТЕЙ. МЕТОДЫ DATA MINING Прогнозирование. Прошлые фактические значения величин используются для прогнозирования будущих значений тех же или других величин на основании на основании знания зависимостей между ними, трендов и статистики. Регрессия – метод использует имеющиеся фактические значения величин для прогнозирования будущих на основании трендов и имеющейся статистики. Примеры: - прогноз объема продаж аксессуаров для спортивных машин по количеству проданных спортивных машин в прошлом месяце; - факторы (независимые переменные), влияющие на число абитуриентов (зависимая переменная), выбравших ВУЗ. - регрессия числа мигрантов в зависимости от 1) среднего уровня зарплат; 2) уровня инфраструктуры; 2) климатических свойств … - моделирование дорожных аварий как функции качества дорог, скорости, погоды и т.д. - регрессия количества потерь и убытков от пожаров как функции от а) числа пожарных станций; б) времени обработки вызова; в) географических особенностей местности.... Временные ряды - предсказывают значения переменных, зависящих от времени. Пример: прогноз количества ЧП во время каникул на основе аналогичных данных за 4 прошлый период. МЕТОДЫ DATA MINING. ЛОГИКА, ДИСКРЕТНАЯ МАТЕМАТИКА Деревья решений: последовательная иерархическая структура; каждый уровень дерева включает проверку (test, критерий расщепления узла) определённой независимой переменной. See5/C5.0 (Австралия), Clementine (Integral Solutions,Великобритания), SIPINA (University of Lyon, Франция), IDIS (Information Discovery, США), Knowledge SEEKER (ANGOSS, Канада). Стоимость: от $1000 до $10000. База данных. Задача прогнозирования Выдавать ли кредит? БД содержит ретроспективные данные клиентах банка: возраст, наличие недвижимости, образование, среднемесячный доход, вернул ли клиент вовремя кредит. МЕТОДЫ DATA MINING. РАСПОЗНАВАНИЕ ОБРАЗОВ Распознавание –отнесение конкретного объекта (реализации СП), представленного значениями его свойств (признаков), к одному из фиксированного перечня образов (классов) по определённому решающему правилу в соответствии с поставленной целью. Распознавание может осуществляться любой системой (живой или неживой): • измерение значений признаков, • вычисления, реализующие решающее правило. Перечень образов, информативных признаков и решающие правила либо задаются распознающей системе извне, либо формируются самой системой. Важная функция распознающих систем – оценка риска потерь⇒ • построение оптимальных решающих правил, • выбор наиболее информативной системы признаков. 2 ≤ S < ∞ – множество распознаваемых образов (классов), называемое иногда алфавитом; X – признаковое (выборочное) пространство; N – размерность признакового пространства (количество признаков, характеризующих распознаваемые объекты); D ( X ) – множество решающих правил, по которым осуществляется отнесение распознаваемого объекта (реализации) к тому или иному образу; R – риск потерь при распознавании. 6 МЕТОДЫ DATA MINING. РАСПОЗНАВАНИЕ ОБРАЗОВ Метод «ближайших соседей». Метод «k-ближайших соседей». Цель: предсказать значение зависимой переменной для некоторой записи из определенного массива, для которого известны значения как зависимой, так и независимой переменных. Идея. Объекты, которые находятся близко друг другу склонны иметь близкие значения предсказываемых величин: зная предсказываемое значение для одного из элементов, можно предсказать его и для ближайших соседей. Метод. Для этого в массиве записей БД (множестве объектов), выбирается запись (объект), наиболее «близкая» к распознаваемой; новая запись интерпретируется как искомая зависимая переменная. Проблема: чувствительность к выбросам (outliers) в обучающей выборке. Примеры систем на основе метода: КАТЕ tools (Acknosoft, Франция), Pattern Recognition.Workbench (Unica, США) 7 МЕТОДЫ DATA MINING. РАСПОЗНАВАНИЕ ОБРАЗОВ И ДР. Нейронные сети: структура, состоящая из узлов и связей между ними; «настройка» на «правильных ответах (подбор весов межнейронных связей, обеспечивающих наибольшую близость ответов сети к известным правильным ответам). Основной недостаток, сдерживающий использование нейронных сетей для извлечения знаний – их «непрозрачность». Построенная модель, как правило, не имеет четкой интерпретации (концепция «черного ящика»). Примеры нейросетевых систем – BrainMaker (CSS), NeuroShell (Ward Systems Group), OWL (HyperLogic). Стоимость $1500 – $8000. Нечеткая логика применяется для анализа таких наборов данных, когда невозможно причислить данные к какой-либо группе; возникает необходимость манипулировать категорией «может быть» в дополнении к «да» и «нет» Генетические алгоритмы. Недостатки: критерий отбора хромосом и используемые процедуры являются эвристическими и далеко не гарантируют нахождения «лучшего» решения; неприменимы к высокоразмерным задачам со сложными внутренними связями. Пример: GeneHunter (Ward Systems Group). Стоимость – около $1000. Эволюционное программирование. Идея: формирование гипотез о зависимости целевой переменной от других переменных в виде автоматически синтезируемых программ, выраженных на внутреннем языке программирования. Система создает некоторое число генетических линий программ, конкурирующих друг с другом по точности, статистической значимости и простоте выражения зависимости. PolyAnalyst, стоимость $10000. Визуализация (когнитивная графика). DataMiner 3D (Dimension5), стоимость до нескольких сот $ 8 ЗАДАЧА РАСПОЗНАВАНИЯ. ТИПЫ ПРИЗНАКОВ • Количественные (числовые) признаки − это признаки в определенной шкале, в шкалах интервалов и отношений • Качественные (ранговые, порядковые, в баллах) используются для выражения терминов и понятий, не имеющих цифровых значений (например, тяжесть состояния); измеряются в шкале порядка • Номинальные (например, профессия, группа крови, тип хозяйства, национальность, пол) − признаки, фиксированные в шкале наименований Описательный признак – признак, который может быть выражен только словесно. Прямой признак – свойство непосредственно присуще характерному объекту. Косвенный признак – свойства не самого характеризуемого объекта, а объекта связанного с ним либо входящих в него. Первичный признак – абсолютная величина, может быть измерен. Вторичный признак – результат сопоставления первичных признаков, не измеряется непосредственно. Безразмерный признак – измерение в долях, % Дискретный признак – принимает только целое значение, без промежуточного. Непрерывный признак –принимающий любые значения в определенном диапазоне. Факторный признак – признак, под действием которого изменяется другой признак. Результативный признак – признак, который изменяется под признаком другого Интервальный признак – сопоставлен определенному интервалу времени. ……………………………………. 9 ТЕХНИКА ПОСТРОЕНИЯ РЕШАЮЩИХ ПРАВИЛ Обучающая выборка –множество объектов, заданных значениями признаков и принадлежность которых к тому или иному классу достоверно известна «учителю» и сообщается учителем «обучаемой» системе. По обучающей выборке система строит решающие правила. Качество решающих правил оценивается по контрольной (экзаменационной) выборке, в которую входят объекты, заданные значениями признаков, и принадлежность которых тому или иному образу известна только учителю. ⇓ Оценка вероятностей ошибок распознавания Пример. Задача классификации «Выдавать ли ипотечный кредит клиенту». Обучающая выборка: база данных, содержащая информацию о клиентах. Признаки: Сумма кредита, Срок кредита, Цель кредитования, Возраст, Пол, Образование, Частная собственность, Квартира, Площадь квартиры. Основные элементы построения системы распознавания Значимость образов (классификации) результата 10 НЕКОТОРЫЕ ТИПЫ МЕТРИК Евклидово расстояние - геометрическое многомерном пространстве Rn. 1/2  2 d 2 ( x, y ) =  ∑ ( xi − yi )   i  i в Квадрат евклидова расстояния: придает прогрессивно возрастающий вес объектам, которые являются более удаленными. xi − yi Метрика Хемминга (покоординатное расстояние, городских кварталов,  2 d 2 ( x, y ) =  ∑ ( xi − yi )   i  d1 ( x, y ) = ∑ расстояние манхэттенское расстояние): усредняет разницу между различными компонентами векторов; эффект, привносимый большими компонентами демпфируется (не возводятся в квадрат). Расстояние Чебышева. Для определения двух объектов как d ∞ ( x, y ) = max xi − yi i различные, если они различны хотя бы по одному измерению. 1/ r  p d pr ( x= , y ) =  ∑ ( xi − yi )  Степенное расстояние. где r и p - определяемые пользователем  i  параметры: p контролирует вес разностей по отдельным компонентам, параметр r контролирует вес придаваемый расстоянию между объектами в целом. Если r=p=2, то это расстояние равно Евклидову расстоянию, при r=p – мера Минковского. Мера «доли рассогласования»; целесообразна для номинальных quantiy ( x ≠ y ) d ( x, y ) = признаков. n Обобщённая мера расстояний Минковского (при p=1 – метрика Хемминга, при p=2 – метрика Евклида, при p=∞ – метрика Чебышева). 11 Существуют и другие виды расстояний (Махаланобиса), ... 1/ p  p d p= ( x, y )  ∑ ( xi − yi )   i  МЕТОД ПОСТРОЕНИЯ ЭТАЛОНОВ КАК МЕТОД СОКРАЩЕНИЯ ВЫБОРКИ Эталон – это усреднённый по обучающей выборке абстрактный объект (может не совпадать не только ни с одним объектом обучающей выборки, но и ни с одним объектом генеральной совокупности) Для каждого класса по обучающей выборке строится эталон, имеющий значения признаков 1 K x = { x , x ,..., x } , x = ∑ xik , K k =1 1 2 N i K – количество объектов данного образа в обучающей выборке, i – номер признака. Процесс распознавания. На вход системы поступает объект x* , принадлежность которого к тому или иному образу системе неизвестна. От этого объекта измеряются расстояния до эталонов всех образов, и x* система относит к тому образу, расстояние до эталона которого минимально. Расстояние измеряется в той метрике, которая введена для решения определённой задачи распознавания. Решающее правило «Минимум расстояния до эталона класса». × × × × × × × × × × × × × x × × * × – эталон первого класса, – эталон второго класса × x* 12 НЕДОСТАТКИ КЛАССИЧЕСКИХ МЕТОДОВ ПОСТРОЕНИЯ ЭТАЛОНОВ ПРИМЕРЫ ЗАДАЧ КЛАССИФИКАЦИИ: • распознавание символов; • распознавание речи; • установление медицинского диагноза; ВАЖНО! Минимум ошибок при • прогноз погоды; распознавании ситуации. • распознавание лиц • классификация документов и др. Имеются объекты двух классов: «+» и «-». Классифицируемый объект «?» лежит ближе к классу «-». Но! Структура классов такова, что он является более типичным представителем класса «+» и должен быть отнесён именно в этот класс. FRiS-функция в большинстве подобных случаев работает корректно. Отличительная особенность FRiS-функции: количественная оценка ответа на вопрос «далеко-близко?», «похож-не похож?» «по сравнению с чем?». Хорошо работает в условиях разного внутриклассового расстояния. 13 ФУНКЦИЯ КОНКУРЕНТНОГО СХОДСТВА (FRIS- Function of Concurrent (Rival) Similarity) (Н.Г. Загоруйко, Новосибирск) Объекты a, b: близки или далеки? b похож на а или нет? Сходство – не абсолютная, а относительная категория 14 СУТЬ АЛГОРИТМА ФОРМИРОВАНИЯ ЭТАЛОНОВ НА ОСНОВЕ FRIS-функции (Н.Г. Загоруйко, Е.В.Волченко) Ω2 ρ =arg max ∑ rij - центр 1-го эталона класса j= 1, Ω1 j =1 ρc =arg min rρj - центр конкурирующего эталона U= (ρ) j= 1, Ω 2 {Y | r j ρj }{ } < rρc j \ Y j | rρj > rρcρ - эталон w ( ρ )= U ( ρ ) - вес обобщенного эталона 15 АЛГОРИТМ ФОРМИРОВАНИЯ ЭТАЛОНОВ НА ОСНОВЕ FRIS-функции (Н.Г. Загоруйко, Е.В.Волченко) Вход: Обучающая выборка {Y j } , Y j = ( a j1 , , a jg ) {значения признаков для каждого объекта Yj}. Выход: усредненные значения признаков для каждого g-эталона Yj’, wj - число объектов, вошедших в g-эталон Gj. 1: Для всех i=1,…,n, для всех j=1,…,n: найти расстояния rij ; 2: Пока выборка Ω1 не пуста осуществлять действия: 3: найти начальную точку формирования g-эталона ρ; 4: найти точку формирования конкурирующего g-эталона ρс ; 5: сформировать множество объектов U ( ρ ) и вес w ( ρ )= U ( ρ ) ; 6: зафиксировать новый g-эталон. 7: удалить из U объекты, вошедшие в U ( ρ ) . 8: повторить шаги 3-6 (формирование всех эталонов Ω1). 9: восстановить исходную обучающую выборку. 10: повторить шаги 3-8 (формирование всех эталонов Ω2). Вернуть {U ( ρ ) , w ( ρ )} для Ω1 и Ω2. 16 ЧИСЛЕННАЯ РЕАЛИЗАЦИЯ АЛГОРИТМА ФОРМИРОВАНИЯ ЭТАЛОНОВ НА ОСНОВЕ FRIS-функции 17 FRIS-ФУНКЦИЯ. ПРИМЕНЕНИЕ (Н.Г.Загоруйко) • Построения решающих правил для распознавания • Построения классификаций (кластерный анализ) • Поиск информативных признаков 18 ТИПЫ ВЫЯВЛЯЕМЫХ ЗАКОНОМЕРНОСТЕЙ. МЕТОДЫ DATA MINING Классификация. На основании информации о свойствах объекта ему присваивается определенное дискретное значение показателя, по которому проводится классификация (идентификатор). Классы заранее известны. Примеры: 1) классификация клиентов: захотят/не захотят приобрести определенный продукт или услугу (сокращение расходов на акциях продвижения товара); 2) фильтрация электронной почты (спам - письмо); 3) (РО) дана обучающая выборка двух образов (I и II) в пространстве двух бинарных признаков Z1 и Z2. Сформулировать решающее правило для разделения двух классов. I II Z1 Z2 1 1 1 1 Решение. Проекции реализаций на каждую ось показывают, что оба признака Z1 и Z2 по отдельности неинформативны. Использование этих признаков в системе позволяет найти правило для распознавания двух образов: признаки Z1 и Z2 у реализаций I -ro образа имеют одинаковые значения, а у II -ro образа - разные. С помощью алгоритмов классификации можно классифицировать объекты по заранее известным характеристикам. 19 ПРИМЕР РЕШАЮЩЕГО РАВИЛА В ЗАДАЧЕ РАСПОЗНАВАНИЯ x2 1 3 D(x1, x2) 2 ⇒ 3 4 2 3 1 2 1 4 1 2 Множество прямоугольников со сторонами, параллельными осям координат и их представление: множество точек в двухмерном признаковом пространстве с евклидовой метрикой, где x1 – длина горизонтальной стороны, x2 – длина вертикальной стороны. x1 Цель: распознавать два образа – S1 «вертикально вытянутые прямоугольники» и S2 «горизонтально вытянутые прямоугольники» Решающее правило. Биссектриса угла D ( x1 , x2 ) в начале координат: все точки (объекты), лежащие выше – левее D ( x1 , x2 ) , относятся к образу «вертикально вытянутые прямоугольники», ниже – правее – «горизонтально вытянутые прямоугольники». 20 ЗАДАЧА КЛАССИФИКАЦИИ ПРИМЕР. Задана следующая БД-таблица обучения (обучающая выборка) и подлежащая распознаванию строка ω'. Выбрать подходящий алгоритм, выбор обосновать, определить принадлежность данной строки какому-либо образу на основе обучения и выбранного алгоритма. Классы Объекты Ω1 Ω2 ω1 ω2 ω3 ω4 ω5 ω6 ω' X1 2 2 1 2 1 1 2 Значения признаков X2 X3 2 2 1 2 1 2 1 2 1 1 1 2 2 1 X4 2 2 1 1 1 2 1 21 ЗАДАЧА КЛАССИФИКАЦИИ Решение задачи-1. Одна метрика. Сумма расстояний от исследуемого объекта до всех объектов каждого класса. 1) Метрика Евклида. Евклидова дистанция между точками p и q – это длина отрезка pq. Пусть p = (p1, p2,…, pn) и q = (q1, q2,…, qn) – две точки в евклидовом пространстве, тогда длина отрезка pq равна: d(p,q)= 2 2 2 (p1 − q1 ) + (p 2 − q 2 ) + ... + (p n − q n ) = n ∑ (p k =1 k − q k )2 Евклидовы расстояния от точки ω' до точек обучающей выборки: 1. Для первого образа d EΩ1ω1 = (2 − 2) 2 + (2 − 2) 2 + (2 − 1) 2 + (2 − 1) 2 = 2 = 1, 41 ; d EΩ1ω2 = d EΩ1ω3 = (2 − 2) 2 + (1 − 2) 2 + (2 − 1) 2 + (2 − 1) 2 = 2 2 2 2 (1 − 2) + (1 − 2) + (2 − 1) + (1 − 1) = 2. Для второго образа 3 = 1,73 ; 3 = 1,73 . 2 = 1, 41 ; d EΩ 2 ω 4 = (2 − 2) 2 + (1 − 2) 2 + (2 − 1) 2 + (1 − 1) 2 = d E Ω 2 ω5 = (1 − 2) 2 + (1 − 2) 2 + (1 − 1) 2 + (1 − 1) 2 = 2 = 1, 41; d EΩ 2 ω6 = (1 − 2) 2 + (1 − 2) 2 + (2 − 1) 2 + (2 − 1) 2 = 4 = 2. Классы Объекты Ω1 Ω2 ω1 ω2 ω3 ω4 ω5 ω6 ω' X1 2 2 1 2 1 1 2 Значения признаков X2 X3 2 2 2 1 1 2 1 2 1 1 1 2 2 1 = 4,87 и ∑ d EΩ 2 = 4,82 , т.е. d EΩ1 > d EΩ2 . На основе полученных результатов можно сделать вывод, что данный объект принадлежит ко второму образу Ω2 (т.к. евклидово расстояние меньше). ∑d EΩ1 22 X4 2 2 1 1 1 2 1 ЗАДАЧА КЛАССИФИКАЦИИ Решение задачи-2. Одна метрика. Сумма расстояний от исследуемого объекта до эталонного объекта каждого класса. Классы Объекты X1 2 2 1 2 1 1 2 ω1 ω2 ω3 ω4 ω5 ω6 ω' Ω1 Ω2 Метод k ближайших соседей с эталонами Значения признаков X2 X3 2 2 1 2 1 2 1 2 1 1 1 2 2 1 X4 2 2 1 1 1 2 1 Усреднения признаков Усреднения признаков для объектов первого образа для объектов второго образа 2 +1+1 = 3 1+1+1 = x22ЭТ = 3 2 +1+ 2 = x32ЭТ = 3 + +2 1 1 = = x24ЭТ 3 2 X ЭТ = (1,33 1 2 + 2 +1 = 1,67 3 2 +1+1 = x12 ЭТ = 1,33 3 2+2+2 = x31ЭТ = 2 3 2 2 +1 + = x14 ЭТ = 1,67 3 1 X ЭТ = (1,67 1,33 2 1,67 ) = x12ЭТ = x11ЭТ 1,33 1 1,67 1,33 1,67 1,33) Рассчитаем расстояния от точки ω' до полученных эталонов: 1 ' d ( X ЭТ , ω= ) (1,67 − 2 ) d(X (1,33 − 2 ) 2 ЭТ , ω= ) ' 2 + (1,33 − 2 ) + ( 2 − 1) + (1,67 − 1)= 2,0067 = 1, 41658 2 + (1 − 2 ) + (1,67 − 1) + (1,33 − 1)= 2,0067 = 1, 41658 2 2 2 2 2 2 . Так как расстояния от заданной точки до первого и второго эталонов одинаковы, то заданную строку можно отнести как к первому Ω1, так и ко второму классу Ω2. 23 ЗАДАЧА КЛАССИФИКАЦИИ Решение задачи-3 («примирительное»). Несколько метрик. Принцип голосования. Евклидова метрика Метрика Хэмминга Метод k ближайщих соседей Метод k ближайщих соседей с эталонами Итоги (число голосов): Первый образ Ω1 Второй образ Ω2 1 1 0,5 0,5 0,5 0,5 1 3 Ответ: По результатам голосования делается вывод: заданную строку можно отнести ко второму образу Ω2. 24 ЗАДАЧИ ЛОГИЧЕСКИЕ. Варианты записи и интерпретации операции импликации В задачах возникают понятия: необходимое условие, достаточное условие, которые могут быть записаны с помощью связи импликации А→В: А достаточное условие для В А только, если В (не путать с «А если и только если В») В необходимое условие для А {А если и только если В}= {если не В, то не А} Необходимое и достаточное условие выражается двойной импликацией А ↔ В ПРИМЕР. Три подразделения – А, В, С – торговой фирмы стремились получить по итогам года максимальную прибыль. Экономисты высказали следующие предположения: 1) А получит максимальную прибыль только тогда, когда получат максимальную прибыль В и С; 2) либо А и С получат максимальную прибыль одновременно, либо одновременно не получат; 3) для того, чтобы С получил максимальную прибыль, необходимо, чтобы и В получил максимальную прибыль. По завершении года оказалось, что одно из трех предположений ложно. Какие из названных подразделений получили максимальную прибыль? Решение: По трем предположениям экономистов составим сложные высказывания: F1 = A →BC F2 = A ≡ C F3 = C → B 25 ЗАДАЧИ ЛОГИЧЕСКИЕ Логический метод системного анализа. Предположим, что у противника имеются три типа мин: Ко – осколочного действия, Коф – осколочно-фугасного действия, Кф – фугасного действия. В инструкции по применению этих мин сказано, что: − осколочные мины применяются на равнинной местности с каменистым грунтом или же на песчаных холмах; − осколочно-фугасные мины применяются либо на равнине, либо на местности с каменистым грунтом; − фугасные мины не применяются, если грунт каменистый, а местность – холмистая. Требуется по полученным знаниям построить прогноз (определить): а) какие мины будут применены противником в зависимости от вида ландшафта и типа грунта? б) что можно сказать о свойствах местности, если известно, что противник применяет только осколочно-фугасные мины? Решение. Предлагается вариант решения, который следует проанализировать и, если обнаружится противоречие, найти способ его исправления. Для решения задачи введем обозначения в терминах алгебры логики: А – равнинная местность; A холмистая местность; В – каменистый грунт; B - песчаный грунт. Условия можно записать: − A ⋅ B + A ⋅ B → Ко − A + B → К оф Всего можно составить 4 пары сочетаний местность-грунт: A⋅ B  A⋅ B  − A ⋅ B → Кф A⋅ B A⋅ B  Исходя из определений конъюнкции и дизъюнкции можно сделать следующие выводы: Результат: 1) если местность равнинная, а грунт каменистый, противник будет применять  A ⋅ B → К о ,К оф осколочные или осколочно-фугасные мины;  К , К A B ⋅ → 2) если местность равнинная, а грунт песчаный – осколочно-фугасные или фугасные оф ф   мины;  A ⋅ B → К оф 3) если местность холмистая, а грунт каменистый – осколочно-фугасные мины. Если  A⋅ B → К местность холмистая, а грунт песчаный – осколочные мины; о  26 КЛАССИФИКАЦИЯ СИСТЕМ РАСПОЗНАВАНИЯ ОБРАЗОВ. Один из вариантов 1. СИСТЕМЫ С ФАКТОРОМ ОБУЧЕНИЯ/БЕЗ ОБУЧЕНИЯ 1.1. Системы без обучения. Требуют значительное количество априорной информации. 1.2. Системы с обучающей последовательностью конкретной длины. Среднее количество априорной информации связано с длиной обучающей последовательности. 1.3. Самообучающиеся системы. Имеют малое количество априорной информации и накапливают ее в процессе функционирования. 2-я группа - системы классифицируются с учетом аппарата обработки данных. 2. СИСТЕМЫ С КОНКРЕТНЫМ ВИДОМ БАЗОВОГО МЕТОДА ОБРАБОТКИ ДАННЫХ - логические методы; - аналитические методы; - статистические методы; - вероятностные методы; - энтропийные методы; - бионические методы (персептрон, сети с латеральным торможением и т,д.). .................................................................................. 3. СИСТЕМЫ С ОПРЕДЕЛЕННЫМИ ХАРАКТЕРИСТИКАМИ ПРОЦЕССА РАСПОЗНАВАНИЯ. - время распознавания (или количество шагов метода); - точность полученного результата; - общность получаемых результатов (универсальность метода); - количество и качество признаков, участвующих в реализации метода и т. д. АЛГЕБРАИЧЕСКИЙ ПОДХОД К КОНСТРУИРОВАНИЮ КОРРЕКТНЫХ АЛГОРИТМИЧЕСКИХ КОМПОЗИЦИЙ И ОЦЕНКЕ КАЧЕСТВА РАСПОЗНАВАНИЯ (СКОЛЬЗЯЩИЙ КОНТРОЛЬ) 27 ИЕРАРХИЯ ОТНОШЕНИЙ МЕЖДУ ОБРАЗАМИ, КЛАССАМИ И ОБЪЕКТАМИ 28 ЛОГИЧЕСКИЙ МЕТОД КЛАССИФИКАЦИИ ОБЪЕКТОВВОПРОСНО-ОТВЕТНАЯ ПРОЦЕДУРА Составить алгоритм распознавания 4-х символов-иероглифов (блок-схему), определив предварительно признаковое пространство. Блок-схема простой логической (вопросноответной) процедуры классификации Простые символы можно распознать с помощью тестов, проверяющих наличие ПРИЗНАКОВ: 1) вертикальной 4) открытой верхней черточки, части, 2) горизонтальной 5) открытой нижней черточки, части и 3) отдельной последовательности точки, точек, 6) количества и последовательности черточек. 29 ПРИМЕР РЕШАЮЩЕГО РАВИЛА В ЗАДАЧЕ РАСПОЗНАВАНИЯ ПРИМЕР (Тестовое распознавание) Даны матрицы Q - описание 6-ти объектов; R соответствие номеров объектов и классов. z1 z2 z3 z4 1 0 1 1 0  1 1  2 1 2 0 1  2 1      3 0 1 0 1  3 1  = Q ; R    . 4 1 2 1 0  4 2 5 1 1 0 1  5 2     6 1 1 1 2  6 2 Решение. Набор тестов порождает описание обучающих объектов: z1 z2 1 2 3 Q1 ( Θ1 ) = 4 5 0 1  0  1 1  6 1 1 2 1 2 1 z3 1 1 z4 − 1 − 2  − 3  ; Q2 ( Θ 2 ) = − 4 − 5  1 1 − 6 z1 z2 0 1  0  1 1  1 1 2 1 2 1 z3 − − − − − 1 − z4 Найденные по ОВ тесты Θ1, Θ2, Θ3: Θ1={z1, z2, z3}, Тест – набор классификационных Θ2={ z1, z2, z4} признаков. Реакция теста на объект дает вектор значений признаков. Учет матрицы Θ3={z2, z3, z4}. R + правило голосования приводит к классификации нового объекта. Задача. Сформировать решающее правило, по которому можно отнести объект S=(0, 1, 2, 2) (не входящий в обучающую выборку) к одному из выделенных классов. 1 0 2 1  3 1  ; Q3 ( Θ3 ) = 4 0 5 1  6 2 z1 z2 z3 z4 1 2 1 2 1 1 1 1 1 0 1  1  0 1  2 − −  −  − −  − Реакция описания S=(0, 1, 2, 2) на тесты Θ1, Θ2, Θ3: Θ1(S)={0, 1, 2, -}, Θ2(S)={0, 1, -, 2}, Θ3(S)={-, 1, 2, 2}. Решение. Новый объект S=(0, 1, 2, 1) тестовый алгоритм не отнесет S ни к одному из классов. Однако по набору Θ={z1, z2} (части теста) по фрагменту (0, 1) (содержится в S и объектах из 1го класса и не содержится в объектах из 2-го класса) возможно отнесение объекта S к первому классу.