Mining Cell Transition Data

Cell transition data is obtained from a cellular phone that switches its current serving cell tower. The data consists of a sequence of transition events, which are pairs of cell identifiers and transition times. The focus of this thesis is applying data mining methods to such data, developing new algorithms, and extracting knowledge that will be a solid foundation on which to build location-aware applications. In addition to a thorough exploration of the features of the data, the tools and methods developed in this thesis provide solutions to three distinct research problems. First, we develop clustering algorithms that produce a reliable mapping between cell transitions and physical locations observed by users of mobile devices. The main clustering algorithm operates in online fashion, and we consider also a number of offline clustering methods for comparison. Second, we define the concept of significant locations, known as bases, and give an online algorithm for determining them. Finally, we consider the task of predicting the movement of the user, based on historical data. We develop a prediction algorithm that considers paths of movement in their entirety, instead of just the most recent movement history. All of the presented methods are evaluated with a significant body of real cell transition data, collected from about one hundred different individuals. The algorithms developed in this thesis are designed to be implemented on a mobile device, and require no extra hardware sensors or network infrastructure. By not relying on external services and keeping the user information as much as possible on the user s own personal device, we avoid privacy issues and let the users control the disclosure of their location information.

Matkapuhelinverkoissa tukiasemat palvelevat tietyllä alueella olevia puhelimia. Tukiaseman radiosignaalin kattamaa aluetta kutsutaan soluksi. Vaihtaessaan käyttämäänsä tukiasemaa puhelin tuottaa solusiirtymädataa, joka koostuu sarjasta solutunnisteita ja siirtymisaikoja. Vaikka data ei sisälläkään paikkojen koordinaatteja, siitä voidaan silti oppia tunnistamaan puhelimen käyttäjälle tärkeitä paikkoja sekä ennustamaan hänen liikkumistaan paikkojen välillä. Väitöskirjatyössä sovelletaan tiedonlouhinnan menetelmiä solusiirtymädataan ja tavoitteena on tuottaa työkaluja paikkatietoisten sovellusten kehittämiseen. Saatuja tuloksia testataan aineistolla, joka on kerätty noin sadalta matkapuhelimen käyttäjältä. Datassa on erityispiirteitä, jotka tekevät sen käsittelystä haastavaa. Yksi keskeinen ongelma on se, että solun vaihtuminen ei aina johdu käyttäjän liikkumisesta, vaan puhelin voi vaihtaa käyttämäänsä tukiasemaa myös muista syistä. Ja kääntäen: yksittäisen solun sisällä on mahdollista liikkua jonkin matkaa ennen solun vaihtumista. Solujen ja fyysisten paikkojen vastaavuuksien löytämiseksi työssä esitellään klusterointimenetelmä, joka yhdistää samaan paikkaan todennäköisesti liittyviä soluja suuremmiksi kokonaisuuksiksi. Kyseessä on ns. online-algoritmi, joka analysoi solusiirtymävirtaa ja päivittää klusterien joukkoa reaaliaikaisesti. Työn tuloksena syntyneet algoritmit voidaan toteuttaa käytännössä kaikilla mobiililaitealustoilla, eikä niiden käyttö vaadi toimenpiteitä puhelinoperaattorilta tai -valmistajalta. Koska menetelmät vaativat vain vähän puhelimen laskenta- ja tallennuskapasiteettia, käyttäjän paikkatietoja ei tarvitse lähettää puhelimesta eteenpäin jatkokäsittelyä varten. Tämä turvaa puhelimen käyttäjän yksityisyyttä, sillä käyttäjä voi päättää itse, kenelle ja kuinka paljon tietoja luovutetaan.