Repository: lenskit/lkpy

Issue:
nDCG metric does not correctly truncate lists
The nDCG metric has two faults whereby it fails to correctly truncate the truth list and recommendation list under certain conditions:

1. If no k is supplied, the full truth list and recommendation list are used to compute the ideal DCG and recommendation DCG, respectively. If the sizes of the input lists do not match, this causes an incorrect result. See the following example, based on "test_ndcg_wrong" in tests/test_topn_ndcg.py:
```
truth = pd.DataFrame({'item': [1, 2, 3], 'rating': [3.0, 5.0, 4.0]})
truth = truth.set_index('item')
recs = pd.DataFrame({'item': [1, 2]})

print(ndcg(recs, truth))  # incorrectly gives ~0.7344
print(ndcg(recs, truth, k=2))  # correctly gives ~0.8888
```

2. If a k is supplied that is less than the length of the recommendation list, the recommendation DCG is not computed correctly (due to "tpos" being defined before the recommendation list is truncated). See the following example, based on "test_ndcg_perfect" found in tests/test_topn_ndcg.py:
```
truth = pd.DataFrame({'item': [1, 2, 3], 'rating': [3.0, 5.0, 4.0]})
truth = truth.set_index('item')
recs = pd.DataFrame({'item': [2, 3, 1]})

print(ndcg(recs, truth))  # correctly gives 1.0
print(ndcg(recs, truth, k=2))  # incorrectly gives ~1.21
print(ndcg(recs[:2], truth, k=2))  # correctly gives 1.0
```

Discussion:

Patch:
diff --git a/lenskit/metrics/topn.py b/lenskit/metrics/topn.py
index ae1b70f3..7f616c53 100644
--- a/lenskit/metrics/topn.py
+++ b/lenskit/metrics/topn.py
@@ -300,11 +300,11 @@ def ndcg(recs, truth, discount=np.log2, k=None):
             The maximum list length.
     """
 
-    tpos = truth.index.get_indexer(recs['item'])
-
     if k is not None:
         recs = recs.iloc[:k]
 
+    tpos = truth.index.get_indexer(recs['item'])
+
     if 'rating' in truth.columns:
         i_rates = np.sort(truth.rating.values)[::-1]
         if k is not None:


Test patch:
diff --git a/tests/test_topn_ndcg.py b/tests/test_topn_ndcg.py
index 5d1601d9..2fdf9e57 100644
--- a/tests/test_topn_ndcg.py
+++ b/tests/test_topn_ndcg.py
@@ -87,6 +87,14 @@ def test_ndcg_perfect():
     assert ndcg(recs, truth) == approx(1.0)
 
 
+def test_ndcg_perfect_k_short():
+    recs = pd.DataFrame({'item': [2, 3, 1]})
+    truth = pd.DataFrame({'item': [1, 2, 3], 'rating': [3.0, 5.0, 4.0]})
+    truth = truth.set_index('item')
+    assert ndcg(recs, truth, k=2) == approx(1.0)
+    assert ndcg(recs[:2], truth, k=2) == approx(1.0)
+
+
 def test_ndcg_wrong():
     recs = pd.DataFrame({'item': [1, 2]})
     truth = pd.DataFrame({'item': [1, 2, 3], 'rating': [3.0, 5.0, 4.0]})