본문 바로가기

전체 글

 (108)
[데이터마이닝] 5.링크분석(Link analysis) 5.2절 연습문제(Exercise 5.2.1 ) Exercise 5.2.1 Suppose we wish to store an n × n boolean matrix (0 and 1 elements only). We could represent it by the bits themselves, or we could represent the matrix by listing the positions of the 1’s as pairs of integers, each integer requiring ⌈log2 n⌉ bits. The former is suitable for dense matrices; the latter is suitable for sparse matrices. How sparse must the matrix be (i.e., what fract..
[데이터마이닝] 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 가능한 행 순서 변경을 모두 적용하지 않아도 열의 자카드 유사도를 추정할 수 있다는 생각을 할 수도 있다. 예를 들어 행들을 순환적으로 교환하는 경우를 생각해보자. 즉 ..
[데이터마이닝] 3. 유사항목 찾기(Finding Similar Items) -3 민해싱 실제 구현은? Minhashing permutation을 하여 민해싱을 하는것은 이론적으로는 가능하지만. 시간적으로, 메모리 공간적으로 비현실적이다. 그래서 실제로 노드를 peremutiation하지 않고 .hash fucntion을 사용한다. 100개의 hash function을 이용한다는것은 100번 permutation한다는것임. 해당 hash value 가 바뀐 row number. documnet가 set이 되고 set을 1개의 column으로 표현. M(i,c) i번째 hash function, c번째 문서(set) M(i,c)는 hi(r)값들중 가장 작은 값이 된다. 각 row에 대해서 100개의 hash function을 이용하여 현재 진행중인 row r의 hash 값을 구한다. 각 column에 대하여 해당 row에서 1..

티스토리툴바