Индекс Рэнда

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

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

Индекс Рэнда [ править ]

Определение [ править ]

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

• ${\ displaystyle a}$, Число пар элементов , которые находятся в той же подгруппе в и в то же подмножество в${\ displaystyle S}$${\ displaystyle X}$${\ displaystyle Y}$
• ${\ displaystyle b}$, количество пар элементов в, которые находятся в разных подмножествах и в разных подмножествах в${\ displaystyle S}$${\ displaystyle X}$${\ displaystyle Y}$
• ${\ displaystyle c}$, количество пар элементов, которые находятся в одном подмножестве и в разных подмножествах в${\ displaystyle S}$${\ displaystyle X}$${\ displaystyle Y}$
• ${\ displaystyle d}$, количество пар элементов в, которые находятся в разных подмножествах и в одном подмножестве в${\ displaystyle S}$${\ displaystyle X}$${\ displaystyle Y}$

Индекс Рэнда : ^{[1] [2]}${\ displaystyle R}$

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

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

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

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

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

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

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

Свойства [ править ]

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

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

• ${\displaystyle a=|S^{*}|}$, куда ${\displaystyle S^{*}=\{(o_{i},o_{j})\mid o_{i},o_{j}\in X_{k},o_{i},o_{j}\in Y_{l}\}}$
• ${\displaystyle b=|S^{*}|}$, куда ${\displaystyle 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}}\}}$
• ${\displaystyle c=|S^{*}|}$, куда ${\displaystyle 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}}\}}$
• ${\displaystyle d=|S^{*}|}$, куда ${\displaystyle 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}\}}$

для некоторых ${\displaystyle 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}}$

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

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

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

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

Скорректированный индекс Rand - это скорректированная версия индекса Rand. ^{[1] [2] [3]} Такая поправка на случайность устанавливает базовый уровень, используя ожидаемое сходство всех парных сравнений между кластерами, заданными случайной моделью. Традиционно индекс Rand корректировался с использованием модели перестановки для кластеризации (количество и размер кластеров в кластере фиксированы, и все случайные кластеры генерируются путем перетасовки элементов между фиксированными кластерами). Однако предпосылки модели перестановки часто нарушаются; во многих сценариях кластеризации количество кластеров или их распределение по размеру сильно различаются. Например, рассмотрим, что в K-среднихколичество кластеров фиксируется практикующим специалистом, но размеры этих кластеров выводятся из данных. Вариации скорректированного индекса Rand учитывают разные модели случайных кластеров. ^[4]

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

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

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

${\displaystyle {\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}}}$

Определение [ править ]

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

${\displaystyle 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}}}}}$

где - значения из таблицы непредвиденных обстоятельств.${\displaystyle n_{ij},a_{i},b_{j}}$

См. Также [ править ]

• Коэффициент простого соответствия

Ссылки [ править ]

Внешние ссылки [ править ]

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