Построение регистра правил на основе фактов — различия между версиями
(Новая страница: «Категория: Регистры правил. Архив 4 января 2005 ==Введение== Одной из актуальных задач сист…») |
м |
||
| (не показано 5 промежуточных версий 2 участников) | |||
| Строка 1: | Строка 1: | ||
| − | + | {| align="right" | |
| − | + | | __TOC__ | |
| − | 4 января 2005 | + | |} |
| + | Дмитрий Малюгин, 4 января 2005 | ||
==Введение== | ==Введение== | ||
| Строка 13: | Строка 14: | ||
Рассмотрим постановку задачи на конкретном примере. Пусть имеем следующий регистр фактов: | Рассмотрим постановку задачи на конкретном примере. Пусть имеем следующий регистр фактов: | ||
| − | {| | + | {|class=standard |
| − | + | !colspan = "3"|''Детерминант<br>(независимые переменные)'' | |
| − | + | !rowspan = "2"| | |
| − | + | !rowspan = "2"|''Корень<br>(зависимая переменная)'' | |
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
|- | |- | ||
| − | |align = "center"| | + | !Д1 |
| − | |align = "center"|C | + | !Д2 |
| − | |align = "center"|E | + | !Д3 |
| − | |align = "center" | + | |-align = "center" |
| − | + | |A ||C ||E || ||Нет | |
| − | |- | + | |-align = "center" |
| − | + | |A ||C ||F || ||Да | |
| − | | | + | |-align = "center" |
| − | | | + | |A ||D ||E || ||Нет |
| − | | | + | |-align = "center" |
| − | + | |B ||C ||E || ||Нет | |
| + | |-align = "center" | ||
| + | |B ||C ||F || ||Да | ||
|} | |} | ||
| Строка 61: | Строка 41: | ||
Итак, для построения регистра правил на основе фактов мы последовательно должны выполнить следующие шаги: | Итак, для построения регистра правил на основе фактов мы последовательно должны выполнить следующие шаги: | ||
| − | + | 1. Провести поиск однозначных правил для каждого из измерений детерминанта (в нашем примере последовательно для Д1, Д2 и Д3). Для этого таблица фактов сворачивается. При этом ключевой колонкой (с уникальными значениями после свертки) служит соответствующее измерение детерминанта, а сворачиваемой колонкой будет корень. Таким образом, после свертки получим таблицу, в которой значению ключевого измерения будет соответствовать множество значений корня. Кандидатом на правило будет такой кортеж данной таблицы, в котором множество значений корня состоит из одного значения (в этом и заключается ''однозначность''). При свертке необходимо рассчитывать мощность множества значений корня. Чем больше мощность, тем более достоверным является правило. Значение мощности также добавляется в регистр правил в атрибут ''Приоритет''. | |
| + | |||
В нашем примере имеем три таблицы одномерных сверток: | В нашем примере имеем три таблицы одномерных сверток: | ||
| − | + | {| | |
| − | {| | + | | |
| − | | | + | {| class="standard" |
| − | | | + | ! Д1 || || Корень || Мощность |
| − | |align = "center"| | + | |-align = "center" |
| − | | | + | | A || || Да, Нет || 3 |
| − | | | + | |-align = "center" |
| − | |align = "center" | + | | B || || Да, Нет || 2 |
| − | | | + | |} |
| − | | | + | | || |
| − | | | + | | |
| − | | | + | {| class="standard" |
| − | | | + | ! Д2 || || Корень || Мощность |
| − | + | |-align = "center" | |
| − | | | + | | C || || Да, Нет || 4 |
| − | | | + | |-align = "center" |
| − | | | + | | D || || Нет || 1 |
| − | | | + | |} |
| − | | | + | | || |
| − | |align = "center"|C | + | | |
| − | | | + | {| class="standard" |
| − | | | + | ! Д3 || || Корень || Мощность |
| − | |align = "center"| | + | |-align = "center" |
| − | | | + | | E || || Нет || 3 |
| − | | | + | |-align = "center" |
| − | | | + | | F || || Да || 2 |
| − | + | |} | |
| − | | | ||
| − | | | ||
| − | | | ||
| − | | | ||
| − | |align = "center"| | ||
| − | | | ||
| − | | | ||
| − | | | ||
| − | |align = "center"| | ||
| − | | | ||
| − | | | ||
| − | | | ||
| − | |||
|} | |} | ||
| − | |||
Итак, в регистр правил следует добавить второй кортеж из таблицы Д2 и оба кортежа из таблицы Д3: | Итак, в регистр правил следует добавить второй кортеж из таблицы Д2 и оба кортежа из таблицы Д3: | ||
| − | {| | + | {|class=standard |
| − | + | !colspan = "3"|''Детерминант'' | |
| − | + | !rowspan = "2"| | |
| − | + | !rowspan = "2"|''Корень'' | |
| − | + | !rowspan = "2"|Приоритет | |
|- | |- | ||
| − | |align = "center" | + | !Д1 |
| − | | | + | !Д2 |
| − | | | + | !Д3 |
| − | + | |-align = "center" | |
| − | | | + | | ||D || || ||Нет ||1 |
| − | | | + | |-align = "center" |
| − | |align = "center"| | + | | || ||F || ||Да ||2 |
| − | |align = "center"| | + | |-align = "center" |
| − | | | + | | || ||E || ||Нет ||3 |
| − | | | + | |} |
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | + | 2. После добавления одномерных правил мы ищем двумерные правила. Алгоритм тот же, только ключевые колонки для свертки определяются теперь парой измерений. Набор таких пар должен покрывать все возможные пары для измерений детерминанта. В нашем случае это пары Д1+Д2, Д1+Д3, Д2+Д3. После выборки из свернутых таблиц однозначных правил в регистр правил добавляются только те, которые не являются подмножеством уже присутствующих в нем одномерных правил. | |
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
В нашем примере все двумерные правила (и трехмерные тоже) являются подмножеством одномерных правил по Д3. Это является следствием того, что набор одномерных правил по Д3 покрыл весь диапазон (все пространство) значений измерения Д3. | В нашем примере все двумерные правила (и трехмерные тоже) являются подмножеством одномерных правил по Д3. Это является следствием того, что набор одномерных правил по Д3 покрыл весь диапазон (все пространство) значений измерения Д3. | ||
| − | + | 3. И так далее до N-мерного правила, где N – количество измерений исходного детерминанта регистра фактов. | |
Построенный регистр правил позволяет помимо решения задач классификации выявить некие общие закономерности представленных фактов. Кроме того, описанный алгоритм можно применить для анализа взаимосвязанности измерений детерминанта. | Построенный регистр правил позволяет помимо решения задач классификации выявить некие общие закономерности представленных фактов. Кроме того, описанный алгоритм можно применить для анализа взаимосвязанности измерений детерминанта. | ||
| − | + | В нашем примере входному вектору [A, D, F] будет соответствовать корень "Да", поскольку его приоритет выше. Если бы приоритеты (мощность) правил были одинаковыми, то выбор правила определился бы расположением измерений детерминанта (чем левее, тем выше приоритет). | |
==Пример построения== | ==Пример построения== | ||
| − | Рассмотрим | + | Рассмотрим пример построения регистра правил на основе известных тестовых данных. Регистр фактов имеет вид: |
| − | |||
| − | |||
| − | |||
| + | {|class="standard sortable" | ||
| + | !Наблюдение ||Температура ||Влажность ||Ветер | ||
| + | ! | ||
| + | !Игра | ||
|- | |- | ||
| − | | | + | |Солнце ||Жарко ||Высокая ||Нет || ||Нет |
| − | | | ||
| − | | | ||
| − | | | ||
| − | | | ||
| − | |||
|- | |- | ||
| − | |Солнце | + | |Солнце ||Жарко ||Высокая ||Есть || ||Нет |
| − | |Жарко | ||
| − | |Высокая | ||
| − | | | ||
| − | | | ||
| − | |||
|- | |- | ||
| − | | | + | |Облачность ||Жарко ||Высокая ||Нет || ||Да |
| − | |Жарко | ||
| − | |Высокая | ||
| − | | | ||
| − | | | ||
| − | |||
|- | |- | ||
| − | | | + | |Дождь ||Норма ||Высокая ||Нет || ||Да |
| − | | | ||
| − | |Высокая | ||
| − | |Нет | ||
| − | | | ||
| − | |||
|- | |- | ||
| − | |Дождь | + | |Дождь ||Холодно ||Норма ||Нет || ||Да |
| − | |Норма | ||
| − | | | ||
| − | |Нет | ||
| − | | | ||
| − | |||
|- | |- | ||
| − | |Дождь | + | |Дождь ||Холодно ||Норма ||Есть || ||Нет |
| − | |Холодно | ||
| − | |Норма | ||
| − | | | ||
| − | | | ||
| − | |||
|- | |- | ||
| − | | | + | |Облачность ||Холодно ||Норма ||Есть || ||Да |
| − | |Холодно | ||
| − | |Норма | ||
| − | |Есть | ||
| − | | | ||
| − | |||
|- | |- | ||
| − | | | + | |Солнце ||Норма ||Высокая ||Нет || ||Нет |
| − | | | ||
| − | |Норма | ||
| − | | | ||
| − | | | ||
| − | |||
|- | |- | ||
| − | |Солнце | + | |Солнце ||Холодно ||Норма ||Нет || ||Да |
| − | |Норма | ||
| − | | | ||
| − | |Нет | ||
| − | | | ||
| − | |||
|- | |- | ||
| − | | | + | |Дождь ||Норма ||Норма ||Нет || ||Да |
| − | | | ||
| − | |Норма | ||
| − | |Нет | ||
| − | | | ||
| − | |||
|- | |- | ||
| − | | | + | |Солнце ||Норма ||Норма ||Есть || ||Да |
| − | |Норма | ||
| − | |Норма | ||
| − | | | ||
| − | | | ||
| − | |||
|- | |- | ||
| − | | | + | |Облачность ||Норма ||Высокая ||Есть || ||Да |
| − | |Норма | ||
| − | | | ||
| − | |Есть | ||
| − | | | ||
| − | |||
|- | |- | ||
| − | |Облачность | + | |Облачность ||Жарко ||Норма ||Нет || ||Да |
| − | |Норма | ||
| − | | | ||
| − | | | ||
| − | | | ||
| − | |||
|- | |- | ||
| − | | | + | |Дождь ||Норма ||Высокая ||Есть || ||Нет |
| − | | | + | |} |
| − | |Норма | ||
| − | |Нет | ||
| − | | | ||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| + | Здесь поля "Наблюдение, Температура, Влажность, Ветер" относятся к детерминанту, а поле "Игра" - к корню регистра. | ||
| − | Данная таблица представляет собой набор фактов, описывающих погодные условия при которых игра может не состояться. Очевидно, что на основании данной таблицы довольно затруднительно делать какие-либо выводы. Данную таблицу необходимо преобразовать в регистр правил. После применения описанной выше процедуры получаем следующий регистр правил для корня | + | Данная таблица представляет собой набор фактов, описывающих погодные условия при которых игра может не состояться. Очевидно, что на основании данной таблицы довольно затруднительно делать какие-либо выводы. Данную таблицу необходимо преобразовать в регистр правил. После применения описанной выше процедуры получаем следующий регистр правил для корня "Игра". |
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| + | {|class="standard sortable" | ||
| + | !Наблюдение ||Температура ||Влажность ||Ветер | ||
| + | ! | ||
| + | !Игра ||Приор. ||Мерность правила | ||
|- | |- | ||
| − | |Облачность | + | |Облачность || || || || ||Да ||4 ||Наблюдение |
| − | | | ||
| − | | | ||
| − | | | ||
| − | | | ||
| − | | | ||
| − | |Наблюдение | ||
| − | |||
|- | |- | ||
| − | |Солнце | + | |Солнце ||Жарко || || || ||Нет ||2 |
| − | |Жарко | ||
| − | | | ||
| − | | | ||
| − | | | ||
| − | | | ||
|rowspan = "2"|Наблюдение + Температура | |rowspan = "2"|Наблюдение + Температура | ||
| − | |||
|- | |- | ||
| − | |Солнце | + | |Солнце ||Холодно || || || ||Да ||1 |
| − | |Холодно | ||
| − | | | ||
| − | | | ||
| − | | | ||
| − | | | ||
| − | |||
|- | |- | ||
| − | |Солнце | + | |Солнце || ||Высокая || || ||Нет ||3 |
| − | | | ||
| − | |Высокая | ||
| − | | | ||
| − | | | ||
| − | | | ||
|rowspan = "2"|Наблюдение + Влажность | |rowspan = "2"|Наблюдение + Влажность | ||
| − | |||
|- | |- | ||
| − | |Солнце | + | |Солнце || ||Норма || || ||Да ||2 |
| − | | | ||
| − | |Норма | ||
| − | | | ||
| − | | | ||
| − | | | ||
| − | |||
|- | |- | ||
| − | |Дождь | + | |Дождь || || ||Есть || ||Нет ||2 |
| − | | | ||
| − | | | ||
| − | |Есть | ||
| − | | | ||
| − | | | ||
|rowspan = "2"|Наблюдение + Ветер | |rowspan = "2"|Наблюдение + Ветер | ||
| − | |||
|- | |- | ||
| − | |Дождь | + | |Дождь || || ||Нет || ||Да ||3 |
| − | | | ||
| − | | | ||
| − | |Нет | ||
| − | | | ||
| − | | | ||
| − | |||
|- | |- | ||
| − | | | + | | ||Жарко ||Норма || || ||Да ||1 |
| − | |Жарко | ||
| − | |Норма | ||
| − | | | ||
| − | | | ||
| − | | | ||
|rowspan = "2"|Температура + Влажность | |rowspan = "2"|Температура + Влажность | ||
| − | |||
|- | |- | ||
| − | | | + | | ||Норма ||Норма || || ||Да ||2 |
| − | |Норма | ||
| − | |Норма | ||
| − | | | ||
| − | | | ||
| − | | | ||
| − | |||
|- | |- | ||
| − | | | + | | ||Жарко || ||Есть || ||Нет ||1 |
| − | |Жарко | ||
| − | | | ||
| − | |Есть | ||
| − | | | ||
| − | | | ||
|rowspan = "2"|Температура + Ветер | |rowspan = "2"|Температура + Ветер | ||
| − | |||
|- | |- | ||
| − | | | + | | ||Холодно || ||Нет || ||Да ||2 |
| − | |Холодно | ||
| − | | | ||
| − | |Нет | ||
| − | | | ||
| − | | | ||
| − | |||
|- | |- | ||
| − | | | + | | || ||Норма ||Нет || ||Да ||4 ||Влажность + Ветер |
| − | | | ||
| − | |Норма | ||
| − | |Нет | ||
| − | | | ||
| − | | | ||
| − | |Влажность + Ветер | ||
| − | |||
|- | |- | ||
| − | |Солнце | + | |Солнце ||Норма || ||Есть || ||Да ||1 |
| − | |Норма | ||
| − | | | ||
| − | |Есть | ||
| − | | | ||
| − | | | ||
|rowspan = "2"|Наблюдение + Температура + Ветер | |rowspan = "2"|Наблюдение + Температура + Ветер | ||
| − | |||
|- | |- | ||
| − | |Солнце | + | |Солнце ||Норма || ||Нет || ||Нет ||1 |
| − | |Норма | ||
| − | | | ||
| − | |Нет | ||
| − | | | ||
| − | | | ||
| − | |||
|} | |} | ||
| − | Как уже отмечалось, наиболее надежными правилами являются правила с наивысшим приоритетом, то есть такие, которые подтверждены наибольшим количеством фактов. | + | Как уже отмечалось, наиболее надежными правилами являются правила с наивысшим приоритетом,- то есть такие, которые подтверждены наибольшим количеством фактов. |
Определим, состоится ли игра при следующем значении вектора ситуации: | Определим, состоится ли игра при следующем значении вектора ситуации: | ||
| − | Наблюдение = Солнце; Температура = Холодно; Влажность = Высокая; Ветер = Есть. | + | Наблюдение = Солнце; Температура = Холодно; Влажность = Высокая; Ветер = Есть. |
Из регистра правил извлекаем следующие правила для данной ситуации: | Из регистра правил извлекаем следующие правила для данной ситуации: | ||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| + | {|class=standard | ||
| + | !Наблюдение ||Температура ||Влажность ||Ветер | ||
| + | ! | ||
| + | !Игра ||Приор. | ||
|- | |- | ||
| − | |Солнце | + | |Солнце ||Холодно || || || ||Да ||1 |
| − | | | + | |- |
| − | |Высокая | + | |Солнце || ||Высокая || || ||Нет ||3 |
| − | | | ||
| − | | | ||
| − | | | ||
| − | |||
|} | |} | ||
| Строка 430: | Строка 211: | ||
В соответствии с приоритетом игра, скорее всего, не состоится. | В соответствии с приоритетом игра, скорее всего, не состоится. | ||
| + | ==Контроль данных== | ||
Можно также провести анализ, насколько зависимыми друг от друга являются измерения детерминанта. Такие данные могут помочь для выявления ошибочных значений входного вектора. | Можно также провести анализ, насколько зависимыми друг от друга являются измерения детерминанта. Такие данные могут помочь для выявления ошибочных значений входного вектора. | ||
| − | Регистр правил для зависимости корня | + | Регистр правил для зависимости корня "Влажность" от Детерминанта "Наблюдение+Температура+Ветер" имеет вид: |
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| + | {|class="standard sortable" | ||
| + | !Наблюдение ||Температура ||Ветер || ||Влажность ||Приор. ||Мерность правила | ||
|- | |- | ||
| − | | | + | | ||Холодно || || ||Норма ||4 ||Температура |
| − | |Холодно | ||
| − | | | ||
| − | | | ||
| − | | | ||
| − | |Температура | ||
| − | |||
|- | |- | ||
| − | |Облачность | + | |Облачность ||Норма || || ||Высокая ||1 |
| − | |Норма | + | |rowspan = "2"|Наблюдение + Температура |
| − | | | ||
| − | | | ||
| − | | | ||
| − | |rowspan = "2"|Наблюдение + Температура | ||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
|- | |- | ||
| − | | | + | |Солнце ||Жарко || || ||Высокая ||2 |
| − | |Жарко | ||
| − | | | ||
| − | | | ||
| − | | | ||
| − | |||
| − | |||
|- | |- | ||
| − | | | + | | ||Жарко ||Есть || ||Высокая ||1 ||Температура + Ветер |
| − | | | ||
| − | |Есть | ||
| − | | | ||
| − | | | ||
| − | |||
|- | |- | ||
| − | | | + | |Дождь ||Норма ||Есть || ||Высокая ||1 |
| − | |Норма | + | |rowspan = "3"|Наблюдение + Температура + Ветер |
| − | |Есть | ||
| − | | | ||
| − | | | ||
| − | |rowspan = " | ||
| − | |||
|- | |- | ||
| − | |Солнце | + | |Солнце ||Норма ||Есть || ||Норма ||1 |
| − | |Норма | ||
| − | | | ||
| − | | | ||
| − | | | ||
| − | |||
|- | |- | ||
| − | | | + | |Солнце ||Норма ||Нет || ||Высокая ||1 |
| − | | | ||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | | | ||
| − | | | ||
| − | | | ||
| − | | | ||
| − | | | ||
| − | | | ||
| − | |||
|} | |} | ||
| Строка 518: | Строка 243: | ||
Корни регистра могут иметь вероятностный характер, поскольку правила (и факты) не всегда можно выразить однозначно. Однозначный корень (ресурс) – это частный случай многозначного, когда вероятность одного из значений корня равна 1. В общем случае корень может представлять собой список (таблицу) значений, где каждому значению присвоен определенный вес. Сумма всех весов – 1. | Корни регистра могут иметь вероятностный характер, поскольку правила (и факты) не всегда можно выразить однозначно. Однозначный корень (ресурс) – это частный случай многозначного, когда вероятность одного из значений корня равна 1. В общем случае корень может представлять собой список (таблицу) значений, где каждому значению присвоен определенный вес. Сумма всех весов – 1. | ||
| − | Например, для представленной выше таблицы фактов можно указать следующие вероятностные наборы правил для одномерных детерминантов ( | + | Например, для представленной выше таблицы фактов можно указать следующие вероятностные наборы правил для одномерных детерминантов ("Наблюдение" и "Температура"): |
| − | |||
| − | |||
| − | |||
| + | |||
| + | {|class=standard | ||
| + | !rowspan = "2"|Температура | ||
| + | !rowspan = "2"| | ||
| + | !colspan = "2"|Игра | ||
|- | |- | ||
| − | + | !P(Да) | |
| − | + | !P(Нет) | |
| − | |||
|- | |- | ||
| − | |Жарко | + | |Жарко || ||0.5 ||0.5 |
| − | | | ||
| − | | | ||
| − | |||
|- | |- | ||
| − | |Норма | + | |Норма || ||2/3 ||1/3 |
| − | | | ||
| − | | | ||
| − | |||
|- | |- | ||
| − | |Холодно | + | |Холодно || ||0.75 ||0.25 |
| − | | | + | |} |
| − | | | ||
| − | |||
| − | |} | ||
| − | {| | + | {|class=standard |
| − | + | !rowspan = "2"|Наблюдение | |
| − | + | !rowspan = "2"| | |
| − | + | !colspan = "2"|Игра | |
|- | |- | ||
| − | + | !P(Да) | |
| − | + | !P(Нет) | |
| − | |||
|- | |- | ||
| − | |Дождь | + | |Дождь || ||0.6 ||0.4 |
| − | | | ||
| − | | | ||
| − | |||
|- | |- | ||
| − | |Облачность | + | |Облачность || ||1 ||0 |
| − | | | ||
| − | | | ||
| − | |||
|- | |- | ||
| − | |Солнце | + | |Солнце || ||0.4 ||0.6 |
| − | | | + | |} |
| − | | | ||
| − | |||
| − | |} | ||
| Строка 577: | Строка 284: | ||
При построении регистра правил на основе регистра фактов должна быть возможность задания порогов вероятности (как верхнего – наиболее вероятно, так и нижнего – наименее вероятно), при котором правило стоит добавлять в регистр. Однозначный регистр правил – это вероятностный регистр с верхним порогом 1. Можно также учитывать ''достоверность'' правила – общую мощность, чтобы различать вероятности 2/3 и 4/6. Последняя более достоверна. | При построении регистра правил на основе регистра фактов должна быть возможность задания порогов вероятности (как верхнего – наиболее вероятно, так и нижнего – наименее вероятно), при котором правило стоит добавлять в регистр. Однозначный регистр правил – это вероятностный регистр с верхним порогом 1. Можно также учитывать ''достоверность'' правила – общую мощность, чтобы различать вероятности 2/3 и 4/6. Последняя более достоверна. | ||
| + | |||
| + | [[Категория: Регистры правил]] | ||
Текущая версия на 15:10, 29 февраля 2016
Дмитрий Малюгин, 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). Для этого таблица фактов сворачивается. При этом ключевой колонкой (с уникальными значениями после свертки) служит соответствующее измерение детерминанта, а сворачиваемой колонкой будет корень. Таким образом, после свертки получим таблицу, в которой значению ключевого измерения будет соответствовать множество значений корня. Кандидатом на правило будет такой кортеж данной таблицы, в котором множество значений корня состоит из одного значения (в этом и заключается однозначность). При свертке необходимо рассчитывать мощность множества значений корня. Чем больше мощность, тем более достоверным является правило. Значение мощности также добавляется в регистр правил в атрибут Приоритет.
В нашем примере имеем три таблицы одномерных сверток:
|
|
|
Итак, в регистр правил следует добавить второй кортеж из таблицы Д2 и оба кортежа из таблицы Д3:
| Детерминант | Корень | Приоритет | |||
|---|---|---|---|---|---|
| Д1 | Д2 | Д3 | |||
| D | Нет | 1 | |||
| F | Да | 2 | |||
| E | Нет | 3 | |||
2. После добавления одномерных правил мы ищем двумерные правила. Алгоритм тот же, только ключевые колонки для свертки определяются теперь парой измерений. Набор таких пар должен покрывать все возможные пары для измерений детерминанта. В нашем случае это пары Д1+Д2, Д1+Д3, Д2+Д3. После выборки из свернутых таблиц однозначных правил в регистр правил добавляются только те, которые не являются подмножеством уже присутствующих в нем одномерных правил.
В нашем примере все двумерные правила (и трехмерные тоже) являются подмножеством одномерных правил по Д3. Это является следствием того, что набор одномерных правил по Д3 покрыл весь диапазон (все пространство) значений измерения Д3.
3. И так далее до 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.
Например, для представленной выше таблицы фактов можно указать следующие вероятностные наборы правил для одномерных детерминантов ("Наблюдение" и "Температура"):
| Температура | Игра | ||
|---|---|---|---|
| P(Да) | P(Нет) | ||
| Жарко | 0.5 | 0.5 | |
| Норма | 2/3 | 1/3 | |
| Холодно | 0.75 | 0.25 | |
| Наблюдение | Игра | ||
|---|---|---|---|
| P(Да) | P(Нет) | ||
| Дождь | 0.6 | 0.4 | |
| Облачность | 1 | 0 | |
| Солнце | 0.4 | 0.6 | |
Здесь P(х) – вероятность ресурса х. Вероятностные правила несут в себе информацию, которая отсутствует в однозначном регистре. Так, например, мы видим, что если нам известна только лишь температура (Холодно), то игра состоится с вероятностью 75%. На основании данных однозначного регистра правил такой информации получить нельзя.
Однозначный регистр правил удобен, когда нам известен полный состав входного вектора ситуации. Если же на входе часть координат неизвестна, то правильней является использование вероятностного регистра правил. В вероятностном регистре незаполненные значения измерений детерминанта означают не квантор «Для всех (любых) значений», а квантор «Неизвестно (неопределенно)».
При построении регистра правил на основе регистра фактов должна быть возможность задания порогов вероятности (как верхнего – наиболее вероятно, так и нижнего – наименее вероятно), при котором правило стоит добавлять в регистр. Однозначный регистр правил – это вероятностный регистр с верхним порогом 1. Можно также учитывать достоверность правила – общую мощность, чтобы различать вероятности 2/3 и 4/6. Последняя более достоверна.
