Repository files navigation

Kendall’s Tau is a measure of rank correlation between two list of rank vectors. This metric's time complexity isO(n log(n)), which can be slow when used in pairwise comparison tasks like clustering. There is an approximated way to calculate it in constant time, which is described in the work"Sketching Algorithms For Approximating Rank Correlations In Collaborative Filtering Systems". I also include a write up in the repo to simplify the descriptions.

Just clone the package and putsketch.py to your working directory.

from sketch import KTSketchx1 = [1,3,2,4,5]x2 = [3,2,1,5,4]epsilon = 0.05     #accuracy as the abs. error <= epsilonCI = 0.95          #confidence interval as P(abs. error <= epsilon) >= CIdimension = 5 #size of vectorktsketch = KTSketch(epsilon=epsilon,CI=CI,dim=dimension,seed=0)ktsketch.correlation(x1,x2)