Исследование и разработка системы поддержки принятия решений на основе прецедентов (стр. 4 )

Рис. 1. Степени близости прецедентов (цифрами обозначены расстояния между текущим случаем и прецедентами).

Приведем более строгое определение предлагаемой меры:

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

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

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

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

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

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

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

по состоянию до применения решения, или воздействия (входным признакам), по воздействию, по состоянию после воздействия (выходным признакам).

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

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

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

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

Представим, что описание текущего случая щ, представленного значениями признаков ,…, (щ1,…,щn, где n – общее число возможных признаков), в этом пространстве признаков находится в пересечении проекций нескольких кластеров. Его аналог ш, представленный значениями признаков ,…, (ш1,…,шn), принадлежит одному из таких кластеров Pш. Набор признаков аналога ш, в общем случае, не совпадает с набором признаков текущего случая щ. Решение, содержащееся в нём, может влиять на признак шi, который отсутствует в щ (шiщ1,…,щn). Первый шаг к адаптации решения – попытаться выявить в щ новый признак, соответствующий шi, без которого решение для щ теряет смысл.

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

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

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

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

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

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

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

Значимость равна 1, когда кластеры разделены, и меньше 1, когда кластеры пересекаются.

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

В третьей главе были рассмотрены практические вопросы построения системы поддержки принятия решений на основе предложенного метода и приведена их конкретная реализация в интегрированной среде объектно-ориентированного программирования Borland C++ Builder.

Предпочтение было отдано системе C++ Builder благодаря широкому набору стандартных средств программирования, позволяющих экономить время на создание различных программных интерфейсов и реализации общих для широкого спектра программных продуктов функций. Еще одним преимуществом выбранной системы является высокая эффективность генерируемого компилятором кода, что весьма существенно для данного продукта, т.к. в нем применяются методы, требующие большого количества вычислений. В состав С++Builder включен Borland Datаbase Engine (BDE), обеспечивающий гибкий механизм работы с базами данных, в который входят средства доступа ко всем популярным форматам современных баз данных. В связи с тем, что система ориентирована на персональный компьютер, для реализации выбраны локальные базы данных, к которым BDE обеспечивает доступ. Системные таблицы реализованы на файлах Paradox, импорт возможен из файлов dBASE, FoxPro, и Access.