1 Подготовка данных 9
1.1. Извлечение данных о таксономии и построение графа .... 9
1.2. Предварительная обработка 10
1.3. Векторная модель данных 11
1.4. Расширение описаний узлов 12
2 Классификация документов без учителя 14
2.1. Метод k-средних 16
2.2. Латентное размещение Дирихле 17
2.3. Построение отображения документов в таксономию 19
2.3.1. Косинусная мера 19
2.3.2. Дивергенция Дженсена-Шеннона 20
3 Реализация и эксперимент 21
3.1. Реализация автоматического классификатора 21
3.1.1. Алгоритм классификации на основе k-means 22
3.1.2. Алгоритм классификации на основе LDA 24
3.2. Эксперимент 26
3.3. Выводы из эксперимента 30
3.4. Дальнейшее направление исследования 31
Заключение 32
Список литературы 33
В настоящее время количество информации в свободном доступе увеличивается колоссальными темпами. Для упрощения навигации среди этих данных используют информационно-поисковые системы, методы ранжирования, рекомендательные системы и многое другое. Одним из подходов для упорядочения данных является построение каталога тем, рубрикатора, предметного указателя — это всё синонимы в рассматриваемом контексте. В каждой книге для удобства поиска нужной информации существует оглавление. Подобная иерархическая структура часто используется и для навигации на сайтах.
В сфере новостей проблема автоматической классификации особенно актуальна. Для повышения удобства читателей новостные сайты встраивают разделение новостей на рубрики и регионы. Самым тривиальным способом присвоения темы документу является ручная разметка тем. При таком подходе появляется ряд проблем. Во-первых, такая разметка будет весьма субъективна даже в пределах одного новостного ресурса. Журналисты могут по-разному воспринимать темы, к тому же могут допустить ошибку. Во-вторых, у каждого новостного агентства могут быть свои собственные наборы рубрик, что приведет к сложностям при создании рубрикатора новостным агрегатором.
Для решения данной проблемы может применяться автоматическая классификация в единую систему классов. Одной из таких систем является таксономия IPTC — таксономия медиа-тематик, предназначенная для упрощения обмена новостными данными. Международный совет по прессе и телекоммуникациям (англ. International Press Telecommunications Council, IPTC) — консорциум крупнейших мировых новостных агентств и других поставщиков новостей. IPTC выступает в качестве глобального органа стандартизации СМИ. Структура таксономии новостных тем является иерархической. Более детальное описание структуры можно увидеть в раз-деле 1.1. Существует два основных подхода для категоризации текстовых документов. Первый основан на изучении связей слов в предложении, использовании тезариуса языка и онтологии предметных областей. Второй подход рассматривает каждое слово или N-грамму как независимую единицу текста. В данной работе используется второй подход.
Новостные статьи и структуру таксономии сначала необходимо представить в пригодном для анализа виде. В работе используется модель векторного представления данных (англ. Vector Space Model, VSM). Об этом и о другой предварительной обработке данных речь пойдет в Главе 1.
Особенностью данной работы является отсутствие обучающей выборки. По этой причине становится невозможным использование классических классификаторов, таких как, наивный классификатор Байеса или метод k ближайших соседей. Для решения задачи используется кластеризация новостной коллекции с дальнейшим сопоставлением каждого кластера ближайшему в семантическом смысле узлу иерархической структуры. Пере-численные задачи рассматриваются в Главе 2.
В Главе 3 формально описываются разработанные алгоритмы авто-матической классификации. Эксперимент и проверка качества проведенной работы также описываются в третьей главе. В качестве тестовой коллекции была выбрана широко известная коллекция Reuters-21578. Коллекция состоит из новостей, опубликованных агентством новостей Reuters в 1987 г. Reuters — британская организация, основанная в 1851 г., является одним из ведущих поставщиков финансовой информации, а также новостей на общественно-политические темы.
В работе была поставлена задача разработать автоматический классификатор для новостных статей. Эта задача актуальна в связи с большим ростом данных и информационной потребностью интернет-пользователей. Для решения задачи были рассмотрены и реализованы метод кластеризации k-средних и латентное размещение Дирихле. Также были разработаны алгоритмы для построения отображения документов в таксономию медиа-тематик IPTC. Алгоритм, основанный на методе k-средних, показал лучшие результаты. Дальнейшие модификации этого метода могут привести к большей точности классификатора, а значит, могут быть включены в основной инструментарий новостных агентств и агрегаторов.
