<filename>project/Transparency/common_code/kendall_top_k.py
"""Top-k kendall-tau distance.

This module generalise kendall-tau as defined in [1].
It returns a distance: 0 for identical (in the sense of top-k) lists and 1 if completely different.

Example:
    Simply call kendall_top_k with two same-length arrays of ratings (or also rankings), length of the top elements k (default is the maximum length possible), and p (default is 0, see [1]) as parameters:

        import kendall
        a = np.array([1,2,3,4,5])
        b = np.array([5,4,3,2,1])
        kendall.kendall_top_k(a,b,k=4)

Author: <NAME>
    https://github.com/AlessandroChecco
References
[1] <NAME>, <NAME>, and <NAME>. "Comparing top k lists." SIAM Journal on Discrete Mathematics 17.1 (2003): 134-160.
"""
import numpy as np
import scipy.stats as stats
import scipy.special as special

def kendall_top_k(a,b,k=None,p=0.5): #zero is equal 1 is max distance, compare with 1-scipy.stats.kendalltau(a,b)/2+1/2
    """
    kendall_top_k(np.array,np.array,k,p)
    This function generalise kendall-tau as defined in [1] <NAME>, <NAME>, and <NAME>. "Comparing top k lists." SIAM Journal on Discrete Mathematics 17.1 (2003): 134-160.
    It returns a distance: 0 for identical (in the sense of top-k) lists and 1 if completely different.

    Example:
        Simply call it with two same-length arrays of ratings (or also rankings), length of the top elements k (default is the maximum length possible), and p (default is 0, see [1]) as parameters:

            $ a = np.array([1,2,3,4,5])
            $ b = np.array([5,4,3,2,1])
            $ kendall_top_k(a,b,k=4)
    """

    a = np.array(a)
    b = np.array(b)
    if k is None:
        k = a.size
    if a.size != b.size:
        raise NameError('The two arrays need to have same lengths')
    k = min(k,a.size)
    a_top_k = np.argpartition(a,-k)[-k:]
    b_top_k = np.argpartition(b,-k)[-k:]
    common_items = np.intersect1d(a_top_k,b_top_k)
    only_in_a = np.setdiff1d(a_top_k, common_items)
    only_in_b = np.setdiff1d(b_top_k, common_items)
    kendall = (1 - (stats.kendalltau(a[common_items], b[common_items])[0]/2+0.5)) * (common_items.size**2) #case 1
    if np.isnan(kendall): # degenerate case with only one item (not defined by Kendall)
        kendall = 0
    for i in common_items: #case 2
        for j in only_in_a:
            if a[i] < a[j]:
                kendall += 1
        for j in only_in_b:
            if b[i] < b[j]:
                kendall += 1
    kendall += 2*p * special.binom(k-common_items.size,2)     #case 4
    kendall /= ((only_in_a.size + only_in_b.size + common_items.size)**2 ) #normalization
    return np.array([kendall, 1.0])
    
if __name__ == "__main__":
    print("This is only a module")
<filename>project/Transparency/common_code/kendall_top_k.py
"""Top-k kendall-tau distance.

This module generalise kendall-tau as defined in [1].
It returns a distance: 0 for identical (in the sense of top-k) lists and 1 if completely different.

Example:
    Simply call kendall_top_k with two same-length arrays of ratings (or also rankings), length of the top elements k (default is the maximum length possible), and p (default is 0, see [1]) as parameters:

        import kendall
        a = np.array([1,2,3,4,5])
        b = np.array([5,4,3,2,1])
        kendall.kendall_top_k(a,b,k=4)

Author: <NAME>
    https://github.com/AlessandroChecco
References
[1] <NAME>, <NAME>, and <NAME>. "Comparing top k lists." SIAM Journal on Discrete Mathematics 17.1 (2003): 134-160.
"""
import numpy as np
import scipy.stats as stats
import scipy.special as special

def kendall_top_k(a,b,k=None,p=0.5): #zero is equal 1 is max distance, compare with 1-scipy.stats.kendalltau(a,b)/2+1/2
    """
    kendall_top_k(np.array,np.array,k,p)
    This function generalise kendall-tau as defined in [1] <NAME>, <NAME>, and <NAME>. "Comparing top k lists." SIAM Journal on Discrete Mathematics 17.1 (2003): 134-160.
    It returns a distance: 0 for identical (in the sense of top-k) lists and 1 if completely different.

    Example:
        Simply call it with two same-length arrays of ratings (or also rankings), length of the top elements k (default is the maximum length possible), and p (default is 0, see [1]) as parameters:

            $ a = np.array([1,2,3,4,5])
            $ b = np.array([5,4,3,2,1])
            $ kendall_top_k(a,b,k=4)
    """

    a = np.array(a)
    b = np.array(b)
    if k is None:
        k = a.size
    if a.size != b.size:
        raise NameError('The two arrays need to have same lengths')
    k = min(k,a.size)
    a_top_k = np.argpartition(a,-k)[-k:]
    b_top_k = np.argpartition(b,-k)[-k:]
    common_items = np.intersect1d(a_top_k,b_top_k)
    only_in_a = np.setdiff1d(a_top_k, common_items)
    only_in_b = np.setdiff1d(b_top_k, common_items)
    kendall = (1 - (stats.kendalltau(a[common_items], b[common_items])[0]/2+0.5)) * (common_items.size**2) #case 1
    if np.isnan(kendall): # degenerate case with only one item (not defined by Kendall)
        kendall = 0
    for i in common_items: #case 2
        for j in only_in_a:
            if a[i] < a[j]:
                kendall += 1
        for j in only_in_b:
            if b[i] < b[j]:
                kendall += 1
    kendall += 2*p * special.binom(k-common_items.size,2)     #case 4
    kendall /= ((only_in_a.size + only_in_b.size + common_items.size)**2 ) #normalization
    return np.array([kendall, 1.0])
    
if __name__ == "__main__":
    print("This is only a module")
Top-k kendall-tau distance.  This module generalise kendall-tau as defined in [1]. It returns a distance: 0 for identical (in the sense of top-k) lists and 1 if completely different.  Example:     Simply call kendall_top_k with two same-length arrays of ratings (or also rankings), length of the top elements k (default is the maximum length possible), and p (default is 0, see [1]) as parameters:          import kendall         a = np.array([1,2,3,4,5])         b = np.array([5,4,3,2,1])         kendall.kendall_top_k(a,b,k=4)  Author: <NAME>     https://github.com/AlessandroChecco References [1] <NAME>, <NAME>, and <NAME>. "Comparing top k lists." SIAM Journal on Discrete Mathematics 17.1 (2003): 134-160. #zero is equal 1 is max distance, compare with 1-scipy.stats.kendalltau(a,b)/2+1/2 kendall_top_k(np.array,np.array,k,p)     This function generalise kendall-tau as defined in [1] <NAME>, <NAME>, and <NAME>. "Comparing top k lists." SIAM Journal on Discrete Mathematics 17.1 (2003): 134-160.     It returns a distance: 0 for identical (in the sense of top-k) lists and 1 if completely different.      Example:         Simply call it with two same-length arrays of ratings (or also rankings), length of the top elements k (default is the maximum length possible), and p (default is 0, see [1]) as parameters:              $ a = np.array([1,2,3,4,5])             $ b = np.array([5,4,3,2,1])             $ kendall_top_k(a,b,k=4) #case 1 # degenerate case with only one item (not defined by Kendall) #case 2 #case 4 #normalization