비슷한 패턴을 빠르게 찾기 위해 세트를 저장하는 방법은 무엇입니까?

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

문제

(이것은 숙제가없고 작업 문제가 아닙니다. 그것은 단지 개인의 관심/직업이며 완전한 가상입니다. 그러나 나는 좋은 알고리즘이나 데이터 구조에 관심이 있습니다.)

데이트 사이트를 운영 할 것이라고 가정합시다. 그리고 내 특징 싱글이 그랬을 것입니다 영화 맛과 일치합니다. (왜 안 돼?)

이 경우 각 사용자의 영화 등급을 저장하는 방법이 필요합니다. (지금까지는 문제가 없습니다.) 그리고 가장 적합한 사용자를 찾으려면 데이터 구조가 필요합니다. 두 맛 패턴 사이의 거리는 두 사용자가 한 모든 등급 사이의 평균 거리입니다.

예시

movies   A B C D E F G H I J K L M ...
user Xm  9 5   1   1   5
user Ym      4 6 1         8
user Zf  9   6 4           7

거리 (x, z) = avg (ABS (9-9) + abs (1-4)) = 1.5

거리 (y, z) = avg (ABS (4-6) + abs (6-4) + abs (8-7)) = 1.666

X 씨는 Y 씨보다 Z 부인에게 약간 더 잘 맞습니다.

나는 그 영혼을 좋아한다 ...

  • ... 데이터베이스에서 많은 작업이 필요하지 않습니다
  • ... 많은 데이터를 처리 할 필요가 없습니다
  • ... 빨리 뛰어
  • ... 최고의 일치하는 것을 제공하십시오
  • 좋아, 아마도 나도 좋은 근사치를 고려할 것입니다.

이것은 또한 수천 개의 가능한 영화, 약 20-50 개의 영화 만 평가하는 사용자 및 수천 명의 사용자와 함께 작동해야한다는 점을 명심하십시오.

(이것은 정신적 퍼즐이기 때문에 실제 문제가 아니기 때문에, 작업 어라운드는 실제로 도움이되지 않습니다.)

검색 알고리즘 또는 데이터 구조는 무엇입니까?

도움이 되었습니까?

해결책

비슷하게 들립니다 넷플릭스 상 도전,보다 구체적으로 가장 인기있는 접근법의 전반부. 당신이하려는 것의 가능한 구현은 다양하고 다양합니다. 그들 중 어느 것도 예외적으로 효율적이지 않으며 L1 메트릭은 신뢰할 수있는 상관 관계에 특히 좋은 옵션이 아닙니다.

다른 팁

당신이 찾고있는 것 같습니다 가장 가까운 이웃 영화 공간에서. 그리고 당신의 거리 기능은 L1 메트릭. 당신은 아마도 a를 사용할 수 있습니다 공간 색인 어떤 종류의. 어쩌면 기술을 사용할 수 있습니다 협업 필터링.

CREATE TABLE data (user INTEGER, movie INTEGER, rate INTEGER);

SELECT  other.user, AVG(ABS(d1.rate - d2.rate)) AS distance
FROM    data me, data other
WHERE   me.user = :user
    AND other.user <> me.user
    AND other.movie = me.movie
GROUP BY
    other.user
ORDER BY
    distance

복잡성은 O (n1.5))) 오히려 O (n2), 그대로 n 비교 sqrt(n) 영화 (각 쌍으로 함께 채워진 영화 평균).

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