Medoid

Medoider är representativa objekt för en datamängd eller ett kluster inom en datamängd vars summa av olikheter till alla objekt i klustret är minimal. Medoider liknar till begrepp medel eller centroider , men medoider är alltid begränsade till att vara medlemmar i datamängden. Medoider används oftast på data när ett medelvärde eller tyngdpunkt inte kan definieras, såsom grafer. De används också i sammanhang där tyngdpunkten inte är representativ för datamängden som i bilder, 3D-banor och genuttryck (där medan data är sparsam behöver medoiden inte vara). Dessa är också av intresse samtidigt som man vill hitta en representant som använder något annat avstånd än kvadratiskt euklidiskt avstånd (till exempel i filmbetyg).

För vissa datamängder kan det finnas mer än en medoid, som med medianer. En vanlig tillämpning av medoiden är k-medoidernas klustringsalgoritm, som liknar k- medelalgoritmen men fungerar när ett medelvärde eller tyngdpunkt inte är definierbart. Denna algoritm fungerar i princip enligt följande. Först väljs en uppsättning medoider slumpmässigt. För det andra beräknas avstånden till de andra punkterna. För det tredje är data klustrade enligt den medoid de liknar mest. För det fjärde optimeras medoiduppsättningen via en iterativ process.

Observera att en medoid inte är likvärdig med en median , en geometrisk median eller tyngdpunkt . En median definieras endast på 1-dimensionell data, och den minimerar endast olikhet med andra punkter för mått som induceras av en norm (som Manhattan-avståndet eller Euklidiskt avstånd ). En geometrisk median definieras i vilken dimension som helst, men är inte nödvändigtvis en punkt från den ursprungliga datamängden.

Definition

Låt ${\textstyle {\mathcal {X}}:=\{x_{1},x_{2},\dots ,x_{n}\}}$ vara en uppsättning av ${\textstyle n}$ punkter i ett utrymme med en avståndsfunktion d. Medoid definieras som

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

Klustring med Medoids

Huvudartikel: k-medoids

Medoider är en populär ersättning för klustermedelvärdet när avståndsfunktionen inte är (kvadrat) euklidiskt avstånd, eller inte ens ett metriskt (eftersom medoiden inte kräver triangelolikheten). När datauppsättningen partitioneras i kluster kan medoiden för varje kluster användas som en representant för varje kluster.

Klustringsalgoritmer baserade på idén om medoider inkluderar:

• Partitioning Around Medoids (PAM), standard k-medoids algoritm
• Hierarchical Clustering Around Medoids (HACAM), som använder medoider i hierarkisk klustring

Algoritmer för att beräkna medelvärdet för en uppsättning

Från definitionen ovan är det tydligt att medoiden för en mängd ${\mathcal {X}}$ kan beräknas efter att ha beräknat alla parvisa avstånd mellan punkter i ensemblen. Detta skulle ta ${\textstyle O(n^{2})}$ avståndsutvärderingar (med $n=|{\mathcal {X}}|$ ). I värsta fall kan man inte beräkna medoiden med färre avståndsutvärderingar. Det finns dock många tillvägagångssätt som gör att vi kan beräkna medoider antingen exakt eller ungefär i sub-kvadratisk tid under olika statistiska modeller.

Om punkterna ligger på den verkliga linjen, reduceras beräkning av medoiden till beräkning av medianen som kan göras i ${\textstyle O(n)}$ med snabbvalsalgoritmen från Hoare. I högre dimensionella reella utrymmen är dock ingen linjär-tidsalgoritm känd. RAND är en algoritm som uppskattar det genomsnittliga avståndet för varje punkt till alla andra punkter genom att sampla en slumpmässig delmängd av andra punkter. Det krävs totalt ${\textstyle O\left({\frac {n\log n}{\epsilon ^{2}}}\right)}$ avståndsberäkningar för att approximera medoiden inom en faktor på ${\textstyle (1+\epsilon \Delta )}$ med hög sannolikhet, där ${\textstyle \Delta }$ är det maximala avståndet mellan två punkter i ensemblen. Observera att RAND är en approximationsalgoritm, och dessutom kanske ${\textstyle \Delta }$ inte är känd apriori.

RAND utnyttjades av TOPRANK som använder uppskattningarna som erhållits av RAND för att fokusera på en liten delmängd av kandidatpoäng, utvärderar det genomsnittliga avståndet för dessa punkter exakt och väljer minimum av dessa. TOPRANK behöver ${\textstyle O(n^{\frac {5}{3}}\log ^{\frac {4}{3}}n)}$ avståndsberäkningar för att hitta den exakta medoiden med hög sannolikhet under ett fördelningsantagande på medelavstånden.

trimed presenterar en algoritm för att hitta medoiden med ${\textstyle O(n^{\frac {3}{2}}2^{\Theta (d)})}$ avståndsutvärderingar under ett fördelningsantagande på punkterna. Algoritmen använder triangelolikheten för att minska sökutrymmet.

Meddit utnyttjar en koppling av medoidberäkningen med flerarmade banditer och använder en upper-Confidence-bound typ av algoritm för att få en algoritm som tar ${\textstyle O(n\log n)}$ avståndsutvärderingar under statistiska antaganden på punkterna.

Korrelerad sekventiell halvering utnyttjar också flerarmade bandittekniker, vilket förbättrar Meddit . Genom att utnyttja korrelationsstrukturen i problemet kan algoritmen bevisligen ge en drastisk förbättring (vanligtvis runt 1-2 storleksordningar) i både antal avståndsberäkningar som behövs och väggklockans tid.

Genomföranden

En implementering av RAND , TOPRANK och trimed finns här . En implementering av Meddit finns här och här . En implementering av Correlated Sequential Halving finns här .