Класифікація документів

Класифікація документів — це одне з завдань інформаційного пошуку, яке полягає у зарахуванні документа до однієї з кількох категорій на підставі його змісту.

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

Документи, що класифікуються, можуть бути текстовими, це можуть бути зображення та музика і так далі. Кожен вид документа має свої особливості класифікації. Зазвичай під класифікацією документів мається на увазі класифікація тексту, якщо не вказано інше.

Слід відрізняти класифікацію текстів від кластеризації. В останньому випадку тексти також об'єднуються за деякими критеріями, але заздалегідь задані категорії відсутні.

Підходи до класифікації текстів

Існують три підходи до задачі класифікації текстів.

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

Інший підхід полягає в написанні правил, згідно яких можна зарахувати текст до тієї чи іншої категорії. Наприклад, одне з таких правил може виглядати наступним чином: «якщо текст містить слова похідна і рівняння, то віднести його до категорії математика». Спеціаліст, який знайомий з предметною областю і володіє навичкою написання регулярних виразів, може скласти низку правил, які потім автоматично застосовуються до класифікації нових документів. Цей підхід кращий, ніж попередній, оскільки процес класифікації автоматизується і кількість оброблюваних документів стає практично не обмеженою. Більш того, створення правил вручну може підвищити точність класифікації у порівнянні з машинним навчанням (див. нижче). Однак створення і підтримка правил в актуальному стані (наприклад, якщо для класифікації новин використовується ім'я чинного президента країни, то відповідне правило потрібно час від часу змінювати) вимагає постійних зусиль фахівця.

Нарешті, третій підхід ґрунтується на машинному навчанні. У цьому підході набір правил або, більш загально, критерій прийняття рішення текстового класифікатора обчислюється автоматично з навчальних даних (іншими словами, проводиться навчання класифікатора).

Навчальні дані — це деяка кількість наочних зразків документів з кожного класу. У машинному навчанні зберігається необхідність ручної розмітки (термін «розмітка» означає процес надання документу певного класу), але вона є більш простим завданням, ніж написання правил. Крім того, розмітка може бути проведена в звичайному режимі використання системи. Наприклад, у програмі електронної пошти може існувати можливість позначати листи як спам, таким чином формуючи навчальну множину для класифікатора — фільтра небажаних повідомлень. Тому класифікація текстів, заснована на машинному навчанні, є прикладом навчання з учителем, де в ролі вчителя виступає людина, що задає набір класів і розмічає навчальну множину.

Постановка завдання

Є множина категорій (класів, міток) ${\mathfrak {C}}=\{c_{1},...,c_{\left|{\mathfrak {C}}\right|}\}$.

Є множина документів ${\mathfrak {D}}=\{d_{1},...,d_{\left|{\mathfrak {D}}\right|}\}$.

Невідома цільова функція $\Phi \colon {\mathfrak {C}}\times {\mathfrak {D}}\rightarrow \{0,1\}$.

Необхідно побудувати класифікатор $\Phi ^{\prime }$, максимально близький до $\Phi$.

Є деяка початкова колекція розмічених документів ${\mathfrak {R}}\subset {\mathfrak {C}}\times {\mathfrak {D}}$, для яких відомі значення $\Phi$. Зазвичай її поділяють на «навчальну» та «перевірочну» частини. Перша використовується для навчання класифікатора, друга — для незалежної перевірки якості його роботи.

Класифікатор може видавати точну відповідь $\Phi ^{\prime }\colon {\mathfrak {C}}\times {\mathfrak {D}}\rightarrow \{0,1\}$ або степінь подібності $\Phi ^{\prime }\colon {\mathfrak {C}}\times {\mathfrak {D}}\rightarrow [0,1]$.

Етапи обробки

Індексація документів

Побудова деякої числової моделі тексту. Наприклад, у вигляді багатовимірного вектора слів і їх ваги в документі. Зменшення розмірності моделі.

Побудова та навчання класифікатора

Можуть використовуватися різні методи машинного навчання: дерево прийняття рішень, наївний баєсів класифікатор, штучні нейронні мережі, метод опорних векторів та ін.

Оцінка якості класифікації

Можна оцінювати за критеріями повноти, точності, порівнювати класифікатори згідно зі спеціальними тестовими наборами.

Навчальні методи

Наївна баєсова модель

Наївна баєсова модель є ймовірнісним методом навчання. Імовірність того, що документ d потрапить у клас c записується як $P(c|d)$. Оскільки мета класифікації — знайти найбільш відповідний клас для даного документа, то в наївній баєсовій класифікації завдання полягає в знаходженні найбільш ймовірного класу c_m

$c_{m}={\underset {c\in C}{\operatorname {argmax} }}\,P(c|d)$

Обчислити значення цієї ймовірності безпосередньо неможливо, оскільки для цього потрібно, щоб навчальна множина містила всі (або майже всі) можливі комбінації класів і документів. Однак, використовуючи формулу баєса, можна переписати вираз для $P(c|d)$

$c_{m}={\underset {c\in C}{\operatorname {argmax} }}\,{\frac {P(d|c)P(c)}{P(d)}}={\underset {c\in C}{\operatorname {argmax} }}\,P(d|c)P(c)$

де знаменник $P(d)$ нехтується, тому що не залежить від c і, отже, не впливає на знаходження максимуму; P(c) — імовірність того, що зустрінеться клас c, незалежно від розглянутого документа; $P(d|c)$ — ймовірність зустріти документ d серед документів класу c.

Використовуючи навчальну множину, ймовірність P(c) можна оцінити як

${\hat {P}}(c)={\frac {N_{c}}{N}}$

де $N_{c}$ — кількість документів в класі c, N — загальна кількість документів у навчальній множині. Тут використаний інший знак для ймовірності, оскільки за допомогою навчальної множини можна лише оцінити ймовірність, але не знайти її точне значення.

Щоб оцінити ймовірність $P(d|c)=P(t_{1},t_{2},...,t_{n_{d}}|c)$, де $t_{k}$ — термін з документа d, $n_{d}$ — загальна кількість термінів у документі (включаючи повторення). Необхідно ввести спрощені припущення (1) про умовну незалежність термінів і (2) про незалежність позицій термінів. Іншими словами, ми нехтуємо, по-перше, тим фактом, що в тексті, написаному природною мовою, поява одного слова часто тісно пов'язана з появою інших слів (наприклад, імовірніше, що слово інтеграл зустрінеться в одному тексті зі словом рівняння, ніж зі словом бактерія), і, по-друге, що ймовірність зустріти теж саме слово різна для різних позицій в тексті. Саме через ці грубі спрощення розглянута модель природної мови називається наївною (тим не менше вона є досить ефективною в задачі класифікації). Отже, у світлі зроблених припущень, використовуючи правило множення ймовірностей незалежних подій, можна записати

$P(d|c)=P(t_{1},t_{2},...,t_{n_{d}}|c)=P(t_{1}|c)P(t_{2}|c)...P(t_{n_{d}}|c)=\prod _{k=1}^{n_{d}}P(t_{k}|c)$

Оцінка ймовірностей $P(t|c)$ за допомогою навчальної множини буде

${\hat {P}}(t|c)={\frac {T_{ct}}{T_{c}}}$

де $T_{ct}$ — кількість входжень терміну t у всіх документах класу c (і на будь-яких позиціях — тут істотно використовується другий механізм спрощення припущень, інакше довелося б обчислювати ці ймовірності для кожної позиції в документі, що неможливо зробити досить точно через розрідженість навчальних даних — важко очікувати, що кожен термін зустрінеться в кожній позиції достатню кількість разів); $T_{c}$ — загальна кількість термінів у документах класу c. При підрахунку враховуються всі повторні входження.

Після того, як класифікатор «навчений», тобто знайдені величини ${\hat {P}}(c)$ й ${\hat {P}}(t|c)$, можна знайти клас документа

$c_{m}={\underset {c\in C}{\operatorname {argmax} }}\,{\hat {P}}(d|c){\hat {P}}(c)={\underset {c\in C}{\operatorname {argmax} }}{\hat {P}}(c)\prod _{k=1}^{n_{d}}{\hat {P}}(t_{k}|c)$

Щоб уникнути в останній формулі переповнення знизу через велику кількість співмножників, на практиці замість добутку зазвичай використовують суму логарифмів. Логарифмування не впливає на знаходження максимуму, оскільки логарифм є монотонно зростаючою функцією. Тому в більшості реалізацій замість останньої формули використовується

$c_{m}={\underset {c\in C}{\operatorname {argmax} }}[\log {\hat {P}}(c)+\sum _{k=1}^{n_{d}}\log {\hat {P}}(t_{k}|c)]$

Ця формула має просту інтерпретацію. Шанси класифікувати документ класом, що часто зустрічається вище, і доданок $\log {\hat {P}}(c)$ вносить в загальну суму відповідний внесок. Величина $\log {\hat {P}}(t|c)$ тим більша, чим важливіший термін t для ідентифікації класу c, і, відповідно, тим вагоміший їх внесок в загальну суму.

Застосування

• фільтрація спаму
• Складання інтернет-каталогів
• Підбір контекстної реклами
• В системах документообігу
• Автоматичне реферування (складання анотацій)
• Зняття неоднозначності при автоматичному перекладі текстів
• Обмеження області пошуку в пошукових системах
• Визначення кодування та мови тексту

Автоматична класифікація документів

Автоматичні задачі класифікації документів можна розподілити на три види: керована класифікація документів, де деякі зовнішні механізми (наприклад, живий зворотній зв'язок) надає інформацію про правильну класифікацію документів, некерована класифікація документів (також відома як кластеризація, де класифікація повинна бути зроблена повністю без посилання на зовнішню інформацію, і напівнавчальна класифікація документів, де частини документів нумеруються зовнішнім механізмом.

Методи

Методи автоматичної класифікації документа:

• Expectation maximization (EM)
• Наївний баєсів класифікатор
• TF-IDF
• Латентно-семантичне індексування
• Метод опорних векторів (англ. Support vector machines, SVM)
• Штучна нейронна мережа
• Метод k найближчих сусідів
• Дерева рішень, такі як алгоритм ID3 чи C4.5
• Глибинний аналіз понять
• Класифікатор на базі грубих множин
• Класифікатор на базі м'яких множин
• Навчання за набором зразків
• Обробка природної мови

Література

• Christopher D. Manning, Prabhakar Raghavan, Hinrich Schütze An Introduction to Information Retrieval [Архівовано 9 Грудня 2012 у Wayback Machine.] Draft. Online edition. Cambridge University Press. — 2009. — 544 p.
• Fabrizio Sebastiani. Machine learning in automated text categorization. ACM Computing Surveys, 34(1):1-47, 2002.
• Stefan Büttcher, Charles L. A. Clarke, and Gordon V. Cormack. Information Retrieval: Implementing and Evaluating Search Engines [Архівовано 5 жовтня 2020 у Wayback Machine.]. MIT Press, 2010.

Див. також

• Наївний баєсів класифікатор
• Кластерний аналіз
• Кластеризація документів

Посилання

• Лекція № 6 по класифікації текстів курсу «Сучасні завдання теоретичної інформатики [Архівовано 15 Жовтня 2008 у Wayback Machine.]» (постановка задачі, побудова та навчання класифікатора, оцінка якості).
• F. Sebastiani. Machine Learning in Automated Text Categorization (PDF). [Архівовано 28 Травня 2016 у Wayback Machine.] (англ.)
• «Text mining. Класифікація тексту». [Архівовано 3 Жовтня 2011 у Wayback Machine.] Приклад класифікації документів з використанням програмних алгоритмів STATISTICA