Підходи до класифікації текстів
Існує три підходи до задачі класифікації текстів [1].
По-перше, класифікація не завжди здійснюється за допомогою комп'ютера. Наприклад, у звичайній бібліотеці тематичні рубрики присвоюються книгам вручну бібліотекарем. Подібна ручна класифікація дорога і непридатна в випадках, коли необхідно класифікувати велику кількість документів з високою швидкістю.
Нарешті, третій підхід ґрунтується на машинному навчанні. У цьому підході набір правил або, більш загально, критерій прийняття рішення текстового класифікатора, обчислюється автоматично з навчальних даних (іншими словами, проводиться навчання класифікатора). Навчальні дані - це деяка кількість хороших зразків документів з кожного класу. У машинному навчанні зберігається необхідність ручної розмітки (термін розмітка означає процес приписування класу документу). Але розмітка є більш простим завданням, ніж написання правил. Крім того, розмітка може бути проведена в звичайному режимі використання системи. Наприклад, в програмі електронної пошти може існувати можливість позначати листи як спам, тим самим формуючи навчальну множину для класифікатора - фільтра небажаної пошти. Таким чином, класифікація текстів, заснована на машинному навчанні, є прикладом навчання з учителем. де в ролі вчителя виступає людина, що задає набір класів і розмічати навчальну множину.
Є деяка початкова колекція розмічених документів R ⊂ C × D> \ subset> \ times >>. для яких відомі значення Φ. Зазвичай її ділять на «навчальну» і «перевірочну» частини. Перша використовується для навчання класифікатора, друга - для незалежної перевірки якості його роботи.
Індексація документів Побудова деякої числової моделі тексту, наприклад у вигляді багатовимірного вектора слів і їх ваги в документі. Зменшення розмірності моделі. Побудова і навчання класифікатора Можуть використовуватися різні методи машинного навчання. вирішальні дерева. наївний байесовский класифікатор. нейронні мережі. метод опорних векторів і ін. Оцінка якості класифікації Можна оцінювати за критеріями повноти, точності, порівнювати класифікатори за спеціальними тестовими наборам.
Наївна байєсівську модель
Наївна байєсівську модель є імовірнісним методом навчання. Імовірність того, що документ d потрапить в клас c записується як P (c | d). Оскільки мета класифікації - знайти найкращий клас для даного документа, то в наївною байєсівської класифікації завдання полягає в знаходженні найбільш ймовірного класу cm
Обчислити значення цієї ймовірності безпосередньо неможливо, оскільки для цього потрібно, щоб навчальна множина містило всі (або майже всі) можливі комбінації класів і документів. Однак, використовуючи формулу Байеса, можна переписати вираз для P (c | d)
де знаменник P (d) опущений, тому що не залежить від c і, отже, не впливає на знаходження максимуму; P (c) - ймовірність того, що зустрінеться клас c. незалежно від розглянутого документа; P (d | c) - ймовірність зустріти документ d серед документів класу c.
Використовуючи навчальну множину, ймовірність P (c) можна оцінити як
де N c> - число документів у класі c. N - загальне число документів у навчальній множині. Тут використаний інший знак для ймовірності, оскільки за допомогою навчальної множини можна лише оцінити ймовірність, але не знайти її точне значення.
Щоб оцінити ймовірність P (d | c) = P (t 1. t 2. t n d | c), t_. t _> \ mid c)>. де t k> - елемент з документа d. n d> - загальне число елементів в документі (включаючи повторення), необхідно ввести спрощують припущення (1) про умовної незалежності елементів і (2) про незалежність позицій елементів. Іншими словами, ми нехтуємо, по-перше, тим фактом, що в тексті на природній мові поява одного слова часто тісно пов'язане з появою інших слів (наприклад, найімовірніше, що слово інтеграл зустрінеться в одному тексті зі словом рівняння. Чим зі словом бактерія) , і, по-друге, що ймовірність зустріти одне і те ж слово різна для різних позицій в тексті. Саме через ці грубих спрощень розглянута модель природної мови називається наївною (проте вона є досить ефективною в завданні класифікації). Отже, в світлі зроблених припущень, використовуючи правило множення ймовірностей незалежних подій, можна записати, що
P (d | c) = P (t 1. t 2. .... Tnd | c) = P (t 1 | c) P (t 2 | c) ... P (tnd | c) = Π k = 1 nd P (tk | c). , T _, \ ldots, t _> \ mid c) = P (t_ \ mid c) P (t_ \ mid c) \ ldots P (t _> \ mid c) = \ prod _ ^> P (t_ \ mid c) .>
Оцінка ймовірностей P (t | c) за допомогою навчальної множини буде
де T ct> - число входжень елемента t в усі документи класу c (і на будь-яких позиціях - тут істотно використовується другий спрощує припущення, інакше довелося б обчислити ці ймовірності для кожної позиції в документі, що неможливо зробити досить точно через розрідженості навчальних даних - годі й чекати, щоб кожен елемент зустрівся в кожній позиції достатню кількість разів); T c> - загальне число елементів в документах класу c. При підрахунку враховуються всі повторні входження.
Після того, як класифікатор «навчений», тобто знайдені величини P ^ (c)> (c)> і P ^ (t | c)> (t \ mid c)>. можна відшукати клас документа:Щоб уникнути в останній формулі антипереполнение знизу через великої кількості співмножників, на практиці замість твори зазвичай використовують суму логарифмів. Логарифмування не впливає на знаходження максимуму, так як логарифм є монотонно зростаючою функцією. Тому в більшості реалізацій замість останньої формули використовується наступна:
Ця формула має просту інтерпретацію. Шанси класифікувати документ часто зустрічається класом вище, і доданок log P ^ (c)> (c)> вносить в загальну суму відповідний внесок. Величини ж log P ^ (t | c)> (t \ mid c)> тим більше, ніж важливіше елемент t для ідентифікації класу c. і, відповідно, тим вагомішим їх внесок в загальну суму.