corankco.algorithms.kwiksort package

Submodules

corankco.algorithms.kwiksort.kwiksortabs module

Module for KwikSortAbs. This module contains an abstract class about KwikSort algorithm for rank aggregation. This algorithm is based on QuickSort: a pivot is chosen, and the elements that should be placed before (resp. tied with, resp. after) the pivot are placed before (resp. tied with, resp. after) the pivot, and this process is done recursively. Complexity (mean): m * n * log(n) with n = nb of elements, m = nb of rankings. A class that implements the abstract class must implement the choice of the pivot.

class corankco.algorithms.kwiksort.kwiksortabs.KwikSortAbs

Bases: RankAggAlgorithm

Interface for KwikSort algorithms. KwikSort is a heuristics designed for Kemeny-Young method. QuickSort based algorithm: pick a pivot, find the set of elements shat should be ranked after pivot, then before pivot, then tied with pivot, and recursively go on with the before and after sets complexity: mean: O(nb_rankings * nb_elements * log2(nb_elements)) if choice of pivot is O(1) complexity: worst: 0(nb_ranking * nb_elements²) if pivot divides elements in groups of size 1 and n-1

compute_consensus_rankings(dataset: Dataset, scoring_scheme: ScoringScheme, return_at_most_one_ranking: bool = True, bench_mode: bool = False) → Consensus

Calculate and return the consensus rankings based on the given dataset and scoring scheme.

Parameters:

• dataset (Dataset) – The dataset of rankings to be aggregated.

• scoring_scheme (ScoringScheme) – The scoring scheme to be used for calculating consensus.

• return_at_most_one_ranking (bool) – If True, the algorithm should return at most one ranking.

• bench_mode (bool) – If True, the algorithm may return additional information for benchmarking purposes.

Returns:

Consensus rankings. If the algorithm is unable to provide multiple consensuses or

return_at_most_one_ranking is True, a single consensus ranking is returned. :raise ScoringSchemeNotHandledException: When the algorithm cannot compute the consensus because the implementation does not support the given scoring scheme.

get_full_name() → str

Return the full name of the algorithm.

Returns:

name of the algorithm, must be defined in daughter classes.

Return type:

str

is_scoring_scheme_relevant_when_incomplete_rankings(scoring_scheme: ndarray) → bool

Check if the scoring scheme is relevant when the rankings are incomplete.

Parameters:

scoring_scheme (ScoringScheme) – The scoring scheme to be checked.

Returns:

True as KwikSort can handle any ScoringScheme

Return type:

bool

corankco.algorithms.kwiksort.kwiksortrandom module

Module for KwikSortRandom. This module contains a class that implements the KwikSortAbs interface. The pivot is chosen randomly.

class corankco.algorithms.kwiksort.kwiksortrandom.KwikSortRandom

Bases: KwikSortAbs

Implementation of KwikSort algorithm (see KwikSortAbs abstract class) with choice of pivot is random, uniform

get_full_name() → str

Return the full name of the algorithm.

Returns:

The string ‘KwikSortRandom’.

Return type:

str

is_scoring_scheme_relevant_when_incomplete_rankings(scoring_scheme: ScoringScheme) → bool

Check if the scoring scheme is relevant when the rankings are incomplete.

Parameters:

scoring_scheme (ScoringScheme) – The scoring scheme to be checked.

Returns:

True as KwikSort can handle any ScoringScheme

Return type:

bool

Module contents

Module for KwikSortRandom rank aggregation algorithm. More details in KwikSortAbs and KwikSortRandom class docstring.