Title

Attribuuttien, tapahtumasarjojen ja tapahtumasarjoissa esiintyvien tapahtumatyyppien samankaltaisuusmittoja tietämyksen muodostamisessa

Mått på likheter mellan kännetecken, händelseserier och händelsetyper inom kunskapsutvinning

Attribute, Event Sequence, and Event Type Similarity Notions for data Mining

Defender

• Pirjo Moen
• University of Helsinki, Department of Computer Science

Opponent

• Professor Jyrki Nummenmaa
• University of Tampere

Custos

• Professor Inkeri Verkamo
• University of Helsinki, Department of Computer Science

Time and Place

• Friday, February 25, 2000
• at 12
• Auditorium XII, University Main Building, Old Side, 2nd floor

Abstract/Fin

Tietokoneteknologian nopea kehitys viime vuosikymmeninä on johtanut siihen, että suurten tietomäärien kerääminen on entistä helpompaa. Tietämyksen muodostaminen (data mining) on tietojenkäsittelytieteen osa-alue, jonka tavoitteena on kehittää erilaisia menetelmiä näiden suurten tietomassojen analysointiin, erityisesti erilaisten datassa esiintyvien säännönmukaisuuksien etsimiseen. Tällaisten erilaisten säännönmukaisuuksien löytäminen edellyttää, että pystymme määrittelemään, kuinka samankaltaisia eri tietoalkiot ovat. Siksi tietoalkioiden samankaltaisuus on yksi tietämyksen muodostamisen keskeisimpiä käsitteitä.

Tietämyksen muodostamisen kannalta hyvin tärkeitä datajoukkoja ovat tietokantarelaatiot, jotka koostuvat tietoalkioista, joilla on useita attribuutteja. Eräs tapa analysoida tällaista dataa on tarkastella tietokannan attribuuttien välisiä samankaltaisuuksia. Esimerkiksi ostosdatasta voitaisiin tutkia eri tuotteiden samankaltaisuutta vertailemalla niitä ostavien asiakkaiden ostoskäyttäymistä.

Perinteisesti kahden attribuutin samankaltaisuutta on tarkasteltu käyttäen mittoja, jotka ottavat huomioon vain näiden kyseisten attribuuttien arvot. Tällaiset mitat ovat usein hyödyllisiä, mutta valitettavasti ne eivät pysty kuvaamaan kaikkia tärkeitä samankaltaisuustyyppejä. Siksi väitöskirjassa esitellään uusi samankaltaisuusmitta, joka ottaa huomioon myös muiden tietokannassa esiintyvien attribuuttien arvot. Lisäksi työssä vertaillaan erilaisten attribuuttien samankaltaisuutta kuvaavien mittojen käyttäytymistä uutisartikkelikokoelman sekä kurssi-ilmoittautumisdatan avulla.

Toinen tietämyksen muodostamisen kannalta tärkeä datatyyppi ovat tapahtumasarjat. Tällaisia tapahtumasarjoja esiintyy useilla sovellusalueilla, esimerkiksi teleliikenteessä ja WWW-sivujen hakupyyntöjen tarkkailussa. Analysoimalla tapahtumasarjoja voimme saada hyödyllistä tietämystä järjestelmän tai käyttäjien toiminnasta. Tätä tietämystä voidaan hyödyntää esimerkiksi puhelinverkossa esiintyvien hälytysten paikallistamisessa. Väitöskirjassa tarkastellaankin tapoja määritellä sekä tapahtumasarjojen että niissä esiintyvien tapahtumatyyppien välinen samankaltaisuus.

Väitöskirjassa esiteltävä tapahtumasarjojen välisen samankaltaisuuden määritelmä perustuu ideaan siitä, että samankaltaisuuden pitäisi jollain tavalla heijastella sitä työn määrää, joka tarvitaan tapahtumasarjan muuttamiseksi toiseksi. Tämä idea määritellään täsmällisesti sarjojen editointietäisyytenä. Esitellyn samankaltaisuusmitan ominaisuuksia kuvataan työssä käyttäen esimerkkeinä sekä puhelinverkon hälytysten että WWW-sivujen hakupyyntöjen muodostamia tapahtumasarjoja.

Kolmantena samankaltaisuusmittojen joukkona työssä tarkastellaan sitä, kuinka tapahtumasarjoissa esiintyvien erilaisten tapahtumatyyppien samankaltaisuutta voitaisiin mitata. Intuitiivisesti kaksi tapahtumatyyppiä ovat samankaltaisia, jos ne esiintyvät samankaltaisissa konteksteissa. Väitöskirjassa tarkastellaan erilaisia tapoja määritellä tapahtuman konteksti sekä sitä, kuinka kahden tapahtumatyypin samankaltaisuus voidaan määritellä niiden kontekstien avulla. Erilaisten samankaltaisuusmittojen ominaisuuksiin tutustutaan tarkastelemalla puhelinverkon hälytysten ja kurssi-ilmoittautumisten muodostamia tapahtumasarjoja sekä joukkoa hemoglobiinisekvenssejä.

Abstract/Swe

Den snabba utvecklingen under de senaste decennierna inom datetekniken har gjort det möjligt att enkelt samla stora kvantiteter data. Kunskapsutvinning (data mining) är ett forskningsområde inom datavetenskapen vars målsättning är att utveckla metoder för analys av stora datamängder, i synnerhet att upptäcka mönster och regelbundheter. För att finna dessa krävs det att man kan beskriva hur lika två objekt är. Därför är likheter mellan objekt ett av de mest centrala begreppen inom kunskapsutvinning.

Ett typiskt forsknings material inom kunskapsutvinning är en databas bestående av ett antal objekt med ett flertal olika kännetecken. Ett sätt att analysera databasen är att studera likheterna mellan de förekommande kännetecknen. Man kan till exempel studera likheterna mellan olika produkter i olika snabbköpkunders inköpskorgar.

Traditionella metoder för att finna likheter mellan två kännetecken tittar oftast endast på de ingående kännetecknen. Dessa metoder kan användas i vissa fall, men de finner inte alla betydelsefulla likheter. Därför förs här fram ett nytt mått på likheter mellan kännetecken, som även tar hänsyn till de kännetecken som ligger utanför den egentliga analysen. En samling nyhetstelegram och kursanmälningar har använts för att visa på skillnaderna mellan de olika måtten.

Dataserier är en annan betydande typ av data som studeras inom kunskapsutvinning. Dessa förekommer inom vitt skilda områden, till exempel telenätverk och internetsökningar. Genom att analysera sådana serier kan man få värdefull information om hur ett system fungerar eller hur en användare beter sig. Detta kan sedan utnyttjas för att till exempel förebygga allvarliga fel inom ett telenätverk. I denna avhandling behandlas både likheter mellan serier och likheter mellan händelsetyper i serier.

Grundidén i denna avhandling är att ett mått på likheten mellan två händelseserier skall spegla det arbete som krävs för att omforma en serie till en annan. Detta arbete definieras i avhandlingen som de två händelseseriernas formella avstånd. Resultat från experiment utförda på felmeddelanden från telenätverk och internetsökningar redovisas i avhandlingen.

Den tredje gruppen likhetsmått bestämmer likheter mellan händelsetyper inom en serie. Två händelsetyper är lika om de förkommer i liknande kontexter. Avhandlingen lyfter fram flera möjligheter att finna en händelses kontext i en serie och sätt att bestämma likheten mellan två händelsetyper genom att titta på deras kontexter. Felmeddelanden från telenätverk, proteinserier i hemoglobin och kursanmälningar har använts för att belysa dessa mått.

Abstract/Eng

The rapid development of computer technology in the last decades has made it possible to easily collect huge amounts of data. Data mining is a research area in computer science that aims at developing methods for analyzing these databases, and especially finding different patterns and regularities in the data. Finding such patterns and regularities requires that we can describe how similar to each other two data objects are. Therefore, one of the central concepts in data mining is similarity between objects.

A typical data set considered in data mining is a relation that consists of a number of data objects with several attributes. One way of analyzing this kind of data is to study similarities between the attributes of the relation. We could, for example, define similarities between products sold in a supermarket by looking at how the customers buy these products.

Traditional approaches for defining similarity between two attributes typically consider only the values of those two attributes. Such similarity measures are often useful, but unfortunately they cannot describe all important types of similarity. Therefore, we introduce a new attribute similarity measure that also takes into account the values of other attributes in the relation. The behavior of the different measures is demonstrated on a collection of newswire articles and a set of course enrollment data.

Another important form of data considered in data mining is sequential data. This kind of data occurs in many application domains, such as telecommunication and World Wide Web page request monitoring. Analyzing such sequences of events gives us important knowledge about the behavior of a system or a user. This knowledge can, for example, be used in predicting severe faults in a telecommunication network. In this thesis we consider both similarities between event sequences and similarities between event types occurring in sequences.

Our approach to event sequence similarity is based on the idea that similarity between event sequences should reflect the amount of work that is needed to transform one event sequence into another. This work we define as an edit distance between sequences. We also give some experimental results on a telecommunication alarm sequence and a log of World Wide Web page requests.

As the third case of similarity notions, we study how similarity between types of events occurring in sequences could be defined. Intuitively, two event types are similar if they occur in similar contexts. We show different possibilities for how a context of an event can be extracted from a sequence, and ways of defining similarity between two event types by using their contexts. Results of experiments on the event type similarity with different measures are described on a telecommunication alarm sequence, a set of hemoglobin sequences, and a set of course enrollment data.