본문 바로가기
728x90
반응형

스터디/데이터사이언스88

[CS246] Finding Similar Items (4) - Locality Sensitive Hashing (LSH) Recap: Shingling and Minhashing$k$-shinglesdocument를 set으로 매핑. 아래 표는 $k=3$인 경우의 예시다.Jaccard Similarity두 집합의 유사도를 구하는 방법 중 하나.$J(S, T) = \text{sim}(S, T) = \cfrac{|S \cap T|}{S \cup T}$$\text{sim}(S_1, S_3) = \cfrac{2}{3}$ Minhashrow의 random permutation을 하나 고르고, 처음으로 1이 나오는 row index를 minhash value로 한다.아래 예시에서 random permutation은 $[1, 0, 3, 2]$라 하자.$S_1 = [0, 1, 1, 0]$에서 $1$이 처음 나오는 row는 2번째이고 ra.. 2023. 9. 21.
[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.
Optuna & LightGBM ※ 원래 velog에 있던 내 글을 티스토리에 옮김 optuna를 이용하면 파라미터 튜닝을 알아서 해준다. 정확히 말하자면 각 파라미터마다 튜닝할 숫자의 범위를 정해주면, 각 trial마다 random하게 숫자를 골라준다. 단순히 random selection이 아니라 grid search도 적용할 수 있어서 효율적으로 파라미터를 튜닝한다. Optuna references나는 아래 링크에 있는 글에서 도움을 많이 받았다. (특히 첫번째 글)좀 더 명확한 feature 분석을 위해서는 추가 작업도 해야하지만 이 글에서는 그냥 파라미터튜닝 자체에만 설명한다.https://www.kaggle.com/code/corochann/optuna-tutorial-for-hyperparameter-optimization.. 2023. 9. 19.
[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.
[CS246] Frequent Itemsets: SON, Toivonen Algorithm Recap: Frequent Itemsets & Intro.A-Priori, PCY, Multistage, Multihash 알고리즘을 이용하면 결국 크기가 $k$인 frequent itemset을 얻기 위해서 $k$번 반복해야한다. 물론 일부는 frequent pair에 특화되어있지만 결국 $k$번 반복하는 것은 동일하다. 이번 포스팅에서는 pass 수가 2번 이하인 알고리즘을 알아보자. 크게 3가지 방법이 알려져있다.Random sampling (random sampling은 대규모 데이터셋에서 효과적이다. 무시하지 말기)ToivonenSON (Savasere, Omiecinski, Navathe) Random Samplingmarket basket에 대하여 랜덤 샘플링(무작위 표본 추출법)을 적용하.. 2023. 9. 15.
728x90
반응형

티스토리툴바