Medoid - Medoid

Medoids er representative objekter av et datasett eller en klynge i et datasett hvis sum av ulikheter med alle objektene i klyngen er minimal. Medoids er i prinsippet det samme middel eller sentroidene , men medoids er alltid begrenset til å være medlemmer av datasettet. Medoider brukes oftest på data når et middel eller en centroid ikke kan defineres, for eksempel grafer. De brukes også i sammenhenger der sentroid ikke er representativ for datasettet som i bilder og 3-D-baner og genuttrykk (der mens dataene er sparsomme, trenger medoid ikke være). Disse er også av interesse mens du ønsker å finne en representant som bruker en annen avstand enn kvadratisk euklidisk avstand (for eksempel i filmkarakterer).

For noen datasett kan det være mer enn en medoid, som medianer. En vanlig anvendelse av medoid er k-medoids klyngealgoritme , som ligner k-betyr algoritme, men fungerer når et middel eller centroid ikke kan defineres. Denne algoritmen fungerer i utgangspunktet som følger. Først velges et sett medoids tilfeldig. For det andre beregnes avstandene til de andre punktene. For det tredje er data gruppert i henhold til medoid de ligner mest på. For det fjerde optimaliseres medoid-settet via en iterativ prosess.

Merk at en medoid ikke tilsvarer en median , en geometrisk median eller sentroid . En median er bare definert på 1-dimensjonale data, og det minimerer bare ulikhet med andre punkter for beregninger indusert av en norm (for eksempel Manhattan-avstanden eller euklidisk avstand ). En geometrisk median er definert i en hvilken som helst dimensjon, men er ikke nødvendigvis et punkt fra det opprinnelige datasettet.

Definisjon

La være et sett med punkter i et rom med avstandsfunksjon d. Medoid er definert som ${\ textstyle {\ mathcal {X}}: = \ {x_ {1}, x_ {2}, \ prikker, x_ {n} \}}$${\ textstyle n}$

${\ displaystyle x _ {\ text {medoid}} = \ arg \ min _ {y \ i {\ mathcal {X}}} \ sum _ {i = 1} ^ {n} d (y, x_ {i}) .}$

Algoritmer for å beregne medoider

Fra definisjonen ovenfor er det klart at medoiden kan beregnes etter å ha beregnet alle parvise avstander mellom punkter i ensemblet. Dette vil ta avstandsevalueringer. I verste fall kan man ikke beregne medoid med færre avstandsevalueringer. Imidlertid er det mange tilnærminger som tillater oss å beregne medoider enten nøyaktig eller omtrent i subkvadratisk tid under forskjellige statistiske modeller. ${\ textstyle O (n ^ {2})}$

Hvis punktene ligger på den virkelige linje, beregning av den medoid reduseres for å beregne median som kan gjøres av Quick-velger algoritme av Hoare. Imidlertid er det ingen kjent algoritme i høyere dimensjonale virkelige rom. RAND er en algoritme som estimerer den gjennomsnittlige avstanden til hvert punkt til alle de andre punktene ved å sample en tilfeldig delsett av andre punkter. Det tar totalt avstandsberegninger å tilnærme medoiden innenfor en faktor med høy sannsynlighet, hvor er den maksimale avstanden mellom to punkter i ensemblet. Merk at RAND er en tilnærmelsesalgoritme, og dessuten er det kanskje ikke kjent apriori. ${\ textstyle O (n)}$${\ textstyle O \ left ({\ frac {n \ log n} {\ epsilon ^ {2}}} \ right)}$${\ textstyle (1+ \ epsilon \ Delta)}$${\ textstyle \ Delta}$${\ textstyle \ Delta}$

RAND ble utnyttet av TOPRANK som bruker estimatene innhentet av RAND for å fokusere på en liten delmengde av kandidatpoeng, evaluerer gjennomsnittsavstanden til disse poengene nøyaktig , og velger minimum av disse. TOPRANK trenger avstandsberegninger for å finne den nøyaktige medoiden med høy sannsynlighet under en distribusjonsantakelse på gjennomsnittsavstandene. ${\ textstyle O (n ^ {\ frac {5} {3}} \ log ^ {\ frac {4} {3}} n)}$

trimmet presenterer en algoritme for å finne medoiden med avstandsevalueringer under en distribusjonsantakelse på punktene. Algoritmen bruker trekantulikheten for å kutte ned søkeområdet. ${\ textstyle O (n ^ {\ frac {3} {2}} 2 ^ {\ Theta (d)})}$

Meddit utnytter en forbindelse av medoidberegningen med flerarmede banditter og bruker en øvre tillitsbundet algoritme for å få en algoritme som tar avstandsevalueringer under statistiske forutsetninger på punktene. ${\ textstyle O (n \ log n)}$

Correlated Sequential Halving utnytter også flerarmede bandittteknikker , forbedrer Meddit . Ved å utnytte korrelasjonsstrukturen i problemet, er algoritmen i stand til å beviselig gi drastisk forbedring (vanligvis rundt 1-2 størrelsesordener) i både antall avstandsberegninger og veggklokketid.

Implementeringer

En implementering av RAND , TOPRANK og trimmet finner du her . En implementering av Meddit finner du her og her . En implementering av Correlated Sequential Halving finner du her .

Se også

• k-medoids
• k-betyr algoritme
• Centroid

Referanser