[데이터마이닝] 3. 유사항목 찾기(Finding Similar Items) -3 민해싱개념 Minhashing

너무 큰 셋들이 많이 있으면 유사도 계산 하나하나 할때만다 오래걸린다. 

셋간의 유사도를 계산할 수 있는 방법은 여러가지 있지만. 

자카르드 유사도가 가장 많이 쓰인다. 

인터섹션의 크기의 비율.

6가지 토큰 중에서 c1은 2,3,5번째 에 해당하는 것을 가지고 있고 

c2는 1,3,5,6번째에 해당하는 것을 가지고 있다. c1과 c2의 intersection은 3번째 것 5번째것.

 

 

민해싱

-Permute the rows(행들의 순서를 뒤섞는다.) --> Thought experiment -not real(실제 실험에해는 이렇게 안한다. )

- Define minhash function (순서를 뒤섞이 위한) --> h(C)

- 모든 column에 여러 minhash fuction을 적용시켜서 각 column에 대한 signature를 얻는다. 

- 민해싱의 결과를 signature matrix라고 하는데 coluumn = sets, rows = minhash value이다. 

 

원래 번호를 써야하나 바뀐 번호를 써야하냐? 

consistent 하기만하면. 

같냐 다르냐가 중요하기 때문에 문제없다. 

 

Suprising Property

이것이 바로 우리가 minhash를 하는 이유. 

기존 열의  유사도를 보존하고 있다. 

 

시그니처의 길이가 너무 짧으면 원래의 유사도와 차이가 날 수 있다 길어지면 길어질수록 error가 줄어든다. 

 

우리가 원하는것은 signature similarity를 통해서 jaccard similairty로 근사하는것이다.