Автоматическая рубрикация текстов Text categorization Manning и др. Введение в информационный поиск гл. 13, 14

Задачи классификации

Рубрикация текстов Классификация/рубрикация информации – отнесение порции информации к одной или нескольким категориям из конечного множества рубрик Применение: –Навигация по коллекции документов –Поиск информации –Замена сложного запроса –Иерархическое упорядочение знаний предметной области Анализ распределения документов по тематике –Фильтрация потока текстов: Тематический сбор новостей Персонализированная фильтация потока текстов Фильтрация спама Тематический сбор информации из интернет

Примеры рубрикаторов Каталог Интернет-сайтов: Open Directory Project – dmoz.org –4,830,584 sites, 75,151 editors, over 590,000 categories –Сетевая структура, ссылки между рубриками

Каталог Яндекс – Фасетная классификация Тематическая –Иерархический классификатор, имеет порядка 600 значений и описывает предметную область интернет-ресурса Регион –230 географических облас тей. Определяется географическим расположением представляемого объекта, сферой управления и влияния, потенциальной аудиторией информации или информационным содержанием ресурса Жанр –художественная литература; научно-техническая литература; научно- популярная литература; нормативные документы; советы; публицистика Источник информации –Официальный, СМИ, Неформальный, Персональный Анонимный Адресат информации –Партнеры, Инвесторы, Потребители, Коллеги Сектор экономики –Государственный, Коммерческий, Некоммерческий

Рубрикатор нормативно-правовых актов Президентский классификатор (Указ ) Иерархия рубрик рубрик Все НПА рубрицируются экспертами в обязательном порядке

Методы рубрицирования текстов Ручное рубрицирование Полуавтоматическое Автоматическое –Инженерный подход (=методы, основанные на знаниях, экспертные методы) –Методы машинного обучения

8 Тестирование автоматической рубрикации: Точность P и полнота R 8 P = TP / ( TP + FP) R = TP / ( TP + FN)

9 Комбинированная мера: F 9

10 Усреднение: Micro vs. Macro 10 Посчитали меру оценки (F 1 ) for one class. Как агрегировать оценки F1 для многих классов. Macroaveraging - макроусреднение Посчитать F 1 для каждого из C классов Среднее арифметическое для этих C чисел Microaveraging - микроусреднение Посчитать TP, FP, FN для каждого из C classes Суммировать эти С чисел для каждого показателя Посчитать F 1 для суммированных TP, FP, FN

Коллекция и рубрикатор Reuters для тестирования автоматического рубрицирования Более 21 тысячи информационных сообщений из области биржевой торговли и слияния предприятий Массив разделен на две части: документы для обучения, документы для тестирования Большинство текстов имеют рубрики, проставленные людьми Основные рубрики: 135 без иерархии Примеры рубрик: Золото (товар), Свинец (товар), Кофе и др. товары, Торговля Средняя длина текста слова

Ручное рубрицирование Высокая точность рубрицирования –Обычно процент документов, в которых проставлена явно неправильная рубрика, чрезвычайно мал (если работают специалисты) –Могут быть существенные различия между специалистами в рубрицировании близких документов Низкая скорость обработки документов Используется: –Парламентские службы, –Looksmart, about.com, ODP, PubMed –Библиотеки (УДК)

Автоматическая рубрикация: Инженерный подход Основное предположение: рубрикатор создается осмысленно, содержание рубрики можно выразить ограниченным количеством понятий в виде формулы Эксперты описывают смысл рубрики в виде булевских выражений, правил продукции Construe system (Hayes) –Reuter news story –674 рубрики: 135 тематических рубрик + география… –4 человеко-года –94 % полноты и 84 % точности на 723 текстах

Reuters: пример описания рубрики if (wheat & farm) or (wheat & commodity) or (bushels & export) or (wheat & tonnes) or (wheat & winter and (¬ soft)) then WHEAT else (not WHEAT)

Автоматическая рубрикация: Методы машинного обучения Имеется коллекция отрубрицированных людьми текстов. Для каждой рубрики имеется множество положительных и отрицательных примеров

Методы машинного для задачи автоматической рубрикации Метод Байеса (Naive Bayes ) Метод Roccio Метод ближайшего соседа (k-Nearest Neighbors – knn) Метод опорных векторов (Support-vector machines – SVM) !!Должно быть размечено достаточное количество данных.

Классификаторы на основе пространства векторов

Векторная модель Преобразование множества текстов в векторы пространства R n Пословная модель – bag of words Удаление стоп-слов (предлоги, союзы…), которые заданы списком Приведение к нормальной морфологической форме (stemming, лемматизация – приведение к словарной форме) Определение весов слов Построение вектора слов документа

Вычисление весов слов Частота встречаемости слова в документе Количество документов коллекции, содержащих данное слово Длина документа, средняя длина документов коллекции => формула TF*IDF tf D (t) = freq D (t) idf(t) = log( |c|/df(t) )

Классификация на основе пространства векторов Документы – вектора, точки в векторном пространстве Предположения: – Документы одного класса находятся в одной области пространства –Документы из разных классов находятся в непересекающихся областях –Таким образом: нужно найти разделяющую поверхность

21 Документы в векторном пространстве Government Science Arts Sec.14.1

22 Документ относится к какому классу? Government Science Arts Sec.14.1

23 Тема документа - Правительство Government Science Arts Верна ли гипотеза Как найти хорошие разделяющие поверхности? Sec.14.1

Положительные и отрицательные примеры: как лучше отделить

Метод Rocchio в автоматической рубрикации Manning et al. Introduction to information retrieval Гл. 14

Метод Rocchio (relevance feedback) Применяется для расширения запроса пользователя –Пользователь задает запрос –Система выдает документы –Пользователь отмечает релевантные (нерелевантные) документы –Слова из релевантных документов вносятся в запрос –Имеющиеся примеры для рубрики – это как бы релевантные документы

Начальный запрос/результаты Initial query: New space satellite applications , 08/13/91, NASA Hasnt Scrapped Imaging Spectrometer , 07/09/91, NASA Scratches Environment Gear From Satellite Plan , 04/04/90, Science Panel Backs NASA Satellite Plan, But Urges Launches of Smaller Probes , 09/09/91, A NASA Satellite Project Accomplishes Incredible Feat: Staying Within Budget , 07/24/90, Scientist Who Exposed Global Warming Proposes Satellites for Climate Research , 08/22/90, Report Provides Support for the Critics Of Using Big Satellites to Study Climate , 04/13/87, Arianespace Receives Satellite Launch Pact From Telesat Canada , 12/02/87, Telecommunications Tale of Two Companies User then marks relevant documents with Sec

Расширенный запрос после учета слов в релевантных документах new space satellite application nasa eos launch aster instrument arianespace bundespost ss rocket scientist broadcast earth oil measure Sec

Использование Rocchio для классификации текстов Для документов в каждой категории вычисляем вектор- прототип: суммируем вектора всех примеров документов в категории –Прототип = центроид документов категории где D c – множество документов, отнесенных к категории С, v(d) - векторное представление документа Присваиваем тестовым документам категорию ближайшего по косинусной мере вектора-прототипа 29 Sec.14.2

Иллюстрация метода Rocchio 30 Sec.14.2

34 Аномалия метода Rocchio Prototype models have problems with polymorphic (disjunctive) categories. Sec.14.2

35 Свойства метода Rocchio Формирует простое обобщение примеров в данном классе (прототип). Вектор прототипа не нужно нормализовывать по длине, поскольку косинусная близость нечувствительна к длине вектора Классификация основана на сходстве с векторами- прототипами Не гарантируется, что классификации буду хорошо соответствовать обучающим данным Мало используется вне текстовой классификации - но может быть вполне эффективным при классификации текстов Дешевый метод для обучения и тестирования классификации Sec.14.2

Метод ближайших соседей (KNN)

37 Метод k ближайших соседей kNN = k Nearest Neighbor Чтобы классифицировать документ в класс c: определяем k-ближайших соседей документа d Для каждого класса С вычисляем количество документов i среди соседей, которые принадлежат С Оцениваем P(c|d) as i/k Выбираем класс: argmax c P(c|d) [ = majority class] Sec.14.3

38 Пример: k=6 (6NN) Government Science Arts P(science| )? Sec.14.3

39 Алгоритм: k ближайших соседей Использование только одного ближайшего соседа (1NN) ведет к ошибкам из-за: –нетипичных примеров –ошибок в ручной привязке единственного обучающего примера. Более устойчивой альтернативой является k наиболее похожих примеров и определение большинства Величина k is типично нечетная: 3, 5 (наиболее распространенные величины) Sec.14.3

40 kNN границы классов Government Science Arts Boundaries are in principle arbitrary surfaces – but usually polyhedra kNN gives locally defined decision boundaries between classes – far away points do not influence each classification decision (unlike in Naïve Bayes, Rocchio, etc.) Sec.14.3

41 Иллюстрация 3NN для текста в векторном пространстве Sec.14.3

42 3 NN vs. Rocchio Ближайшие соседи справляются с полиморфными категриями лучше, чем Rocchio

Линейные классификаторы. Классификатор SVM

44 Линейные классификаторы Проблема разделения документов на 2 класса –например, government and non-government –one-versus-rest классификация Как правильно определить разделяющую поверхность Как решить, к какой области относится тестовый документ? Sec.14.4

45 Разделение гиперплоскостями Сильное предположение – линейная разделимость (linear separability): –в двух измерения – линия –В больших измерениях – гиперплоскость –Сепаратор может быть выражен как ax + by = c Sec.14.4

46 Линейные классификаторы: Какая гиперплоскость? Множество возможностей для a, b, c. Некоторые методы ищут разделяющую гиперплоскость, но не оптимально Метод опорных векторов (SVM) находит оптимальное решение –Максимизирует расстояние между гиперплоскостью и трудными точками, близкими к границе раздела –Интуитивно: если нет точек около границы раздела, то нет и сложных (неопределенных) примеров This line represents the decision boundary: ax + by c = 0 Ch. 15

47 Другая интуиция С «толстым сепаратором» меньше вариантов поворота Sec. 15.1

48 Метод опорных векторов (SVM) Support vectors Maximizes margin SVMs maximize the margin around the separating hyperplane. A.k.a. large margin classifiers The decision function is fully specified by a subset of training samples, the support vectors. Solving SVMs is a quadratic programming problem Currently widely seen as as the best text classification method. Sec Narrower margin

Результаты на коллекции Reuters 49 Sec

Байесовская классификация. Наи́вный ба́йесовский классифика́тор простой вероятностный классификатор, основанный на применении Теоремы Байеса со строгими (наивными) предположениями о независимости.классификаторТеоремы Байесанезависимости Абстрактно, вероятностная модель для классификатора это условная модель

На практике мы заинтересованы лишь в числителе этой дроби, так как знаменатель не зависит от C и значения свойств F i даны, так что знаменатель константа. Числитель эквивалентен совместной вероятности моделисовместной вероятности

и т. д. Теперь начинаем использовать «наивные» предположения условной независимости:условной независимости

предположим, что каждое свойство F i условно независимо от любого другого свойства F j при. Это означает

Оценка параметров Все параметры модели могут быть аппроксимированы относительными частотами из набора данных обучения. Это оценки максимального правдоподобия вероятностей. Не дискретные свойства должны быть сначала дискретизированы. Если данный класс и значений свойства никогда не встречаются вместе в наборе обучения, тогда оценка, основанная на вероятностях, будет равна нулю. Это проблема, так как при перемножении нулевая оценка приведет к потере информации о других вероятностях. Поэтому предпочтительно проводить небольшие поправки во все оценки вероятностей так, чтобы никакая вероятность не была строго равна нулю.

Построение классификатора по вероятностной модели Наивный байесовский классификатор объединяет модель с правилом решения. Одно общее правило должно выбрать наиболее вероятную гипотезу; оно известно как апостериорное правило принятия решения (MAP). Соответствующий классификатор это функция classify, определённая следующим образом:

Заключение Задача автоматической классификации (рубрикации) Методы классификации Методы машинного обучения –Требуют последовательно размеченной коллекции примеров –Такую коллекцию непросто обеспечить при большом сложном рубрикаторе