Verwendung von Kendall's Tau zum Vergleich von Empfehlungen

Kendalls Tau ist eine Metrik, mit der Sie die Reihenfolge zweier Listen vergleichen können. Sie ist nur definiert, wenn beide Listen genau die gleichen Elemente enthalten. Wenn Sie nur einen Teil zweier Listen vergleichen, z.B. die Top-5-Elemente von zwei Empfehlungsgebern, kann es nicht verwendet werden, da es unwahrscheinlich ist, dass diese nur gemeinsame Elemente enthalten. Mit ein paar Tricks kann man jedoch den Kendall tau nutzen, um solche Listen zu vergleichen.

Intro

Der Kendall-Tau ist eine Metrik, mit der Sie die Reihenfolge zweier Ränge vergleichen können. Er nimmt zwei Ränge, die die gleichen Elemente enthalten, und berechnet die Korrelation zwischen ihnen. Eine Korrelation von +1 bedeutet, dass die Ränge gleich sind, während eine Korrelation von -1 bedeutet, dass die Ränge genau das Gegenteil voneinander sind. Wenn zwei Ränge unabhängig voneinander sind oder zufällig gemischt werden, ist die Korrelation im Durchschnitt gleich Null.

Der Kendall-Tau ist undefiniert, wenn die beiden Ränge nicht genau dieselben Elemente enthalten. Wenn Sie alsoRänge vergleichen möchten, die nicht unbedingt die gleichen Elemente enthalten, müssen Sie sich anderweitig umsehen. Dasselbe gilt, wenn Sie nur Teile (z.B. die 10 höchsten Einträge) von Rängen vergleichen wollen, da diese wahrscheinlich nicht die gleichen Elemente enthalten.

Im Folgenden erkläre ich Ihnen, wie Sie mit ein paar Tricks Kendalls Tau für den Vergleich von Rängen verwenden können, die nicht notwendigerweise dieselben Elemente enthalten. Am Ende habe ich eine Python-Implementierung bereitgestellt, mit der Sie in wenigen Minuten zum Laufen bringen sollten.

Anwendungsfall

Warum sollten Sie also zwei Ränge vergleichen wollen, die nicht dieselben Elemente enthalten?

Sie können an einem Teil einer Rangliste interessiert sein, z.B. an den Top-10-Elementen. Ein Beispiel für einen solchen Fall ist die Ausgabe eines Empfehlungsprogramms: Das Empfehlungsprogramm liefert Ihnen eine Rangliste aller Artikel, die es möglicherweise empfehlen kann, aber Sie zeigen dem Benutzer nur die besten davon.

Wenn Sie die Ergebnisse von zwei Empfehlungsprogrammen vergleichen, ist es nicht sinnvoll, Artikel zu vergleichen, die nicht angezeigt werden. Wenn dieEmpfehlungsgeber und die gleichen Top-10-Elemente liefern, sind sie im Wesentlichen gleich, unabhängig davon, ob das Elementan Position 100 von auch an Position 100 von zu finden ist. Wir können jedoch nicht Kendalls Tau verwenden, um die ersten 10 Elemente von A direkt mit den ersten 10 Elementen von B zu vergleichen, da sie wahrscheinlich nicht genau die gleichen Elemente enthalten.

Der beste Weg, zwei Empfehlungsprogramme zu vergleichen, ist natürlich ein A/B-Test. Aber die Durchführung eines A/B-Tests erfordert Zeit und Ressourcen , die Sie vielleicht nicht immer haben. In diesem Fall können Sie die Ergebnisse der Empfehlungsprogramme auch direkt vergleichen.

Ich habe diese Methode zum Beispiel verwendet, um eine Änderung in einem Empfehlungsprogramm zu bewerten, bei der ein Leistungsgewinn gegen eine Verringerung der Genauigkeit eingetauscht wurde. Ein direkter Vergleich der Ergebnisse kann Ihnen wertvolle Informationen über die Auswirkungen vonauf die reduzierte Genauigkeit liefern. Wenn die Ergebnisse ähnlich sind, können Sie die Änderung in die Produktion übernehmen, wenn nicht, sollten Sie nicht länger Ihre Zeit verschwenden und die Änderung vergessen.

Definition

Die gebräuchlichste Definition des Kendall-Tau zwischen zwei Rängen a und b lautet:

tau equiv frac{n_c - n_d}{sqrt{(n_0-n_a)(n_0-n_b)}},

wobei n_c und n_d die Anzahl der übereinstimmenden Paare bzw. die Anzahl der nicht übereinstimmenden Paare sind, n_0 ist definiert als

n_0 equiv frac{n(n-1)}{2},

wobei n die Länge der Ränge ist und n_a und n_b die Gleichheit der Ränge berücksichtigen und wie folgt definiert sind

begin{aligned}
n_a &equiv sum_i frac{t^a_i (t^a_i-1)}{2},\\
n_b &equiv sum_j frac{t^b_j (t^b_j-1)}{2},
end{aligned}

wobei t^a_i und t^b_j sind die Anzahl der (gebundenen) Artikel, die sich das i^text{th} Platz im Rang a, und die Anzahl der (gebundenen) Artikel, die sich das j^text{th} Platz im Rang b beziehungsweise.

Zwischen den Rängen a und b liegt ein Paar von Artikeln x und y.

• übereinstimmend, wenn

(a_x > a_y wedge b_x > b_y) | (a_x < a_y wedge b_x < b_y)

• diskordant (a_x > a_y wedge b_x < b_y) | (a_x < a_y wedge b_x > b_y)
• weder konkordant noch diskordant im Falle von Unentschieden,

  a_x = a_y wedge b_x = b_y

Wenn es keine Bindungen gibt, reduziert sich dies auf die einfachere Form

tau equiv frac{n_c - n_d}{n_0},

da sowohl n_a als auch n_b gleich Null sind.

Ein Beispiel

Lassen Sie uns einen Blick auf diese beiden Ränge werfen:

rank_a = {'apple': 0, 'banana': 2, 'kiwi': 3, 'pear': 1}
rank_b = {'apple': 2, 'banana': 1, 'kiwi': 3, 'pear': 0}

Hier atext{apple} < atext{pear}, während btext{apple} > btext{pear}, also ist dieses Paar diskordant. Außerdem atext{pear} < atext{banana} und btext{pear} < btext{banana}, also ist dieses Paar kondordant. Insgesamt enthält dieses Beispiel vier konkordante Paare und zwei diskordante Paare. Da n=4, bedeutet dies, dass

tau = frac{4-2}{4(4-1)/2} = frac{1}{3},

was bedeutet, dass die beiden Ränge leicht korreliert sind.

Da es im obigen Beispiel keine Bindungen gibt, können wir es direkt auf zwei Listen übertragen:

a = ['apple', 'pear', 'banana', 'kiwi']
b = ['pear', 'banana', 'apple', 'kiwi']

In Listenform hat ein übereinstimmendes Paar in beiden Listen die gleiche Reihenfolge, während die Reihenfolge eines nicht übereinstimmenden Paares zwischen und den Listen vertauscht wird. Zwei Elemente können nicht denselben Platz einnehmen, so dass es keine Gleichheit geben kann.

Umgang mit Unstimmigkeiten

Die Definition des Kendall tau kann nicht mit Elementen umgehen, die nur in einer der Listen vorkommen. Aber wenn wirdie Top-5-Ergebnisse des Empfehlungsprogramms mit den Top-5-Ergebnissen des Empfehlungsprogramms vergleichen, können wir erwarten, dassnicht übereinstimmt: Es ist unwahrscheinlich, dass die Algorithmen die gleichen Ergebnisse liefern. Dennoch möchten wir nicht die gesamte Rangliste der Empfehlungsprogramme vergleichen, da uns das untere Ende der Rangliste überhaupt nicht interessiert.

Unstimmigkeiten ignorieren

Der einfachste Weg, mit Unstimmigkeiten umzugehen, ist, sie zu ignorieren. Indem wir einfach alle Elemente entfernen, die nicht in beiden Listen vonvorkommen, reduzieren wir das Problem auf eines, das wir lösen können. Zum Beispiel,

a = ['apple', 'pear', 'banana', 'kiwi', 'pineapple']
b = ['pear', 'orange', 'banana', 'apple', 'kiwi']

würde sich auf das obige Beispiel reduzieren, wobei tau = frac{1}{3}. Auf den ersten Blick scheint das akzeptabel. Aber hier:

a = ['apple', 'pear', 'banana', 'kiwi', 'pineapple']
b = ['apple', 'pear', 'banana', 'kiwi', 'orange']

werden die Listen a und b auf identische Listen reduziert, so dass tau = 1 entsteht, obwohl die ursprünglichen Listen nicht identisch sind.

Die Probleme verschlimmern sich, wenn es in der Liste mehr Unstimmigkeiten gibt:

a = ['pineapple', 'lemon', 'apple', 'kiwi', 'grape']
b = ['apple', 'pear', 'banana', 'kiwi', 'orange']

würde auch tau = 1 auswerten (da apple und kiwi übereinstimmen), während ich argumentieren würde, dass die Listen bei weitem nicht gleich sind. In dem extremen Fall, dass es nur eine Übereinstimmung gibt,

a = ['pineapple', 'lemon', 'apple', 'kiwi', 'grape']
b = ['apple', 'pear', 'banana', 'plum', 'orange']

ist der Kendall tau undefiniert, da der Nenner n(n-1)/2 = 0 für n=1 steht. Es ist also klar, dass das Ignorieren von Fehlanpassungen nicht die Lösung für unser Problem ist.

Anhängen von Unstimmigkeiten

Anstatt die Nichtübereinstimmungen zu ignorieren, können wir sie auch an das Ende der anderen Liste anhängen. In gewisser Weise ist dies sinnvoll, da alle Ergebnisse in beiden Listen enthalten sind, nur nicht unbedingt in den Top-5. Da wir keine Informationen darüber haben, wo die Ergebnisse in der Liste stehen (unterhalb der Top-5), sollten wir alle Ergebnisse unterhalb der Top-5 als gleichwertig behandeln. Zum Beispiel:

a = ['pineapple', 'apple', 'pear', 'kiwi', 'grape']
b = ['apple', 'pear', 'banana', 'kiwi', 'orange']

würde dann zu

rank_a = {'apple': 1, 'banana': 5, 'grape': 4, 'orange': 5, 'pear': 2, 'pineapple': 0, 'kiwi': 3}
rank_b = {'apple': 0, 'banana': 2, 'grape': 5, 'orange': 4, 'pear': 1, 'pineapple': 5, 'kiwi': 3}

wobei banana und orange auf dem 5. Platz der Rangliste landen a, und pineapple und grape teilen sich den 5. Platz im Rang b. Das Ergebnis ist tau approx 0.15, was in etwa dem entspricht, was ich erwarten würde.

Wenn wir dies für andere Beispiele tun, erhalten wir einige schöne Ergebnisse:

a = ['apple', 'pear', 'banana', 'kiwi', 'grape']
appended_tau(a, a) -> 1

# replace last element
b = ['apple', 'pear', 'banana', 'kiwi', 'orange']
appended_tau(a, b) -> 0.87

# replace first element
c = ['orange', 'pear', 'banana', 'kiwi', 'grape']
appended_tau(a, c) -> -0.20

# replace two elements
d = ['orange', 'pear', 'pineapple', 'kiwi', 'grape']
appended_tau(a, d) -> -0.45

# replace all elements
e = ['orange', 'tomato', 'pineapple', 'lemon', 'plum']
appended_tau(a, e) -> -0.71

# invert
f = ['grape', 'kiwi', 'banana', 'pear', 'apple']
appended_tau(a, f) -> -1

Die Korrelation verringert sich, wenn ein Element ersetzt wird, und das Ersetzen des ersten Elements hat deutlich mehr Auswirkungen als das Ersetzen des letzten. Das ist genau so, wie wir es erwarten. Das Ersetzen aller Elemente führt jedoch zu einer höheren Korrelation als das Invertieren der Liste. Ich würde sagen, das ist nicht das, was wir erwarten: Ich würde sagen, dass eine invertierte Top-5 dem Original näher ist als eine, die völlig anders ist.

Warum ist also die Korrelation von a und e größer als die von a und f? Es ist klar, dass zwischen a und f alle Wortpaare nicht übereinstimmen. Wenn wir uns die resultierenden Ränge genauer ansehen, wenn wir a und e vergleichen:

rank_a = {'apple': 0, 'banana': 2, 'grape': 4, 'kiwi': 3, 'lemon': 5,
          'orange': 5, 'pear': 1, 'pineapple': 5, 'plum': 5, 'tomato': 5}
rank_e = {'apple': 5, 'banana': 5, 'grape': 5, 'kiwi': 5, 'lemon': 3,
          'orange': 0, 'pear': 5, 'pineapple': 2, 'plum': 4, 'tomato': 1}

sehen wir, dass es auch hier keine übereinstimmenden Paare gibt. Allerdings sind nicht alle Paare diskordant, denn alle Paare, bei denen beide Artikel in derselben Liste vorkommen, sind im Rang des jeweils anderen gebunden. Zum Beispiel sind apple und banana im Rang e, gleichauf und sind daher nicht diskordant. Der Unterschied zwischen den beiden Korrelationen ergibt sich also aus dem Unterschied in der Anzahl der Gleichheiten oder der unterschiedlichen Länge der Ränge.

Ausweitung der Ränge

Wir können das Ungleichgewicht in der Anzahl der Gleichheiten beheben, indem wir eine Anzahl von Dummy-Elementen zu den Rängen hinzufügen, so dass alle Ränge die gleiche Länge haben. Die Ränge, die wir erhalten, wenn wir zwei Listen vergleichen, können nie länger als die doppelte Länge einer Liste sein, was der Fall ist, wenn die Listen keine gemeinsamen Elemente haben. Wenn wir also alle Ränge auf die doppelte Länge einer Liste erweitern, hat jeder Rang die gleiche Länge.

Im obigen Beispiel von a und e haben die Listen keine gemeinsamen Elemente und die Ränge sind doppelt so lang wie die Listen. Das heißt, wir fügen keine Dummy-Elemente hinzu und die Korrelation bleibt tau = -0.71. Im Fall von a und f, sind jedoch alle Elemente gemeinsam, und daher haben die Ränge die gleiche Länge wie die Listen. Wir werden also die Ränge mit Dummy-Elementen erweitern (z.B. Körner):

a = ['apple', 'pear', 'banana', 'kiwi', 'grape']
f = ['grape', 'kiwi', 'banana', 'pear', 'apple']

rank_a = {'apple': 0, 'banana': 2, 'grape': 4, 'kiwi': 3,  'pear': 1,
          'wheat': 5, 'barley': 5, 'rice': 5, 'corn': 5, 'rye': 5}
rank_f = {'apple': 4, 'banana': 2, 'grape': 0, 'kiwi': 1,  'pear': 3,
          'wheat': 5, 'barley': 5, 'rice': 5, 'corn': 5, 'rye': 5}

was zu einer Korrelation von tau approx 0.45 führt.

Ist das nicht eine ziemlich hohe Korrelation zwischen einer Liste und ihrer Umkehrung? Für diese Listen ist das in der Tat eine ziemlich hohe Korrelation, aber bedenken Sie, dass wir die Top-5 der höchsten Einträge von (viel) längeren Listen vergleichen. Die Tatsache, dass die Listen in ihren fünf höchsten Einträgen die gleichen Elemente enthalten, macht sie meiner Meinung nach ziemlich ähnlich.

Schauen wir uns nun einige Beispiele an:

a = ['apple', 'pear', 'banana', 'kiwi', 'grape']
extended_tau(a, a) -> 1

# replace the last element
b = ['apple', 'pear', 'banana', 'kiwi', 'lemon']
extended_tau(a, b) -> 0.83

# invert
c = ['grape', 'kiwi', 'banana', 'pear', 'apple']
extended_tau(a, c) -> 0.43

# replace the first element
d = ['tomato', 'pear', 'banana', 'kiwi', 'grape']
extended_tau(a, d) -> 0.37

# replace three elements and add three new
e = ['lemon', 'tomato', 'apple', 'pineapple', 'grape']
extended_tau(a, e) -> -0.23

# replace all elements
f = ['orange', 'tomato', 'pineapple', 'lemon', 'plum']
extended_tau(a, f) -> -0.71

Diese Ergebnisse sehen richtig aus: Jeder Schritt, der die Liste noch mehr durcheinander bringt, führt zu einer niedrigeren Korrelation. Das Ersetzen des ersten Elements hat eine größere Auswirkung als das Ersetzen des letzten, und das Invertieren der Liste führt zu einer weitaus größeren Korrelation als das Ersetzen aller Elemente. Das einzige Problem, das bleibt, ist die Skala: Wir erwarten, dass die Korrelation im Bereich [-1, +1] skaliert, aber in diesem Fall liegt der Mindestwert bei -0.71. Dieser Mindestwert hängt von der Länge der Listen ab, die wir vergleichen.

Skalierung des Ergebnisses

Wir können den Mindestwert in Abhängigkeit von der Länge unserer Listen berechnen. Die minimale Korrelation ist erreicht, wenn die beiden Listen keine überlappenden Elemente haben. Gehen wir zurück zur Definition,

tau equiv frac{n_c - n_d}{sqrt{(n_0-n_a)(n_0-n_b)}},

bedeutet dies, dass n_c = 0, und n = 2l, wobei l die Länge der Listen ist. In jedem der Ränge gibt es l Elemente, die an der letzten Position gebunden sind, und es gibt keine weiteren Bindungen. Das bedeutet, dass n_a = n_b = l(l-1)/2. Auch n_d = n_0 - n_a - n_b, da alle Paare, außer denen, die gebunden sind, diskordant sind. Folglich,

begin{aligned}
tau_{min}(l) &= -frac{n_0 - 2n_a}{n_0 - n_b}\\
            &= -frac{n(n-1) - 2l(l-1)}{n(n-1) - l(l-1)}\\
            &= -frac{2l(2l-1) - 2l(l-1)}{2l(2l-1) - l(l-1)}.
end{aligned}

Wenn Sie l=5 wählen, ergibt dies tau_{min} approx -0.71.

Mit dem obigen Ergebnis können wir das erweiterte Tau so skalieren, dass es ein Intervall von [-1, +1] abdeckt:

tau_s equiv 2frac{tau-tau_{min}(l)}{1-tau_{min}(l)} - 1.

Zusammenfassung

Der Kendall-Tau ist für Listen, die nicht dieselben Elemente enthalten, undefiniert, was uns daran hindert, ihn zu verwenden, um Teile von Rängen zu vergleichen. Wir können diese Einschränkung umgehen, indem wir alle fehlenden Elemente an den Rang einer der beiden Listen in einer gebundenen letzten Position anhängen, hinter allen in der Liste vorhandenen Elementen. Eine variable Anzahl von gebundenen Elementen verzerrt die resultierenden Korrelationen, was wir verhindern können, indem wir gebundene Dummy-Elemente zu beiden Rängen hinzufügen. Am Ende müssen wir das Ergebnis skalieren, um sicherzustellen, dass es in das Intervall [-1, +1] fällt.

Es ist wichtig zu beachten, dass die resultierende "Korrelation", obwohl sie ein Maß für die Ähnlichkeit zwischen zwei Rängen ist, nicht mehr alle Eigenschaften hat, die Sie von einem Kendall-Tau oder einer Korrelation im Allgemeinen erwarten würden. Offensichtlich ist das Ergebnis des Vergleichs einer Liste mit ihrer Umkehrung nicht mehr -1 und das erwartete Ergebnis zwischen zufällig verschlüsselten Listen ist nicht mehr. Dennoch kann das Maß nützlich sein, wenn Sie die obersten Elemente von Ranglisten vergleichen.

Eine Python-Implementierung wird unten gezeigt.

import pandas as pd
import scipy.stats as stats

def extended_tau(list_a, list_b):
    """ Calculate the extended Kendall tau from two lists. """
    ranks = join_ranks(create_rank(list_a), create_rank(list_b)).fillna(len(list_a))
    dummy_df = pd.DataFrame([{'rank_a': len(list_a), 'rank_b': len(list_b)} for i in range(len(list_a)*2-len(ranks))])
    total_df = ranks.append(dummy_df)
    return scale_tau(len(list_a), stats.kendalltau(total_df['rank_a'], total_df['rank_b'])[0])

def scale_tau(length, value):
    """ Scale an extended tau correlation such that it falls in [-1, +1]. """
    n_0 = 2*length*(2*length-1)
    n_a = length*(length-1)
    n_d = n_0 - n_a
    min_tau = (2.*n_a - n_0) / (n_d)
    return 2*(value-min_tau)/(1-min_tau) - 1

def create_rank(a):
    """ Convert an ordered list to a DataFrame with ranks. """
    return pd.DataFrame(
                  zip(a, range(len(a))),
                  columns=['key', 'rank'])
             .set_index('key')

def join_ranks(rank_a, rank_b):
    """ Join two rank DataFrames. """
    return rank_a.join(rank_b, lsuffix='_a', rsuffix='_b', how='outer')