Datahashing forbedrer skøn over antallet af ofre i databaser

Forskere fra Rice University og Duke University bruger værktøjerne til statistik og datavidenskab i samarbejde med Human Rights Data Analysis Group (HRDAG) til præcist og effektivt at estimere antallet af identificerede ofre, der blev dræbt i den syriske borgerkrig.

I et papir, der er tilgængeligt online og skal offentliggøres i juni-udgaven af Annals of Applied Statistics , forskerne rapporterer om en fireårig indsats for at kombinere en dataindekseringsmetode kaldet "hashing med statistisk estimering." Den nye metode producerer realtidsestimat af dokumenterede, identificerede ofre med en langt lavere fejlmargin end eksisterende statistiske metoder til at finde duplikerede poster i databaser.

"Det er nemt at smide duplikerede poster ud, hvis alle data er rene - navnene er fuldstændige, stavemåder er korrekte, datoer er nøjagtige, etc., " sagde studie medforfatter Beidi Chen, en Rice kandidatstuderende i datalogi. "Krigsskadedataene er ikke sådan. Folk bruger kaldenavne. Datoer er nogle gange inkluderet i én database, men mangler i en anden. Det er et klassisk eksempel på, hvad vi omtaler som et 'støjende' datasæt. Udfordringen er at finde en måde at estimer antallet af unikke poster nøjagtigt på trods af denne støj."

Ved at bruge optegnelser fra fire databaser over mennesker, der blev dræbt i den syriske krig, Chen, Duke-statistiker og maskinlæringsekspert Rebecca Steorts og Rice-datamatiker Anshumali Shrivastava anslåede, at der var 191, 874 unikke individer dokumenteret fra marts 2011 til april 2014. Det er meget tæt på estimatet på 191, 369 udarbejdet i 2014 af HRDAG, en nonprofitorganisation, der hjælper med at opbygge videnskabeligt forsvarlige, evidensbaserede argumenter for menneskerettighedskrænkelser.

Men mens HRDAG's skøn var afhængig af menneskelige arbejderes omhyggelige indsats for omhyggeligt at luge potentielle duplikerede optegnelser ud, hashing med statistisk estimering viste sig at være hurtigere, nemmere og billigere. Forskerne sagde, at hashing også havde den vigtige fordel ved et skarpt konfidensinterval:Fejlområdet er plus eller minus 1, 772, eller mindre end 1 procent af det samlede antal ofre.

"Den store gevinst ved denne metode er, at vi hurtigt kan beregne det sandsynlige antal unikke elementer i et datasæt med mange dubletter, " sagde Patrick Ball, HRDAGs forskningsdirektør. "Vi kan gøre meget med dette skøn."

Shrivastava sagde, at skarpheden af ​​hashing-estimatet skyldes den teknik, der blev brugt til at indeksere tabsposterne. Hashing involverer konvertering af en komplet datapost – et navn, dato, dødssted og køn i tilfælde af hvert syrisk krigsoffer – i ét nummer kaldet en hash. Hashes produceres af en algoritme, der tager højde for de alfanumeriske oplysninger i en post, og de er gemt i en hash-tabel, der fungerer meget som indekset i en bog. Jo mere tekstlig lighed der er mellem to poster, jo tættere sammen er deres hash i tabellen.

"Vores metode - unik entitetsvurdering - kunne vise sig at være nyttig ud over blot den syriske konflikt, sagde Steorts, assisterende professor i statistisk videnskab ved Duke.

Hun sagde, at algoritmen og metoden kunne bruges til lægejournaler, officiel statistik og brancheansøgninger.

"I takt med at vi indsamler flere og flere data, dobbeltarbejde bliver et mere aktuelt og socialt vigtigt problem, " sagde Steorts. "Entitetsløsningsproblemer skal skaleres til millioner og milliarder af poster. Selvfølgelig, den mest nøjagtige måde at finde duplikerede poster på er at få en ekspert til at tjekke hver post. Men dette er umuligt for store datasæt, da antallet af par, der skal sammenlignes, vokser dramatisk, efterhånden som antallet af poster stiger."

For eksempel, en rekord-for-record-analyse af alle fire syriske krigsdatabaser ville medføre omkring 63 milliarder parrede sammenligninger, hun sagde.

Shrivastava, assisterende professor i datalogi ved Rice, sagde, "Hvis du antager, som datoer, der er tæt på, kan være dubletter, du kan reducere antallet af sammenligninger, der er nødvendige, men enhver antagelse kommer med en bias, og i sidste ende vil du have et upartisk skøn. En statistisk tilgang, der undgår bias, er tilfældig stikprøve. Så vælg måske 1 million tilfældige par ud af de 63 milliarder, se, hvor mange der er dubletter, og anvend derefter denne sats på hele datasættet. Dette giver et objektivt skøn, hvilket er godt, men sandsynligheden for at finde dubletter rent tilfældigt er ret lav, og det giver en høj varians.

"I dette tilfælde, for eksempel, stikprøveudtagning kunne også estimere de dokumenterede tællinger til omkring 191, 000, " sagde han. "Men det kunne ikke fortælle os med nogen sikkerhed, om tællingen var 176, 000 eller 216, 000 eller et tal imellem.

"I det seneste arbejde, mit laboratorium har vist, at hashing-algoritmer, der oprindeligt var designet til at udføre søgning, også kan bruges som adaptive samplere, der præcist afbøder den høje varians, der er forbundet med tilfældig prøveudtagning, " sagde Shrivastava.

"At løse hver dublet virker meget tiltalende, " han sagde, "men det er den sværere måde at estimere antallet af unikke entiteter på. Den nye teori om adaptiv sampling med hashing giver os mulighed for direkte at estimere unikke entitetstællinger effektivt, med stor selvtillid, uden at løse dubletterne."

"I sidste ende, det har været fænomenalt at gøre metodiske og algoritmiske fremskridt motiveret af et så vigtigt problem, " sagde Steorts. "HRDAG har banet vejen. Vores mål og håb er, at vores indsats vil vise sig nyttig for deres arbejde."

Shrivastava og Steorts sagde, at de planlægger fremtidig forskning for at anvende hashing-teknikken til unik entitetstilnærmelse til andre typer datasæt.