Индекс Rand

Примеры кластеризации для набора данных с kMeans (слева) и Средний сдвиг (справа) алгоритмы. Рассчитанный скорректированный индекс Rand для этих двух кластеров равен

{displaystyle ARIapprox 0.94}

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

Определение

Учитывая набор из ${displaystyle n}$ элементы ${displaystyle S = {o_ {1}, ldots, o_ {n}}}$ и два перегородки из ${displaystyle S}$ сравнивать, ${displaystyle X = {X_ {1}, ldots, X_ {r}}}$ , раздел S в р подмножества и ${displaystyle Y = {Y_ {1}, ldots, Y_ {s}}}$ , раздел S в 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}$

Индекс Рэнда, ${displaystyle R}$ , является:^[1]^[2]

{displaystyle R = {frac {a + b} {a + b + c + d}} = {frac {a + b} {n выберите 2}}}

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

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

${displaystyle {n choose 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}) в середине o_ {i}, o_ {j} в X_ {k}, o_ {i}, o_ {j} в Y_ {l} }}$
${displaystyle b = | S ^ {*} |}$ , куда ${displaystyle S ^ {*} = {(o_ {i}, o_ {j}) в середине o_ {i} в X_ {k_ {1}}, o_ {j} в X_ {k_ {2}}, o_ {i } в Y_ {l_ {1}}, o_ {j} в Y_ {l_ {2}}}}$
${displaystyle c = | S ^ {*} |}$ , куда ${displaystyle S ^ {*} = {(o_ {i}, o_ {j}) в середине o_ {i}, o_ {j} в X_ {k}, o_ {i} в Y_ {l_ {1}}, o_ {j} в Y_ {l_ {2}}}}$
${displaystyle d = | S ^ {*} |}$ , куда ${displaystyle S ^ {*} = {(o_ {i}, o_ {j}) в середине o_ {i} в X_ {k_ {1}}, o_ {j} в X_ {k_ {2}}, o_ {i }, o_ {j} в Y_ {l}}}$

для некоторых ${displaystyle 1leq i, jleq n, ieq j, 1leq k, k_ {1}, k_ {2} leq r, k_ {1} eq k_ {2}, 1leq l, l_ {1}, l_ {2} leq s , l_ {1} экв 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 - это версия индекса Rand с поправкой на случайность.^[1]^[2]^[3] Такая поправка на случайность устанавливает базовый уровень, используя ожидаемое подобие всех парных сравнений между кластеризациями, заданными случайной моделью. Традиционно индекс Rand корректировался с использованием модели перестановки для кластеризации (количество и размер кластеров в кластере фиксированы, и все случайные кластеры генерируются путем перетасовки элементов между фиксированными кластерами). Однако посылки модели перестановок часто нарушаются; во многих сценариях кластеризации количество кластеров или их распределение по размеру сильно различаются. Например, рассмотрим, что в K-означает количество кластеров фиксируется практикующим специалистом, но размеры этих кластеров выводятся из данных. Вариации скорректированного индекса Rand учитывают разные модели случайных кластеров.^[4]

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

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

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