Технологии интеллектуального анализа данных

Знания представляются и обрабатываются с помощью определенного формализма, т.е. формальной системы, содержащей средства представления знаний и процедуру вывода при решении задачи в этой системе |12|. При представлении знаний и работе с ними могут использоваться такие формализмы, как функциональный, основанный на Л-исчислении, логический — на исчислении предикатов первого порядка, объектный — на концепции абстрактных типов данных и агентский — на базе теории акторов. В практическом плане формализмы поддерживаются соответствующими языками программирования: функциональными, логическими, объектно- ориентированными и агентно-ориентированными.

Исчисление функций.

Теоретической моделью функционального формализма является Х-исчисление, разработанное А. Чёрчем в 1941 г. как средство описания свойств математических функций и эффективной их обработки. Все функциональные программы можно преобразовать в Х-выражения. Нотация A-исчисления особенно удобна для описания манипулирования функциями или как средство записи промежуточного кода при трансляции исходной программы.

^-Исчисление — исчисление безымянных функций. Оно включает нотацию для записи Х-выражений и набор правил преобразования этих выражений. Х-Выражение записывается как Хх.Е, где символ X читается как «функция от», а точка после переменной х — как «которая возвращает». Здесь х — связанная переменная абстракции, соответствующая понятию формального параметра в традиционной процедуре или функции. Выражение Е справа называется телом абстракции и подобно коду процедуры или функции описывает, что нужно сделать с параметром, поступившим на вход функции.

Например, Хх.Ху*{х+у)2 читается так: «функция от х> которая вызывает функцию от у и возвращает (х + у) • 2». Для вычисления A-выражений используются правила вывода, описывающие, как вычислить выражение.

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

(записывается символом —> с соответствующим знаком преобразования). Редуцируемое выражение называется редексом.

а-Преобразование — это переименование переменных таким образом, чтобы они имели разные 

имена. Конфликт имен возникает, когда в ^-выражении связанные и заменяемые переменные имеют одно имя, например в таком случае: Xx.(kx.x) (+Lr). Здесь до собственно редукции обязательно выполняется а-преобразование.

P-Преобразование выполняет собственно редукцию. При этом копируется тело абстракции Е с заменой всех вхождений связанной переменной на выражении аргумента. Редуцирование выражения упрощает тело абстракции. Как правило, в итоге остаются связанная переменная или только константы, например: ((Хх.Ху.+ху)7)8^>('ку.+7у)8^>+7 8.

^-Преобразование — это правило функциональной экстенсивности, основанное на том, что выражения Хх.Е и Е обозначают одну и ту же функцию при условии, что х— не свободная переменная в Е. Поэтому можно записать Хх.Е—>?, имея в виду, что, когда Хх.Е подвергается ^-преобразованию, оно редуцируется в Е.

5-Правило редуцирует константные ^-выражения. Константа в Л-исчис- лении самоопределена, т.е. ее преобразовывать нельзя. Преобразуются константные функции, например: (+7 8)—>15. Здесь имеется в виду, что (+7 8) путем 5-редукции преобразуется в константу 15.

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

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

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

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

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