Класифікація документів — це одне з завдань інформаційного пошуку, яке полягає у зарахуванні документа до однієї з кількох категорій на підставі його змісту.
Класифікація може здійснюватися людиною або автоматично, за допомогою створеного набору правил чи із застосуванням методів машинного навчання.
Документи, що класифікуються, можуть бути текстовими, це можуть бути зображення та музика і так далі. Кожен вид документа має свої особливості класифікації. Зазвичай під класифікацією документів мається на увазі класифікація тексту, якщо не вказано інше.
Слід відрізняти класифікацію текстів від кластеризації. В останньому випадку тексти також об'єднуються за деякими критеріями, але заздалегідь задані категорії відсутні.
Підходи до класифікації текстів
Існують три підходи до задачі класифікації текстів.
По-перше, класифікація не завжди здійснюється за допомогою комп'ютера. Наприклад, у звичайній бібліотеці тематичні рубрики присвоюються книгам власноруч бібліотекарем. Подібна ручна класифікація дорога і непридатна у випадках, коли необхідно класифікувати велику кількість документів з високою швидкістю.
Інший підхід полягає в написанні правил, згідно яких можна зарахувати текст до тієї чи іншої категорії. Наприклад, одне з таких правил може виглядати наступним чином: «якщо текст містить слова похідна і рівняння, то віднести його до категорії математика». Спеціаліст, який знайомий з предметною областю і володіє навичкою написання регулярних виразів, може скласти низку правил, які потім автоматично застосовуються до класифікації нових документів. Цей підхід кращий, ніж попередній, оскільки процес класифікації автоматизується і кількість оброблюваних документів стає практично не обмеженою. Більш того, створення правил вручну може підвищити точність класифікації у порівнянні з машинним навчанням (див. нижче). Однак створення і підтримка правил в актуальному стані (наприклад, якщо для класифікації новин використовується ім'я чинного президента країни, то відповідне правило потрібно час від часу змінювати) вимагає постійних зусиль фахівця.
Нарешті, третій підхід ґрунтується на машинному навчанні. У цьому підході набір правил або, більш загально, критерій прийняття рішення текстового класифікатора обчислюється автоматично з навчальних даних (іншими словами, проводиться навчання класифікатора).
Навчальні дані — це деяка кількість наочних зразків документів з кожного класу. У машинному навчанні зберігається необхідність ручної [en] (термін «розмітка» означає процес надання документу певного класу), але вона є більш простим завданням, ніж написання правил. Крім того, розмітка може бути проведена в звичайному режимі використання системи. Наприклад, у програмі електронної пошти може існувати можливість позначати листи як спам, таким чином формуючи навчальну множину для класифікатора — фільтра небажаних повідомлень. Тому класифікація текстів, заснована на машинному навчанні, є прикладом навчання з учителем, де в ролі вчителя виступає людина, що задає набір класів і розмічає навчальну множину.
Постановка завдання
Є множина категорій (класів, міток) .
Є множина документів .
Невідома цільова функція .
Необхідно побудувати класифікатор , максимально близький до
.
Є деяка початкова колекція розмічених документів , для яких відомі значення
. Зазвичай її поділяють на «навчальну» та «перевірочну» частини. Перша використовується для навчання класифікатора, друга — для незалежної перевірки якості його роботи.
Класифікатор може видавати точну відповідь або степінь подібності
.
Етапи обробки
- Індексація документів
- Побудова деякої числової моделі тексту. Наприклад, у вигляді багатовимірного вектора слів і їх ваги в документі. Зменшення розмірності моделі.
- Побудова та навчання класифікатора
- Можуть використовуватися різні методи машинного навчання: дерево прийняття рішень, наївний баєсів класифікатор, штучні нейронні мережі, метод опорних векторів та ін.
- Оцінка якості класифікації
- Можна оцінювати за критеріями повноти, точності, порівнювати класифікатори згідно зі спеціальними тестовими наборами.
Навчальні методи
Наївна баєсова модель
Наївна баєсова модель є ймовірнісним методом навчання. Імовірність того, що документ d потрапить у клас c записується як . Оскільки мета класифікації — знайти найбільш відповідний клас для даного документа, то в наївній баєсовій класифікації завдання полягає в знаходженні найбільш ймовірного класу cm
Обчислити значення цієї ймовірності безпосередньо неможливо, оскільки для цього потрібно, щоб навчальна множина містила всі (або майже всі) можливі комбінації класів і документів. Однак, використовуючи формулу баєса, можна переписати вираз для
де знаменник нехтується, тому що не залежить від c і, отже, не впливає на знаходження максимуму; P(c) — імовірність того, що зустрінеться клас c, незалежно від розглянутого документа;
— ймовірність зустріти документ d серед документів класу c.
Використовуючи навчальну множину, ймовірність P(c) можна оцінити як
де — кількість документів в класі c, N — загальна кількість документів у навчальній множині. Тут використаний інший знак для ймовірності, оскільки за допомогою навчальної множини можна лише оцінити ймовірність, але не знайти її точне значення.
Щоб оцінити ймовірність , де
— термін з документа d,
— загальна кількість термінів у документі (включаючи повторення). Необхідно ввести спрощені припущення (1) про умовну незалежність термінів і (2) про незалежність позицій термінів. Іншими словами, ми нехтуємо, по-перше, тим фактом, що в тексті, написаному природною мовою, поява одного слова часто тісно пов'язана з появою інших слів (наприклад, імовірніше, що слово інтеграл зустрінеться в одному тексті зі словом рівняння, ніж зі словом бактерія), і, по-друге, що ймовірність зустріти теж саме слово різна для різних позицій в тексті. Саме через ці грубі спрощення розглянута модель природної мови називається наївною (тим не менше вона є досить ефективною в задачі класифікації). Отже, у світлі зроблених припущень, використовуючи правило множення ймовірностей незалежних подій, можна записати
Оцінка ймовірностей за допомогою навчальної множини буде
де — кількість входжень терміну t у всіх документах класу c (і на будь-яких позиціях — тут істотно використовується другий механізм спрощення припущень, інакше довелося б обчислювати ці ймовірності для кожної позиції в документі, що неможливо зробити досить точно через розрідженість навчальних даних — важко очікувати, що кожен термін зустрінеться в кожній позиції достатню кількість разів);
— загальна кількість термінів у документах класу c. При підрахунку враховуються всі повторні входження.
Після того, як класифікатор «навчений», тобто знайдені величини й
, можна знайти клас документа
Щоб уникнути в останній формулі переповнення знизу через велику кількість співмножників, на практиці замість добутку зазвичай використовують суму логарифмів. Логарифмування не впливає на знаходження максимуму, оскільки логарифм є монотонно зростаючою функцією. Тому в більшості реалізацій замість останньої формули використовується
Ця формула має просту інтерпретацію. Шанси класифікувати документ класом, що часто зустрічається вище, і доданок вносить в загальну суму відповідний внесок. Величина
тим більша, чим важливіший термін t для ідентифікації класу c, і, відповідно, тим вагоміший їх внесок в загальну суму.
Застосування
- (фільтрація спаму)
- Складання інтернет-каталогів
- Підбір контекстної реклами
- В системах документообігу
- Автоматичне реферування (складання анотацій)
- Зняття неоднозначності при автоматичному перекладі текстів
- Обмеження області пошуку в пошукових системах
- Визначення кодування та мови тексту
Автоматична класифікація документів
Автоматичні задачі класифікації документів можна розподілити на три види: керована класифікація документів, де деякі зовнішні механізми (наприклад, живий зворотній зв'язок) надає інформацію про правильну класифікацію документів, некерована класифікація документів (також відома як кластеризація, де класифікація повинна бути зроблена повністю без посилання на зовнішню інформацію, і напівнавчальна класифікація документів, де частини документів нумеруються зовнішнім механізмом.
Методи
Методи автоматичної класифікації документа:
- Expectation maximization (EM)
- Наївний баєсів класифікатор
- TF-IDF
- Латентно-семантичне індексування
- Метод опорних векторів (англ. Support vector machines, SVM)
- Штучна нейронна мережа
- Метод k найближчих сусідів
- Дерева рішень, такі як алгоритм ID3 чи C4.5
- [en]
- Класифікатор на базі [en]
- Класифікатор на базі [en]
- Навчання за набором зразків
- Обробка природної мови
Примітки
- Manning et al. (2009) — p. 255
Література
- 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
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет
Klasifikaciya dokumentiv ce odne z zavdan informacijnogo poshuku yake polyagaye u zarahuvanni dokumenta do odniyeyi z kilkoh kategorij na pidstavi jogo zmistu Klasifikaciya mozhe zdijsnyuvatisya lyudinoyu abo avtomatichno za dopomogoyu stvorenogo naboru pravil chi iz zastosuvannyam metodiv mashinnogo navchannya Dokumenti sho klasifikuyutsya mozhut buti tekstovimi ce mozhut buti zobrazhennya ta muzika i tak dali Kozhen vid dokumenta maye svoyi osoblivosti klasifikaciyi Zazvichaj pid klasifikaciyeyu dokumentiv mayetsya na uvazi klasifikaciya tekstu yaksho ne vkazano inshe Slid vidriznyati klasifikaciyu tekstiv vid klasterizaciyi V ostannomu vipadku teksti takozh ob yednuyutsya za deyakimi kriteriyami ale zazdalegid zadani kategoriyi vidsutni Pidhodi do klasifikaciyi tekstivIsnuyut tri pidhodi do zadachi klasifikaciyi tekstiv Po pershe klasifikaciya ne zavzhdi zdijsnyuyetsya za dopomogoyu komp yutera Napriklad u zvichajnij biblioteci tematichni rubriki prisvoyuyutsya knigam vlasnoruch bibliotekarem Podibna ruchna klasifikaciya doroga i nepridatna u vipadkah koli neobhidno klasifikuvati veliku kilkist dokumentiv z visokoyu shvidkistyu Inshij pidhid polyagaye v napisanni pravil zgidno yakih mozhna zarahuvati tekst do tiyeyi chi inshoyi kategoriyi Napriklad odne z takih pravil mozhe viglyadati nastupnim chinom yaksho tekst mistit slova pohidna i rivnyannya to vidnesti jogo do kategoriyi matematika Specialist yakij znajomij z predmetnoyu oblastyu i volodiye navichkoyu napisannya regulyarnih viraziv mozhe sklasti nizku pravil yaki potim avtomatichno zastosovuyutsya do klasifikaciyi novih dokumentiv Cej pidhid krashij nizh poperednij oskilki proces klasifikaciyi avtomatizuyetsya i kilkist obroblyuvanih dokumentiv staye praktichno ne obmezhenoyu Bilsh togo stvorennya pravil vruchnu mozhe pidvishiti tochnist klasifikaciyi u porivnyanni z mashinnim navchannyam div nizhche Odnak stvorennya i pidtrimka pravil v aktualnomu stani napriklad yaksho dlya klasifikaciyi novin vikoristovuyetsya im ya chinnogo prezidenta krayini to vidpovidne pravilo potribno chas vid chasu zminyuvati vimagaye postijnih zusil fahivcya Nareshti tretij pidhid gruntuyetsya na mashinnomu navchanni U comu pidhodi nabir pravil abo bilsh zagalno kriterij prijnyattya rishennya tekstovogo klasifikatora obchislyuyetsya avtomatichno z navchalnih danih inshimi slovami provoditsya navchannya klasifikatora Navchalni dani ce deyaka kilkist naochnih zrazkiv dokumentiv z kozhnogo klasu U mashinnomu navchanni zberigayetsya neobhidnist ruchnoyi en termin rozmitka oznachaye proces nadannya dokumentu pevnogo klasu ale vona ye bilsh prostim zavdannyam nizh napisannya pravil Krim togo rozmitka mozhe buti provedena v zvichajnomu rezhimi vikoristannya sistemi Napriklad u programi elektronnoyi poshti mozhe isnuvati mozhlivist poznachati listi yak spam takim chinom formuyuchi navchalnu mnozhinu dlya klasifikatora filtra nebazhanih povidomlen Tomu klasifikaciya tekstiv zasnovana na mashinnomu navchanni ye prikladom navchannya z uchitelem de v roli vchitelya vistupaye lyudina sho zadaye nabir klasiv i rozmichaye navchalnu mnozhinu Postanovka zavdannyaYe mnozhina kategorij klasiv mitok C c 1 c C displaystyle mathfrak C c 1 c left mathfrak C right Ye mnozhina dokumentiv D d 1 d D displaystyle mathfrak D d 1 d left mathfrak D right Nevidoma cilova funkciya F C D 0 1 displaystyle Phi colon mathfrak C times mathfrak D rightarrow 0 1 Neobhidno pobuduvati klasifikator F displaystyle Phi prime maksimalno blizkij do F displaystyle Phi Ye deyaka pochatkova kolekciya rozmichenih dokumentiv R C D displaystyle mathfrak R subset mathfrak C times mathfrak D dlya yakih vidomi znachennya F displaystyle Phi Zazvichaj yiyi podilyayut na navchalnu ta perevirochnu chastini Persha vikoristovuyetsya dlya navchannya klasifikatora druga dlya nezalezhnoyi perevirki yakosti jogo roboti Klasifikator mozhe vidavati tochnu vidpovid F C D 0 1 displaystyle Phi prime colon mathfrak C times mathfrak D rightarrow 0 1 abo stepin podibnosti F C D 0 1 displaystyle Phi prime colon mathfrak C times mathfrak D rightarrow 0 1 Etapi obrobkiIndeksaciya dokumentiv Pobudova deyakoyi chislovoyi modeli tekstu Napriklad u viglyadi bagatovimirnogo vektora sliv i yih vagi v dokumenti Zmenshennya rozmirnosti modeli Pobudova ta navchannya klasifikatora Mozhut vikoristovuvatisya rizni metodi mashinnogo navchannya derevo prijnyattya rishen nayivnij bayesiv klasifikator shtuchni nejronni merezhi metod opornih vektoriv ta in Ocinka yakosti klasifikaciyi Mozhna ocinyuvati za kriteriyami povnoti tochnosti porivnyuvati klasifikatori zgidno zi specialnimi testovimi naborami Navchalni metodiNayivna bayesova model Dokladnishe Nayivnij bayesiv klasifikator Nayivna bayesova model ye jmovirnisnim metodom navchannya Imovirnist togo sho dokument d potrapit u klas c zapisuyetsya yak P c d displaystyle P c d Oskilki meta klasifikaciyi znajti najbilsh vidpovidnij klas dlya danogo dokumenta to v nayivnij bayesovij klasifikaciyi zavdannya polyagaye v znahodzhenni najbilsh jmovirnogo klasu cm c m argmax c C P c d displaystyle c m underset c in C operatorname argmax P c d Obchisliti znachennya ciyeyi jmovirnosti bezposeredno nemozhlivo oskilki dlya cogo potribno shob navchalna mnozhina mistila vsi abo majzhe vsi mozhlivi kombinaciyi klasiv i dokumentiv Odnak vikoristovuyuchi formulu bayesa mozhna perepisati viraz dlya P c d displaystyle P c d c m argmax c C P d c P c P d argmax c C P d c P c displaystyle 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 de znamennik P d displaystyle P d nehtuyetsya tomu sho ne zalezhit vid c i otzhe ne vplivaye na znahodzhennya maksimumu P c imovirnist togo sho zustrinetsya klas c nezalezhno vid rozglyanutogo dokumenta P d c displaystyle P d c jmovirnist zustriti dokument d sered dokumentiv klasu c Vikoristovuyuchi navchalnu mnozhinu jmovirnist P c mozhna ociniti yak P c N c N displaystyle hat P c frac N c N de N c displaystyle N c kilkist dokumentiv v klasi c N zagalna kilkist dokumentiv u navchalnij mnozhini Tut vikoristanij inshij znak dlya jmovirnosti oskilki za dopomogoyu navchalnoyi mnozhini mozhna lishe ociniti jmovirnist ale ne znajti yiyi tochne znachennya Shob ociniti jmovirnist P d c P t 1 t 2 t n d c displaystyle P d c P t 1 t 2 t n d c de t k displaystyle t k termin z dokumenta d n d displaystyle n d zagalna kilkist terminiv u dokumenti vklyuchayuchi povtorennya Neobhidno vvesti sprosheni pripushennya 1 pro umovnu nezalezhnist terminiv i 2 pro nezalezhnist pozicij terminiv Inshimi slovami mi nehtuyemo po pershe tim faktom sho v teksti napisanomu prirodnoyu movoyu poyava odnogo slova chasto tisno pov yazana z poyavoyu inshih sliv napriklad imovirnishe sho slovo integral zustrinetsya v odnomu teksti zi slovom rivnyannya nizh zi slovom bakteriya i po druge sho jmovirnist zustriti tezh same slovo rizna dlya riznih pozicij v teksti Same cherez ci grubi sproshennya rozglyanuta model prirodnoyi movi nazivayetsya nayivnoyu tim ne menshe vona ye dosit efektivnoyu v zadachi klasifikaciyi Otzhe u svitli zroblenih pripushen vikoristovuyuchi pravilo mnozhennya jmovirnostej nezalezhnih podij mozhna zapisati 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 k 1 n d P t k c displaystyle 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 Ocinka jmovirnostej P t c displaystyle P t c za dopomogoyu navchalnoyi mnozhini bude P t c T c t T c displaystyle hat P t c frac T ct T c de T c t displaystyle T ct kilkist vhodzhen terminu t u vsih dokumentah klasu c i na bud yakih poziciyah tut istotno vikoristovuyetsya drugij mehanizm sproshennya pripushen inakshe dovelosya b obchislyuvati ci jmovirnosti dlya kozhnoyi poziciyi v dokumenti sho nemozhlivo zrobiti dosit tochno cherez rozridzhenist navchalnih danih vazhko ochikuvati sho kozhen termin zustrinetsya v kozhnij poziciyi dostatnyu kilkist raziv T c displaystyle T c zagalna kilkist terminiv u dokumentah klasu c Pri pidrahunku vrahovuyutsya vsi povtorni vhodzhennya Pislya togo yak klasifikator navchenij tobto znajdeni velichini P c displaystyle hat P c j P t c displaystyle hat P t c mozhna znajti klas dokumenta c m argmax c C P d c P c argmax c C P c k 1 n d P t k c displaystyle 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 Shob uniknuti v ostannij formuli perepovnennya znizu cherez veliku kilkist spivmnozhnikiv na praktici zamist dobutku zazvichaj vikoristovuyut sumu logarifmiv Logarifmuvannya ne vplivaye na znahodzhennya maksimumu oskilki logarifm ye monotonno zrostayuchoyu funkciyeyu Tomu v bilshosti realizacij zamist ostannoyi formuli vikoristovuyetsya c m argmax c C log P c k 1 n d log P t k c displaystyle c m underset c in C operatorname argmax log hat P c sum k 1 n d log hat P t k c Cya formula maye prostu interpretaciyu Shansi klasifikuvati dokument klasom sho chasto zustrichayetsya vishe i dodanok log P c displaystyle log hat P c vnosit v zagalnu sumu vidpovidnij vnesok Velichina log P t c displaystyle log hat P t c tim bilsha chim vazhlivishij termin t dlya identifikaciyi klasu c i vidpovidno tim vagomishij yih vnesok v zagalnu sumu Zastosuvannyafiltraciya spamu Skladannya internet katalogiv Pidbir kontekstnoyi reklami V sistemah dokumentoobigu Avtomatichne referuvannya skladannya anotacij Znyattya neodnoznachnosti pri avtomatichnomu perekladi tekstiv Obmezhennya oblasti poshuku v poshukovih sistemah Viznachennya koduvannya ta movi tekstuAvtomatichna klasifikaciya dokumentivAvtomatichni zadachi klasifikaciyi dokumentiv mozhna rozpodiliti na tri vidi kerovana klasifikaciya dokumentiv de deyaki zovnishni mehanizmi napriklad zhivij zvorotnij zv yazok nadaye informaciyu pro pravilnu klasifikaciyu dokumentiv nekerovana klasifikaciya dokumentiv takozh vidoma yak klasterizaciya de klasifikaciya povinna buti zroblena povnistyu bez posilannya na zovnishnyu informaciyu i napivnavchalna klasifikaciya dokumentiv de chastini dokumentiv numeruyutsya zovnishnim mehanizmom MetodiMetodi avtomatichnoyi klasifikaciyi dokumenta Expectation maximization EM Nayivnij bayesiv klasifikator TF IDF Latentno semantichne indeksuvannya Metod opornih vektoriv angl Support vector machines SVM Shtuchna nejronna merezha Metod k najblizhchih susidiv Dereva rishen taki yak algoritm ID3 chi C4 5 en Klasifikator na bazi en Klasifikator na bazi en Navchannya za naborom zrazkiv Obrobka prirodnoyi moviPrimitkiManning et al 2009 p 255LiteraturaChristopher D Manning Prabhakar Raghavan Hinrich Schutze An Introduction to Information Retrieval 9 Grudnya 2012 u 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 Buttcher Charles L A Clarke and Gordon V Cormack Information Retrieval Implementing and Evaluating Search Engines 5 zhovtnya 2020 u Wayback Machine MIT Press 2010 Div takozhNayivnij bayesiv klasifikator Klasternij analiz Klasterizaciya dokumentivPosilannyaLekciya 6 po klasifikaciyi tekstiv kursu Suchasni zavdannya teoretichnoyi informatiki 15 Zhovtnya 2008 u Wayback Machine postanovka zadachi pobudova ta navchannya klasifikatora ocinka yakosti F Sebastiani Machine Learning in Automated Text Categorization PDF 28 Travnya 2016 u Wayback Machine angl Text mining Klasifikaciya tekstu 3 Zhovtnya 2011 u Wayback Machine Priklad klasifikaciyi dokumentiv z vikoristannyam programnih algoritmiv STATISTICA