Geometrický medián - Geometric median - Wikipedia

Příklad geometrický medián (žlutě) řady bodů. V modré barvě Centrum hmoty.

The geometrický medián diskrétní sady vzorkovacích bodů v a Euklidovský prostor je bod minimalizující součet vzdáleností k bodům vzorkování. Tím se zobecňuje medián, který má vlastnost minimalizace součtu vzdáleností pro jednorozměrná data a poskytuje a centrální tendence ve vyšších dimenzích. To je také známé jako 1-medián,^[1] prostorový medián,^[2] Euklidovský minisumový bod,^[2] nebo Torricelliho bod.^[3]

Geometrický medián je důležitý odhadce z umístění ve statistikách,^[4] kde je také známý jako L₁ odhadce.^[5] Je to také standardní problém v umístění zařízení, kde modeluje problém lokalizace zařízení, aby se minimalizovaly náklady na dopravu.^[6]

Zvláštní případ úlohy pro tři body v rovině (tj. m = 3 a n = 2 v níže uvedené definici) je někdy také známý jako Fermatův problém; vzniká při konstrukci minima Steinerovy stromy, a původně byl považován za problém uživatelem Pierre de Fermat a vyřešil Evangelista Torricelli.^[7] Jeho řešení je nyní známé jako Fermatův bod trojúhelníku tvořeného třemi body vzorkování.^[8] Geometrický medián lze zase zobecnit na problém minimalizace součtu vážený vzdálenosti, známé jako Weberův problém po Alfred Weber pojednání o problému v jeho knize o umístění zařízení z roku 1909.^[2] Některé zdroje místo toho nazývají Weberův problém problémem Fermat-Weber,^[9] ale ostatní používají tento název pro nevážený geometrický mediánový problém.^[10]

Wesolowsky (1993) poskytuje přehled geometrického mediánu problému. Vidět Fekete, Mitchell & Beurer (2005) pro zobecnění problému na diskrétní množiny bodů.

Definice

Formálně pro danou sadu m bodů ${ displaystyle x_ {1}, x_ {2}, tečky, x_ {m} ,}$ s každým ${ displaystyle x_ {i} in mathbb {R} ^ {n}}$, geometrický medián je definován jako

${ displaystyle { underset {y in mathbb {R} ^ {n}} { operatorname {arg , min}}} sum _ {i = 1} ^ {m} left | x_ {i } -y doprava | _ {2}}$

Tady, arg min znamená hodnotu argumentu ${ displaystyle y}$ což minimalizuje součet. V tomto případě jde o věc ${ displaystyle y}$ odkud je součet všech Euklidovské vzdálenosti do ${ displaystyle x_ {i}}$je minimální.

Vlastnosti

• U jednorozměrného případu se geometrický medián shoduje s medián. Je to proto, že univariate medián také minimalizuje součet vzdáleností od bodů.^[11]
• Geometrický medián je unikátní kdykoli body nejsou kolineární.^[12]
• Geometrický medián je ekvivariant pro euklidovský transformace podobnosti, počítaje v to překlad a otáčení.^[5][11] To znamená, že by člověk získal stejný výsledek buď transformací geometrického mediánu, nebo aplikací stejné transformace na ukázková data a nalezení geometrického mediánu transformovaných dat. Tato vlastnost vyplývá ze skutečnosti, že geometrický medián je definován pouze z párových vzdáleností a nezávisí na systému ortogonálních Kartézské souřadnice kterým jsou reprezentována ukázková data. Naproti tomu medián jednotlivých komponent pro mnohorozměrný datový soubor není obecně invariantní rotací ani nezávislý na volbě souřadnic.^[5]
• Geometrický medián má a bod poruchy 0,5.^[5] To znamená, že až polovina údajů o vzorku může být libovolně poškozena a medián vzorků bude i nadále poskytovat robustní odhad pro umístění nepoškozených dat.

Speciální případy

• Pro 3 (ne-kolineární ) body, pokud je jakýkoli úhel trojúhelníku tvořeného těmito body 120 ° nebo více, pak geometrický medián je bod na vrcholu tohoto úhlu. Pokud jsou všechny úhly menší než 120 °, je geometrickým středem bod uvnitř trojúhelníku, který svírá úhel 120 ° s každým třem párem vrcholů trojúhelníku.^[11] Toto je také známé jako Fermatův bod trojúhelníku tvořeného třemi vrcholy. (Pokud jsou tři body kolineární, pak geometrický medián je bod mezi dvěma dalšími body, jako je tomu u jednorozměrného mediánu.)
• Pro 4 koplanární body, pokud je jeden ze čtyř bodů uvnitř trojúhelníku tvořeného dalšími třemi body, pak geometrický medián je tento bod. Jinak čtyři body tvoří konvexní čtyřúhelník a geometrický medián je bodem křížení úhlopříček čtyřúhelníku. Geometrický medián čtyř koplanárních bodů je stejný jako jedinečný Radonový bod ze čtyř bodů.^[13]

Výpočet

Navzdory tomu, že geometrický medián je snadno srozumitelný koncept, výpočet představuje výzvu. The těžiště nebo těžiště, definovaný podobně jako geometrický medián jako minimalizace součtu čtverce vzdáleností ke každému bodu lze zjistit pomocí jednoduchého vzorce - jeho souřadnice jsou průměrem souřadnic bodů - ale ukázalo se, že žádný explicitní vzorec, ani přesný algoritmus zahrnující pouze aritmetické operace a kth kořeny, mohou existovat obecně pro geometrický medián. Proto jsou v tomto rámci možné pouze numerické nebo symbolické aproximace řešení tohoto problému model výpočtu.^[14]

Je však jednoduché vypočítat aproximaci geometrického mediánu pomocí iteračního postupu, při kterém každý krok vytvoří přesnější aproximaci. Postupy tohoto typu lze odvodit ze skutečnosti, že součet vzdáleností k bodům odběru je a konvexní funkce, protože vzdálenost do každého vzorkovaného bodu je konvexní a součet konvexních funkcí zůstává konvexní. Proto postupy, které snižují součet vzdáleností v každém kroku, nemohou být zachyceny v a místní optimum.

Jeden společný přístup tohoto typu, tzv Weiszfeldův algoritmus po práci Endre Weiszfeld,^[15] je forma iterativně znovu zváženo nejméně čtverců. Tento algoritmus definuje množinu vah, které jsou nepřímo úměrné vzdálenostem od aktuálního odhadu k bodům vzorkování, a vytváří nový odhad, který je váženým průměrem vzorku podle těchto vah. To znamená

${ displaystyle left.y_ {i + 1} = left ( sum _ {j = 1} ^ {m} { frac {x_ {j}} { | x_ {j} -y_ {i} |}} right) right / left ( sum _ {j = 1} ^ {m} { frac {1} { | x_ {j} -y_ {i} |}} right). }$

Tato metoda konverguje téměř ke všem počátečním pozicím, ale nemusí konvergovat, když jeden z jejích odhadů spadne na jeden z daných bodů. Může být upraven tak, aby zvládl tyto případy tak, aby konvergoval pro všechny počáteční body.^[12]

Bose, Maheshwari & Morin (2003) popsat složitější postupy geometrické optimalizace pro nalezení přibližně optimálního řešení tohoto problému. Tak jako Nie, Parrilo & Sturmfels (2008) ukázat, problém lze také vyjádřit jako a semidefinitní program.

Cohen a kol. (2016) ukázat, jak vypočítat geometrický medián s libovolnou přesností téměř lineární čas.

Charakterizace geometrického mediánu

Li y je odlišný od všech daných bodů, X_j, pak y je geometrický medián, jen když splňuje:

${ displaystyle 0 = sum _ {j = 1} ^ {m} { frac {x_ {j} -y} { left | x_ {j} -y right |}}.}$

To odpovídá:

${ displaystyle left.y = left ( sum _ {j = 1} ^ {m} { frac {x_ {j}} { | x_ {j} -y |}} right) right / left ( sum _ {j = 1} ^ {m} { frac {1} { | x_ {j} -y |}} right),}$

což úzce souvisí s Weiszfeldovým algoritmem.

Obecně, y je geometrický medián právě tehdy, pokud existují vektory u_j takové, že:

${ displaystyle 0 = součet _ {j = 1} ^ {m} u_ {j}}$

kde pro X_j ≠ y,

${ displaystyle u_ {j} = { frac {x_ {j} -y} { vlevo | x_ {j} -y vpravo |}}}$

a pro X_j = y,

${ displaystyle | u_ {j} | leq 1.}$

Ekvivalentní formulace tohoto stavu je

${ displaystyle sum _ {1 leq j leq m, x_ {j} neq y} { frac {x_ {j} -y} { left | x_ {j} -y right |} } leq left | {, j mid 1 leq j leq m, x_ {j} = y , } vpravo |.}$

Lze jej chápat jako zevšeobecnění mediánové vlastnosti v tom smyslu, že jakékoli rozdělení bodů, zejména vyvolané jakoukoli nadrovinou prostřednictvím y, má stejný a opačný součet kladných hodnot Pokyny z y na každé straně. V jednorozměrném případě je hyperplánem bod y sama o sobě a součet směrů se zjednodušuje na (směrovanou) míru počítání.

Zobecnění

Geometrický medián lze zobecnit z euklidovských prostorů na obecné Riemannovy rozdělovače (a dokonce metrické prostory ) používající stejnou myšlenku, která se používá k definování Fréchet znamená na Riemannově potrubí.^[16] Nechat ${ displaystyle M}$ být Riemannovo potrubí s odpovídající funkcí vzdálenosti ${ displaystyle d ( cdot, cdot)}$, nechť ${ displaystyle w_ {1}, ldots, w_ {n}}$ být ${ displaystyle n}$ závaží se součtem 1, a nechat ${ displaystyle x_ {1}, ldots, x_ {n}}$být ${ displaystyle n}$ pozorování od ${ displaystyle M}$. Poté definujeme vážený geometrický medián ${ displaystyle m}$ (nebo vážený Fréchetův medián) datových bodů jako

${ displaystyle m = { underset {x in M} { operatorname {arg , min}}} sum _ {i = 1} ^ {n} w_ {i} d (x, x_ {i}) }$.

Pokud jsou všechny váhy stejné, řekneme to jednoduše ${ displaystyle m}$ je geometrický medián.

Viz také

• Medoid
• Geometrická střední absolutní odchylka

Poznámky

Reference