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

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

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

5. Использование методов добычи данных для отбора прецедентов

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

Большая часть существующих подходов к использованию методов добычи данных в системах вывода по прецедентам сосредоточена на одном аспекте такого использования: выборе наиболее релевантных прецедентов. Здесь применяются различные методы добычи данных, среди них – деревья решений, байесовские сети, нейронные сети, методы k-ближайших соседей, и т.д. Все они предлагают тот или иной способ измерения степени близости прецедента и текущего случая по их признакам.

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

5.1. Байесовские сети

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

В основе байесовских сетей лежит теорема Байеса теории вероятностей для определения апостериорных вероятностей попарно несовместных событий Y_i по их априорным вероятностям:

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

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

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

Экерман [Heckerman 97] отмечает четыре достоинства байесовских сетей как средства извлечения данных:

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

Несмотря на свою простоту, скорость и интерпретируемость результатов, наивно-байесовский алгоритм имеет недостатки:

• перемножать условные вероятности корректно только тогда, когда все входные переменные действительно статистически независимы; допущение этой независимости и обуславливает уточнение "наивно-" в названии алгоритма, хотя, по приведенным в [Brand 98/2] примерам он показывает неплохие практические результаты даже при несоблюдении условия статистической независимости; корректно данная ситуация обрабатывается только более сложными методами, основанными на обучении байесовских сетей [Heckerman 95, Heckerman 97];
• невозможна непосредственная обработка непрерывных переменных – их требуется разбивать на множество интервалов, чтобы атрибуты были дискретными; такое разбиение в ряде случаев приводит к потере значимых закономерностей [Brand 98/2];
• наивно-байесовский подход учитывает только индивидуальное влияние входных переменных на результат классификации, не принимая во внимание комбинированного влияния пар или троек значений разных атрибутов [Brand 98/2], что было бы полезно с точки зрения прогностической точности, но значительно увеличило бы количество проверяемых комбинаций.

Байесовские сети активно использовались для формализации знаний экспертов в экспертных системах [Heckerman 95], но с недавних пор стали применяться для извлечения знаний из наборов данных. Приведем несколько примеров систем, в которых используется интеграция байесовских сетей и вывод по прецедентам.

Компания Microsoft разработала прототип системы для диагностики неисправностей с кодовым именем ALADDIN [Breese 95]. В системе используется трехуровневая байесовская сеть. Первый уровень описывает одну или несколько причин – факторов, приведших к сбою, второй – результат, который будет получен при наличии всех причин, и третий – симптомы, вызываемые результатом. Байесовская сеть конструируется экспертом и корректируется при каждом использовании. Microsoft прекратила использование системы в связи с малым объемом базы знаний.

В Университете Salford’а [Rodriguez 97], была разработана система, в которой одна байесовская сеть используется для индексации категорий – групп прецедентов, объединенных по принципу общности свойств, а другая – для индексации экземпляров, то есть единичных прецедентов внутри категории.

INBANCA [Aha 96] – система, разработанная Центром Прикладных Исследований ВМС США для принятия плана действий, адекватных текущей ситуации. Байесовская модель используется при описании окружающей среды.

D-SIDE [Tirri 96] – это программный пакет, разработанный в Университете Хельсинки. Здесь прецеденты рассматриваются как вектора. Допускается, что база может иметь некорректные прецеденты. Байесовская модель используется при адаптации решения прецедента к текущему случаю, в частности, для предсказания наиболее вероятных значений отсутствующих признаков.

Существующие системы используют разные подходы. Первые две используют добычу данных для выявления знаний о предметной области. INBANCA использует прецеденты для выбора плана действий, ALADDIN использует прецеденты для устранения ошибки, найденной с помощью байесовских сетей, система в Salford’е использует байесовские сети для манипулирования прецедентами, и, наконец, D-SIDE использует прецеденты для классификации.

5.2. Разбиение базы прецедентов на классы

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

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

В решении, предложенном авторами системы M² [Anand 97/2, Anand 98], используется предварительная кластеризация базы прецедентов. Кластеризация применяется в двух аспектах: сбор прецедентов и отыскание недостающих знаний при адаптации решения. В [Anand 98] подробно обсуждается подход к обнаружению прецедентов и в кратких чертах – методология адаптации решения.

В этой системе задачу кластеризации входных данных выполняет нейронная сеть Кохонена. При решении этой задачи образуются начальные кластеры, которые затем анализируются с использованием алгоритма построения дерева решений C4.5 [Quinlan 93]. Неуникальные кластеры группируются.

На последней стадии используется алгоритм индукции регрессионного дерева, чтобы гарантировать, что эти понятия информационно полны.

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

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

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

Для наглядности приведем пример из медицины. Текущий случай – это пациент, описываемый тремя признаками (симптомы острого живота):

1. боли в животе,
2. напряжение передних мышц брюшной стенки,
3. болезненная перкуссия по брюшной стенке.

В пространстве этих признаков точка, соответствующая текущему случаю, попадает в пересечение кластеров (заболеваний):

1. прободная язва желудка,
2. спонтанный разрыв пищевода,
3. перитонит,
4. базальная плевропневмония.

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

5.3. Другие примеры систем, использующих интегрированный подход

Корпорацией NEC для управления общей корпоративной базой данных разработан Case-метод [Kitano 96, Leake 96]. Утверждается, что накопление данных в виде прецедентов, выявление закономерностей и последующее внедрение полученных знаний повышают общий профессиональный уровень сотрудников корпорации. В качестве алгоритмов добычи данных используются извлечение правил, статистические методы, и другие.

В Университете города Росток (ФРГ) разработана система для прогноза эпидемий [Bull 97]. В качестве прецедентов используются последовательности т.н. сценариев, в которые входят новые случаи заболеваний, нагрузка на органы здравоохранения, контекстная информация о сезоне и погоде. Чтобы обнаружить "заметные" изменения в последовательностях сценариев, используется статистический метод добычи данных, называемый G-тест. Для сверки результата используются методы вывода по прецедентам.

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