본문 바로가기
728x90
반응형

cs24635

[CS246] BFR Algorithm: Extension of k-means to large data Motivationk-mean 알고리즘은 모든 데이터를 메모리에 올리고 클러스터링 알고리즘을 수행한다.그러나 현실세계의 데이터는 너무 커서(데이터베이스로 관리 등) 메인메모리에 올릴 수 없다.BFR 알고리즘을 매우 큰 데이터(disk-resident data sets)에 k-mean 클러스터링을 적용하는 알고리즘이다. BFR은 논문의 세 저자 Paul S. Bradley, Usama M. Fayyad, Cory A. Reina의 앞글자를 딴 것이다.(논문: Scaling Clustering Algorithms to Large Database)BFR OverviewAssume모든 클러스터는 axis-aligned ellipse이다. (그러나 각 axis마다 표준편차가 다른 것은 허용된다)Ideadata p.. 2023. 10. 1.
[CS246] Finding Similar Items (6) - LSH Family for Cosine Distance 이전까지 LSH를 구할 때 자카드 유사도를 이용했다.이번 포스트에서는 여러가지 유클리드/비유클리드 distance를 소개하고, 코사인 거리를 이용한 LSH를 알아보자.※ 정확히는 자카드 유사도는 거리는 아니다. (자카드 거리) = 1 - (자카드 유사도) 이다.Distance MeasuresAxioms of a Distance Measure$d$가 아래 4가지 조건을 충족하면 distance measure(거리 측도)라고 한다.$d(x, y) \ge 0$$d(x,y)=0 \text{ iff } x=y$$d(x, y) = d(y,x)$ (symmetric, 대칭성)$d(x,y) \le d(x,z) + d(z,y)$ (triangle inequality, 삼각부등식)다양한 유클리드/비유클리드 거리가 있지만,.. 2023. 9. 23.
[CS246] Finding Similar Items (5) - LSH Family Locality-Sensitive FamilyMeanings of Sensitivity Valuesfamily of $F$ of function은 다음을 만족하면 $(d_1, d_2, p_1, p_2)$-sensitive라고 부른다.모든 함수 $f \in F$와 점 $x,y$에 대하여 $d(x,y) \le d_1$이면, $f(x)=f(y)$일 확률은 최소 $p_1$이다.$d(x,y) \ge d_1$이면, $f(x)=f(y)$일 확률은 최대 $p_2$이다.$d$가 Jaccard distance라면 $d = 1-\text{sim}(x,y)$이므로$d(x,y) \le d_1 \Rightarrow 1 - \text{sim}(x, y) \le d_1 \Rightarrow 1 - d_1 \le \text{sim}(.. 2023. 9. 22.
[CS246] Finding Similar Items (3) - Minhashing Jaccard Similarity자카드 유사도는 두 집합의 유사도를 구하는 방법 중 하나이다.두 집합 $A,\ B$의 자카드 유사도를 구하면 다음과 같다.\[ J(A,\ B) = \cfrac{|A \cap B|}{ |A \cup B| } = \cfrac{|A \cap B|}{|A| + |B| - |A \cap B|} \] ※ 자카드 거리(Jaccard distance)는 $d_J(A,\ B) = 1 - J(A,\ B)$ 이다.※ IoU(Intersection over Union) 과 식이 유사하지만 보통 IoU는 region, bounding box 에서 사용되는 용어이다. 자카드 유사도는 앞서 설명한 characteristic matrix의 column similarity를 계산하는데 사용된다. (컬럼.. 2023. 9. 20.
[CS246] Finding Similar Items (2) - Shingling Shinglings$k$-Shinglingsdocument를 길이가 $k$인 문자열 집합으로 표현한다.예를 들어 "abcdabd"에 대해 $k=2$인 2-shingling 집합은 {ab, bc, cd, da, ab, bd} 이다.공백과 관련하여 몇까지 옵션이 가능하다. (blank, tab, newline 등)일반적으로 $k=9,\ 9,\ 10$ 정도로 한다. textually similar한 문서들은 많은 수의 shingling이 겹칠 것이다. 단순히 한단어를 바꾸는 것으로는  $k-1$ 거리만큼만 바뀐다.  예를 들어 "The dog which chased the cat" 과 "The dog that chased the cat"을 비교해보자.두 문장의 차이점은 오직 "g_which_c"에서만 발생한다.. 2023. 9. 19.
[CS246] Finding Similar Items (1) - Introduction Big Picturenaive하게 similar item을 찾는다고 하면 이중 루프를 통해 유사도를 계산하는 것을 생각할 수 있다. 해싱(hashing)을 이용하여 제곱의 시간복잡도 없이 유사한 아이템을 빠르게 찾을 수 있다.대표적인 알고리즘으로 Locality-Sensitive Hashing (LSH)에 대하여 공부할 것이다.LSH의 장점으로 매우 적은 pair만으로도 계산이 가능하다는 것이고, 단점으로 false negative가 존재할 수 있다는 것이다. ApplicationsFinding Similar Documentsweb, 뉴스 기사 등의 매우 큰 스케일에서 문자 그대로(textually) 유사한 문서를 찾는 것이다. 의미가 비슷한(similar meaning, topic) 것을 찾는 것이 아.. 2023. 9. 18.
728x90
반응형

티스토리툴바