Построение регистра правил на основе фактов — различия между версиями

Материал из КинтВики
Перейти к: навигация, поиск
Строка 1: Строка 1:
[[Категория:Регистры правил. Архив]]
+
[[Категория: Регистры правил. Архив]]
  
 
4 января 2005
 
4 января 2005
  
== Введение ==
+
==Введение==
 
Одной из актуальных задач систем анализа данных (Data Mining) является задача классификации. В общей постановке задача состоит в том, чтобы на основании некоторой таблицы фактов, в которой есть определяющая и зависимая часть, построить некий набор обобщающих правил. Данный набор должен позволять классифицировать новые факты (относить их к определенным классам).
 
Одной из актуальных задач систем анализа данных (Data Mining) является задача классификации. В общей постановке задача состоит в том, чтобы на основании некоторой таблицы фактов, в которой есть определяющая и зависимая часть, построить некий набор обобщающих правил. Данный набор должен позволять классифицировать новые факты (относить их к определенным классам).
  
 
Существующие подходы к решению данной задачи (классификационные правила, деревья решений, Naive Bayes и пр.) являются не вполне удовлетворительными. Их недостатки описаны в специальной литературе.
 
Существующие подходы к решению данной задачи (классификационные правила, деревья решений, Naive Bayes и пр.) являются не вполне удовлетворительными. Их недостатки описаны в специальной литературе.
  
Мы предлагаем использовать для решения данной задачи концепцию регистров правил. Концепция регистров правил предлагает удобную терминологию. Набор ''независимых переменных'' называется ''Детерминантом''. ''Зависимая переменная'' называется ''Корнем''. Атрибуты детерминанта (переменные) называются измерениями (координатами). Атрибуты корня — ресурсами.
+
Мы предлагаем использовать для решения данной задачи концепцию регистров правил. Концепция регистров правил предлагает удобную терминологию. Набор ''независимых переменных'' называется ''Детерминантом''. ''Зависимая переменная'' называется ''Корнем''. Атрибуты детерминанта (переменные) называются измерениями (координатами). Атрибуты корня – ресурсами.
  
== Описание алгоритма ==
+
==Описание алгоритма==
 
Рассмотрим постановку задачи на конкретном примере. Пусть имеем следующий регистр фактов:
 
Рассмотрим постановку задачи на конкретном примере. Пусть имеем следующий регистр фактов:
  
 
{|border="1" cellpadding="1" cellspacing="1"
 
{|border="1" cellpadding="1" cellspacing="1"
|align = «center» bgcolor = «#D9D9D9» colspan = «3»|'''Детерминант'''<br />'''(независимые переменные)'''
+
|align = "center" bgcolor = "#D9D9D9" colspan = "3"|'''Детерминант'''<br>'''(независимые переменные)'''
|align = «center» bgcolor = «#CCFFCC» rowspan = «2»|'''Корень'''<br />'''(зависимая переменная)'''
+
|align = "center" bgcolor = "#CCFFCC" rowspan = "2"|'''Корень'''<br>'''(зависимая переменная)'''
  
 
|-
 
|-
|align = «center» bgcolor = «#E0E0E0»|'''Д1'''
+
|align = "center" bgcolor = "#E0E0E0"|'''Д1'''
|align = «center» bgcolor = «#E0E0E0»|'''Д2'''
+
|align = "center" bgcolor = "#E0E0E0"|'''Д2'''
|align = «center» bgcolor = «#E0E0E0»|'''Д3'''
+
|align = "center" bgcolor = "#E0E0E0"|'''Д3'''
  
 
|-
 
|-
|align = «center»|A
+
|align = "center"|A
|align = «center»|C
+
|align = "center"|C
|align = «center»|E
+
|align = "center"|E
|align = «center» bgcolor = «#CCFFCC»|Нет
+
|align = "center" bgcolor = "#CCFFCC"|Нет
  
 
|-
 
|-
|align = «center»|A
+
|align = "center"|A
|align = «center»|C
+
|align = "center"|C
|align = «center»|F
+
|align = "center"|F
|align = «center» bgcolor = «#CCFFCC»|Да
+
|align = "center" bgcolor = "#CCFFCC"|Да
  
 
|-
 
|-
|align = «center»|A
+
|align = "center"|A
|align = «center»|D
+
|align = "center"|D
|align = «center»|E
+
|align = "center"|E
|align = «center» bgcolor = «#CCFFCC»|Нет
+
|align = "center" bgcolor = "#CCFFCC"|Нет
  
 
|-
 
|-
|align = «center»|B
+
|align = "center"|B
|align = «center»|C
+
|align = "center"|C
|align = «center»|E
+
|align = "center"|E
|align = «center» bgcolor = «#CCFFCC»|Нет
+
|align = "center" bgcolor = "#CCFFCC"|Нет
  
 
|-
 
|-
|align = «center»|B
+
|align = "center"|B
|align = «center»|C
+
|align = "center"|C
|align = «center»|F
+
|align = "center"|F
|align = «center» bgcolor = «#CCFFCC»|Да
+
|align = "center" bgcolor = "#CCFFCC"|Да
  
 
|}
 
|}
Строка 57: Строка 57:
 
Требуется построить по данному набору фактов ''наиболее подходящий'' регистр правил. Данный регистр правил мы используем для ответа на вопрос: какому значению корня регистра наиболее соответствует значение входного вектора [A, D, F]? Другими словами, нам надо классифицировать вектор детерминанта [A, D, F].
 
Требуется построить по данному набору фактов ''наиболее подходящий'' регистр правил. Данный регистр правил мы используем для ответа на вопрос: какому значению корня регистра наиболее соответствует значение входного вектора [A, D, F]? Другими словами, нам надо классифицировать вектор детерминанта [A, D, F].
  
Здесь мы приведем алгоритм построения ''однозначных правил'', то есть таких, при которых значения корня не является множеством, а определено однозначно. Будем идти от простого к сложному, то есть от простых (одномерных) правил, к многомерным. Мерность правила определяется количеством ''определяющих'' измерений детерминанта. То есть, если для какого-либо правила в регистре значение корня определяется значением лишь одного измерения, то такое правило назовем одномерным, если значением 2-х измерений — двумерным и т. д. Очевидно, что чем больше количество определяющих измерений, тем сложнее правило.
+
Здесь мы приведем алгоритм построения ''однозначных правил'', то есть таких, при которых значения корня не является множеством, а определено однозначно. Будем идти от простого к сложному, то есть от простых (одномерных) правил, к многомерным. Мерность правила определяется количеством ''определяющих'' измерений детерминанта. То есть, если для какого-либо правила в регистре значение корня определяется значением лишь одного измерения, то такое правило назовем одномерным, если значением 2-х измерений – двумерным и т.д. Очевидно, что чем больше количество определяющих измерений, тем сложнее правило.
  
 
Итак, для построения регистра правил на основе фактов мы последовательно должны выполнить следующие шаги:
 
Итак, для построения регистра правил на основе фактов мы последовательно должны выполнить следующие шаги:
Строка 66: Строка 66:
  
 
{|border="1" cellspacing="1" cellpadding="2"
 
{|border="1" cellspacing="1" cellpadding="2"
|align = «center» bgcolor = «#E0E0E0»|'''Д1'''
+
|align = "center" bgcolor = "#E0E0E0"|'''Д1'''
|align = «center» bgcolor = «#CCFFCC»|'''Корень'''
+
|align = "center" bgcolor = "#CCFFCC"|'''Корень'''
|align = «center»|'''Мощ.'''
+
|align = "center"|'''Мощ.'''
|align = «center»|&nbsp;
+
|align = "center"|&nbsp;
|align = «center» bgcolor = «#E0E0E0»|'''Д2'''
+
|align = "center" bgcolor = "#E0E0E0"|'''Д2'''
|align = «center» bgcolor = «#CCFFCC»|'''Корень'''
+
|align = "center" bgcolor = "#CCFFCC"|'''Корень'''
|align = «center»|'''Мощ.'''
+
|align = "center"|'''Мощ.'''
|align = «center»|&nbsp;
+
|align = "center"|&nbsp;
|align = «center» bgcolor = «#E0E0E0»|'''Д3'''
+
|align = "center" bgcolor = "#E0E0E0"|'''Д3'''
|align = «center» bgcolor = «#CCFFCC»|'''Корень'''
+
|align = "center" bgcolor = "#CCFFCC"|'''Корень'''
|align = «center»|'''Мощ.'''
+
|align = "center"|'''Мощ.'''
  
 
|-
 
|-
|align = «center»|A
+
|align = "center"|A
|align = «center» bgcolor = «#CCFFCC»|Да; Нет
+
|align = "center" bgcolor = "#CCFFCC"|Да; Нет
|align = «center»|3
+
|align = "center"|3
|align = «center»|&nbsp;
+
|align = "center"|&nbsp;
|align = «center»|C
+
|align = "center"|C
|align = «center» bgcolor = «#CCFFCC»|Да; Нет
+
|align = "center" bgcolor = "#CCFFCC"|Да; Нет
|align = «center»|4
+
|align = "center"|4
|align = «center»|&nbsp;
+
|align = "center"|&nbsp;
|align = «center»|E
+
|align = "center"|E
|align = «center» bgcolor = «#CCFFCC»|Нет
+
|align = "center" bgcolor = "#CCFFCC"|Нет
|align = «center»|3
+
|align = "center"|3
  
 
|-
 
|-
|align = «center»|B
+
|align = "center"|B
|align = «center» bgcolor = «#CCFFCC»|Да; Нет
+
|align = "center" bgcolor = "#CCFFCC"|Да; Нет
|align = «center»|2
+
|align = "center"|2
|align = «center»|&nbsp;
+
|align = "center"|&nbsp;
|align = «center»|D
+
|align = "center"|D
|align = «center» bgcolor = «#CCFFCC»|Нет
+
|align = "center" bgcolor = "#CCFFCC"|Нет
|align = «center»|1
+
|align = "center"|1
|align = «center»|&nbsp;
+
|align = "center"|&nbsp;
|align = «center»|F
+
|align = "center"|F
|align = «center» bgcolor = «#CCFFCC»|Да
+
|align = "center" bgcolor = "#CCFFCC"|Да
|align = «center»|2
+
|align = "center"|2
  
 
|}
 
|}
Строка 110: Строка 110:
  
 
{|border="1" cellspacing="1" cellpadding="2"
 
{|border="1" cellspacing="1" cellpadding="2"
|align = «center» bgcolor = «#D9D9D9» rowspan = «2»|'''Приоритет'''
+
|align = "center" bgcolor = "#D9D9D9" rowspan = "2"|'''Приоритет'''
|align = «center» bgcolor = «#D9D9D9» colspan = «3»|'''Детерминант '''
+
|align = "center" bgcolor = "#D9D9D9" colspan = "3"|'''Детерминант '''
|align = «center» bgcolor = «#CCFFCC» rowspan = «2»|'''Корень '''
+
|align = "center" bgcolor = "#CCFFCC" rowspan = "2"|'''Корень '''
  
 
|-
 
|-
|align = «center» bgcolor = «#E0E0E0»|'''Д1'''
+
|align = "center" bgcolor = "#E0E0E0"|'''Д1'''
|align = «center» bgcolor = «#E0E0E0»|'''Д2'''
+
|align = "center" bgcolor = "#E0E0E0"|'''Д2'''
|align = «center» bgcolor = «#E0E0E0»|'''Д3'''
+
|align = "center" bgcolor = "#E0E0E0"|'''Д3'''
  
 
|-
 
|-
|align = «center»|1
+
|align = "center"|1
|align = «center»|&nbsp;
+
|align = "center"|&nbsp;
|align = «center»|D
+
|align = "center"|D
|align = «center»|&nbsp;
+
|align = "center"|&nbsp;
|align = «center» bgcolor = «#CCFFCC»|Нет
+
|align = "center" bgcolor = "#CCFFCC"|Нет
  
 
|-
 
|-
|align = «center»|2
+
|align = "center"|2
|align = «center»|&nbsp;
+
|align = "center"|&nbsp;
|align = «center»|&nbsp;
+
|align = "center"|&nbsp;
|align = «center»|F
+
|align = "center"|F
|align = «center» bgcolor = «#CCFFCC»|Да
+
|align = "center" bgcolor = "#CCFFCC"|Да
  
 
|-
 
|-
|align = «center»|3
+
|align = "center"|3
|align = «center»|&nbsp;
+
|align = "center"|&nbsp;
|align = «center»|&nbsp;
+
|align = "center"|&nbsp;
|align = «center»|E
+
|align = "center"|E
|align = «center» bgcolor = «#CCFFCC»|Нет
+
|align = "center" bgcolor = "#CCFFCC"|Нет
  
 
|}
 
|}
Строка 144: Строка 144:
  
 
# После добавления одномерных правил мы ищем двумерные правила. Алгоритм тот же, только ключевые колонки для свертки определяются теперь парой измерений. Набор таких пар должен покрывать все возможные пары для измерений детерминанта. В нашем случае это пары Д1+Д2, Д1+Д3, Д2+Д3. После выборки из свернутых таблиц однозначных правил в регистр правил добавляются только те, которые не являются подмножеством уже присутствующих в нем одномерных правил.
 
# После добавления одномерных правил мы ищем двумерные правила. Алгоритм тот же, только ключевые колонки для свертки определяются теперь парой измерений. Набор таких пар должен покрывать все возможные пары для измерений детерминанта. В нашем случае это пары Д1+Д2, Д1+Д3, Д2+Д3. После выборки из свернутых таблиц однозначных правил в регистр правил добавляются только те, которые не являются подмножеством уже присутствующих в нем одномерных правил.
В нашем примере все двумерные правила (и трехмерные тоже) являются подмножеством одномерных правил по Д3. Это является следствием того, что набор одномерных правил по Д3 покрыл весь диапазон (все пространство) значений измерения Д3.
+
В нашем примере все двумерные правила (и трехмерные тоже) являются подмножеством одномерных правил по Д3. Это является следствием того, что набор одномерных правил по Д3 покрыл весь диапазон (все пространство) значений измерения Д3.
  
# И так далее до N-мерного правила, где N — количество измерений исходного детерминанта регистра фактов.
+
# И так далее до N-мерного правила, где N – количество измерений исходного детерминанта регистра фактов.
  
 
Построенный регистр правил позволяет помимо решения задач классификации выявить некие общие закономерности представленных фактов. Кроме того, описанный алгоритм можно применить для анализа взаимосвязанности измерений детерминанта.
 
Построенный регистр правил позволяет помимо решения задач классификации выявить некие общие закономерности представленных фактов. Кроме того, описанный алгоритм можно применить для анализа взаимосвязанности измерений детерминанта.
Строка 152: Строка 152:
 
Кстати, в нашем примере, входному вектору [A, D, F] будет соответствовать корень «Да», поскольку его приоритет выше. Если бы приоритеты (мощность) правил были одинаковыми, то выбор правила определился бы расположением измерений детерминанта (чем левее, тем выше приоритет).
 
Кстати, в нашем примере, входному вектору [A, D, F] будет соответствовать корень «Да», поскольку его приоритет выше. Если бы приоритеты (мощность) правил были одинаковыми, то выбор правила определился бы расположением измерений детерминанта (чем левее, тем выше приоритет).
  
== Пример построения ==
+
==Пример построения==
 
Рассмотрим более интересный пример построения регистра правил на основе фактов. Регистр фактов имеет вид:
 
Рассмотрим более интересный пример построения регистра правил на основе фактов. Регистр фактов имеет вид:
  
 
{|border="1" cellspacing="1" cellpadding="2"
 
{|border="1" cellspacing="1" cellpadding="2"
|align = «center» bgcolor = «#E0E0E0» colspan = «4»|'''Детерминант'''
+
|align = "center" bgcolor = "#E0E0E0" colspan = "4"|'''Детерминант'''
|align = «center» bgcolor = «#CCFFCC»|'''Корень'''
+
|align = "center" bgcolor = "#CCFFCC"|'''Корень'''
  
 
|-
 
|-
|align = «center» bgcolor = «#E0E0E0»|'''Наблюдение'''
+
|align = "center" bgcolor = "#E0E0E0"|'''Наблюдение'''
|align = «center» bgcolor = «#E0E0E0»|'''Температура'''
+
|align = "center" bgcolor = "#E0E0E0"|'''Температура'''
|align = «center» bgcolor = «#E0E0E0»|'''Влажность'''
+
|align = "center" bgcolor = "#E0E0E0"|'''Влажность'''
|align = «center» bgcolor = «#E0E0E0»|'''Ветер'''
+
|align = "center" bgcolor = "#E0E0E0"|'''Ветер'''
|align = «center» bgcolor = «#CCFFCC»|'''Игра'''
+
|align = "center" bgcolor = "#CCFFCC"|'''Игра'''
  
 
|-
 
|-
Строка 171: Строка 171:
 
|Высокая
 
|Высокая
 
|Нет
 
|Нет
|bgcolor = «#CCFFCC»|Нет
+
|bgcolor = "#CCFFCC"|Нет
  
 
|-
 
|-
Строка 178: Строка 178:
 
|Высокая
 
|Высокая
 
|Есть
 
|Есть
|bgcolor = «#CCFFCC»|Нет
+
|bgcolor = "#CCFFCC"|Нет
  
 
|-
 
|-
Строка 185: Строка 185:
 
|Высокая
 
|Высокая
 
|Нет
 
|Нет
|bgcolor = «#CCFFCC»|Да
+
|bgcolor = "#CCFFCC"|Да
  
 
|-
 
|-
Строка 192: Строка 192:
 
|Высокая
 
|Высокая
 
|Нет
 
|Нет
|bgcolor = «#CCFFCC»|Да
+
|bgcolor = "#CCFFCC"|Да
  
 
|-
 
|-
Строка 199: Строка 199:
 
|Норма
 
|Норма
 
|Нет
 
|Нет
|bgcolor = «#CCFFCC»|Да
+
|bgcolor = "#CCFFCC"|Да
  
 
|-
 
|-
Строка 206: Строка 206:
 
|Норма
 
|Норма
 
|Есть
 
|Есть
|bgcolor = «#CCFFCC»|Нет
+
|bgcolor = "#CCFFCC"|Нет
  
 
|-
 
|-
Строка 213: Строка 213:
 
|Норма
 
|Норма
 
|Есть
 
|Есть
|bgcolor = «#CCFFCC»|Да
+
|bgcolor = "#CCFFCC"|Да
  
 
|-
 
|-
Строка 220: Строка 220:
 
|Высокая
 
|Высокая
 
|Нет
 
|Нет
|bgcolor = «#CCFFCC»|Нет
+
|bgcolor = "#CCFFCC"|Нет
  
 
|-
 
|-
Строка 227: Строка 227:
 
|Норма
 
|Норма
 
|Нет
 
|Нет
|bgcolor = «#CCFFCC»|Да
+
|bgcolor = "#CCFFCC"|Да
  
 
|-
 
|-
Строка 234: Строка 234:
 
|Норма
 
|Норма
 
|Нет
 
|Нет
|bgcolor = «#CCFFCC»|Да
+
|bgcolor = "#CCFFCC"|Да
  
 
|-
 
|-
Строка 241: Строка 241:
 
|Норма
 
|Норма
 
|Есть
 
|Есть
|bgcolor = «#CCFFCC»|Да
+
|bgcolor = "#CCFFCC"|Да
  
 
|-
 
|-
Строка 248: Строка 248:
 
|Высокая
 
|Высокая
 
|Есть
 
|Есть
|bgcolor = «#CCFFCC»|Да
+
|bgcolor = "#CCFFCC"|Да
  
 
|-
 
|-
Строка 255: Строка 255:
 
|Норма
 
|Норма
 
|Нет
 
|Нет
|bgcolor = «#CCFFCC»|Да
+
|bgcolor = "#CCFFCC"|Да
  
 
|-
 
|-
Строка 262: Строка 262:
 
|Высокая
 
|Высокая
 
|Есть
 
|Есть
|bgcolor = «#CCFFCC»|Нет
+
|bgcolor = "#CCFFCC"|Нет
  
 
|}
 
|}
Строка 270: Строка 270:
  
 
{|border="1" cellspacing="1" cellpadding="2"
 
{|border="1" cellspacing="1" cellpadding="2"
|align = «center» bgcolor = «#E0E0E0»|'''Наблюдение'''
+
|align = "center" bgcolor = "#E0E0E0"|'''Наблюдение'''
|align = «center» bgcolor = «#E0E0E0»|'''Температура'''
+
|align = "center" bgcolor = "#E0E0E0"|'''Температура'''
|align = «center» bgcolor = «#E0E0E0»|'''Влажность'''
+
|align = "center" bgcolor = "#E0E0E0"|'''Влажность'''
|align = «center» bgcolor = «#E0E0E0»|'''Ветер'''
+
|align = "center" bgcolor = "#E0E0E0"|'''Ветер'''
|align = «center» bgcolor = «#CCFFCC»|'''Игра'''
+
|align = "center" bgcolor = "#CCFFCC"|'''Игра'''
|align = «center»|'''Приор.'''
+
|align = "center"|'''Приор.'''
|align = «center»|'''Мерность правила'''
+
|align = "center"|'''Мерность правила'''
  
 
|-
 
|-
Строка 283: Строка 283:
 
|&nbsp;
 
|&nbsp;
 
|&nbsp;
 
|&nbsp;
|bgcolor = «#CCFFCC»|Да
+
|bgcolor = "#CCFFCC"|Да
|align = «right»|4
+
|align = "right"|4
 
|Наблюдение
 
|Наблюдение
  
Строка 292: Строка 292:
 
|&nbsp;
 
|&nbsp;
 
|&nbsp;
 
|&nbsp;
|bgcolor = «#CCFFCC»|Нет
+
|bgcolor = "#CCFFCC"|Нет
|align = «right»|2
+
|align = "right"|2
|rowspan = «2»|Наблюдение + Температура
+
|rowspan = "2"|Наблюдение + Температура
  
 
|-
 
|-
Строка 301: Строка 301:
 
|&nbsp;
 
|&nbsp;
 
|&nbsp;
 
|&nbsp;
|bgcolor = «#CCFFCC»|Да
+
|bgcolor = "#CCFFCC"|Да
|align = «right»|1
+
|align = "right"|1
  
 
|-
 
|-
Строка 309: Строка 309:
 
|Высокая
 
|Высокая
 
|&nbsp;
 
|&nbsp;
|bgcolor = «#CCFFCC»|Нет
+
|bgcolor = "#CCFFCC"|Нет
|align = «right»|3
+
|align = "right"|3
|rowspan = «2»|Наблюдение + Влажность
+
|rowspan = "2"|Наблюдение + Влажность
  
 
|-
 
|-
Строка 318: Строка 318:
 
|Норма
 
|Норма
 
|&nbsp;
 
|&nbsp;
|bgcolor = «#CCFFCC»|Да
+
|bgcolor = "#CCFFCC"|Да
|align = «right»|2
+
|align = "right"|2
  
 
|-
 
|-
Строка 326: Строка 326:
 
|&nbsp;
 
|&nbsp;
 
|Есть
 
|Есть
|bgcolor = «#CCFFCC»|Нет
+
|bgcolor = "#CCFFCC"|Нет
|align = «right»|2
+
|align = "right"|2
|rowspan = «2»|Наблюдение + Ветер
+
|rowspan = "2"|Наблюдение + Ветер
  
 
|-
 
|-
Строка 335: Строка 335:
 
|&nbsp;
 
|&nbsp;
 
|Нет
 
|Нет
|bgcolor = «#CCFFCC»|Да
+
|bgcolor = "#CCFFCC"|Да
|align = «right»|3
+
|align = "right"|3
  
 
|-
 
|-
Строка 343: Строка 343:
 
|Норма
 
|Норма
 
|&nbsp;
 
|&nbsp;
|bgcolor = «#CCFFCC»|Да
+
|bgcolor = "#CCFFCC"|Да
|align = «right»|1
+
|align = "right"|1
|rowspan = «2»|Температура + Влажность
+
|rowspan = "2"|Температура + Влажность
  
 
|-
 
|-
Строка 352: Строка 352:
 
|Норма
 
|Норма
 
|&nbsp;
 
|&nbsp;
|bgcolor = «#CCFFCC»|Да
+
|bgcolor = "#CCFFCC"|Да
|align = «right»|2
+
|align = "right"|2
  
 
|-
 
|-
Строка 360: Строка 360:
 
|&nbsp;
 
|&nbsp;
 
|Есть
 
|Есть
|bgcolor = «#CCFFCC»|Нет
+
|bgcolor = "#CCFFCC"|Нет
|align = «right»|1
+
|align = "right"|1
|rowspan = «2»|Температура + Ветер
+
|rowspan = "2"|Температура + Ветер
  
 
|-
 
|-
Строка 369: Строка 369:
 
|&nbsp;
 
|&nbsp;
 
|Нет
 
|Нет
|bgcolor = «#CCFFCC»|Да
+
|bgcolor = "#CCFFCC"|Да
|align = «right»|2
+
|align = "right"|2
  
 
|-
 
|-
Строка 377: Строка 377:
 
|Норма
 
|Норма
 
|Нет
 
|Нет
|bgcolor = «#CCFFCC»|Да
+
|bgcolor = "#CCFFCC"|Да
|align = «right»|4
+
|align = "right"|4
 
|Влажность + Ветер
 
|Влажность + Ветер
  
Строка 386: Строка 386:
 
|&nbsp;
 
|&nbsp;
 
|Есть
 
|Есть
|bgcolor = «#CCFFCC»|Да
+
|bgcolor = "#CCFFCC"|Да
|align = «right»|1
+
|align = "right"|1
|rowspan = «2»|Наблюдение + Температура + Ветер
+
|rowspan = "2"|Наблюдение + Температура + Ветер
  
 
|-
 
|-
Строка 395: Строка 395:
 
|&nbsp;
 
|&nbsp;
 
|Нет
 
|Нет
|bgcolor = «#CCFFCC»|Нет
+
|bgcolor = "#CCFFCC"|Нет
|align = «right»|1
+
|align = "right"|1
  
 
|}
 
|}
Строка 414: Строка 414:
 
|&nbsp;
 
|&nbsp;
 
|&nbsp;
 
|&nbsp;
|bgcolor = «#CCFFCC»|Да
+
|bgcolor = "#CCFFCC"|Да
|align = «right»|1
+
|align = "right"|1
  
 
|-
 
|-
Строка 422: Строка 422:
 
|Высокая
 
|Высокая
 
|&nbsp;
 
|&nbsp;
|bgcolor = «#CCFFCC»|Нет
+
|bgcolor = "#CCFFCC"|Нет
|align = «right»|3
+
|align = "right"|3
  
 
|}
 
|}
Строка 435: Строка 435:
  
 
{|border="1" cellspacing="1" cellpadding="2"
 
{|border="1" cellspacing="1" cellpadding="2"
|align = «center» bgcolor = «#E0E0E0»|'''Наблюдение'''
+
|align = "center" bgcolor = "#E0E0E0"|'''Наблюдение'''
|align = «center» bgcolor = «#E0E0E0»|'''Температура'''
+
|align = "center" bgcolor = "#E0E0E0"|'''Температура'''
|align = «center» bgcolor = «#E0E0E0»|'''Ветер'''
+
|align = "center" bgcolor = "#E0E0E0"|'''Ветер'''
|align = «center» bgcolor = «#CCFFCC»|'''Влажность'''
+
|align = "center" bgcolor = "#CCFFCC"|'''Влажность'''
|align = «center»|'''Приор.'''
+
|align = "center"|'''Приор.'''
|align = «center»|'''Мерность правила'''
+
|align = "center"|'''Мерность правила'''
  
 
|-
 
|-
Строка 446: Строка 446:
 
|Холодно
 
|Холодно
 
|&nbsp;
 
|&nbsp;
|bgcolor = «#CCFFCC»|Норма
+
|bgcolor = "#CCFFCC"|Норма
|align = «right»|4
+
|align = "right"|4
 
|Температура
 
|Температура
  
Строка 454: Строка 454:
 
|Норма
 
|Норма
 
|&nbsp;
 
|&nbsp;
|bgcolor = «#CCFFCC»|Высокая
+
|bgcolor = "#CCFFCC"|Высокая
|align = «right»|1
+
|align = "right"|1
|rowspan = «2»|Наблюдение + Температура<br />
+
|rowspan = "2"|Наблюдение + Температура<br>
  
 
|-
 
|-
Строка 462: Строка 462:
 
|Жарко
 
|Жарко
 
|&nbsp;
 
|&nbsp;
|bgcolor = «#CCFFCC»|Высокая
+
|bgcolor = "#CCFFCC"|Высокая
|align = «right»|2
+
|align = "right"|2
  
 
|-
 
|-
Строка 469: Строка 469:
 
|Жарко
 
|Жарко
 
|Есть
 
|Есть
|bgcolor = «#CCFFCC»|Высокая
+
|bgcolor = "#CCFFCC"|Высокая
|align = «right»|1
+
|align = "right"|1
|rowspan = «2»|Температура + Ветер<br />Наблюдение + Температура + Ветер
+
|rowspan = "2"|Температура + Ветер<br>Наблюдение + Температура + Ветер
  
 
|-
 
|-
Строка 477: Строка 477:
 
|Норма
 
|Норма
 
|Есть
 
|Есть
|bgcolor = «#CCFFCC»|Высокая
+
|bgcolor = "#CCFFCC"|Высокая
|align = «right»|1
+
|align = "right"|1
  
 
|-
 
|-
Строка 484: Строка 484:
 
|Норма
 
|Норма
 
|Есть
 
|Есть
|bgcolor = «#CCFFCC»|Норма
+
|bgcolor = "#CCFFCC"|Норма
|align = «right»|1
+
|align = "right"|1
|rowspan = «2»|<br />Температура
+
|rowspan = "2"|<br>Температура
  
 
|-
 
|-
Строка 492: Строка 492:
 
|Норма
 
|Норма
 
|Нет
 
|Нет
|bgcolor = «#CCFFCC»|Высокая
+
|bgcolor = "#CCFFCC"|Высокая
|align = «right»|1
+
|align = "right"|1
  
 
|-
 
|-
Строка 499: Строка 499:
 
|Холодно
 
|Холодно
 
|&nbsp;
 
|&nbsp;
|bgcolor = «#CCFFCC»|Норма
+
|bgcolor = "#CCFFCC"|Норма
|align = «right»|1
+
|align = "right"|1
|rowspan = «2»|Наблюдение <nowiki>+</nowiki> Температура
+
|rowspan = "2"|Наблюдение <nowiki>+</nowiki> Температура
  
 
|-
 
|-
Строка 507: Строка 507:
 
|Норма
 
|Норма
 
|&nbsp;
 
|&nbsp;
|bgcolor = «#CCFFCC»|Высокая
+
|bgcolor = "#CCFFCC"|Высокая
|align = «right»|1
+
|align = "right"|1
  
 
|}
 
|}
Строка 515: Строка 515:
 
Из данного регистра видно, что если температура холодная, то влажность должна быть в норме. Если данный инвариант не выполняется для данных входного вектора, значения данных подозрительны.
 
Из данного регистра видно, что если температура холодная, то влажность должна быть в норме. Если данный инвариант не выполняется для данных входного вектора, значения данных подозрительны.
  
== Вероятностный регистр правил ==
+
==Вероятностный регистр правил==
Корни регистра могут иметь вероятностный характер, поскольку правила (и факты) не всегда можно выразить однозначно. Однозначный корень (ресурс) — это частный случай многозначного, когда вероятность одного из значений корня равна 1. В общем случае корень может представлять собой список (таблицу) значений, где каждому значению присвоен определенный вес. Сумма всех весов — 1.
+
Корни регистра могут иметь вероятностный характер, поскольку правила (и факты) не всегда можно выразить однозначно. Однозначный корень (ресурс) это частный случай многозначного, когда вероятность одного из значений корня равна 1. В общем случае корень может представлять собой список (таблицу) значений, где каждому значению присвоен определенный вес. Сумма всех весов – 1.
  
 
Например, для представленной выше таблицы фактов можно указать следующие вероятностные наборы правил для одномерных детерминантов («Наблюдение» и «Температура»):
 
Например, для представленной выше таблицы фактов можно указать следующие вероятностные наборы правил для одномерных детерминантов («Наблюдение» и «Температура»):
  
 
{|border="1" cellspacing="1" cellpadding="2" align="left"
 
{|border="1" cellspacing="1" cellpadding="2" align="left"
|align = «center» bgcolor = «#E0E0E0» rowspan = «2»|'''Температура'''
+
|align = "center" bgcolor = "#E0E0E0" rowspan = "2"|'''Температура'''
|align = «center» bgcolor = «#CCFFCC» colspan = «2»|'''Игра'''
+
|align = "center" bgcolor = "#CCFFCC" colspan = "2"|'''Игра'''
  
 
|-
 
|-
|align = «center» bgcolor = «#CCFFCC»|'''P(Да)'''
+
|align = "center" bgcolor = "#CCFFCC"|'''P(Да)'''
|align = «center» bgcolor = «#CCFFCC»|'''P(Нет)'''
+
|align = "center" bgcolor = "#CCFFCC"|'''P(Нет)'''
  
 
|-
 
|-
 
|Жарко
 
|Жарко
|align = «right» bgcolor = «#CCFFCC»|0.5
+
|align = "right" bgcolor = "#CCFFCC"|0.5
|align = «right» bgcolor = «#CCFFCC»|0.5
+
|align = "right" bgcolor = "#CCFFCC"|0.5
  
 
|-
 
|-
 
|Норма
 
|Норма
|align = «right» bgcolor = «#CCFFCC»|2/3
+
|align = "right" bgcolor = "#CCFFCC"|2/3
|align = «right» bgcolor = «#CCFFCC»|1/3
+
|align = "right" bgcolor = "#CCFFCC"|1/3
  
 
|-
 
|-
 
|Холодно
 
|Холодно
|align = «right» bgcolor = «#CCFFCC»|0.75
+
|align = "right" bgcolor = "#CCFFCC"|0.75
|align = «right» bgcolor = «#CCFFCC»|0.25
+
|align = "right" bgcolor = "#CCFFCC"|0.25
  
|}<br clear="all" />
+
|}<br clear="all">
  
  
 
{|border="1" cellspacing="1" cellpadding="2" align="left"
 
{|border="1" cellspacing="1" cellpadding="2" align="left"
|align = «center» bgcolor = «#E0E0E0» rowspan = «2»|'''Наблюдение'''
+
|align = "center" bgcolor = "#E0E0E0" rowspan = "2"|'''Наблюдение'''
|align = «center» bgcolor = «#CCFFCC» colspan = «2»|'''Игра'''
+
|align = "center" bgcolor = "#CCFFCC" colspan = "2"|'''Игра'''
  
 
|-
 
|-
|align = «center» bgcolor = «#CCFFCC»|'''P(Да)'''
+
|align = "center" bgcolor = "#CCFFCC"|'''P(Да)'''
|align = «center» bgcolor = «#CCFFCC»|'''P(Нет)'''
+
|align = "center" bgcolor = "#CCFFCC"|'''P(Нет)'''
  
 
|-
 
|-
 
|Дождь
 
|Дождь
|align = «right» bgcolor = «#CCFFCC»|0.6
+
|align = "right" bgcolor = "#CCFFCC"|0.6
|align = «right» bgcolor = «#CCFFCC»|0.4
+
|align = "right" bgcolor = "#CCFFCC"|0.4
  
 
|-
 
|-
 
|Облачность
 
|Облачность
|align = «right» bgcolor = «#CCFFCC»|1
+
|align = "right" bgcolor = "#CCFFCC"|1
|align = «right» bgcolor = «#CCFFCC»|&nbsp;
+
|align = "right" bgcolor = "#CCFFCC"|&nbsp;
  
 
|-
 
|-
 
|Солнце
 
|Солнце
|align = «right» bgcolor = «#CCFFCC»|0.4
+
|align = "right" bgcolor = "#CCFFCC"|0.4
|align = «right» bgcolor = «#CCFFCC»|0.6
+
|align = "right" bgcolor = "#CCFFCC"|0.6
  
|}<br clear="all" />
+
|}<br clear="all">
  
  
Здесь P(х) — вероятность ресурса х. Вероятностные правила несут в себе информацию, которая отсутствует в однозначном регистре. Так, например, мы видим, что если нам известна только лишь температура (Холодно), то игра состоится с вероятностью 75 %. На основании данных однозначного регистра правил такой информации получить нельзя.
+
Здесь P(х) вероятность ресурса х. Вероятностные правила несут в себе информацию, которая отсутствует в однозначном регистре. Так, например, мы видим, что если нам известна только лишь температура (Холодно), то игра состоится с вероятностью 75%. На основании данных однозначного регистра правил такой информации получить нельзя.
  
 
Однозначный регистр правил удобен, когда нам известен полный состав входного вектора ситуации. Если же на входе часть координат неизвестна, то правильней является использование вероятностного регистра правил. В вероятностном регистре незаполненные значения измерений детерминанта означают не квантор «Для всех (любых) значений», а квантор «Неизвестно (неопределенно)».
 
Однозначный регистр правил удобен, когда нам известен полный состав входного вектора ситуации. Если же на входе часть координат неизвестна, то правильней является использование вероятностного регистра правил. В вероятностном регистре незаполненные значения измерений детерминанта означают не квантор «Для всех (любых) значений», а квантор «Неизвестно (неопределенно)».
  
При построении регистра правил на основе регистра фактов должна быть возможность задания порогов вероятности (как верхнего — наиболее вероятно, так и нижнего — наименее вероятно), при котором правило стоит добавлять в регистр. Однозначный регистр правил — это вероятностный регистр с верхним порогом 1. Можно также учитывать ''достоверность'' правила — общую мощность, чтобы различать вероятности 2/3 и 4/6. Последняя более достоверна.
+
При построении регистра правил на основе регистра фактов должна быть возможность задания порогов вероятности (как верхнего – наиболее вероятно, так и нижнего – наименее вероятно), при котором правило стоит добавлять в регистр. Однозначный регистр правил – это вероятностный регистр с верхним порогом 1. Можно также учитывать ''достоверность'' правила – общую мощность, чтобы различать вероятности 2/3 и 4/6. Последняя более достоверна.

Версия 09:09, 14 октября 2009


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. Последняя более достоверна.