Vzdálenost Kendall tau - Kendall tau distance

The Vzdálenost hodnosti Kendall tau je metrický který počítá počet párových neshod mezi dvěma žebříčky. Čím větší je vzdálenost, tím odlišnější jsou dva seznamy. Také se nazývá vzdálenost Kendall tau vzdálenost třídění bublin protože to odpovídá počtu swapů, které třídění bublin algoritmus by umístil jeden seznam ve stejném pořadí jako druhý seznam. Vzdálenost Kendall tau byla vytvořena Maurice Kendall.

Definice

Vzdálenost mezi dvěma seznamy podle Kendall tau ${displaystyle au _ {1}}$ a ${displaystyle au _ {2}}$ je

{displaystyle K (au _ ​​{1}, au _ {2}) = | {(i, j): i au _ {2} (j)) vee (au _ ​​{1} (i)> au _ {1} (j) wedge au _ {2} (i)

kde

${displaystyle au _ {1} (i)}$ a ${displaystyle au _ {2} (i)}$ jsou hodnocení prvku ${displaystyle i}$ v ${displaystyle au _ {1}}$ a ${displaystyle au _ {2}}$ resp.

${displaystyle K (au _ {1}, au _ {2})}$ bude rovno 0, pokud jsou dva seznamy shodné a ${displaystyle n (n-1) / 2}$ (kde ${displaystyle n}$ je velikost seznamu), pokud je jeden seznam opakem druhého. Vzdálenost Kendall tau se často normalizuje dělením ${displaystyle n (n-1) / 2}$ takže hodnota 1 označuje maximální nesouhlas. Normalizovaná Kendallova tau vzdálenost proto leží v intervalu [0,1].

Vzdálenost Kendall tau může být také definována jako

{displaystyle K (au _ ​​{1}, au _ {2}) = {egin {matrix} součet _ {{i, j} v P} {ar {K}} _ {i, j} (au _ ​​{1 }, au _ {2}) end {matrix}}}

kde

P je sada neuspořádaných párů odlišných prvků v ${displaystyle au _ {1}}$ a ${displaystyle au _ {2}}$
${displaystyle {ar {K}} _ {i, j} (au _ {1}, au _ {2})}$ = 0 pokud i a j jsou ve stejném pořadí v ${displaystyle au _ {1}}$ a ${displaystyle au _ {2}}$
${displaystyle {ar {K}} _ {i, j} (au _ {1}, au _ {2})}$ = 1 pokud i a j jsou v opačném pořadí ${displaystyle au _ {1}}$ a ${displaystyle au _ {2}.}$

Vzdálenost Kendall tau lze také definovat jako celkový počet nesouhlasné páry.

Vzdálenost Kendall tau v žebříčku: Permutace (nebo hodnocení) je pole N celých čísel, kde se každé z celých čísel mezi 0 a N-1 objeví přesně jednou. Kendall tau vzdálenost mezi dvěma žebříčky je počet párů, které jsou v jiném pořadí ve dvou žebříčcích. Například vzdálenost Kendall tau mezi 0 3 1 6 2 5 4 a 1 0 3 6 4 2 5 je čtyři, protože dvojice 0-1, 3-1, 2-4, 5-4 jsou v odlišném pořadí ve dvou žebříčku, ale všechny ostatní páry jsou ve stejném pořadí.^[1]

Pokud je funkce Kendall tau prováděna jako ${displaystyle K (L1, L2)}$ namísto ${displaystyle K (au _ {1}, au _ {2})}$ (kde ${displaystyle au _ {1}}$ a ${displaystyle au _ {2}}$ jsou žebříčky ${displaystyle L1}$ a ${displaystyle L2}$ prvků), pak trojúhelníková nerovnost není zaručena. Trojúhelníková nerovnost selže v případech, kdy se v seznamech opakuje. Takže už se metrikou nezabýváme.

Příklad

Předpokládejme, že jeden řadí skupinu pěti lidí podle výšky a hmotnosti:

Osoba	A	B	C	D	E
Pořadí podle výšky	1	2	3	4	5
Pořadí podle hmotnosti	3	4	1	2	5

Zde je osoba A nejvyšší a třetí nejtěžší atd.

Chcete-li vypočítat vzdálenost Kendall tau, spárujte každou osobu s každou další osobou a spočítejte, kolikrát jsou hodnoty v seznamu 1 v opačném pořadí než hodnoty v seznamu 2.

Pár	Výška	Hmotnost	Počet
(A, B)	1 < 2	3 < 4
(A, C)	1 < 3	3 > 1	X
(INZERÁT)	1 < 4	3 > 2	X
(A, E)	1 < 5	3 < 5
(PŘED NAŠÍM LETOPOČTEM)	2 < 3	4 > 1	X
(B, D)	2 < 4	4 > 2	X
(BÝT)	2 < 5	4 < 5
(CD)	3 < 4	1 < 2
(C, E)	3 < 5	1 < 5
(D, E)	4 < 5	2 < 5

Jelikož existují čtyři páry, jejichž hodnoty jsou v opačném pořadí, vzdálenost Kendall tau je 4. Normalizovaná vzdálenost Kendall tau je

{displaystyle {frac {4} {5 (5-1) / 2}} = 0,4.}

Hodnota 0,4 naznačuje, že 40% párů se liší v pořadí mezi dvěma seznamy.

Výpočet vzdálenosti Kendall tau

Vzhledem ke dvěma hodnocením ${displaystyle au _ {1}, au _ {2}}$ , je možné položky tak přejmenovat ${displaystyle au _ {1} = (1,2,3, ...)}$ . Poté se problém výpočtu vzdálenosti Kendall tau sníží na výpočet počtu inverze v ${displaystyle au _ {2}}$ --- počet indexových párů ${displaystyle i, j}$ takhle ${displaystyle i$ zatímco ${displaystyle au _ {2} (i)> au _ {2} (j)}$ . Existuje několik algoritmů pro výpočet tohoto počtu.

Jednoduchý algoritmus založený na Sloučit třídění vyžaduje čas ${displaystyle O (nlog n)}$ .^[2]
Pokročilejší algoritmus vyžaduje čas ${displaystyle O (n {sqrt {log {n}}})}$ .^[3]

Viz také

Reference

^ http://algs4.cs.princeton.edu/25applications/
^ Ionescu, Vlade. "výpočet počtu" inverzí "v permutaci". Přetečení zásobníku. Citováno 24. února 2017.
^ Chan, Timothy M .; Pătraşcu, Mihai (2010). "Počítání konverzí, offline počítání ortogonálního rozsahu a související problémy". Sborník z dvacátého prvního výročního sympozia ACM-SIAM o diskrétních algoritmech. p. 161. CiteSeerX 10.1.1.208.2715. doi:10.1137/1.9781611973075.15. ISBN 978-0-89871-701-3.

Fagin, R .; Kumar, R .; Sivakumar, D. (2003). Msgstr "Porovnávám nejlepší seznamy k". SIAM Journal on Discrete Mathematics. 17 (1): 134–160. CiteSeerX 10.1.1.86.3234. doi:10.1137 / S0895480102412856.
Kendall, M. (1948). "Metody korelace pořadí". Charles Griffin & Company Limited. Citovat deník vyžaduje | deník = (Pomoc)
Kendall, M. (1938). "Nové měřítko korelace hodností". Biometrika. 30 (1/2): 81–89. doi:10.2307/2332226. JSTOR 2332226.

externí odkazy

Online software: počítá Kendallovu tau korelaci

[1] ttp://algs4.cs.princeton.edu/25applications/

[2] Ionescu, Vlade. "výpočet počtu" inverzí "v permutaci". Přetečení zásobníku. Citováno 24. února 2017.

[3] Chan, Timothy M .; Pătraşcu, Mihai (2010). "Počítání konverzí, offline počítání ortogonálního rozsahu a související problémy". Sborník z dvacátého prvního výročního sympozia ACM-SIAM o diskrétních algoritmech. p. 161. CiteSeerX 10.1.1.208.2715. doi:10.1137/1.9781611973075.15. ISBN 978-0-89871-701-3.

[1]

[2]

[3]