[데이터마이닝] 3. 유사항목 찾기(Finding Similar Items) - 3.3연습문제

이는 제프리 데이비드 울만의 저서 빅데이터 마이닝의  3.3절 연습문제에 대한 풀이이다. 

연습문제3.3.5  두 열의 자카드 유사도가 0이면 민해싱을 통해 얻은 추정 자카드 유사도는 항상 정확함을 증명하여라. Prove that if the Jaccard similarity of two columns is 0, then
then minhashing always gives a correct estimate of the Jaccard similarity.

민해싱을 통해 얻은 추정 자카드 유사도는 두 열의 자카드 유사도와 같다.

연습문제3.3.6 가능한 행 순서 변경을 모두 적용하지 않아도 열의 자카드 유사도를 추정할 수 있다는 생각을 할 수도 있다. 예를 들어 행들을 순환적으로 교환하는 경우를 생각해보자. 즉 임의로 선택된 행 r을 순서쌍 첫 번재로 시작해 행  r+1, r+2를 거쳐 마지막 행으로 이동한 후, 계속해서 첫 번째 행, 두 번째 행 등을 거쳐 행 r-1로 이동하는 방식이다. 행이 n개 일 경우 이런 순서 변경은 오직 n번 가능하다. 그러나 이는 자카드 유사도를 정확하게 추정하기에 충분하지 않은 횟수다. 모든 순서 변경을 적용한 결과의 평균으로 자카드 유사도를 얻을 수 없다는 사실을, 열이 2개인 행렬을 사용해 증명하여라. 

Exercise 3.3.6 : One might expect that we could estimate the Jaccard similarity of columns without using all possible permutations of rows. For example,  we could only allow cyclic permutations; i.e., start at a randomly chosen row
r, which becomes the first in the order, followed by rows r + 1, r + 2, and so on, down to the last row, and then continuing with the first row, second row, and so on, down to row r − 1. There are only n such permutations if there are  n rows. However, these permutations are not sufficient to estimate the Jaccard similarity correctly. Give an example of a two-column matrix where averaging over all the cyclic permutations does not give the Jaccard similarity.