В этой статье мы попытаемся рассказать о проблеме множественной классификации на примере решения задачи автоматической расстановки поисковых тегов для текстовых документов в нашем проекте www.favoraim.com. Хорошо знакомые с предметом читатели скорее всего не найдут для себя ничего нового, однако в процессе решения этой задачи мы перечитали много различной литературы где о проблеме множественной классификации говорилось очень мало, либо не говорилось вообще.
Итак, начнем с постановки задачи классификации. Пусть X — множество описаний объектов, Y — множество номеров (или наименований) классов. Существует неизвестная целевая зависимость — отображение 
, значения которой известны только на объектах конечной обучающей выборки 
. Требуется построить алгоритм 
, способный классифицировать произвольный объект x∈X. Однако более распространенным является вероятностная постановка задачи. Пусть X — множество описаний объектов, Y — множество номеров (или наименований) классов. На множестве пар «объект, класс» X×Y определена вероятностная мера P. Имеется конечная обучающая выборка независимых наблюдений 
, полученных согласно вероятностной мере P.
Теперь перейдем к задаче автоматической расстановки поисковых тегов. У нас имеется объект x – текстовый документ и множество классов 
– поисковых тегов. Каждому документу нужно поставить в соответствие один или несколько поисковых тегов. Например у нас есть событие с заголовком «Концерт группы Apocalyptica», данному событию можно присвоить следующие поисковые теги: «Apocalyptica», «концерт», «heavy metal», «виолончель» и т.п. Также у нас имеется обучающая выборка, т.е. набор документов с уже расставленными поисковыми тегами. Таким образом, у нас есть задача классификации с пересекающимися классами, т.е. объект может относиться одновременно к нескольким классам. Но вместо этого мы будем решать N задач бинарной классификации, каждую пару 
классифицируем на классы {0,1}, т.е. определяем, можно ли поставить поисковый тег 
документу x или нет.
Для решения данной задачи мы будем представлять текстовые документы в виде «bag of words» или многомерного вектора слов и их веса (частота встречаемости) в документе (http://en.wikipedia.org/wiki/Bag-of-words_model). На рис. 1 показана гистограмма слов описания бизнес-тренинга, на рис. 2 – гистограмма слов описания мастер-класса по фотографии.
В качестве метода классификации можно взять любой статистический (Байесовский) метод классификации. Вероятностная модель для классификатора — это условная модель 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 раз. На практике использовать данный прием проблематично, т.к. вычисления занимают очень много времени.
ROC-кривая обладает следующими основными характеристиками. Чувствительность (sensitivity) – это и есть доля истинно положительных случаев. Специфичность (specificity) – доля истинно отрицательных случаев, которые были правильно идентифицированы моделью. Заметим, что fpr=100-specifity. Площадь под ROC-кривой (AUC). Значение AUC обычно используют для оценки качества классификатора. Например, зависимость fpr=tpr соответствует худшему случаю (случайное гадание). На рис. 3 худший случай обозначен пунктирной линией. Чем выше плотность, тем более качественные предсказания дает классификатор. Для идеального классификатора график ROC-кривой проходит через верхний левый угол.
Теперь нужно выбрать минимальный отсекающий порог. Тут существует 3 подхода.
- Требование минимальной величины чувствительности (специфичности) модели. Т.е. одно из значений задается константно и, исходя из этого, подбирается значение отсекающего порога.
- Требование максимальной суммарной чувствительности и специфичности модели.
- Требование баланса между чувствительностью и специфичностью, т.е. когда specificity≈sensivity. Тут порог – это точка пересечения двух кривых, когда по оси x откладывается порог отсечения, а по оси y – чувствительность и специфичность модели (рис. 4).
Таким образом, мы можем присвоить нашему документу 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 вычисляется по формуле 
, где P(t) – вероятность того что встретится тег t, 
– лексемы документа d включая повторения. Вероятность P(t) можно оценить как 
, где 
– это количество документов в обучающей выборке с тегом t, а N – количество всех документов в обучающей выборке. Оценка вероятностей P(l│t) с помощью обучающего множества происходит следующим образом 
, где 
– количество вхождений лексемы l во все документы с тегом t, а 
– количество всех лексем во всех документах с тегом 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: требование максимальной суммарной чувствительности и специфичности модели, думаю найти его труда не составит. На этом пожалуй все, если будут вопросы или пожелания, пишите, я с радостью на них отвечу.
