Практическое занятие

«Построение дерева решений (индуктивная процедура ID3)»

Задание. Найдите посредством алгоритма ID3 закономерность в таблице экспериментальных данных и постройте максимально информативное логическое правило (модель), заменяющее таблицу. Правило должно быть минимальным с точки зрения записи из всех возможных.

Краткие теоретические сведения

Понаблюдайте за принятием решений какого-нибудь эксперта. Принятие решения Y обычно зависит от нескольких входных факторов (x1, x2, x3, …). Часто эксперт принимает решение интуитивно. Хорошо, если принимать решение будет опытный эксперт, а если его заменить на этом месте молодым экспертом? Сколько он будет ошибаться, пока приобретет необходимый опыт?

Кроме этого, даже опытный эксперт не может часто объяснить свое решение кому-либо, передать свой собственный опыт. А среди десятка конкретных случаев может не оказаться случай, который однажды рассмотрен. Опыт - это нечто особое, не перечень конкретных примеров, а закономерность, имея которую обладающий ею человек может решить новую задачу. Не обладая закономерностью, каждый раз, таким образом, новому человеку приходится набирать свой собственный опыт, создавая его заново. Но человечество как раз и отличалось от животного мира, из которого вышло, тем, что могло эффективно передавать опыт следующему поколению. Для этого нами были изобретены язык, а позднее письменность, отделившая информацию от непосредственного носителя, сохраняя ее в независимости от того, жив он или нет. Однако переданный и прочитанный текст надо проинтерпретировать снова подготовленным для этого мозгом. Текст, передавая частный случай (рекомендуемую реакцию на описанную в них ситуацию), есть не самый концентрированный способ передачи знаний. Из текста надо выделять нечто большее, - закон, его порождающий.

Алгоритм ID3 ищет закономерность среди известных экспериментальных данных, извлекает знание из данных, строит модель. При этом закономерность ищется в виде дерева решений, далее дерево легко превращается в логическую функцию Y = F(x1, x2, x3, …), точнее в уравнение. Дерево также может быть представлено алгоритмом, если задача неизменна.

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

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

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

Главное достоинство модели – за счет обобщения модель позволяет прогнозировать, предсказывать новые ранее неизвестные данные. При подстановке значения причины уравнение предсказывает (вычисляет) значение следствия.

Переход от частного к общему – индукция. Переход от общего к частному – дедукция. Построение моделей – индукция, решение задач – дедукция.

Пронумеруем полки сверху вниз от 1 до 8. Диалог может выглядеть так…

– Книга спрятана на четвертой полке и выше?

– Нет (получен 1 бит информации, неопределенность снизилась в 2 раза до четырех нижних полок: 5,6,7,8).

– Книга спрятана на шестой полке и выше?

– Да (получен еще 1 бит информации, неопределенность снизилась еще в 2 раза до двух полок: 5 и 6).

– Книга на шестой полке?

– Нет (получен еще 1 бит информации, неопределенность снизилась в 2 раза, Р=1, полка угадана, она номер 5).

Итак, чтобы получить ответ в случае N=8, Р=1/8, понадобилось три вопроса и, соответственно, три ответа типа «да»/»нет», то есть i = 3 бита информации.

При разном количестве полок N имеем соответствующее им количество вопросов i:

• Всего понадобится три вопроса и, соответственно, три ответа типа «да»/»нет», то есть i = 3 (бит).

Рисунок – Получая информацию (например, 1 бит), уменьшаем энтропию на такую же величину (1 бит), неопределенность выбора N уменьшаем вдвое (8, 4, 2, 1), а вероятность P увеличиваем вдвое (1/8, 1/4, 1/2, 1/1)

Энтропия E связана с информацией I линейно и обратно: E = -I+const, так как имеет место закон сохранения: E+I=const. Если где-то возросло количество информации, то где-то соответственно на эту же величину уменьшилась энтропия. Энтропия – это мера неупорядоченности, характеризует количество хаоса в системе. При полном порядке Е=0.

Информация I связана с N (неопределенностью выбора) степенной функцией: N=2ⁱ.

Шеннон усложнил постановку задачи. Он предположил, что выбор полки не равновероятен. Или в речи одни символы в информационном сообщении встречаются чаще (например, буква А), другие (например, буква Щ) – реже.

• Значит, связь между i и N: N=2ⁱ, P=1/N, где Р – вероятность найти книгу на одной из N полок.

То есть: i = log₂N или i = log₂(1/P) = log₂1 - log₂P = 0 - log₂P

В итоге связь информации и вероятности имеет вид: I = - log₂P (формула Хартли).

Исчисление информативности (информации) происходит по формуле Хартли, далее обобщенной Шенноном:

i = - ∑ P_j * log₂(P_j),

где i – количество информации, P_j – вероятность j–того исхода, суммирование идет по индексу j. Естественно, что P₁ + P₂ + … = 1.

На языке полок и книг это можно объяснить так.

• В шкафу (N=8) полок, на которых спрятана книга, но на полках разное количество книг. Вероятность найти книгу на одной из них – разная.
• Е = - Сумма (P_j*log₂P_j, j=1, N) (формула Шеннона)
• P_j- вероятность найти книгу на j-той полке среди К книг: P_j = 1/ К_j. Продолжая преобразования, имеем: log₂P = lgP/lg2 = lgP/0.301 = 3.32*lgP.

Рисунок – График функции, соответствующей формуле Шеннона и геометрическая иллюстрация отдельных ее точек

На рисунке показан график функции для случая Р₁ + Р₂ = 1. Р₁ – вероятность появления белой пиксели на экране телевизора. Р₂ – черной.

Интересно, что полный порядок (сплошной черный или сплошной белый экран) нам в качестве телевизионной картинки не интересен. Здесь энтропия минимальна.

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

Интерес с точки зрения информации представляет «средняя» картинка. В ней есть и порядок (сохранение каких-то узнаваемых черт от кадра к кадру, похожесть на какие-то известные нам ранее объекты), и хаос (изменение, развитие картинки). Мир без закономерностей не имеет смысла, мир абсолютного порядка также бессмысленнен. Жизнь – соотношение сохранения и развития одновременно. Мир усложняется, но не сваливается в абсолютную сложность, сохраняя некий порядок.

Посмотрите на подборку портретов. Так видят разные художники свою жену. Портреты упорядочены по шкале «хаос – порядок».

Рисунок – Портрет жены художника (портреты упорядочены по значению переменной энтропия)

1 – абсолютный хаос. Зрители не останавливаются около этого произведения, хотя оно крайне сложно, запомнить переплетение линий невозможно.

7 – высокая степень порядка. Здесь зритель также почти не задерживает своего внимания. Портрет банален. Образ не запоминается.

4 – наиболее привлекательный образ, таящий в себе и загадку, и узнаваемость одновременно.

Неопределенность монотонно нелинейно соответствует понятию энтропии. Чем больше неопределенность (хаос), тем больше энтропия системы. Энтропия гасится информацией. Большая энтропия – это «хаос». «Порядок» соответствует минимальной энтропии. Получение информации системой переводит хаос в порядок, упорядочивает структуру системы, повышает ее предсказуемость, закономерность поведения.

Рисунок – Понятие энтропии и связь ее с информацией: информация гасит энтропию

Интересный вопрос состоит в следующем: «Энтропия – полезна людям или нет?» Рассмотрим это на примерах. Пример 1 – приглашаем девушку пойти с нами в кино. Пример 2 – смотрим телевизионную картинку. Пример 3 – слушаем новостную передачу по радио.

Поводя итог, скажем, что если энтропия максимальна, и мы имеем дело с полным хаосом, белым шумом, то пользы от этого маловато. Мир с максимальной энтропией непознаваем, случаен, непредсказуем и выглядит как мелькание черных и белых точек на экране телевизора. В таком мире нет и не может быть никаких законов. В некотором смысле мир однороден в своем случайном мелькании. С другой стороны, однако, и полностью детерминированный мир (минимальная энтропия), который выглядит как однородная монотонная структура, повторяющаяся во всех своих частях, хотя и познаваем и имеет четкий и простой закон своего построения и поведения, мало кому интересен. В нем ничего никогда не происходит. Это мир полного порядка. Интерес, конечно представляет какое-то разнообразие, но имеющее смысл, закономерность, некоторое значение энтропии. В этом есть какой-то интерес.

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

• системы со случайными нерегулярными и изменчивыми связями – это системы с высокой энтропией, их изучать сложно, их поведение плохо предсказуемо, это сложные системы;
• системы с регулярными связями – простые системы с простой структурой и с предсказуемым поведением.

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

Пример

Описание задачи

Эксперт – банковский служащий, решающий вопрос о выдаче кредита клиентам. Наблюдение за экспертом показало, что в результате 14 экспериментов эксперт спрашивал у клиентов и принимал во внимание «Кредитную историю», «Наличие долга у клиента», «Наличие поручителей», «Доход клиента».

При этом Кредитная история могла быть плохой, неизвестной, хорошей,

Долг – высокий или низкий,

Поручительство – нет или адекватное,

Доход – 0-15 тысяч рублей, 15-35 тысяч рублей, более 35 тысяч рублей.

Решением эксперта являлась оценка риска невозврата кредита, которую эксперт оценивал как высокую, среднюю, низкую.

То есть обозначим:

Y – риск невозврата кредита (высокий В, средний С, низкий Н),

x1 – кредитная история (плохая П, неизвестная Н, хорошая Х),

x2 – долг (высокий В, низкий Н),

x3 – поручительство (нет Н, адекватное А),

x4 – доход (0-15 тысяч рублей М, 15-35 тысяч рублей С, более 35 тысяч рублей В).

Y, x1, x2, x3, x4 – это атрибуты базы данных, переменные закона, признаки. Значения признаков, числа – это свойства.

На технических схемах это выглядит так.

Рисунок – Инженерная схема, отражающая зависимость риска Y от действующих на него причин (x1-кредитная история, x2-долг, x3-поручительство, x4-доход)

Ищем функцию Y = F(x1, x2, x3, x4) или в наших обозначениях Р = F(К, Дг, П, Дд).

Из наблюдений за экспертом и его общением с клиентами удалось заполнить следующую экспериментальную таблицу фактов. Всего было зафиксировано 14 случаев (14 клиентов, 14 записей базы данных).

Таблица – Экспериментальные данные

В столбце «Риск» базы данных отмечены решения, сделанные на практике экспертом. В столбце «Эксперимент. Пример» - конкретный случай, номер записи базы данных.

Решение задачи

Найдем закон выдачи кредитов.

В принципе можно построить множество деревьев по этой таблице, все они будут разного размера. Постройте хотя бы одно дерево для примера. В принципе, максимальное дерево будет иметь: 3 (КИ) * 2 (Дг) * 2 (П) * 3 (Дд) = 36 листьев в кроне. Такое дерево соответствует полной базе ДАННЫХ, содержит все варианты. Задача состоит в том, чтобы МИНИМИЗИРОВАТЬ дерево, найдя в нем закономерности, то есть уменьшить крону. В этом случае, чем меньше дерево, тем более компактной будет формула его описания. Тем самым совершится переход от базы данных к формуле – базе ЗНАНИЙ. Формула заменит собой таблицу данных, если, конечно, мы, конечно, найдем в дереве закономерность. Если такая закономерность в таблице экспериментальных данных есть, то по формуле Шеннона мы ее найдем.

Постановка задачи Шеннона: как за минимальное число вопросов найти ответ, то есть раскрыть неопределенность, сколько надо получить информации (ответов клиентов на вопросы служащего банка), чтобы погасить неопределенность (энтропию) в принятии решения «давать кредит – не давать кредит».

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

1. Начнем строить дерево с верхнего уровня 1.

В вершину дерева можно установить узел Дд, или К, или Дг, или П. Установить надо такой узел, который ведет быстрее к решению, то есть самый информативный.

1.1. Испытаем узел Дд. Вычислим, сколько он содержит неопределенности?

У него в дереве может быть три возможных продолжения (0-15, 15-35, >35).

Оценим каждую ветвь. По таблице видно, что в ветвь Дд=(0-15) попадают примеры 1,4,7,11, которые все ведут к случаю Риск=В.

Неопределенность, которая содержится в этой ветви, равна 0, так как 4/4*log₂(4/4) = 0 (бит). (Минимальная неопределенность!!)

В этой ветви, после ответа о доходе, неопределенности не осталось. Энтропия минимальна, получен максимум информации, что соответствует полному порядку.

Продолжать эту ветвь (задавать еще какие-то вопросы) далее нет смысла. В принципе ясно, что в таблице обнаружена закономерность «если ваш доход меньше 15, то кредит вам не выдадут».

По таблице видно, что в ветвь Дд=(15-35) попадают примеры 2,3,12,14. Примеры 2 и 14 ведут к случаю Риск=В. Примеры 3 и 12 ведут к случаю Риск=С. Неопределенность, которая содержится в этой ветви, равна -(2/4*log₂(2/4) + 2/4*log₂(2/4)) = 1 (бит). (Неопределенность по сравнению с предыдущим случаем больше!! Полная информация здесь еще не получена – при среднем доходе риск бывает и высокий, и средний, 50 на 50. Придется задавать еще дополнительные вопросы, чтобы получить полную ясность.)

По таблице видно, что в ветвь Дд=(>35) попадают примеры 5,6,8,9,10,13. Пример 8 ведет к случаю Риск=С. Примеры 5,6,9,10,13 ведут к случаю Риск=Н. Неопределенность, которая содержится в этой ветви, равна –(1/6*log₂(1/6) + 5/6*log₂(5/6))=0.65 (бит). (6 исходов, 1 и 5 – количество исходов по каждому из значений).

Итак, если Дд установить в качестве узла, то это даст неопределенность вершины при поиске решения 4/14*0+4/14*1+6/14*0.65 = 0.564 (бит).

Здесь, всего 14 возможных исходов, 4, 4, 6 – количество исходов в каждой из ветвей, 0, 1, 0.65 – неопределенности этих ветвей.

1.2. Испытаем узел К. Вычислим, сколько он содержит неопределенности?

У него в дереве может быть три возможных продолжения (П, Х, Н).

Оценим каждую ветвь. По таблице видно, что в ветвь П попадают примеры 1,7,8,14, которые ведут к случаям Риск = В, В, С, В. Неопределенность, которая содержится в этой ветви, равна –(1/4*log₂(1/4)+ 3/4*log₂(3/4))=0.81 бит. (4 исхода, 1 и 3 – количество исходов по каждому из значений Риска).

По таблице видно, что в ветвь Х попадают пять примеров: 9,10,11,12,13. Пример 11 ведет к случаю Риск=В. Пример 12 ведет к случаю Риск=С. Примеры 9,10,13 ведут к случаю Риск=Н. Неопределенность, которая содержится в этой ветви, равна –(1/5*log₂(1/5)+ 1/5*log₂(1/5) + 3/5*log₂(3/5))=1.37 бит.

По таблице видно, что в ветвь Н попадают примеры 2,3,4,5,6. Пример 3 ведет к случаю Риск=С. Примеры 2, 4 ведут к случаю Риск=В. Примеры 5, 6 ведут к случаю Риск=Н. Неопределенность, которая содержится в этой ветви, равна –(1/5*log₂(1/5)+2/5*log₂(2/5)+ 2/5*log₂(2/5)) = 1.52 бит. (5 исходов, 1, 2 и 2 – количество исходов по каждому из значений).

Итак, если К установить в качестве узла, то это даст неопределенность вершины при поиске решения 4/14*0.81+5/14*1.37+5/14*1.52 = 1.265 (бит).

Здесь, всего 14 возможных исходов, 4, 5, 5 – количество исходов в каждой из ветвей, 0.81, 1.37, 1.52 – неопределенности этих ветвей.

1.3. Испытаем узел Дг. Вычислим, сколько он содержит неопределенности?

У него в дереве может быть два возможных продолжения (В, Н). Оценим каждую ветвь. По таблице видно, что в ветвь В попадают примеры 1,2,6,10,11,12,13,14, которые ведут к случаям Риск = В, В, Н, Н, В, С, Н, В. Неопределенность, которая содержится в этой ветви, равна –(4/8*log₂(4/8)+ 3/8*log₂(3/8) + 1/8*log₂(1/8)) = 1.4 бит. (8 исходов, 4, 3 и 1 – количество исходов по каждому из значений Риска).

По таблице видно, что в ветвь Н попадают примеры 3,4,5,7,8,9. Примеры 3, 8 ведут к случаю Риск=С. Примеры 4, 7 ведут к случаю Риск=В. Примеры 5, 9 ведут к случаю Риск=Н. Неопределенность, которая содержится в этой ветви, равна –(2/6*log₂(2/6)+ 2/6*log₂(2/6) + 2/6*log₂(2/6))=1.58 бит. (6 исходов, 2, 2 и 2 – количество исходов по каждому из значений).

Итак, если Дг установить в качестве узла, то это даст неопределенность вершины при поиске решения 8/14*1.4+6/14*1.58 = 1.48 бит неопределенности.

Здесь, всего 14 возможных исходов, 8, 6 – количество исходов в каждой из ветвей, 1.4, 1.58 – неопределенности этих ветвей.

1.4. Испытаем узел П. Вычислим, сколько он содержит неопределенности?

У него в дереве может быть два возможных продолжения (Н, А). Оценим каждую ветвь. По таблице видно, что в ветвь Н попадают примеры 1,2,3,4,5,7,9,11,12,13,14, которые ведут к случаям Риск = В, В, С, В, Н, В, Н, В, С, Н, В. Неопределенность, которая содержится в этой ветви, равна –(6/11*log₂(6/11) + 2/11*log₂(2/11) + 3/11*log₂(3/11)) = 1.43 бит. (11 исходов, 6, 2 и 3 – количество исходов по каждому из значений Риска).

По таблице видно, что в ветвь А попадают примеры 6,8,10. Примеры 6, 10 ведут к случаю Риск=Н. Примеры 8 ведут к случаю Риск=С. Неопределенность, которая содержится в этой ветви, равна –(2/3*log₂(2/3) + 1/3*log₂(1/3)) =0.92 бит. (3 исхода, 2 и 1 – количество исходов по каждому из значений).

Итак, если П установить в качестве узла, то это даст неопределенность вершины при поиске решения 11/14*1.43+3/14*0.92 = 1.32 бит.

Здесь, всего 14 возможных исходов, 11, 3 – количество исходов в каждой из ветвей, 1.43, 0.92 – неопределенности этих ветвей.

Вариантов установки в этот уровень других узлов больше нет, надо принимать решение – какой узел устанавливаем. Выберем наименьшую ранее вычисленную неопределенность ответов среди вопросов {Доход, Кредитная история, Долг, Поручители} – min {0.564, 1.26, 1.48, 1.32} = 0.564, что соответствует вершине Дд (Доход).

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

Дерево выглядит сейчас так.

2. Переходим во второй уровень дерева по незакрытым веткам.

2.1. Первый узел во втором уровне уже полностью определен. Далее детализировать его не надо. Риск=В при любых продолжениях {1,2,7,11}.

2.2. На роль второго узла во втором уровне могут претендовать вершины {К, Дг, П}.

2.2.1. Испытаем вершину К. Вычислим, сколько она содержит неопределенности?

У него в дереве может быть три возможных продолжения (П, Х, Н). Оценим каждую ветвь. По таблице видно, что в ветвь П попадает пример 14, который реализует случай Риск = В. Неопределенность, которая содержится в этой ветви, равна 1/1*log₂(1/1)=0. (1 исход, 1 – количество исходов по одному значению Риска).

По таблице видно, что в ветвь Х попадает пример 12. Пример 12 ведет к случаю Риск=С. Неопределенность, которая содержится в этой ветви, равна 1/1*log₂(1/1)=0. (Неопределенность минимальна!! В этой ветви все ясно).

По таблице видно, что в ветвь Н попадают примеры 2,3. Пример 3 ведет к случаю Риск=С. Пример 2 ведет к случаю Риск=В. Неопределенность, которая содержится в этой ветви, равна –(1/2*log₂(1/2) +1/2*log₂(1/2)) = 1 бит.

Итак, если К установить в качестве узла, то это даст неопределенность вершины при поиске решения 1/4*0+1/4*0+2/4*1 = 0.5 бит.

Здесь, всего 4 возможных исхода, 1,1,2 – количество исходов в каждой из ветвей, 0, 0, 0.5 – неопределенности этих ветвей.

2.2.2. Испытаем вершину Дг. Вычислим, сколько она содержит неопределенности?

У него в дереве может быть два возможных продолжения (В, Н). Оценим каждую ветвь. По таблице видно, что в ветвь В попадают примеры 2,12,14, которые реализуют случаи Риск = В, С, В, соответственно. Неопределенность, которая содержится в этой ветви, равна –(2/3*log₂(2/3) + 1/3*log₂(1/3) = 0.92 бит.

По таблице видно, что в ветвь Н попадает пример 3. Пример 3 ведет к случаю Риск=С. Неопределенность, которая содержится в этой ветви, равна 1/1*log₂(1/1) =0 бит. (Неопределенность минимальна!! В этой ветви все ясно).

Итак, если Дг установить в качестве узла, то это даст неопределенность вершины при поиске решения 3/4*0.92+1/4*0 = 0.689 бит.

Здесь, всего 4 возможных исхода, 3,1 – количество исходов в каждой из ветвей, 0.92, 0 – неопределенности этих ветвей.

2.2.3. Испытаем вершину П. Вычислим, сколько она содержит неопределенности?

У него в дереве может быть два возможных продолжения (А, Н). Оценим каждую ветвь. По таблице видно, что в ветвь А ничего не попадает. Неопределенность, которая содержится в этой ветви, равна 0 бит.

По таблице видно, что в ветвь Н попадают примеры 2,3,12,14. Примеры 2 и 14 ведут к случаю Риск=В. Примеры 3 и 12 ведут к случаю Риск=Н.

Неопределенность, которая содержится в этой ветви, равна –(2/4*log₂(2/4) +2/4*log₂(2/4))=1 бит.

Итак, если П установить в качестве узла, то это даст неопределенность вершины при поиске решения 0/4*0+4/4*1 = 1 бит.

Вариантов установки в этот уровень узлов больше нет, надо принимать решение – какой узел устанавливаем. Выберем наименьшую неопределенность из ранее вычисленных – min {0.5, 0.689, 1} = 0.5, что соответствует вершине К. Итак, выбираем в качестве узла вершину Кредитная история.

Дерево выглядит сейчас так.

2.3. На роль третьего узла во втором уровне могут претендовать вершины К, Дг, П.

2.3.1. Испытаем вершину К. Вычислим, сколько она содержит неопределенности?

У него в дереве может быть три возможных продолжения (П, Х, Н). Оценим каждую ветвь.

По таблице видно, что в ветвь П попадает пример 8, который реализует случай Риск = С. Неопределенность, которая содержится в этой ветви, равна 1/1*log₂(1/1) =0 бит. (1 исход, 1 – количество исходов по одному значению Риска).

По таблице видно, что в ветвь Х попадают примеры 9, 10, 13. Все примеры ведут к случаю Риск=Н. Неопределенность, которая содержится в этой ветви, равна 3/3*log₂(3/3) =0 бит. (Неопределенность минимальна!! В этой ветви все ясно).

По таблице видно, что в ветвь Н попадают примеры 5,6. Оба примера ведут к случаю Риск=Н. Неопределенность, которая содержится в этой ветви, равна 2/2*log₂(2/2) = 0 бит.

Итак, если К установить в качестве узла, то это даст неопределенность вершины при поиске решения 3/6*0+1/6*0+2/6*0 = 0 (бит).

Замечательное значение неопределенности 0 (бит) говорит нам о том, что правило уже есть, закономерность установлена, но все равно для полноты картины проверим остальные вершины претенденты.

2.3.2. Испытаем вершину Дг. Вычислим, сколько она содержит неопределенности?

У него в дереве может быть два возможных продолжения (В, Н). Оценим каждую ветвь.

По таблице видно, что в ветвь В попадают примеры 6, 10, 13, которые реализуют случай Риск = Н. Неопределенность, которая содержится в этой ветви, равна 3/3*log₂(3/3)=0.

По таблице видно, что в ветвь Н попадают примеры 5, 8, 9. Примеры 5 и 9 ведут к случаю Риск=Н. Пример 8 ведет к случаю Риск=С. Неопределенность, которая содержится в этой ветви, равна –(2/3*log₂(2/3) + 1/3*log₂(1/3)) = 0.918 бит.

Итак, если Дг установить в качестве узла, то это даст неопределенность вершины при поиске решения 3/6*0+3/6*0.918 = 0.54 бит.

2.3.3. Испытаем вершину П. Вычислим, сколько она содержит неопределенности?

У него в дереве может быть два возможных продолжения (А, Н). Оценим каждую ветвь.

По таблице видно, что в ветвь А попадают примеры 6, 8, 10. Пример 6 и 10 реализуют случай Риск = Н. Пример 8 реализует Риск=С. Неопределенность, которая содержится в этой ветви, равна –(2/3*log₂(2/3) + 1/3*log₂(1/3)) =0.918 бит.

По таблице видно, что в ветвь Н попадают примеры 5, 9, 13. Все примеры ведут к случаю Риск=Н. Неопределенность, которая содержится в этой ветви, равна 3/3*log₂(3/3) =0.

Итак, если П установить в качестве узла, то это даст неопределенность вершины при поиске решения 3/6*0+3/6*0.918 = 0.54 бит.

Вариантов установки в этот уровень узлов больше нет, надо принимать решение – какой узел устанавливаем. Выберем наименьшую из ранее вычисленных неопределенностей – min {0, 0.54, 0.54} = 0, что соответствует вершине К. Итак, выбираем в качестве узла вершину Кредитная история.

Дерево выглядит сейчас так.

3. Переходим в третий уровень.

3.2.1. Первый узел второго узла второго уровня недоопределен. На роль второго узла во втором уровне могут претендовать вершины Дг и П.

3.2.1.1. Испытаем вершину Дг. Вычислим, сколько она содержит неопределенности?

У него в дереве может быть два возможных продолжения (В, Н). Оценим каждую ветвь.

По таблице видно, что в ветвь В попадает пример 2. Пример 2 реализует случай Риск = В. Неопределенность, которая содержится в этой ветви, равна 1/1*log₂(1/1) =0 бит.

По таблице видно, что в ветвь Н попадает примеры 3. Пример 3 ведет к случаю Риск=С. Неопределенность, которая содержится в этой ветви, равна 1/1*log₂(1/1) =0 бит.

Итак, если Дг установить в качестве узла, то это даст неопределенность вершины при поиске решения 1/2*0+1/2*0 = 0 бит. (Полная определенность!!)

3.2.1.2. Проверьте вершину П самостоятельно.

Итак, выбираем в качестве узла вершину Долг.

Дерево выглядит сейчас так.

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

Следствия

Следствие 1. Очевидно, что важнейший фактор для решения - Доход, так как он попал в верхний уровень. Он самый информативный и больше всех остальных факторов снижает неопределенность до 0.564 бит. На языке банковского служащего это звучит так: «Без дохода > 35 кредита не дадут ни при каких условиях». Второй по важности фактор (второй ярус) – кредитная история, она уточняет ситуацию после дохода. Далее (на третьем месте по важности) долг.

Следствие 2. Показатель «поручительство» роли при принятии решения не играет. Эксперт зря выяснял у клиентов значение этого фактора (требовал подтверждающие документы), от него, как показывает дерево, ничего не зависит.

Следствие 3. Что хуже для эксперта – неизвестная или плохая кредитная история? Видно, что неизвестная кредитная история лучше для принятия положительного решения о выдаче кредита. Дерево сортирует критерии принятия решения.

Следствие 4. В построенном дереве 12 вершин. Сравните с числом вершин дерева, которое вы построили в самом начале. У дерева, построенного алгоритмом ID3, вершин меньше. Минимальное дерево содержит 8 вершин-листьев. Максимальное дерево (таблица примера) содержит 14 вершин (14 строк).

Эффективность сжатия – (14-8)/14 = 43%

В случае плохих предметных областей эффективность сжатия может быть намного ниже. Это говорит о том, что закономерности в примерах данной предметной области мало само по себе. Например, таблица случайных чисел дает эффективность 0%. Такой же результат дает таблица ортогональных примеров.

Следствие 5. Построим правила принятия решения о выдаче кредита в виде логической функции.

Риск = ‘Низкий’ И ((Дд>35) И ((К==Х) ИЛИ (К==Н))) ИЛИ ‘Средний’ И (((Дд>35) И (К==П)) ИЛИ ((15<Дд<35) И (К==Х))) ИЛИ ((15<Дд<35) И (К==Н) И (Дг==Н))) ИЛИ ‘Высокий’ И ((Дд<=15) ИЛИ ((15<ДД<35) И (К==П)) ИЛИ ((15<ДД<35) И (К==Н) И (Дг==В))).

Можно записать это уравнение, используя знаки логических операций (&-И, |-ИЛИ).

Риск = Низкий & ((Дд>35) & ((К==Х) | (К==Н))) | Средний & (((Дд>35) & (К==П)) | ((15<Дд<35) & (К==Х))) | ((15<Дд<35) & (К==Н) & (Дг==Н))) | Высокий & ((Дд<=15) | ((15<ДД<35) & (К==П)) | ((15<ДД<35) & (К==Н) & (Дг==В))).

Часто знак & в записи опускают, просто подразумевая его по умолчанию (как и знак умножения *). Тогда запись будет иметь вид:

Риск = Низкий ((Дд>35) ((К==Х) | (К==Н))) | Средний (((Дд>35) (К==П)) | ((15<Дд<35) (К==Х))) | ((15<Дд<35) (К==Н) (Дг==Н))) | Высокий ((Дд<=15) | ((15<ДД<35) (К==П)) | ((15<ДД<35) (К==Н) (Дг==В))).

Например, рассчитаем значение функции для случая: Дд>=15, Дд<=35, К=Х.

Функция вернет значение: Риск = Низкий ((Дд>35)((К==Х) | (К==Н))) | Средний (((Дд>35)(К==П)) | ((15<Дд<35)(К==Х))) | ((15<Дд<35)(К==Н)(Дг==Н))) | Высокий ((Дд<=15) | ((15<ДД<35)(К==П)) | ((15<ДД<35)(К==Н)(Дг==В))).

Синим маркером подкрашены выражения, которые при подстановке исходных данных примут значение 0 (False), зеленым – 1 (True). Значения переменной Риск будем считать символьными (string): ‘Высокий’, ’Средний’, ’Низкий’. Знак логического умножения И (&) – опущен, знак логического сложения ИЛИ - |.

Упрощая пошагово по правилам логики, получаем.

Риск = Низкий ((0) ((1) | (0))) | Средний (((0) (0)) | ((1) (1))) | ((1) (0) (Дг==Н))) | Высокий ((0) | ((1) (0)) | ((1) (0) (Дг==В))).

Риск = Низкий (0 | 0) | Средний (0 | (1) (1)) | ((1) (0) (Дг==Н))) | Высокий ((0) | ((1) (0)) | ((1) (0) (Дг==В))).

Риск = Низкий (0) | Средний (0 | 1 | 0) | Высокий ((0) | (0) | (0)).

Риск = Низкий (0) | Средний (1) | Высокий (0).

Риск = Средний (1).

Риск = Средний.

Вспомните методы Дискретной математики. Запишите логическую функцию через операции И, ИЛИ, НЕ и в обозначениях Y и x1, x2, … . Минимизируйте количество символов в записи функции (МДНФ, МКНФ).

Следствие 6. Допустим, что экономика находится в кризисе: банк будет выдавать кредиты только в случае низкого риска их возврата, а в случае среднего и высокого риска – отказывать в выдаче кредитов. Заменяем в дереве листья Риск=Высокий и Риск=Средний на Кредит=Нет, а листья Риск=Низкий - на листья Кредит=Да.

Выводим по дереву краткую формулу выдачи кредита: Кредит = (Дд>35)*(1-(К=П)). Здесь показан вариант записи в закодированной числами форме, 0 – Кредит не выдается, 1 – Кредит выдается. Выражение (1-(К=П)) в числовой области заменяет выражение НЕ (К=П), знак логического И заменяется на знак численного умножения «*», знак логического ИЛИ заменяется на знак числового сложения «+».

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

Более подробно эти рассуждения приведены в учебнике «Моделирование систем». Данная функция является предикатом и в итоге после подстановки исходных значений возвращает выходные значения 1 (Кредит выдать) или 0 (Кредит не выдавать).

На языке алгоритмов это будет выглядеть так, как показано на рисунке.

Рисунок – Алгоритм принятия решения о выдаче кредита в кризисной ситуации, соответствующий полученной модели эксперта

Следствие 7. Докажите, что найденное дерево и функция принятия решения являются моделью в отличие от таблицы, где представлены только данные. Используя дерево (функцию), спрогнозируйте новые данные, отсутствующие в таблице (не менее двух записей). Результат добавьте в тестовую таблицу (следствие 6).

Например, Клиент =15, Доход = (от 15 до 35), Кредитная история = Хорошая, Долг – не важно, Поручительство – не важно. Риск = Средний.

Еще пример, Клиент =16, Доход = (<15), Кредитная история = Хорошая, Долг – не важно, Поручительство – не важно. Риск = Высокий.

В терминах и записях базы данных это будет выглядеть так.

Таблица – Дополнение к исходной базе данных. Прогноз

Так как система может предсказывать новые, ранее неизвестные данные, то она интеллектуальна. База данных к такому не способна.

Следствие 8.

Поскольку нами построена модель, то ее можно преобразовать (в отличие от алгоритма).

Например, стоит обратная задача: найти x1 из закона Y=F(x1, x2) при заданных Y и x2. С помощью преобразований найдите x1=G(Y, x2).

Для примера преобразуем полученную ранее модель: Кредит = (Дд>35)*(1-(К=П)), выразим Дд через переменные Кредит и К.

Преобразуем правилами дискретной логики модель:

(Дд>35) = 0*((Кредит=1)*(К=П) | ((Кредит=0)*(К=П))) | 1*((Кредит=1)*(1-(К=П))).

Или, упрощая:

(Дд>35) = (Кредит=1)*(1-(К=П)).

Иными словами, на вопрос «Какие клиенты имеют доход больше 35 т.р.?» модель дает ответ «Те, которым дали кредит И у которых неплохая кредитная история!».

Алгоритм на вычисление такого ответа не способен. Если задача изменена – требуются новые усилия программиста по написанию нового оригинального алгоритма (программы).

Важное примечание (для желающих)

Чем кардинально отличается Модель от Функции? Функция для одного значения аргумента (набора уникальных значений аргументов) имеет только ОДНО значение функции. Например, при х=2 функция y=3x+5 дает значение y=11.

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

Однако в физике пространства есть вертикальные линии – косяк двери, столб, дерево и т.п.. Записывают этот факт в виде модели – уравнения: Ax+By+С=0. В частном случае, при А=0 имеем By+C=0 или y=-C/B.

Если сразу выразить y через х (перейти от уравнения g(x,y)=0 к функции y=f(x)), то при В=0 возможна аварийная ситуация «деления на ноль»: Ax+By+C=0, y = -C/B-A/B*x.

Поэтому моделями (универсальная запись законов) оперировать удобнее. Модель превращается в функцию. Модель – это связь переменных в неявном виде (F=ma, F-ma=0), указывающая на их равновесие в законе.

Функция – это модель, выраженная в явном виде, относительно неизвестной. Поэтому при записи функции знак модели «=» меняется на знак «:=». Функция – частный вид модели.

Отсталость языков программирования состоит в том, что в программировании до сих пор используется нотация функции. Языки создавались под физику времени, но не под физику пространства (время программируют, пространство проектируют). И языки программирования в своем большинстве не оперируют моделями, уравнениями. Решение систем уравнений появляется не как конструкция языка, а как процедура. Оперировать моделями в языках программирования невозможно или неудобно. Хотя окружающий мир описывается именно свойствами и сущностями – уравнениями.

Второй, преодолеваемый уже постепенно недостаток языков программирования, - глагольный язык (делай 1, делай 2, …). Постепенно вводится язык описания сущностей (ООП). Полностью второй недостаток пока не преодолен, так как в них нет алгебры прилагательных (свойств объектов).

В записи системы уравнений, модели содержатся все возможные функции, алгоритмы, поведения.

Следствие 9.

Задача поиска закономерности (формулы) во множестве данных (чисел) в итоге сводится к классификации битовых строк в виде уравнения c минимальным количеством переменных в записи

Пример базы данных, приведенной к двоичному виду.

Так как для m примеров существует 2^m вариантов классификации, что приводит к очень быстрому росту функции при увеличении значения m, то на практике учитывается ограниченное число примеров.

Чем больше примеров, тем компактнее классификация (если, конечно, она содержится изначально в исходных данных).

При добавлении примеров частные случаи отсеиваются, закон становится более общим.

Конечно, можно в качестве таблицы подсунуть алгоритму ID3 в виде примеров случайные комбинации. В таких таблицах в принципе нет закономерностей. Обнаружит ли ID3 что-то?

Обнаружит, но закон будет таким же длинным, как сама таблица. Закон не сожмет данные. То есть, «законы в пределе информативности это данные».

Белый шум (случайные таблицы) не дает компактных классификаций. Если закономерности нет, то закон найти не удастся. В этом случае знания равны данным, дерево не сжимается.

Закономерности характеризуются количеством сущностей и связей между ними. Подсчитайте количество переменных (элементов) в законе и число операций (связей) с ними – получится оценка сложности закона. Фундаментальные законы максимально просты.

Закон тем более ценен, чем более общим он является. Самые общие законы содержат минимум переменных и операций (F=ma, E=mc²), конечно, если они описывают примеры правильно и таких примеров много.

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

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

Рисунок - От болта к модели двигателя, далее к модели машины, к эволюции рядов машин и к заводу-автомату по производству машин – цифровые двойники в одном компьютере. Цифровой двойник – модель, система уравнений, описывающая ВСЕ возможные свойства и поведения проектируемого устройства

Программирование сводится к сортировкам.

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

Рисунок – Изображение дерева решений в виде пространства признаков-свойств, областей и их границ-правил

Очевидна закономерность в расположении областей (ответов)

Кредит = (Дд>35)*(1-(К=П)) (для области Риск=«Н»).

Рисунок – Примеры из исходной базы данных обозначены черными точками (слева), предсказания по формуле – зеленые точки 15 и 16 (справа)

Следствие 10.1

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

Пример – смешаем две жидкости и рассмотрим свойства смеси.

Следствие 10.2

Противоречия в примерах говорят о необходимости расширения базиса. Необходимо рассматривать большее количество входных переменных, признаков (концептов).

Пример

На лицо противоречие в базе данных между первой и второй записями.

Однако, если дополнить систему удачным признаком, то конфликт будет разрешен.

Следствие 10.3

При выводе можно использовать как Modus ponens (правило подтверждающее), так и Modus tollens (правило отвергающее). Чаще используют Modus ponens, однако это чревато опасными последствиями.

Modus ponens – даже 100 подтверждающих примеров не доказывают правдивость вывода. Когда-то появится 101 пример и опровергнет все.

Более ценны контрпримеры, поскольку один контрпример отменяет неверное правило (или его часть).

«Лучше принять палку за змею, чем змею за палку» - хорошая иллюстрация преимущества правила вывода Modus tollens.

Разница «авантюриста» и «консерватора».

Пример.

Modus ponens: А, А->В >> В

«Идет дождь», ЕСЛИ «Идет дождь», ТО «Земля мокрая» >> «Земля мокрая».

Однако: из того, что «Земля мокрая», вовсе не следует, что «Идет дождь». Почему? Потому что Земля может быть мокрой из-за других причин, например, «Пролили воду из ведра».

И еще, из утверждения, что НЕ «Идет дождь», не следует, что «Земля НЕ мокрая». Опять же из-за того, что при сухой погоде могут пролить воду из ведра и земля будет мокрой.

Получается, что к следствию С может вести много причин: ИЛИ П1, ИЛИ П2, ИЛИ П3. И по следствию догадаться, какая из причин сработала, невозможно.

Пример.

Modus tollens: НЕ В, А->В >> НЕ А

«Земля НЕ мокрая», ЕСЛИ «Идет дождь», ТО «Земля мокрая» >> Не верно, что «Идет дождь».

И это безусловная правда, если «земля не мокрая», то «дождя точно не было», иначе дождь бы замочил землю.

Раз следствия С нет, то ни одна из причин не сработала, в том числе и П1.

Следствие 11. Энтропия дерева вопросов и ответов

Подсчитаем сколько неопределенности содержится в изначальной таблице.

Рисунок – Энтропия, содержащаяся в исходной примере (базе данных)

Во втором ярусе (дерево еще построено не до конца, вся информация еще не получена) в дереве содержится (-0.5) бит энтропии. Выбор кредитной истории во втором ярусе оставляет недостроенным дерево в ветке Доход (15-35), неопределенность остается.

В третьем ярусе дерево построено полностью, неопределенность равна 0. В окончательном дереве содержится 0 бит энтропии, вся информация получена.

Рисунок – Уменьшение энтропии по мере построения дерева

При переходе от Дохода к Кредитной истории энтропия упала с -1.52 до -0.5, то есть получено 1.52-0.5=1.02 бит информации. При переходе от Кредитной истории к вопросу про Долг получено 0.5 бит информации, а энтропия (неопределенность) стала равна нулю.

E+I=0.

Энтропия Е переходит в информацию I, приобретение информации уменьшает (гасит) энтропию, а потеря информации увеличивает энтропию системы.

В сумме энтропия и информация в закрытой активной системе постоянны и могут переходить друг в друга.

В открытой системе энтропия может и расти, и падать. В такой системе значение const – ы меняется.

В закрытой консервативной (пассивной) системе энтропия только растет. Большой вопрос: с какой скоростью и отчего эта скорость зависит.

dE/dI=кпд.

Процесс перехода E в I – индукция, обобщение, нахождение некоторого порядка в хаосе, выявление закономерности, переход от «числа» (факта) к «букве-операции-уравнению» (модели), проявление интеллектуальности.

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

Следствие 12. Генетическая связь алгоритма ID3 с регрессионной моделью

Перекодируем содержание таблицы числами в непрерывной области.

Кредитная история – {0,1,2}={П,Н,Х}

Долг – {0,1}={В,Н}

Поручители – {0,1}={Н,А}

Доход – {0,1,2}={0-15,15-35,>35}

Риск – {0,1,2}={Н,С,В}

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

Таблица – Экспериментальная база данных

Из ранее построенного дерева можно пока предположить, что признак Доход влияет на Риск в 2 раза сильнее, чем Кредитная история.

Формула Риск = 2*Доход + Кредитная история дает:

Риск={5,6} – Низкий, {4} – Средний, {0,1,2,3} – Высокий.

Дальнейшая нормализация дает: Р=0*(Риск>=5)*(Риск<=6)+1*(Риск=4)+2*(Риск<=3)

или Р=(Риск=4)+2*(Риск<=3)

или Р=((2*Доход+Кредитная история)=4)+2*((2*Доход+Кредитная история)<=3).

Проверьте эту формулу на всех 14 примерах, сравнив ее результат со значениями Риск в таблице при соответствующих значениях аргументов Доход и Кредитная история.

Примечание 1: иногда вывод закона требует нелинейной формулы.

Рисунок – График функции Риска в системе координат «Доход-Кредитная история» при кодировании: Доход – {0,1,2}={0-15,15-35,>35} и Кредитная история – {0,1,2}={П,Н,Х}

Примечание 2: результат зависит от способа кодирования.

Задача: нахождение наилучшей кодировки и наиболее компактной модели-закона, описывающей табличные данные-факты.

Повторение пройденного «Как построить регрессионную модель»

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

Y = A₀ + A₁ • X₁ + … + A_m • X_m.

Рисунок – Обозначение многомерного черного ящика на схемах

Так как подразумевается, что мы имеем экспериментальные данные о всех входах и выходах черного ящика, то можно вычислить ошибку между экспериментальным (Y_i^Эксп.) и теоретическим (Y_i^Теор.) значением Y для каждой i-ой точки (пусть число экспериментальных точек равно n):

Ei = (Y_i^Эксп. – Y_i^Теор.), i = 1, …, n;

E_i = Y_i – A₀ – A₁ • X_1i – … – A_m • X_mi, i = 1, …, n.

Минимизируем суммарную ошибку F:

Ошибка F зависит от выбора параметров A₀, A₁, …, A_m. Для нахождения наилучших значений коэффициентов А у функции Y найдем экстремум (минимум) суммарной ошибки F. Для этого приравняем все частные производные F по неизвестным A₀, A₁, …, A_m к нулю:

Получим систему из m + 1 уравнения с m + 1 неизвестными, которую следует решить, чтобы определить коэффициенты линейной множественной модели A₀, A₁, …, A_m. Для нахождения коэффициентов методом Крамера представим систему в матричном виде:

Далее вычисляем коэффициенты A₀, A₁, …, A_m.

В нашем случае предполагая гипотезу о связи переменных

Риск = f ( КИ, Долг, Поручители, Доход)

в виде линейной формы:

Риск = А0+А1*КИ+А2*Долг+А3*Поручители+А4*Доход (модель 1),

имеем систему уравнений в матричном виде (таблица).

Рисунок - Матричная запись системы уравнений модели 1

Решая систему уравнений относительно вектора неизвестных (A0, A1, A2, A3, A4) методом Крамера, имеем:

А0=2,5; А1=-0.36; А2=-0.25; А3=-0.13; А4=-0.80 или

Риск = 2.5 - 0.36*КИ - 0.25*Долг - 0.13*Поручители - 0.80*Доход (модель 1),

Проверим это решение, сопоставив его с исходной экспериментальной таблицей.

Таблица – Сравнение базы данных с результатами модели 1

Выводы. Отметим, что практически во всех случаях (3-14 примеры) мы имеем совпадение результата, вычисленного по построенной регрессионной модели, с экспериментальными данными. Исключениями являются 1 и 2 пример таблицы. Тем не менее, приглядевшись, можно увидеть, что тенденцию и результат модель вычисляет правильно, увеличив риск в первом случае и уменьшив его во втором (первый случай действительно хуже второго, поэтому риски выдачи кредита увеличиваются). То есть модель действует точнее, чем эксперт. Аналоговая модель точнее дискретной.

Примечание. Значения коэффициентов регрессионной модели, которые мы нашли, указывают на вес (значимость) отдельных признаков для принятия правильного решения. Наиболее значимы по убыванию величины коэффициента: 0.80 > 0.36 > 0.25 > 0.13, то есть Доход -> КИ -> Долг -> Поручители. Заметим, что их порядок совпадает со значимостью (важностью), определенной ранее нами методом ID3.

Но ID3 дополнительно указал на отсутствие необходимости вносить в решение признака Поручители. Если в регрессионном моделировании мы сами указываем возможно необходимые признаки, то метод ID3 делает это за нас, минимизируя автоматически их количество. Метод ID3 сам определяет размерность пространства признаков.

Преимуществом регрессии является ее аналоговость. Такая модель может показать, например, сколько вносит в решение одна единица Дохода и чем ее можно компенсировать.

Например, одна единица Дохода стоит сразу всех вместе взятых по дополнительной единице переменных КИ, Поручители и Долг: 0.8*1≈0.36*1+0.25*1+0.13*1. Или единица Дохода примерно соответствует двум единицам КИ: 0.8*1≈0.36*2.

Такая информация дает возможность исследовать чувствительность модели. Соответственно, по значениям коэффициентов регрессии можно судить, какими признаками можно пожертвовать при упрощении модели в первую очередь.

Всё более грубые модели:

Риск=А0+А1*Доход+А2*КИ+А3*Долг+А4*Поручители

Риск=А0+А1*Доход+А2*КИ+А3*Долг

Риск=А0+А1*Доход+А2*КИ

Риск=А0+А1*Доход

Риск=А0

Теперь решим еще раз этот же пример, упростив гипотезу. Так как ранее было показано, что определяющими входными признаками в этом примере являются «Доход» и «Кредитная история», то построим регрессионную модель от этих двух переменных:

Риск = f (КИ, Доход).

Предполагая гипотезу о связи переменных в виде

Риск = А0+А1*КИ+А2* Доход,

Рисунок - Матричная запись системы уравнений модели 2

Решая систему уравнений относительно вектора неизвестных (A0, A1, A2), имеем: А0=2,4; А1=-0.30; А2=-0.85 или

Риск = 2.4 - 0.30*КИ - 0.85*Доход (модель 2)

Важно! Посмотрите на значения коэффициентов модели 2 и сравните их со значением коэффициентов модели 1. Обратите внимание на то, что значения коэффициентов второй модели изменились по сравнению со значениями коэффициентов первой модели, округлились.

Снова проверим решение второй модели, сопоставив его с исходной экспериментальной таблицей.

Таблица – Сравнение базы данных с результатами модели 2

Выводы. Отметим, что практически во всех случаях (1, 3-14 примеры) мы имеем совпадение результата, вычисленного по построенной регрессионной модели, с экспериментальными данными. Исключением является пример 2. Тем не менее, приглядевшись, можно увидеть, что тенденцию и результат модель и в этом случае вычисляет правильно. Сравните также примеры 2 и 3, которые на усеченном множестве идентичных входных данных (КИ и Дд) различны. Огрубление модели привело к выявлению противоречия в исходной базе данных. При одних и тех же исходных данных значение выходной переменной Риск – различно. Кроме этого, доказано, что живой эксперт упрощал модель своего решения (в примере 1 модель ИИ стала совпадать с мнением эксперта после упрощения предметной области).

Таблица – Противоречия огрубленной базы данных

Однако, метод с честью вышел из создавшегося затруднения.

Построим график полученной функции.

Рисунок – График функции Риска в осях «Кредитная история» и «Доход»

График полученной функции: Риск = 2.4-0.3*КИ-0.85*Доход весьма похож на ранее приведенный график Риск = 2*Доход + Кредитная_история, но «пытается» идти более вертикально. График имеет вид семейства параллельных прямых, каждая из которых соответствует различным значениям переменной Риск = {0,1,2}.

Примечание.

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

Примеры ситуаций, в которых был использован алгоритм ID3

• 1. США, Чикаго, больница «Кук Каунти». Узкое место: очереди к узким врачам, ложный начальный диагноз, больной попадает не к тому врачу.
  Решение: введение доврачебного осмотра - попытка разгрузить очередь к узким специалистам. Задача: найти базовые симптомы, повышающие вероятность правильного предварительного диагноза.
  Решение – введение ЭКГ и уменьшение остальных анализов с 5 до 3 увеличило число правильных диагнозов с 75% до 90% и уменьшило очереди к узким специалистам.
• 2. США, Пентагон. Виртуальные военные учения на суперкомпьютере. Специалисты запутались в громоздкой системе. Выиграла простота - мотоциклы (оперативная связь) и малые катера (против авианосцев).
• 3. Оптимальная организационная структура департамента. Оптимизация нагрузки на сотрудников с учетом равномерности распределения дел между ними, их способностей и эффективности принятия решений каждым из них. Оптимизация документооборота. Сортировка документов по важности.
• 4. Можно составить модель (формулу) человека на основе его ответов на вопросы. Актуальная проблема – прогноз поведения человека по его информационному портрету в социальной сети. Предсказание очагов напряженности по информации в социальной сети. Управление обществом через социальную сеть.

Вывод.

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

Формула Искусственного интеллекта – найти закономерность в окружающем мире и применить ее для раннего обнаружения и обхода будущих проблем (польза и безопасность), что снижает риски. Польза меряется в кпд и использует усилители.

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

Задание

Постройте нейросеть, которая выдает те же результаты {Высокий, Средний, Низкий} на входные воздействия-рецепторы: Доход, Кредитная история, Долг, Поручители. Приведите схему нейросети. Постройте и приведите геометрию разбиения пространства в координатах рецепторов сети.

Выведите формулу нейронной сети, покажите, что формула минимальной сети совпадает с формулой минимального дерева и регрессионной моделью. Какова мощность (размеры) такой нейронной сети?

Возьмите за основу какой-нибудь пример (не менее 4-5 значений выходной переменной Y, не менее 7-8 признаков, входных переменных (x1, x2, x3, …), влияющих на решение).

Опишите, что означают выбранные классы и признаки.

Следя за экспертом, запишите решения Y эксперта в нескольких случаях и значения известной при этом информации (x1, x2, x3, …), не менее 20 строк в таблице экспериментов (то есть принятых решений).

Рассчитайте дерево. Постройте по дереву логическую функцию (уравнение, модель). Спрогнозируйте новую строку таблицы, неизвестную эксперту ранее.

Приведите геометрическую интерпретацию решения.