Kendall tau mesafesi - Kendall tau distance

Kendall tau sıra mesafesi bir metrik bu, iki sıralama listesi arasındaki ikili anlaşmazlıkların sayısını sayar. Mesafe ne kadar büyükse, iki liste o kadar farklı olur. Kendall tau mesafesi de denir kabarcık sıralama mesafesi takas sayısına eşit olduğundan kabarcık sıralama algoritması, bir listeyi diğer listeyle aynı sıraya yerleştirir. Kendall tau mesafesi Maurice Kendall.

Tanım

İki liste arasındaki Kendall tau sıralama mesafesi ve dır-dir

nerede

  • ve elementin sıralaması içinde ve sırasıyla.

iki liste aynıysa 0'a eşit olacaktır ve (nerede liste boyutudur) eğer bir liste diğerinin tersiyse. Genellikle Kendall tau mesafesi şuna bölünerek normalleştirilir: dolayısıyla 1 değeri maksimum anlaşmazlığı gösterir. Dolayısıyla normalize edilmiş Kendall tau mesafesi [0,1] aralığında yer alır.

Kendall tau mesafesi şu şekilde de tanımlanabilir:

nerede

  • P sıralanmamış farklı eleman çiftleri kümesidir. ve
  • = 0 eğer ben ve j aynı sırada ve
  • = 1 eğer ben ve j ters sırada ve

Kendall tau mesafesi ayrıca toplam sayı olarak da tanımlanabilir. uyumsuz çiftler.

Sıralamalarda Kendall tau mesafesi: Bir permütasyon (veya sıralama), 0 ile N-1 arasındaki tam sayıların her birinin tam olarak bir kez göründüğü N tam sayı dizisidir. İki sıralama arasındaki Kendall tau mesafesi, farklı sıradaki çiftlerin sayısıdır iki sıralamada. Örneğin, 0 3 1 6 2 5 4 ve 1 0 3 6 4 2 5 arasındaki Kendall tau mesafesi dörttür, çünkü 0-1, 3-1, 2-4, 5-4 çiftleri, ikisinde farklı sıradadır. sıralamalar, ancak diğer tüm çiftler aynı sıradadır.[1]

Kendall tau işlevi şu şekilde gerçekleştirilirse onun yerine (nerede ve sıralaması ve sırasıyla), bu durumda üçgen eşitsizlik garanti edilmez. Listelerde tekrarların olduğu durumlarda üçgen eşitsizlik başarısız olur. Öyleyse artık bir metrikle uğraşmıyoruz.

Misal

Birinin boyuna ve ağırlığına göre beş kişilik bir grup sıraladığını varsayalım:

KişiBirBCDE
Yüksekliğe göre sıralama12345
Ağırlığa göre sıralama34125

Burada A kişisi en uzun ve üçüncü en ağırdır, vb.

Kendall tau mesafesini hesaplamak için, her kişiyi diğer kişilerle eşleştirin ve liste 1'deki değerlerin liste 2'deki değerlerin tersi sırasına göre kaç kez olduğunu sayın.

ÇiftYükseklikAğırlıkMiktar
(A, B)1 < 23 < 4
(AC)1 < 33 > 1X
(A, D)1 < 43 > 2X
(A, E)1 < 53 < 5
(M.Ö)2 < 34 > 1X
(B, D)2 < 44 > 2X
(B, E)2 < 54 < 5
(CD)3 < 41 < 2
(C, E)3 < 51 < 5
(D, E)4 < 52 < 5

Değerleri ters sırada olan dört çift olduğu için Kendall tau mesafesi 4'tür. Normalize edilmiş Kendall tau mesafesi

0,4 değeri, iki liste arasındaki sıralamada çiftlerin% 40'ının farklı olduğunu gösterir.

Kendall tau mesafesini hesaplama

İki sıralama verildiğinde , öğeleri şu şekilde yeniden adlandırmak mümkündür: . Daha sonra, Kendall tau mesafesini hesaplama sorunu, sayıları hesaplamaya indirgenir. ters çevirmeler içinde --- dizin çifti sayısı öyle ki süre . Bu sayıyı hesaplamak için birkaç algoritma vardır.

  • Dayalı basit bir algoritma sıralamayı birleştir zaman gerektirir .[2]
  • Daha gelişmiş bir algoritma zaman gerektirir .[3]

Ayrıca bakınız

Referanslar

  1. ^ http://algs4.cs.princeton.edu/25applications/
  2. ^ Ionescu, Vlad. "bir permütasyondaki" inversiyonların "sayısının hesaplanması". Yığın taşması. Alındı 24 Şubat 2017.
  3. ^ Chan, Timothy M .; Pătraşcu, Mihai (2010). "Ters Çevirmeleri Sayma, Çevrimdışı Ortogonal Aralık Sayma ve İlgili Sorunlar". Yirmi Birinci Yıllık ACM-SIAM Sempozyumu Kesikli Algoritmalar Bildirileri. s. 161. CiteSeerX  10.1.1.208.2715. doi:10.1137/1.9781611973075.15. ISBN  978-0-89871-701-3.

Dış bağlantılar