Осколки знаний

Россия, Санкт-Петербургский институт информатики и автоматизации РАН

В.А. Дюк

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

К задаче поиска комбинаций элементарных логических событий, характерных для строк определенных частей таблиц данных “объект-признак”, сводятся различные задачи: классификации, диагностики, прогнозирования, распознавания, определения ассоциаций, нахождения if-then правил и др. (элементарные логические события это X = C₁, X < C₂, X > C₃, C₄ < X < C₅ и др., где X – какой либо признак, C_i – константы). В аналогичном ракурсе может быть рассмотрена задача поиска шаблонов (в том числе непериодических, сложной формы) в последовательности символов.

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

В настоящее время широко используются три основных подхода к поиску логических правил в данных: деревья решений, генетические алгоритмы и ограниченный перебор. Эти подходы представляют собой современную теоретическую базу области, получившей название Data Mining и “обнаружение знаний в базах данных” (knowledge discovery in databases).

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

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

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

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