Алгоритм оценки сходства наборов чисел

Прежде всего, спросите себя, это наборы или заказанные коллекции.

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

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

Поскольку вы хотите сравнивать измерения с течением времени, вы можете просто исключить отсутствующие значения в расчетах.

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

В финансах они используют бета для измерения корреляции двух рядов чисел. Например, Beta могла бы ответить на вопрос: «Насколько за последний год цена IBM вырастет в день, когда цена индекса S&P 500 выросла на 5%?» Он имеет дело с процентом хода, поэтому 2 серии могут иметь разные масштабы.

В моем примере бета - это ковариация (IBM, S&P 500) / дисперсия (S&P 500).

В Википедии есть страницы, объясняющие Ковариация, Дисперсия и бета: http://en.wikipedia.org/wiki/Beta_(finance)

Посмотрите статистические сайты. Я думаю, вы ищете корреляцию.

У меня есть решение, реализованное для этого в моем приложении, но я хочу посмотреть, есть ли что-то лучше или более «правильное». Для каждого исторического дня я делаю следующее:

function calculate_score(historical_set, forecast_set)
{
    double c = correlation(historical_set, forecast_set);
    double avg_history = average(historical_set);
    double avg_forecast = average(forecast_set);
    double penalty = abs(avg_history - avg_forecast) / avg_forecast
    return c - penalty;
}

Затем я сортирую все результаты по убыванию.

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

В качестве примера я предполагаю, что вы измеряете температуру, ветер и осадки. Мы будем называть эти предметы «особенностями». Итак, допустимые значения могут быть:

• Температура: от -50 до 100F (я в Миннесоте, США)
• Ветер: от 0 до 120 миль / час (не уверен, что это реально, но потерпите меня)
• Осадки: от 0 до 100

Начните с нормализации ваших данных. Диапазон Temp составляет 150 единиц, Wind 120 единиц и Precip 100 единиц. Умножьте единицы ветра на 1,25 и осадок на 1,5, чтобы они были примерно того же «масштаба», что и ваша температура. Здесь вы можете пофантазировать и создать правила, в которых одна функция будет более ценной, чем другие. В этом примере ветер может иметь большой диапазон, но обычно остается в меньшем диапазоне, поэтому вам нужно меньше его взвешивать, чтобы он не исказил ваши результаты.

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

for each historicalpoint

    distance = sqrt(
        pow(currentpoint.temp - historicalpoint.temp, 2) + 
        pow(currentpoint.wind - historicalpoint.wind, 2) +
        pow(currentpoint.precip - historicalpoint.precip, 2))

    if distance is smaller than the largest distance in our match collection
        add historicalpoint to our match collection
        remove the match with the largest distance from our match collection

next

Это метод грубой силы. Если бы у вас было время, вы могли бы стать намного интереснее. Многомерные данные могут быть представлены в виде деревьев, таких как kd-деревья или r-деревья. Если у вас много данных, сравнение вашего текущего наблюдения с каждым историческим наблюдением будет слишком медленным. Деревья ускоряют поиск. Возможно, вы захотите взглянуть на Кластеризация данных и Поиск ближайшего соседа.

Ваше здоровье.

Пару раз вы упоминали, что не знаете распределения данных, что, конечно, верно. Я имею в виду, что завтра может быть день с температурой 150 градусов по Фаренгейту и ветром 2000 км / ч, но это кажется маловероятным.

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

Нормализация в любом стиле должна сделать все переменные сопоставимыми.

Например, предположим, что сегодня ветреный и жаркий день: квантиль температуры может быть 0,75, а квантиль ветра - 0,75. Квантиль 0,76 для тепла может быть на расстоянии 1 градуса, а квантиль для ветра может быть на расстоянии 3 км / ч.

Этот акцент на эмпирическом распределении также легко понять, и он может быть более надежным, чем обычная оценка (например, среднеквадратическая ошибка).

Поговорите со статистиком.

Серьезно.

Они зарабатывают этим на жизнь.

Вы пишете это «Сходство двух наборов немного субъективно», но это совсем не субъективно - это вопрос определения соответствующих критериев сходства для вашей проблемной области.

Это одна из тех ситуаций, когда гораздо лучше поговорить с профессионалом, чем задавать вопросы кучке программистов.

Используйте коэффициент корреляции Пирсона. Я понял, как вычислить это в SQL-запросе, который можно найти здесь: http://vanheusden.com/misc/pearson.php

Упорядочены два набора данных или нет?

Если заказано, индексы такие же? на равном расстоянии?

Если индексы являются общими (например, температуры, измеренные в одни и те же дни (но в разных местах), вы можете регрессировать первый набор данных по второму, а затем проверьте, что наклон равен 1, а точка пересечения равна 0.
http://stattrek.com/AP-Statistics-4/Test-Slope.aspx?Tutorial=AP

В противном случае вы можете выполнить две регрессии значений y = по их индексам. http://en.wikipedia.org/wiki/Correlation. Вы все равно захотите сравнить склоны и пересечения.

====

Если неупорядочено, я думаю, вы хотите посмотреть на кумулятивные функции распределения http://en.wikipedia.org/wiki/Cumulative_distribution_function

Один из подходящих тестов - это тест Колмогорова-Смирнова: http://en.wikipedia.org/wiki/Kolmogorov-Smirnov_test

Вы также можете посмотреть

T-критерий Стьюдента, http://en.wikipedia.org/wiki/Student%27s_t-test

или знаковый ранговый тест Вилкоксона http://en.wikipedia.org/wiki/Wilcoxon_signed-rank_test

чтобы проверить равенство средних значений двух выборок.

И вы можете проверить равенство дисперсий с помощью теста Левена http://www.itl.nist.gov/div898/handbook/eda/section3/eda35a.htm

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

Возможно, вы можете видеть свой набор чисел как вектор (каждое число из набора является компонентом вектора).

Затем вы можете просто использовать точечный продукт для вычисления сходства двух заданных векторов (то есть набора чисел).

Возможно, вам потребуется нормализовать ваши векторы.

Подробнее: Косинусное сходство