숫자 집합의 유사성을 평가하는 알고리즘

StackOverflow https://stackoverflow.com/questions/139811

  •  02-07-2019
  •  | 
  •  

문제

여러 숫자 세트를 대상 세트와 비교하여 가장 "유사한" 숫자를 결정하는 알고리즘은 무엇입니까?

이 알고리즘의 한 가지 용도는 오늘의 시간별 일기 예보를 과거 기상 기록과 비교하여 날씨가 비슷한 날을 찾는 것입니다.

두 세트의 유사성은 약간 주관적이므로 알고리즘은 실제로 좋은 일치와 나쁜 일치를 구별하면 됩니다.과거 데이터가 많기 때문에 가깝지 않은 세트를 자동으로 버리고 "가장 좋은" 일치 항목을 상위에 배치하여 사용자가 살펴봐야 하는 일수를 줄이려고 합니다. 목록.

편집하다:이상적으로 알고리즘의 결과는 다른 데이터 세트를 사용한 결과와 비교할 수 있습니다.예를 들어 다음과 같이 제안한 평균 제곱 오류를 사용합니다. 나일스 꽤 좋은 결과가 나오지만, 온도를 비교할 때 생성되는 수치는 데이터의 규모가 다르기 때문에 풍속이나 강수량 등 다른 데이터로 생성되는 수치와 비교할 수 없습니다.날씨 이외의 데이터 중 일부는 매우 크기 때문에 평균 제곱 오차 알고리즘은 온도를 사용하여 생성되는 수십 또는 수백에 비해 수십만 개의 숫자를 생성합니다.

도움이 되었습니까?

해결책

평균 제곱 오류 메트릭은 날씨 비교와 같은 응용 프로그램에 효과가있을 수 있다고 생각합니다. 계산하기 쉽고 의미가있는 숫자를 제공합니다.

시간이 지남에 따라 측정을 비교하려면 계산에서 결 측값을 제거 할 수 있습니다.

시간에 묶이지 않거나 조종되지 않은 다차원 산란 데이터가 아닌 값의 경우 조금 더 어렵습니다. 좋은 거리 메트릭을 선택하면 그러한 데이터를 분석하는 기술의 일부가됩니다.

다른 팁

피어슨 상관 계수를 사용하십시오. 여기에서 찾을 수있는 SQL 쿼리에서 계산하는 방법을 알아 냈습니다. http://vanheusden.com/misc/pearson.php

금융에서는 베타를 사용하여 두 계열 숫자의 상관관계를 측정합니다.예를 들어, 베타는 "작년에 ​​IBM의 가격이 S & P 500 지수의 가격이 5%상승한 날에 얼마의 가격으로 올라갈 것인가?" 이동의 백분율을 다루므로 2 시리즈는 다른 척도를 가질 수 있습니다.

내 예에서 베타는 공분산(IBM, S&P 500) / 분산(S&P 500)입니다.

Wikipedia에는 ​​설명하는 페이지가 있습니다. 공분산, 변화, 및 베타: http://en.wikipedia.org/wiki/Beta_(금융)

통계 사이트를보십시오. 나는 당신이 상관 관계를 찾고 있다고 생각합니다.

예를 들어, 당신이 온도, 바람 및 침전을 측정한다고 가정 할 것입니다. 이 항목을 "기능"이라고 부를 것입니다. 따라서 유효한 값은 다음과 같습니다.

  • 온도 : -50 ~ 100F (저는 미국 미네소타에 있습니다)
  • 바람 : 0 ~ 120 마일/시간
  • 침전 : 0 ~ 100

데이터를 정규화하여 시작하십시오. Temp의 범위는 150 단위, 바람 120 단위 및 침전 100 단위를 가지고 있습니다. 풍력 장치에 1.25를 곱하고 1.5를 곱하여 온도와 거의 동일한 "스케일"으로 만듭니다. 당신은 여기서 공상을 얻고 하나의 기능을 다른 기능보다 더 가치있는 규칙을 만들 수 있습니다. 이 예에서는 바람의 범위가 큰 범위를 가질 수 있지만 일반적으로 더 작은 범위에 머무르기 때문에 결과를 왜곡하지 않도록 덜 무게를 두려고합니다.

이제 각 측정이 다차원 공간의 지점으로 상상해보십시오. 이 예는 3D 공간 (온도, 바람, 침전)을 측정합니다. 좋은 점은 더 많은 기능을 추가하면 공간의 차원을 증가 시키지만 수학은 동일하게 유지됩니다. 어쨌든, 우리는 현재 요점에 가장 가까운 역사적 요점을 찾고 싶습니다. 그렇게하는 가장 쉬운 방법은입니다 유클리드 거리. 따라서 현재 지점에서 각 역사적 지점까지의 거리를 측정하고 가장 가까운 일치를 유지하십시오.

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-Trees 또는 R- 트리. 데이터가 많은 경우 현재 관찰을 모든 역사적 관찰과 비교하면 너무 느립니다. 나무는 검색 속도를 높입니다. 당신은보고 싶을 수도 있습니다 데이터 클러스터링 그리고 가장 가까운 이웃 검색.

건배.

통계 학자와 대화하십시오.

진지하게.

그들은 생계를 위해 이런 종류의 일을합니다.

당신은 그것을 씁니다 "두 세트의 유사성은 약간 주관적입니다", 그러나 그것은 전혀 주관적이지 않습니다. 문제 영역의 유사성에 대한 적절한 기준을 결정하는 문제입니다.

이것은 많은 프로그래머에게 물어 보는 것보다 전문가와 대화하는 것이 훨씬 더 나은 상황 중 하나입니다.

우선, 이들이 세트인지 주문했는지 또는 주문한 컬렉션인지 스스로에게 물어보십시오.

나는 이것들이 복제 된 컬렉션이라고 가정합니다. 가장 명백한 알고리즘은 숫자가 동일하게 간주되는 공차를 선택하고 해당 측정에서 숫자가 동일 인 슬롯 수를 계산하는 것입니다.

응용 프로그램에서 이것을 위해 구현 된 솔루션이 있지만 더 나은 "올바른"것이 있는지 확인하려고합니다. 각 역사적 날에 대해 다음을 수행합니다.

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까지의 값이므로 숫자가 함께 떨어지거나 상승하는지 여부를 말하면, 나는 두 숫자 세트의 평균을 비율 차이로 "처벌"합니다.

두 번, 당신은 당신이 데이터의 분포를 모른다고 언급했는데, 물론 사실입니다. 내일, 내일은 150km/hr의 바람이있는 150도 F의 날이있을 수 있지만, 거의 가능성이 거의없는 것 같습니다.

나는 당신이 오랫동안 역사적인 기록을 가지고 있기 때문에 배포에 대해 아주 좋은 아이디어를 가지고 있다고 주장합니다. 이를 감안할 때, 당신은 역사적 분포의 양자 측면에서 모든 것을 넣을 수 있으며, 모든 측정에서 Quantiles의 절대적 또는 제곱 차이로 무언가를 할 수 있습니다. 이것은 또 다른 정규화 방법이지만 데이터의 비선형 성을 설명하는 방법입니다.

모든 스타일의 정규화는 모든 변수를 비교할 수 있어야합니다.

예를 들어, 하루는 바람이 불고 더운 날이라고 가정 해 봅시다. 그것은 온도 양자가 .75이고 바람이 0.75의 바람이있을 수 있습니다. 열에 대한 .76 Quantile은 1도 떨어져 있고 바람에 대한 것은 3kmh 떨어져있을 수 있습니다.

경험적 분포에 대한 이러한 초점은 이해하기 쉽고 평균 제곱 오류와 같은 정상 추정보다 더 강력 할 수 있습니다.

두 데이터 세트가 순서대로 정렬되어 있습니까, 아니면 정렬되지 않습니까?

주문하면 인덱스가 동일합니까?균등한 간격?

인덱스가 일반적 인 경우 (예를 들어 같은 날 (그러나 다른 위치)에 측정 된 온도는 두 번째 데이터 세트에 대해 첫 번째 데이터 세트를 회귀 한 다음 기울기가 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

관련 테스트 중 하나는 Kolmogorov-Smirnov입니다.http://en.wikipedia.org/wiki/Kolmogorov-Smirnov_test

당신은 또한 볼 수 있습니다

학생의 t- 테스트,http://en.wikipedia.org/wiki/Student%27s_t-test

또는 Wilcoxon 부호 순위 테스트 http://en.wikipedia.org/wiki/Wilcoxon_signed-rank_test

두 표본 간의 평균이 동일한지 테스트합니다.

그리고 Levene 테스트를 통해 등분산 테스트를 수행할 수 있습니다. http://www.itl.nist.gov/div898/handbook/eda/section3/eda35a.htm

메모:서로 다른 데이터 세트가 동일한 평균과 분산을 가질 수 있습니다. 얼마나 엄격한지(그리고 보유하고 있는 데이터의 양)에 따라 ~할 수 있었다 더 높은 순간의 동등성에 대한 테스트도 고려하십시오.

어쩌면 숫자 세트를 벡터로 볼 수 있습니다 (세트의 각 숫자는 벡터의 구성 요소).

그런 다음 DOT 제품을 사용하여 주어진 벡터 2의 유사성을 계산할 수 있습니다 (예 : 숫자 세트).

벡터를 정규화해야 할 수도 있습니다.

더 : 코사인 유사성

라이센스 : CC-BY-SA ~와 함께 속성
제휴하지 않습니다 StackOverflow
scroll top