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

Question

Что такое алгоритм для сравнения нескольких наборов чисел с целевым набором, чтобы определить, какие из них являются наиболее "похожими"?

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

Сходство двух наборов немного субъективно, поэтому алгоритм на самом деле просто должен различать хорошие и плохие совпадения. У нас много исторических данных, поэтому я хотел бы попытаться сузить количество дней, которые пользователи должны просматривать, автоматически выбрасывая не близкие наборы и пытаясь поставить «лучшие» совпадения на вершине список.

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

Answer 1

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

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

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

Answer 2

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

Answer 3

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

Серьезно.

Они делают такие вещи для жизни.

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

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

Answer 4

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

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

Начните с нормализации ваших данных. Temp имеет диапазон 150 единиц, Wind 120 единиц и Precip 100 единиц. Умножьте свои единицы ветра на 1.25 и Precip на 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-деревья . Если у вас много данных, сравнение вашего текущего наблюдения с каждым историческим наблюдением будет слишком медленным. Деревья ускоряют поиск. Возможно, вы захотите взглянуть на Кластеризация данных и Поиск ближайшего соседа .

Приветствие.

Answer 5

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

Answer 6

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

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

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

Answer 7

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

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

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

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

Answer 8

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

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

Если индексы являются общими (например, температуры измеряются в одни и те же дни (но в разных местах), вы можете регрессировать первый набор данных со вторым, а затем проверьте, что наклон равен 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

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

Answer 9

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

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

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

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

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

Answer 10

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

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, указывающее, падают ли числа вместе или растут вместе, я затем "штрафую", что с процентной разностью средние значения двух наборов чисел.