Graafiteoreettisten klusterointimenetelmien soveltaminen sisätilapaikannuksessa
Pinkkilä, Valtteri (2019)
2019
Matematiikan ja tilastotieteen tutkinto-ohjelma
Informaatioteknologian ja viestinnän tiedekunta - Faculty of Information Technology and Communication Sciences
This publication is copyrighted. You may download, display and print it for Your own personal use. Commercial use is prohibited.
Hyväksymispäivämäärä
2019-05-28
Julkaisun pysyvä osoite on
http://urn.fi/URN:NBN:fi:tuni-201907182675
http://urn.fi/URN:NBN:fi:tuni-201907182675
Tiivistelmä
Tässä tutkielmassa käsitellään sisätilapaikannusta ja sovelletaan klusterointialgoritmeja WLAN-signaalien voimakkuuksista muodostuvien sormenjälkien klusterointiin. Työssä esitellään paikannusmenetelmä, jossa sormenjälkien välisiä etäisyyksiä arvioimalla pyritään luomaan tarkasteltavasta alueesta radiokartta. Sormenjälkien välisten etäisyyksien arviointi hankaloituu, kun etäisyydet kasvavat riittävän suuriksi. Näin ollen menetelmä edellyttää sormenjälkien klusterointia pienempiin ryhmiin.
Tutkielmassa käydään läpi klusteroinnin perusperiaatteet ja pääpaino on graafiteoreettisissa klusterointimenetelmissä. Työssä käydään läpi Markov-, k-means- ja affinity propagation -klusterointialgoritmin toimintaperiaatteet. Tämän lisäksi tarkastellaan laajemmin spektrisiä klusterointialgoritmeja. Algoritmeja testataan Tampereen yliopiston Hervannan kampuksen Sähkötalo-rakennuksesta kerätyillä aineistoilla eri samanlaisuus- ja erilaisuusfunktioita käyttäen. Testauksia suoritetaan kaksiulotteisilla aineistoilla, jolloin sormenjälkiä klusteroidaan kerroksittain. Tämän lisäksi algoritmeja testataan aineistoilla, joissa sormenjälkiä on kolmessa
eri kerroksessa. Eri algoritmien palauttamia klusterointeja vertaillaan klustereiden yhtenäisyyden perusteella tutkielmassa esiteltävän arviointimenetelmän mukaisesti. Klusteroinnin lisäksi suoritetaan paikannusmenetelmää havainnollistava esimerkki.
Työssä saadut tulokset osoittavat, että yleisesti ottaen yhtenäisimmät RSS-sormenjäljistä muodostetut klusterit saadaan spektrisillä klusterointialgoritmeilla käytettäessä kosini-, Czekanowski- tai Wang-samanlaisuusfunktiota. Klusteroitaessa kaksiulotteista aineistoa saadaan tutkimuksissa kooltaan tasaisempia klustereita kuin kolmiulotteista aineistoa klusteroitaessa. Yhtenäisten klustereiden muodostaminen onnistuu paremmin tiheämmällä mittausaineistolla. Testaukset osoittavat myös, että sormenjälkien kerrosten väliseen erotteluun tarvitaan klusteroinnin lisäksi sensoreista saatavaa informaatiota.
Tutkielmassa käydään läpi klusteroinnin perusperiaatteet ja pääpaino on graafiteoreettisissa klusterointimenetelmissä. Työssä käydään läpi Markov-, k-means- ja affinity propagation -klusterointialgoritmin toimintaperiaatteet. Tämän lisäksi tarkastellaan laajemmin spektrisiä klusterointialgoritmeja. Algoritmeja testataan Tampereen yliopiston Hervannan kampuksen Sähkötalo-rakennuksesta kerätyillä aineistoilla eri samanlaisuus- ja erilaisuusfunktioita käyttäen. Testauksia suoritetaan kaksiulotteisilla aineistoilla, jolloin sormenjälkiä klusteroidaan kerroksittain. Tämän lisäksi algoritmeja testataan aineistoilla, joissa sormenjälkiä on kolmessa
eri kerroksessa. Eri algoritmien palauttamia klusterointeja vertaillaan klustereiden yhtenäisyyden perusteella tutkielmassa esiteltävän arviointimenetelmän mukaisesti. Klusteroinnin lisäksi suoritetaan paikannusmenetelmää havainnollistava esimerkki.
Työssä saadut tulokset osoittavat, että yleisesti ottaen yhtenäisimmät RSS-sormenjäljistä muodostetut klusterit saadaan spektrisillä klusterointialgoritmeilla käytettäessä kosini-, Czekanowski- tai Wang-samanlaisuusfunktiota. Klusteroitaessa kaksiulotteista aineistoa saadaan tutkimuksissa kooltaan tasaisempia klustereita kuin kolmiulotteista aineistoa klusteroitaessa. Yhtenäisten klustereiden muodostaminen onnistuu paremmin tiheämmällä mittausaineistolla. Testaukset osoittavat myös, että sormenjälkien kerrosten väliseen erotteluun tarvitaan klusteroinnin lisäksi sensoreista saatavaa informaatiota.