Hierarkkinen klusterointi tiedonhaussa.

KORENIUS, TUOMO (2003)
 

Tässä tietueessa ei ole kokotekstiä saatavilla Treposta, ainoastaan metadata.



KORENIUS, TUOMO
2003

Tilastotiede - Statistics
Informaatiotieteiden tiedekunta - Faculty of Information Sciences
Hyväksymispäivämäärä
2003-07-31
Näytä kaikki kuvailutiedot

Sisällysluettelo

1 JOHDANTO 1 2 TUTKIMUKSEN AINEISTO 3 2.1 TUTKIMUSAINEISTON KUVAUS 3 2.2 SUOMENKIELISEN AINEISTON ERITYISPIIRTEET 4 2.3 TUTKIMUSAINEISTON ESIKÄSITTELY 5 3 AUTOMAATTINEN INDEKSOINTI 8 3.1 AUTOMAATTISEN INDEKSOINNIN TAUSTAA 8 3.1.1 Tekstidokumenttien kuvaaminen numeerisesti 8 3.1.2 Sanojen yleisyys ja erottelukyky 9 3.2 DOKUMENTTIKOKOELMAN VEKTORIAVARUUSMALLI 11 3.3 AVAINTEN PAINOKERTOIMIEN MÄÄRITTÄMINEN 13 3.3.1 tf.idf-painotus 13 3.3.2 Dokumenttivektorien normeeraus 14 4 AINEISTON MONIULOTTEISUUDEN PIENENTÄMINEN PÄÄKOMPONENTTIANALYYSILLÄ 17 4.1 PÄÄKOMPONENTTIANALYYSIN TAUSTAA 17 4.1.1 Dimensionaalisuuden kirouksesta 17 4.1.2 Pääkomponenttianalyysin teoriaa 18 4.2 PÄÄKOMPONENTTIEN MÄÄRITTÄMINEN 21 4.2.1 Lineaarikombinaation maksimivarianssi 21 4.2.2 Matriisihajotelmien hyödyntäminen pääkomponenttianalyysissä 24 4.3 TARVITTAVIEN PÄÄKOMPONENTTIEN LUKUMÄÄRÄN ARVIOINTI 26 5 DOKUMENTTIEN SAMANLAISUUDEN ARVIOINTI 30 5.1 YLEISTÄ SAMANLAISUUDEN MITTAAMISESTA 30 5.2 METRIIKAN MÄÄRITELMÄ 31 5.3 ETÄISYYSMITAN VALINTA 32 5.3.1 Kosinimitta 32 5.3.2 Euklidinen etäisyys 34 5.3.3 Pääkomponenttien väliset etäisyydet 37 5.3.4 Kosinietäisyys pääkomponenttiaineistossa 38 6 DOKUMENTTIEN RYHMITTELYSSÄ KÄYTETTÄVÄT KLUSTEROINTIMENETELMÄT 42 6.1 YLEISTÄ KLUSTEROINTIMENETELMISTÄ 42 6.2 KLUSTEROINTIMENETELMIEN JAOTTELU 43 6.2.1 Optimointiperustaiset klusterointimenetelmät 43 6.2.2 Hierarkkiset klusterointimenetelmät 44 6.3 HIERARKKISIA KLUSTEROINTIMENETELMIÄ 49 6.3.1 Yhden ja täydellisen yhteyden menetelmät 49 6.3.2 Keskiarvomenetelmä 53 6.3.3 Wardin menetelmä 54 6.4 KLUSTEROINTIMENETELMIEN OMINAISUUKSIA 56 6.4.1 Kombinatoriset menetelmät 56 6.4.2 Klusterointimenetelmän monotonisuus 58 6.4.3 Etäisyysfunktioiden monotoniset muunnokset 61 7 KLUSTEROINNIN TULOSTEN HYÖDYNTÄMINEN JA ARVIOINTI 66 7.1 KLUSTEROINNIN HYÖDYNTÄMINEN TIEDONHAUSSA 66 7.2 KLUSTEREIDEN LUKUMÄÄRÄN MÄÄRITTÄMINEN 68 7.2.1 Yleistä klustereiden lukumäärän arvioinnista 68 7.2.2 Siluetti-indeksi ja siluettikerroin 68 7.2.2 Mojenan sääntö ja ristiriitaisuuskerroin 71 7.3 KLUSTEROINNIN TULOSTEN ARVIOINTI JA VERTAILU 74 7.3.1 Yleistä klusteroinnin hyvyyden arvioinnista 74 7.3.2 Tulosten arviointi tiedonhaun näkökulmasta 76 8 TUTKIMUSAINEISTON ANALYYSI 80 8.1 YLEISTÄ TUTKIMUSAINEISTON ANALYSOINNISTA 80 8.2 TUTKIMUSAINEISTON INDEKSOINTI 81 8.3 TUTKIMUSAINEISTON PÄÄKOMPONENTTIANALYYSI 83 8.4 TUTKIMUSAINEISTON KLUSTEROINTI 85 8.5 TULOSTEN ARVIOINTI JA VERTAILU 89 8.5.1 Yleistä tutkimuksen tulosten arvioinnista 89 8.5.2 Saanti- ja tarkkuusarvojen tarkastelua 90 8.5.3 Klusterointimenetelmien vertailu 95 8.5.4 Menetelmien välisten erojen tilastollinen testaus 98 9 PÄÄTELMÄT 104 LÄHTEET 106 KUVALUETTELO 109 TAULUKKOLUETTELO 111 LIITTEET 112 LIITE 1. TUTKIMUSAINEISTON ARTIKKELEIDEN RELEVANSSIARVIOIDEN PERUSTANA OLEVAT TESTITEHTÄVÄT 112 LIITE 2. TESTITEHTÄVIIN LIITTYVIEN, RELEVANTTIEN DOKUMENTTIEN LUKUMÄÄRÄT TESTITEHTÄVITTÄIN JA RELEVANSSILUOKITTAIN 114 LIITE 3. TUTKIMUKSESSA KÄYTETTYJEN APUOHJELMIEN KUVAUS 115
Tiivistelmä
Sähköisessä muodossa olevan tiedon määrä on kasvanut viime vuosina räjähdysmäisesti. Etenkin Internetin käytön yleistyminen on lisännyt erilaisten tiedonhakusovellusten ­ niin sanottujen hakukoneiden tarvetta. Tekstidokumenttien klusterointia voidaan hyödyntää tiedonhakusovellusten toiminnassa. Dokumenttien klusterointia ja siihen perustuvaa tiedonhakua on tutkittu aiemmin lähinnä englanninkielisellä aineistolla. Tässä tutkimuksessa selvitetään ja vertaillaan yleisimmin käytettyjen hierarkkisten klusterointimenetelmien soveltuvuutta suomenkielisten tekstidokumenttien ryhmittelyyn tiedonhaun näkökulmasta.

Dokumenttien klusterointi perustuu ryhmiteltävien dokumenttien samankaltaisuuden mittaamiseen niissä esiintyvien sanojen perusteella. Erilaisten samanlaisuus- ja etäisyysmittojen lisäksi tässä tutkimuksessa tarkastellaan tekstidokumenttien numeerista kuvailua sekä dokumenttikokoelman vektoriavaruusmallin käyttöä.

Tiedonhaussa käsiteltävät tietomäärät ovat tyypillisesti suuria. Tässä tutkimuksessa tarkasteltava aineisto käsitti 5 000 uutisartikkelia. Runsaasti laskentaa vaativien klusterointimenetelmien käytön helpottamiseksi dokumenttikokoelmasta tunnistettujen erilaisten sanojen ­ tässä tutkimuksessa tarkasteltavien muuttujien ­ lukumäärää pienennettiin pääkomponenttianalyysillä. Tarkasteltavien muuttujien lukumäärä putosi noin kymmenesosaan alkuperäisten muuttujien määrästä, kun klusterointi tehtiin pääkomponenttianalyysissä muodostetun pääkomponenttiaineiston avulla.

Tutkimuksen tulokset vastaavat aiemmin englanninkielisellä aineistolla tehdyissä tutkimuksissa saatuja tuloksia. Näin ollen myös suomenkielisen dokumenttiaineiston klusterointi on mahdollista, kunhan suomenkielen ominaispiirteet otetaan huomioon. Eri klusterointimenetelmien tuottamien tulosten välillä ei ollut havaittavissa kovin suuria eroja. Yhden yhteyden klusterointimenetelmä tuotti kuitenkin selvästi muita tutkittuja menetelmiä huonoimpia tuloksia, joskaan mikään tutkituista klusterointimenetelmistä ei yltänyt erityisen hyviin tuloksiin. Kaikki tarkastellut menetelmät tuottivat kuitenkin yleensä yhden melko hyvän dokumenttiryhmän, joka sisälsi suurimman osan samaa aihetta käsittelevistä dokumenteista, mutta melko vähän muita aiheita käsitteleviä dokumentteja.

Avainsanat: Etäisyysmitta, pääkomponenttianalyysi, ryhmittelyanalyysi, vektoriavaruusmalli
Kokoelmat