슬로프 원

Slope One은 Daniel Lemire와 Anna Maclachlan이 2005년 논문에서 소개한 협업 필터링에 사용되는 알고리즘 계열이다.^[1]논란의 여지가 있는 것은, 이것은 등급을 기준으로 한 비독점적인 품목 기반 협업 필터링의 가장 단순한 형태라는 것이다.그들의 단순성은 그들의 정확성이 종종 더 복잡하고 계산적으로 비싼 알고리즘과 동등한 수준에 있는 동안, 그것들을 효율적으로 구현하는 것을 특히 쉽게 만든다.^[1][2]그것들은 또한 다른 알고리즘을 향상시키기 위한 빌딩 블록으로 사용되어 왔다.^{[3][4][5][6][7][8][9]}이들은 아파치 마하트, 이지렉과 같은 주요 오픈소스 라이브러리의 일부분이다.

정격 리소스의 항목 기반 협업 필터링 및 오버피팅

사용자에게 등급 자원의 선택권이 주어진 경우(예: 1에서 5 사이)와 같이 항목의 등급을 사용할 수 있는 경우, 협업 필터링은 과거의 등급과 다른 사용자가 제공한 등급의 (대규모) 데이터베이스에 근거하여 한 개인의 등급을 예측하는 것을 목표로 한다.

예제: 한 개인이 비틀즈에게 5점 만점에 5점을 줬다는 점에서 새로운 셀린 디온 앨범에 줄 등급을 예측할 수 있을까?

이러한 맥락에서 항목 기반 협업 필터링은 일반적으로 선형 회귀(${\displaystyle f}$( ${\displaystyle x}$)${\displaystyle }$= ${\displaystyle x}$+ b ${\displaystyle f(x)=ax+b}$를 사용하여 다른 항목에 대한 등급을 예측한다.$$따라서 1,000개의 항목이 있는 경우, 학습해야 할 선형 퇴행은 최대 100만개, 즉 200만개까지 될 수 있다.여러 사용자가 두 항목을 모두 평가한 항목 쌍만 선택하지 않는 한 이 접근방식은 심각한 과대^[1] 적합으로 인해 어려움을 겪을 수 있다.

$더{\displaystyle }$ 나은 대안은 f${\displaystyle }$( ${\displaystyle x}$)${\displaystyle }$= x${\displaystyle }$+ ${\displaystyle b}$ $(\displaystyle f(x)=x+b}$와 같은 단순한 예측 변수를 배우는 것일 수 있다$:$ 실험 결과, 이 단순한 예측 변수(일명 경사 원)가 회귀 분석보다 선형^[1] 회귀 분석 횟수를 절반으로 하는 경우가 있다.이러한 단순화된 접근 방식은 스토리지 요구 사항과 지연 시간을 줄여준다.

항목 기반 협업 필터링은 협업 필터링의 한 형태일 뿐이다.다른 대안으로는 사용자 간의 관계가 관심 있는 사용자 기반 협업 필터링이 있다.그러나 항목 기반 협업 필터링은 사용자 수와 관련하여 특히 확장 가능하다.

구매 통계에 대한 항목 기반 협업 필터링

사용자가 바이너리 데이터(항목 구매 여부)만 제공하는 경우 Slope One 및 기타 등급 기반 알고리즘은 적용되지^{[citation needed]} 않는다.이진 항목 기반 협업 필터링의 예로는 사용자 항목 매트릭스에서 구매를 나타내는 이진 벡터 사이의 코사인(cosine)을 계산하는 아마존의 항목 대 항목 특허 알고리즘이^[12] 있다.

슬로프 원보다 훨씬 간단한 Item-to Item 알고리즘은 흥미로운 기준점을 제공한다.예를 들어보자.

샘플구매통계

고객	항목 1	항목 2	항목 3
존	샀다	사지 않았다	샀다
마크	사지 않았다	샀다	샀다
루시.	사지 않았다	샀다	사지 않았다

이 경우 항목 1과 항목 2 사이의 코사인은 다음과 같다.

${\displaystyle \frac{(1}{}}$,${\displaystyle \frac{0}{}}$, 0 )${\displaystyle \frac{\cdot }{}}$ (${\displaystyle \frac{1}{}}$,${\displaystyle \frac{}{1}}$,${\displaystyle \frac{}{1}}$)${\displaystyle \frac{}{}}$‖ (${\displaystyle \frac{1}{}}$,${\displaystyle \frac{0}{}}$)${\displaystyle \frac{\Vert }{}}$(${\displaystyle \frac{1}{}}$, 1, 1${\displaystyle \frac{)\Vert }{}}$= 0 ${\displaystyle {\frac {\frac${($1,$,$0)\cdot$ ($0,1)}{\vert (1,0)\vert ($1,1)\$Vert$

항목 1과 항목 3 사이의 코사인:

${\displaystyle {\frac {(1,0,0)\cdot (1,1,0)}{\Vert (1,0,0)\Vert \Vert (1,1,0)\Vert }}={\frac {1}{\sqrt {2}}}}$,

항목 2와 항목 3 사이의 코사인은 다음과 같다.

${\displaystyle {\frac {(0,1,1)\cdot (1,1,0)}{\Vert (0,1,1)\Vert \Vert (1,1,0)\Vert }}={\frac {1}{2}}}$.

따라서 사용자 방문 항목 1은 권고사항으로 항목 3을, 사용자 방문 항목 2는 권장사항으로 항목 3을, 마지막으로 사용자 방문 항목 3은 권장사항으로 항목 1(그리고 항목 2)을 받는다.모델에서는 품목 쌍(코사인)당 단일 매개변수를 사용하여 권장사항을 작성한다.따라서, n개의 항목이 있는 경우, 최대 n(n-1)/2 코사인까지 계산하여 저장해야 한다.

등급이 지정된 리소스에 대해 한 번의 협업 필터링 기울기

오버피팅을 획기적으로 줄이고 성능을 향상시키며 구현을 용이하게 구현하기 위해 Item-based Rating-Based 협업 필터링 알고리즘의 Slope One 제품군이 제안되었다.본질적으로 한 항목의 등급에서 다른 항목의 등급으로의 선형 회귀(${\displaystyle f}$(x${\displaystyle }$)${\displaystyle }$= x${\displaystyle }$+ ${\displaystyle b}$ = x + b ${\displaystyle$ f$(x)=ax+b}$을(를) 사용하는 대신, 단일 자유 매개변수(${\displaystyle }$ ${\displaystyle (x}$) =${\displaystyle x}$ + ${\displaystyle b}$ $(\displaystyle f(x)=x+b})$로 더 단순한 회귀 형태를 사용한다.$$자유 매개변수는 단순히 두 항목의 등급 간의 평균 차이일 뿐이다.어떤 경우에는 선형 회귀보다 훨씬 정확한 것으로 나타났으며,^[1] 저장량의 절반 또는 그 이하가 소요된다.

예:

1. 사용자 A는 I 항목에 1을, J 항목에 1.5를 부여했다.
2. 사용자 B는 I 항목에 2를 부여했다.
3. 사용자 B가 항목 J를 어떻게 평가했다고 생각하십니까?
4. 슬로프 원 답은 2.5(1.5-1+2=2.5)이다.

보다 현실적인 예를 위해 다음 표를 고려하십시오.

샘플 등급 데이터베이스

고객	A품목	B품목	항목 C
존	5	3	2
마크	3	4	평가하지 않음
루시.	평가하지 않음	2	5

이 경우 B항목과 A항목의 평균 등급 차이는 (2+(-1)/2=0.5이다.따라서 평균적으로 A항목은 B항목보다 0.5만큼 높게 평가된다.마찬가지로 C항목과 A항목의 평균 차이는 3이다.따라서 B 항목에 대한 Lucy 등급을 사용하여 A 항목에 대한 Lucy 등급을 예측하려고 하면 2+0.5 = 2.5를 얻는다.마찬가지로 A 항목의 등급을 C 항목의 등급을 예측하려고 하면 5+3=8이 나온다.

사용자가 여러 항목을 평가한 경우 가중 평균을 사용하여 예측을 조합할 수 있으며, 가중치에 대한 좋은 선택은 두 항목을 모두 평가한 사용자 수입니다.위의 예에서, 존과 마크 모두 A와 B를 평가했고, 따라서 2의 가중치와 오직 존만이 A와 C를 평가했고, 따라서 아래와 같이 1의 가중치를 부여했다.A 항목에 대한 Lucy의 다음 등급은 다음과 같을 것으로 예상한다.

${\displaystyle {\frac {2\frac 2.5+1\fil 8}{2+1}:{2+1}={\frac {13}{3}=4.33}$

따라서 슬로프 1을 구현하기 위해 n개의² 항목을 지정하면, 각 항목 쌍에 대한 평균 차이와 공통 등급 수를 계산하고 저장하기만 하면 된다.

슬로프 1의 알고리즘 복잡성

n개의 항목, m 사용자 및 N개의 등급이 있다고 가정해 보십시오.각 항목 쌍에 대한 평균 등급 차이를 계산하려면 최대 n(n-1)/2단위의 스토리지와 최대 m n개의² 시간 단계가 필요하다.이 계산적 한계치는 비관적일 수 있다: 만약 우리가 사용자가 y 항목까지 등급을 매겼다고 가정한다면, n²+my² 이하에서 차이를 계산할 수 있다.사용자가 x 등급을 입력한 경우, 단일 등급을 예측하려면 x 시간 단계가 필요하고, 누락된 모든 등급을 예측하려면 최대 (n-x)x 시간 단계가 필요하다.사용자가 이미 x 등급을 입력하고 새 등급을 입력했을 때 데이터베이스를 업데이트하려면 x 시간 단계가 필요하다.

데이터 파티셔닝(파티션(데이터베이스) 참조)이나 희소성 스토리지를 사용함으로써 스토리지 요구사항을 줄일 수 있다. 코팅 사용자가 없거나 적은 항목 쌍은 생략할 수 있다.

각주