Деревья принятия решений на JavaScript

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


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


    Данные алгоритмы точно так же можно применить и для классификации объектов многомерного пространства. Объекты обучающей выборки могут содержать как числовые так и нечисловые атрибуты:

    В зависимости от типа атрибута используются различные предикаты для разбиения обучающего множества
    var predicates = {
       // предикат для нечисловых атрибутов
       '==': function (a, b) { return a == b },
       // например, группу людей можно разделить по цвету глаз:
       // в одну подгруппу поместим людей с зелёными глазами (цвет глаз == "зелёный"),
       // в другую группу - всех остальных
    
       // предикат для числовых атрибутов
       '>=': function (a, b) { return a >= b }
       // например, группу людей можно разделить по возрасту:
       // в одну подгруппу поместим людей, которым больше 18 лет (возраст >= 18),
       // в другую группу - всех остальных
    };
    


    Давайте рассмотрим использование данной библиотеки на игрушечном примере.

    Классификация персонажев из мультсериала Симпсоны


    Попытаемся определить пол персонажа, основываясь на таких признаках, как длина волос, возраст и вес.

    Обучающая выборка:
    Персонаж Длина волос (дюймы) Вес (фунты) Возраст Пол
    Гомер 0 250 36 М
    Мардж 10 150 34 Ж
    Барт 2 90 10 М
    Лиза 6 78 8 Ж
    Мэгги 4 20 1 Ж
    Эйб 1 170 70 М
    Сельма 8 160 41 Ж
    Отто 10 180 38 М
    Красти 6 200 45 М

    Формируем обучающую выборку средствами JavaScript
    var data = 
        [{person: 'Homer', hairLength: 0, weight: 250, age: 36, sex: 'male'},
         {person: 'Marge', hairLength: 10, weight: 150, age: 34, sex: 'female'},
         {person: 'Bart', hairLength: 2, weight: 90, age: 10, sex: 'male'},
         {person: 'Lisa', hairLength: 6, weight: 78, age: 8, sex: 'female'},
         {person: 'Maggie', hairLength: 4, weight: 20, age: 1, sex: 'female'},
         {person: 'Abe', hairLength: 1, weight: 170, age: 70, sex: 'male'},
         {person: 'Selma', hairLength: 8, weight: 160, age: 41, sex: 'female'},
         {person: 'Otto', hairLength: 10, weight: 180, age: 38, sex: 'male'},
         {person: 'Krusty', hairLength: 6, weight: 200, age: 45, sex: 'male'}];
    


    После чего — строим дерево принятия решений:

    Код для построения классификаторов
    var config = {
        // обучающая выборка
        trainingSet: data, 
    
        // название атрибута, который содержит название класса, к которому относится тот или иной элемент обучающей выборки
        categoryAttr: 'sex', 
    
        // масив атрибутов, которые должны игнорироваться при построении дерева
        ignoredAttributes: ['person']
        
        // при желании, можно установить ограничения:
    
        // максимальная высота дерева
        // maxTreeDepth: 10
    
        // порог энтропии, при достижении которого следует остановить построение дерева
        // entropyThrehold: 0.05
    
        // порог количества элементов обучающей выборки, при достижении которого следует остановить построение дерева
        // minItemsCount: 3 
    };
    
    // построение дерева принятия решений:
    var decisionTree = new dt.DecisionTree(config);
    
    // вот так можно пострить лес принятия решений:
    var numberOfTrees = 3;
    var randomForest = new dt.RandomForest(config, numberOfTrees);
    


    Теперь, с помощью построенных классификаторов можно классифицировать других персонажей мультфильма, например:

    Использование построенных классификаторов
    var comic = {person: 'Comic guy', hairLength: 8, weight: 290, age: 38};
    
    var decisionTreePrediction = decisionTree.predict(comic);
    // результатом классификации с использованием дерева принятия решений
    // является название класса, к которому следует отнести классифицируемый объект
    
    var randomForestPrediction = randomForest.predict(comic);
    // результатом классификации с использованием леса деревьев принятия решений
    // есть объект, полями которого являются названия классов, 
    // а значениями полей - является количество деревьев, которые "проголосовали" за то, 
    // что классифицируемый объект принадлежит к соответствующему классу
    //
    // таким образом - чем больше деревьев проголосовало за какой-то класс, 
    // тем больше вероятность того, что объект относится к данному классу
    


    Если визуализировать дерево, то можно заметить, что возраст не влияет на пол персонажей :-)


    Исходники библиотеки расположены на GitHub
    Ссылка на демку с классифкатором Симпоснов: jsfiddle.net/xur98
    Данные взяты из презентации: www.cs.sjsu.edu/faculty/lee/cs157b/ID3-AllanNeymark.ppt

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

    P.S.
    Мне сообщили, что в Хроме и Яндекс Браузере демки не работают.
    Браузеры, в которых я проверял демки: Safari 6.0 и 7.0, Firefox 8.0 и 26.0, Google Chrome 31.0 — в них должны работать.
    Постараюсь разобраться в чём проблема, и пофиксить.

    P.P.S.
    Пофиксил. Теперь демки должны работать и в Яндекс Браузере и в Хроме.
    Причина была в том, что к jsfiddle подключал JS код, который хостится на гитхабе (более подробное описание здесь: stackoverflow.com/questions/17341122/link-and-execute-external-javascript-file-hosted-on-github)
    AdBlock has stolen the banner, but banners are not teeth — they will be back

    More
    Ads

    Comments 26

      –1
      Интересная штука, думаю можно использовать в различных «играх» на сайтах или интерактиве!
        +1
        очень интересно описано, с этой темой до этого знаком не был. Но пример и демка выбраны таким образом, что стало ясно как это работает. Только пока не очень понятно, где бы можно было использовать эту штуку.
          0
          В общем случае, деревья принятия решений находят применение в качестве нелинейных классификаторов (из примеров, на ум приходит — оценка кредитоспособности клиентов в банке). Также, в сравнении с другими видами классификаторов, результаты классификации деревьев принятия решений легче интерпретировать — можно взглянуть внутрь дерева и проследить цепочку условий (правда, с практической точки зрения — здесь тоже имеются свои нюансы).

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

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

          0
          А ID3 деревья могут строить регрессии?
            0
            В качестве довольно грубого приближения — можно разбить ряд непрерывных значений на несколько классов (например, «очень маленькие значения», «маленькие значения», «большие значения» и т.д.). Затем, имея ограниченное число классов — можно использовать ID3 дерево. Правда, такую технику получится использовать лишь для прогнозирования трендов.

            А вообще, для регрессии, лучше посмотреть в сторону CART. На Хабре была статья, в которой упоминался данный метод: habrahabr.ru/post/116385/
              0
              Для работы с непрерывными значениями Куинлан (создатель ID3) предложил алгоритм C4.5. Дальше другие авторы еще развивали эту тему.
              Вообще, ID3 — это алгоритм построения дерева классификации. Для регресии, как сказали выше, лучше смотреть другие вещи.
              +3
              Чет т в хроме и IE 10 не пашет. FF и опера работает. Напишите, пожалуйста, поддерживаемые сейчас браузеры. А так весьма любопытно.
                0
                Проверял в Safari 6.0 и 7.0, Firefox 8.0 и 26.0, Google Chrome 31.0
                А что именно не пашет?

                Если честно, то в хроме и FF наблюдал проблемы с отображением очень больших деревьев.

                CSS для рисования дерева на основе вложенных списков — взят отсюда: thecodeplayer.com/walkthrough/css3-family-tree
                Но, поскольку с вёрсткой я фактически не работал раньше — то пофиксить стили для определённых браузеров у меня не получилось (
                  0
                  Пофиксил.
                  Теперь демки должны работать и в Яндекс Браузере и в Хроме (надеюсь, что и в IE тоже).

                  Причина была в том, что к jsfiddle подключал JS код, который хостится на гитхабе (более подробное описание здесь: stackoverflow.com/questions/17341122/link-and-execute-external-javascript-file-hosted-on-github)

                  Ссылки на демки обновил.
                  0
                  А насколько однозначным получается решение при обучающей выборке, не охватывающей весь диапазон десятка параметров, но охватывающей все возможные ветви (в некоторых ветвях некоторые значения не важны)? Есть ли вероятность, что набор, имеющий признаки как одной («синий»), так и другой («круглый») ветви, уйдёт не ту ветвь, которая в обучающей выборке была первой(ну или последней) — в общем можно ли как-то задавать приоритет одного набора параметров перед другим?

                  Вообще суть задачи: иметь человекочитаемые и машинообрабатываемые правила вычисления некоей дискретной функции, заданной десятком правил на естественном языке, но с чётким приоритетом одних над другими (срабатывает первое). Сейчас используется по сути полная таблица принятия решений (чуть уменьшенная за счет отсекания хвостовых параметров в некоторых случаях), обрабатываемая за один проход. Но читать или править её дюже неудобно. Идея обучающей выборки понравилась, но вот ложные срабатывания недопустимы, должен быть чёткий приоритет примеров.
                    +2
                    Советую почитать предыдущую статью автора.
                    Если кратко, то приоритет одного параметра перед другим четко определяется самой моделью через понятие энтропии. И порядок атрибутов обучающей выборки неважен. В этом, собственно, и состоит весь изюм этой модели: она сама определяет, какой атрибут наиболее важен на данной стадии, и разбивает обучающую выборку на подмножества по значениям этого атрибута. На следующем шаге анализ «важности» происходит снова, и каждое подмножество в свою очередь разбивается. И так до тех пор, пока в очередном подмножестве не окажутся только те объекты, которые принадлежат одному и тому же классу. В этот момент дальнейшее разбиение по этой ветке больше не нужно, потому что мы получили путь, эффективно классифицирующий эту часть изначальной выборки.

                    Если ваш вопрос касался того, что делать с ситуацией, когда в обучающей выборке могут оказаться противоречивые данные, то ответ прост: представленный алгоритм ID3 не обрабатывает такие ситуации. Дерево он, конечно, построит, но часть объектов из самой же обучающей выборке потом будут классифицироваться им с ошибкой, что естественно. Разумеется, существуют методы предварительной проверки данных на противоречивость, оценка достоверности и так далее. В реальных системах все это должно применяться в комплексе.
                      0
                      Нет, мой вопрос касался ситуации когда в обучающей выборке ровно один случай попадания под каждую категорию. Скажем, есть 5 булевых параметров, и есть таблица результатов типа
                      (1 1 1 0 0) => 1
                      (0 0 0 1 1) => 2
                      (0 0 0 1 0) => 3
                      (0 0 0 0 1) => 4
                      (0 0 0 0 0) => 5
                      При этом система должна «понять», что первые три параметра значимы только если все три установлены, и тогда игнорируются последние два, а иначе игнорируются первые три и значимы только последние два.
                        +1
                        Построил дерево решений для Вашего примера.
                        Судя по структуре дерева, значимыми являются только три параметра из пяти: x1, x4 и x5

                        Ссылка на демку: jsfiddle.net/H4jpA/



                        Таким образом, чтобы понять что объект принадлежит к классу «1» — достаточно всего двух параметров x1 и x4.
                          0
                          Опять проблема с подключением либы из гитхаба на jsfiddle (
                          Вот эта ссылка на демку, которая должна работать во всех браузерах: jsfiddle.net/ug4Hs/
                            0
                            Вообще полная таблица выглядит примерно так:
                            (1 1 1 * *) = 1
                            (* * * 1 1) => 2
                            (* * * 1 0) => 3
                            (* * * 0 1) => 4
                            (* * * 0 0) => 5
                            И первая запись имеет явный приоритет.
                            на псевдокоде это выглядит примерно так:
                            if (x1 == 1 && x2 == 1 && x3 == 1)
                              result = 1
                            else
                              if (x4 == 1)
                                if (x5 == 1)
                                  result = 2
                                else
                                  result = 3
                              else
                                if (x5 == 1)
                                  result = 4
                                else
                                  result = 5
                            

                            и (вроде) не допускает неоднозначных решений либо отсутствия решения (при условии, что параметры 0 или 1).
                              +1
                              Прекрасный пример!
                              По поводу дерева, которое представил stemm. У меня тоже получилось такое дерево (ура, наши модели написаны без ошибок! :). Но стоит заметить, что атрибуты Х2 и Х3 не то чтобы не имеют значения, они равнозначны (что очевидно) атрибуту Х1. В данном дереве везде вместо Х1 можно смело подставить, например Х2. Алгоритм просто выбрал первый по счету атрибут из равнозначных. Атрибуты Х4 и Х5 тоже равнозначны между собой (это тоже понятно уже по исходному виду таблицы), поэтому корнем дерева вполне мог бы быть и Х5.

                              Теперь по поводу полной таблицы:
                              (1 1 1 * *) => 1
                              (* * * 1 1) => 2
                              (* * * 1 0) => 3
                              (* * * 0 1) => 4
                              (* * * 0 0) => 5
                              Полная таблица как раз не совпадает с кодом :)
                              Строка (1 1 1 1 1) будет удовлетворять сразу классам 1 и 2. Псевдокод, конечно, распределит как надо, но обучаемая модель не поймет. В общем-то, никто не поймет, куда распределить строку из всех единиц, если не смотреть псевдокод.
                              Что интересно, если пройти по предложенному выше дереву, то мы попадем в нужный класс 2, но это будет почти что совпадение.
                              Если к таблице добавить строку (1 1 1 1 1)=2, то вид дерева не изменится.
                              Если к таблице добавить строку (1 1 1 1 1)=1, то дерево станет таким:

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

                                Потом я посмотрел еще раз псевдокод и обнаружил, что как раз-таки первоначальное дерево не соответствует вашему псевдокоду. Дерево, которое представил я, псевдокоду соответствовать будет, как раз из-за дополнительной строки в обучающем множестве: (1 1 1 1 1)=1.
                                  +1
                                  Полная таблица как раз не совпадает с кодом :) Строка (1 1 1 1 1) будет удовлетворять сразу классам 1 и 2.

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

                                  Первые три атрибута не то чтобы синонимы, просто их логическое сложение является по сути одним атрибутом и таблицу можно свести к виду:
                                  (1 * *) => 1
                                  (0 1 1) => 2
                                  (0 1 0) => 3
                                  (0 0 1) => 4
                                  (0 0 0) => 5
                                  

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

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

                              В общем случае модель для этого и предназначена. Но это не значит, что модель определит так же, как предполагаете вы. Для модели могут оказаться важными не первые три параметра, а, например, первый и четвертый.
                                0
                                Грубо говоря, обучающая выборка должна содержать полную таблицу вариантов, чтобы получить предсказуемый результат?
                                  +2
                                  Грубо говоря, да. А лучше, чтобы обучающая выборка была с пересекающимися данными. Модель для того и нужна, чтобы из кучи данных выявить тренд. Смотрите мой комментарий выше, я попытался показать на вашем же примере.
                          0
                          Отто же дрыщ, откуда в нём 180 фунтов? Там от силы 160.

                          //Я понимаю, что так дерево компактнее выходит, но всё же…
                            0
                            Закон Майерса
                            Если факты не подтверждают теорию, от них надо избавиться.
                            0
                            Спасибо, весьма интересная статья (а предыдущая — вообще блеск!). В своей диссертации я использовал деревья решений как основную модель для классификации. Тоже писал на javascript построение деревьев, вижу в представленной в статье библиотеке частично свой же по сути код, только лучше оформленный :) Приятно, что деревья решений удерживают определенный интерес. И, на мой взгляд, очень заслуженно.
                              0
                              А, если не секрет, почему Вы выбрали именно javascript в диссертации? Вы рассматривали какую-то задачу, которая должна решаться на стороне клиента, или просто симпатия к языку?
                                0
                                В первую очередь из-за симпатии к языку, а также из-за желания также разобраться в D3js.

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