Medoid - Medoid

Medoidele sunt obiecte reprezentative ale unui set de date sau al unui cluster dintr-un set de date a căror sumă de diferențe față de toate obiectele din cluster este minimă. Medoidele sunt similare în concepție cu mijloacele sau centroizii , dar medoidele sunt întotdeauna restricționate să fie membre ale setului de date. Medoidele sunt cel mai frecvent utilizate pe date atunci când nu se poate defini o medie sau un centroid, cum ar fi graficele. Ele sunt, de asemenea, utilizate în contexte în care centroidul nu este reprezentativ pentru setul de date, cum ar fi în imagini și traiectorii 3D și expresia genelor (în timp ce datele sunt rare, medoidul nu trebuie să fie). Acestea sunt, de asemenea, de interes, în timp ce doresc să găsească un reprezentant folosind o altă distanță decât distanța euclidiană pătrată (de exemplu, în evaluările filmelor).

Pentru unele seturi de date poate exista mai mult de un medoid, ca și în cazul medianelor. O aplicație obișnuită a medoidului este algoritmul de grupare k-medoid , care este similar cu algoritmul k-mijloace , dar funcționează atunci când o medie sau un centru nu este definibil. Acest algoritm funcționează practic după cum urmează. În primul rând, un set de medoizi este ales la întâmplare. În al doilea rând, se calculează distanțele față de celelalte puncte. În al treilea rând, datele sunt grupate în funcție de medoidul cu care sunt cele mai asemănătoare. În al patrulea rând, setul medoid este optimizat printr-un proces iterativ.

Rețineți că un medoid nu este echivalent cu o mediană , o mediană geometrică sau un centroid . O mediană este definită numai pe date unidimensionale și minimizează diferențierea față de alte puncte pentru metricele induse de o normă (cum ar fi distanța Manhattan sau distanța euclidiană ). O mediană geometrică este definită în orice dimensiune, dar nu este neapărat un punct din setul de date original.

Definiție

Fie un set de puncte dintr-un spațiu cu funcția de distanță d. Medoidul este definit ca ${\ textstyle {\ mathcal {X}}: = \ {x_ {1}, x_ {2}, \ dots, x_ {n} \}}$${\ textstyle n}$

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

Algoritmi pentru calcularea medoizilor

Din definiția de mai sus, este clar că medoidul poate fi calculat după calcularea tuturor distanțelor perechi între punctele din ansamblu. Acest lucru ar necesita evaluări la distanță. În cel mai rău caz, nu se poate calcula medoidul cu mai puține evaluări la distanță. Cu toate acestea, există multe abordări care ne permit să calculăm medoizii fie exact, fie aproximativ în timp subcadratic sub diferite modele statistice. ${\ textstyle O (n ^ {2})}$

Dacă punctele se află pe linia reală, calculul medoidului se reduce la calculul medianei care poate fi realizat prin algoritmul de selectare rapidă al lui Hoare. Cu toate acestea, în spații reale cu dimensiuni superioare, nu se cunoaște niciun algoritm în timp liniar. RAND este un algoritm care estimează distanța medie a fiecărui punct la toate celelalte puncte prin eșantionarea unui subset aleatoriu de alte puncte. Este nevoie de un număr total de calcule ale distanței pentru a aproxima medoidul într-un factor cu probabilitate mare, unde este distanța maximă dintre două puncte din ansamblu. Rețineți că RAND este un algoritm de aproximare și, în plus, este posibil să nu fie cunoscut în apriori. ${\ textstyle O (n)}$${\ textstyle O \ left ({\ frac {n \ log n} {\ epsilon ^ {2}}} \ right)}$${\ textstyle (1+ \ epsilon \ Delta)}$${\ textstyle \ Delta}$${\ textstyle \ Delta}$

RAND a fost valorificat de TOPRANK, care folosește estimările obținute de RAND pentru a se concentra pe un subset mic de puncte candidate, evaluează exact distanța medie a acestor puncte și alege minimul dintre acestea. TOPRANK are nevoie de calcule la distanță pentru a găsi medoidul exact cu probabilitate mare sub o presupunere de distribuție a distanțelor medii. ${\ textstyle O (n ^ {\ frac {5} {3}} \ log ^ {\ frac {4} {3}} n)}$

trimed prezintă un algoritm pentru a găsi medoidul cu evaluări de distanță sub o ipoteză de distribuție pe puncte. Algoritmul folosește inegalitatea triunghiului pentru a reduce spațiul de căutare. ${\ textstyle O (n ^ {\ frac {3} {2}} 2 ^ {\ Theta (d)})}$

Meddit folosește o conexiune a calculului medoid cu bandiți multi-înarmați și folosește un tip de algoritm de încredere superioară pentru a obține un algoritm care efectuează evaluări de distanță în conformitate cu ipotezele statistice ale punctelor. ${\ textstyle O (n \ log n)}$

Înjumătățirea secvențială corelată folosește, de asemenea, tehnici de bandiți multi-armate, îmbunătățind Meddit . Prin exploatarea structurii de corelație din problemă, algoritmul este capabil să obțină o îmbunătățire drastică (de obicei în jur de 1-2 ordine de mărime) atât în ​​numărul de calcule de distanță necesare, cât și în timpul ceasului de perete.

Implementări

O implementare a RAND , TOPRANK și trimed poate fi găsită aici . O implementare a Meddit poate fi găsită aici și aici . O implementare a înjumătățirii secvențiale corelate poate fi găsită aici .

Vezi si

• k-medoizi
• k-înseamnă algoritm
• Centroid

Referințe