www.wikidata.uk-ua.nina.az

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

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

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

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

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

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

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

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

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

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

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

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


Постановка завдання Редагувати

Є множина категорій (класів, міток) .

Є множина документів .

Невідома цільова функція .

Необхідно побудувати класифікатор , максимально близький до .

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

Класифікатор може видавати точну відповідь або степінь подібності .

Етапи обробки Редагувати

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

Наївна баєсова модель Редагувати

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

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

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

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

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

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

Оцінка ймовірностей за допомогою навчальної множини буде

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

Після того, як класифікатор «навчений», тобто знайдені величини й , можна знайти клас документа

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

Ця формула має просту інтерпретацію. Шанси класифікувати документ класом, що часто зустрічається вище, і доданок вносить в загальну суму відповідний внесок. Величина тим більша, чим важливіший термін t для ідентифікації класу c, і, відповідно, тим вагоміший їх внесок в загальну суму.

Застосування Редагувати

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

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

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

Методи Редагувати

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

Примітки Редагувати

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

Література Редагувати

Див. також Редагувати

Посилання Редагувати

Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри
Дата публікації:
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 Zmist 1 Pidhodi do klasifikaciyi tekstiv 2 Postanovka zavdannya 3 Etapi obrobki 4 Navchalni metodi 4 1 Nayivna bayesova model 5 Zastosuvannya 6 Avtomatichna klasifikaciya dokumentiv 7 Metodi 8 Primitki 9 Literatura 10 Div takozh 11 PosilannyaPidhodi do klasifikaciyi tekstiv RedaguvatiIsnuyut tri pidhodi do zadachi klasifikaciyi tekstiv 1 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 rozmitki 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 zavdannya RedaguvatiYe mnozhina kategorij klasiv mitok C c 1 c C displaystyle mathfrak C c 1 c left mathfrak C right nbsp Ye mnozhina dokumentiv D d 1 d D displaystyle mathfrak D d 1 d left mathfrak D right nbsp Nevidoma cilova funkciya F C D 0 1 displaystyle Phi colon mathfrak C times mathfrak D rightarrow 0 1 nbsp Neobhidno pobuduvati klasifikator F displaystyle Phi prime nbsp maksimalno blizkij do F displaystyle Phi nbsp Ye deyaka pochatkova kolekciya rozmichenih dokumentiv R C D displaystyle mathfrak R subset mathfrak C times mathfrak D nbsp dlya yakih vidomi znachennya F displaystyle Phi nbsp 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 nbsp abo stepin podibnosti F C D 0 1 displaystyle Phi prime colon mathfrak C times mathfrak D rightarrow 0 1 nbsp Etapi obrobki RedaguvatiIndeksaciya 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 metodi RedaguvatiNayivna bayesova model Redaguvati Dokladnishe Nayivnij bayesiv klasifikatorNayivna bayesova model ye jmovirnisnim metodom navchannya Imovirnist togo sho dokument d potrapit u klas c zapisuyetsya yak P c d displaystyle P c d nbsp Oskilki meta klasifikaciyi znajti najbilsh vidpovidnij klas dlya danogo dokumenta to v nayivnij bayesovij klasifikaciyi zavdannya polyagaye v znahodzhenni najbilsh jmovirnogo klasu cmc m argmax c C P c d displaystyle c m underset c in C operatorname argmax P c d nbsp 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 nbsp 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 nbsp de znamennik P d displaystyle P d nbsp 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 nbsp jmovirnist zustriti dokument d sered dokumentiv klasu c Vikoristovuyuchi navchalnu mnozhinu jmovirnist P c mozhna ociniti yakP c N c N displaystyle hat P c frac N c N nbsp de N c displaystyle N c nbsp 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 nbsp de t k displaystyle t k nbsp termin z dokumenta d n d displaystyle n d nbsp 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 zapisatiP 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 nbsp Ocinka jmovirnostej P t c displaystyle P t c nbsp za dopomogoyu navchalnoyi mnozhini budeP t c T c t T c displaystyle hat P t c frac T ct T c nbsp de T c t displaystyle T ct nbsp 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 nbsp 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 nbsp j P t c displaystyle hat P t c nbsp mozhna znajti klas dokumentac 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 nbsp 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 vikoristovuyetsyac 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 nbsp Cya formula maye prostu interpretaciyu Shansi klasifikuvati dokument klasom sho chasto zustrichayetsya vishe i dodanok log P c displaystyle log hat P c nbsp vnosit v zagalnu sumu vidpovidnij vnesok Velichina log P t c displaystyle log hat P t c nbsp tim bilsha chim vazhlivishij termin t dlya identifikaciyi klasu c i vidpovidno tim vagomishij yih vnesok v zagalnu sumu Zastosuvannya Redaguvatifiltraciya 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 dokumentiv RedaguvatiAvtomatichni 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 Metodi RedaguvatiMetodi 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 Glibinnij analiz ponyat en Klasifikator na bazi grubih mnozhin en Klasifikator na bazi m yakih mnozhin en Navchannya za naborom zrazkiv Obrobka prirodnoyi moviPrimitki Redaguvati Manning et al 2009 p 255Literatura RedaguvatiChristopher D Manning Prabhakar Raghavan Hinrich Schutze An Introduction to Information Retrieval Arhivovano 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 Arhivovano 5 zhovtnya 2020 u Wayback Machine MIT Press 2010 Div takozh RedaguvatiNayivnij bayesiv klasifikator Klasternij analiz Klasterizaciya dokumentivPosilannya RedaguvatiLekciya 6 po klasifikaciyi tekstiv kursu Suchasni zavdannya teoretichnoyi informatiki Arhivovano 15 Zhovtnya 2008 u Wayback Machine postanovka zadachi pobudova ta navchannya klasifikatora ocinka yakosti F Sebastiani Machine Learning in Automated Text Categorization PDF Arhivovano 28 Travnya 2016 u Wayback Machine angl Text mining Klasifikaciya tekstu Arhivovano 3 Zhovtnya 2011 u Wayback Machine Priklad klasifikaciyi dokumentiv z vikoristannyam programnih algoritmiv STATISTICA Otrimano z https uk wikipedia org w index php title Klasifikaciya dokumentiv amp oldid 40181114