Преференциальная медиана набора интервалов

Если термины «ранжирование», «правило Борда», «правило Кемени» незнакомы — начните со страницы «Теория»: там основа метода и демонстрация, в которой можно проголосовать самому.

Задача

Есть m результатов измерения одной величины. Каждый задан центром x_k и стандартной неопределённостью u_k, то есть интервалом

Нужно одно значение — консенсус — и его неопределённость. Результаты могут противоречить друг другу: одни смещены, у других неопределённость занижена.

Идея за минуту

Каждый интервал «голосует»: значения внутри него он считает более правдоподобными, чем значения снаружи. Голоса всех интервалов сводятся в общее ранжирование правилом Борда. Победители — значения, которые предпочитает наибольшее число интервалов; их медиана и есть преференциальная медиана (ПМ).

Важное следствие: каждый интервал даёт ровно один голос, как бы узок он ни был. Результат с заниженной неопределённостью не получает большого веса, в отличие от взвешенного среднего.

Алгоритм по шагам

Посмотрите вживую: нажимайте «Далее», а интервалы можно двигать мышью на любом шаге.

1. Диапазон актуальных значений (ДАЗ) A = {a₁ < a₂ < … < a_n} — n равноотстоящих дискретных значений от a₁ = min_k x_k^н до a_n = max_k x_k^в, где x_k^н = x_k − u_k и x_k^в = x_k + u_k — нижняя и верхняя границы интервала. Соседние значения отстоят на норму разбиения h = (a_n − a₁) / (n − 1). Число значений по умолчанию выбирают так, чтобы в каждый интервал попало хотя бы одно: n = max(⌈(a_n − a₁) / min_k 2u_k⌉, 11).
2. Инранжирования. Интервал I_k делит ДАЗ на A_k = {a_i ∈ A | a_i ∈ I_k} и остальные значения A \ A_k. Значения из A_k строго предпочтительнее остальных, внутри каждой группы значения равноценны: λ_k = A_k ≻ A \ A_k. Такое ранжирование называют инранжированием, набор Λ(m, n) = {λ₁, …, λ_m} — профилем.
3. Агрегирование правилом Борда. Строится взвешенная турнирная матрица S = [s_ij] размера n × n: s_ij = Σ_k=1^m C_ij^k, где C_ij^k = 2, если в λ_k a_i ≻ a_j; 1, если a_i ~ a_j; 0, если a_j ≻ a_i; s_ii = 0. Счёт Борда значения a_i — строковая сумма z_i = Σ_j=1ⁿ s_ij. Для профилей инранжирований правила Кемени и Борда дают одну и ту же ПМ, поэтому используется правило Борда с полиномиальной сложностью.
4. Победители. A_best = {a_i | z_i = max_j z_j}, p = |A_best|. Если номера победителей идут не подряд, ПМ при данном n не определена: n увеличивается на единицу и шаги 1–4 повторяются. В реализациях на сайте n не превышает 201; дальше берётся самый широкий блок подряд идущих победителей.
5. Преференциальная медиана — выборочная медиана победителей, упорядоченных по возрастанию: x_pm = a_(p+1)/2 при нечётном p и (a_p/2 + a_p/2+1) / 2 при чётном (номера — внутри A_best).

Быстрый подсчёт

Пусть сводный индикатор c_i — число интервалов, содержащих a_i. Тогда

Первое слагаемое от i не зависит. Значит, победители Борда — значения, накрытые наибольшим числом интервалов, а счёт вычисляется за O(m·n) вместо O(m·n²) — без построения матрицы S. Обе формы дают один результат; в калькуляторе пошаговый разбор показывает c_i и z_i для ваших данных.

Неопределённость результата

ПМ — одно из дискретных значений ДАЗ или середина двух соседних, поэтому её точность ограничена нормой разбиения. Консервативная интервальная оценка — граница ±0,5h. Стандартная неопределённость в духе GUM получается, если приблизить погрешность симметричным треугольным распределением с полушириной h:

Оценка строится по конечной выборке, поэтому в реализациях на сайте к ней квадратически добавляется стандартная ошибка медианы центров интервалов — это наше дополнение, в статьях о методе его нет:

где MAD — медиана абсолютных отклонений центров x_k от их медианы; 1,4826·MAD — робастная оценка стандартного отклонения, 1,2533 = √(π/2) переводит её в стандартную ошибку медианы.

Версии метода

Метод развивается в двух направлениях: каким правилом агрегировать профиль (точное, но NP-трудное правило Кемени или полиномиальное правило Борда) и уточнять ли результат повторно.

β — ранжирование консенсуса; u* — граница интервальной неопределённости результата комплексирования x*; W — число выполненных циклов самоуточнения (его определяет условие остановки); h₀ — норма разбиения исходного ДАЗ. Правило Борда не гарантирует точного ранжирования консенсуса β, но для профилей инранжирований даёт ту же преференциальную медиану, что и правило Кемени. Стандартная неопределённость ПМ — u_pm ≈ 0,41h (см. выше).

Самоуточнение

Циклы нумеруются w = 1, 2, …; величины цикла w отмечены индексом w, исходный расчёт — цикл 0.

1. Новый ДАЗ вокруг результата. a₁^w = x*_w−1 − 0,5h_w−1, a_n^w = x*_w−1 + 0,5h_w−1; он разбивается на n_w = 11 значений, поэтому h_w = 0,1h_w−1.
2. Новый профиль. Интервалы, не пересекающие новый ДАЗ, удаляются, оставшиеся перенумеровываются (m = m_w) и заново представляются инранжированиями λ_k^w; получается профиль Λ^w.
3. Уточнённый результат. Ранжирование консенсуса нового профиля даёт результат x*_w. Циклы продолжаются, пока выполняется условие остановки — оно сравнивает длину нового ДАЗ с длинами его пересечений с интервалами. После W циклов результат x*_W, его неопределённость ±0,5h_W = ±0,5·10^−Wh₀.

Обозначения: в статьях о преференциальной медиане результат обозначается x_pm, его неопределённость — u_pm; в ранних работах и презентациях результат комплексирования — x*, неопределённость — u*.

Псевдокод

function preferential_median(x[1..m], u[1..m]):
    lo = x − u;  hi = x + u                   # границы интервалов I_k
    a1 = min(lo);  an = max(hi)               # границы ДАЗ
    n  = max(ceil((an − a1) / min(hi − lo)), 11)
    loop:
        h = (an − a1) / (n − 1)               # норма разбиения
        a[i] = a1 + (i − 1)·h,  i = 1..n
        c[i] = число k, для которых lo[k] ≤ a[i] ≤ hi[k]   # сводный индикатор
        A_best = { i : c[i] = max(c) }          # победители Борда
        if A_best — подряд идущие номера or n ≥ 201:
            (если не подряд — самый широкий блок подряд идущих номеров)
            x_pm = median(a[A_best])
            u    = sqrt((0.41·h)² + (1.2533·1.4826·MAD(x)/sqrt(m))²)
            return x_pm, u
        n = n + 1

Это алгоритм 2 из статьи Muravyov et al., Int. J. Data Sci. Anal., 2026 (doi:10.1007/s41060-026-01222-6) в сокращённой записи. В статье победители находятся по суммам строк z_i турнирной матрицы S; здесь — по сводному индикатору c_i. Это то же самое: для инранжирований z_i = Σ_k(n − |A_k| − 1) + n·c_i, первое слагаемое одинаково для всех i. Предел n ≤ 201 и выборочная составляющая неопределённости — дополнения реализаций на сайте; в статье u_pm = 0,41h.

Готовые реализации на пяти языках — на странице «Код».

От норм к расписанию

IF&PA применяют и там, где результат — не измерение, а норма для планирования. Цепочка такая: история выполнения работ → норма трудоёмкости → потребность каждой части работы в ресурсах → календарный план минимального срока. Ошибка на первом шаге переходит в план, поэтому норма должна быть устойчивой к засорённой истории.

1. Норма трудоёмкости по истории

Норма b — сколько смен уходит на единицу объёма. По каждому наблюдению известны фактическая длительность T_k и выполненный объём V_k; их отношение T_k/V_k — частная оценка нормы. Отношения обычно кучные, но задержки (непогода, простои, ожидание материалов) дают редкие большие значения, и всегда в одну сторону. Среднее и оценки, которые отталкиваются от медианы, такая односторонняя засорённость смещает вверх.

В IF&PA каждое отношение становится интервалом [T_k/V_k − u; T_k/V_k + u] с полушириной u = κ·MAD, где MAD — медиана абсолютных отклонений отношений, κ — множитель ширины. Норма — преференциальная медиана этих интервалов. Норма зависит от месяца: зимой одни и те же работы идут дольше, поэтому её оценивают отдельно по каждой паре «работа × месяц».

2. Месяц — задача о рюкзаке

Работу делят на захватки — части на участках трассы. Захватка j требует r_j = b_j·V_j смен. За месяц бригады могут отработать R смен — это вместимость «рюкзака». Решение x_j = 1, если захватка взята в месяц:

Ресурсов обычно несколько — бригады, техника, материалы, — и помещаться нужно по каждому: Σ_j r_j^lx_j ≤ R^l для каждого типа ресурса l. Это многомерный рюкзак. Задача NP-трудна, но при размерах, типичных для проекта, решается точно методом ветвей и границ.

3. Проект — цепочка месяцев-рюкзаков

Календарный план — это набор рюкзаков, по одному на каждый месяц t = 1, …, H, связанных порядком работ. Решение x_jt = 1 ставит захватку j в месяц t; потребность r_jt^l зависит от месяца через сезонную норму. Наименьший срок

и порядок соблюдён: захватка последующей работы на участке — не раньше предыдущей. Выполнимость при заданном H проверяет целочисленный решатель, а наименьший H находят перебором или бисекцией от ресурсной нижней границы.

4. Почему важна точная и несмещённая норма

• Заниженная норма. В месяц «помещается» больше работы, чем бригады успеют на деле: план короче, но при исполнении месяцы перегружены, и срок срывается.
• Завышенная норма. План выполним, но длиннее необходимого — скрытый резерв, который никто не видит и не использует.

Поэтому оценку нормы выбирают не только по разбросу, но и по смещению. Пошаговое объяснение с рюкзаком — в интерактивной лекции, полная модель с несколькими ресурсами, сезонными нормами и точным решателем — в Планировщике.

Обозначения

Чем ПМ отличается от похожих оценок

На каких данных какая оценка точнее — проверьте в конфигураторе применимости.

Первоисточники

• Muravyov S.V., Khudonogova L.I., Emelyanova E.Yu. Interval data fusion with preference aggregation // Measurement. 2018. Vol. 116. P. 621–630. DOI: 10.1016/j.measurement.2017.08.045
• Muravyov S.V., Khudonogova L.I., Ho M.D. Analysis of heteroscedastic measurement data by the self-refining method of interval fusion with preference aggregation – IF&PA // Measurement. 2021. Vol. 183. Art. 109851. DOI: 10.1016/j.measurement.2021.109851.
• Muravyov S.V., Khudonogova L.I., Shabramov V.S., Ignatyev V.D. Comparative studies of preferential and weighted medians accuracy in robust estimation of central tendency // International Journal of Data Science and Analytics. 2026. Vol. 22, No. 1. Art. 262. DOI: 10.1007/s41060-026-01222-6.
• Muravyov S.V., Khudonogova L.I., Shabramov V.S., Ignatyev V.D., Andreyev D.I. Kemeny and Borda rules in constructing central tendency estimators based on the preferential median // Proc. AISP'25. 2025. DOI: 10.1109/AISP68263.2025.11396113.

Все публикации →