본문 바로가기

전체 글

 (108)
[데이터마이닝] 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과의 유사도를 구하면 효율적..

티스토리툴바