Medcouple - Medcouple
v statistika, medcouple je robustní statistika který měří šikmost a jednorozměrná distribuce.[1] Je definován jako zmenšený mediánový rozdíl levé a pravé poloviny distribuce. Díky své robustnosti je vhodný pro identifikaci odlehlé hodnoty v upravené boxploty.[2][3] Obyčejný krabicové grafy nedopadají dobře se zkosenými distribucemi, protože označují delší nesymetrické ocasy jako odlehlé hodnoty. Pomocí medcouple mohou být whiskery boxplot upraveny pro zkosené distribuce a mají tak přesnější identifikaci odlehlých hodnot pro nesymetrické distribuce.
Jako druh statistika objednávky, medcouple patří do třídy neúplných generalizovaných L-statistiky.[1] Jako obyčejný medián nebo znamenat, medcouple je a neparametrická statistika, lze jej tedy vypočítat pro jakoukoli distribuci.
Definice
Za účelem harmonizace s nulové indexování v mnoha programovacích jazycích budeme indexovat od nuly ve všem, co následuje.
Nechat být objednaným vzorkem velikosti a nechte být medián z . Definujte sady
- ,
- ,
velikostí a resp. Pro a , definujeme funkce jádra
kde je znaková funkce.
The medcouple je pak medián množiny[1]:998
- .
Jinými slovy, rozdělíme rozdělení na všechny hodnoty větší nebo rovné mediánu a všechny hodnoty menší nebo rovné mediánu. Definujeme funkci jádra, jehož první proměnná je nad větší hodnoty a jejichž druhá proměnná je nad nižší hodnoty. Pro speciální případ hodnot vázaných na medián definujeme jádro pomocí funkce signum. Medcouple je pak mediánem nad všemi hodnoty .
Protože medcouple není medián aplikovaný na všechny páry, ale pouze pro ty, pro které , patří do třídy neúplných zobecněných L-statistiky.[1]:998
Vlastnosti medcouple
Medcouple má řadu žádoucích vlastností. Několik z nich je přímo zděděno z funkce jádra.
Jádro medcouple
O funkci jádra provádíme následující pozorování :
- Funkce jádra je invariantní k umístění.[1]:999 Pokud přidáme nebo odečteme jakoukoli hodnotu ke každému prvku vzorku , odpovídající hodnoty funkce jádra se nemění.
- Funkce jádra je neměnná.[1]:999 Stejné měřítko všech prvků vzorku nemění hodnoty funkce jádra.
Tyto vlastnosti jsou zase zděděny medcouple. Medcouple je tedy nezávislý na znamenat a standardní odchylka distribuce, žádoucí vlastnost pro měření šikmost.Pro usnadnění výpočtu nám tyto vlastnosti umožňují definovat dvě sady
kde . To dělá sadu mít rozsah maximálně 1, medián 0, a zachovat stejný medcouple jako .
Pro , jádro medcouple se redukuje na
Používání poslední červené a změněné sady můžeme pozorovat následující.
- Funkce jádra je mezi -1 a 1,[1]:998 to je . To vyplývá z nerovnost obráceného trojúhelníku s a a skutečnost, že .
- Jádro medcouple je neklesající v každé proměnné.[1]:1005 To lze ověřit částečnými derivacemi a , oba nezáporné, protože .
S vlastnostmi 1, 2 a 4 tak můžeme definovat následující matice,
Pokud setřídíme sady a v sestupném pořadí pak matice má seřazené řádky a seřazené sloupce,[1]:1006
Medcouple je pak medián této matice s seřazenými řádky a seřazenými sloupci. Skutečnost, že řádky a sloupce jsou seřazeny, umožňuje implementaci a rychlý algoritmus pro výpočet medcouple.
Robustnost
The bod poruchy je počet hodnot, kterým může statistika odolat, než se stane bezvýznamným, tj. počet libovolně velkých odlehlých hodnot, kterým datová sada může mít, než bude ovlivněna hodnota statistiky. Pro medcouple je bod poruchy 25%, protože se jedná o medián převzatý páry takhle .[1]:1002
Hodnoty
Jako všechna opatření šikmost, medcouple je pozitivní pro distribuce, které jsou zkosené doprava, negativní pro distribuce zkosené doleva, a nula pro symetrické distribuce. Kromě toho jsou hodnoty medcouple omezeny 1 v absolutní hodnotě.[1]:998
Algoritmy pro výpočet medcouple
Před představením algoritmů medcouple si uvědomíme, že existují algoritmy pro nalezení mediánu. Protože medcouple je medián, jsou důležité běžné algoritmy pro nalezení mediánu.
Naivní algoritmus
Naivní algoritmus pro výpočet medcouple je pomalý.[1]:1005 Postupuje ve dvou krocích. Nejprve vytvoří matici medcouple který obsahuje všechny možné hodnoty jádra medcouple. Ve druhém kroku najde medián této matice. Protože tam jsou položky v matici v případě, že jsou všechny prvky datové sady jsou jedinečné, algoritmická složitost naivního algoritmu je .
Přesněji řečeno, naivní algoritmus probíhá následovně. Připomeňme, že používáme nulové indexování.
funkce naïve_medcouple (vektor X): // X je vektor o velikosti n. // Řazení v sestupném pořadí lze provádět na místě v čase O (n log n) sort_decreasing (X) xm: = medián (X) xscale: = 2 * max (abs (X)) // Definujte horní a dolní vystředěné a změněné vektory // zdědí X vlastní klesající třídění Zplus: = [(x - xm) / xscale | X v X takhle x> = xm] Zminus: = [(x - xm) / xscale | X v X takhle x <= xm] p: = velikost (Zplus) q: = velikost (Zminus) // Definujte funkci jádra zavírání nad Zplusem a Zminusem funkce h (i, j): a: = Zplus [i] b: = Zminus [j] -li a == b: vrátit se signum (p - 1 - i - j) jiný: vrátit se (a + b) / (a - b) endif koncová funkce // O (n ^ 2) operace nutné k vytvoření tohoto vektoru H: = [h (i, j) | i v [0, 1, ..., p - 1] a j v [0, 1, ..., q - 1]] vrátit se medián (H)koncová funkce
Poslední volání medián na vektoru velikosti lze provést sám v operace, proto je celý naivní algoritmus medcouple stejné složitosti.
Rychlý algoritmus
Rychlý algoritmus překonává naivní algoritmus využíváním tříděné povahy matice medcouple . Místo výpočtu všech záznamů matice používá rychlý algoritmus K.th párový algoritmus Johnson & Mizoguchi.[4]
První fáze rychlého algoritmu probíhá jako naivní algoritmus. Nejprve spočítáme potřebné přísady pro matici jádra, s seřazenými řádky a seřazenými sloupci v sestupném pořadí. Spíše než počítat všechny hodnoty místo toho využíváme monotónnost v řádcích a sloupcích pomocí následujících pozorování.
Porovnání hodnoty s maticí jádra
Nejprve si všimneme, že můžeme porovnat libovolné se všemi hodnotami z v čas.[4]:150 Například pro určení všech a takhle , máme následující funkci:
funkce větší_h(jádro h, int str, int q, nemovitý u): // h je funkce jádra, h (i, j) dává i-tý, j-tý záznam H // p a q je počet řádků a sloupců matice jádra H // vektor velikosti p P := vektor(str) // indexování od nuly j := 0 // počínaje zdola vypočítat [[supremum | nejmenší horní mez]] pro každý řádek pro i := str - 1, str - 2, ..., 1, 0: // prohledejte tento řádek, dokud nenajdeme hodnotu menší než u zatímco j < q a h(i, j) > u: j := j + 1 nekonečně // položka předcházející té, kterou jsme právě našli, je větší než u P[i] := j - 1 konec vrátit se P koncová funkce
Tento větší_h funkce prochází maticí jádra zleva dole vpravo nahoře a vrací vektor indexů, které označují pro každý řádek, kde hranice leží mezi hodnotami většími než a ti menší nebo rovni . Tato metoda funguje kvůli tříděné vlastnosti řádek-sloupec . Od té doby větší_h počítá nanejvýš hodnoty , jeho složitost je .[4]:150
Koncepčně výsledek vektor lze vizualizovat jako stanovení hranice na matici, jak navrhuje následující diagram, kde jsou všechny červené položky větší než :
Symetrický algoritmus pro výpočet hodnot méně než je velmi podobný. Místo toho postupuje dál v opačném směru, zprava nahoře dole dole:
funkce less_h(jádro h, int str, int q, nemovitý u): // vektor velikosti p Q := vektor(str) // poslední možný index řádků j := q - 1 // počínaje od horního rohu spočítáme [[infimum | největší dolní mez]] pro každý řádek pro i := 0, 1, ..., str - 2, str - 1: // prohledejte tento řádek, dokud nenajdeme hodnotu větší než u zatímco j >= 0 a h(i, j) < u: j := j - 1 nekonečně // položka následující po té, kterou jsme právě našli, je menší než u Q[i] := j + 1 konec vrátit se Q koncová funkce
Tuto dolní hranici lze vizualizovat tak, že modré položky jsou menší než :
Pro každého , máme to , přičemž k přísné nerovnosti dochází pouze u těch řádků, které mají stejné hodnoty .
Máme také ty částky
uveďte počet prvků které jsou větší než a počet prvků, které jsou větší nebo rovny . Tato metoda tedy také poskytuje hodnost z uvnitř prvků z .[4]:149
Vážený medián průměrů řádků
Druhým pozorováním je, že můžeme použít seřazenou maticovou strukturu k okamžitému porovnání libovolného prvku s alespoň polovinou položek v matici. Například medián průměrů řádků napříč celou maticí je menší než červený levý horní kvadrant, ale větší než modrý pravý dolní kvadrant:
Obecněji řečeno, s využitím hranic daných a vektory z předchozí části, můžeme předpokládat, že po několika iteracích jsme určili polohu medcouple tak, aby ležela mezi červenou levou hranicí a modrou pravou hranicí:[4]:149
Žluté položky označují medián každého řádku. Pokud mentálně znovu uspořádáme řádky tak, aby se mediány zarovnaly a ignorovaly vyřazené položky mimo hranice,
můžeme vybrat a vážený medián z těchto mediánů, přičemž každý záznam je vážen počtem zbývajících záznamů v tomto řádku. Tím je zajištěno, že můžeme zahodit alespoň 1/4 všech zbývajících hodnot bez ohledu na to, zda musíme zahodit větší hodnoty červeně nebo menší hodnoty modře:
Medián každého řádku lze vypočítat čas, protože řádky jsou seřazeny, a vážený medián lze vypočítat v času pomocí binárního vyhledávání.[4]:148
K.th párový algoritmus
Spojením těchto dvou pozorování postupuje rychlý algoritmus medcouple zhruba následovně.[4]:148
- Vypočítejte nezbytné přísady pro funkci jádra medcouple s seřazené řádky a seřazené sloupce.
- Při každé iteraci aproximujte medcouple s vážený medián mediánů řádků.[4]:148
- Porovnejte tento předběžný odhad s celou maticí a získáte pravý a levý hraniční vektor a resp. Součet těchto vektorů nám také dává hodnost tohoto předběžného medcouple.
- Pokud je hodnost předběžného medcouple přesně , pak přestaň. Našli jsme medcouple.
- V opačném případě zahoďte položky větší nebo menší než předběžný odhad výběrem jedné z těchto možností nebo jako nová pravá nebo levá hranice, podle toho, na které straně je prvek hodnosti je dovnitř. Tento krok vždy zahodí alespoň 1/4 všech zbývajících položek.
- Jakmile je počet kandidátů na medcouples mezi pravou a levou hranicí menší nebo roven , proveďte a výběr pořadí mezi zbývajícími položkami tak, aby hodnost v této menší sadě kandidátů odpovídala hodnost medcouple v celé matici.
Počáteční třídění za účelem vytvoření funkce trvá čas. Při každé iteraci se použije vážený medián času, stejně jako výpočty nového pokusu a levá a pravá hranice. Jelikož každá iterace odhodí alespoň 1/4 všech zbývajících položek, bude jich nanejvýš iterace.[4]:150 Celý rychlý algoritmus tedy trvá čas.[4]:150
Pojďme přepracovat rychlý algoritmus podrobněji.
funkce medcouple (vektor X): // X je vektor o velikosti n // Počítejte počáteční přísady jako pro naivní medcouple sort_decreasing (X) xm: = medián (X) xscale: = 2 * max (abs (X)) Zplus: = [(x - xm) / xscale | X v X takhle x> = xm] Zminus: = [(x - xm) / xscale | X v X takhle x <= xm] p: = velikost (Zplus) q: = velikost (Zminus) funkce h (i, j): a: = Zplus [i] b: = Zminus [j] -li a == b: vrátit se signum (p - 1 - i - j) jiný: vrátit se (a + b) / (a - b) endif koncová funkce // Zahájení algoritmu párů Kth (Johnson & Mizoguchi) // Počáteční levé a pravé hranice, dva vektory velikosti p L: = [0, 0, ..., 0] R: = [q - 1, q - 1, ..., q - 1] // počet záznamů nalevo od levé hranice Celkem: = 0 // počet záznamů nalevo od pravé hranice Rtotal: = p * q // Protože indexujeme od nuly, index medcouple je jeden // menší než jeho hodnost. medcouple_index: = podlaha (Rtotal / 2) // Iterujte, zatímco počet záznamů mezi hranicemi je // větší než počet řádků v matici. zatímco Rtotal - Ltotal> p: // Vypočítat střední řádky a jejich přidružené váhy, ale přeskočit // všechny řádky, které jsou již prázdné. middle_idx: = [i | i v [0, 1, ..., p - 1] takový že L [i] <= R [i]] row_medians: = [h (i, podlaha ((L [i] + R [i]) / 2) | i v middle_idx] váhy: = [R [i] - L [i] + 1 | i v middle_idx] WM: = vážený medián (row_medians, váhy) // Nové předběžné pravé a levé hranice P: = větší_h (h, p, q, WM) Q: = less_h (h, p, q, WM) Ptotal: = součet (P) + velikost (P) Qcelkem: = součet (Q) // Určete, které položky chcete zahodit, nebo zda jsme našli medcouple -li medcouple_index <= Ptotal - 1: R: = P Rtotal: = Ptotal jiný: -li medcouple_index> Qtotal - 1: L: = Q Ltotal: = Qtotal jiný: // Nalezeno medcouple, pozice váženého mediánu se rovná indexu medcouple vrátit se WM endif endif nekonečně // Nenašel jsem medcouple, ale zbývá jen velmi málo nezávazných záznamů: = [h (i, j) | i v [0, 1, ..., p - 1], j v [L [i], L [i] + 1, ..., R [i]] takový že L [i] <= R [i]] // Vyberte medcouple podle pořadí mezi zbývajícími položkami medcouple: = select_nth (zbývající, medcouple_index - Ltotal) vrátit se medcouplekoncová funkce
Při použití v reálném světě musí algoritmus také počítat s chybami vyplývajícími z konečné přesnosti aritmetika s plovoucí desetinnou čárkou. Například srovnání funkce jádra medcouple by mělo být provedeno uvnitř stroj epsilon, stejně jako srovnání objednávek v the větší_h a less_h funkce.
Software / zdrojový kód
- Algoritmus rychlého medcouple je implementován v R je balíček robustbase.
- Algoritmus rychlého medcouple je implementován v rozšíření C pro Python v Balíček Robustats Python.
- GPL C ++ provádění rychlý algoritmus, odvozené od implementace R.
- A Stata provádění rychlý algoritmus.
- Implementace naivní algoritmus v Matlab (a tedy GNU oktáva ).
- Naivní algoritmus je implementován také pro Krajta balík statsmodels.
Viz také
Reference
- ^ A b C d E F G h i j k l Brys, G .; Hubert, M.; Struyf, A. (listopad 2004). "Robustní míra šikmosti". Journal of Computational and Graphical Statistics. 13 (4): 996–1017. doi:10.1198 / 106186004X12632. PAN 2425170.
- ^ Hubert, M .; Vandervieren, E. (2008). Msgstr "Upravený boxplot pro šikmé distribuce". Výpočetní statistika a analýza dat. 52 (12): 5186–5201. doi:10.1016 / j.csda.2007.11.008. PAN 2526585.
- ^ Pearson, Ron (6. února 2011). „Boxplots and Beyond - Part II: Asymetry“. ExploringDataBlog. Citováno 6. dubna 2015.
- ^ A b C d E F G h i j Johnson, Donald B.; Mizoguchi, Tetsuo (květen 1978). "Výběr K.th prvek v X + Y a X1 + X2 +...+ Xm". SIAM Journal on Computing. 7 (2): 147–153. doi:10.1137/0207013. PAN 0502214.