Datautvinning

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

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  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å  (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.

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: 
 Uppgiftsförståelse (business understanding)
 Dataförståelse
 Datapreparering
 Modellering 
 Validering
 Införande i verksamheten

Metoder och algoritmer 

 

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)

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  
. För att avgöra variablernas betydelse och beroenden av varandra används ofta icke-tränade algoritmer, se nedan. Exempel:
 (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:

Utifrån denna matris kan man beräkna : (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, </p>och förarbetena till FRA:s PUL.</p>

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

Noter 

Analys
Datavetenskap
Informationsvetenskap
Statistik
Signalspaning