Классификация документов методом опорных векторов

Потребовалось мне года три назад сделать классификатор текстов. В этой статье я расскажу о том как это заработало и вообще некоторые аспекты реализации и тестирования таких алгоритмов.

Классификация


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

Думаю, тут нет нужды расписывать зачем это нужно, ведь классификация документов давно используется в информационном поиске, в поиске плагиата, и так далее.

Коллекция


Для обучения классификатора (если наш классификатор обучаемый) нужна некоторая коллекция документов. Впрочем, как и для тестов.
Для этого существуют различные тестовые коллекции текстов, которые в основном можно легко найти в интернете. Я использовал коллекцию RCV1 (Reuters Corpus Volume 1). Эта коллекция отсортированных вручную новостей агентства Reuters за период с августа 1996 по август 1997 года. Коллекция содержит около 810000 новостных статей на английском языке. Она постоянно используется для разнообразных исследований в области информационного поиска и обработки текстовой информации.

Коллекция содержит иерархические категории (один документ может относится к разным категориям, например к экономике и к нефти одновременно). Каждая категория имеет свой код, и эти коды уже приписываются новостям (всего около восьмидесяти категорий). Например, во главе иерархии стоят четыре категории: CCAT (Corporate/Industrial), ECAT (Economics), GCAT (Government/Social), и MCAT (Markets).
Полный список категорий можно посмотреть здесь.

Теперь разберемся с еще несколькими важными моментами. Во-первых, для обучения классификатора неплохо бы еще сделать стемминг текстов и выбросить стоп-слова.
  • Стемминг. Нам при классификации не важно, как написано слово «нефть» («нефть», «нефти», «нефтяной», «нефтяные») — мы всё равно поймем что это о нефти. Приведение слов к одному виду и называется стеммингом. Для стемминга текстов на английском языке есть готовые решения, например вот эта реализация алгоритма Портера. Эта библиотека написана на java в Indiana University и распространяется свободно. На русском языке не искал, может быть тоже что-то есть.
  • Стоп-слова. Тут всё понятно. Слова «и», «но», «по», «из», «под» и так далее, ну никак не влияют на классификацию, так как они встречаются везде. На практике обычно берут некоторое количество самых популярных слов в коллекции и выбрасывают их (числа тоже можно выбросить). Можно просто взять список отсюда.

Подобная обработка — уже устоявшийся способ уменьшения размерности задачи и улучшения производительности.

Метод опорных векторов


Теперь абстрагируемся от текстовых документов и рассмотрим один из существующих алгоритмов классификации.
Не буду здесь грузить деталями и математическими выкладками. Если они интересны, то их можно найти, например, в википедии или на Хабре.
Расскажу вкратце.
Допустим, что у нас есть много точек в n-мерном пространстве, и каждая из точек принадлежит только одному из двух классов. Если мы сможем разделить их как-то на два множества гиперплоскостью размерностью n-1, то это сразу решит проблему. Так случается не всегда, но если множество линейно разделимо то нам повезло:

image

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

image

Для поиска используется простоя идея: построить две параллельные гиперплоскости, между которыми нет никаких точек множества и максимизировать расстояние между ними. Ближайшие к параллельным гиперплоскостям точки называются опорными векторами, которые и дали название методу.
А что делать, если множества не является линейно-разделимым? Тем более, что скорее всего это так. В этом случае, мы просто позволяем классификатору делить множества так, чтобы между гиперплоскостями могли оказываться точки (отсюда появляется погрешность классификатора, которую мы пытаемся минимизировать). Найдя такую гиперплоскость, классификация становится делом техники: надо посмотреть с какой стороны от гиперплоскости оказался вектор, класс которого нужно определить.

Готовая реализация


Конечно, можно реализовать алгоритм самому. Но если есть хорошие готовые решения, то это может привести к трате большого количества времени, и не факт что Ваша реализация окажется лучше или хотя бы такой же.
Есть отличная реализация support vector machine под названием SVM light. Она создана в Техническом Университете Дортмунда и распространяется бесплатно (только для исследовательских целей). Есть несколько вариантов реализации (например, умеющий обучаться на реляционных базах данных), но можно взять самый простой, работающий с текстовыми файлами. Такой классификатор состоит из двух исполняемых файлов — обучающего и классифицирующего модулей.

Обучение

Обучающий модуль принимает на вход текстовый файл с обучающими данными. Файл должен содержать вектора с меткой +1 или -1 в зависимости от того, какому из двух классов он принадлежит.
Выглядит это так:
-1 0 0 0 0 0 0 6 0 0 0 6.56 0 0 0 0 0 0 0 45.56 0 0 0 0 0 0.5 0 0 0 0 0 0 0
Так же модуль поймет и такую запись:
-1 7:6 11:6.56 19:45.56 25:0.5 (то есть можно перечислить только ненулевые значения с указанием индекса).

Классификация

Второй модуль принимает на вход текстовый файл с данными, которые нужно классифицировать. Формат такой же, что и для обучения. После классификации создается res.txt в котором записаны результаты.

svm для классификации документов


Теперь разберемся, как можно применить svm к классификации документов. Откуда взять вектора? Как определить к каким категориям относится наш документ, если всего их 80, а svm умеет определять только принадлежность к одному из двух классов?

Документ — это вектор

Представить документ в виде вектора не сложно. Сначала нужно сделать словарь коллекции — это список всех слов, которые в этой коллекции встречаются (для коллекции RCV1 это 47 000 слов). Количество слов и будет размерностью векторов. После этого документ представляется в виде вектора, где i-тый элемент это мера вхождения i-того слова словаря в документ. Это может быть + 1 или -1 в зависимости от того, входит ли слово в документ или нет, или количество вхождений. Или «доля» этого слова в документе. Вариантов много. В итоге получаются вектора большой размерности, где большая часть элементов — нули.

80 категорий — 80 классификаторов

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

Тесты. Метрики


Для тестирования классификатора можно использовать часть той же самой коллекции (только тогда не стоит использовать эту часть при обучении) сравнивая результаты классификатора с результатами, полученными вручную.
Для оценки работы классификаторов используются несколько метрик:
  • Accuracy = ((r — kr) + kw)/n
    Фактически — это точность.
  • Precision = kr/n
  • Recall = kr/r

Здесь kw — количество документов, которые классификатор неправильно отметил как не относящиеся к искомой категории.
kr — количество документов, которые классификаторов правильно отметил как относящиеся к искомой категории.
r — общее количество документов, относящихся к искомой категории по мнению классификатора.
n — общее количество документов, относящихся к искомой категории.

Из этих метрик Precision и Recall являются самыми важными, так как они показывают как сильно мы ошиблись приписав документу категорию и насколько вообще наш классификатор беспорядочно работает. Чем ближе обе метрике к единице — тем лучше.

И небольшой пример. Составив вектора, взяв как меру слова в документе его «долю» (количество вхождений слова в документ деленное на общее количество слов в документе), и обучив классификатор на 32000 документов и при классификации 3000, получились следующие результаты:
Precision = 0.95
Recall = 0.75

Неплохие результаты, с ними классификатор вполне можно использовать для обработки новых данных.

Ссылки


Про RCV1:
О RCV1
Здесь можно найти коллекцию
Про SVM:
Википедия
Большая статья
Support the author
Share post

Comments 20

    +2
    За статью спасибо, но есть одно замечание.

    > А что делать, если множества не является линейно-разделимым? [...] мы просто позволяем классификатору делить множества так, чтобы между гиперплоскостями могли оказываться точки.

    С теоретической точки зрения это не имеет смысла. Если множество не разделимо, то алгоритм просто не сможет построить разделяющую гиперплоскость — какие точки тогда считать опорными векторами? Как с этим поступают на практике в популярных реализациях (SVMLight, LibSVM), честно говоря, не знаю. Но в прикладной программе для обработки линейно неразделимых образцов используют сложные нелинейные ядра, например, полиномиальное ядро. Правда для текста это не актуально — 47000 атрибутов как правило более чем достаточно, чтобы разделить любые документы даже используя линейное ядро.
      +3
      Спасибо за замечание!
        +2
        Как на практике решается проблема нелинейности я также сказать не смогу, но помимо смены ядра есть еще один метод. Было доказано, что любую линейно не разделимую задачу можно свести к линейной путем перехода в другое пространство. Например, из декартовых координат можно перейти к полярным. Впрочем, это можно «сыметировать» использовав другое ядро.
          0
          На сколько я понимаю, ядро как раз таки пространство и «искривляет», хотя это с какой стороны посмотреть — дуализм :)
            0
            Вот я тоже в этом неочень уверен. )
            0
            да, это так и делается в svm. используются ядра более высокого порядка.
            но как уже выше было сказано при очень большом количестве атрибутов и относительно маленьком количестве документов линейное ядро показывает такие же результаты
          +1
          Яндекс также писал про классификацию со сравнением с SVM Light на Яндекс Каталоге:
          download.yandex.ru/company/experience/rcdl2008/rcdl_sites_autoclassification.pdf

          Также интересная работа:
          download.yandex.ru/company/grant/2005/08_Petrov_103106.pdf
            0
            А вот это уже очень интересно! Почитаю обязательно.
              0
              Тогда ещё советую погуглить «site:download.yandex.ru классификация» — много всего познавательного.
            0
            > Документ — это вектор… это список всех слов
            Нужно добавить, что метод работает не только для слов, но и для n-грамм, например, биграмм.
            И это существенно повышает точность. При этом, естественно, при переходе к биграммам объем словаря растет.
            • UFO just landed and posted this here
                0
                лучше использовать libSVM так как она поддерживает мультиклассовость — то есть входной файл содержит не +1/-1, а номер класса для каждого документа, который вы хотите классифицировать. таким образом вам не нужно 80 классификаторов. а всего лишь 2 файла — для обучения и для тестов

                далее, неразумно в качестве свойста использовать +1/-1 для классификации документов. так как у вас из обычного очень разреженного вектора из например 500 значений (500 features), получится вектор из полного списка (47тыс в вашем примере* количество оцениваемых свойств) значений, большая часть которых просто неинформативна — забита -1. или я вас в этом моменте неправильно поняла?

                очень рекомендую к прочтению в этом контексте данную статью — A Practical Guide to Support Vector Classication

                и по поводу того, какие свойста имеет смысл оценивать в документе — есть так называемые distributional features, которые как раз таки используются для классификации текстов. и если вы знаете о них, то стоило в статье их и описать и назвать своими названиями, можно даже с формулами :) а не обобщенно «доля слова в документе» и т.п.

                но в целом приятно было встретить на хабре данную статью.
                  0
                  зато можно классифицировать документ по нескольким категориям
                    0
                    ошиблась кнопочкой — ответ
                    0
                    неразумно в качестве свойста использовать +1/-1 для классификации документов. так как у вас из обычного очень разреженного вектора из например 500 значений (500 features), получится вектор из полного списка (47тыс в вашем примере* количество оцениваемых свойств) значений, большая часть которых просто неинформативна — забита -1. или я вас в этом моменте неправильно поняла?

                    Если я правильно понял Ваш вопрос, то отвечу: из 500 значений переходить к 47000 приходится для соблюдения размерности. А как иначе? Да, они получаются разряженные, и забиты нулями (не -1), но так уж приходится делать.
                    За статью спасибо.
                      +1
                      «После этого документ представляется в виде вектора, где i-тый элемент это мера вхождения i-того слова словаря в документ. Это может быть + 1 или -1 в зависимости от того, входит ли слово в документ или нет»

                      Я к сожалению не вникала в то как именно работает svmlight, но есть подозрение что структуры там частино одинаковые. это значит, что вы передаете туда компактный вектор:
                      7:6 11:6.56 19:45.56 25:0.5. то есть только те значения, которые не равны нулю.

                      Если же вы будете делать как у вас написано в статье +1/-1, то у вас получится вектор с кучей -1 вместо нулей. и вместо того чтобы передавать вектор из 500 значений, вы будете передавать вектор из 47тысяч. Это как бы совсем нелогично и для данного типа классификации не используется. И поэтому я подумала, что либо вы не совсем точно описали в статье что вы хотите сказать этим «i-тый элемент = +1/-1», либо я вас просто не поняла.

                      Кстати, только что заметила, что например у вас в примере очень разрозненные данные. 19 элемент — 45, 25 — меньше 1! В данном случае просто необходимо делать нормализацию, скалирование. Об этом кстати тоже написано в той статье по моей ссылке.
                        0
                        Если же вы будете делать как у вас написано в статье +1/-1, то у вас получится вектор с кучей -1 вместо нулей. и вместо того чтобы передавать вектор из 500 значений, вы будете передавать вектор из 47тысяч. Это как бы совсем нелогично и для данного типа классификации не используется.

                        Да, согласен! Я написал это для примера, понятно что на практике так делать не стоит.

                        В данном случае просто необходимо делать нормализацию, скалирование.

                        Да, я знаю про это. Для эксперимента я брал долю слова в документе, и значения находились в пределах от 0 до 1 (единица, конечно, не достигалась, поэтому значения нормализовывались).
                    0
                    кто вам мешает это сделать в libSVM? :)
                      0
                      вы не подскажете, где скачать этот корпус целиком? на самой странице нашёл ссылки только результаты обработки…

                    Only users with full accounts can post comments. Log in, please.