Convergence – 2-07. GPS, data mining

Hej Numb3rs fans.

Jeg lagde mærke til en hel del matematik denne gang: Fourieranalyse, data-mining, banen for et projektil, GPS-systemet og diverse fra Charlies forskning – og hans konkurrent fra tiden på Princeton: Repræsentationsteori, den unitære gruppe, neurale netværk og et par imponerende integraler. I får noget om datamining og om GPS idag. Vi må se, om jeg får tid til at se på de andre emner en anden gang.
I øvrigt fremgik det, at alle mobiltelefoner i USA er udstyret med en GPS-chip, så de kan spores, og så man lagrer, hvor de har været. Det skulle være et krav efter 11/9. Sådan er det ikke i Danmark. Her kan man (politiet efter en dommerkendelse) få at vide, hvilke master en bestemt telefon har haft forbindelse til; den har forbindelse til en mast og et bestemt panel på masten – den mast, der er tættest på. Det giver en 120 graders vinkel (der er tre paneler) udfra masten, hvor telefonen har været. Området afgrænses af, hvor andre master ville være tættere på. Ser man ikke bare på gemte data, men får tilladelse til en sporing af en bestemt telefon i en kommende periode, kan man gøre det mere præcist. Vist nok noget med at lukke for det panel, der er tættest på, hvorefter telefonen opretter forbindelse til det, der er næsttættest på.

GPS
Der er masser af matematik bag GPS-systemet. Og bag det kommende europæiske projekt, Galileo.
GPS-systemet blev oprindeligt udviklet af det amerikanske militær, men anvendes nu, som de fleste ved, af masser af mennesker; f.eks. til at finde vej. Når man køber “en GPS” plejer man nok at mene et dyr, der kan bruges til at fortælle, hvordan man kommer fra Aalborg til Sønderborg; som kan tegne det på et kort, og som undervejs kan fortælle, at nu skal vi snart dreje til højre.
GPS er den del af apparatet, der regner ud, hvor vi er. GPS-systemet består af 21 aktive og 3 reservesatellitter, i baner 20200 km over Jorden med banehældning 55 grader (i forhold til Ækvator). De er placeret, så man til enhver tid og på ethvert punkt på Jorden vil kunne “se” mindst 4 satellitter (der er midst 4 satellitter over horisonten).
Udfra satellitternes koordinater og GPS-modtagerens afstand til hver af dem, kan man bestemme modtagerens koordinater.
Det er der naturligvis noget geometri i, og man skal i sidste ende løse et ligningssystem, hvor der kun burde være tre ubekendte, nemlig x, y og z koordinaten for GPS-modtageren i et passende koordinatsystem.
Men så let går det ikke. Afstanden til en af satellitterne udregnes ved, at satellitten har et MEGET nøjagtigt ur (faktisk to ure – så er der et i reserve); den sender et signal, 1001111011… et tal for hvert tidsinterval- f.eks. hvert sekund, men det er nu meget hyppigere. Modtageren kan generere samme følge af tal. Hvis nu modtageren havde et lige så præcist ur, ville man

• kunne se, hvor meget talfølgen er forskudt/forsinket;
• bruge det til at regne ud, hvor lang tid det tager for satellittens signal at nå frem,
• og dermed finde afstanden – hastigheden for signalet er lysets hastighed.

MEN modtageren har ikke sådan et fint ur – de er nemlig dyre, og det er GPS-modtagere ikke. Derfor er der 4 ubekendte: x, y og z koordinaten, og unøjagtigheden i uret i modtageren. Man skal altså bruge 4 satellitter.
Læs mere i Johan P. Hansens noter om, hvordan man løser de fire ligninger. Man kan også se andre aspekter af matematikken i GPS. Især om, hvordan følgerne af 0 og 1 frembringes i sender og modtager.
Der er også brug for fejlkorrigerende koder (omtalt her på bloggen) – så støj på signalet kan fjernes – der er en hel del statistik og masser af fysik f.eks. relativitetsteori; både den specielle og den generelle.

Data mining
Charlie ledte efter sammenhænge i store datamængder.
Data mining, som vi ikke plejer at oversætte, dækker over flere forskellige teknikker. Overordnet går det ud på at lede efter struktur og sammenhæng i store datamængder. Struktur kan f.eks. være: Kunder, der køber både cola og økologisk mælk, skal nok også have en pose lakrids, eller noget i den retning. Det kan være at finde risikable kunder i kreditforeningen eller forsikringsselskabet, eller at opdage, at der er en sammenhæng mellem at spise bestemte ting og at få grøn stær. Et andet eksempel er undersøgelse af DNA-microarrays, hvor man måler aktiviteten af tusindvis af gener og leder efter gener med abnormt aktivitetsniveau i forhold til alskens sygdomme.
Det drejer sig normalt om meget store datamængder, hvor man ikke bare kan undersøge alle de mulige sammenhænge.
Man skal altså være mere smart. (Og her har jeg fået hjælp af Poul Svante Eriksen, som ved meget om Data mining)

Der er mange forskellige metoder, f.eks. taksonomi a la Carl von Linné’s klassifikation af planter, men lad mig omtale en, som er af geometrisk natur.
Man har, ligesom jeg omtalte i sidste uge, datapunkterne i et rum af meget høj dimension. Det skal man ikke filosofere så meget over. Dimensionen er simpelthen antallet af koordinater for hvert punkt (f.eks. hver kunde). Så hvis der er 8 egenskaber for hvert punkt, har rummet dimension 8.

Vi forestiller os, at der er noget interessant struktur; altså at data ikke er normalfordelt, men er delt op i flere “skyer” af punkter.
Lad os forestille os, at vi er i planen; altså at der er to egenskaber for hvert datapunkt. Lad os sige, vi har tre dataskyer, alle liggende ud ad x-aksen – en ligner en cirkel med centrum i (2,0) og radius 1, en med centrum i (6,0) og radius 3, og en med centrum i (122,0) og radius 3. (Plus en hel del punkter som ligger spredt rundt omkring udenfor cirklerne)
Nu projiceres ind på y-aksen (svarende til, at man glemmer punkternes x-koordinat, så et punkt med koordinater (7,8) bliver sendt til punktet (0,8), men det gør punktet (15,8) også.) Man kan se det for sig, som at alt mases ind på y-aksen.
Så bliver de tre skyer ud ad x-aksen mast sammen til 1 sky.
Hvis vi i stedet projicerer på x-aksen, vil der stadig være tre “skyer”, nu af dimension 1.
Man kan også forestille sig, at den bedste projektion ikke kan skille alle skyer ad, men måske kun 7 ud af 10.
Man leder efter den projektion, som ser mest “interessant” ud, og det kan man definere på mange måder. For eksempel at den bevarer mest afvigelse fra normalfordelingen. Igen er der noget at overveje: Hvad er f.eks. et mål for afvigelsen fra normalfordelingen? (Det kan man vælge).
Der er mange andre teknikker bag data mining – se f.eks. Wikipedia
Som Charlie siger, kan man sommetider finde sammenhænge, som ikke giver mening. Han fortæller, at man brugte data-mining til at lede efter terrorister efter 11/9, og en af de meget mistænkelige personer var Condoleeza Rice. Hun har jo oplagt haft forbindelse til meget, der har med terror at gøre. Så man skal altså have mennesker til at se efter, om resultaterne giver mening.

Hilsen Lisbeth www.math.aau.dk/~fajstrup
numb3rs@math.aau.dk