지미뉴트론 개발일기

Min-Hashing 기반 LSH 기법 설명 안녕하세요. 이번 시간에는 지난 번에 다룬 MinHash를 기반으로 유사한 문서 쌍을 빠르게 근사하여 찾을 수 있는 알고리즘인 LSH(Locality-Sensitive Hashing)에 대해서 다루어보도록 하겠습니다. 참고로, 이 글은 MinHash의 원리를 알고있음을 가정하고 설명할 예정이므로 해당 알고리즘에 대한 설명이 필요하신 분들은 아래 링크의 이전 글을 참고해주세요. Min-Hashing이란? MinHash 알고리즘 설명 안녕하세요. 이번 시간에는 데이터 마이닝 분야에서 문서 등 자료형 간의 유사도를 빠른 시간 내에 쉽게 근사하여 비교할 수 있는 Min-Hashing 알고리즘에 대해서 이해해보도 jimmy-ai.tistory.com LSH 기본 가정 ..

MinHash 알고리즘 설명 안녕하세요. 이번 시간에는 데이터 마이닝 분야에서 문서 등 자료형 간의 유사도를 빠른 시간 내에 쉽게 근사하여 비교할 수 있는 Min-Hashing 알고리즘에 대해서 이해해보도록 하겠습니다. 일반적으로 N개의 연속된 단어 집합인 N-gram을 토큰으로 사용하지만, 여기서는 쉬운 이해를 위하여 단어 단위를 토큰으로 가정해보겠습니다. 아래처럼 3개의 문서에서 각각 4개의 단어씩을 포함하고 있는 상황이라고 해보겠습니다. 아래처럼 문서 내 토큰(단어)의 포함 여부를 나타내는 TF 행렬을 생각해볼 수 있습니다. 이제, 이 예시를 기반으로 MinHash 알고리즘을 설명해보겠습니다. 유사도 예시 : Jaccard Similarity 문서 간의 유사도는 어떻게 측정할까요? 여러가지 방법이 ..

그래프 분할(Graph Partition) 다음과 같은 그래프가 있다고 가정을 해봅시다. 이제 이 그래프를 2개의 그룹으로 나누어보겠습니다. 그래프 분할을 위한 여러 알고리즘을 적용할 수 있겠지만 속마음으로 한번 나누어 보세요. 이제 두 개의 그래프가 A, B 두 가지 방법으로 나누어진 경우를 생각해보겠습니다. 두 그룹 사이 cut(주황색 선)을 지나는 edge 개수 등의 대략적인 기준이나 이 경우는 눈대중으로만 보더라도 B가 A보다는 그래프 분할이 잘 진행된 것으로 보입니다. 그래프 분할이 의미있는 상황은 예를 들어, 제가 고등학교때 만난 친구들 그룹끼리 SNS 친구 관계가 얽혀있을 것이고, 대학교 과에서 만난 친구들 그룹끼리 SNS 친구 관계가 얽혀있을 것이고 등의 관계를 생각해보면 이해가 쉬울 것입..