Алгоритмы ограниченного перебора

Алгоритмы ограниченного перебора были предложены в середине 60-х годов М.М. Бонгардом для поиска логических закономерностей в данных. С тех пор они продемонстрировали свою эффективность при решении множества задач из самых различных областей.

Эти алгоритмы вычисляют частоты комбинаций простых логических событий в подгруппах (классах) данных. Примеры простых логических событий: X = C1; X < C2; X > C3; C4 < X < C5 и др., где X – какой либо параметр (поле), Ci – константы. Ограничением служит длина комбинации простых логических событий (у М. Бонгарда она была равна 3). На основании сравнения вычисленных частот в различных подгруппах данных делается заключение о полезности той или иной комбинации для установления ассоциации в данных, для классификации, прогнозирования и пр.

Система WizWhy предприятия WizSoft (http://www.wizsoft.com) является современным представителем подхода, реализующего ограниченный перебор. Хотя разработчики системы не раскрывают специфику алгоритма, положенного в основу работы WizWhy, вывод о наличии здесь ограниченного перебора был сделан по результатам тщательного тестирования системы (изучались результаты, зависимости времени их получения от числа анализируемых параметров и др.). По-видимому, в WizWhy ограниченный перебор используется в модифицированном варианте с применением дополнительного алгоритма “Apriori”, заранее исключающего из анализа элементарные логические события, встречающиеся с одинаково высокой (низкой) частотой в различных классах.

Авторы WizWhy акцентируют внимание на следующих общих свойствах системы:

• Выявление ВСЕХ if-then правил

• Вычисление вероятности ошибки для каждого правила

• Определение наилучшей сегментации числовых переменных

• Вычисление прогностической силы каждого признака

• Выявление необычных феноменов в данных

• Использование обнаруженных правил для прогнозирования

• Выражение прогноза в виде списка релевантных правил

• Вычисление ошибки прогноза

• Прогноз с учетом стоимости ошибок

В качестве достоинств WizWhy дополнительно отмечают такие:

- На прогнозы системы не влияют субъективные причины

- Пользователям системы не требуется специальных знаний в прикладной статистике

- Более точные и быстрые вычисления, чем у других методов Data Mining

Для убедительности авторы WizWhy противопоставляют свою систему нейросетевому подходу и алгоритмам построения деревьев решений и утверждают, что WizWhy, обладая более высокими характеристиками, вытесняет другие программные продукты с рынка Data Mining. Стоимость системы около $ 4000, количество пользователей » 30000.

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

Так, система WizWhy “категорически отказывается” находить какое-либо логическое правило в тесте 1. Это связано с неадекватностью утверждения об “Определении наилучшей сегментации числовых переменных”. Здесь совершается классическая ошибка, связанная с непониманием того, что “часть не есть целое”. Разработчики стремятся найти наилучшее разбиение количественных признаков на интервалы, рассматривая каждый признак изолированно от всей системы признаков. А в тесте 1, как уже указывалось, признаки Х1 и Х2 по отдельности не представляют абсолютно никакой ценности для разграничения крестиков и ноликов.

В тесте 2 система WizWhy сумела найти только одно более или менее полное логическое высказывание, которое правильно относит к классу К 52 из 53 покрываемых объектов (записей):

IF (a2 = B) и (a6 = B) и (a7 = A) и (a34 = B) и (a61 = A) THEN класс = K.

Причина очевидной оплошности системы здесь кроется в том, что она способна находить логические правила, содержащие не более 6 элементарных событий. Это, собственно говоря, и есть ограничение “ограниченного перебора” в действии – в рассмотренном тесте требуется найти заданные экзаменатором логические правила, включающие до 15 элементарных событий (ai = A или B).

Knowledge Discovery in Databases

Knowledge Discovery in Databases (KDD) – (обнаружение знаний в базах данных) это процесс поиска полезных знаний в 'сырых данных'. KDD включает в себя вопросы подготовки данных, выбора информативных признаков, очистки данных, применения методов Data Mining (DM), постобработки данных, интерпретации полученных результатов. Безусловно, сердцем всего этого процесса являются методы DM, позволяющие обнаруживать знания.

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

Процесс KDD, состоит из следующих шагов:

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

2. Предобработка данных. Для того, чтобы эффективно применять методы Data Mining, следует обратить серьезное внимание на вопросы предобработки данных. Данные могут содержать пропуски, шумы, аномальные значения и т.д. Кроме того, данные могут быть избыточны, недостаточны и т.д. В некоторых задачах требуется дополнить данные некоторой априорной информацией. Наивно предполагать, что если подать данные на вход системы в существующем виде, то на выходе получим полезные знания. Данные должны быть качественны и корректны с точки зрения используемого метода DM. Поэтому первый этап KDD заключается в предобработке данных. Более того, иногда размерность исходного пространства может быть очень большой, и тогда желательно применение специальных алгоритмов понижения размерности. Это как отбор значимых признаков, так и отображение данных в пространство меньшей размерности.

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

4. Data Mining. На этом шаге применяются различные алгоритмы для нахождения знаний. Это нейронные сети, деревья решений, алгоритмы кластеризации и установления ассоциаций и т.д.

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

Пакет Deductor – полнофункциональный инструмент для Knowledge Discovery in Databases, позволяющий провести все вышеописанные шаги.

Подготовка исходного набора данных. В каждом приложении из состава пакета для этого предназначен специальный мастер подключения. Мастер позволяет импортировать данные из следующих источников: Oracle, DB2, MS SQL, Informix, Sybase, Interbase, DBase, FoxPro, Paradox, MS Access, CSV (текстовые файлы с разделителями), ODBC.

Предобработка данных. Для выполнения этого шага в пакете существует приложение RawData Analyzer.

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

Data Mining. В состав пакета включены приложения, реализующие популярные и эффективные методы DM. Neural Analyzer – нейронные сети, Tree Analyzer – деревья решений, Somap Analyzer – самоорганизующиеся карты Кохонена.

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

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