Индекс Рэнда

Пример кластеризации набора данных с помощью алгоритмов kMeans (слева) и среднего сдвига (справа). Рассчитанный скорректированный индекс Рэнда для этих двух кластеров равен $ARI\approx 0.94$

Индекс Рэнда или мера Рэнда (названная в честь Уильяма М. Рэнда) в статистике и, в частности, в кластеризации данных , является мерой сходства между двумя кластеризациями данных . Может быть определена форма индекса Рэнда, адаптированная к случайной группировке элементов, это скорректированный индекс Рэнда . Индекс Рэнда — это точность определения принадлежности ссылки внутри кластера или нет.

Индекс Рэнда

Определение

Учитывая набор ​ $n$ элементы $S=\{o_{1},\ldots ,o_{n}\}$ и перегородки две $S$ сравнивать, $X=\{X_{1},\ldots ,X_{r}\}$, разбиение S на r подмножества и $Y=\{Y_{1},\ldots ,Y_{s}\}$, разбиение S на s подмножеств, определяют следующее:

• $a$, количество пар элементов в $S$ которые находятся в одном подмножестве в $X$ и в том же подмножестве в $Y$
• $b$, количество пар элементов в $S$ которые находятся в разных подмножествах $X$ и в разных подмножествах в $Y$
• $c$, количество пар элементов в $S$ которые находятся в одном подмножестве в $X$ и в разных подмножествах в $Y$
• $d$, количество пар элементов в $S$ которые находятся в разных подмножествах $X$ и в том же подмножестве в $Y$

Индекс Рэнда, $R$, является:

$R={\frac {a+b}{a+b+c+d}}={\frac {a+b}{n \choose 2}}$

Интуитивно, $a+b$ можно рассматривать как количество соглашений между $X$ и $Y$ и $c+d$ как количество разногласий между $X$ и $Y$.

Поскольку знаменателем является общее количество пар, индекс Рэнда представляет частоту появления соглашений по общему количеству пар, или вероятность того, что $X$ и $Y$договоримся о случайно выбранной паре.

${n \choose 2}$ рассчитывается как $n(n-1)/2$.

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

$RI={\frac {TP+TN}{TP+FP+FN+TN}}$

где $TP$ количество истинных положительных результатов, $TN$ количество истинных негативов , $FP$ - количество ложных срабатываний , и $FN$ это количество ложноотрицательных результатов .

Характеристики

Индекс Рэнда имеет значение от 0 до 1, где 0 указывает, что две кластеризации данных не согласуются ни по одной паре точек, а 1 указывает, что кластеризации данных абсолютно одинаковы.

В математических терминах a, b, c, d определяются следующим образом:

• $a=|S^{*}|$, где $S^{*}=\{(o_{i},o_{j})\mid o_{i},o_{j}\in X_{k},o_{i},o_{j}\in Y_{l}\}$
• $b=|S^{*}|$, где $S^{*}=\{(o_{i},o_{j})\mid o_{i}\in X_{k_{1}},o_{j}\in X_{k_{2}},o_{i}\in Y_{l_{1}},o_{j}\in Y_{l_{2}}\}$
• $c=|S^{*}|$, где $S^{*}=\{(o_{i},o_{j})\mid o_{i},o_{j}\in X_{k},o_{i}\in Y_{l_{1}},o_{j}\in Y_{l_{2}}\}$
• $d=|S^{*}|$, где $S^{*}=\{(o_{i},o_{j})\mid o_{i}\in X_{k_{1}},o_{j}\in X_{k_{2}},o_{i},o_{j}\in Y_{l}\}$

для некоторых $1\leq i,j\leq n,i\neq j,1\leq k,k_{1},k_{2}\leq r,k_{1}\neq k_{2},1\leq l,l_{1},l_{2}\leq s,l_{1}\neq l_{2}$

Связь с точностью классификации

Индекс Рэнда также можно рассматривать через призму точности двоичной классификации пар элементов в $S$. Две метки класса: " $o_{i}$ и $o_{j}$ находятся в одном подмножестве в $X$ и $Y$" и " $o_{i}$ и $o_{j}$ находятся в разных подмножествах $X$ и $Y$".

В этой обстановке $a$ — это количество пар, правильно помеченных как принадлежащие к одному и тому же подмножеству ( истинные положительные результаты ), и $b$ — это количество пар, правильно помеченных как принадлежащие к разным подмножествам ( истинно отрицательные значения ).

Скорректированный индекс Рэнда

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

Хотя индекс Рэнда может давать значение только от 0 до +1, скорректированный индекс Рэнда может давать отрицательные значения, если индекс меньше ожидаемого.

Таблица непредвиденных обстоятельств

Дан набор S из n элементов и две группы или разделы ( например, кластеризации) этих элементов, а именно $X=\{X_{1},X_{2},\ldots ,X_{r}\}$ и $Y=\{Y_{1},Y_{2},\ldots ,Y_{s}\}$, совпадение между X и Y можно свести в таблицу непредвиденных обстоятельств. $\left[n_{ij}\right]$ где каждая запись $n_{ij}$ обозначает количество объектов, общих между $X_{i}$ и $Y_{j}$ : $n_{ij}=|X_{i}\cap Y_{j}|$.

${\begin{array}{c|cccc|c}{{} \atop X}\!\diagdown \!^{Y}&Y_{1}&Y_{2}&\cdots &Y_{s}&{\text{sums}}\\\hline X_{1}&n_{11}&n_{12}&\cdots &n_{1s}&a_{1}\\X_{2}&n_{21}&n_{22}&\cdots &n_{2s}&a_{2}\\\vdots &\vdots &\vdots &\ddots &\vdots &\vdots \\X_{r}&n_{r1}&n_{r2}&\cdots &n_{rs}&a_{r}\\\hline {\text{sums}}&b_{1}&b_{2}&\cdots &b_{s}&\end{array}}$

Определение

Исходный скорректированный индекс Рэнда с использованием модели перестановок равен

$ARI={\frac {\left.\sum _{ij}{\binom {n_{ij}}{2}}-\left[\sum _{i}{\binom {a_{i}}{2}}\sum _{j}{\binom {b_{j}}{2}}\right]\right/{\binom {n}{2}}}{\left.{\frac {1}{2}}\left[\sum _{i}{\binom {a_{i}}{2}}+\sum _{j}{\binom {b_{j}}{2}}\right]-\left[\sum _{i}{\binom {a_{i}}{2}}\sum _{j}{\binom {b_{j}}{2}}\right]\right/{\binom {n}{2}}}}$

где $n_{ij},a_{i},b_{j}$ являются значениями из таблицы сопряженности.

См. также

• Простой коэффициент соответствия

Внешние ссылки

• Реализация C++ с файлами MATLAB mex