Attributtegenskaper

Vi kan utføre forskjellige operasjoner på forskjellige attributter. Dette avhenger av hvilke egenskaper attributtene har.

• Nominelle attributter: Kan utføre distinkthetsoperasjonen ("=", "!=")
• Ordinale attributter: Kan utføre distinkthets- og rekkefølgeoperasjoner ("<", ">")
• Intervallattributter: Kan utføre distinkthets-, rekkefølge- og adderingsoperasjoner ("+", "-")
• Ratioattributter: Kan utføre alle de foregående, og multiplisering og dividiering.

Attributter kan være enten symmetriske eller asymmetriske. En asymmetrisk attributt tar kun hensyn til om verdien er tilstedeværende. F.eks. er vi kun interessert i kunder som kjøper noe, så kunder med tom handlevogn oversees av systemet.

Antallet dimensjoner påvirker hvor lett det er å behandle dataene våre. Hvis vi får for mange dimensjoner kan det bli svært vanskelig å håndtere dataene. Vi får ytelses- og plassproblemer, som ofte refereres til som the curse of dimensionality.

Post

Vi kan organisere data som en samling av poster, hvor hver post har et fast sett attributter. Dataene kan representeres som en m*n-matrise, og kan representere et punkt i m-dimensjonalt rom.

Vi kan lage et dokument som en vektor av termer i en post. På denne måten blir verdien av hvert attributt antallet ganger det gitte ordet forekommer i teksten.

Transaksjonsdata kan også lagres som en post, da inneholder posten et sett av enheter som hører sammen.

Graf

Her organiseres data som noder med relasjoner. En lenke mellom to noder indikerer en form for forbindelse mellom dataene. Vi kan traversere grafen effektivt, og dermed finne informasjon om sammenhenger svært raskt.

Ordnede data

Her har vi data som er relatert til tid. Det er altså en rekkefølge i dataene som er relevant. Vi kan ordne en brukers transaksjoner i systemet over tid, eller logge temperaturer på forskjellige steder over tid.

Støy

Støy er unøyaktigheter eller feil i målingene. Dette kan forekomme ved overføring av analoge signaler, eller ved målfeil og andre feilkilder.

Outlier

En outlier er et datapunkt som har en signifikant forskjell fra resten av objektene i datasettet. Dette er forskjellig fra støy ved at det ikke er noe feil i målingen, men at det reelle datapunktet befinner seg langt unna resten av målingene.

Manglende verdier

Vi kan mangle data i settet vårt. Dette kan være at en måling ikke har blitt foretatt, at noen attributter ikke gir mening for dette tilfellet (barn har neppe inntekt), eller lignende tilfeller.

Vi kan håndtere dette ved enten å fjerne objekter som ikke har alle attributter, erstatte attributter som mangler med enten et estimat eller med den mest sannsynlige verdien. Vi kan også benytte oss av dataene, men kun ignorere de manglende attributtene.

Duplikate data

Duplikate data kan forekomme hvis vi slår sammen data fra ulike kilder. Vi kan også komme til å gjøre dobbeltregistreringer. Problemene oppstår hvis man registrerer tilnærmet duplikate data, men med enkelte forskjeller. Et eksempel kan være en person som registreres to ganger med ulikt telefonnummer.

Aggregering

Vi slår sammen objekter, f.eks. på samme måte som når vi beveger oss oppover i et konsepthierarki i et datavarehus. Ved å bruke aggregerte data får vi mer stabilitet i dataene våre, ved at de gjerne gir mindre variasjon, men dette kan skjule interessante avvik.

Sampling

Vi velger ut et subsett av dataene våre som representanter for hele settet. Her er det viktig med en rettferdig utvelgelse, og en utvelgelsesprosess som gir representative utvalg.

Dimensjonsreduksjon

For å unngå the curse of dimensionality kan vi velge å lage nye attributter som er en sammenslåing av eksisterende. Dette vil gjøre datasettet vårt mer håndterlig, men også gjøre at vi kan miste viktige detaljer.

Opprettelse av nye egenskaper

Vi kan opprette nye attributter som fanger opp mer informasjon, eller representerer den på en bedre måte. Vi kan konstruere en ny attributt k = m*n, slik at vi slipper å beregne k for hver gang vi gjør et oppslag.

Binærisering og diskretisering

Vi kan gjøre om en variabel til et kategorisk attributt, enten binært eller diskret. Dette kan gjøres både supervised (med bruk av klasser) og unsupervised (med bruk av klynger).

Transformering av attributter

Vi kan benytte en funksjon for å mappe en verdi til nye verdier. Vi kan f.eks. normalisere verdier slik at de blir like viktige i en beregning.

Simple matching coefficient (SMC)

Her ser vi på to sett med binære attributter. Vi sammenligner deretter om settene har den samme verdien for hvert attributt, og beregner deretter SMC = Antall like attributter / antall attributter.

Jaccard coefficient

Jaccard tar ikke hensyn til de stedene hvor begge datasettene har 0 som verdi på en attributt. Dette er nyttig i de tilfeller hvor dette ville skapt en falsk likhetsantagelse. To handlekurver som begge ikke innholder 2000 av de samme varene er neppe spesielt like, men for SMC vil antallet varer som mangler likt i begge kurvene overskygge de like elementene.

Jaccard er derfor definert som J = antall like positive attributter / antall attributter som ikke er negative matcher.

Cosinuslikhet

Her beregner vi en vektor for hver av datasettene, og regner deretter ut cosinusverdien mellom vektorene.

Kompleksitet

Kompleksiteten i beregningen av assosiasjonsreglene er gitt ved en kombinasjon av

• Valg av minimum støtte
• Dimensjonaliteten til dataene
• Databasestørrelse
• Transaksjonsbredde

Størrelsen på settet av kandidatregler er gitt som |L| = k, med (2^k)-2 kandidatregler. Dette ser bort fra reglene L -> Ø og Ø -> L (hvor Ø er det tomme settet).

Hunt's algoritme

Hunt's algoritme er den enkleste av algoritmene som brukes til beslutningstrær. For hver node avgjør vi for de poster som tilhører noden: - Tilhører alle poster den samme klassen? Hvis ja er dette en løvnode med den klassen - Hvis ingen poster peker til noden gis den majoritetsklassen til hele datasettet - Hvis det er ulike klasser, splitt på den beste attributten, og gjenta rekursivt for alle noder

Andre algoritmer

• C4.5 -- Trenger å ha hele datasettet i minnet for å fungere, er derfor lite brukbar på store datasett.
• ID3
• CART
• SLIQ, SPRINT

Den beste splitten

For de fleste algoritmer trenger vi å definere hva som er den beste attributten å utføre en splitt på. Dette kan vi beregne ved hjelp av ulike teknikker, nevneverdig er GINI, entropi og klassifiseringsfeil (misclassification error). Målet til alle algoritmene er å finne et mål på "renheten" til en node: Hvor stor andel av tilfellene har samme klasse. Vi ønsker å oppnå så høy renhet som mulig, vi sier da at vi har høy diskrimineringsgrad.

Stoppkriterie for trebygging

Et sentralt spørsmål vi kommer til er når vi skal stanse å bygge treet. Vi kan gjøre dette når det ikke lenger er mulig å utvide treet fordi all kjent informasjon er brukt opp, men dette kan være tidkrevende, og det er som vi skal se ulemper med å bygge et for nøyaktig tre.

Modellevaluering

Når vi skal evaluere modellen vår kan vi se på nøyaktighet (accuracy). Dette er et mål på hvor mange korrekte klassifiseringer som ble gjort, altså sanne positive og sanne negative i forhold til totalt antall eksempler i settet. En utfordring med dette er dersom vi har svært ulik størrelse på noen klasser. Vi kan da oppnå nesten 100% nøyaktighet, men utelate flere klasser.

For å evaluere ytelsen til modellen kan vi bruke en av flere teknikker:

• Holdout: Vi reserverer en del av settet til testing
• Tilfeldig subsampling: Vi gjennomfører holdout flere ganger med tilfeldig utvalg
• Kryssvalidering: Vi partisjonerer data i k disjunkte sett, trener på k-1 av settene, og tester på det siste.
• Bootstrapping
• Stratified samling

Nærmeste nabo klassifiserere

Her benytter vi oss av et antall (k) naboer som er nærmest det punktet vi skal klassifisere. Vi må ha en metrikk for å beregne avstanden mellom punkter, og et gitt tall for antall noder vi skal bruke. Standard metrikk er euklidsk avstand.

Dersom vi velger en for liten K vil vi være sensitive mot støypunkt, mens en for stor K kan gjøre at vi ser på et alt for bredt sett av tilfeller.

Når vi behandler høydimensjonale data med nærmeste nabo klassifisering kan vi treffe på the curse of dimensionality. Dette skjer f.eks. ved at data som har mange ulike attributter kan bli klassifisert med samme likhet som data med like mange like attributter. En løsning på dette problemet er å normalisere vektorene til enhetslengder.

k-NN klassifiserere er regnet som "late klassifiserere". De bygger ikke opp en modell på forhånd, men gjør kun arbeid når det trengs, altså når vi skal klassifisere et nytt tilfelle. Dette gjør at klassifisering er en relativt dyr oppgave.

Baysianske klassifiserere

Baysianske klassifiserere benytter seg av baysianske sannsynligheter for å klassifisere en post. Gitt en variabel Y, hva er sannsynligheten for at vi skal klassifisere som X, eller mer formelt:

P(X|Y)

Dette utvides til å gjelde alle kjente attributter, og vi beregner disse sannsynlighetene på forhånd slik at de er klare til bruk.

Vi kan utvide baysianske klassifiserere ved å gjøre noen antagelser, og får dermed en naiv baysiansk klassifiserer. Her antar vi at det er uavhengighet mellom attributtene gitt klassene, og vi ser bort fra manglende verdier. Det siste er viktig da en manglende verdi vil gjøre sannsynlighetsuttrykket lik 0. Når vi kan se bort fra disse verdiene får vi en langt mer robust utregning. Ulempen er at det ikke nødvendigvis stemmer at attributtene er uavhengige.

Support vektor machines (SVM)

Målet med en support vektor machine er å finne et lineært hyperplan som separerer dataene våre. Det vil normalt være mange ulike plasseringer for hyperplanet. Den beste plasseringen er da den som har høyest margin, altså hvor avstanden til det nærmeste punktet fra planet er størst.

Hvis det er umulig å finne en lineær linje gjennom dataene kan man transformere dataene til en høyere dimensjon hvor de vil være lineært separable.

Evaluering av K-means-klynger

For å finne ut hvor god klyngingen vi har oppnådd er kan vi benytte en evalueringsteknikk. Den vanligste er Sum of Squared Errors (SSE). For hvert punkt finner vi avstanden til den nærmeste sentroiden. Vi summerer feilene og har da et feilmål. En ulempe med denne teknikken er at vi ved å velge like mange sentroider som det er datapunkter vil få en SSE på 0. Vi må altså balansere mellom antall klynger og lav feil. Vi kan finne et godt tall for k ved å se på grafen over SSE, plottet mot antall klynger. Der grafen har knekkpunkter ser vi at vi vil tjene mindre på å øke k. Vi velger dermed et av knekkpunktene.

Valg av startsentroider

Valget av de første sentroidene er avgjørende for hvordan K-means oppfører seg. Ettersom valget er tilfeldig kan vi ende opp med en veldig god eller veldig dårlig klynging. Dette kan vi forbedre med ulike taktikker: - Gjør klynging mange ganger med tilfeldig valg, og velg den klyngingen som har lavest SSE. - Ulempen med dette er at vi må gjøre mange kjøringer, og ikke har noen garanti for at vi bare gjør dårlige valg. - Vi kan velge startsentroidene basert på hierarkisk klynging av et sample av dataene - Vil være effektivt for små k - Velg mer enn k startsentroider tilfeldig, og velg blant disse - Her kan vi velge de sentroidene som er lengst unna hverandre - Dersom vi gjør denne utvelgelsen på et sample reduserer vi faren for å velge en outlier - Vi kan løse problemet i pre/postprosessering - Normaliser data og eliminer outliers før kjøring. - Eliminer små klynger, splitt løse klynger, slå sammen nære klynger etter kjøring. - Vi kan benytte Bisecting K-means

Bisecting K-means

Her starter vi med alle punkter i en klynge, og splitter den deretter i to ved hjelp av standard k-means. Vi gjentar dette et forhåndsbestemt antall ganger, og beholder den splitten som har den beste splitten, typisk beregnet ved SSE. De to punktene vi velger som startsentroider skal være symetrisk over linjen som deler klyngen i to. Når vi har valgt den beste splitten gjentar vi prosedyren på de nye klyngene inntil vi har k klynger.

Utfordringer med K-means

K-means er en svært effektiv algoritme, men vi har et sett begrensinger. Den fungerer dårlig på ikke-sirkulære klynger, klynger med ulik tetthet og størrelse, den håndterer outliers dårlig, og det kreves data som det er mulig å uttrykke et senter for.

Agglomerativ klynging

For å utføre en agglomerativ hierarkisk klynging starter vi med alle punkter som klynger. Vi finner deretter de to nærmeste klyngene og slår disse sammen. Dette gjentar vi til det kun gjenstår en klynge.

DBSCAN-algoritmen

Vi utfører DBSCAN ved å klassifisere alle punkter som enten kjerne-, grense-, eller støypunkt. Deretter eliminerer vi alle støypunkt og lager deretter grupper av kjernepunkt som er innenfor hverandres Eps. Hver separerte gruppe av kjernepunkt blir en klynge. Alle grensepunkt tilegnes til sitt kjernepunkts klynge.

Fordeler og ulemper

DBSCAN er motstandsdyktig mot støy, og håndterer irregulære klyngeformer. Den er derimot svak på varierende tettheter og høydimensjonale data. Valg av verdier for Eps og MinPts er også essensielt for god ytelse. En måte å velge Eps er å sortere alle punkt etter deres avstand til nærmeste nabo, plotte dette mot antall punkt med lik eller lavere avstand, og velge Eps ut i fra knekkpunkt i grafen.

Siluettkoeffisient

Siluettkoeffisienten kombinerer tanker fra både kohesjon og separasjon. Kohesjon beskriver i hvor stor grad objektene i en klynge er relaterte, og beregnes ofte som summen av deres interne differanser, mens separasjon beskriver hvor stor avstand det er til andre klynger, og beregnes ofte som summen av differanser i avstand. Siluettkoeffisienten kan defineres som:

s = (b-a)/max(a,b)

hvor a = gjennomsnittlig distanse fra punkt i til punktene i klyngen til i, og b = min(gjennomsnittlig distanse fra punkt i til punkt i andre klynger). Jo nærmere 1 dette tallet kommer, jo bedre. Verdien kan ta alle tall mellom -1 og 1, hvor negative tall indikerer at det er større avstand internt i klyngen enn det er til punkter i andre klynger, noe som tyder på at klyngene våre ikke er velseparerte.