Ниже представлены демки, которые демонстрируют классификацию точек на двухмерной плоскости — определение цвета точки, базируясь на значениях её координат (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 и т.п.), так и динамические атрибуты, указывающие на степень соответствия содержимого сайта поисковому запросу.
В локальном хранилище браузера можно сохранять историю кликов пользователя — каждому клику будет соответствовать вектор атрибутов. На этих векторах можно обучать классификатор (который тоже хранить локально), и с его помощью ранжировать результаты поиска на стороне клиента.
Возможно это поможет обеспечить баланс между анонимностью и ранжированием результатов в соответствии со вкусами пользователя.
ссылка на оригинал статьи http://habrahabr.ru/post/208952/
Добавить комментарий