В этом и следующих постах, я хочу на пальцах описать процесс создания простого классификатора текстовых документов, а также рассказать о некоторых нетипичных с обывательской точки зрения подходах используемых при классификации документов.
Классификатор – это алгоритм соотносящий некие входные данные с одним или несколькими классами. В отличие от алгоритмов кластеризации эти классы должны быть определены заранее.
Возможно, кому-то это определение покажется слишком общими или академическим, поэтому лучше наверное рассмотреть задачу классификации на примерах. А примеров хоть отбавляй.
Пожалуй самый яркий пример автоматической классификации – это фильтрация спама. Каждый день на мой ящик падает десятки если не сотни спам-писем, которые автоматически отфильтровываются из моего inbox’а.
Современные коммерческие системы способны успешно фильтровать спам с точностью превышающей 99%1. Другим довольно типичным примером классификации служит автоматическое определение тематики того или иного текста. Некоторые новостные аггрераторы используют подобный подход для группировки новостей в направления: экономика, политика, общественная жизнь и т.д.
Зачастую классификация является фундаментом на котором строятся алгоритмы решения более сложных задач. Например, классификация используется при создании рекомендательных систем и в частности при реализации коллаборативной фильтрации.
Safari Reader Mode является еще одним примером где используются алгоритмы классификации для достижения конечной цели. Суть этого режима работы браузера заключается в том что он позволяет автоматически убрать со страницы всю шелуху не имеющую отношения к сути контента страницы2.
Так же классификация используется в задачах face detection’а и face recognition’а.
Классификация используется как инструмент для решения множества других задач:
Этот список можно продолжать еще долго. Например, в медицине алгоритмы классификации используются для реконструирования 3D модели головного мозга по серии МРТ снимков3, а также для диагностики пациентов страдающих синдромом Альцгеймера4.
Если говорить о задаче классификации текстов, то пожалуй ее традиционным решением является классификация основная на правилах (rule based classification). Вы имплементируете правила определения класса документа по его тексту в виде if-then-else
выражений (код на Scala).
def classify(text: String) =
if (text.contains("виагра") || text.contains("бухгалтер")) "SPAM" else "NOT SPAM"
Этот подход может быть хорошим вариантом если вы работаете с небольшой коллекцией документов которую вы способны охватить и тщательно проанализировать. Просто потому что вы четко контролируете правила по которым классификатор принимает решения. Но есть у этого подхода и очевидные минусы:
Поподробней остановлюсь на последнем пункте. Если вернуться к задаче определения спама и немного подумать о том какие слова являются хорошими классификационными признаками (classifying feature), то станет понятно что нет такого слова наличие которого гарантировало бы что сообщение является спамом. Возможно, в пределах компании производящей силденафил в промышленных масштабах слово “виагра” не является показательным признаком спам-сообщения, кто знает.
В общем, суть такова: любое из известных спам-слов пусть редко но встречается в повседневной жизни. Поэтому, принимать окончательно решение основываясь на факте наличия или отсутствия какого-либо одного слова идея контрпродуктивная. Мы можем усложнять правила добавляя вложенные if
‘ы. Но довольно быстро вы поймете что возможности человека в формулировании таких правил очень ограничены, потому что сложность правил растет экспоненциально с количеством выбранных для классификации слов.
Мы можем пойти другим путем. Мы можем для каждого слова выбрать некий вес, который будет означать насколько вероятно что сообщение с этим словом является спамом (0 – никогда не является спамом, 1 – всегда спам).
spam | not spam | |
---|---|---|
бухгалтер | 0.99 | 0.01 |
виагра | 0.99 | 0.01 |
выгодное | 0.70 | 0.30 |
github | 0.01 | 0.99 |
В этой таблице перечислены гипотетические веса для четырех слов. Сумма значений в строке должна быть равна единице. Тогда наша классификация может выглядеть следующим образом:
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) если не самый, то один из самых часто используемых классификаторов. Тому есть ряд причин:
В последующих заметках я более детально опишу вопросы связанные с созданием и тестированием подобного классификатора. Подписывайтесь на RSS.
Automatic classification of MRI images for three-dimensional volume reconstruction by using general regression neural networks ↩
Automatic classification of patients with Alzheimer’s disease from structural MRI: a comparison of ten methods using the ADNI database ↩
On the Optimality of the Simple Bayesian Classifier under Zero-One Loss ↩