Метод сравнения гистограмм в процентах

[alexey007]

Привет, всем!

Мне нужен метод для сравнения гистограмм, желательно метрика должна выдавать процент похожести двух гистограмм.
Я хочу вычислить точность работы алгоритма по поиску объектов различной формы. У меня есть истинная гистограмма распределения объектов по размерам и гистограмма, которая получилась в результате работы алгоритма поиска этих объектов. Если посчитать процент точности количества всех найденных объектов, то это легко, мы знаем сколько должно быть объектов и вычитаем из того сколько алгоритм нашёл и делим на число объектов сколько должно быть и таким образом можно получить ошибку в процентах.
А вот когда доходит дело до сравнения гистограмм и причём отличие должно выражаться в процентах, то я не очень понимаю как это сделать.
Если кто знает как такую задачу правильно решить, подскажите плиз. Может есть литература где можно почитать. Спасибо

[Schrodinger's cat]

alexey007 если я правильно понял то Вам поможет дивергенция Кульбака-Лейблера. Это метрика сравнения двух распределений.

[alexey007]

Да! Отлично! То что надо, спасибо!

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

Приведу данные первой и второй гистограммы:
$P=[1,0,2 ,5 ,7, 4, 3, 0, 1]; Q=[2, 1, 0, 4, 8, 5, 2, 1, 0]; $

Согласно формуле дивергенция Кульбака-Лейблера
$D_{KL}(P||Q)=\sum\limits_{i=1}^np_i\log\frac{p_i}{q_i}$

Если подставить данные в формулу, то например для второго члена суммы мы получим:
$0\cdot\log\frac{0}{1}=0\cdot\log{0}=0\cdot-\infty$
А для третьего столбца получим
$2\cdot\log\frac{2}{0}=2\cdot\log{\infty}=2\cdot\infty=\infty$
Подскажите, пожалуйста, как сравнить правильно близость двух гистограмм

[B@R5uk]

Я так понимаю, расстояние Кульбака — Лейблера вычисляется для распределений. В вашем же распоряжении имеются выборки. Аппроксимируйте каждую выборку подходящей моделью распределения (например, с помощью ММП), а потом уже к двум аппроксимациям можно будет применить предложенную выше дивергенцию.

[KregSeptim]

B@R5uk
Эмпирическое распределение -- тоже распределение (хотя автору нужно еще все нормализировать)

alexey007
Почти все правильно. +бесконечность -- валидное значение для KL-дивергенции, оно выражает то, что мы не сможем нормально закодировать референсное распределение предложенным (так как у референсного распределения ненулевую вероятность имеют точки, которые у данного имеют нулевую). А вот -бесконечность исключено, поскольку такая дивергенция вычисляется только для распределений, связанных абсолютной непрерывностью.

В вашем случае, вероятно, подойдет расстояние Колмогорова-Смирнова.

[B@R5uk]

KregSeptim в сообщении #1566375 писал(а):

Эмпирическое распределение -- тоже распределение

Так то оно так, да только разница между ними, как между дискретной и непрерывной функцией. Причём в данном конкретном случае это утверждение верно буквально: высота столбика на гистограмме — целое число (количество наблюдений), в то время как матожидание этой высоты — наверняка действительное число. Если б числа были бы большими (прям так много больше единицы), то ещё бы было ничего (в плане погрешности округления).

-- 10.10.2022, 01:20 --

KregSeptim в сообщении #1566375 писал(а):

нужно еще все нормализировать

Можно сделать и после вычислений: вычесть $\log(N_Q/N_P)$ и результат поделить на $N_P$

-- 10.10.2022, 01:22 --

KregSeptim в сообщении #1566375 писал(а):

расстояние Колмогорова-Смирнова

Кстати, отличная штука. Логарифмы считать не надо.

[Schrodinger's cat]

Почему бы не попробовать использовать просто RMSE или MAPE? В пределе можно и SE (сумму разностей).
Распределения то совпадают, можно рассматривать их просто как 2 ряда.

[Евгений Машеров]

А $\chi^2$ не спасёт гиганта мысли?
Обычная проверка однородности распределений.
$\chi^2=n\Sigma_i\Sigma_j \frac{\nu_{i,j}-\frac {\nu_{i.}\nu_{.j}} n }{\nu_{i.}\nu_{.j}}$
Где $\nu_{i,j}$ число попаданий в ячейку, n - общее число наблюдений во всех выборках, $\nu_{i.} \nu_{.j}$ суммы по гистограмме и по ячейке по всем гистограммам.
Для двух ещё проще$\chi^2=n_1 n_2\Sigma \frac {\frac {\mu_i} {n_1}-\frac {\nu_i} {n_2}}{\mu_i+\nu_i}$
где мю и ню число в соответствующей ячейке первой и второй гистограммы, Эн один и два - общее число наблюдений в первой и второй гистограммах.
Распределение с $(r-1)(k-1)$ степенями свободы, где r число ячеек гистограмм, k - число гистограмм (для двух просто $r-1$)

[KregSeptim]

B@R5uk в сообщении #1566377 писал(а):

Так то оно так, да только разница между ними, как между дискретной и непрерывной функцией. Причём в данном конкретном случае это утверждение верно буквально: высота столбика на гистограмме — целое число (количество наблюдений), в то время как матожидание этой высоты — наверняка действительное число. Если б числа были бы большими (прям так много больше единицы), то ещё бы было ничего (в плане погрешности округления).

Ну у индикатора тоже матожидание не 0 или 1 (кроме тривиальных случаев). :)
В плане расстояний дискретные распределения почти ничем не хуже, чем абсолютно непрерывные. Более того, "непрерывные распределения" это распределения, которые абсолютно непрерывны относительно (как правило) меры Лебега, а дискретные -- которые абсолютно непрерывны относительно считающей меры. Фундаментально это суть одна и та же конструкция.

[mihaild]

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

[KregSeptim]

Schrodinger's cat в сообщении #1566381 писал(а):

Почему бы не попробовать использовать просто RMSE или MAPE?

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

mihaild в сообщении #1566388 писал(а):

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

Адекватен ли этот приор задаче?

[Евгений Машеров]

Евгений Машеров в сообщении #1566384 писал(а):

А $\chi^2$ не спасёт гиганта мысли?
Обычная проверка однородности распределений.
$\chi^2=n\Sigma_i\Sigma_j \frac{(\nu_{i,j}-\frac {\nu_{i.}\nu_{.j}} n )^2}{\nu_{i.}\nu_{.j}}$
Где $\nu_{i,j}$ число попаданий в ячейку, n - общее число наблюдений во всех выборках, $\nu_{i.} \nu_{.j}$ суммы по гистограмме и по ячейке по всем гистограммам.
Для двух ещё проще$\chi^2=n_1 n_2\Sigma \frac {(\frac {\mu_i} {n_1}-\frac {\nu_i} {n_2})^2}{\mu_i+\nu_i}$
где мю и ню число в соответствующей ячейке первой и второй гистограммы, Эн один и два - общее число наблюдений в первой и второй гистограммах.
Распределение с $(r-1)(k-1)$ степенями свободы, где r число ячеек гистограмм, k - число гистограмм (для двух просто $r-1$)

Сорри, очепятался. Приведен исправленный вариант.

[Schrodinger's cat]

KregSeptim в сообщении #1566389 писал(а):

В чем будет смысл полученных чисел?

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

[KregSeptim]

Schrodinger's cat
В алгоритмах ML (вы это имеете в виду под алгоритмами обучения?) эта штука тоже плохая. В качестве функции потерь плохая, ибо не завязана на какой-либо inference в статмодели, так что само обучение будет под вопросом; в качестве метрики плохая, ибо сложно ее нормально проинтерпретировать.

[Александрович]

alexey007 в сообщении #1566333 писал(а):

Приведу данные первой и второй гистограммы:
$P=[1,0,2 ,5 ,7, 4, 3, 0, 1]; Q=[2, 1, 0, 4, 8, 5, 2, 1, 0]; $

Обычно объединяют интервалы с малыми частотами.
$P=[3,5 ,7, 4, 4]; Q=[3, 4, 8, 5, 3] $. А потом можно воспользоваться советом Евгений Машеров