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

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

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

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

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

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

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

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

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

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

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

Класифікація «заснована на змісті» проти класифікації «заснованої на запиті»

Класифікація за змістом є класифікацією, в якій увага приділена конкретним питанням. У документі визначається клас, до якого його зараховують. Це, наприклад, правило бібліотечної класифікації: принаймні 20% від змісту книги має бути близько класу, до якого відноситься книга.[2] В автоматичній класифікації — це може бути кількість разів, коли дані слова з'являються в документі.

Класифікація за запитом (або індексація) є класифікацією, в якій очікуваний запит від користувачів впливає на те, як документи класифікуються. Класифікатор запитує себе: «За якими дескрипторами цей об'єкт можна знайти?» Тоді оброблюються всі можливі запити та обираються найбільш відповідні[3].

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

Класифікація проти індексації

Іноді виникає відмінність між розподіленням документів на класи («класифікацією») та розподіленням предметів на документи індексації. Але як стверджував Фредерік Уилфрид Ланкастер — ця відмінність не є значущою. «Ці термінологічні відмінності — він пише, — досить безглузді і призначенні тільки для створення плутанини»[4]. Думка, що це розходження тільки зовнішнє також підтверджується тим фактом, що систему класифікації може бути перетворено в тезауруса, і навпаки[5][6][7][8]. Тому це акт маркування документа (скажімо, внесення терміну до словника в документі) й одночасно призначення йому класу документів проіндексованих цим терміном (всі документи проіндексовані або оголошені як X належать до того ж класу документів).

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

Є множина категорій (класів, міток) ${\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
Глибинний аналіз понять
Класифікатор на базі грубих множин
Класифікатор на базі м'яких множин
Навчання за набором зразків
Обробка природної мови

Примітки

Manning et al. (2009) — p. 255
Бібліотека Конгресу (2008). Керівництво предметні рубрики. Вашингтон, округ Колумбія.: Бібліотека Конгресу США, Відділ політики і стандартів. (Лист H 180: «Зв'язати заголовки тільки для тих, які містять, щонайменше, 20% роботи.»)
Зергель, Дагоберт (1985) Організація інформації: Принципи баз даних і пошукових систем. Орландо, Флорида: Academic Press
Ланкастер, FW (2003) Індексування та реферування в теорії і практиці бібліотечної асоціації Лондон.
Aitchison, J. (1986) «класифікації як джерело для тезауруса :. ББК Є. П. Блаженства як джерело умов і структури тезауруса» … Журнал документації, том 42, № 3, стор 160–181.
Aitchison, J. «Тезаурус від BC2 :. Проблеми та можливості, виявлених в експериментальній тезауруса, отриманої з графіка Bliss Music» … Bliss Класифікація бюлетень, Vol 46, стор 20 −26
Бротон, В. (2008) "гранований класифікація як основа гранований термінології: … Перетворення секретної структури в форматі тезауруса в блаженстві ББК (2-е изд .). "Axiomathes, Vol. 18 № 2, стор. 193–210.
Riesthuis, GJA, і Bliedung, Санкт (1991). «Thesaurification в УДК.» Інструменти для організації знань і людино-машинного інтерфейсу, Vol. 2, стор. 109–117. Список Verlag, Франкфурт.

Література

Christopher D. Manning, Prabhakar Raghavan, Hinrich Schütze An Introduction to Information Retrieval 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. MIT Press, 2010.

Див. також

Посилання

Лекція № 6 по класифікації текстів курсу «Сучасні завдання теоретичної інформатики» (постановка задачі, побудова та навчання класифікатора, оцінка якості).
F. Sebastiani. Machine Learning in Automated Text Categorization (PDF). (англ.)
«Text mining. Класифікація тексту». Приклад класифікації документів з використанням програмних алгоритмів STATISTICA

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.

[1] Manning et al. (2009) — p. 255

[2] Бібліотека Конгресу (2008). Керівництво предметні рубрики. Вашингтон, округ Колумбія.: Бібліотека Конгресу США, Відділ політики і стандартів. (Лист H 180: «Зв'язати заголовки тільки для тих, які містять, щонайменше, 20% роботи.»)

[3] Зергель, Дагоберт (1985) Організація інформації: Принципи баз даних і пошукових систем. Орландо, Флорида: Academic Press

[4] Ланкастер, FW (2003) Індексування та реферування в теорії і практиці бібліотечної асоціації Лондон.

[5] Aitchison, J. (1986) «класифікації як джерело для тезауруса :. ББК Є. П. Блаженства як джерело умов і структури тезауруса» … Журнал документації, том 42, № 3, стор 160–181.

[6] Aitchison, J. «Тезаурус від BC2 :. Проблеми та можливості, виявлених в експериментальній тезауруса, отриманої з графіка Bliss Music» … Bliss Класифікація бюлетень, Vol 46, стор 20 −26

[7] Бротон, В. (2008) "гранований класифікація як основа гранований термінології: … Перетворення секретної структури в форматі тезауруса в блаженстві ББК (2-е изд .). "Axiomathes, Vol. 18 № 2, стор. 193–210.

[8] Riesthuis, GJA, і Bliedung, Санкт (1991). «Thesaurification в УДК.» Інструменти для організації знань і людино-машинного інтерфейсу, Vol. 2, стор. 109–117. Список Verlag, Франкфурт.