Энтропия и деревья принятия решений

    Деревья принятия решений являются удобным инструментом в тех случаях, когда требуется не просто классифицировать данные, но ещё и объяснить почему тот или иной объект отнесён к какому-либо классу.

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

    Комбинаторная энтропия


    Рассмотрим множество разноцветных шариков: 2 красных, 5 зеленых и 3 желтых. Перемешаем их и расположим в ряд. Назовём эту операцию перестановкой:



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

    Если бы каждый шарик имел уникальный цвет, то количество перестановок было бы 10!, но если два шарика одинакового цвета поменять местами — новой перестановки не получится. Таким образом, нужно исключить 5! перестановок зеленых шариков между собой (а также, 3! желтых и 2! красных). Поэтому, в данном случае, решением будет:

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

    Все перестановки можно пронумеровать числами от 0 до (W — 1). Следовательно, строка из log2(W) бит однозначно кодирует каждую из перестановок.

    Поскольку перестановка состоит из N шариков, то среднее количество бит, приходящихся на один элемент перестановки можно выразить как:

    Эта величина называется комбинаторной энтропией:


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

    Энтропия Шеннона


    Давайте рассмотрим подробнее описанное выше выражение для энтропии:

    Учитывая свойства логарифмов, преобразуем формулу следующим образом:

    Предположим, что количество шариков достаточно велико для того чтобы воспользоваться формулой Стирлинга:

    Применив формулу Стирлинга, получаем:

    (где k — коэффициент перехода к натуральным логарифмам)

    Учитывая что выражение можно преобразовать:


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

    Данное выражение является энтропией Шенонна.

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

    Сравнение двух энтропий представлено на следующем рисунке, который рассчитан для множеств, содержащих два типа объектов — А и В (суммарное количество элементов в каждом множестве — 100):



    Термодинамика


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

    Понятие энтропии играет фундаментальную роль в термодинамике, фигурируя в формулировке Второго начала термодинамики: если изолированная макроскопическая система находится в неравновесном состоянии, то наиболее вероятным является её самочинный переход в состояние с большим значением энтропии:



    Демон Максвелла


    Чтобы подчеркнуть статистическую природу Второго начала термодинамики в 1867 году Джеймс Максвелл предложил мысленный эксперимент: «Представим сосуд, заполненный газом определённой температуры, сосуд разделен перегородкой с заслонкой, которую демон открывает чтобы пропускать быстрые частицы в одну сторону, а медленные — в другую. Следовательно, спустя некоторое время, в одной части сосуда сконцентрируются быстрые частицы, а в другой — медленные. Таким образом, вопреки Второму началу термодинамики, демон Максвелла может уменьшать энтропию замкнутой системы»:


    Позже, Лео Сциллард разрешил парадокс, но это обсуждение несколько выходит за рамки данной статьи.

    Демон Максвелла == Классификатор


    Если вместо «быстрых» и «медленных» частиц рассматривать объекты, принадлежащие к различным классам, тогда демона Максвелла можно рассматривать в качестве своеобразного классификатора.

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

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

    Для примера, рассмотрим множество двухцветных шариков, в котором цвет шарика зависит только от координаты х:
    (из практических соображений, при расчётах удобно использовать энтропию Шеннона)



    Из рисунка видно что если разделить множество на две части, при условии что одна часть будет содержать все элементы с координатой х ≤ 12, а другая часть — все элементы, у которых х > 12, то средняя энтропия будет меньше исходной на ∆S. Это значит, что данный предикат обобщает некоторую информацию о данных (легко заметить, что при х > 12 — почти все шарики жёлтые).

    Если использовать относительно простые предикаты («больше», «меньше», «равно» и т.п.) — то, скорее всего, одного правила будет недостаточно для создания полноценного классификатора. Но процедуру поиска предикатов можно повторять рекурсивно для каждого подмножества. Критерием остановки является нулевое (или очень маленькое) значение энтропии. В результате получается древовидный набор условий, который называется Деревом принятия решений:


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

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

    Также, не накладывается ограничений на значения атрибутов объекта — они могут иметь как категориальную, так и числовую или логическую природу. Нужно только определить предикаты, которые умеют правильно обрабатывать значения атрибутов (например, вряд ли есть смысл использовать предикаты «больше» или «меньше» для атрибутов с логическими значениями).

    Алгоритм построения дерева принятия решений


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

    s0 = вычисляем энтропию исходного множества
    
    Если s0 == 0 значит:
       Все объекты исходного набора, принадлежат к одному классу
       Сохраняем этот класс в качестве листа дерева
    
    Если s0 != 0 значит:
       Ищем предикат, который разбивает исходное множество таким образом чтобы уменьшилось среднее значение энтропии
       Найденный предикат является частью дерева принятия решений, сохраняем его
    
       Разбиваем исходное множество на подмножества, согласно предикату
       Повторяем данную процедуру рекурсивно для каждого подмножества
    

    Что значит «ищем предикат»?
    Как вариант, можно считать, что на основе каждого элемента исходного множества можно построить предикат, который разбивает множество на две части. Следовательно, алгоритм можно переформулировать:

    s0 = вычисляем энтропию исходного множества
    
    Если s0 == 0 значит:
       Все объекты исходного набора, принадлежат к одному классу
       Сохраняем этот класс в качестве листа дерева
    
    Если s0 != 0 значит:
       Перебираем все элементы исходного множества:
          На основе каждого элемента генерируем предикат, который разбивает исходное множество на два подмножества
          Рассчитываем среднее значение энтропии
          Вычисляем ∆S
       Нас интересует предикат, с наибольшим значением ∆S
       Найденный предикат является частью дерева принятия решений, сохраняем его
    
       Разбиваем исходное множество на подмножества, согласно предикату
       Повторяем данную процедуру рекурсивно для каждого подмножества
    

    Как можно «на основе каждого элемента множества генерировать предикат»?
    В самом простом случае, можно использовать предикаты, которые относятся только к значению какого-нибудь атрибута (например «x ≥ 12», или «цвет == жёлтый» и т.п.). Следовательно, алгоритм примет вид:

    s0 = вычисляем энтропию исходного множества
    
    Если s0 == 0 значит:
       Все объекты исходного набора, принадлежат к одному классу
       Сохраняем этот класс в качестве листа дерева
    
    Если s0 != 0 значит:
       Перебираем все элементы исходного множества:
          Для каждого элемента перебираем все его атрибуты:
             На основе каждого атрибута генерируем предикат, который разбивает исходное множество на два подмножества
             Рассчитываем среднее значение энтропии
             Вычисляем ∆S
       Нас интересует предикат, с наибольшим значением ∆S
       Найденный предикат является частью дерева принятия решений, сохраняем его
    
       Разбиваем исходное множество на подмножества, согласно предикату
       Повторяем данную процедуру рекурсивно для каждого подмножества
    


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

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

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

    Одним из возможных критериев остановки может быть небольшое значение ∆S. Но при таком подходе, всё же, невозможно дать универсальный совет: при каких значениях ∆S следует прекращать построение дерева.

    Random forest


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



    Полученный в результате ансамбль деревьев (упрощённая версия Random forest) можно использовать для классификации, прогоняя классифицируемый объект через все деревья. Каждое дерево как будто «голосует» за принадлежность объекта к определённому классу. Таким образом, на основе того, какая часть деревьев проголосовала за тот или иной класс — можно заключить с какой вероятностью объект принадлежит к какому либо классу.

    Данный метод позволяет достаточно адекватно обрабатывать пограничные области данных:



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

    Если есть желание поэкспериментировать


    Я создал небольшое приложение, для сравнения дерева принятия решений и random forest. При каждом запуске приложения создаётся случайный набор данных, соответствующий красному кругу на зелёном фоне, а в результате выполнения приложения получается картинка, типа той, которая изображена выше.

    • У Вас должна быть установлена среда выполнения Java
    • Загрузите отсюда бинарник dec_tree_demo.jar
    • Для запуска приложения наберите в командной строке: java -jar dec_tree_demo.jar out.png

    Исходники есть на гитхабе.

    Вместо заключения


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

    Дополнительная информация


    1. Яцимирский В.К. Физическая химия (здесь довольно неплохо описано понятие энтропии, а также рассматриваются некоторые философские аспекты данного феномена)
    2. Интересный тред про сжатие и энтропию на compression.ru
    3. Ещё одна статья о деревьях принятия решений на Хабре
    4. Toby Segaran, Programming Collective Intelligence (в данной книге есть глава посвящённая деревьям принятия решений, и вообще, если Вы ещё не читали этой книги — советую обязательно заглянуть туда :-)
    5. Такие библиотеки как Weka и Apache Mahout содержат реализацию деревьев принятия решений.


    Share post

    Similar posts

    Comments 14

      +2
      Божественно!

      А Вы не подскажете некие общие возможно эмпирические оценки относительно того, когда следует ограничить построение дерева (понятно что если в исходном множестве N-элементов, то выделение N-подмножеств смысла не несет)
        0
        Эмпирические можно получить самим, поварьировать параметры (например макс.глубина и минимальное кол-во элементов в листе), и посмотреть производительность с учетом сложности модели (советую почитать про bayesian information criteria и model selection в общем).
          +1
          Вообще для оценки сложности любой data mining модели (в том числе при построении деревьев принятия решения) — лучше использовать тесовую выборку (или кросс-валидацию). В этом случае как только пойдет переобучение тестовая выборка это покажет и можно остановить обучение.

          Однако, алгоритмы CART и оригинальный Random Forest, например, предпологает строить модель «до упора» — пока есть сплиты (конечно с заданными минимальнми размерами листьев). После чего, в CART используется так называемый pruning — удаления вершин из дерева на основе сложности (complexity) вершины и насколько эта вершина уменьшает энтропию (i.e. node improvement). В RandomForest же просто используються полные деревья — и усредненеием голосов убирается возможное переобучение, так как каждое дерево построено на случайной подвыборке данных.
            +1
            Если я правильно понял вопрос — Вас интересует как выбрать количество деревьев в ансамбле.
            Как уже отмечали, для этого полезно использовать выборку данных, которая не принимает участия в построении дерева — на ней будем тестировать качество классификатора.

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


            То есть, после некоторого порогового значения, увеличение количества деревьев перестаёт значительно увеличивать качество классификации. На этом количестве деревьев можно и остановиться.
              0
              спасибо
            +6
            попридираюсь :)

            Деревья принятия решений являются удобным инструментом в тех случаях, когда требуется не просто классифицировать данные, но ещё и объяснить почему тот или иной объект отнесён к какому-либо классу.

            Пробовали когда-нибудь интерпретировать то, что в деревьях принятия решений получается?) У отдельных деревьев (построенных одним из широко применяемых алгоритмов — ID3, C4.5, CART и тд) очень большая вариативность — при небольших изменениях в данных может получаться совершенно другое дерево; в таких условиях сложно говорить о какой-то интерпретации результатов. Ну т.е. интерпретировать можно; чуть данные изменились — совсем другое дерево и совсем другая интерпретация, смысл в такой интерпретации. Там не получается так, чтоб сверху дерева были более важные критерии. То, что вы же описали — это, вроде бы, ID3; у него точно те же проблемы — интерпретация работает только на примитивных примерах и редко работает в реальной жизни.

            Дальше, Random Forest. Их интерпретировать, разглядывая структуру деревьев, еще сложнее, т.к. вместо одного дерева имеем много деревьев (совсем разных).

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

            Т.е. на практике RF может быть более понятным для интерпретации, чем отдельные деревья принятия решений: для каждой фичи можно вычислить хотя бы ее «важность».
              0
              Спасибо за Ваши замечания :-)

              В общем, я с Вами согласен.

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

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

              В общем, я считаю, что многие подводные камни являются результатом специфики той или иной предметной области, в применении к которой используется классификатор.
                +1
                А какой объем данных обычно у Вас при решении реальных задач? И пробовали ли Вы использовать boostrapping с дереьвями принятия решений для оценки разброса (variance\confidence interval) предсказаний?
                +2
                Действительно, Leo Breinman пришел в RandomForest, а Jerry Friedman к TreeNet (Gradient Boosted Decision Trees) по причине неустойчивости CART алгоритма и слишком сильной дискретизации при решении задачи регрессии (хотя, конечно можно в каждом leaf строить регрессию для создания smooth predictions).

                Однако, у CART алгоритма есть такая же возможнсть оценить влияние переменных (фич) на результат. И в избравлении от неустойчивости очень помогает использование surrogates и competitors.

                Хотя, конечно, анасамбли деревьев позволяют использовать соврешенно другую машинерию — в том числе Dependency Plots — которая показывает частную производную по переменной полученной функции (см. как влияет изменения переменной на конечный prediction). Так же для Random Forest есть множество интересных post-processing техник — Parallel Coordinates, Proximity matrices которые позволяют глубже взглянуть на имеющиеся данные.
                +7
                У Вас — самый весёлый (или ехидный? ) демон Максвелла из тех что я видел :-). И без рожек.
                  0
                  Ну, допустим. А не подскажите, существуют ли какие-нибудь методы решения своего рода «обратной задачи». Когда известны классы и нужно понять по каким признакам объекты были отнесены к этим классам?
                    +1
                    Так а сами признаки есть? Если нет — то тут будет сложно что-то решить :)

                    Если же есть — то это ничем не отличается от обычной классификации — у вас есть признаки и классы — вы обучаете классификатор (к примеру дерево принятия решения) и получаете вашу зависимости классов от признаков. Другой вопрос — что при обратной задаче существует неоднозначность интерпретации — из серии человек в категории высокого риска потому что: у него возраст меньше 18 или больше 65, но это решать нужно используя какие-то доменные знания и возможно модифицируя переменные, к примеру создавая переменные вида «18<=возраст<=65?» в зависимости что получилось при построении классификатора и какой именно вид связи Вам нужен.
                      0
                      Спасибо.
                      Да, признаки есть. Суть задачи в следующем: Есть таблица базы данных с N полями и идентификатором. Идентификатор вычисляется на основе нескольких полей (бизнес-ключ), используя хеш-функцию. Хеш функция должна генерировать для одинаковых значений полей одинаковый хеш (так как это MD5). В результате чего-то неизвестного в определенный период времени мы обнаружили дубликаты: строчки с одинаковым бизнес-ключом, но разным идентификатором. Мы пытаемся понять, что могло послужить причиной такого поведения. Чтобы клиент не ворчал, мы обнули таблицу и перезагрузили таблицу заново, сохранив копию таблицы с дубликатами. В результате анализа мы обнаружили, что после новой перезагрузки таблицы, идентификаторы в тех строках, что дублировались стали совпадать с одним из дублировавшихся идентификаторов. Мы сравнили затем старую и новую таблицу и выяснили, что на самом деле иногда новые идентификаторы совпадают и со старыми. Таким образом, у нас есть два класса: строки с совпадающими идентификаторами в старых и новых таблицах и строки с разными идентификаторами. Наша задача, выявить какие-нибудь закономерности в полях, которые могли привести к в генерации «неправильных» хешей. Какие могут быть причины? Например, поплывшая кодировка у строковых полей (на самом деле, мы это проверили, но как пример), наличие пустых значений в некоторых полях (или групп полей).
                      Отладка довольно затруднительна, так как генерация ключа происходит в проприетарном продукте, поведение которого нам неизвестно точно. Поэтому мы хотим попытаться выявить какие-нибудь закономерности в строках, которые совпали и которые нет и в случае необходимости сообщить, например, вендору о нестабильности в его продукте, если таковые будут иметь место.
                      Поэтому меня вдохновила эта статья и я понадеялся, что реально провести соответствующий анализ.
                      Надеюсь, что удалось более мене подробно объяснить.
                        0
                        Если у Вас достаточно много таких записей, то можно собрать все записи, для которых ожидается одинаковый айдишник (но по факту айдишники разные) — это будет обучающая выборка. Пусть записи с разными айдишниками будут принадлежать разным классам. Затем, на основе данной выборки, можно построить дерево принятия решений.

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

                  Only users with full accounts can post comments. Log in, please.