본문 바로가기

분류 전체보기

 (108)
[Django] webcompiler 만들기
[데이터마이닝] 5.링크분석(Link analysis) 5.3절 연습문제(Exercise 5.3.5 ) Exercise 5.3.1 : Compute the topic-sensitive PageRank for the graph of Fig. 5.15, assuming the teleport set is: (a) A only. M = matrix(c(0, 1/3 ,1/3 ,1/3, 1/2,0,0,1/2, 1,0,0,0, 0, 1/2 , 1/2, 0),nrow = 4) r = matrix(c(1/4,1/4,1/4,1/4)) beta = 0.8 es = matrix(c(1,0,0,0),nrow=4) s = 1 pre_r = r r = (beta*M)%*%r + (1-beta)/s * es while(pre_r != r ){ pre_r = r r = (beta*M)%*%r + (1-beta)/s * es } r (..
[데이터마이닝] 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..
[데이터마이닝] 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에..
[데이터마이닝] 3. 유사항목 찾기(Finding Similar Items) -2 슁글링 shingling 싱글링 uni-gram, bi-gram tri-gram example : k= 2; doc = abcab. set of 2-shingles = {ab,bc,ca} combi(a,b,c,d)? silding 기반의 k-shingle을 이용할 경우에 distance k-1정도만 영향을 받는다. 2문단 3문단.. 순서가 바뀌면? 이렇다고 해도 similarity가 크게 바뀌지 않는다. 딱 핑크 네모 부분만 영향을 받는다. k-shingle을 compression을 해야한다.(공간을 너무 많이 차지하므로) 슁글의 개수가 너무 작으면 ...극단적으로 1이라고하면. 모든 doucment가 a-z까지 결국 모든 문서가 유사하다 라는 결론이 난다. k=10이면 26^10 1 bite짜리 10개 사용하면 256^10 -..
[데이터마이닝] 3. 유사항목 찾기(Finding Similar Items) - 1 주어진 많은 아이템 중에서 무엇이 input과 가장 비슷한가.? 모든 아이템을 비교해 보면 되지만. 그것은 사실상 불가능하다. 시간이 오래 걸리기 때문이다. 따라서 해싱을 이용한다 해싱이라는것은 굉장히 효율적인 방법이다. 삽입 삭제 찾기 .. 해싱을 이용하면 O(1)이다. LSH는 해싱을 하는데 주변에 있는지(simillar)한지를 알아챌 수 있는것. 모든 pair를 다 보지 않고 100*100 정도면 제곱에 비례하게 되는 이런 상황이 괜찮을수 있겠지만 더 커지면 힘들다. item을 hash bucket으로 여러 hash fuction을 써서 mapping한다. 비슷하다면 같은 bucket으로 mapping이 잘 될것이다. 한번이라도 같은 bucket에 들어간 것들과 input과의 유사도를 구하면 효율적..

티스토리툴바