Построение регистра правил на основе фактов

4 января 2005

Введение

Одной из актуальных задач систем анализа данных (Data Mining) является задача классификации. В общей постановке задача состоит в том, чтобы на основании некоторой таблицы фактов, в которой есть определяющая и зависимая часть, построить некий набор обобщающих правил. Данный набор должен позволять классифицировать новые факты (относить их к определенным классам).

Существующие подходы к решению данной задачи (классификационные правила, деревья решений, Naive Bayes и пр.) являются не вполне удовлетворительными. Их недостатки описаны в специальной литературе.

Мы предлагаем использовать для решения данной задачи концепцию регистров правил. Концепция регистров правил предлагает удобную терминологию. Набор независимых переменных называется Детерминантом. Зависимая переменная называется Корнем. Атрибуты детерминанта (переменные) называются измерениями (координатами). Атрибуты корня – ресурсами.

Описание алгоритма

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

Детерминант (независимые переменные)			Корень (зависимая переменная)
Д1	Д2	Д3
A	C	E	Нет
A	C	F	Да
A	D	E	Нет
B	C	E	Нет
B	C	F	Да

Требуется построить по данному набору фактов наиболее подходящий регистр правил. Данный регистр правил мы используем для ответа на вопрос: какому значению корня регистра наиболее соответствует значение входного вектора [A, D, F]? Другими словами, нам надо классифицировать вектор детерминанта [A, D, F].

Здесь мы приведем алгоритм построения однозначных правил, то есть таких, при которых значения корня не является множеством, а определено однозначно. Будем идти от простого к сложному, то есть от простых (одномерных) правил, к многомерным. Мерность правила определяется количеством определяющих измерений детерминанта. То есть, если для какого-либо правила в регистре значение корня определяется значением лишь одного измерения, то такое правило назовем одномерным, если значением 2-х измерений – двумерным и т.д. Очевидно, что чем больше количество определяющих измерений, тем сложнее правило.

Итак, для построения регистра правил на основе фактов мы последовательно должны выполнить следующие шаги:

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

В нашем примере имеем три таблицы одномерных сверток:

Д1	Корень	Мощ.		Д2	Корень	Мощ.		Д3	Корень	Мощ.
A	Да; Нет	3		C	Да; Нет	4		E	Нет	3
B	Да; Нет	2		D	Нет	1		F	Да	2

Итак, в регистр правил следует добавить второй кортеж из таблицы Д2 и оба кортежа из таблицы Д3:

Приоритет	Детерминант			Корень
	Д1	Д2	Д3
1		D		Нет
2			F	Да
3			E	Нет

1. После добавления одномерных правил мы ищем двумерные правила. Алгоритм тот же, только ключевые колонки для свертки определяются теперь парой измерений. Набор таких пар должен покрывать все возможные пары для измерений детерминанта. В нашем случае это пары Д1+Д2, Д1+Д3, Д2+Д3. После выборки из свернутых таблиц однозначных правил в регистр правил добавляются только те, которые не являются подмножеством уже присутствующих в нем одномерных правил.

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

1. И так далее до N-мерного правила, где N – количество измерений исходного детерминанта регистра фактов.

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

Кстати, в нашем примере, входному вектору [A, D, F] будет соответствовать корень «Да», поскольку его приоритет выше. Если бы приоритеты (мощность) правил были одинаковыми, то выбор правила определился бы расположением измерений детерминанта (чем левее, тем выше приоритет).

Пример построения

Рассмотрим более интересный пример построения регистра правил на основе фактов. Регистр фактов имеет вид:

Детерминант				Корень
Наблюдение	Температура	Влажность	Ветер	Игра
Солнце	Жарко	Высокая	Нет	Нет
Солнце	Жарко	Высокая	Есть	Нет
Облачность	Жарко	Высокая	Нет	Да
Дождь	Норма	Высокая	Нет	Да
Дождь	Холодно	Норма	Нет	Да
Дождь	Холодно	Норма	Есть	Нет
Облачность	Холодно	Норма	Есть	Да
Солнце	Норма	Высокая	Нет	Нет
Солнце	Холодно	Норма	Нет	Да
Дождь	Норма	Норма	Нет	Да
Солнце	Норма	Норма	Есть	Да
Облачность	Норма	Высокая	Есть	Да
Облачность	Жарко	Норма	Нет	Да
Дождь	Норма	Высокая	Есть	Нет

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

Наблюдение	Температура	Влажность	Ветер	Игра	Приор.	Мерность правила
Облачность				Да	4	Наблюдение
Солнце	Жарко			Нет	2	Наблюдение + Температура
Солнце	Холодно			Да	1
Солнце		Высокая		Нет	3	Наблюдение + Влажность
Солнце		Норма		Да	2
Дождь			Есть	Нет	2	Наблюдение + Ветер
Дождь			Нет	Да	3
	Жарко	Норма		Да	1	Температура + Влажность
	Норма	Норма		Да	2
	Жарко		Есть	Нет	1	Температура + Ветер
	Холодно		Нет	Да	2
		Норма	Нет	Да	4	Влажность + Ветер
Солнце	Норма		Есть	Да	1	Наблюдение + Температура + Ветер
Солнце	Норма		Нет	Нет	1

Как уже отмечалось, наиболее надежными правилами являются правила с наивысшим приоритетом, то есть такие, которые подтверждены наибольшим количеством фактов.

Определим, состоится ли игра при следующем значении вектора ситуации:

Наблюдение = Солнце; Температура = Холодно; Влажность = Высокая; Ветер = Есть.

Из регистра правил извлекаем следующие правила для данной ситуации:

Солнце	Холодно			Да	1
Солнце		Высокая		Нет	3

В соответствии с приоритетом игра, скорее всего, не состоится.

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

Регистр правил для зависимости корня «Влажность» от Детерминанта «Наблюдение+Температура+Ветер» имеет вид:

Наблюдение	Температура	Ветер	Влажность	Приор.	Мерность правила
	Холодно		Норма	4	Температура
Облачность	Норма		Высокая	1	Наблюдение + Температура
Солнце	Жарко		Высокая	2
	Жарко	Есть	Высокая	1	Температура + Ветер Наблюдение + Температура + Ветер
Дождь	Норма	Есть	Высокая	1
Солнце	Норма	Есть	Норма	1	Температура
Солнце	Норма	Нет	Высокая	1
	Холодно		Норма	1	Наблюдение + Температура
Облачность	Норма		Высокая	1

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

Вероятностный регистр правил

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

Например, для представленной выше таблицы фактов можно указать следующие вероятностные наборы правил для одномерных детерминантов («Наблюдение» и «Температура»):

Температура	Игра
	P(Да)	P(Нет)
Жарко	0.5	0.5
Норма	2/3	1/3
Холодно	0.75	0.25

Наблюдение	Игра
	P(Да)	P(Нет)
Дождь	0.6	0.4
Облачность	1
Солнце	0.4	0.6

Здесь P(х) – вероятность ресурса х. Вероятностные правила несут в себе информацию, которая отсутствует в однозначном регистре. Так, например, мы видим, что если нам известна только лишь температура (Холодно), то игра состоится с вероятностью 75%. На основании данных однозначного регистра правил такой информации получить нельзя.

Однозначный регистр правил удобен, когда нам известен полный состав входного вектора ситуации. Если же на входе часть координат неизвестна, то правильней является использование вероятностного регистра правил. В вероятностном регистре незаполненные значения измерений детерминанта означают не квантор «Для всех (любых) значений», а квантор «Неизвестно (неопределенно)».

При построении регистра правил на основе регистра фактов должна быть возможность задания порогов вероятности (как верхнего – наиболее вероятно, так и нижнего – наименее вероятно), при котором правило стоит добавлять в регистр. Однозначный регистр правил – это вероятностный регистр с верхним порогом 1. Можно также учитывать достоверность правила – общую мощность, чтобы различать вероятности 2/3 и 4/6. Последняя более достоверна.