Datautvinning

Beslutsträdsinlärning är ett exempel på en databrytningsalgoritm som skapar prediktionsmodeller, i detta exempel för överlevnaden av en passagerare på RMS Titanic. Sibsp är antalet makar och syskon som personen har ombord. Siffrorna under trädets löv visar sannolikheten för överlevnad respektive procent av observationerna inom respektive löv.

Databrytning

Under­klass till	upptäckt, Text and data mining
Aspekt av	artificiell intelligens, maskininlärning, databas, algoritm, multivariat statistik

Databrytning, informationsutvinning eller datautvinning, av engelskans data mining, betecknar verktyg för att söka efter mönster, samband och trender i stora datamängder. Verktygen använder beräkningsmetoder för multivariat statistisk analys kombinerat med beräkningseffektiva algoritmer för maskininlärning och mönsterigenkänning hämtade från artificiell intelligens.

Allmänt

Tekniker för datautvinning tillämpas inom områden som visualisering av öppna data, bioinformatik, affärsunderrättelser (business intelligence), beslutsstödsystem, webbanvändningsanalys (web mining), IT-forensik och analys av medicinska data, sensordata och mycket annat. Text mining innebär datautvinning ur icke-strukturerade data i form av text, och kan användas för maskinöversättning, automatisk sammanfattning av texter, statistisk analys av språk, med mera.

Det bredare begreppet big data åsyftar även tekniker för insamling av data från flera stora databaser och datafiler till ett sökbart informationslager (data warehousing), vilket ofta föregår men inte ska sammanblandas med datautvinning.

Data mining är ett trendord som åsyftar tidigare kända tekniker, och som har fått uppmärksamhet på senare år därför att dagens växande datamängder med ett stort antal variabler ofta är svåröverblickbara för människor. Dessutom kan klassiska metoder för multivariat statistisk dataanalys, exempelvis korrelationsberäkning och multipel regression, ge orimligt stor beräkningskomplexitet och fungerar därför inte vid storskalig analys.

Syftet med verktyg för datautvinning är att underlätta sökandet efter strukturer bland ett stort antal variabler och leda till upptäckt av tidigare okända relationer, och på så sätt extrahera begriplig och användbar information ur rådata.

Forskningsmetod

Tredimensionellt sambandsdiagram där värdet av tre variabler indikeras med datapunktens position i rummet, och en fjärde variabel med dess färg.

Användaren av verktyg för databrytning väljer bland en uppsättning algoritmer och diagram som lämpar sig för olika typer av analys och problemställningar, och för olika typer av data. Användaren testar och jämför vilken algoritm och vilka parameterinställningar som ger bäst reliabilitet eller tydligast diagram inom rimlig beräkningstid för det aktuella problemet.

Den datamängd^(en) som analyseras är vanligen i form av en tabell, där varje rad eller post kan motsvara resultatet från ett mättillfälle eller för en försöksperson, och varje kolumn är en variabel eller ett attribut. Varje rad betraktas som en datapunkt i ett flerdimensionellt rum. Varje attribut har en specifik statistisk mätskala och en specifik datatyp. Ett av attributen kan ha roll som målvariabel, det vill säga den variabel vi vill träna självlärande algoritmer att prediktera.

Explorativ dataanalys

Arbetssättet vid databrytning baseras på exploratativ dataanalys^(en) (EDA), som innebär att man omväxlande kombinerar verktygets automatiserade beräkningar med visualisering och manuell observation. Syftet med EDA är att hjälpa forskaren att upptäcka nya okända relationer som kan åskådliggöras med tydliga diagram, och att bygga nya prediktionsmodeller. Syftet är också att bedöma vilka samband som kan vara intressanta och att identifiera vilka variabler och datapunkter som förväntas ha betydelse vid prediktering av en målvariabel, och vilka som kan elimineras för att reducera beräkningstiden.

Explorativ dataanalys skiljer sig från konfirmativ dataanalys (CDA) som är det traditionella arbetssättet vid kvantitativ forskning. Vid CDA formulerar man hypoteser och bygger modeller innan man påbörjar insamling och analys av experimentella data, och dataanalysen används enbart för att verifiera prediktioner genom systematisk hypotesprövning. EDA är däremot en hypotesgenererande och induktiv metod, som ger upphov till datadrivna hypoteser. EDA bör kompletteras med CDA för att undvika felaktiga slutsatser.

Vid databrytning arbetar man dessutom ofta heuristiskt genom att utnyttja problemspecifik kunskap om vilken data som förväntas ha betydelse för resultatet och vilka typer av relationer som är rimliga och användbara att identifiera.

Risk för förhastade slutsatser

Kritiker menar att man vid databrytning och annan explorativ dataanalys riskerar att dra förhastade slutsatser eftersom man kringgår inledande formulering och testning av hypoteser. Tillfälliga slumpmässiga mönster och relationer finns alltid mellan ett stort antal variabler, och om man letar förutsättningslöst bland alla upptänkliga samband riskerar man att identifiera slumpmässiga relationer. Sådant missbruk av multivariat analys kallas ibland data dredging, data fishing eller data snooping bias. Vid hypotestestning brukar man rekommendera en signifikansnivå med ett p-värde på högst 0,05, vilket innebär att det är mindre än en chans på tjugo att det som ser ut som ett samband i själva verket bara är ren slump. Denna tumregel förutsätter emellertid att man har ett fåtal tydliga hypoteser från början, medan signifikansnivån bör vara betydligt lägre vid explorativ dataanalys.

Liksom vid annan multivariat dataanalys riskerar man confounding (okända snedvridande faktorer som är korrelerade med indata och målvariabel och därför ger felaktigt intryck av samband), eller att predikteringar görs långt in i framtiden genom extrapolation av gamla data som inte är ett representativt urval för framtida data.

Resultatet av datamodellering implementeras ofta i form av policier, exempelvis för vilken produkt som ska marknadsföras för vilken kund, eller i form av verktyg för att prediktera variabler, exempelvis marknadspris. Vid införandet av sådana riskerar man att förändra marknadens eller systemets beteende, och då är inte prediktionsmodellerna tillämpliga längre. Om exempelvis kunder på en auktionssajt utnyttjar en web mining-tjänst som predikterar auktionspriset på en vara baserat på hur många som klickar på varans webblänk, finns en risk att intresserade köpare undviker att klicka på varans webbsida för att inte höja priset, och att säljare försöker höja priset genom att klicka på varans webbsida.

Processdiagram som visar relationen mellan de olika faserna i CRISP-DM

Standardiserad arbetsprocess

För att undvika ovanstående problem bör den explorativa datauvinningen följas av en valideringsfas, då generaliserbarheten av de identifierade sambanden utvärderas på andra datamängder (så kallade testdata). Under utvärderingsfasen beräknas olika prestandamått för mönstrens och predikteringarnas reliabilitet. Generaliserbarheten av de samband man kommer fram till måste också rimlighetsbedömas baserat på begripliga förklaringsmodeller, vilket förutsätter att man först utvecklar en grundförståelse för problemområdet och variablernas innebörd. Vissa metoder inom databrytning kan ge upphov till prediktionsmodeller som har ett förklaringsvärde som kan rimlighetsbedömas, exempelvis beslutsträd, medan andra modeller, exempelvis vikterna i neurala nätverk, är svårtolkade.

Standardmodeller för arbetsprocessen vid databrytning har därför formulerats. Den så kallade CRISP-DM-modellen är idag den vanligaste metodiken som tillämpas för databrytning:

1. Uppgiftsförståelse (business understanding)
2. Dataförståelse
3. Datapreparering
4. Modellering
5. Validering
6. Införande i verksamheten

Klusteranalys med K-means-algoritmen grupperar datapunkter i ett givet antal kluster (i detta fall tre, representerade av tre färger). Algoritmen maximerar avståndet mellan klustren, som förutsätts vara lika stora (inte adekvat i detta exempel) och vara geometriskt konvexa.

Tvådimensionellt korrelogram kan illustrera en korrelationsmatris, som kan användas vid urval av variabler.

Metoder och algoritmer

k-NN-klassificering. Träningsdatat har klassificerats i två klasser: blå kvadrater respektive röda trianglar. Testdatapunkten (grön cirkel) har okänd klass. Om k = 3 (heldragen cirkel - de tre närmaste träningsdatapunkterna) klassificeras den som röd triangel eftersom det finns fler trianglar än kvadrater i cirkeln. Om k = 5 (streckad cirkel - med fem träningsdatapunkter) klassificeras den istället som blå kvadrat.

Tränad klassificering med stödvektormaskin (SVM), som avgränsar klasserna med hyperplan för minsta möjliga fel och största möjliga avstånd mellan hyperplanet och närmaste datapunkt.

Ett artificiellt neuralt nätverk kan tränas att prediktera och klassificera.

Linjär och ickelinjär regressionsanalys med polynom av olika ordning.

En genetisk algoritm genererar slumpvisa kombinationer av parametervärden, och korsfertiliserar parvis de kombinationer ("föräldrar") som ger bäst prestanda så att nya potentiellt goda kombinationer ("barn") uppstår. Efter några generationer erhålles en lösning som sannolikt är nära optimum.

Datatutvinning innefattar en rad metoder och algoritmer för olika typer av dataanalys, som kan grupperas enligt följande.

Datavisualisering

• sambandsdiagram
• histogram
• dendrogram (trädkliknande grafer)
• korrelogram^(en)

Datapreparering och datarensning

• Formatkonvertering och import av data på olika filformat, exempelvis kalkylark, kommaseparerade värden (CSV-filer) med decimalpunkt, tab- eller semikolonsepararade värden med decimalkomma, samt import från relationsdatabaser och webbtjänster, ofta på XML- eller JSON-format eller genom web scraping^(en)
• Urval av attribut^(en). För att avgöra variablernas betydelse och beroenden av varandra används ofta icke-tränade algoritmer, se nedan. Exempel:
  • Correlation feature selection^(en) (CFS), som behåller attribut med högt absolutbelopp av korrelationen med målvariabeln, men som har lågt belopp av korrelationen sinsemellan.
• Identifiering och borttagning av avvikande värden (anomalier och uteliggare)
• Hantering av saknade värden (bortfall), exempelvis genom estimering
• Normalisering så att vektornormen av attribut blir 1
• Klassificering av numeriska variabler och ordnade kategorier i intervall, för att konvertera till nominala variabler (med ett begränsat antal kategorier)
• Datatransformation eller -konvertering, exempelvis:
  • av polynominal variabel (med fler än två icke-ordnade kategorier) till flera binominala variabler (med två värden)
  • till oberoende och ortogonala variabler, genom principalkomponentanalys (PCA), i syfte att reducera antal variabler

Icke-tränade självlärande algoritmer

Icke-tränade (non-supervised) algoritmer saknar målvariabel. Syftet är att ge förståelse för hur mindre grupper av variabler förhåller sig till varandra. Algoritmerna används för att upptäcka lokala mönster och relationer mellan en delmängd av variablerna, men som inte är tillämpliga på datamängden i sin helhet. Algoritmerna används bland annat under dataförståelsefasen i ovan nämnda arbetsprocess för att identifiera vilka variabler som sannolikt saknar betydelse för den variabel man vill prediktera. De kan också användas för att extrahera dold information, exempelvis kategorier och kluster av datapunkter, som kan ha betydelse för predikteringen. Exempel på typer av algoritmer:

• klusteranalys, för att gruppera liknande poster i en tabell till ett kluster eller en kategori, exempelvis marknadssegment. Syftet kan vara att identifiera vilka variabler som har betydelse för marknadssegmenteringen. Exempel:
  • k means
• Associationsregelanalys (mönsterigenkänning), exempelvis för market basket analysis (att upptäcka att en kund som handlar vara A och B med stor sannolikhet och låg statistisk signifikansnivå handlar vara C), eller för IT-forensik (att upptäcka att en person som brukar kommunicera med A och B med stor sannolikhet och låg signifikansnivå också kommunicerar med person C). Exempel:
  • a priorialgoritmen
  • FP-Growth-algoritmen
• korrelationsanalys
• subjektbaserad igenkänning
• Principalkomponentanalys och faktoranalys

Tränade algoritmer

Syftet med tränade (supervised) självlärande algoritmer är att ge upphov till prediktionsmodeller som kan förutsäga värdet av en målvariabel, med utgångspunkt i att målvariabeln är känd för träningsdata. Detta kan användas för klassificering, utifrån att träningsdata redan klassificerats (försetts med en känd målvariabel), exempelvis en kategori, ett rekommenderat beslut eller en diagnos. Tränade algoritmer kan också användas för skattning, interpolation, extrapolation och trendanalys av en numerisk målvariabel. Modellen utgör en global beskrivning av relationen mellan målvariabeln och summan av hela datamängden.

Exempel på tränade algoritmer:

• klassificering av datapunkter i kategorier. Exempel:
  • k-nearest neighbors (k-NN) - som även kan användas för att detektera anomalier och för prediktering av numeriska värden
  • Beslutsträdsinlärning - där varje förgrening i trädet motsvarar ett intervall för en specifik variabel, vilket ger begriplig modell
    • Random forest - som delar upp träningsdata i flera slumpmässiga subset, som var och en ger upphov till i ett beslutsträd (en skog av träd), som kombineras genom röstningsförfarande
  • Stödvektormaskin (SVM) - där klasser avgränsas med hyperplan, och algoritmen eftersträvar maximal felmarginal
    • Ickelinjär stödvektormaskin - där klasser avgränsas med icke-plana ytor, vilket förorsakar hög beräkningskomplexitet
  • Naiv bayesiansk klassificerare - som uppskattar sannolikheter enligt Bayes sats men under antagande att alla variabler är sinsemellan oberoende, förutom med målvariabeln
• Artificiella neurala nätverk - ger låg beräkningskomplexitet
• Regressionsanalys:
  • linjär regression
  • ickelinjär regression
  • multipel regression

Verifiering och validering

Vid träning av självlärande algoritmer används träningsdata som måste vara ett statistiskt urval av de data som det ska tillämpas på, och som innehåller en målvariabel med givna värden. Ett prestandamått beräknas genom att jämföra målvariabeln med algoritmens estimering av målvariabeln. Det finns metoder för att undvika överanpassning (eng overfitting), det vill säga att modellen får för hög komplexitet och hög prestanda för träningsdata men låg reliabilitet för andra data. Ett exempel är med split-half-metoden genom att dela upp den datamängd som har känd målvariabel i träningsdata och testdata, och efter varje träningsiteration applicera den erhållna modellen på testdata. Träningen avbryts när modellen inte ger ökad prestanda för testdata. Den modell som erhålles efter slutförd träning tillämpas därefter på nya data, som saknar känd målvariabel. Om mängden tränings- och testdata är begränsad kan man upprepa förfarandet för flera olika uppdelningar i testdata och träningsdata. Därmed erhålles flera prediktionsmodeller, som kan kombineras exempelvis genom majoritetsröstning av kategorisering eller medelvärdesbildning av estimering.

Ett annat exempel på metod för att undvika överanpassning är beskärning av komplexa beslutsträd (eng. pruning).

Exempel på prestandamått:

• Andel korrekt klassificerade testpunkter (%)
• En confusion matrix:

	Predikterade som positiva:	Predikterade som negativa:	Summa:
Positiv målvariabel:	Antal sant positiva (TP)	Antal falskt negativa (FN)	(TP + FN)
Negativ målvariabel:	Antal falsk positiva (FP)	Antal sant negativa (TN)	(FP + TN)
Summa:	TP + FP	FN + TN	TP + FN + FP + TN

• Utifrån denna matris kan man beräkna träffsäkerhet^(en): (TP + TN)/(TP + FN + FP + TN),
• Utrifån matrisen kan man även beräkna specificitet, sensitivitet, negativt prediktivt värde och positivt prediktivt värde

Andra vanliga mått är:

• Receiver operating characteristic (ROC-kurvor) kan visa relationen mellan sant positiv och sant negativ, exempelvis vid naiv baysisk klassificering. Arean under kurven (AUC) ska då vara så stor som möjligt.
• Kvadratiskt medelfel (MSE, mean squared error)
• Sammanlagt kvadratiskt fel (SSE, summed squared error, eller TSE, total squared error)
• Standardfel

Meta-analys

Meta-analys är metoder för att välja lämpligast algoritm och optimera algoritmens parameterinställningar för respektive fall, och för att utveckla strategier för att förbättra systemets lärande som är tillämpliga på ett stort antal fall. Exempel på optimeringsalgoritm:

• genetiska algoritmer

Programvara

Vanlig programvara för databrytning är:

• R (statistikprogram som användaren programmerar med ett skriptspråk - öppen källkod)
• WEKA (programbibliotek i Java som också har ett grafiskt användargränssnitt - öppen källkod)
• Rapidminer (baseras på grafisk programmering - öppen källkod fram till version 5.3)
• Orange, Pandas eller scikit learn (programbibliotek för Python - öppen källkod)
• SPSS (kommersiellt statistikprogram)

Tillämpning i Sverige

FRA:s användning av databrytning

FRA använder databrytning i sin bearbetning av trafikdata, benämnt som "trafikbearbetning" och fastställande av "trafikmönster" i förarbetena till FRA-lagen,

och förarbetena till FRA:s PUL.

Se även

• Deep learning
• Suddig logik (fuzzy logic)
• Trafikanalys

Källor

• Larose, D. T. (2005): Discovering Knowledge in Data: An introduction to Data mining, Wiley