Numpy based implementation of the Borda Selection Algorithm for Rankings

borda.py

"""Python/Numpy implementation of the Borda Count"""

import numpy as np
from nptyping import NDArray
from typing import Tuple, Union, List, Any

RankingsList = Union[NDArray[(Any, Any), np.int], List[List[int]]]
Ranking = NDArray[(Any,), np.int]
Counts = NDArray[(Any,), np.int]
AveragePositions = NDArray[(Any,), np.float]
Borda = Tuple[Ranking, Counts, AveragePositions]


def borda_count_np(X: RankingsList, min_score: float = 1, k: int = None) -> Borda:
    """Given N ranked ids lists of length P compute the number of
    extractions on top-k positions and the mean position for each id.

    Sort the element ids (in reversed DECREASING order) based on the
    Borda Extraction Scores (BES). IDs having the same BES will be sorted
    by their increasing average position (i.e. the average of the position
    of each ID in all the rankings).

    Parameters
    ----------
    X : Numpy array of integer with shape [N, P] or List of Lists
        The list of rankings
    min_score: float, optional
        Minimum score considered for IDs (Default is 1)
    k : int, optional
        Top-K positions to select.
        Default is None, which means that all the positions will be
        selected (i.e. k = P)

    Returns
    -------
    Borda
        A tuple containing three NDarray:
        1. Sorted IDs, i.e. the Borda Ranking;
        2. The number of Extractions, i.e. Count;
        3. The average positions of each ID.

    Raises
    ------
    ValueError
        If k < 1 or k > p
    ValueError
        If X contains duplicate IDs
    """

    x_np = np.asarray(X)  # make sure X is a Numpy array for efficiency
    n, p = x_np.shape
    if k is None:
        k = p
    if not 1 <= k <= p:
        raise ValueError(f"k must be in [1, {p}], {k} given instead!")
    # Verify that ranked lists do no contain repetitions
    unique_ids = np.asarray([len(set(r)) for r in x_np[:]])
    if len(unique_ids[unique_ids < p]):
        raise ValueError(
            f"IDs in list of rankings are not unique! Unique IDs found: {unique_ids}"
        )

    positions = np.argsort(x_np, axis=1)
    # Select TopK by forcing positions of others to last position
    positions[positions >= k] = p
    # Calculate scores of extractions in each ranking based on their relative position
    exts = (p - positions - 1 + min_score).sum(axis=0)
    # Count total number of valid extractions
    counts = (positions < k).sum(axis=0)
    # Reset all non-valid positions (>=k) for TopK selection
    positions[positions >= k] = 0
    # Calculate Average positions of each element in each ranking
    non_zero_counts = counts != 0
    avg_positions = positions.sum(axis=0) / np.where(non_zero_counts, counts, 1)
    avg_positions[~non_zero_counts] = p - 1
    # Sort rankings based on average positions, and extraction scores
    idx = np.lexsort((avg_positions, exts))[::-1]

    return idx, counts[idx], avg_positions[idx]

metric_ranking_dap_fixture.csv

test_borda.py

import pytest
import pandas as pd
import os
from numpy.testing import assert_array_almost_equal, assert_array_equal
from mlpy import borda_count as borda_mlpy
from .borda import borda_count_np


@pytest.fixture()
def docstring_example():
    """Returns the example reported in MLPY borda_count docstring"""
    x = [
        [2, 4, 1, 3, 0],  # first ranked list
        [3, 4, 1, 2, 0],  # second ranked list
        [2, 4, 3, 0, 1],  # third ranked list
        [0, 1, 4, 2, 3],  # fo`urth ranked list
    ]
    return x


@pytest.fixture()
def ranking_lists_with_reps():
    """Returns the example reported in MLPY borda_count docstring"""
    x = [
        [2, 4, 3, 3, 0],  # first ranked list
        [3, 4, 1, 2, 0],  # second ranked list
        [2, 4, 1, 0, 1],  # third ranked list
        [0, 1, 2, 2, 3],  # fourth ranked list
    ]
    return x


@pytest.fixture()
def data_folder():
    return os.path.abspath(os.path.dirname(__file__))


@pytest.fixture()
def dap_rankings(data_folder):
    """Loads a Ranking example as returned by a DAP execution"""
    fp = os.path.join(data_folder, "metric_ranking_dap.csv")
    df = pd.read_csv(fp, header=0, index_col=0)
    return df.values


def _compare_borda_arrays(fixture, top_k=None):
    ids_mlpy, count_exts_mlpy, mean_pos_mlpy = borda_mlpy(fixture, k=top_k)
    ids_np, count_exts_np, mean_pos_np = borda_count_np(fixture, k=top_k)

    assert_array_equal(ids_mlpy, ids_np, "Rankings are Different")
    assert_array_equal(
        count_exts_mlpy, count_exts_np, "Count Extractions are Different"
    )
    assert_array_almost_equal(
        mean_pos_mlpy, mean_pos_np, decimal=6, err_msg="Mean Positions are Different"
    )


def test_dummy_ranking(docstring_example):
    _compare_borda_arrays(docstring_example)


def test_borda_numpy_implementation_dap_ranking(dap_rankings):
    _compare_borda_arrays(dap_rankings)


# Test and Compare Borda results at different values of TopK selections
def test_dummy_ranking_top_k(docstring_example):
    for top_k in (1, 2, 3, 4):
        _compare_borda_arrays(docstring_example, top_k=top_k)


def test_dap_ranking_top_k(dap_rankings):
    for top_k in (1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 107):
        _compare_borda_arrays(dap_rankings, top_k=top_k)


def test_exception_is_raised_with_k_out_of_range(docstring_example):
    # Testing MLPY implementation first for comparability
    with pytest.raises(ValueError):
        borda_mlpy(docstring_example, k=0)

    with pytest.raises(ValueError):
        borda_count_np(docstring_example, k=0)

    # Testing MLPY implementation first for comparability
    with pytest.raises(ValueError):
        borda_mlpy(docstring_example, k=6)

    with pytest.raises(ValueError):
        borda_count_np(docstring_example, k=6)


def test_value_error_rankings_list_with_repetitions(ranking_lists_with_reps):
    with pytest.raises(ValueError):
        borda_count_np(ranking_lists_with_reps)