www.romver.ru / Полный список статей / анализ алгоритмов

Dannaa rabota provoditsa v ramkax issledovania sposobov obespe4enia periodi4eskogo temati4eskogo poiska, 4to vklu4aet v seba i razrabotku takogo roda sistemi. Odnim iz osnovnix etapov raboti etoy sistemi avlaetsa etap klassifikacii tekstov. Poskol'ku ka4estvo rubrikacii vo mnogom opredelaet ka4estvo itogovogo rezul'tata, issledovanie algoritmov klassifikacii i sposobov predvaritel'noy obrabotki dokumentov, avlaetsa vajney6ey zada4ey.

Algoritmi klassifikacii rabotaut s nekotoroy matemati4eskoy model'u predstavlenia ekzemplara (v dannom slu4ae – tekstovogo dokumenta). Naibolee rasprostranennoy model'u avlaetsa predstavlenie v vide nabora priznakov, kotoroe i budet rassmotreno v dal'ney6em. Opredelenie priznakov i sopostavlenie im vesov avlaetsa su6estvenno neformal'nim 6agom i vo mnogom vliaet na rezul'tat klassifikacii. Po etoy pri4ine etap predvaritel'noy obrabotki dokumenta rassmatrivaetsa otdel'no.

2. Rassmatrivaemie algoritmi

V xode eksperimentov bili rassmotreni tri predstavitela semeystva lineynix algoritmov: metod opornix vektorov (SVM) [1], algoritm PrTFIDF[2] i modificirovanniy naivniy algoritm Bayesa[3].

Algoritmi PrTFIDF i naivniy algoritm Bayesa osnovani na statisti4eskoy modeli i imeut mnogo ob6ego. Dannie algoritmi predstavlaut interes, poskol'ku oni xoro6o mas6tabiruemi i obladaut visokoy proizvoditel'nost'u. Izvestnim ix nedostatkom avlaetsa sravnitel'no nizkaa to4nost' klassifikacii, osobenno v slu4ae binarnoy klassifikacii. Algoritm PrTFIDF rassmatrivaetsa v ka4estve bazovogo algoritma po radu pri4in:

• Eksperimental'no[2] pokazana bolee visokaa to4nost' klassifikacii po sravneniu s naivnim Bayesom i TFIDF[4]. Takje eto bilo podtverjdeno i v drugix eksperimentax, vixoda6ix za ramki dannoy stat'i.

• Danniy algoritm primenim dla analiza bol'6ogo koli4estva dokumentov i pozvolaet ispol'zovat' bol'6oe koli4estvo priznakov. Eto vajno, poskol'ku algoritm planiruetsa primenat' dla obrabotki bol'6ix ob&emov dannix.

Algoritm Bayesa v poslednee vrema ocenivaetsa kak sravnitel'no nizkoka4estvenniy algoritm. Osnovnimi pri4inami avlautsa problemi, svazannie s principom nezavisimosti priznakov i nekorrektnoy ocenkoy apriornoy veroatnosti v slu4ae su6estvenno neravnomo6nix obu4au6ix viborok. Predlojiv rad empiri4eskix modifikaciy algoritma ili dobaviv dopolnitel'nie priznaki, naprimer, na osnove vibora fraz v dokumente, mojno popitat'sa re6it' su6estvuu6ie problemi i polu4it' bolee ka4estvenniy algoritm, soxraniv ego prostotu, proizvoditel'nost' i mas6tabiruemost'.

Rezul'tati klassifikacii metodom opornix vektorov v poslednee vrema ocenivautsa[5] kak lu46ie ili odni iz lu46ix. Odnako, skorost' obu4enia dannogo algoritma sravnitel'no nizka (O(|D|^a, gde a>1,2[5])) i on trebuet bol'6ogo ob&ema pamati, 4to snijaet ego mas6tabiruemost'. Tem ne menee, danniy algoritm mojno ispol'zovat' v ka4estve etalona s to4ki zrenia ka4estva klassifikacii. Takje bili predlojeni modifikacii ocenki vesov priznakov, kotorie budut rassmotreni pozdnee.

Takim obrazom, trebovania k algoritmu klassifikacii v ramkax re6aemoy zada4i mojno sformulirovat' sleduu6im obrazom:

1. Ka4estvo klassifikacii doljno bit' sravnimo s ka4estvom metoda opornix vektorov.

2. Algoritm doljen obladat' nizkoy vi4islitel'noy slojnost'u i avlaetsa xoro6o mas6tabiruemim.

Rassmotrim predlagaemie modifikacii k su6estvuu6im algoritmam.

2.1 Metodika predvaritel'noy ocenki modifikaciy

Modifikacii algoritmov trebuut eksperimental'noy proverki dla ocenki ix vliania na algoritm. V ramkax dannoy raboti predvaritel'naa ocenka proizvodilas' na dvux testovix naborax: Newsgroup-20[6] i obu4au6ey kollekcii normativnix dokumentov. Dla vtoroy kollekcii v ka4estve obu4au6ey viborki bilo vibrano 40% dokumentov slu4aynim obrazom, ostal'nie dokumenti ispol'zovalis' dla ocenki to4nosti klassifikacii. Vtoraa viborka interesna sil'noy neravnomernost'u raspredelenia dokumentov po klassam i bol'6im koli4estvom klassov.

2.2 Modifikacii naivnogo algoritma Bayesa

Pravilo opredelenia klassa dla dokumenta v algoritme Bayesa mojno predstavit' sleduu6im obrazom:

]log)([log(maxarg)(Σ∈+=dwCwwCpfCpdC,

gde - koli4estvo vxojdeniy leksemi w v dokument, wf)|(CwppCw=

Dla bor'bi s nekorrektnim opredeleniem apriornoy uslovnoy veroatnosti priznakov v slu4ae neravnomo6nix obu4au6ix viborok, predlagaetsa ispol'zovat' paradigmu klassa-dopolnenia, to est' vmesto veroatnosti prinadlejnosti leksemi klassu ocenivat' veroatnost' prinadlejnosti leksemi klassu-dopolneniu C’ (sleduet u4est', 4to p(w|C) ~ 1-p(w|C’)).Ispol'zua princip sglajivania parametrov po Laplasu, polu4aem sleduu6ee pravilo:

])||1log()([log(maxarg)(Σ∈++−=dwCCwwCVNNfCpdC

gde CwN- koli4estvo leksem vo vsex klassax krome dannogo, CN-ob6ee koli4estvo leksem v klasse-dopolnenii, -razmernost' slovara leksem. ||V

Sleduet otmetit', 4to dannaa evristika rabotaet tol'ko v tom slu4ae, esli koli4estvo klassov N >> 2.

Dla dal'ney6ego ulu46enia ka4estva klassifikacii predlagautsa sleduu6ie priemi:

• Logarifmi4eskoe sglajivanie 4astoti priznakov

• Normalizacia vesov priznakov v dokumente po ego dline

• Ispol'zovanie inversnoy 4astoti priznaka (IDF i IDF’[2])

• Normalizacia logarifmov vesov priznakov (log(p_Cw))

Predvaritel'nie eksperimenti pokazali ulu46enie to4nosti klassifikacii pri vklu4enii vsex evristik, krome logarifmi4eskogo sglajivania i ispol'zovania inversnoy 4astoti. V itoge pered okon4atel'nim progonom algoritma (dalee ModBayes) uxud6au6ie ka4estvo evristiki bili otklu4eni. To4nost' algoritma pri predvaritel'nom testirovanii okazalas' sravnimoy s to4nost'u SVM, pri etom to4nost' bazovogo algoritma Bayesa bila blizka k nulu.

2.3 Modifikacii algoritma SVM

Rassmatrivaemaa modifikacia algoritma svoditsa k trivial'nomu empiri4eskomu izmeneniu ocenki vesa priznakov. Izna4al'nie predposilki obuslovleni sleduu6im:

• Leksemi s visokoy inversnoy 4astotoy vozmojno bolee zna4imi, i sootvetstvenno doljni imet' bol'6iy ves, analogi4no predpolojeniam algoritma TFIDF.

• Esli leksema 4asto vstre4aetsa v dokumentax odnogo klassa, no redko v dokumentax drugogo, to eta leksema takje vozmojno bolee zna4ima, 4em leksema, vstre4au6aasa v malom koli4estve dokumentov, no vo mnogix klassax. V ka4estve primera mojno privesti dve situacii: leksema vstre4aetsa v desati dokumentax odnogo klassa, a drugaa po dva raza v oboix klassax. S to4ki zrenia inversnoy 4astoti vtoraa leksema budet imet' bol'6iy ves, no fakti4eski pervaa gorazdo bolee zna4ima dla ka4estvennogo razdelenia dvux klassov.

Takim obrazom bil predlojen sleduu6iy modifikator vesa leksemi:

'*)',(max'IDFCwTFCC∈, gde ΣΣ∈∈=CCFwCwTFCwTFDIDF'')','()',(||'

V xode predvaritel'nix eksperimentov na testovoy kollekcii Newsgroup-20 primenenie etoy evristiki privelo k nebol'6omu uveli4eniu to4nosti klassifikacii. Pri progone algoritma SVM na kollekcii normativnix dokumentov eta evristika bila vklu4ena.

3. Predvaritel'naa obrabotka dokumentov

Zada4ey etapa predvaritel'noy obrabotki dokumentov avlaetsa videlenie priznakov dokumenta i sopostavlenia im vesov. V prostey6em slu4ae mul'tinomial'noy modeli naborom priznakov dokumenta budet soderja6iysa v nem nabor leksem, a v ka4estve vesa ispol'zuetsa koli4estvo vxojdeniy leksemi v dokument.

Nedostatkom takogo podxoda avlaetsa to, 4to prakti4eski ne u4itivautsa osobennosti estestvennogo azika, a takje strukturirovannost' dokumenta i svazi mejdu dokumentami v slu4ae Web-stranic.

3.1 Obrabotka tekstov na estestvennom azike

Pri obrabotke teksta mojno videlit' neskol'ko etapov:

1. Leksi4eskiy analiz

2. Morfologi4eskiy analiz

3. Sintaksi4eskiy i post-morfologi4eskiy analiz

4. Videlenie fraz (n-gramm)

5. Ustranenie stop-slov

Pervie dva etapa dostato4no o4evidni: zada4ey pervogo avlaetsa videlenie leksem, a vtoroy na osnove nabora pravil i vnutrennego slovara sopostavlaet kajdoy lekseme nabor vozmojnix slovoosnov s ix grammati4eskimi xarakteristikami.

Ispol'zovanie sintaksi4eskogo analiza pozvolaet razre6it' zna4itel'nuu 4ast' slu4aev omonimii. Takje sintaksi4eskiy analiz mojet pozvolit' obespe4it' bolee to4nuu fil'traciu stop-slov i postroenie fraz na osnove sintaksi4eski svazannix leksem, 4to su6estvenno sokra6aet ix koli4estvo po sravneniu s polnim pereborom sosedey leksemi.

3.1.1 Sintaksi4eskiy analiz

Problemami su6estvuu6ix re6eniy v oblasti sintaksi4eskogo analiza (naprimer, LinkParser [7], Dialing[8]) avlautsa dostato4no nizkaa skorost' obrabotki teksta i 4uvstvitel'nost' k nekorrektnim sintaksi4eskim konstrukciam. Eti problemi sleduut iz oblastey primenenia etix re6eniy – proverka pravopisania i ma6inniy perevod. V zada4e klassifikacii tekstov trebovania k sintaksi4eskomu analizu neskol'ko drugie: visokaa skorost' obrabotki tekstov i rabota s sintaksi4eski nepolnimi fragmentami teksta, pri etom dopustimo nekotoroe uveli4enie pogre6nosti analiza.

Razrabotanniy v xode raboti sintaksi4eskiy analizator imeet mnogo ob6ego s algoritmom, ispol'zuemim v sisteme Dialing. Otli4ia zaklu4autsa v izmenenii spiska pravil i su6estvennom upro6enii fragmentacionnogo analiza. V rezul'tate algoritm bolee korrektno razbiraet sintaksi4eski nepolnie fragmenti, a skorost' obrabotki teksta virosla primerno na poradok.

Rezul'tatom raboti sintaksi4eskogo analizatora avlaetsa ustranenie morfologi4eskix neodnozna4nostey i postroenie nabora sintaksi4eski svazannix fraz. Post-morfologi4eskiy analiz pozvolaet bolee to4no opredelit' 4ast' re4i leksemi, sootvetstvenno etap fil'tracii stop-slov proizvoditsa posle sintaksi4eskogo analiza.

3.1.2 Vibor fraz

V predidu6em punkte mi rassmotreli vibor fraz na osnove sintaksi4eskogo analiza. Takje su6estvuut algoritmi vibora fraz, osnovannie na statisti4eskom analize. Sleduet otmetit', 4to pri ispol'zovanii takix algoritmov v 4istom vide analiziruetsa 4rezvi4ayno bol'6oe koli4estvo fraz, 4to zatrudnaet ix primenenie pri obrabotke bol'6ogo koli4estva dokumentov.

Rassmotrim dva bazovix algoritma otbora fraz. Sut' pervogo algoritma zaklu4aetsa v tom, 4to frazi rassmatrivautsa kak nekotoriy kontekst dla naibolee vesomix leksem v ramkax nekotoroy tematiki. Takim obrazom, fraza s4itaetsa «kontekstnoy», esli ona soderjit xota bi odin iz naibolee vesomix termov, predvaritel'no otobrannix po obi4nim algoritmam otbora priznakov.

Vtoroy algoritm osnovivaetsa na sleduu6em: esli dannaa fraza avlaetsa «ustoy4ivoy», to sredi mnojestva dokumentov, v kotorix vstre4autsa termi frazi, doljno bit' i dokumenti, v

kotorix prisutstvuet fraza. Takim obrazom, otbor «ustoy4ivix fraz» v ramkax nekotoroy tematiki svoditsa k sleduu6emu:

Dla kajdoy frazi rass4itivaetsa koli4estvo dokumentov , v kotorix ona vstre4aetsa. pN

Zatem rass4itivaetsa koli4estvo dokumentov , v kotorix vstre4autsa vse termi frazi. tN

Fraza s4itaetsa ustoy4ivoy, esli , gde K – nekotoriy koefficient stabil'nosti frazi, opredelaemiy eksperimental'no. tpNKN≥*

Na praktike pri analize bol'6ogo koli4estva dokumentov prixoditsa sovme6at' oba algoritma. Odnako, bolee perspektivnim predstavlaetsa sovmestnoe ispol'zovanie sintaksi4eskogo otbora fraz i fil'tracii fraz na osnove principa “ustoy4ivosti”.

3.2 Obrabotka Web-stranic

Ispol'zuemiy pri testax analiz Web-stranic dostato4no prost. V 4astnosti, neobxodimo re6at' problemu avtomati4eskogo opredelenia kodirovki, poskol'ku avno ona ukazivaetsa daleko ne vo vsex dokumentax. Re6enia etoy zada4i proizvodilos' v dva etapa:

• Analiz 4astoti vxojdenia naibolee 4asto ispol'zuemix liter

• V slu4ae, kogda 4astotniy analiz ne pozvolaet sdelat' opredelennogo vivoda, proizvoditsa proverka nali4ia 4asti videlennix leksem v morfologi4eskom slovare

V slu4ae, esli 4astotniy ili slovarniy analiz pokazali nesootvetstvie kodirovki, tekst dokumenta konvertiruetsa v druguu kodirovku.

Takje pri obrabotke dokumenta proizvodilos' uveli4enia vesa leksem, vxoda6ix v zagolovki, nazvanie, klu4evie slova, tekst ssilki i t.p.

4. Rezul'tati eksperimentov

4.1 Dorojka klassifikacii Web-stranic

V etoy dorojke bil proveden odin progon. V ka4estve algoritma klassifikacii ispol'zovalsa modificirovanniy algoritm PrTFIDF. V xode predvaritel'noy obrabotki tekstov ispol'zovalsa

morfologi4eskiy analiz na osnove slovarey ISpell i analiz strukturi Web-stranici. Osnovnoy cel'u dannogo progona bilo sravnit' algoritm s drugimi na bol'6om ob&eme real'nix dannix.

Polu4ennie rezul'tati okazalis' xuje, 4em u drugix u4astnikov seminara, 4to vo mnogom ob&asnaetsa slabost'u algoritma v slu4ae neravnomo6nix obu4au6ix viborok i pokazivaet fakti4eskuu neprimenimost' etogo algoritma dla takogo roda zada4. Eto podtverdilos' i pri testirovanii na obu4au6ey kollekcii normativnix dokumentov.

4.2 Dorojka klassifikacii normativno-pravovix dokumentov

V ramkax dorojki klassifikacii normativnix dokumentov bilo provedeno 4etire progona:

Progon 1. algoritm PrTFIDF.

Progon 2. algoritm PrTFIDF so statisti4eskim viborom fraz.

Progon 3. modificirovanniy naivniy algoritm Bayesa s ispol'zovaniem post-morfologii i 4asti4nim viborom fraz

Progon 4. modificirovanniy algoritm SVM s ispol'zovaniem post-morfologii i 4asti4nim viborom fraz

Cel'u progonov bilo opredelit' stepen' vliania vibora fraz na ka4estvo klassifikacii, a takje sravnitel'nuu ocenku algoritmov PrTFIDF, modificirovannogo algoritma Bayesa i SVM.

00,10,20,30,40,50,60,7F1(macro)F1(micro)xxxxxxxxPrTFIDF+phrasePrTFIDFModBayesSVMxxxxxxxxxxxxxxxxxxxxxxxx

Ris.1 Sravnenie ka4estva klassifikatorov

Rezul'tati progonov okazalis' su6estvenno otli4nimi ot rezul'tatov, polu4ennix v xode predvaritel'nix eksperimentov i ix dostato4no slojno interpretirovat', osobenno srednevzve6ennuu po dokumentam ocenku F1. V 4astnosti, mojno obnarujit', 4to algoritm PrTFIDF prevosxodit SVM, 4to mojno ob&asnit' razve 4to neuda4nim podborom modifikatorov vesov. Tem ne menee, v slu4ae predvaritel'nogo testirovania na obu4au6ey viborke kollekcii normativnix dokumentov viigri6 SVM bil bolee 4em su6estvennim.

Takje sleduet otmetit' otsutstvie viigri6a pri ispol'zovanii vibora fraz, 4to stavit pod somnenie ispol'zovanie statisti4eskogo vibora v 4istom vide. V predvaritel'nix eksperimentax statisti4eskiy (na nabore Newsgroup-20) i sintaksi4eskiy (na obu4au6ey kollekcii) vibor fraz pokazivali ulu46enie to4nosti dla vsex analiziruemix algoritmax v diapazone ot 1 do 4%.

Itogovie rezul'tati, v tom 4isle i po modificirovannomu algoritmu Bayesa, su6estvenno rasxodatsa s ojidaemimi, 4to trebuet dopolnitel'nogo issledovania.

4.3 Eksperimenti na obu4au6em nabore kollekcii normativno-pravovix dokumentov

V xode analiza rezul'tatov klassifikacii bil obnarujen rad slabostey ispol'zuemix algoritmov. Dla re6enia naydennix problem bil predlojen rad modifikaciy k algoritmu Bayesa, a takje predlojen algoritm ModSimpl, osnovanniy na postroenii neskol'kix razdelau6ix giperploskostey, sootvetstvuu6ix diskriminantu Fi6era.

Eksperimenti, provedennie na obu4au6em nabore normativnix dokumentov (vne ramok seminara ROMIP) pokazali rezul'tati, pozvolau6ie govorit' o perspektivnosti etix algoritmov.

© Maksakov Aleksey

VMiK MGU

bruzz@yandex.ru