Расчет индекса ранда

Я пытаюсь выяснить, как рассчитать индекс Рэнда кластерного алгоритма, но я застрял в точке, как рассчитать истинные и ложные отрицания.

Сейчас я использую пример из книги «Введение в поиск информации» (Manning, Raghavan & Schütze, 2009). На странице 359 они говорят о том, как рассчитать индекс Рэнда. Для этого примера они используют три кластера, и кластеры содержат следующие объекты.

1. aaaaab
2. abbbbc
3. aaccc

Я заменяю объект (оригинальные знаки на буквы, но идея и количество остаются неизменными). Я приведу точные слова из книги, чтобы понять, о чем они говорят:

Сначала мы вычисляем TP + FP. Три кластера содержат 6, 6 и 5 баллов соответственно, поэтому общее количество «позитивов» или пар документов, которые находятся в одном кластере:

TP + FP = + +${6 \choose 2}$${6 \choose 2}$${5 \choose 2}$ = 15 + 15+ 10 = 40

Из них пары a в кластере 1, пары b в кластере 2, пары c в кластере 3 и пара a в кластере 3 являются истинными положительными значениями:

TP = + + + = 10 + 6 + 3 + 1 = 20${5 \choose 2}$${4 \choose 2}$${3 \choose 2}$${2 \choose 2}$

Таким образом, FP = 40 - 20 = 20.

До сих пор расчеты понятны, и если я беру другие примеры, я получаю те же результаты, но когда я хочу вычислить ложноотрицательный и истинно отрицательный Manning et al. заявить следующее:

FN и TN рассчитываются аналогично, что приводит к следующей таблице непредвиденных расходов:

Таблица непредвиденных расходов выглядит следующим образом:

+--------+--------+
| TP: 20 | FN: 24 |
+--------+--------+
| FP: 20 | TN: 72 |
+--------+--------+

Предложение: «FN и TN рассчитываются аналогично» не совсем понятно для меня, и я не понимаю, какие числа мне нужны для вычисления TN и FN. Я могу рассчитать правую часть таблицы, выполнив следующие действия:

TP + FP + FN + TN = = = 136${n \choose 2}$${17 \choose 2}$

Источник: http://en.wikipedia.org/wiki/Rand_index

Таким образом, FN + TN = 136 - TP + FP = 136 - 40 = 96, но это на самом деле не помогает мне понять, как вычислять переменные по отдельности. Особенно, когда авторы говорят: «FN и TN рассчитываются одинаково». Я не вижу как. Также, когда я смотрю на другие примеры, они вычисляют каждую ячейку таблицы сопряженности, просматривая каждую пару.

Например: http://www.otlet-institute.org/wikics/Clustering_Problems.html#toc-Subsection-4.1

Мой первый вопрос, основанный на примере Manning et al (2009), можно ли рассчитать TN и FN, если вы знаете только TP & NP? И если да, то как выглядит аналогичный расчет на основе приведенного примера?

Я размышлял о том же самом и решил это так. Предположим, у вас есть таблица совпадений / таблица непредвиденных обстоятельств, где строки - это кластеры наземных истин, а столбцы - кластеры, найденные алгоритмом кластеризации.

Итак, для примера в книге это будет выглядеть так:

  | 1 | 2 | 3
--+---+---+---
x | 5 | 1 | 2
--+---+---+---
o | 1 | 4 | 0
--+---+---+---
◊ | 0 | 1 | 3

Теперь вы можете очень легко вычислить TP + FP, взяв сумму на столбец и выбрав «2» для всех этих значений. Таким образом, суммы равны [6, 6, 5], и вы выбираете «6 выберите 2» + «6 выберите 2» + «5 выберите 2».

Теперь, действительно, аналогично, вы можете получить TP + FN, взяв сумму по строкам (то есть [8, 5, 4] в приведенном выше примере), применив «выбрать 2» для всех этих значений, и взять сумма этого.

Сами TP можно вычислить, применив «выбрать 2» к каждой ячейке в матрице и взяв сумму всего (предполагая, что «1 выбор 2» равен 0).

На самом деле, вот код Python, который делает именно это:

import numpy as np
from scipy.misc import comb

# There is a comb function for Python which does 'n choose k'                                                                                            
# only you can't apply it to an array right away                                                                                                         
# So here we vectorize it...                                                                                                                             
def myComb(a,b):
  return comb(a,b,exact=True)

vComb = np.vectorize(myComb)

def get_tp_fp_tn_fn(cooccurrence_matrix):
  tp_plus_fp = vComb(cooccurrence_matrix.sum(0, dtype=int),2).sum()
  tp_plus_fn = vComb(cooccurrence_matrix.sum(1, dtype=int),2).sum()
  tp = vComb(cooccurrence_matrix.astype(int), 2).sum()
  fp = tp_plus_fp - tp
  fn = tp_plus_fn - tp
  tn = comb(cooccurrence_matrix.sum(), 2) - tp - fp - fn

  return [tp, fp, tn, fn]

if __name__ == "__main__":
  # The co-occurrence matrix from example from                                                                                                           
  # An Introduction into Information Retrieval (Manning, Raghavan & Schutze, 2009)                                                                       
  # also available on:                                                                                                                                   
  # http://nlp.stanford.edu/IR-book/html/htmledition/evaluation-of-clustering-1.html                                                                     
  #                                                                                                                                                      
  cooccurrence_matrix = np.array([[ 5,  1,  2], [ 1,  4,  0], [ 0,  1,  3]])

  # Get the stats                                                                                                                                        
  tp, fp, tn, fn = get_tp_fp_tn_fn(cooccurrence_matrix)

  print "TP: %d, FP: %d, TN: %d, FN: %d" % (tp, fp, tn, fn)

  # Print the measures:                                                                                                                                  
  print "Rand index: %f" % (float(tp + tn) / (tp + fp + fn + tn))

  precision = float(tp) / (tp + fp)
  recall = float(tp) / (tp + fn)

  print "Precision : %f" % precision
  print "Recall    : %f" % recall
  print "F1        : %f" % ((2.0 * precision * recall) / (precision + recall))

Если я запускаю его, я получаю:

$ python testCode.py
TP: 20, FP: 20, TN: 72, FN: 24
Rand index: 0.676471
Precision : 0.500000
Recall    : 0.454545
F1        : 0.476190

На самом деле я не проверял никаких других примеров, кроме этого, поэтому я надеюсь, что сделал все правильно .... ;-)

После изучения других ответов в этой теме, вот моя реализация Python, которая принимает массивы в качестве входных данных, sklearn-style:

import numpy as np
from scipy.misc import comb

def rand_index_score(clusters, classes):

    tp_plus_fp = comb(np.bincount(clusters), 2).sum()
    tp_plus_fn = comb(np.bincount(classes), 2).sum()
    A = np.c_[(clusters, classes)]
    tp = sum(comb(np.bincount(A[A[:, 0] == i, 1]), 2).sum()
             for i in set(clusters))
    fp = tp_plus_fp - tp
    fn = tp_plus_fn - tp
    tn = comb(len(A), 2) - tp - fp - fn
    return (tp + tn) / (tp + fp + fn + tn)

In [319]: clusters
Out[319]: [0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2]

In [320]: classes
Out[320]: [0, 0, 1, 0, 0, 0, 0, 1, 1, 1, 2, 1, 0, 2, 2, 2, 0]

In [321]: rand_index_score(clusters, classes)
Out[321]: 0.67647058823529416

Я не совсем уверен, но вот как я сделал значение
TN : TN = (7 2) (10 2) (4 2)

(7 2) - кластер 1 - тест говорит «х», поэтому посчитайте те, которые НЕ х (и правильно сгруппированы в кластеры 2 и 3)

т.е. 4 'o's + 3' d (алмазы) = (7 2)

(10 2) - Кластер 2, подсчитайте те, которые НЕ 'и правильно сгруппированы в кластеры 1 и 3,

то есть 5 'x' + (2'x '+ 3'd') = (10 2)

(4 2) - Кластер 3, подсчитайте те, которые НЕ являются «x» и НЕ «d» (ромбовидный элемент), которые правильно сгруппированы в кластеры 1 и 2.

то есть 4 'в кластере 2. = (4 2)

TN = (7 2) + (10 2) + (4 2) = 72.

Тогда FN это:

FN = (17 2) - (TP + FP) - TN = 136 - 40 -72 = 24. ---> (17 = общее количество документов)

Возьмем пример другого вопроса:

  | 1 | 2 | 3
--+---+---+---
x | 5 | 1 | 2
--+---+---+---
o | 1 | 4 | 0
--+---+---+---
◊ | 0 | 1 | 3

Разумный ответ для ФН:

FN = (c(8,2)-c(5,2)-c(2,2))+(c(5,2)-c(4,2))+(c(4,2)-c(3,2))=24  

Объяснение:

• (С (8,2) -c (5,2) -c (2,2))

  выберите 2 из 8 для «x» (a) комбинацию одного и того же класса в одних и тех же кластерах (c (5,2) для кластера 1 и c (2,2) для кластера 3),

• (С (5,2) -c (4,2))

  выберите 2 из 5 'o' (b) минус комбинацию одного и того же класса в одних и тех же кластерах (c (4,2) для кластера 2)

• (С (4,2) -c (3,2)

  выберите 2 из 4 для «◇» (c) минус комбинацию одного и того же класса в одних и тех же кластерах (c (3,2) для кластера 3)

Я вывел это так.

У меня есть реализация этого в R, который я объясню:

TP (a в коде) - это сумма каждой ячейки, выбранной 2. Согласно исходному вопросу (0 или 1, выберите 2, что равно 0).

FN (b) - сумма каждой строки выбора 2, все суммированы, за вычетом TP. Где каждая сумма строк представляет количество документов в каждом классе True.

Сумма этого - все документы, которые похожи и находятся в одном кластере (TP), плюс все документы, которые похожи и не находятся в одном кластере (FN).

Так что это (TP + FN) - TP = FN

FP (c) рассчитывается аналогично. Сумму каждого столбца выбирают 2, все суммируются за вычетом TP. В этом случае каждый столбец сумма представляет количество документов в каждом кластере.

Таким образом, сумма всех документов, которые похожи и находятся в одном кластере (TP), плюс все документы, которые не похожи и находятся в одном кластере (FP).

Так что это (TP + FP) - TP = FP

С этими 3 рассчитанными оставшийся расчет TN является прямым. Сумму из таблицы выбирают 2, за вычетом TP, FP & FN = TN (d)

Единственный запрос, который я имею с этим методом, - это определение TP. Используя терминологию в этом вопросе, я не понимаю, почему 2 в кластере 3 считаются TP. Я нашел это и здесь, и в соответствующем учебнике. Тем не менее, я понимаю их расчеты с предположением, что их расчет TP является правильным.

Надеюсь это поможет

FMeasure = function (x, y, beta) 
{
  x <- as.vector(x)
  y <- as.vector(y)
  if (length(x) != length(y)) 
    stop("arguments must be vectors of the same length")
  tab <- table(x, y)
  if (all(dim(tab) == c(1, 1))) 
    return(1)
  a <- sum(choose(tab, 2))
  b <- sum(choose(rowSums(tab), 2)) - a
  c <- sum(choose(colSums(tab), 2)) - a
  d <- choose(sum(tab), 2) - a - b - c
  ## Precision
  P = a / (a + c)
  ## Recall
  R = a / (a + b)
  ##F-Measure
  Fm <- (beta^2 + 1) * P * R / (beta^2*P + R)
  return(Fm)
}

Вы можете вычислить TN и FN одинаково.

Просто поменяйте роли меток и кластеров .

a) 1 1 1 1 1 2 3 3
b) 1 2 2 2 2
c) 2 3 3 3 3

... затем выполните те же вычисления.

Я ДУМАЮ, что реверс-инжиниринг ложного негатива (FN) из этого. Для истинных положительных результатов вы сделали 4 группы, которые были положительными. В кластере 1 у вас было пять очков; в кластере 2 у вас было 4 б; в кластере 3 у вас было 3 с и 2 с.

Так что за ложный минус.

1. Начните с a в кластере 1; в кластере 1 есть 5 правильно размещенных a. В кластере 2 есть 1 ложное a, а в кластере 3 два ложных a, что дает (5 1) и (5 2).
2. Тогда для б. Есть 4 правильно размещенных б, которые вы рассчитали ранее. У вас есть один ложный b в кластере 1, и все. Это дает вам (4 1) для б.
3. Тогда для с. У вас есть один ложный c в кластере 2, с тремя правильными в кластере 3, так что есть (3 1).
4. После этого мы не можем забыть о той паре в кластере 3, которые мы назвали истинно положительными. Итак, что касается этого, у нас есть 1 ложное a в кластере 2. Даже если в кластере 1 есть другие a, мы не можем назвать их ложными a, потому что их так много.

Следовательно, у вас есть (5 1) + (5 2) + (4 1) + (3 1) + (2 1), что равняется 5 + 10 + 4 + 3 + 2 = 24. Отсюда 24 просто вычтите это из 136, которые вы уже нашли, чтобы получить истинный нег (TN).

Вот как можно рассчитать каждую метрику для индекса Рэнд без вычитания

Дополнительные примечания для облегчения понимания:

1) Индекс Рэнда основан на сравнении пар элементов. Теория предполагает, что подобные пары элементов должны быть размещены в одном кластере, в то время как разнородные пары элементов должны быть размещены в отдельных кластерах.

2) RI не заботится о разнице в количестве кластеров. Он просто заботится о парах True / False элементов.

На основании этого предположения рассчитывается индекс Рэнда

Хорошо, давайте погрузимся в наш пример:

  | 1 | 2 | 3
--+---+---+---
x | 5 | 1 | 2
--+---+---+---
o | 1 | 4 | 0
--+---+---+---
◊ | 0 | 1 | 3

В знаменателе у нас есть общее количество возможных пар, которое (17 2) = 136

Теперь давайте посчитаем каждую метрику для лучшего понимания:

A) Давайте начнем с простого a , ( True Positives или исправить подобное )

Это значит, что вам нужно найти все возможные пары элементов, в которых прогноз и истинная метка были размещены вместе. На примере сетки это означает получение суммы возможных пар в каждой ячейке.

a = (5 2) + (1 2) + (2 2) + (1 2) + (4 2) + (0 2) + (0 2) + (1 2) + (3 2) = 
  = 10 + 0 + 1 + 0 + 6 + 0 + 0 + 0 + 3 = 20

C) Теперь давайте сделаем c ( Ложные Позитивы или неправильные различия )

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

c = 5*1 + 5*2 + 1*2 + 
  + 1*4 + 1*0 + 4*0 + 
  + 0*1 + 0*3 + 1*3 = 
  = 5 + 10 + 2 + 4 + 0 + 0 + 0 + 0 + 3 = 24

D) Вычисление d ( False Negative или неправильный аналог ). Это значит, найти все пары, которые мы поместили в разные кластеры, но которые должны быть вместе. На примере сетки найдите все возможные пары между любыми 2 вертикальными ячейками

d = 5*1 + 5*0 + 1*0 + 
  + 1*4 + 1*1 + 4*1 + 
  + 2*0 + 2*3 + 0*3 = 
  = 5 + 0 + 0 + 4 + 1 + 4 + 0 + 6 + 0 = 20

Б) И, наконец, давайте сделаем б ( Истинные негативы или исправить несходные )

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

Вот то, какие числа должны быть умножены, чтобы лучше понять, что я имел в виду:

d = x1*o2 + x1*o3 + x1*◊2 + x1*◊3 + 
  + x2*o1 + x2*o3 + x2*◊1 + x2*◊3 + 
  + x3*o1 + x3*o2 + x3*◊1 + x3*◊2 + 
  + o1*◊2 + o1*◊3 + 
  + o2*◊1 + o2*◊3 + 
  + o3*◊1 + o3*◊2

В цифрах:

d = 5*4 + 5*0 + 5*1 + 5*3 + 
  + 1*1 + 1*0 + 1*0 + 1*3 + 
  + 2*1 + 2*4 + 2*0 + 2*1 + 
  + 1*1 + 1*3 +
  + 4*0 + 4*3 = 72

И в конце индекс Рэнда равен: (20 + 72) / 136 = 0.676

Ниже изображение, которое описывает ваш вопрос:

Чтобы решить эту проблему, вам нужно рассмотреть эту матрицу:

+--------------------------------+--------------------------------------+
| TP:                            | FN:                                  |
| Same class + same cluster      | Same class + different clusters      |
+--------------------------------+--------------------------------------+
| FP:                            | TN:                                  |
| different class + same cluster | different class + different clusters |
+--------------------------------+--------------------------------------+

Вот как мы рассчитываем TP, FN, FP для индекса Rand:

ПРИМЕЧАНИЕ. В приведенных выше уравнениях я использовал треугольник, чтобы показать ромб на рисунке.

Например, для False Negative мы должны выбирать из класса, но в разных кластерах. Итак, мы можем выбрать

• 1 X из группы 1 и 1 X из группы 2 = ${5 \choose 1}{1 \choose 1} = 5$
• 1 X из группы 1 и 1 X из группы 3 = ${5 \choose 1}{2 \choose 1} = 10$
• 1 O из кластера 1 и 1 O из кластера 2 = ${1 \choose 1}{4 \choose 1} = 4$
• 1 X из группы 2 и 1 X из группы 3 = ${1 \choose 1}{2 \choose 1} = 2$
• 1 $\diamond$ из кластера 2 и 1 $\diamond$ из кластера 3 = ${1 \choose 1}{3 \choose 1} = 3$

Наконец, у нас будет $24$ ($=5+10+4+2+3$) состояния.

То же самое относится и к остальным уравнениям.

Самая сложная часть - это TN, что можно сделать как на картинке ниже:

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

+--------+--------+
| TP: 20 | FN: 24 |
+--------+--------+
| FP: 20 | TN: 72 |
+--------+--------+