Logo Море(!) аналитической информации!
IT-консалтинг Software Engineering Программирование СУБД Безопасность Internet Сети Операционные системы Hardware
Обучение от Mail.Ru Group.
Онлайн-университет
для программистов с
гарантией трудоустройства.
Набор открыт!
2007 г.

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

Л. Е. Карпов, В. Н. Юдин
Препринт ИСП РАН

Назад   Оглавление   Вперёд

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

2.1. Концепция вывода

Вывод на основе прецедентов – это метод принятия решений, в котором используются знания о предыдущих ситуациях или случаях (прецедентах). При рассмотрении новой проблемы (текущего случая) отыскивается похожий прецедент в качестве аналога. Вместо того, чтобы искать решение каждый раз сначала, можно пытаться использовать решение, принятое в сходной ситуации, возможно, адаптировав его к изменившейся ситуации текущего случая. После того, как текущий случай будет обработан, он вносится в базу прецедентов вместе со своим решением для его возможного последующего использования в будущем. Более формальное определение дано в [Bundy 97].

Прецедент ­­­­­– это описание проблемы или ситуации в совокупности с подробным указанием действий, предпринимаемых в данной ситуации или для решения данной проблемы.

Согласно [Althof 95/1] прецедент включает:

  • Описание проблемы,
  • Решение этой проблемы,
  • Результат (обоснованность) применения решения.

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

    Исход как результат применения решения – это обратная связь, полученная от применения решения. Описание результата может содержать перечень выполненных операций, результат их выполнения, способ восстановления (в случае отказа), указания на то, что можно сделать, чтобы избежать отказа, результаты восстановления. Описание результата может также включать ссылки на другие прецеденты, дополнительную текстовую информацию.

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

    Имеется множество способов представления прецедента: от записей в базах данных, древовидных структур – до предикатов и фреймов. Конкретное выбранное представление прецедентов должно соответствовать общим целям системы. Проблема представления прецедента – прежде всего проблема выбора информации, которую надо включать в описание прецедентов, нахождение соответствующей структуры для описания содержания прецедента, а также определения, каким образом должна быть организована и индексирована база знаний прецедентов для эффективного поиска и многократного использования.

    2.2. Декомпозиция метода (основные фазы)

    Хотя не все системы вывода, основанного на прецедентах, полностью включают этапы, приведенные ниже (Рис. 1), подход, основанный на прецедентах, в целом состоит из следующих компонентов [Aamodt 94]:

  • Извлечение наиболее релевантных прецедентов для текущего случая из библиотеки прецедентов.
  • Адаптация выбранного решения для текущего случая, если это необходимо.
  • Применение решения.
  • Оценка применения (проверка корректности).
  • Сохранение. Добавление текущего случая в базу прецедентов.

    Рис 1. Цикл вывода на основе прецедентов

    Проблема выбора подходящего прецедента является одной из самых важных в таких системах. Естественно искать подходящий прецедент в той области пространства поиска, где находятся решения сходных проблем, иначе говоря, поиск должен быть организован сообразно цели. Но как определить, какие именно решения считать сходными?

    Эффективность поиска прецедентов для текущего случая во многом зависит от того, по каким признакам организован индекс в базе прецедентов. Это, в свою очередь, требует хороших знаний о предметной области и конечной цели решения проблемы. Однако выбор наилучшего индекса не может быть столь же прост, как это звучит, так как не имеется никаких общих рекомендаций для этого. Для ориентира, однако, можно привести четыре свойства хороших индексов [Kolodner 83]:

  • Направленность: Индексы должны быть направлены на решение цели.
  • Абстрактность: Индексы должны быть достаточно абстрактны, чтобы прецедент мог быть использован в разных запросах.
  • Конкретность: Индексы должны быть распознаваемы в других ситуациях без дальнейшей обработки.
  • Полноценность: Индексы должны быть способны дифференцировать прецеденты.

    После того, как прецеденты извлечены, нужно выбрать "наиболее подходящий" из них. Это определяется сравнением признаков текущего случая и выбранных прецедентов. Определение метода, на котором будет основываться нахождение меры сходства прецедентов, решается во время создания системы ее разработчиками. Наиболее популярным и часто используемым является метод "ближайшего соседа" (nearest neighbour) [Anand 99]. В его основе лежит тот или иной способ измерения степени близости прецедента и текущего случая по каждому признаку (будь это текстовый, числовой или булевский), который пользователь сочтет полезным для достижения цели.

    Говоря более строгим языком, вводится метрика на пространстве всех признаков, в этом пространстве определяется точка, соответствующая текущему случаю, и в рамках этой метрики находится ближайшая к ней точка из точек, представляющих прецеденты. Описанный здесь алгоритм очень прост – реально применяются некоторые его модификации. Обычно прогноз делается на основе нескольких ближайших точек, а не одной (K-nearest neighbours). Такой метод более устойчив, поскольку позволяет сгладить отдельные выбросы, случайный шум, всегда присутствующий в данных.

    Каждому признаку назначают вес, учитывающий его относительную ценность. Полностью степень близости прецедента по всем признакам можно вычислить, используя обобщенную формулу вида:

    где wj – вес j-го признака, sim – функция подобия (метрика), xij и xik – значения признака xj для текущего случая и прецедента, соответственно. После вычисления степеней близости все прецеденты выстраиваются в единый ранжированный список.

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

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

    Пусть имеются образцы Xi и Xk в N-мерном пространстве признаков. Основные метрики, традиционно используемые при выборе прецедентов, приводятся в таблице 1.

    После того, как выбран подходящий прецедент, при поиске решения для целевой проблемы выполняется адаптация – модификация имеющегося в нем решения с целью его оптимизации. Невозможно выработать единый вариант для такой адаптации, так как это в большой степени зависит от предметной области. Если существуют алгоритмы адаптации, они обычно предполагают наличие зависимости между признаками прецедентов и признаками содержащихся в них решений. Такие зависимости могут задаваться человеком при построении базы прецедентов или обнаруживаться в базе автоматически.

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

    • Повторная конкретизация переменных в существующем прецеденте и присвоение им новых значений.
      • Уточнение параметров. Некоторые прецеденты могут содержать числовые значения, например, время выполнения какого-либо этапа плана. Это значение должно быть уточнено в соответствии с новым значением другого свойства.
    • Поиск в памяти. Иногда требуется найти способ преодоления затруднения, возникшего как побочный эффект замены одних компонентов решения другими.

    Обратная связь, возникающая при сохранении решений для новых проблем, означает, что вывод по прецедентам по своей сути является "самообучающейся" технологией, благодаря чему рабочие характеристики каждой базы прецедентов с течением времени и накоплением опыта непрерывно улучшаются. Разработка баз прецедентов по конкретной проблеме или области деятельности происходит на естественном (русском, английском) языке, то есть не требует никакого программирования, и может быть выполнена наиболее опытными сотрудниками – экспертами, работающими в данной конкретной области.

    Не стоит, однако, рассчитывать, что экспертная система будет действительно принимать решения. Принятие решения всегда остается за человеком, а система лишь предлагает несколько возможных вариантов и указывает на самый "разумный" из них с ее точки зрения.
    Наименование метрики Тип признаков Формула для оценки меры близости (метрики)
    Эвклидово расстояние Количественные
    Манхэттенская метрика Количественные
    Мера сходства Хэмминга Номинальные (качественные) ,
    где nik – число совпадающих признаков у образцов Xi и Xk.
    Мера сходства Роджерса-Танимото Номинальные шкалы
    где – число совпадающих единичных признаков у образцов Xi и Xk;
    , – общее число еди-ничных признаков у образцов Xi и Xk соответственно.
    Расстояние Махалонобиса Количественные
    W – ковариационная матрица выборки
    Расстояние Журавлева Смешанные , где

    Таблица 1. Основные типы метрик.

    2.3. Примеры систем вывода на основе прецедентов

    Вывод по прецедентам – не новая технология, ее возникновение прослеживается в работе Роджера Шанка по динамической памяти [Schank 82]. Изложенные этим исследователем идеи были далее расширены Джанет Колоднер, которая разработала систему CYRUS [Kolodner 83]. С 1988 года проводился ряд ежегодных семинаров под эгидой DARPA (Управление Перспективных Исследований Министерства Обороны США) [Kolodner 88, Hammond 89, Bareiss 91]. Интерес к методу вырос в последние годы, регулярно проводятся конференции и семинары типа широко известного Европейского семинара (EWCBR, в последующем – ECCBR) [Wess 93, Haton 94, Smith 96, Smyth 98, Blanzieri 00, Craw 02, Funk 04], семинара Соединенного Королевства (UKCBR) [UKCBR 04, UKCBR 05].

    К ранним разработкам относят CHEF [Hammond 86] – систему, которая предназначалась для формирования кулинарных рецептов. Эта программа принимает информацию о целевых характеристиках блюда (тип, вкусовые качества, своеобразие) и формирует подходящий рецепт. Результатом работы программы должен быть рецепт – последовательность операций, позволяющая приготовить такое блюдо. Получив заказ, программа просматривает свою базу прецедентов, отыскивает в ней рецепт приготовления аналогичного блюда и адаптирует его в соответствии с особенностями текущего заказа.

    Из других систем можно отметить PROTOS [Bareiss 88] для классификации и диагностирования нарушений слуха, MEDIATOR [Simpson 85] для области посредничества в спорных судебных вопросах.

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

    В основу программы HYPO [Ashley 88, Ashley 90], которая была создана для обучения студентов-юристов методике ведения судебных дел, положена абстрактная модель процесса прения сторон. И расследования, и рассуждения в юриспруденции направляются аргументацией, а более точно – аргументами, выражающими противоположные интересы, с помощью которых стороны процесса пытаются склонить на свою сторону судью или присяжных, убедить их в том, что именно предлагаемая интерпретация закона и фактов является корректной в данном случае.

    Базовая предпосылка, сделанная авторами, состоит в том, что эти ходы могут быть описаны в рамках какой-то системы и затем использованы для обучения. Для выполнения очередного хода в игре нужно выбрать прецеденты в базе знаний о прецедентах, причем выбор должен учитывать как информацию о текущем случае, так и возможные ходы оппонентов. Таким образом, поведение сторон можно рассматривать как планирование трехходовой комбинации в игре:

  • одна сторона с помощью своего набора прецедентов "продвигает" свою позицию в игре;
  • противоположная сторона выдвигает другой набор прецедентов для представления своих аргументов;
  • первая сторона наносит новый удар, выдвигая соображения, парирующие в определенной степени аргумент противной стороны.

    Ходы и контрходы можно анализировать в терминах суждений, основанных на прецедентах. Авторы системы считают, что в основе такой модели аргументации лежит следующий процесс [Ashley 90]:

  • Сравнение текущего случая с прецедентом с прицелом на обоснование аналогичного результата.
  • Определение отличия (противопоставления) между текущим случаем и прецедентом, чтобы найти аргумент против того же результата.
  • Поиск контрпримера к (1), в котором аналогичный прецедент привел к другому результату.
  • Формулировка гипотетических прецедентов, которые дали бы аргументы за и против определенной позиции.
  • Комбинирование сравнений и противопоставлений в аргумент, который включает оценку конкурирующих аргументов.

    Эта модель аргументации реализована в системе HYPO, в которой процесс формирования аргумента выполняется за шесть шагов.

  • Анализ факторов, присущих текущему случаю.
  • Извлечение прецедентов на основе этих факторов.
  • Упорядочение извлеченных прецедентов по степени близости к текущему случаю.
  • Выбор наиболее подходящих прецедентов как с точки зрения одной стороны, так и с точки зрения другой.
  • Формирование аргументов для трехходовой комбинации по каждому из пунктов текущего дела.
  • Проверка результатов на гипотетических случаях.

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

    Что касается доступности коммерческих систем и успеха в информационных приложениях – это система SMART [Acorn 92], которая дала импульс этой технологии. Система SMART предназначена для технической поддержки заказчиков корпорации COMPAQ. Когда заказчик сталкивается с проблемой (например, печать принтера блекнет), подробности передаются в систему. Выполняется начальный поиск в библиотеке прецедентов, чтобы найти случаи с подобными признаками. При недостатке информации система задает дополнительные вопросы. Как только определенный порог достигнут (скажем, прецедент совпадает не менее, чем на 80%), предлагается решение от прецедента. В дополнение к этому, система может быть использована как инструмент обучения.

    В дальнейшем COMPAQ расширила эту систему, продвинув ее непосредственно к покупателям. Система QUICKSOURCE [Nguyen 93] позволяет пользователю самому справляться с проблемами и обращаться в центр поддержки в качестве последнего прибежища.

    В системе KATE TOOLS компании Acknosoft (Франция) [Althof 95/1] поддерживается упрощенный взгляд на процесс вывода. Входная информация для KATE – это файл, который содержит описания признаков и их значения на специальном языке CASUAL [Althof 95/2]. KATE может работать со сложными данными, представленными в виде структурированных объектов, отношениями или даже общими знаниями о проблемной области. Но для выявления сходства между прецедентами используется одна простая метрика.

    Основной акцент делается на отбор прецедентов с помощью алгоритма "ближайшего соседа". KATE использует версию алгоритма ближайшего соседа для вычисления метрики подобия. Близость между двумя случаями x и y, имеющими p признаков вычисляется по формуле:

    Similarity(x,y)= -, где f определяется как

    Алгоритм работы системы может быть описан следующим образом:

     

      Classified Data = 0
     for each Case x in Casebase do

    1. for each y in Classified Data do

    Sim(y) = Similarity(y,x)

    2. y_max = (y_1,...,y_k) such that

    Sim(y_k)= max(K-nearest neighbors)

    3. if class(y_max) = class(x)

    then classification is correct

    Classified Data = Classified Data + {x}

    else classification is incorrect

    Система KATE не предлагает возможностей для автоматической адаптации решения. Проверка корректности решения невозможна, но есть проверка базы прецедентов на наличие контрпримеров. Все же, KATE – это эффективная индустриальная система, которая позволяет использовать взвешенные признаки при вычислении метрики подобия, а также использовать определяемую пользователем метрику. Ее легко расширять, потому что все функции KATE доступны при подключении сопутствующих динамических библиотек (.dll).

    В настоящее время на рынке программных продуктов реально предлагается лишь несколько коммерческих продуктов, реализующих технологию вывода, основанного на прецедентах. Это объясняется, в первую очередь, сложностью алгоритмов и их эффективной программной реализации. Наиболее успешные и известные из присутствующих на рынке продуктов – CBR Express и Case Point (Inference Corp.), Apriori (Answer Systems), DP Umbrella (VYCOR Corp.) [Althof 96].

    CBR Express и CasePoint – продукты, предназначенные для разработки экспертных систем, основанных на прецедентах. CBR Express тоже накапливает "опыт", обеспечивая ввод, сопровождение и динамическое добавление прецедентов, а также простой доступ к ним с помощью вопросов и ответов. Обе системы используются при автоматизации информационно-справочных служб и "горячих линий", а также при создании интеллектуальных программных продуктов, систем доступа к информации, систем публикации знаний и т. д.

    При общении с системой сначала вводится простой запрос, например: "Мой компьютер не работает". Далее происходит выделение ключевых слов, поиск в базе прецедентов, и генерируется перечень потенциальных решений. Пользователю могут быть также заданы уточняющие вопросы. Предлагаемые варианты решения проблемы могут включать в себя видео- или фотоматериалы. Технология вывода по прецедентам представляет собой основу для практически безграничных приложений, которые наращиваются за счет постоянного сбора информации (причем обеспечивается совмещение структурированных и неструктурированных данных, включая мультимедиа). По мнению компаний, активно использующих эту технологию, таких как Nippon Steel, Lockheed и некоторых других, создается самообучающаяся коллективная память, исключительно удобная для накопления и передачи профессионального опыта.

    Назад   Оглавление   Вперёд

  • Новости мира IT:

    Архив новостей

    Последние комментарии:

    Релиз ядра Linux 4.14  (9)
    Среда 22.11, 19:04
    Loading

    IT-консалтинг Software Engineering Программирование СУБД Безопасность Internet Сети Операционные системы Hardware

    Информация для рекламодателей PR-акции, размещение рекламы — adv@citforum.ru,
    тел. +7 985 1945361
    Пресс-релизы — pr@citforum.ru
    Обратная связь
    Информация для авторов
    Rambler's Top100 TopList liveinternet.ru: показано число просмотров за 24 часа, посетителей за 24 часа и за сегодня This Web server launched on February 24, 1997
    Copyright © 1997-2000 CIT, © 2001-2015 CIT Forum
    Внимание! Любой из материалов, опубликованных на этом сервере, не может быть воспроизведен в какой бы то ни было форме и какими бы то ни было средствами без письменного разрешения владельцев авторских прав. Подробнее...