29 January 2014

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

JavaScriptProgrammingData Mining
В качестве практического приложения к предыдущей статье, хочу предоставить крошечную 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)
Tags:деревья принятия решениймашинное обучение
Hubs: JavaScript Programming Data Mining
+45
30.9k 322
Comments 26
Popular right now
Data Scientist
from 150,000 to 300,000 ₽NZT GroupМосква
Разработчик информационной системы (backend)
from 80,000 ₽ГК “Северный Путь”Санкт-ПетербургRemote job
Специалист по машинному обучению (Machine Learning)
from 20,000 to 60,000 ₽БастионМоскваRemote job
Senior ML Engineer
from 4,000 to 5,500 $HyprrRemote job
Middle/Senior Software Engineer
from 100,000 ₽dicehub GmbH - GermanyRemote job
Top of the last 24 hours