Luokittimien yhdistämisestä maanpinnan luokittelussa

Ismo Lahtinen
ielahtin@cc.hut.fi

Tämä dokumentti on kurssin Maa-57.270 Fotogrammetrian, kuvatulkinnan ja kaukokartoituksen seminaari kirjallinen osuus keväällä 2003.

Johdanto

Parametrisilla menetelmillä toimivat tilastolliset luokittimet olivat pitkään valttia kaukokartoituskuvilta tehtävässä luokittelussa. Vähitellen ainakin rinnalle nousivat ei-parametriset neuroverkot. Erilaisten menetelmien pätevyys on osoitettu lukuisissa tutkimuksissa ja käytännön luokittelutehtävissä, mutta täydellisyyteen on saavuttamattoman pitkä matka. [Kanellopoulos ja muut 1993]

Neuroverkoilla ja parametrisilla luokittimilla on selkeästi toisistaan poikkeava matemaattinen perusta. Kun tarkastellaan kaikkia toimivaksi todettuja menetelmiä, saadaan aikaan kirjava joukko varsin erilaisilta alustoilta ponnistavia luokittimia. Tästä syntyy perusta kehitellä menetelmiä, jotka yhdistävät erilaiset luokittimet hyödyntäen niiden parhaita puolia. [Kanellopoulos ja muut 1993],[Ho ja muut 1994]

Tässä seminaarityössä paneudutaan puoleentoista opintoviikkoon nähden järkevässä mittakaavassa eri luokittimien yhdistämiseen maanpinnan luokittelussa. Maanpinnan luokittelun valitsemiseen esimerkiksi on selkeitä syitä. Aihe on riittävän käytännönläheinen ja tekijää kiinnostava. Toisaalta luokittimien yhdistämistä käytännössä esittelevät artikkelit tuntuvat käsittelevän suurimmaksi osaksi juuri maanpinnan luokittelua.

Luokittimien suomenkielisiin nimiin ja erilaisiin toteutustapoihin liittyvät ristiriidat pyrin ratkaisemaan esittelemällä läpikäymissäni tutkimuksissa käytetyt luokittimet siinä muodossaan kuin niitä on käytetty kappaleessa "Käytettyjä luokittimia". Kappaleen tarkoitus ei siis ole luoda kokonaiskuvaa kaikista maanpinnan luokitteluun käytettävistä luokittimista.

Luokittimien yhdistämisen perusteita

Keskinäisissä vertailussa neuroverkkojen on todettu yleensä toimivan luokittimista parhaiten, mikäli ratkaisevana tekijänä pidetään luokittelun kokonaistarkkuutta. Niihin ei kuitenkaan pidä luottaa sokeasti. Hyvä kokonaistarkkuus saattaa peitellä täydellisiä epäonnistumisia jopa kokonaisten luokkien luokittelussa. Kun katsotaan luokittelun sisällä jonkin yksittäisen luokan luokittelutarkkuuksia, neuroverkko häviää usein muunlaisille luokittimille. Luokiteltavan aineiston ominaisuudet, kuten suuret luokkakoot ja kohina, kärjistävät vielä luokittimien välisiä eroja. Näiden syiden takia on järkevää tarkastella, miten luokittimia voisi yhdistää siten että käytetyistä luokittimista saadaan esille parhaat puolet. [Kanellopoulos ja muut 1993],[Ho ja muut 1994]

Ajatus luokittimien yhdistämisen taustalla on yksinkertainen. Tarkoituksena on löytää algoritmi, joka korostaa yksittäisten luokittimien parhaita puolia, häivyttää niiden huonot puolet ja parantaa näin luokittelun tarkkuutta. Tässä työssä esiteltävät yhdistämismenetelmät perustuvat enemmän tai vähemmän eri luokittimilla saatujen lopputulosten yhdistämiseen. Käytännössä yhdistämisalgoritmi siis päättää, mikä saaduista tuloksista on paras. [Ho ja muut 1994]

Hon ja muiden artikkelissa [Ho ja muut 1994] lähestytään aihetta toisesta näkökulmasta. Yksittäisistä luokittimista ei huomioida pelkästään lopputulosta, vaan niiden antamat todennäköisyydet luokiteltavalle vektorille kuhunkin luokkaan. Luokat asetetaan tämän perusteella järjestykseen ja niille annetaan sijoitusluvut (todennäköisin luokka on 1, toiseksi todennäköisin 2 jne.). Lopullinen luokitus tehdään sijoituslukuja yhdistämällä. Yhdistämiseen esitetään useita vaihtoehtoisia tapoja. [Ho ja muut 1994]

Artikkelissa [Ho ja muut 1994] esitetään perusteluja sijoituslukujen käyttöön. Selkeä syy on, että sijoitukset ottavat luokittelusta irti enemmän informaatiota kuin pelkän ykkösluokan käyttäminen. Lisäksi erilaisten luokittimien tulokset (esimerkiksi a posteriori todennäköisyydet) tai luokittelun onnistumista kuvaavat mitat eivät välttämättä ole vertailtavissa suoraan. Sijoituslukuja käyttämällä erilaisten luokittimien tulokset saadaan samanarvoiseen asemaan. [Ho ja muut 1994]

Käytettyjä luokittimia

Suurimman uskottavuuden luokitin (Maximum Likelihood Classifier, MLC)

Suurimman uskottavuuden luokitin on yleisesti maanpinnan luokittelussa käytetty parametrisella menetelmällä toimiva tilastollinen luokitin, joka pohjautuu suoraan bayesläiseen luokitteluun. MLC:n mukaan jokainen luokiteltava pikseli liitetään luokkaan, jonka keskiarvovektoriin on lyhin Mahalanobis-etäisyys. Mahalanobis-etäisyyksien ajatellaan kuvaavan todennäköisyyksiä, joilla pikseli kuuluu kuhunkin luokkaan. [Kanellopoulos ja muut 1993],[Liu ja muut 2002]

Luokkien keskiarvovektorit ja kovarianssimatriisi määritetään ennakkotiedon perusteella. Mahalanobis-etäisyys lasketaan seuraavasti:

[Theodiridis ja Koutrombas 1999]

MLC perustuu oletukseen, jonka mukaan jokaisen luokan piirrevektorit ovat normaalijakautuneita. Kun oletus pitää paikkaansa, MLC täyttää tehtävänsä mallikkaasti. Näin ei kuitenkaan aina ole. [Kanellopoulos ja muut 1993],[Liu ja muut 2002]

Expert system –luokittimet (Expert System Classifier, ESC)

Expert system –luokittimien ryhmä sisältää hyvinkin selkeästi toisistaan poikkeavia luokittimia. Ryhmän luokittimille on kuitenkin yhteistä kaksi osaa: ennakkotiedon ja tulkinnassa käytettävät säännöt sisältävä tietokanta sekä varsinaisen luokittelun suorittava päätöskone (engl. inference engine). [Liu ja muut 2002]

Ennakkotiedon luonne vaihtelee sovelluksen mukaan. Maanpinnan luokittelussa ennakkotieto on tyypillisesti paikkatietojärjestelmästä tai muusta lähteestä saatavaa tietoa siitä, mitä luokkia tutkimusalue sisältää ja mitkä ovat niiden esiintymistodennäköisyydet. [Liu ja muut 2002]

Päätöskone voi perustua joko Dempster-Shaferin teoriaan tai yleisemmin käytettyyn Bayesin sääntöön. Dempster-Shaferin päättely eroaa bayesläisestä päättelystä siten että todennäköisyyksiä voidaan antaa myös alkeistapahtumien joukoille yksittäisten alkeistapausten lisäksi. Luokittimiin liittyen teorian edut tulevat esiin, kun tiedot piirrevektorien jakaumasta ovat puutteelliset. [Liu ja muut 2002]

Bayesin sääntöä hyödyntävässä menetelmässä (Bayesian expert system) käytettävien kuvien pikseleistä saatavat piirrevektorit yhdistetään ennakkotietoon luokkien esiintymistodennäköisyyksistä. Pikselien luokat ratkaistaan Bayesin kaavan perusteella.
Bayes
[Liu ja muut 2002],[Heikkilä ja Törmä 2003]

Menetelmän käytännön sovelluksissa a priori todennäköisyydet määritetään ennakkotiedon perusteella. Bayesin sääntöön perustuvaa luokitinta voidaan hyvällä syyllä pitää käyttäjäystävällisimpänä. Toisaalta menetelmä edellyttää tutkittavan alueen tuntemista riittävän tarkasti, jotta a priori todennäköisyydet voidaan estimoida järkevästi. [Liu ja muut 2002]

Neuroverkot (Neural Network Classifier, NNC)

Hahmontunnistuksessa käytettävien neuroverkkojen perusajatus poikkeaa oleellisesti tilastollisista luokittimista. Neuroverkkojen lähtökohtana on ihmisten ja eläinten mainion hahmontunnistuskyvyn mallintaminen. [Vuori 2001]

Neuroverkko koostuu solmuista ja niiden välisistä synaptisista kytkennöistä. Kytkentöjen vahvuutta pystytään säätelemään painojen avulla. Kytkentöjä säätelemällä monimutkainen ongelma jaetaan pieniksi osaongelmiksi. Laskenta-aikaa voidaan pienentää oleellisesti ratkaisemalla osaongelmat rinnakkaisesti. Neuroverkko on dynaaminen systeemi, jossa solmujen kytkennät ja verkon ulostulo muuttuvat ajan, syötteiden ja alkutilan mukaan. Perseptroni on solmu, joka jakaa piirreavaruuden kahteen osaan. [Vuori 2001],[Törmä]

Yleisimmin käytettyjä neuroverkkoja ovat monikerrosperseptronit (multi layer perceptron, MLP). MLP:n ensimmäistä kerrosta kutsutaan sisääntulokerrokseksi. Siinä jokaiselle piirteelle on oma perseptroni. Sisääntulokerroksessa ei suoriteta lainkaan laskentaa. Viimeinen kerros on ulostulokerros, joka määrää samalla koko verkon vasteen (esim. luokittelussa luokat). Väliin jääviä kerroksia kutsutaan piilokerroksiksi. [Vuori 2001],[Törmä]

Varsinaista luokittelua edeltää opetusvaihe. Koska halutut luokat ovat tiedossa etukäteen, maanpinnan luokittelussa käytetään ohjattua oppimista. Ohjatussa oppimisessa määritetään verkon rakenne (kerrosten ja solmujen lukumäärä sekä kytkennät) ja synaptiset painot. Systeemiä opetetaan opetusnäytteillä niin pitkään kunnes saavutetaan halutun pieni virhe luokittelutuloksen ja näytteiden oikeiden luokkien välillä. Verkon rakenne pyritään pitämään hallitun yksinkertaisena. [Liu ja muut 2002],[Vuori 2001]

Suosituin ohjatun oppimisen menetelmä on backpropagation-algoritmi. Siinä verkon rakenne on kiinnitetty etukäteen. Verkon halutun ja todellisen vasteen eroa kuvataan kustannusfunktiolla, jonka arvoa minimoidaan painoja muuttamalla. [Liu ja muut 2002],[Vuori 2001]

Luokittelussa neuroverkkojen suosioon on monia syitä:
- neuroverkko toimii ei-parametrisesti
- päätösrajan muoto ei rajoita ratkaisua epälineaarisissa ongelmissa
- neuroverkko on helppo sovittaa eri tyyppisiin aineistoihin ja syötteisiin
- neuroverkko pystyy erittelemään opetusjoukosta lähellä toisiaan olevat luokat
- neuroverkko toimii hyvin kohinaisissa aineistoissa [Kanellopoulos ja muut 1993],[Liu ja muut 2002]

Neuroverkkojen hyvät luokittelutarkkuudet vertailuissa tilastollisiin luokittimiin perustunevat juuri riippumattomuuteen päätösrajan muodosta. Lukuisat piirreavaruuteen sijoitetut hypertasot pystyvät erottamaan luokat toisistaan paremmin kuin muutamat tarkasti mallinnetut tilastolliset jakaumat. [Kanellopoulos ja muut 1993],[Liu ja muut 2002]

Neuroverkkojen käytössä ongelmana ovat käyttäjän määrittelemät verkon parametrit, kuten piilokerroksen solmujen lukumäärä ja virheraja opetusvaiheessa, sekä vasteen stokastisuus. Lisäksi hyvän yleistyskyvyn saavuttamiseksi tarvitaan erittäin paljon opetusaineistoa.[Liu ja muut 2002]

Yhdistämisalgoritmeja

Liu ja muut esittelevät tutkimuksessaan [Liu ja muut 2002] kaksi menetelmää eri luokittimien yhdistämiseen tulosten parantamiseksi. Ensimmäinen menetelmä on nimetty suurieleisesti consensus builderiksi (consensus, suom. konsensus, yksimielisyys). Toinen tutkimuksessa esitelty menetelmä yhdistää expert system -luokittimen neuroverkkoon. [Liu ja muut 2002]

Consensus builder (CSB)

Tutkimuksessa käytettiin kolmea eri luokitinta: suurimman uskottavuuden luokitinta, backpropagation-algoritmillä opetettua neuroverkkoa ja Bayesin sääntöön perustuvaa expert system -luokitinta. Consensus builderin tehtävänä on yhdistää näillä saadut luokittelutulokset. Tulosten yhdistämisessä käytetään hyväksi saatuja tuottajantarkkuuksia. Tuottajantarkkuudella tarkoitetaan todennäköisyyttä, jolla luokkaan n luokiteltu vektori kuuluu oikeasti luokkaan n. [Liu ja muut 2002]

Consensus builder toimii varsin yksinkertaisella periaatteella. Luokittelutulosta tulkitaan pikseleittäin. Jos luokittimista vähintään kaksi on saanut pikselille saman luokan, pikseli luokitellaan tähän luokkaan. Jos kaikilla luokittimilla on saatu eri tulos, siirrytään tutkimaan tuottajantarkkuuksia. Pikseli luokitellaan siihen luokkaan, jonka tuottajantarkkuus on suurin. [Liu ja muut 2002]

Yhdistetty expert system -luokitin ja neuroverkko (ESNNC)

Menetelmän ensimmäisessä osassa tehdään luokittelu ensin expert system -luokittimella. Saadusta vasteesta muodostetaan sisääntulokerros neuroverkkoon, jolla luokitellaan vektorit tavalliseen tapaan. Ajatuksena on neuroverkon parantaminen ESC:n sisältämän ennakkotiedon avulla. [Liu ja muut 2002]

Toisessa osassa luokittelutulokselle tehdään jälkiprosessointi. Jälkiprosessoinnin tarkoituksena on saada mukaan alkuperäistä informaatiota, jota on mahdollisesti hukattu kahdessa luokittelussa. Jälkiprosessoinnissa hyödynnetään expert system –luokittimen ja ensimmäisessä osassa käytetyn neuroverkon tuottajantarkkuuksia sekä ennakkotietoa. Mikäli expert system –luokitin ja neuroverkko luokittelivat pikselin eri luokkiin, pikseli luokitellaan suuremman tuottajantarkkuuden perusteella. Ennakkotiedon perusteella määritettyjä sääntöjä käytetään edelleen loogiseen päättelyyn. Esimerkiksi laidunta ei voi olla alueella, jolla on jyrkkiä korkeuseroja. [Liu ja muut 2002]
ESNNC
Selventävä kaaviokuva algoritmin toiminnasta. [Liu ja muut 2002]

Yhdistetty suurimman uskottavuuden luokitin ja neuroverkko (MLNNC)

Kanellopouloksen ja muiden artikkeli [Kanellopoulos ja muut 1993] esittelee menetelmän neuroverkon ja parametrisen luokittimen yhdistämiseen. Parametrisena luokittimena käytetään suurimman uskottavuuden luokitinta. [Kanellopoulos ja muut 1993]

Opetusvaiheessa pikselit luokitellaan ensin normaalisti sekä suurimman uskottavuuden luokittimella että neuroverkolla (NN1). Jos luokittimet ovat eri mieltä luokasta, otetaan käyttöön uusi neuroverkko. Toinen neuroverkko (NN2) opetetaan pikseleillä, joiden luokasta luokittimet ovat olleet eri mieltä. Ajatuksena on kouluttaa hankaliin tapauksiin erikoistunut neuroverkko. [Kanellopoulos ja muut 1993]

Varsinainen luokittelu suoritetaan samaan tapaan. Jokainen pikseli luokitellaan sekä suurimman uskottavuuden luokittimella että neuroverkolla NN1. Mikäli luokittimet päätyvät samaan tulokseen, pikseli luokitellaan tähän luokkaan. Riitatapauksissa käytetään neuroverkkoa NN2. [Kanellopoulos ja muut 1993]

Käytännön tuloksia

CSB ja ESNNC

Molempia Liun ja muiden tutkimuksen menetelmiä kokeiltiin käytännössä Overijsselin provinssin alueella Hollannin itäosassa. Luokittelussa käytettiin yhtätoista etukäteen määritettyä luokkaa. [Liu ja muut 2002]

Kuva-aineistona käytettiin Landsat TM -kuvaa ja SPOT-satelliitin pankromaattista kuvaa. Aineistoa täydennettiin paikallisesta paikkatietojärjestelmästä saaduilla maanpinnan muotoja ja maaperää kuvaavilla kartoilla. Lopulta aineistosta päädyttiin käyttämään kuutta piirrettä: Landsat-kuvan kanavia 2 ja 4, SPOT-kuvaa sekä paikkatietojärjestelmästä saatuja korkeusmallia, rinteitä kuvaava karttaa ja maaperäkarttaa. Jokaisesta luokasta valittiin ilmakuvien ja maastotyön perusteella esimerkkinäytteet, jotka jaettiin opetus- ja testinäytteiksi. Expert system -luokitinta varten tarvittiin lisäksi ennakkotietoa maanpinnan luokkien esiintymistodennäköisyyksistä alueella. [Liu ja muut 2002]

Käytetty neuroverkko oli kolmekerroksinen ja opetettu backpropagation-algoritmillä. Neuroverkossa oli kuusi sisääntulokerroksen solmua (yksi jokaista piirrettä kohti), kahdeksan piilokerroksen solmua ja 11 ulostulokerroksen solmua (yksi jokaiselle luokalle). [Liu ja muut 2002]

vertailu
Testien tulokset.
T: Kokonaistarkkuus kertoo kuinka monta prosenttia pikseleistä luokittui oikein.
TT: Tuottajantarkkuus on todennäköisyys, jolla luokkaan n luokiteltu pikseli todella kuuluu luokkaan n.
KT: Käyttäjäntarkkuus puolestaan on todennäköisyys, jolla oikeasti luokkaan n kuuluva pikseli luokitellaan luokkaan n.
kappa: Kappa-arvo määrittää paljonko luokitus eroaa satunnaisesta tuloksesta. Esimerkiksi kappa-arvo 0,8 merkitsee tuloksen olevan 80 prosenttia parempi kuin täysin satunnainen luokittelu.
varianssi: Kappa-arvon varianssi ilmaisee eroja eri testikertojen välillä.
[Liu ja muut 2002]

ESNNC-menetelmällä saavutettiin siis melko selkeästi paras luokittelutulos. Sen sijaan consensus builder hävisi jopa pelkälle neuroverkolle. Luokkatasolla yhdistetyt luokittelumenetelmät tuottivat mielenkiintoisia tuloksia. Neuroverkko luokitteli alueen kulmaan ylimääräisen laajahkon vesialueen. Consensus builder kuitenkin korjasi erheen mallikkaasti. CSB:lle ongelmalliseksi osoittautuivat kaupunki- ja tiealueet, joiden käyttäjäntarkkuudet jäivät 26 ja 24 prosenttiin. ESNNC:llä saatu tulos puolestaan poikkesi kaikista muista 95 prosentin merkitsevyystasolla. ESNNC:n hyvä toimivuus perustuu suurelta osin jälkiprosessoinnissa tehtyyn loogiseen päättelyyn ennakkotiedon avulla. [Liu ja muut 2002]

MLNNC

Yhdistettyä suurimman uskottavuuden menetelmää ja neuroverkkoa testattiin käytännössä Lissabonin ympäristössä Portugalissa. Kuva-aineisto koostui kokonaisuudessaan Landsat TM –kuvista. Aineisto jaettiin opetus- ja testinäytteisiin. [Kanellopoulos ja muut 1993]

Saatu tulos ei puolusta menetelmän käytön mielekkyyttä. Pelkällä suurimman uskottavuuden luokittelijalla saatiin kokonaistarkkuudeksi 88,6 prosenttia, kun taas yksi neuroverkko (NN1) ylsi 91,6 prosenttiin. MLNNC:n tulos oli vain hitusen parempi, 91,9 prosenttia. [Kanellopoulos ja muut 1993]

Artikkeli [Kanellopoulos ja muut 1993] ei valitettavasti sisällä tarkempaa analyysiä tuloksista. Virhematriiseista voi päätellä NN1:n ja MLNNC:n tulosten poikkeavan toisistaan erittäin vähän. [Kanellopoulos ja muut 1993]

Yhteenveto

Luokittimien yhdistämisen tarkoituksena on parantaa luokittelutulosta eri luokittimien hyviä puolia hyödyntämällä. Tässä seminaarityössä käsitellyissä menetelmissä yhtenä osapuolena on aina neuroverkko. Käytännön kokeissa selvästi parhaiten selvisi neuroverkon ja expert system -luokittimen yhdistelmä. Muiden menetelmien tulokset eivät juuri erottuneet yksittäisillä luokittimilla saaduista tuloksista.

Luokittimien yhdistämisen käytännön hyödyt jäivät näissä tutkimuksissa varsin pieniksi. Teoreettinen perusta saavutettavalle hyödylle on kuitenkin niin vahva, että asian tarkempi tutkiminen saattaisi olla kannattavaa. Toimivan yhdistämisalgoritmin löytäminen on kuitenkin vaikeaa - yhdistämisalgoritmin valintaan kun liittyvät samat ongelmat kuin yksittäisen luokittelijankin tapauksessa.

Lähteet

Kanellopoulos I., Wilkinson G.G., Mégier J. 1993. Integration of neural network and statistical image classification for land cover mapping. Proceedings of the International Geoscience and Remote Sensing Symposium IGARSS’93, Kogakuin University, Tokyo, Japan, 18-21 August. s. 511-513. Saatavissa (6.3.2003): http://ieeexplore.ieee.org/iel2/1064/7705/00322597.pdf?isNumber=7705&prod=CNF&arnumber=322597&arSt=511&ared=513+vol.2&arAuthor=Kanellopoulos%2C+I.%3B+Wilkinson%2C+G.G.%3B+Megier%2C+J.

Liu Xue-Hua, Skidmore A.K., Van Oosten H. 2002. Integration of classification methods for improvement of land-cover map accuracy. ISPRS Journal of Photogrammetry & Remote Sensing, Volume 56, Issue 4. s. 257-268. Saatavissa (7.3.2003): http://www.sciencedirect.com/science?_ob=MImg&_imagekey=B6VF4-467JS0N-6-7&_cdi=6000&_orig=browse&_coverDate=07%2F31%2F2002&_sk=999439995&view=c&wchp=dGLbVlb-lSzBA&_acct=C000049220&_version=1&_userid=952938&md5=f90e75fdb545529a7e34f5910f21ac3b&ie=f.pdf

Ho K.T., Hull J.J., Srihari S.N. 1994. Decision combination in multiple classification system. IEEE Transactions on Pattern Analysis and Machine Intelligence, Volume 16, Issue 1. s. 66-75.

Heikkilä J., Törmä M. 2003. Hahmontunnistus – tilastollinen lähestymistapa (opetusmonistetta muistuttava teos on valmistunut nykyiseen muotoonsa 1995). Teknillinen korkeakoulu, Fotogrammetrian ja kaukokartoituksen laboratorio. 3:s uudistettu painos. Espoo. 286 sivua.

Vuori V. 2001. Hahmontunnistuksen perusteet (opetusmoniste). Teknillinen korkeakoulu, Informaatiotekniikan laboratorio. Espoo. 310 sivua.

Törmä M. Neuraaliverkot ja niiden käyttö kuvien analysoinnissa (www-sivu). Saatavissa (13.3.2003): http://foto.hut.fi/~markus/article/mk97.html

Theodoridis S., Koutroumbas K. Pattern Recognition. 1999. Academic Press. 625 sivua.