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

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

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

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


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

Існує три підходи до задачі класифікації текстів [1].

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

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

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


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

Є безліч категорій (класів, міток) \ 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] .


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

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

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

4.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, і, відповідно, тим вагоміші їх внесок в загальну суму.


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

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

Примітки

  1. Manning et al. (2009) - p. 255

Література

  • Christopher D. Manning, Prabhakar Raghavan, Hinrich Schtze An Introduction To Information Retrieval - www.informationretrieval.org/ Draft. Online edition. Cambridge University Press. - 2009. - 544 p.