LiteCoding

Заметки о программировании

Построение иерархических классификаторов на основе тщательно спроектированной системы тегов

without comments

Введение

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

Современные системы классификации страдают очевидным недостатком — отсутствием гибкости. Хорошо, когда предмет классификации досконально изучен, как, например, деление всего живого в биологии на 3 царства (животные, растения, грибы). Но вот происходит контакт с внеземной цивилизацией силикоидов, которых нельзя причислить куда-либо, и система классификации нуждается в изменениях. Конечно, я утрирую, но в динамично развивающихся областях знаний появление чего-то принципиально нового не такой уж и редкий факт. С другой стороны, отсутствие гибкости проявляется, когда нужно классифицировать элемент, входящий сразу в несколько категорий. Например, фильм «Назад в будущее» (1985) относится к жанрам фантастика и приключения. Иерархическая система в этом случае потребует выделения главного жанра.

С другой стороны, система тегов дает слишком большую свободу для пользователя. А т.к. педантичных и пунктуальных людей не так уж и много, в массе получается разброд и шатание (знаю, т.к. сам такой). Что же будет, когда системой тегов начнут пользоваться пять, восемь, тысяча человек? Все то же самое, только многократно преумноженное.

Идея

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

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

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

Гипотеза. Теги, встречающиеся с близкими частотами, являются категориями одного уровня вложенности соответствующего иерархического классификатора.

Реализация

И вот, самая интересная часть повествования. О том, как воплотить в жизнь все вышесказанное.

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

Недостатки

Описанный в предыдущем разделе алгоритм обладает следующими известными (да, есть еще и неизвестные мне) недостатками:

  1. Константы, определяющие параметр кластеризации и пороговое значение частоты вхождения тега придется подбирать вручную
  2. В настоящее время алгоритм непригоден для обработки разнородных характеристик элементов. Точнее, использовать его с такими входными данными можно, но в результате получится абсурдный классификатор
  3. Нет известной реализации данного алгоритма, потому его практическое применение пока невозможно

Заключение

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

Эту статью я написал в сентябре 2008 года для Хабра, и сразу выяснилось, что описанный алгоритм дает приемлемый результат только на специальным образом отобранных входных данных. Также в обсуждении мы выяснили, что его можно доработать, если учитывать и параметр «родства» тегов, которым в самом простом случае может выступить ковариация.

Share and Enjoy:
  • Print
  • Digg
  • Sphinn
  • del.icio.us
  • Facebook
  • Mixx
  • Google Bookmarks
  • LinkedIn
  • Tumblr

Written by Дмитрий Воробьев

Вторник, Февраль 15th, 2011 at 12:17

Posted in Статьи

Tagged with

Leave a Reply

You must be logged in to post a comment.