Afstande, nærmest, størst, mindst

Når vi adskiller eller samler data bygger vi på en form for afstand. De \(k\) nærmeste naboer er dem, der ligger tættest på i én eller anden forstand. Hvis det drejer sig om dem, hvis højder er tætte på hinanden eller måske dem, der vejer nogenlunde det samme, er det klart, hvad man mener. Der er tal, man umiddelbart kan sammenligne. Men hvad med at sammenligne både vægt og højde? Hvad betyder så mest? Er der lige langt mellem en person A, der vejer 80 kg og er 1,80 m høj og en anden, B, der vejer 90 kg og er 2,00 m eller mellem A og C, der vejer 70 kg og er 1,60 m? Det er ikke klart, selvom vi da kan plotte de tre punkter i et (vægt, højde) koordinatsystem og endda bruge Pythagoras og få den samme afstand.1 Udregner man BMI, er \(A\) tættere på \(B\) end på \(C\). Det kommer nok også an på, hvad vi gerne vil udtale os om: Er de nogenlunde lige gode til at løbe langt? Eller hurtigt? Mere kompliceret bliver det, hvis vi også vil inddrage øjenfarve, skostørrelse eller måske, om de køber rigtig meget mælk. Der er mange eksempler på afstande, som ikke umiddelbart er fysisk afstand. For eksempel mellem ord (LINK) eller mellem DNA (Link)

1 Afstanden bliver \(10^2+0,2^2\). Bemærk, at det er udregnet udfra vægt i kg og højde i meter. Med højde i cm ville det være \(10^2+20^2\), men stadig samme afstand fra A til B som fra A til C. Se Afstand udfra Data for mere info om effekten af at skifte enheder. Det kan godt lave om på, hvilke punkter, der ligger nærmest.

Clustering - klyngeanalyse. SKAL DET BRUGES?

Clustering er at samle datapunkter i grupper, klynger, så objekter i en klynge har mere til fælles med hinanden end med objekter i andre grupper. Har man et afstandsbegreb, der passer godt til det, vi mener med til fælles, kan man bruge det til clustering - objekter i samme klynge er tæt på hinanden, men længere fra punkter i de andre klynger.

Hierarkisk clustering

Her kender vi alle parvise afstande. Og ikke andet.

Udfra den information laver vi et dendogram, hvor i første omgang par af datapunkter "mødes" i den højde, der svarer til deres afstand. Men der er mere: Hvornår skal datapunktet \(p\) mødes med \(qr\), som mødtes tidligere? Hvornår skal \(pqr\) mødes med \(ab\)? Det er linkage-reglerne.

  • Single linkage: \(pqr\) mødes med \(ab\) i den højde, hvor minimumsafstanden mellem de to grupper af punkter nås:
    Minimum af \(d(a,p),d(a,q), d(a,r), d(b,p), d(b,q), d(p,r)\)

  • Complete linkage: \(pqr\) mødes med \(ab\), når den maksimale afstand mellem punkter i de to grupper er nået.
    Maksimum af \(d(a,p),d(a,q), d(a,r), d(b,p), d(b,q), d(p,r)\)

  • Middelafstand- average linkage: Når den gennemsnitlige afstand er nået. \(\frac{1}{2\cdot 3}(d(a,p)+d(a,q)+ d(a,r)+ d(b,p)+ d(b,q)+ d(p,r))\)

(OBS: Her skal være tegninger og diagrammer -dendrogrammer. Og eksempler på, hvad forskellen er på de forskellige linkagekrav)

Klyngeanalyse af DNA eller for eksempel mRNA giver anledning til dendrogrammer, som kaldes de phylogenetiske træer for de arter/sygdomme,... der svarer til den analyserede DNA.

https://www.ncbi.nlm.nih.gov/pmc/articles/PMC2859286/

https://www.ncbi.nlm.nih.gov/pmc/articles/PMC6130602/

k-means clustering

Vores data er punkter med \(d\) koordinater. Afstanden er Euklidisk. Vi vælger \(k\), det antal clusters, det skal ende med. Målet er at opdele data i \(k\) dele, \(S_1, S_2,\ldots , S_k\) så den samlede gennemsnitlige kvadratiske afstand \[\Sigma_{i=1}^{k}\Sigma_{p,q\in S_i}\frac{1}{2|S_i|}\|p-q\|^2\] indenfor de \(k\) clusters er mindst mulig.

Clustering og anbefalingsalgoritmer. DET SKAL NOK IKKE BRUGES

Clustering er samling af datapunkter i "klumper", hvor punkterne i en klump ligner hinanden, men ikke ligner dem, der er i andre klumper. Det kan man bruge en metrik til, men der er andre måder, data kan ligne hinanden på. Når musiktjenester anbefaler musik, online boghandlere anbefaler bøger, online supermarkeder anbefaler grønsager etc. "Andre, der hører xxx hører også yyy." "Andre, der har set filmen xxx har også set filmen yyy", så baserer de anbefalingerne på en forståelse af, hvordan vi ligner andre kunder.

Ligner handler her om, hvor mange film, vi har fælles med hinanden. Der er et stykke vej, til definitionen, men hold hovedet koldt, så går det:

Hyppige delmængder - frequent item set:

Hvis vi har forbrugere, der har købt/lyttet til/set som følger:

1 { c,e,a}
2 { d,b,e}
3 { b,c,e,d}
4 { c,e,d,a}
5 {b,e}
6 {c,d,a}
7 {b,e,a}
8 {b,c}
9 {c,e,d}

uddrager vi hyppige delmængder

{a} hørt af 1,4,6,7
{b} hørt af 2,3,5,7,8
{c} hørt af 1,3,4,6,8
{d} hørt af 2,3,4,6,8,9
{e} hørt af 1,2,3,4,5,7,9
{a,b} hørt af 7
{a,c} hørt af 1,4,6
{a,d} hørt af 4,6
{ a,e} hørt af 1,4,7
{b,c} hørt af 3, 8
{b,d} hørt af 2,3,8
{b,e} hørt af 2,3,5,7
{c,d} hørt af 3,4,6,8
{c,e} hørt af 1,3,4
{d,e} hørt af 2,3,4,9
{a,c,d} hørt af 4
{a,c,e} hørt af 1,4
{b,c,d} hørt af 3
{b,c,e} hørt af 3
{b,d,e} hørt af 2,3
{c,d,e} hørt af 3,4,9

Det løber ret hurtigt ud over det, man kan overskue. Men vi kan strukturere: Når {c,d,e} er set/hørt af 3,4,9 er det klart, at {c,d}, {c,e} og {d,e} også er hørt af disse og muligvis andre. Desuden synes vi nok ikke, delmængder, der kun er hørt af én, er "hyppige delmængder" og vi er ikke interesserede i delmængder med kun ét element - vi vil jo anbefale noget nyt. Vi reagerer med to tiltag:

  • Vi sætter en minimal længde - lad os sige 2, så kun delmængder med mindst to elementer er med.

  • En minimal support - hvor stor en andel af lytterne skal have denne delmængde til fælles. Her vælger vi 33% - så mindst 3 skal have delmængden fælles.

Tilbage har vi

{a,c} hørt af 1,4,6
{ a,e} hørt af 1,4,7
{b,d} hørt af 2,3,8
{b,e} hørt af 2,3,5,7
{c,d} hørt af 3,4,6,8
{c,e} hørt af 1,3,4
{d,e} hørt af 2,3,4,9
{c,d,e} hørt af 3,4,9

Nu vender vi det lidt om og vil gruppere lytterne/seerne. Vi vil lave clustering baseret på tabellen ovenfor.