Szolnoki Tudományos Közlemények XV. Szolnok, 2011.
Subecz Zoltán1
Információkinyerés természetes nyelvű szövegekből
STOPSZÓ SZŰRÉS, LEMMATIZÁLÁS HATÁSA ÉS OSZTÁLYOZÁS A VEKTORTÉR MODELLEL A természetes nyelvi feldolgozás egy új interdiszciplináris terület. Ennek a területnek a célja a számítógép segítségül hívása olyan feladatokban, mint a természetes szövegek feldolgozása, az ember-gép közötti kommunikáció elősegítése és egyéb szöveg feldolgozási feladatok. Az Interneten több millió természetes nyelven írt oldal található, amelyek nincsenek feldolgozva. Enne az új kutatási területnek az egyik célja olyan programozási módszerek kidolgozása, amelyek segítségével ezen oldalak szövegéből minél több információ kinyerhető és táblázatokba, adatbázisokba lementhető. A táblázatokból és adatbázisokból a ez az információ a későbbiekben már könynyen lekérdezhető. Jelen publikációban bemutatom a stopszó szűrést és a lemmatizálást és ezek hatását a Vektortér modellre, valamint a szövegek osztályozását a Vektortér modell segítségével. THE EFFECT OF THE STOPWORD FILTERING AND LEMMATIZATION TO THE VECTORSPACE MODEL AND ITS USAGE IN A CLASSIFICATION TASK The natural language processing is a new interdisciplinary field. The goal of this new field is to get computers to perform useful tasks involving human language, tasks like enabling human-machine communication, improving human-human communication, or simply doing useful processing of text or speech. What distinguishes language processing applications from other data processing systems is their use of knowledge of language. The natural language processing uses some formal models or theories. These models and theories are all drawn from the standard toolkits of computer science, mathematics, and linguistics. Among these models is the Vectorspace model. In a classification task, we are given some observations and our job is to determine which of a set of classes a document belongs to. In this article, I rewieved the effect of the stopword filtering and lemmatization to the Vectorspace model and I created a program for text classification and I tested it in a multi-thousand document environment. [1]
1.BEVEZETÉS Kutatási témám: Információkinyerés természetes nyelvű szövegekből. Előző és jelen publikációban is az Interneten megtalálható Ingatlanközvetítői hirdetések természetes nyelvű szövegein vizsgáltam meg az információkinyerés adott módszereit.
1
Szolnoki Főiskola, Gazdaságelemzési és Módszertani Tanszék, főiskolai tanársegéd, Email:
[email protected] A cikket lektorálta: Madaras Lászlóné Dr., Szolnoki Főiskola, főiskolai tanár, PhD.
Előző publikációmban áttekintettem a szöveg-feldolgozási lépéseket a Vektortér modellig. [3] Ebben a publikációban bemutatom a stopszó szűrést és a lemmatizálást és ezek hatását a Vektortér modellre, valamint a szövegek osztályozását a Vektortér modell segítségével. A megvalósítás során a következő lépéseket végeztem el: Stopszó szűrés vizsgálata Lemmatizálás vizsgálata Osztályozás a Vektortér modellel A stopszó szűrés és a lemmatizálás hatása az osztályozás eredményére Ezekhez a feladatokhoz Java programozási nyelven írtam programokat. A kutatási anyag a következő weboldalon megtalálható: http://kutat.uw.hu/Tema2/Tema2.html Ez tartalmazza az alábbiakat: Java nyelven írt forrásprogramok, a programok kimeneti és bemeneti fájljai, a programok részletes leírásai. 1.1. Az információkinyerés és szövegbányászat Az információkinyerés (IE, Information Extraction) technológiájának kutatása dinamikusan fejlődő terület a természetesnyelv-feldolgozásban. Az interneten megjelenő hatalmas információtömeg gépi feldolgozása és a kívánt információ tömör formában történő összegyűjtése napi szükséglet, amelyre a gazdaság, a tudomány, a politika területén is van igény. Míg az információ visszakeresés (IR, Information Retrieval), amely a webes kereső programok jellemző tevékenysége, arra irányul, hogy a felhasználó igényeinek megfelelő dokumentumokat változatlan formában bocsássa rendelkezésre, addig az információkinyerés célja a megtalált dokumentumokban a lényeges információ megjelölése, majd összegyűjtése. Az utóbbi években az informatika egyik leggyorsabban fejlődő részterülete az adatbányászat lett. Ez az új tudományág szolgál a nagy mennyiségű adatokban rejlő információk automatikus feltárására mesterséges intelligencia algoritmusok alkalmazásával (például neurális hálók, szabálygenerálók, asszociációs modellek). Az adatbányászat egyik igen fontos részterülete a szövegbányászat, amely a strukturálatlan (vagy részben strukturált), elektronikus szöveges állományokban megbúvó, nem triviális információk kinyerését jelenti. Az új alkalmazási lehetőségek közül a web-bányászat az egyik legígéretesebb, mivel a világ legnagyobb és leggyorsabban bővülő adattárát, az internetet használja. A web-bányászat célja, hogy az internethez kapcsolható dokumentumokból (honlapok, e-mailek, blogok, fórumok stb.) hasznos információkat automatikus összegyűjtsön. Ilyen feladat lehet például állásajánlatok automatikus összegyűjtése vállalati honlapokról, vagy újsághírekben egy vállalkozásról fellelhető információk kinyerése. Az így nyert információ strukturált szerkezetű (mezőértékekből áll), azaz például betölthető egy adatbázisba. 1.2. A Java programozási nyelv A szövegbányászati feladatokra programokat kell írni valamilyen programozási nyelven. Ehhez a feladathoz a Java programozási nyelvet választott am, mert a Számítógépes Nyelvészet alkalmazásainak nagy része ezen a nyelven íródott. Így a modulok jól illeszthetők egymáshoz. 2
A Java általános célú, objektumorientált programozási nyelv, amelyet a Sun Microsystems fejleszt a ’90-es évek elejétől kezdve napjainkig. A Java nyelv szintaxisát főleg a C és a C++ nyelvektől örökölte, viszont a Java sokkal egyszerűbb objektummodellel rendelkezik, mint a C++.
2. A VEKTORTÉR MODELL A szövegbányászatban a tartalmak tömör reprezentációjára a vektortér modell (VTM) nyújtja a legszélesebb körben használt megoldást. A modell minden egyes dokumentumot egy vektorral ír le, amelyben minden elem az egyes termek (általában szavak) előfordulását jelenti. Termek alatt a reprezentáció egységeit, alapesetben az írásjelek által határolt szavakat (unigram) értjük. Adva van egy dokumentumgyűjtemény, amelynek elemein valamilyen rendszerezési műveletet kívánunk végrehajtani. Ehhez olyan modellt kell felépítenünk, amiben a dokumentumok távolságát, vagy hasonlóságát egyszerűen meg tudjuk határozni. Intuitív módon nyilván azok a dokumentumok hasonlítanak egymásra, amelyeknek a szókészlete átfedi egymást, és a hasonlóság mértéke az átfedéssel arányos. Ezt a megfigyelést használja fel az információvisszakeresésben (information retrieval IR) széles körben használt vektortér modell. A vektortér modellben a D={d1,…,dN} dokumentumgyűjteményt a szó-dokumentum mátrixszal (term-document mátrix) reprezentáljuk (D Є RMxN), ahol a mátrix dki eleme a k-adik szó(tk) relevanciáját reprezentálja az i-edik dokumentumban, di-ben. A di dokumentumot reprezentáló dokumentumvektort di=
- vel jelöljük. A D mátrixban a sorok száma, M megegyezik az egyedi szavak számával. N pedig a dokumentumok száma. 𝐷=
𝑑11 𝑑12 … 𝑑1𝑁 𝑑21 𝑑22 … 𝑑2𝑁 … … … … 𝑑𝑀1 𝑑𝑀2 … 𝑑𝑀𝑁
(1)
A dokumentumvektorok tehát a mátrix oszlopai lesznek. A mátrix egy sora azon pozíciókban tartalmaz nullától különböző értéket, amelyekhez tartozó dokumentumokban a szó nem nulla relevanciájú. Ez általában ekvivalens azzal, hogy a szó nem szerepel a dokumentumban, de ettől eltérő esetekben is lehet a relevancia nulla. Az egyedi szavak összességét szótárnak, vagy lexikonnak nevezzük, jelölése: T. A szótár mérete tehát |T|=M. Mivel általában egy dokumentumban a szótár szavainak csak egy kis töredéke fordul elő, ezért a D mátrix ritka. Ugyanakkor az egyedi szavak száma rendkívül nagy lehet, akár a milliós nagyságrendet is elérheti.
3. BEVEZETŐ LÉPÉSEK A stopszó szűrés és a lemmatizálás vizsgálatához 1000 ingatlanközvetítői oldalt töltöttem le az Internetről. Az 1000 dokumentumhoz elkészítettem a Vektortér mátrixot a következő lépések segítségével. (A lépéshez Java nyelven írtam programokat. Azok részletes leírása megtalálható az előző publikációban [3]) HTML oldalakról szöveg kivétele
3
A jelen kutatás szempontjából csak az oldalakon lévő természetes nyelvi szövegek az érdekesek. Azokból kell az információt kigyűjteni. Egy hirdetési oldalon a hirdetési szövegen kívül sok egyéb adat, található. Szövegek szavakra bontása A hirdetési szövegekből kigyűjti a szövegben található szavakat egy másik szövegfájlba egymás alá. Átalakítás - Fölösleges karakterek kiszűrése - Szövegek kisbetűssé alakítása Fájlok egymáshoz fűzése (egyutt.txt) - 1000 fájl szavait összefűzi 1 szöveges fájllá - 148 286 szót tartalmaz a fájl Ez a fájl tartalmazza az 1000 dokumentum minden szavát. Statisztika az előző összefűzött fájlról (4 darab szövegfájl) - Minden szó kigyűjtése, de minden szót csak egyszer. Vannak szavak, amelyek sokszor előfordulnak az 1000 dokumentumban - Minden szó mellé kiírtam, hogy hányszor fordul elő a dokumentumokban összesen. - Készítettem egy olyan szövegfájlt is, amelyikben az előző az előfordulások szerint csökkenően van kigyűjtve. Így a listában előre kerültek a gyakori szavak. Szavak rendezése, egyediek megtartása (rendezett.txt) 16 991 szó Így abc sorrendbe megkapjuk az 1000 dokumentum egyedi szavait. A Vektortér mátrix elkészítése a feldolgozás során elkészített dokumentumok alapján.
4. STOPSZÓ SZŰRÉS A szövegbányászati feladatok többségénél a gyakran előforduló, tartalmi információt egyáltalán nem tartalmazó, megkülönböztető képesség nélküli un. stop szavakat már a szavakra bontás után elhagyják. A szótárból való elhagyásukkal csökkenthető a szó-dokumentum mátrix bejegyzéseinek a száma. [2] 4.1 A stopszó szűrés bemutatása a saját 1000 dokumentumból álló korpuszon Az előző fejezetben készítettem egy olyan statisztikai fájlt, amiben kiírattam, hogy az egyes szavak hányszor szerepeltek. (Darabszám szerint csökkenően) Ebből az első 50 szó: a: 12145 db az: 3730 db és: 3405 db egy: 2005 db es: 1736 db is: 1708 db ház: 1539 db található: 1398 db van: 1156 db
lakás: 850 db 2: 811 db nm: 802 db családi: 734 db ingatlan: 726 db épült: 625 db két: 606 db m2: 603 db eladó: 601 db konyha: 570 db
3: 566 db szoba: 550 db fürdőszoba: 543 db nappali: 509 db csendes: 453 db jó: 448 db külön: 412 db ben: 408 db nagy: 396 db garázs: 390 db
épület: 359 db telken: 352 db de: 347 db valamint: 339 db perc: 337 db minden: 328 db el: 324 db 1: 319 db wc: 317 db 5: 309 db
1. táblázat. A leggyakoribb szavak
4
szinten: 297 db szobás: 290 db tartozik: 290 db m: 287 db megközelíthető: 275 db 4: 274 db belső: 271 db még: 268 db 10: 264 db étkező: 261 db alkalmas: 258 db
Azoknak a szavaknak, amelyek sokszor szerepelnek (pl. névelők) kevés a jelentősége. Ezért ezeket kihagyhatjuk a vektortér modellből. Olyan szavakat érdemes csak kihagyni a vektortér modellből, amelyek nem hordoznak információt a későbbi feldolgozáshoz. Igaz, hogy a ház szó sok dokumentumban szerepel (ház: 1539 db), de majd egy olyan osztályozási feladatban, ahol pl. két csoportra kell kigyűjteni a családi házakat és a lakásokat, akkor a ház szónak lesz jelentősége Így látjuk, hogy a stopszavak kiválasztása nem egyszerű feladat. A kiválasztás gyakran az adott feladattól függ: - pl. az épült: 625 db szó nem hordoz önmagában sok információt - De ha azokat a hirdetéseket keresem, amelyek tartalmazzák, hogy mikor épült az épület, akkor már megnő a jelentősége. Így van olyan feladat ahol csak néhány szó hagyható el, de van ahol akár több száz, vagy több ezer is. A leggyakoribb 50 szóból a pirossal jelzettek általában elhagyhatóak. Az osztályozásnál majd megvizsgáljuk a Stopszó szűrés hatását. A Szegedi Tudományegyetem Mesterséges Intelligencia Kutatócsoportja a következő szavakat használja a Stopszó szűréshez: (stopword.txt: 219 db szó) a abban ahhoz ahogy ahol aki akik akkor akár alatt amely amelyek amelyekben amelyeket amelyet amelynek ami amikor amit amolyan amíg annak arra arról az azok azon azonban azt aztán azután
azzal azért be belül benne bár cikk cikkek cikkeket csak de e ebben eddig egy egyes egyetlen egyik egyre egyéb egész ehhez ekkor el ellen elő először előtt első elég előtt
emilyen ennek erre ez ezek ezen ezt ezzel ezért fel felé ha hanem hiszen hogy hogyan hát ide igen ill ill. illetve ilyen ilyenkor inkább is ismét ison itt jobban jó
jól kell kellett keressünk keresztül ki kívül között közül le legalább legyen lehet lehetett lenne lenni lesz lett ma maga magát majd meg mellett mely melyek mert mi miatt mikor milyen
minden mindenki mindent mindig mint mintha mit mivel miért mondta most már más másik még míg nagy nagyobb nagyon ne nekem neki nem nincs néha néhány nélkül o oda ők őket
2. táblázat Stop szavak gyűjteménye
5
olyan ott pedig persze például rá s saját sem semmi sok sokat sokkal stb. szemben szerint szinte számára szét talán te tehát teljes ti tovább továbbá több túl ugyanis utolsó után utána
vagy vagyis vagyok valaki valami valamint való van vannak vele vissza viszont volna volt voltak voltam voltunk által általában át én éppen és így ön össze úgy új újabb újra ő őket
A további feladatokban én is ezt a szógyűjteményt fogom használni.
5. LEMMATIZÁLÁS A legtöbb nyelvben a szavaknak vannak toldalékolt vagy módosított alakjai is. Ez különösen jellemző a magyar nyelvre. A vektortér-modell kialakításánál kézenfekvő ötlet, hogy az azonos szavaknak a különböző szóalakú előfordulásait közös kanonikus alakba vonjuk össze, és összesítve reprezentáljuk. Ezzel ugyan a szóalakra vonatkozó információt elveszítjük, de a vektortér modell méretét jelentősen csökkenthetjük. [2] 5.2 A lemmatizálás bemutatása a saját 1000 dokumentumból álló korpuszon A 3. fejezetben készítettem egy olyan statisztikai fájlt, amiben kiírattam az egyedi szavakat abc sorrendben. A következő szavak kezdődtek a ház szótővel: ház háza házacskával házak házakat házakból házakhoz házakkal
házaktól házas házasok házasoknak házaspár házat házba házban
házból házhoz házi háziasszony háziasszonynak háziasszonyok házigazda házikertben
házikó házikót házimozi háziállatok házként házközponti házmesterlakást háznak
háznyira háznál házon házra házrésszé házrész házrészhez házrésznek
házrészt házról háztartás háztartáshelyiség háztartási háztetők háztól háztömb
házukat házvezetőnőnek házzal házzá házát házé
3. táblázat. A ház szótővel kezdődő szavak
A szavak lemmájának megtalálása sem mindig egyértelmű feladat. A pirossal bejelölt szavak lemmája lehet a ház szó. A Szegedi Tudományegyetem Mesterséges Intelligencia Kutatócsoportja is használ lemmatizálásra egy fájlt (corpus.lex) mérete: 4,6 MB, Sorainak száma: 133 387 Ebben a fájlban a következő szavakhoz rendeli a ház lemmát: ház háza házai házaiba házaiban házaiból házait
házak házakat házakban házakból házakhoz házakkal házaknak
házam házamat házat házba házban házból házhoz
háznak háznál házon házra házról háztól házuk
házukat házukba házukból házukhoz házunk házunkat házunkba
házunkban házunktól házzal házába házában házából házán
4. táblázat. A ház lemmához tartozó szavak
A további feladatokban én is ezt a fájlt fogom használni lemmatizálásra.
6
házának házát házától házával
6. STOPSZÓ SZŰRÉS HATÁSA A VEKTORTÉR MÁTRIXRA A következőkben megvizsgáltam a stopszó szűrés hatását a Vektortér mátrixra. A rendezett.txt fájlból azokat másoltam át a stopszavaknelkul.txt fájlba, amelyek nem szerepeltek a stopword.txt fájlban. A vizsgálat eredménye: Stopszavak száma: 219 (stopword.txt) Beolvasott sorok száma: 16 991 (rendezett.txt) Kiírt sorok száma: 16 810 (stopszavaknelkul.txt) A Vektortér mátrix mérete nem csökkent jelentősen. (1%-os csökkenés), de a jelentéssel nem bíró szavak kikerültek a további vizsgálatokból. Szerepelt stop szavak száma: 181 (16 991 – 16 810) (megtalált-stopszavak.txt) Nem szerepelt stopszavak száma: 32 (213-181) A következő stopszavak szerepeltek a kiindulási (rendezett.txt) fájlban: a ahhoz ahogy ahol aki akik akkor akár alatt amely amelyek amelyet amelynek ami amikor amit amíg annak arra az azok azon azonban azt azzal be belül benne bár
csak de e ebben eddig egy egyes egyetlen egyik egyre egyéb egész ehhez ekkor el ellen első elég elő először előtt ennek erre ezek ezen ezt ezzel ezért fel
ha hanem hiszen hogy hogyan hát ide igen ill illetve ilyen inkább is ismét itt jó jól kell keresztül kívül között közül le legalább legyen lehet lenne lenni lesz
ma maga magát majd meg mellett mely melyek mert mi miatt mikor milyen minden mindenki mindent mindig mint mintha mit miért most már más másik még míg nagy nagyobb
7
ne nem nincs néhány nélkül oda olyan ott pedig persze például rá s saját sem sok sokat sokkal szemben szerint szinte számára szét talán tehát teljes tovább továbbá több
ugyanis utolsó után vagy vagyis valaki valami valamint való van vannak vele viszont volna volt voltak által általában át én éppen és így ön össze úgy új újabb újra
cikk
felé
lett
nagyon
túl
ő ők
5. táblázat. A dokumentumokban szereplő stop szavak
A következő stopszavak nem szerepeltek a fájlban: abban amelyekben amelyeket amolyan arról aztán azután azért cikkek cikkeket
emilyen ez ill. ilyenkor ison jobban kellett keressünk ki lehetett
mivel mondta nekem neki néha ő ők őket semmi stb.
te ti utána vagyok vissza voltam voltunk őket
6. táblázat . A dokumentumokban nem szereplő stop szavak
7. LEMMATIZÁLÁS HATÁSA A VEKTORTÉR MÁTRIXRA A stopszavaknelkul.txt fájlban lévő szavakra (16 810 darab szó) megnéztem, hogy melyik szerepel a corpus.lex fájlban. Amelyik szerepelt, azt a lemmájával helyettesítettem. (Lemmatizált-nyers.txt) A vizsgálat eredménye: corpus.lex fájl sorainak a száma: 133 386 stopszavaknelkul.txt-ből beolvasott sorok száma: 16 810 Ennyi szóhoz talált lemmát: 7069 Vagyis a 16 810 szóból 7069 szóhoz talált lemmát. (42%) Kimeneti fájl: Lemmatizált-nyers.txt (Ez is természetesen 16 810 db sort tartalmaz.) Szavak rendezése-egyediek megtartása: Mivel több szónak is van azonos lemmája, pl. házakban, házakból, házakhoz, házakkal,…. => ház ezért a Lemmatizált-nyers.txt fájlban vannak azonos sorok. Ezért ezt a fájlt rendeztem, és az egyedi szavakat magtartottam. (Lemmatizált.txt) Ennek eredménye: A stopszavaknelkul.txt és a Lemmatizált-nyers.txt fájlok sorainak a száma: 16 810 Lemmatizált.txt sorainak a száma: 13 873 A kettő aránya vezet a lemmatizálás hatásfokához: 13 873 / 16 810 = 0,82 Így a Lemmatizálás 18%-al csökkentette a Vektortér mátrix sorainak a számát.
8
8. DOKUMENTUMOK OSZTÁLYOZÁSA A VEKTORTÉR MODELL SEGÍTSÉGÉVEL 8.1 Az osztályozás elmélete A dokumentumok visszakereshetőségét nagy mértékben segíti, ha rendszerezve tároljuk őket. Például, ha hierarchikus rendszerbe, un. taxonómiába rendszerezzük. Itt a tartalom szerinti besorolást vizsgáljuk. A dokumentumok tartalom szerinti rendszerezésének automatizálása az egyik legalapvetőbb szövegbányászati feladat, amelyet osztályozásnak neveznek. Az osztályozás célja szöveges dokumentumok előre definiált halmazból vett tematikus kategóriacímkékkel való ellátása. Az alkalmazások spektruma igen széles, pl. a rögzített tárgyszó-halmaz alapú dokumentumannotálás, a dokumentumszűrés (pl. kéretlen leveleké), webes dokumentumgyűjtemények feltöltése, vélemények értékelése stb. A gépi tanulási (machine learning) módszernél tanítóadatok alapján készül el a kategóriák jellegzetességeit felismerni képes osztályozó. Az emberi erőforrásra csak a kategóriákból és a hozzájuk rendelt dokumentumokból álló tanító környezet előállításánál van szükség, ettől eltekintve az osztályozó létrehozása teljesen automatizálható. A szövegosztályozás bármely területen való sikeres alkalmazásának előfeltétele a megfelelő minőségű tanítókörnyezet megteremtése. Az osztályozás feladata dokumentumok kategóriacímkékkel való ellátása. Formálisan egy Ф: D → 2C osztályozófüggvény megalkotása a cél, amely a D dokumentumtér elemeihez a C={ c1,…,c|C|} kategóriarendszerből vett kategóriák (más néven osztályok) halmazát rendeli. A Ф függvényt osztályozónak nevezzük. Az osztályozót ismert kategóriájú dokumentumokból kinyert információk alapján építjük fel. Ezeket tanítódokumentumoknak nevezik. A tanítódokumentumok a hozzájuk rendelt osztályokat jól jellemző mintaadatok. Az osztályozó tanulóalgoritmusa a tanítódokumentumok alapján megtanulja az egyes osztályok jellegzetességeit, ebből modellt készít, amellyel becslés adható ismeretlen kategóriájú dokumentumok címkéjére. A tanulásnak ezt a fajtáját felügyelt tanulásnak (supervised learning) nevezik, ahol a szakértő az általa megadott tanítóadatokon keresztül felügyeli a tanulás folyamatát. A bináris osztályozás esetén csak két osztályunk van. Ahhoz, hogy a felépített osztályozó hatékonyságát meghatározhassuk, szükség van tesztadatokra. Ennek érdekében a kiinduló D dokumentumgyűjteményt két diszjunkt halmazra bontjuk, tanító- és teszthalmazra (training/test set). DTrain ∩ DTest=0, és DTrain U DTest =D Az osztályozót a DTrain dokumentumain megfigyelt jellemzők alapján induktív következtetéssel hozzuk létre. A DTest teszthalmaz elemeit az osztályozó hatékonyságának megállapítására használjuk. A tesztadatok nem használhatóak fel az osztályozó felépítésénél. 8.2 Rocchio osztályozó A lineáris osztályozók építésének egyik módja a kategóriát reprezentáló cj kategóriavektornak a dokumentumtér elemeként való meghatározása. A dokumentum és a kategória hasonlósága ekkor egyszerűen meghatározható a két vektor koszinusz-távolságaként.
9
M k =1 w ik w jk
s 𝐝i , 𝐜j =
M w2 k =1 ik
(2)
M w2 k =1 jk
Ez az érték a dokumentum- és a kategóriavektorok által bezárt szög koszinuszát adja meg. A koszinusz távolság kiszámítása a két vektor skaláris szorzatából következik: a*b = |a|*|b|*cos α (3) cos α =
𝐚∗𝐛
(4)
a ∗|b|
Két vektor távolságának jellemzésére koszinusz-távolság pontosabb értéket ad, mint a Manhattan vagy az Euklidészi távolság: Manhattan távolság (x, y) = Euklidészi távolság (x, y) =
N i=1 |xi
− yi |
(5)
N i=1(xi
− yi )2
(6)
Az osztályozás folyamata a következőképpen történik: Minden dokumentumot ahhoz a kategóriához rendelünk,a melyikre a koszinusz-távolság nagyobb lesz. Mivel cos 0° = 1 és cos 90° = 0, ezért minél kisebb a távolság két dokumentum között, annál nagyobb a bezárt szög koszinusza. A legegyszerűbb módszer a cj kategóriavektorok meghatározására a centroidok használata. A cj osztály centroidját az osztályba tartozó dokumentumvektorok átlagaként definiáljuk: 𝐜𝑗 =
1 |Pos j |
d i∈Pos
j
𝐝i
(7)
di: a dokumentumvektorok Posj: a cj kategóriába tartozó tanítódokumentumok Az osztályozás lépései tehát az alábbiak lesznek: tanulás: a tanítóadatok átlagaként határozzuk meg minden cj kategória centroidját. tesztelés: a di dokumentum osztályozásakor számítsuk ki a koszinusztávolságot a dokumentum és a centroid között az összes kategóriára, és válasszuk ki azt a kategóriát, amelyikre a koszinusz-távolság a legnagyobb. [2] 8.3 Az osztályozás megvalósítása a Vektortér mátrixszal Kiválasztottam az Ingatlanhirdetések közül 1000 darabot, ami családi házakra és 1000 darabot, ami panel-lakásokra vonatkozott. Ennek módszere: Ezekben az Internetes hirdetési fájlokban van egy kis táblázat, amiben az ingatlan fontosabb adatai össze vannak foglalva. Például:
10
Az ingatlan típusa (pl. Családi ház, Panel, Társasházi) is itt található a Típus szó után. A HTML fájlban ennek a helyét megkeresve látható, hogy a Típus a Típus | kódrészletben van, amit követ pl. a Családi ház | kódrészlet. Így először meg kell keresni a Típus | kódrészletet. Majd az ezt követő és | közötti részt kell kiválasztani. Erre a 2 000 dokumentumra is elvégeztem a 3. fejezet lépéseit. Aminek segítségével megkaptam a Vektortér mátrixot. a mátrix sorainak száma: 20 968 oszlopainak száma: 2000 Így a mátrixnak 20 968*2000 = 41 936 000 cellája van Vektorter-tomb.t mérete: nagyobb, mint 167 MB A fájlt becsomagolva: kb. 600 KB Ez is mutatja, hogy a Vektortér mátrix egy ritkán kitöltött mátrix: elemeinek nagy része = 0. 8.4 Centroidok meghatározása (lásd 8.1 fejezet) Tanulás: meghatározzuk mindkét kategória centroidját a tanító adatok alapján Osztályozás: minden új, ismeretlen dokumentumra meghatározzuk a dokumentum a centroidtól való „távolságát”. Két dokumentum (vektor) távolságának egyik meghatározási lehetősége: a két vektor koszinusz-távolságával. A 2000 dokumentum így 2 osztályra osztható: 1-1000: Családi házak 1001-2000: Panel-lakások Ez a 2000 dokumentum a tanító adat. Az új dokumentumok lesznek a teszt adatok.
11
Mindkét osztályra meghatároztam az osztály centroidját. A Vektortér mátrix sorainak száma: 20 968. Így mindkét centroid egy 20 968 elemű vektor (tömb). A centroid jól jellemzi az adott osztályt. Egy új, a rendszernek ismeretlen dokumentum esetén a két centroiddal hasonlítja öszsze a dokumentum vektorát. Amelyikhez közelebb van, abba az osztályba sorolja a dokumentumot. 8.5 Tesztelés az eredeti 2000 dokumentummal Először megnéztem, hogy a program által „ismert” 2000 dokumentumra hogyan működik az Osztályozás. Ennél csak rosszabb eredmény várható új, ismeretlen dokumentumokra.
A dokumentum vektorához kiszámítottam a koszinusz értéket a két centroidhoz képest. amelyikhez nagyobb a koszinusz érték, abba az Osztályba soroltam az adott dokumentumot. A vizsgálat eredménye: jo1= 991; rossz1= 9; jo2= 991; rossz2= 9 Az 1000 családi házból 991-et jól besorolt a családi házak közé. 9-et rosszul a panellakások közé. Az 1000 panel-lakásból 991-et jól besorolt a panel-lakások közé. 9-et rosszul a családi házak közé. (A rossz1= 9.0 és rossz2= 9.0 egybeesés véletlen.) 8.6 Tesztelés új dokumentumokkal Kiválasztottam új, a rendszer számára ismeretlen 1000 - 1000 dokumentumot. Elvégeztem ezekre a dokumentumokra is a 3. fejezetben leírt átalakításokat. Elvégeztem a 8.4 pontban leírt tesztelést mind a 2000 új dokumentumra. A vizsgálat eredménye: jo1= 969; rossz1= 31; jo2= 989; rossz2= 11 Az 1000 családi házból 969-et jól besorolt a családi házak közé. 31-et rosszul a panellakások közé. Az 1000 panel-lakásból 989-et jól besorolt a panel-lakások közé. 11-et rosszul a családi házak közé. Az osztályozás eredményei jók lettek! A felidézés a pontosság értékek jól jellemzik egy osztályozás hatékonyságát: Családi házakra: Recall (Felidézés) R= 969 / (969 + 31) = 969 / 1000 =0,969 Precision (Pontosság) P= 969 / (969 + 11) = 969 /980 = 0,988 Panel lakásokra: Recall (Feidézés) Precision (Pontosság)
R= P=
989 / (989+11) = 989 / 1000 = 0,989 989 / (989+31) = 989 / 1020 = 0,970
12
9. A STOPSZÓ SZŰRÉS ÉS LEMMATIZÁLÁS HATÁSA AZ OSZTÁLYOZÁSRA Megvizsgáltam még azt, hogy milyen hatása van annak, ha a bemeneti fájlokra először elvégzem a stopszó szűrést és a lemmatizálást és utána végzem el az osztályozás folyamatát. Azt kaptam, hogy a stopszó szűrés és a lemmatizálás javította az osztályozás eredményét: A Vektortér mátrix mérete most így alakult: Sorok száma: 17.169; Oszlopok száma: 2000 A vizsgálat eredménye: jo1= 991; rossz1= 9, jo2= 990; rossz2= 10 A stopszó szűrés és lemmatizálás nélkül a következő eredmény volt: (lásd 8.5 fejezet ) jo1= 969; rossz1= 31; jo2= 989; rossz2= 11 Családi házakra: Recall (Felidézés) Precision (pontosság)
R= P=
991 / (969 + 9) = 991 / 1000 =0,991 991 / (991 + 10) = 991 /1001 = 0,990
Panel lakásokra: Recall (Felidézés) Precision (Pontosság)
R= P=
990 / (990+10) = 990 / 1000 = 0,99 990 / (990+9) = 990 / 999 = 0,991
Vagyis a stopszó szűrés és a lemmatizálás javította az osztályozás eredményét.
10. ÖSSZEFOGLALÁS – TOVÁBBLÉPÉSI LEHETŐSÉGEK Ebben a publikációban először megvizsgáltam a stopszó szűrés és a lemmatizálás hatását a Vektortér modellre. Azt tapasztaltam, hogy segítségükkel ki lehet szűrni a jelentéssel nem bíró szavakat (pl. névelőket) és felhasználásukkal jelentősen csökkenthető a Vektortér mátrix mérete. Majd készítettem egy programot szövegek osztályozására. Az osztályozó tesztelése azt mutatta, hogy a programot jól lehet használni szövegek bináris osztályozására. Majd megvizsgáltam a stopszó szűrés és a lemmatizálás hatását az osztályozásra. Láttuk, hogy felhasználásukkal javult az osztályozás eredménye. Egy következő publikációban tervezem más osztályozó algoritmusok, módszerek vizsgálatát. FELHASZNÁLT IRODALOM [1] Martin Daniel JURAFSKY, James H. MARTIN: Speech and Language Processing: An introduction to natural language processing, computational linguistics, and speech recognition. Stanford, CA: Pearson Prentice Hall, 2009. [2] TIKK Domonkos: Szövegbányászat. Typotex, Budapest, 2007. [3] SUBECZ Zoltán: Szövegfeldolgozási lépések a Vektortér modellig, Economica, A Szolnoki Főiskola Tudományos Közleményei, Szolnok, 2011.
13
