Логические алгоритмы классификации как средство извлечения знаний

Пусть ϕ: X → {0, 1} — некоторый предикат, определённый на множестве объ-

ектов X. Говорят, что предикат ϕ выделяет или покрывает (cover) объект x, если

ϕ (x) = 1. Предикат называют закономерностью, если он выделяет достаточно много объектов какого-то одного класса c, и практически не выделяет объекты других

классов (более строгое определение будет дано ниже).

Особую ценность представляют закономерности, которые описываются простой

логической формулой. Их называют правилами (rules). Процесс поиска правил по выборке называют извлечением знаний из данных (knowledge discovery). К знаниям

предъявляется особое требование — они должны быть интерпретируемы, то есть

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

привыкли выражать свой житейский и профессиональный опыт.

Пример 1.1. (из области медицины). Решается вопрос о целесообразности хирургической операции. Закономерность: если возраст пациента выше 60 лет и ранее он

перенёс инфаркт, то операцию не делать — риск отрицательного исхода велик.

Пример 1.2. (из области банковской деятельности). Решается вопрос о выдаче

кредита. Закономерность: если заёмщик указал в анкете свой домашний телефон,

и его зарплата превышает $1000 в месяц, и сумма кредита не превышает $10 000,

то кредит можно выдать — риск невозврата мал.

Всякая закономерность классифицирует лишь некоторую часть объектов. Объединив определённое количество закономерностей в композицию, можно получить

алгоритм, способный классифицировать любые объекты. Логическими алгоритма-

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

• Каков критерий информативности, позволяющий называть предикаты законо-

мерностями?

• Как строить закономерности?

• Как строить алгоритмы классификации на основе закономерностей? Рассмат-

риваются наиболее распространённые типы логических алгоритмов: решающие

списки (§1.3), решающие деревья и леса (§1.4), голосование правил (§1.5), ал-

горитмы вычисления оценок (§1.6).

Напомним основные обозначения. Имеется пространство объектов X и конечное

множество имён классов Y = {1,..., M}. Целевая зависимость y^∗ : X → Y извест-

на только на объектах обучающей выборки X^ℓ = (xi, yi)^ℓ _i=1, y_i = y^∗ (x_i). Требуется

построить алгоритм классификации a: X → Y, аппроксимирующий y∗ на всём X.