Автоматическая расстановка поисковых тегов

В этой статье мы попытаемся рассказать о проблеме множественной классификации на примере решения задачи автоматической расстановки поисковых тегов для текстовых документов в нашем проекте www.favoraim.com. Хорошо знакомые с предметом читатели скорее всего не найдут для себя ничего нового, однако в процессе решения этой задачи мы перечитали много различной литературы где о проблеме множественной классификации говорилось очень мало, либо не говорилось вообще.

Итак, начнем с постановки задачи классификации. Пусть X — множество описаний объектов, Y — множество номеров (или наименований) классов. Существует неизвестная целевая зависимость — отображение 15aae4fb7e5052ee59893b56c67495c1, значения которой известны только на объектах конечной обучающей выборки 01eedfa4b9348c9faa76ce75cec26eb0. Требуется построить алгоритм 9b146d6bc74d3bea499caf31395f7279, способный классифицировать произвольный объект x∈X. Однако более распространенным является вероятностная постановка задачи. Пусть X — множество описаний объектов, Y — множество номеров (или наименований) классов. На множестве пар «объект, класс» X×Y определена вероятностная мера P. Имеется конечная обучающая выборка независимых наблюдений 01eedfa4b9348c9faa76ce75cec26eb01, полученных согласно вероятностной мере P.

Теперь перейдем к задаче автоматической расстановки поисковых тегов. У нас имеется объект x – текстовый документ и множество классов 6a5803fee18da3583ef23e5b14208d6d – поисковых тегов. Каждому документу нужно поставить в соответствие один или несколько поисковых тегов. Например у нас есть событие с заголовком «Концерт группы Apocalyptica», данному событию можно присвоить следующие поисковые теги: «Apocalyptica», «концерт», «heavy metal», «виолончель» и т.п. Также у нас имеется обучающая выборка, т.е. набор документов с уже расставленными поисковыми тегами. Таким образом, у нас есть задача классификации с пересекающимися классами, т.е. объект может относиться одновременно к нескольким классам. Но вместо этого мы будем решать N задач бинарной классификации, каждую пару a07338d124c5695f760215b28822a767 классифицируем на классы {0,1}, т.е. определяем, можно ли поставить поисковый тег 0df0c887052ed9ffbd2a3e33b2427353 документу x или нет.
Для решения данной задачи мы будем представлять текстовые документы в виде «bag of words» или многомерного вектора слов и их веса (частота встречаемости) в документе (http://en.wikipedia.org/wiki/Bag-of-words_model). На рис. 1 показана гистограмма слов описания бизнес-тренинга, на рис. 2 – гистограмма слов описания мастер-класса по фотографии.

2ed7cc6f3f1dcae43a1020cf5cf1c86a

7dd4efad5fd51b21cb084a55307b746d

В качестве метода классификации можно взять любой статистический (Байесовский) метод классификации. Вероятностная модель для классификатора — это условная модель p(y│d), y∈Y. Теперь нам нужно восстановить плотность p(y│d), y∈Y, т.е. вероятность того, что для нашего документа d можно поставить поисковый тег y∈Y. Для восстановления плотности существует множество методов, начать можно с наивной байесовской модели классификации документов (http://ru.wikipedia.org/wiki/Классификация_документов). Для этой модели делается «наивное» предположение о независимости встречающихся в документе слов, и, хотя это очевидно неверное предположение, модель работает достаточно неплохо. 
Теперь, когда мы восстановили плотность распределения и для каждого тега y∈Y нашли вероятность того, что его можно присвоить нашему документу d, нужно определить, какие из тегов нужно присвоить документу, а какие отбросить, т.е. найти минимальный отсекающий порог для вероятности p(y│d). Тут придется воспользоваться анализом ROC-кривой (http://www.machinelearning.ru/wiki/index.php?title=ROC-кривая).
ROC-кривая показывает зависимость количества верно классифицированных положительных примеров (true positive rate) от количества неверно классифицированных отрицательных примеров (false positive rate). При этом предполагается, что у классификатора имеется некоторый параметр, варьируя который, мы будем получать то или иное разбиение на два класса. Этот параметр часто называют порогом, или точкой отсечения. В нашем случае, в роли данного параметра будет выступать вероятность p(y│d). Строится ROC-кривая по контрольной выборке, которая обычно является частью обучающей выборки. При этом объекты контрольной выборки нельзя использовать для обучения классификатора, в противном случае мы можем получить излишне-оптимистичную ROC-кривую вследствие явления переобучения. Однако, если нам позволяют ресурсы, мы можем воспользоваться перекрестной проверкой (cross-validation). Суть ее заключается в том, что обучающая выборка разбивается на k частей, k-1 из которых используются для обучения модели, оставшаяся же часть используется в качестве контрольной выборки. Данная процедура выполняется k раз. На практике использовать данный прием проблематично, т.к. вычисления занимают очень много времени.

988b4937e52b7cf229d0c75c6c97fc37

ROC-кривая обладает следующими основными характеристиками. Чувствительность (sensitivity) – это и есть доля истинно положительных случаев. Специфичность (specificity) – доля истинно отрицательных случаев, которые были правильно идентифицированы моделью. Заметим, что fpr=100-specifity. Площадь под ROC-кривой (AUC). Значение AUC обычно используют для оценки качества классификатора. Например, зависимость fpr=tpr соответствует худшему случаю (случайное гадание). На рис. 3 худший случай обозначен пунктирной линией. Чем выше плотность, тем более качественные предсказания дает классификатор. Для идеального классификатора график ROC-кривой проходит через верхний левый угол.
Теперь нужно выбрать минимальный отсекающий порог. Тут существует 3 подхода.

  • Требование минимальной величины чувствительности (специфичности) модели. Т.е. одно из значений задается константно и, исходя из этого, подбирается значение отсекающего порога.
  • Требование максимальной суммарной чувствительности и специфичности модели.
  • Требование баланса между чувствительностью и специфичностью, т.е. когда specificity≈sensivity. Тут порог – это точка пересечения двух кривых, когда по оси x откладывается порог отсечения, а по оси y – чувствительность и специфичность модели (рис. 4).



fdfaaa342327706e836935d2903daace

Таким образом, мы можем присвоить нашему документу d те поисковые теги, для которых выполняется p(y│d) > c, где c – значение порога отсечения.

А теперь немного практики. Первое что нужно сделать – это преобразовать текст нашего документа к нормальной форме с удаление стоп-слов (например, normalized_string(«пример строки в нормальной форме») = «пример строка нормальный форма»). Для этих целей вполне подойдут FTS-словари postgreSQL. Дальше нам потребуется набор документов с уже проставленными тегами для обучения нашего классификатора. В качестве примера приведу псевдокод обучения байесовского наивного классификатора.

Map<String, Map<String, Integer>> naiveBayes;
for (Entry<String, String[]> entry: docSet)
{
    for (String lexem: get_normalized_string(entry.key).split(MY_DELIMS))
    {
        for (String tag: entry.value)
        {
            naiveBayes[tag][lexem]++;
        }
    }
}



Таким образом мы каждому поисковому тегу поставили в соответствие гистограмму лексем из документов нашей обучающей выборке. После того как классификатор обучен, можно переходить к подсчету вероятностей присутствия того или иного тега в новом документе. В наивной байесовской модели вероятность появления тега t для документа d вычисляется по формуле 2d20c19ef74b3209b1c39c2a472d19f2, где P(t) – вероятность того что встретится тег t, 04c7382c5c9e20ecf0378214831dfe31 – лексемы документа d включая повторения. Вероятность P(t) можно оценить как 65d6487516d0174f93db59f0027d0e2a, где 6334500a26658cad706f59b8f71eac1e – это количество документов в обучающей выборке с тегом t, а N – количество всех документов в обучающей выборке. Оценка вероятностей P(l│t) с помощью обучающего множества происходит следующим образом 3b7b289f361b4172af01f12fc832e07d, где 1127fff258918a71723a6166b4f1336b – количество вхождений лексемы l во все документы с тегом t, а bcef82ff55d803a1c4520c90a4ea1fcf – количество всех лексем во всех документах с тегом t. Чтобы избежать переполнения в формуле расчета вероятностей из-за большого числа сомножителей, на практике вместо произведения обычно используют сумму логарифмов. Логарифмирование не влияет на нахождение максимума, так как логарифм является монотонно возрастающей функцией.

Map<String, Double> probs;
for (String tag: naiveBayes.keySet())
{
    probs[tag] = log(P(t));
    for (String lexem: get_normalized_string(document).split(MY_DELIMS))
    {
        probs[tag] += log(naiveBayes[tag][lexem]/sum(naiveBayes[tag]));
    }
}



Остается построить ROC-кривую. В качестве псевдокода я, пожалуй, вставлю копипасту.

Канонический алгоритм построения ROC-кривой
Входы: L – множество примеров; f[i] – рейтинг, полученный моделью, или вероятность того, что i-й пример имеет положительный исход; min и max – минимальное и максимальное значения, возвращаемые f; dx – шаг; P и N – количество положительных и отрицательных примеров соответственно.

t=min
повторять
    FP=TP=0
    для всех примеров i принадлежит L {
        если f[i] >= t тогда // этот пример находится за порогом
            если i положительный пример тогда
                { TP=TP+1 }
            иначе // это отрицательный пример
                { FP=FP+1 }
    }
    Se=TP/P*100
    100_m_Sp=FP/N // расчет (100 минус Sp)
    Добавить точку (100_m_Sp, Se) в ROC кривую
    t=t+dx
пока (t>max)


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