В качестве практического приложения к предыдущей статье, хочу предоставить крошечную 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 | М |
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/9bvvD/
Данные взяты из презентации: www.cs.sjsu.edu/faculty/lee/cs157b/ID3-AllanNeymark.ppt
В качестве заключения хочу поделиться идеей о поисковой системе, которая ранжирует результаты поиска на стороне клиента.
В ответ на поисковый запрос возвращается список сниппетов. К каждому сниппету прикрепляется вектор атрибутов, описывающих соответствующий сайт. Это могут быть как статические атрибуты (среднее количество котиков на сайте, PageRank и т.п.), так и динамические атрибуты, указывающие на степень соответствия содержимого сайта поисковому запросу.
В локальном хранилище браузера можно сохранять историю кликов пользователя — каждому клику будет соответствовать вектор атрибутов. На этих векторах можно обучать классификатор (который тоже хранить локально), и с его помощью ранжировать результаты поиска на стороне клиента.
Возможно это поможет обеспечить баланс между анонимностью и ранжированием результатов в соответствии со вкусами пользователя.
Автор: stemm