Social Media Mining: An Introduction

P1: Trim: 6.125in×9.25in Top: 0.5in Gutter: 0.75in
CUUS2079-09 CUUS2079-Zafarani 978 1 107 01885 3 January 13, 2014 17:28

266 Recommendation in Social Media

9.4.3 Evaluating Ranking of Recommendations

Often, we predict ratings for multiple products for a user. Based on the pre-

dicted ratings, we can rank products based on their levels of interestingness

to the user and then evaluate this ranking. Given the true ranking of inter-

estingness of items, we can compare this ranking with it and report a value.

Rank correlation measures the correlation between the predicted ranking

and the true ranking. One such technique is the Spearman’s rank correla-

tion discussed in Chapter 8. Letxi,1≤xi≤n, denote the rank predicted

for itemi,1≤i≤n. Similarly, letyi,1≤yi≤n, denote the true rank of

itemifrom the user’s perspective. Spearman’s rank correlation is defined

as

ρ= 1 −

6

∑n

i= 1 (xi−yi)^2

n^3 −n

, (9.83)

wherenis the total number of items.

Here, we discuss another rank correlation measure: Kendall’s tau. We

KENDALL’S say that the pair of items (i,j)areconcordantif their ranks{xi,yi}and

TAU {xj,yj}are in order:

xi>xj, yi>yj or xi<xj, yi<yj. (9.84)

A pair of items isdiscordantif their corresponding ranks are not in

order:

xi>xj, yi<yj or xi<xj, yi>yj. (9.85)

Whenxi=xjoryi=yj, the pair is neither concordant nor discordant.

Letcdenote the total number of concordant item pairs anddthe total

number of discordant item pairs. Kendall’s tau computes the difference

between the two, normalized by the total number of item pairs

(n

2

)

:

τ=

c(−d

n

2

). (9.86)

Kendall’s tau takes value in range [− 1 ,1]. When the ranks completely

agree, all pairs are concordant and Kendall’s tau takes value 1, and when the

ranks completely disagree, all pairs are discordant and Kendall’s tau takes

value−1.