О задачах классификации

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

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

Возможно, кому-то это определение покажется слишком общими или академическим, поэтому лучше наверное рассмотреть задачу классификации на примерах. А примеров хоть отбавляй.

Они повсюду

Пожалуй самый яркий пример автоматической классификации – это фильтрация спама. Каждый день на мой ящик падает десятки если не сотни спам-писем, которые автоматически отфильтровываются из моего inbox’а.

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

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

Safari Reader Mode является еще одним примером где используются алгоритмы классификации для достижения конечной цели. Суть этого режима работы браузера заключается в том что он позволяет автоматически убрать со страницы всю шелуху не имеющую отношения к сути контента страницы².

Так же классификация используется в задачах face detection’а и face recognition’а.

Классификация используется как инструмент для решения множества других задач:

• снятие омонимии при обработке натуральных языков;
• в поисковых системах – для ограничения области поиска в целях повышения точности (вертикальный поиск);
• автоматическое определение языка на котором написан текст;
• анализ тональности (определение эмоциональной окраски текста).

Этот список можно продолжать еще долго. Например, в медицине алгоритмы классификации используются для реконструирования 3D модели головного мозга по серии МРТ снимков³, а также для диагностики пациентов страдающих синдромом Альцгеймера⁴.

Традиционные подходы

Rule based classification

Если говорить о задаче классификации текстов, то пожалуй ее традиционным решением является классификация основная на правилах (rule based classification). Вы имплементируете правила определения класса документа по его тексту в виде if-then-else выражений (код на Scala).

def classify(text: String) =
	if (text.contains("виагра") || text.contains("бухгалтер")) "SPAM" else "NOT SPAM"

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

• для того чтобы выбрать значимые для классификации слова необходимо обладать экспертными знаниями в предметной области. Есть ли у вас например соображения по поводу ключевых слов которые хорошо отличают документы посвященные финансовой тематике от документов экономической? У меня очень смутные;
• отнюдь не всегда факт наличия или отсутствия какого-либо одного слова является решающим фактором для принятия решения.

Поподробней остановлюсь на последнем пункте. Если вернуться к задаче определения спама и немного подумать о том какие слова являются хорошими классификационными признаками (classifying feature), то станет понятно что нет такого слова наличие которого гарантировало бы что сообщение является спамом. Возможно, в пределах компании производящей силденафил в промышленных масштабах слово “виагра” не является показательным признаком спам-сообщения, кто знает.

В общем, суть такова: любое из известных спам-слов пусть редко но встречается в повседневной жизни. Поэтому, принимать окончательно решение основываясь на факте наличия или отсутствия какого-либо одного слова идея контрпродуктивная. Мы можем усложнять правила добавляя вложенные if‘ы. Но довольно быстро вы поймете что возможности человека в формулировании таких правил очень ограничены, потому что сложность правил растет экспоненциально с количеством выбранных для классификации слов.

Weight based classification

Мы можем пойти другим путем. Мы можем для каждого слова выбрать некий вес, который будет означать насколько вероятно что сообщение с этим словом является спамом (0 – никогда не является спамом, 1 – всегда спам).

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

def classify(text: String) = {
	val weights = Map("бухгалтер"->0.9, "виагра"->0.99, "выгодное"->0.7, "github"->0.01)
	val words = text.split(' ').filter(weights.contains(_))
	val P_spam = words.map(weights(_)).reduce(_ * _)
	val P_not_spam = words.map(1 - weights(_)).reduce(_ * _)
	if (P_spam > P_not_spam) "SPAM" else "NOT SPAM"
}

Мы берем каждое слово и определяем суммарный вес документа отдельно для класса “спам” и класса “не спам”. Суммарный вес определяется как произведение весов всех известных слов документа. Слова для которых у нас нет веса мы пропускаем при классификации. Какой суммарный вес оказался больше тот класс и побеждает.

Это более разумный подход, так как он более гибок и принимает решение на основании всех известных слов в тексте. Так же его гораздо проще сопровождать чем полотна if‘ов.

Метод машинного обучения

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

Если быть более точным, то описанный мною метод является зародышем наивного байесовского классификатора. Но не позволяйте названию обмануть вас, NBC (Naïve Bayes Classifier) если не самый, то один из самых часто используемых классификаторов. Тому есть ряд причин:

• он прост в имплементации и тестировании;
• процесс обучения довольно эффективен по сравнению с другими более сложными классификаторами;
• на небольших корпусах документов разница между NBC и другими гораздо более сложными алгоритмами классификации зачастую несущественна, а иногда NBC может оказаться и более точным⁵.

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

Ссылки по теме