순위 상관 알고리즘

나는 친구들의 순위 목록이 있습니다. 그런 다음 동일한 친구의 목록을 몇 개 더 얻었지만 순위는 다릅니다. 원래 순위 목록에 가장 가까운 목록을 확인하는 알고리즘이 있습니까? 그것은 가능성이 순위 사이의 "거리"당신의 척도가 무엇인지에 따라 달라집니다순위 상관 알고리즘

감사

출처

2013-03-21 Mike

O (n log n)에서 실행되는 [배열 반전 알고리즘] (http://stackoverflow.com/questions/337664/counting-inversions-in-an-array)을 사용하면이 작업을 수행 할 수 있다고 생각합니다. 기본적으로 원래의 순위를 매기 며 각 항목에 ID가 증가하는 순서로 할당 한 다음 n 개의 항목 각각에 대해 "다른 순위"를 검색하여 초기 순위에서 해당 ID를 할당합니다 (가능한 한 이것을 효율적으로 수행하기 위해) 그리고 나서 위에서 언급 한 알고리즘을 "다른 순위"에 할당 된 ID에 적용합니다. –

. 우리가

dist(R1, R2) = Sum abs(position of i in R1 - position of i in R2), over all i

은 다음

즉

pos[Peter] = 3

수단 배열의 첫 번째 순위의 모든 i의 위치를 저장할 수 있습니다 정의하면 예를 들어

, 그 안에서 Peter가 세 번째 친구로 나타납니다. 순위.

pos을 사용하여 위의 합계를 계산하여 가장 가까운 순위를 선형 시간에서 찾을 수 있습니다.

출처

2013-03-21 14:53:08 abeln

좋은 해결책입니다. 그러나, 그것은 거리의 중요성에 대해 많이 말하지 않습니다. 한 곳에서 200 명의 친구가있는 순위 목록이 있고, 다른 한 편으로 한 친구의 순위가 200 곳인 순위 목록이 있습니다. 거리는 동일합니다. 그러나 두 번째 순위 목록은 첫 번째 순위 목록보다 훨씬 더 빠릅니다. – Mike

위치 차이가있는 정사각형이나 큐브를 취하면 커다란 불일치를 벌 수 있습니다. – abeln

내가 할 수있을 것 같아. 감사 – Mike

나는 그들 사이의 순위 거리를 비교해야하지만 무게를 사용해야한다고 생각한다. 예를 들어 1 위를 차지한 사용자가 10 위를 차지하는 경우 큰 차이가 있지만 101 위를 차지한 사용자가 110 위를 차지하면 큰 변화가 아닙니다. 따라서 순위가 높은 사용자의 차이에 대해 더 높은 계수를 넣어야합니다.

출처

2013-03-21 15:55:08 aram90

순위 상관 알고리즘

답변

관련 문제