В цьому і наступних постах, я хочу на пальцях описати процес створення простого класифікатора текстових документів, а також розповісти про деякі нетипових з обивательської точки зору підходах використовуваних при класифікації документів.
Класифікатор - це алгоритм співвідносить якісь вхідні дані з одним або декількома класами. На відміну від алгоритмів кластеризації ці класи повинні бути визначені заздалегідь.
Можливо, комусь це визначення здасться занадто загальними або академічним, тому краще напевно розглянути задачу класифікації на прикладах. А прикладів хоч відбавляй.
вони всюди
Мабуть найяскравіший приклад автоматичної класифікації - це фільтрація спаму. Кожен день на мою скриньку падає десятки якщо не сотні спам-листів, які автоматично фільтруються з мого inbox'а.
Сучасні комерційні системи здатні успішно фільтрувати спам з точністю перевищує 99% 1. Іншим досить типовим прикладом класифікації служить автоматичне визначення тематики того чи іншого тексту. Деякі новинні аггрератори використовують подібний підхід для угруповання новин в напрямку: економіка, політика, громадське життя і т.д.
Найчастіше класифікація є фундаментом на якому будуються алгоритми вирішення складніших завдань. Наприклад, класифікація використовується при створенні рекомендаційних систем і зокрема при реалізації коллаборатівной фільтрації.
Safari Reader Mode є ще одним прикладом де використовуються алгоритми класифікації для досягнення кінцевої мети. Суть цього режиму роботи браузера полягає в тому що він дозволяє автоматично прибрати зі сторінки все лушпиння не має відношення до суті контенту сторінки 2.
Так само класифікація використовується в задачах face detection'а і face recognition'а.
Класифікація використовується як інструмент для вирішення безлічі інших завдань:
- зняття омонімії при обробці натуральних мов;
- в пошукових системах - для обмеження області пошуку з метою підвищення точності (вертикальний пошук);
- автоматичне визначення мови на якому написаний текст;
- аналіз тональності (визначення емоційного забарвлення тексту).
Цей список можна продовжувати ще довго. Наприклад, в медицині алгоритми класифікації використовуються для реконструювання 3D моделі головного мозку по серії МРТ знімків 3. а також для діагностики пацієнтів страждають синдромом Альцгеймера 4.
традиційні підходи
Rule based classification
Якщо говорити про завдання класифікації текстів, то мабуть її традиційним рішенням є класифікація основна на правилах (rule based classification). Ви імплементіруете правила визначення класу документа по його тексту в вигляді if-then-else виразів (код на Scala).
Цей підхід може бути хорошим варіантом якщо ви працюєте з невеликою колекцією документів яку ви здатні охопити і ретельно проаналізувати. Просто тому що ви чітко контролюєте правила за якими класифікатор приймає рішення. Але є у цього підходу і очевидні мінуси:
- для того щоб вибрати значимі для класифікації слова необхідно володіти експертними знаннями в предметній області. Чи є у вас наприклад міркування з приводу ключових слів які добре відрізняють документи присвячені фінансовій тематиці від документів економічної? У мене дуже смутні;
- аж ніяк не завжди факт наявності або відсутності якого-небудь одного слова є вирішальним фактором для прийняття рішення.
Докладніше зупинюся на останньому пункті. Якщо повернутися до задачі визначення спаму і трохи подумати про те які слова є хорошими класифікаційними ознаками (classifying feature), то стане зрозуміло що немає такого слова наявність якого гарантувало б що повідомлення є спамом. Можливо, в межах компанії виробляє силденафіл в промислових масштабах слово "віагра" не є показовою ознакою спам-повідомлення, хто знає.
Загалом, суть така: будь-яка з відомих спам-слів нехай рідко але зустрічається в повсякденному житті. Тому, приймати остаточне рішення грунтуючись на факті наявності або відсутності якого-небудь одного слова ідея контрпродуктивна. Ми можемо ускладнювати правила додаючи вкладені if 'и. Але досить швидко ви зрозумієте що можливості людини в формулюванні таких правил дуже обмежені, тому що складність правил зростає експоненціально з кількістю обраних для класифікації слів.
Weight based classification
Ми можемо піти іншим шляхом. Ми можемо для кожного слова вибрати якийсь вагу, який буде означати наскільки ймовірно що повідомлення з цим словом є спамом (0 - ніколи не є спамом, 1 - завжди спам).
У цій таблиці перераховані гіпотетичні ваги для чотирьох слів. Сума значень в рядку має дорівнювати одиниці. Тоді наша класифікація може виглядати наступним чином:
Ми беремо кожне слово і визначаємо сумарний вага документа окремо для класу "спам" і класу "не спам". Сумарна вага визначається як добуток ваг всіх відомих слів документа. Слова для яких у нас немає ваги ми пропускаємо при класифікації. Який сумарна вага виявився більше той клас і перемагає.
Це більш розумний підхід, так як він більш гнучкий і приймає рішення на підставі всіх відомих слів в тексті. Так само його набагато простіше супроводжувати ніж полотна if 'ов.
Метод машинного навчання
А тепер дуже важливе зауваження. Якщо у нас буде якийсь спосіб автоматично підібрати оптимальні ваги слів, то даний підхід можна вважати методом машинного навчання. Сильно спрощений, можливо навіть гіпертрофований, але по своїй суті це саме метод машинного навчання.
Якщо бути більш точним, то описаний мною метод є зародком наївного байєсівського класифікатора. Але не дозволяйте назвою обдурити вас, NBC (Naïve Bayes Classifier) якщо не самий, то один з найбільш часто використовуваних класифікаторів. Для цього є ряд причин:
- він простий в імплементації та тестуванні;
- процес навчання досить ефективний в порівнянні з іншими більш складними класифікаторами;
- на невеликих корпусах документів різниця між NBC і іншими набагато складнішими алгоритмами класифікації часто несуттєва, а іноді NBC може виявитися і більш точним 5.
У наступних замітках я більш детально опишу питання пов'язані зі створенням і тестуванням подібного класифікатора. Підписуйтесь на RSS.