Medcouple - Medcouple

Гистограмма 5000 случайных значений, выбранных из перекоса гамма-распределение выше, и соответствующая гистограмма значений ядра medcouple ниже. Фактическая medcouple - это медиана нижнего распределения, отмеченная желтой линией как 0,188994.

В статистика, то медицинская пара это надежная статистика это измеряет перекос из одномерное распределение.^[1] Он определяется как масштабированная медианная разница левой и правой половины распределения. Его надежность делает его пригодным для идентификации выбросы в скорректированные коробчатые участки.^[2][3] Обычный коробчатые участки плохо справляются с асимметричным распределением, поскольку они помечают более длинные несимметричные хвосты как выбросы. Используя medcouple, усы коробчатой ​​диаграммы можно отрегулировать для асимметричных распределений и, таким образом, получить более точную идентификацию выбросов для несимметричных распределений.

Как своего рода статистика заказов, медпара относится к классу неполных обобщенных L-статистика.^[1] Как обычный медиана или же иметь в виду, медпара - это непараметрическая статистика, поэтому его можно вычислить для любого распределения.

Определение

Чтобы гармонировать с индексация с нуля во многих языках программирования мы будем индексировать с нуля все последующее.

Позволять ${\displaystyle X:=\{x_{0}\geq x_{1}\geq \ldots \geq x_{n-1}\}}$ быть заказанным образцом размера ${\displaystyle n}$, и разреши ${\displaystyle x_{m}}$ быть медиана из ${\displaystyle X}$. Определите наборы

${\displaystyle X^{+}:=\{x_{i}~|~x_{i}\geq x_{m}\}}$,

${\displaystyle X^{-}:=\{x_{j}~|~x_{j}\leq x_{m}\}}$,

размеров ${\displaystyle p:=|X^{+}|}$ и ${\displaystyle q:=|X^{-}|}$ соответственно. За ${\displaystyle x_{i}^{+}\in X^{+}}$ и ${\displaystyle x_{j}^{-}\in X^{-}}$, мы определяем функция ядра

${\displaystyle h(x_{i}^{+},x_{j}^{-}):={\begin{cases}\displaystyle {\frac {(x_{i}^{+}-x_{m})-(x_{m}-x_{j}^{-})}{x_{i}^{+}-x_{j}^{-}}}&{\text{ if }}x_{i}^{+}>x_{j}^{-},\\\operatorname {signum} (p-1-i-j)&{\text{ if }}x_{i}^{+}=x_{m}=x_{j}^{-},\end{cases}}}$

куда ${\displaystyle \operatorname {signum} }$ это функция знака.

В медицинская пара тогда является медианой множества^[1]:998

${\displaystyle \{h(x_{i}^{+},x_{j}^{-})~|~x_{i}^{+}\in X^{+}{\text{ and }}x_{j}^{-}\in X^{-}\}}$.

Другими словами, мы разделяем распределение на все значения, большие или равные медиане, и все значения, меньшие или равные медиане. Мы определяем функцию ядра, первая переменная которой находится над ${\displaystyle p}$ большие значения и вторая переменная которого превышает ${\displaystyle q}$ меньшие значения. Для частного случая значений, связанных с медианой, мы определяем ядро ​​как сигнум функция. Тогда медпара - это медиана по всем ${\displaystyle pq}$ ценности ${\displaystyle h(x_{i}^{+},x_{j}^{-})}$.

Поскольку медиана не применяется ко всем ${\displaystyle (x_{i},x_{j})}$ парам, но только тем, для которых ${\displaystyle x_{i}^{+}\geq x_{m}\geq x_{j}^{-}}$, он принадлежит к классу неполных обобщенных L-статистика.^[1]:998

Свойства медпары

Medcouple имеет ряд желательных свойств. Некоторые из них напрямую унаследованы от функции ядра.

Ядро medcouple

Сделаем следующие наблюдения о функции ядра ${\displaystyle h(x_{i}^{+},x_{j}^{-})}$:

1. Функция ядра не зависит от местоположения.^[1]:999 Если мы добавим или вычтем какое-либо значение к каждому элементу выборки ${\displaystyle X}$, соответствующие значения функции ядра не меняются.
2. Ядерная функция масштабно инвариантна.^[1]:999 Равномерное масштабирование всех элементов образца ${\displaystyle X}$ не изменяет значения функции ядра.

Эти свойства в свою очередь наследуются медицинской парой. Таким образом, медицинская пара не зависит от иметь в виду и стандартное отклонение распределения, желаемое свойство для измерения перекос.Для простоты вычислений эти свойства позволяют нам определить два набора

${\displaystyle Z^{+}:=\left.\left\{{\frac {x_{i}^{+}-x_{m}}{r}}~\right|~x_{i}^{+}\in X^{+}\right\}}$

${\displaystyle Z^{-}:=\left.\left\{{\frac {x_{j}^{-}-x_{m}}{r}}~\right|~x_{j}^{-}\in X^{-}\right\}}$

куда ${\displaystyle r=2\max _{0\leq i\leq n-1}|x_{i}|}$. Это делает набор ${\displaystyle Z:=Z^{+}\cup Z^{-}}$ имеют классифицировать не более 1, медиана 0, и сохраните ту же пару, что и ${\displaystyle X}$.

За ${\displaystyle Z}$, ядро ​​medcouple сводится к

${\displaystyle h(z_{i}^{+},z_{j}^{-}):={\begin{cases}\displaystyle {\frac {z_{i}^{+}+z_{j}^{-}}{z_{i}^{+}-z_{j}^{-}}}&{\text{ if }}z_{i}^{+}>z_{j}^{-}\\\operatorname {signum} (p-1-i-j)&{\text{ if }}z_{i}^{+}=0=z_{j}^{-}\end{cases}}}$

Использование недавно измененного и измененного набора ${\displaystyle Z}$ мы можем наблюдать следующее.

3. Функция ядра находится между -1 и 1,^[1]:998 то есть, ${\displaystyle |h(z_{i}^{+},z_{j}^{-})|\leq 1}$. Это следует из обратное неравенство треугольника ${\displaystyle |a|-|b|\leq |a-b|}$ с ${\displaystyle a=z_{i}^{+}}$ и ${\displaystyle b=z_{j}^{-}}$ и тот факт, что ${\displaystyle z_{i}^{+}\geq 0\geq z_{j}^{-}}$.
4. Ядро medcouple ${\displaystyle h(z_{i}^{+},z_{j}^{-})}$ не убывает по каждой переменной.^[1]:1005 В этом можно убедиться с помощью частных производных ${\displaystyle {\frac {\partial h}{\partial z_{i}^{+}}}}$ и ${\displaystyle {\frac {\partial h}{\partial z_{j}^{-}}}}$, оба неотрицательны, так как ${\displaystyle z_{i}^{+}\geq 0\geq z_{j}^{-}}$.

Таким образом, с помощью свойств 1, 2 и 4 мы можем определить следующие матрица,

${\displaystyle H:=(h_{ij})=(h(z_{i}^{+},z_{j}^{-}))={\begin{pmatrix}h(z_{0}^{+},z_{0}^{-})&\cdots &h(z_{0}^{+},z_{q-1}^{-})\\\vdots &\ddots &\vdots \\h(z_{p-1}^{+},z_{0}^{-})&\cdots &h(z_{p-1}^{+},z_{q-1}^{-})\end{pmatrix}}.}$

Если мы отсортируем наборы ${\displaystyle Z^{+}}$ и ${\displaystyle Z^{-}}$ в порядке убывания, то матрица ${\displaystyle H}$ имеет отсортированные строки и отсортированные столбцы,^[1]:1006

${\displaystyle H={\begin{pmatrix}h(z_{0}^{+},z_{0}^{-})&\geq &\cdots &\geq &h(z_{0}^{+},z_{q-1}^{-})\\\geq &&&&\geq \\\vdots &&\ddots &&\vdots \\\geq &&&&\geq \\h(z_{p-1}^{+},z_{0}^{-})&\geq &\cdots &\geq &h(z_{p-1}^{+},z_{q-1}^{-})\end{pmatrix}}.}$

Тогда medcouple - это медиана этой матрицы с отсортированными строками и отсортированными столбцами. Тот факт, что строки и столбцы отсортированы, позволяет реализовать быстрый алгоритм для расчета медпары.

Надежность

В точка разрушения - это количество значений, которым статистика может сопротивляться, прежде чем она станет бессмысленной, то есть количество произвольно больших выбросов, которым набор данных ${\displaystyle X}$ может иметь до того, как значение статистики будет затронуто. Для медицинской пары точка разрушения составляет 25%, поскольку это медиана, принятая для пар. ${\displaystyle (x_{i},x_{j})}$ такой, что ${\displaystyle x_{i}\geq x_{m}\geq x_{j}}$.^[1]:1002

Значения

Как и все меры перекос, medcouple положителен для распределений, которые смещены вправо, отрицателен для распределений, смещенных влево, и равен нулю для симметричных распределений. Кроме того, значения medcouple ограничены 1 по абсолютной величине.^[1]:998

Алгоритмы расчета медпары

Перед тем, как представить алгоритмы медпары, напомним, что существуют ${\displaystyle O(n)}$ алгоритмы нахождения медианы. Поскольку медиана - это медиана, важны обычные алгоритмы нахождения медианы.

Наивный алгоритм

Наивный алгоритм для вычисления medcouple медленный.^[1]:1005 Это происходит в два этапа. Во-первых, он строит матрицу medcouple ${\displaystyle H}$ который содержит все возможные значения ядра medcouple. На втором этапе он находит медиану этой матрицы. Поскольку есть ${\displaystyle pq\approx {\frac {n^{2}}{4}}}$ записи в матрицу в случае, когда все элементы набора данных ${\displaystyle X}$ уникальны, алгоритмическая сложность наивного алгоритма ${\displaystyle O(n^{2})}$.

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

функция naïve_medcouple (вектор ИКС): // X - вектор размера n.        // Сортировку в порядке убывания можно выполнить на месте за время O (n log n)    sort_decreasing (X) xm: = медиана (X) xscale: = 2 * max (abs (X)) // Определяем верхний и нижний центрированные и масштабированные векторы    // они наследуют собственную убывающую сортировку X    Zplus: = [(x - xm) / xscale | Икс в Икс такой, что x> = xm] Zminus: = [(x - xm) / xscale | Икс в Икс такой, что x <= xm] p: = размер (Zplus) q: = размер (Zminus) // Определяем функцию ядра закрытие над Zplus и Zminus    функция h (i, j): a: = Zplus [i] b: = Zminus [j] если а == б: возвращаться сигнум (п - 1 - я - к) еще:            возвращаться (а + б) / (а - б) endif    конечная функция        // O (n ^ 2) операций, необходимых для формирования этого вектора    H: = [h (i, j) | я в [0, 1, ..., p - 1] и j в [0, 1, ..., q - 1]] возвращаться медиана (H)конечная функция

Последний призыв к медиана на векторе размера ${\displaystyle O(n^{2})}$ можно сделать сам в ${\displaystyle O(n^{2})}$ операций, следовательно, весь наивный алгоритм medcouple имеет такую ​​же сложность.

Быстрый алгоритм

Быстрый алгоритм превосходит наивный алгоритм за счет использования отсортированного характера матрицы медицинских пар. ${\displaystyle H}$. Вместо вычисления всех элементов матрицы быстрый алгоритм использует K^th парный алгоритм Джонсона и Мизогучи.^[4]

Первый этап быстрого алгоритма продолжается как наивный алгоритм. Сначала мы вычисляем необходимые ингредиенты для матрицы ядра, ${\displaystyle H=(h_{ij})}$, с отсортированными строками и отсортированными столбцами в порядке убывания. Вместо того, чтобы вычислять все значения ${\displaystyle h_{ij}}$, вместо этого мы используем монотонность строк и столбцов с помощью следующих наблюдений.

Сравнение значения с матрицей ядра

Прежде всего отметим, что мы можем сравнивать любые ${\displaystyle u}$ со всеми ценностями ${\displaystyle h_{ij}}$ из ${\displaystyle H}$ в ${\displaystyle O(n)}$ время.^[4]:150 Например, для определения всех ${\displaystyle i}$ и ${\displaystyle j}$ такой, что ${\displaystyle h_{ij}>u}$, у нас есть следующая функция:

     функция больше_ч(ядро час, int п, int q, настоящий ты):         // h - функция ядра, h (i, j) дает i-ю, j-ю запись H         // p и q - количество строк и столбцов матрицы ядра H                  // вектор размера p         п := вектор(п)                  // индексация с нуля         j := 0                  // начиная снизу, вычисляем [[супремум | наименьшую верхнюю границу]] для каждой строки         за я := п - 1, п - 2, ..., 1, 0:                               // ищем в этой строке, пока не найдем значение меньше u             пока j < q и час(я, j) > ты:                 j := j + 1             в конце концов                          // запись, предшествующая найденной, больше, чем u             п[я] := j - 1         конец                  возвращаться п     конечная функция

Этот больше_ч функция проходит по матрице ядра от нижнего левого угла до верхнего правого и возвращает вектор ${\displaystyle P}$ индексов, указывающих для каждой строки, где проходит граница между значениями, превышающими ${\displaystyle u}$ и те, которые меньше или равны ${\displaystyle u}$. Этот метод работает из-за свойства сортировки по столбцам строк ${\displaystyle H=(h_{ij})}$. С больше_ч вычисляет самое большее ${\displaystyle p+q}$ ценности ${\displaystyle h_{ij}}$, его сложность ${\displaystyle O(n)}$.^[4]:150

Концептуально получившийся ${\displaystyle P}$ вектор можно визуализировать как устанавливающий границу на матрице, как показано на следующей диаграмме, где все красные элементы больше, чем ${\displaystyle u}$:

Симметричный алгоритм вычисления значений ${\displaystyle h_{ij}}$ меньше, чем ${\displaystyle u}$ очень похожа. Вместо этого он продолжается ${\displaystyle H}$ в обратном направлении, сверху справа налево:

     функция less_h(ядро час, int п, int q, настоящий ты):              // вектор размера p         Q := вектор(п)                  // последний возможный индекс строки         j := q - 1                  // начиная сверху, вычисляем [[infimum | точная нижняя граница]] для каждой строки         за я := 0, 1, ..., п - 2, п - 1:                      // ищем в этой строке, пока не найдем значение больше u             пока j >= 0 и час(я, j) < ты:                 j := j - 1             в конце концов                          // запись, следующая за той, которую мы только что нашли, меньше u             Q[я] := j + 1         конец                  возвращаться Q     конечная функция

Эту нижнюю границу можно визуализировать так, где синие записи меньше, чем ${\displaystyle u}$:

Для каждого ${\displaystyle i}$у нас есть это ${\displaystyle P_{i}\geq Q_{i}}$, причем строгое неравенство имеет место только для тех строк, которые имеют значения, равные ${\displaystyle u}$.

У нас также есть, что суммы

${\displaystyle \sum _{i=0}^{p-1}(P_{i}+1)~\qquad ~\sum _{i=0}^{p-1}Q_{i}}$

дают соответственно количество элементов ${\displaystyle H}$ которые больше, чем ${\displaystyle u}$, и количество элементов, которые больше или равны ${\displaystyle u}$. Таким образом, этот метод также дает классифицировать из ${\displaystyle u}$ внутри элементов ${\displaystyle h_{ij}}$ из ${\displaystyle H}$.^[4]:149

Средневзвешенная медиана медианы строк

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

В более общем плане, используя границы, заданные ${\displaystyle P}$ и ${\displaystyle Q}$ векторов из предыдущего раздела, мы можем предположить, что после некоторых итераций мы точно определили положение медицинской пары между красной левой границей и синей правой границей:^[4]:149

Желтые записи обозначают медианное значение каждой строки. Если мы мысленно перестроим строки так, чтобы медианы выровнялись и игнорировали отброшенные записи за пределами границ,

мы можем выбрать взвешенная медиана из этих медиан, каждая запись взвешивается по количеству оставшихся записей в этой строке. Это гарантирует, что мы можем отбросить не менее 1/4 всех оставшихся значений независимо от того, нужно ли отбрасывать большие значения красным или меньшие значения синим:

Медиана каждой строки может быть вычислена в ${\displaystyle O(1)}$ время, так как строки отсортированы, а взвешенная медиана можно вычислить в ${\displaystyle O(n)}$ раз, используя бинарный поиск.^[4]:148

K^th парный алгоритм

Визуализация алгоритма быстрой пары. Он начинается с матрицы с отсортированными строками и отсортированными столбцами, где темные квадраты меньше светлых. На каждой итерации желтым цветом выбирается взвешенная медиана медиан строк. Затем он сравнивается с остальной частью матрицы для получения возможных красных верхних и синих нижних границ. Затем алгоритм выбирает границу, которая, как известно, исключает медианную глобальную матрицу, учитывая количество записей, исключенных этой границей (что эквивалентно рассмотрению ранга желтой записи). Затем алгоритм продолжается до тех пор, пока желтая взвешенная медиана медиан строк не станет в точности медпарой или пока количество записей-кандидатов не станет достаточно маленьким, чтобы выполнить сортировку с выбором среди оставшихся записей.

Объединив эти два наблюдения, алгоритм быстрой медицинской пары в общих чертах работает следующим образом.^[4]:148

1. Вычислить необходимые ингредиенты для функции ядра medcouple ${\displaystyle h(i,j)}$ с ${\displaystyle p}$ отсортированные строки и ${\displaystyle q}$ отсортированные столбцы.
2. На каждой итерации аппроксимируйте медицинскую пару с взвешенная медиана медианы ряда.^[4]:148
3. Сравните это предварительное предположение со всей матрицей, получив правые и левые граничные векторы ${\displaystyle P}$ и ${\displaystyle Q}$ соответственно. Сумма этих векторов также дает нам классифицировать этой экспериментальной пары.
   1. Если ранг предварительной медицинской пары точно равен ${\displaystyle pq/2}$, затем остановись. Мы нашли медпару.
   2. В противном случае отбросьте записи больше или меньше, чем предварительное предположение, выбрав либо ${\displaystyle P}$ или же ${\displaystyle Q}$ в качестве новой правой или левой границы, в зависимости от того, с какой стороны элемент ранга ${\displaystyle pq/2}$ находится в. На этом шаге всегда отбрасывается не менее 1/4 всех оставшихся записей.
4. Как только количество кандидатов в медицинские пары между правой и левой границами станет меньше или равно ${\displaystyle p}$, выполнить выбор ранга среди оставшихся записей, так что ранг в этом меньшем наборе кандидатов соответствует ${\displaystyle pq/2}$ ранг медпары во всей матрице.

Первоначальная сортировка с целью формирования ${\displaystyle h(i,j)}$ функция принимает ${\displaystyle O(n\log n)}$ время. На каждой итерации взвешенная медиана принимает ${\displaystyle O(n)}$ время, а также вычисления нового ориентировочного ${\displaystyle P}$ и ${\displaystyle Q}$ левая и правая границы. Поскольку каждая итерация отбрасывает не менее 1/4 всех оставшихся записей, будет не более ${\displaystyle O(\log n)}$ итераций.^[4]:150 Таким образом, весь быстрый алгоритм занимает ${\displaystyle O(n\log n)}$ время.^[4]:150

Сформулируем более подробно быстрый алгоритм.

функция медпара (вектор ИКС): // X - вектор размера n        // Рассчитываем начальные ингредиенты как для наивная пара    sort_decreasing (X) xm: = медиана (X) xscale: = 2 * max (abs (X)) Zplus: = [(x - xm) / xscale | Икс в Икс такой, что x> = xm] Zminus: = [(x - xm) / xscale | Икс в Икс такой, что x <= xm] p: = размер (Zplus) q: = размер (Zminus) функция h (i, j): a: = Zplus [i] b: = Zminus [j] если а == б: возвращаться сигнум (п - 1 - я - к) еще:            возвращаться (а + б) / (а - б) endif    конечная функция        // Начать алгоритм пары K (Johnson & Mizoguchi)        // Начальные левая и правая границы, два вектора размера p    L: = [0, 0, ..., 0] R: = [q - 1, q - 1, ..., q - 1] // количество записей слева от левой границы    Ltotal: = 0 // количество записей слева от правой границы    Rtotal: = p * q // Поскольку мы индексируем с нуля, индекс medcouple равен единице    // меньше своего ранга.    medcouple_index: = этаж (Rtotal / 2) // Итерация, пока количество записей между границами равно    // больше, чем количество строк в матрице.    пока Rtotal - Ltotal> p: // Вычислить медианы строк и связанные с ними веса, но пропустить        // любые строки, которые уже пусты.        middle_idx: = [i | я в [0, 1, ..., p - 1] такой который L [i] <= R [i]] row_medians: = [h (i, этаж ((L [i] + R [i]) / 2) | я в middle_idx] веса: = [R [i] - L [i] + 1 | я в middle_idx] WM: = взвешенная медиана (row_medians, веса) // Новые ориентировочные правая и левая границы        P: = больше_ч (h, p, q, WM) Q: = less_h (h, p, q, WM) Ptotal: = sum (P) + size (P) Qtotal: = sum (Q) // Определяем, какие записи следует отбросить, или если мы нашли медицинскую пару        если medcouple_index <= Ptotal - 1: R: = P Rtotal: = Ptotal еще:            если medcouple_index> Qtotal - 1: L: = Q Ltotal: = Qtotal еще: // Найдена медицинская пара, ранг взвешенной медианы равен индексу медпары возвращаться WM endif        endif       в конце концов        // Не удалось найти медицинскую пару, но осталось очень мало пробных записей: = [h (i, j) | я в [0, 1, ..., p - 1], j в [L [i], L [i] + 1, ..., R [i]] такой который L [i] <= R [i]] // Выбираем медпару по рангу среди оставшихся записей    medcouple: = select_nth (Осталось, medcouple_index - Ltotal) возвращаться медицинская параконечная функция

В реальных условиях алгоритм также должен учитывать ошибки, связанные с конечной точностью. арифметика с плавающей запятой. Например, сравнения для функции ядра medcouple должны выполняться в машина эпсилон, а также сравнения порядков в то больше_ч и less_h функции.

Программное обеспечение / исходный код

• Алгоритм быстрой пары реализован в р с пакет robustbase.
• Алгоритм fast medcouple реализован в расширении C для Python в Пакет Python Robustats.
• Под лицензией GPL C ++ реализация быстрый алгоритм, полученный из реализации R.
• А Stata реализация быстрый алгоритм.
• Реализация наивный алгоритм в Matlab (и поэтому GNU Octave ).
• Наивный алгоритм реализован и для Python упаковка statsmodels.

Смотрите также

• Математический портал

• Надежная статистика
• Асимметрия
• Скорректированные коробчатые графики

Рекомендации

1. Brys, G .; Юбер, М.; Струйф, А. (ноябрь 2004 г.). «Надежная мера перекоса». Журнал вычислительной и графической статистики. 13 (4): 996–1017. Дои:10.1198 / 106186004X12632. МИСТЕР  2425170.
2. Hubert, M .; Вандервирен, Э. (2008). «Скорректированная коробчатая диаграмма для искаженных распределений». Вычислительная статистика и анализ данных. 52 (12): 5186–5201. Дои:10.1016 / j.csda.2007.11.008. МИСТЕР  2526585.
3. Пирсон, Рон (6 февраля 2011 г.). "Коробчатые сюжеты и не только - Часть II: Асимметрия". ИзучениеДанныхБлог. Получено 6 апреля, 2015.
4. Джонсон, Дональд Б.; Мидзогути, Тецуо (май 1978 г.). "Выбор K^th элемент в Икс + Y и Икс₁ + Икс₂ +...+ Икс_м". SIAM Журнал по вычислениям. 7 (2): 147–153. Дои:10.1137/0207013. МИСТЕР  0502214.