- Алгоритмы извлечения знаний

Алгоритмы извлечения знаний

В настоящее время в мире накоплено огромное количество информации, однако в подавляющем числе случаев эффективность её использования крайне низка. Дело в том, что мало просто обладать информацией, нужно ещё понимать её смысл, уметь находить в ней скрытые зависимости, правильно её структурировать для более качественного анализа. Сегодня в мире разработана масса методов решения подобных задач, которые объединены в единое направление известное как Knowledge Discovery in Data Bases and Data Mining (KDD&DM).

Одним из наиболее популярных подходов к решению задач Data Mining являются деревья решений (decision trees). Они создают иерархическую структуру классифицирующих правил типа "ЕСЛИ... ТО..." (if-then), имеющую вид дерева. Для принятия решения, к какому классу отнести некоторый объект или ситуацию, требуется ответить на вопросы, стоящие в узлах этого дерева, начиная с его корня. Вопросы имеют вид "значение параметра A больше x?". Если ответ положительный, то осуществляется переход к правому узлу следующего уровня, если отрицательный - к левому узлу; затем снова следует вопрос, связанный с соответствующим узлом. Популярность подхода связана с наглядностью и понятностью, однако за это приходится расплачиваться качеством найденных закономерностей.

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

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

Наша группа при решении практических задач успешно применяет как широко известные методики, так и собственные инновационные разработки.

Инновации

Исследуя современные методы KDD&DM, мы столкнулись с тем, что многие из них носят аппроксимационный характер. Другими словами в них искомая зависимость представляется с помощью заранее заданного объекта: функции, дерева, решающего правила и т.д. Аппроксимируя искомую зависимость с требуемым уровнем точности, эти методы, решают по существу задачу предсказания. Найденная аппроксимация ничего не говорит об информационной структуре исследуемых данных.

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

«если A, B, C выполнено, то с вероятностью р выполнено D».

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

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

«если A, B, C выполнено, то с вероятностью р выполнено D».

Такая нейронная сеть способна не только решать все задачи обычных нейронных сетей, но и обосновывать свои решения логически.