pairwise-combinatorial 0.1.0

Combinatorial method for pairwise comparison aggregation using Prüfer sequences with parallel processing

Pairwise Combinatorial

English version

Python бібліотека для агрегації парних порівнянь з використанням комбінаторного методу та послідовностей Прюфера. Ця реалізація забезпечує ідеальну паралелізацію для майже лінійного прискорення з декількома робочими процесами.

Особливості

• Комбінаторний метод: Агрегує матриці парних порівнянь через перерахування остовних дерев
• Паралельна обробка: Використовує послідовності Прюфера для ідеального розподілу роботи між процесами
• Гнучка агрегація: Підтримує зважене та просте середнє геометричне
• Підтримка неповних матриць: Обробляє неповні матриці парних порівнянь за допомогою LLSM
• Генерація матриць: Вбудовані утиліти для генерації тестових матриць порівнянь

Встановлення

Встановити за допомогою uv:

uv pip install pairwise-combinatorial

Або встановити з джерела:

git clone https://github.com/danolekh/pairwise_combinatorial
cd pairwise-combinatorial
uv pip install -e .

Швидкий старт

import numpy as np
from pairwise_combinatorial import (
    combinatorial_method,
    weighted_geometric_mean,
    generate_comparison_matrix,
)

# Генеруємо випадкову матрицю порівнянь
n = 9  # Кількість критеріїв
A = generate_comparison_matrix(n, missing_ratio=0.0)

# Застосовуємо комбінаторний метод з паралельною обробкою
result = combinatorial_method(
    A,
    n_workers=10,  # Кількість паралельних робочих процесів
    aggregator=weighted_geometric_mean,
)

print(f"Вектор пріоритетів: {result}")

Довідник API

Основні функції

combinatorial_method(A, n_workers, aggregator)

Основний комбінаторний метод з використанням послідовностей Прюфера.

Параметри:

• A (np.ndarray): Матриця парних порівнянь (n × n)
• n_workers (int | Callable): Кількість робочих процесів або функція, що повертає їх кількість
  • За замовчуванням: smart_worker_count (автоматично визначає на основі розміру матриці та кількості CPU)
• aggregator (Callable): Функція для агрегації векторів пріоритетів
  • Геометричні: weighted_geometric_mean (за замовчуванням), simple_geometric_mean
  • Арифметичні: weighted_arithmetic_mean, simple_arithmetic_mean

Повертає:

• np.ndarray: Фінальний агрегований вектор пріоритетів

Функції агрегації

Геометричне середнє

weighted_geometric_mean(results)

Агрегує вектори пріоритетів за допомогою зваженого середнього геометричного.

simple_geometric_mean(results)

Агрегує вектори пріоритетів за допомогою простого середнього геометричного (рівні ваги).

Арифметичне середнє

weighted_arithmetic_mean(results)

Агрегує вектори пріоритетів за допомогою зваженого середнього арифметичного.

simple_arithmetic_mean(results)

Агрегує вектори пріоритетів за допомогою простого середнього арифметичного (рівні ваги).

Допоміжні функції

generate_comparison_matrix(n, missing_ratio, generator)

Генерує матрицю парних порівнянь.

Параметри:

• n (int): Розмірність матриці (кількість критеріїв)
• missing_ratio (float): Частка відсутніх порівнянь (від 0.0 до 1.0)
• generator (Callable): Функція, що генерує значення порівнянь
  • За замовчуванням: saaty_generator (використовує шкалу Сааті 1-9)

Повертає:

• np.ndarray: Матриця парних порівнянь

is_full(A)

Перевіряє, чи матриця порівнянь не має відсутніх значень.

is_connected(A)

Перевіряє, чи граф матриці порівнянь є зв'язним.

calculate_consistency_ratio(A, w)

Обчислює коефіцієнт узгодженості (CR) для матриці парних порівнянь.

llsm_incomplete(A)

Заповнює неповні матриці за допомогою методу логарифмічних найменших квадратів.

Вибір кількості робочих процесів

smart_worker_count(n)

Інтелектуально визначає кількість робочих процесів на основі розміру матриці та кількості CPU.

auto_detect_workers()

Автоматично визначає кількість робочих процесів лише на основі кількості CPU.

Приклади

Приклад з повною матрицею

import numpy as np
from pairwise_combinatorial import combinatorial_method, weighted_geometric_mean

# Створюємо просту матрицю порівнянь 4x4
A = np.array([
    [1.0, 3.0, 5.0, 7.0],
    [1/3, 1.0, 2.0, 4.0],
    [1/5, 1/2, 1.0, 2.0],
    [1/7, 1/4, 1/2, 1.0]
])

# Обчислюємо вектор пріоритетів
weights = combinatorial_method(A, n_workers=4)
print(f"Ваги: {weights}")

Приклад з неповною матрицею

import numpy as np
from pairwise_combinatorial import (
    combinatorial_method,
    generate_comparison_matrix,
    is_connected,
)

# Генеруємо матрицю з 30% відсутніх значень
A = generate_comparison_matrix(n=6, missing_ratio=0.3)

if is_connected(A):
    # Застосовуємо комбінаторний метод
    weights = combinatorial_method(A, n_workers=4)
    print(f"Ваги: {weights}")
else:
    print("Матриця не є зв'язною!")

Власна агрегація

from pairwise_combinatorial import (
    combinatorial_method,
    simple_geometric_mean,
    weighted_arithmetic_mean,
    simple_arithmetic_mean,
)

# Використовуємо просте середнє геометричне
weights = combinatorial_method(
    A,
    n_workers=8,
    aggregator=simple_geometric_mean
)

# Використовуємо зважене середнє арифметичне
weights = combinatorial_method(
    A,
    n_workers=8,
    aggregator=weighted_arithmetic_mean
)

# Використовуємо просте середнє арифметичне
weights = combinatorial_method(
    A,
    n_workers=8,
    aggregator=simple_arithmetic_mean
)

Перевірка узгодженості

from pairwise_combinatorial import (
    combinatorial_method,
    calculate_consistency_ratio,
    generate_comparison_matrix,
)

A = generate_comparison_matrix(n=5)
weights = combinatorial_method(A)

cr = calculate_consistency_ratio(A, weights)
print(f"Коефіцієнт узгодженості: {cr:.4f}")

if cr < 0.10:
    print("Матриця має прийнятну узгодженість (за критерієм Сааті)")
else:
    print("Узгодженість матриці викликає сумніви")

Продуктивність

Бібліотека використовує послідовності Прюфера для ідеальної паралелізації:

• Розмір матриці n=5: ~125 остовних дерев, < 1 секунди
• Розмір матриці n=7: ~16,807 остовних дерев, ~1 секунда
• Розмір матриці n=8: ~262,144 остовних дерев, ~10 секунд (8 робочих процесів)
• Розмір матриці n=9: ~4,782,969 остовних дерев, ~3 хвилини (10 робочих процесів)

Продуктивність масштабується майже лінійно з кількістю робочих процесів до кількості критеріїв (n).

Деталі алгоритму

Комбінаторний метод:

1. Перераховує всі остовні дерева за допомогою послідовностей Прюфера
2. Для кожного дерева будує ідеально узгоджену МПП (ICPCM)
3. Обчислює вектори пріоритетів з кожної ICPCM
4. Агрегує всі вектори пріоритетів за допомогою середнього геометричного

Послідовності Прюфера забезпечують ідеальну паралелізацію через розподіл префіксів послідовностей між робочими процесами.

Ліцензія

MIT

Внесок

Внески вітаються! Будь ласка, не соромтеся відправляти Pull Request.

Цитування

Якщо ви використовуєте цю бібліотеку у своїх дослідженнях, будь ласка, процитуйте:

@software{pairwise_combinatorial,
  title = {Pairwise Combinatorial: Паралельний комбінаторний метод для агрегації парних порівнянь},
  author = {Your Name},
  year = {2024},
  url = {https://github.com/danolekh/pairwise_combinatorial}
}