[Finding Similar Items] 2. Locality Sensitive Hashing

1.Locality Sensitive Hashing (LSH)

• 지역 민감 해싱(Locality Sensitive Hashing, LSH)은 유사한 문서들의 짝을 찾는 과정에서 사용.
  • 이 방법은 문서 간의 유사성을 효율적으로 찾기 위해, 유사할 가능성이 높은 signature 짝에 초점.
• LSH 과정.
  • Shingling
    • 문서에서 k 길이의 문자열 집합을 생성.
    • 이 집합은 문서를 대표하는 집합으로, 문서의 내용을 기반으로 함.
  • Min Hashing
    • 생성된 문자열 집합을 기반으로 짧은 정수 벡터 형태의 signature 을 생성.
    • 이 서명은 원래의 집합을 대표하며, 집합 간의 유사성을 반영.
  • Locality Sensitive Hashing (LSH)
    • Min Hashing을 통해 생성된 signature을 사용하여 유사성을 검사할 필요가 있는 짝, 즉 후보 짝들을 찾음.
• LSH는 유사한 문서의 서명이 해시 버킷에 함께 배치될 확률을 높여, 유사한 문서 짝을 효과적으로 찾을 수 있도록 함.
• 이 과정을 통해, 대규모 문서 집합에서 유사한 문서를 효율적으로 찾을 수 있으며, 이는 문서 분류, 중복 검출, 추천 시스템 등 다양한 분야에서 활용될 수 있다.
• LSH는 유사한 문서의 짝을 빠르게 찾아내어 복잡한 유사성 계산을 줄여줌.

2.First Cut of LSH

• Locality Sensitive Hashing (LSH)의 첫 번째 단계에서는 문서들 사이의 자카드 유사도(Jaccard similarity)가 특정 임계값(s) 이상인 문서를 찾는 것이 문제입니다.
  • 예를 들어, s가 0.8일 경우, 유사도가 최소 0.8 이상인 문서 쌍을 찾아야 합니다.
• 이를 위한 일반적인 아이디어는 평가해야 할 후보 쌍을 생성하는 것입니다.
  • 이 과정에서는 두 개의 문서 x와 y가 후보 쌍인지를 판별하는 함수 f(x, y)를 사용합니다.
• Min-Hash 행렬에 대해서는, 서명 행렬 M의 열을 많은 버킷에 해싱합니다.
• 동일한 버킷에 해싱되는 각 문서 쌍은 후보 쌍으로 간주.
  • 이 방식을 통해, 서명 행렬의 열이 같은 버킷에 할당되면, 해당 문서들이 유사하다는 가정 하에, 실제 유사도를 계산하기 전에 먼저 후보 쌍을 선별.
• 이러한 접근 방식은 대규모 문서 집합에서 유사한 문서 쌍을 효율적으로 찾는 데 도움이 되며, 전체 문서 쌍을 직접 비교하는 것보다 계산 비용을 크게 줄일 수 있습니다.

3.Motivation: LSH

• Locality Sensitive Hashing (LSH)의 주요 동기는 높은 유사도를 가진 두 컬럼이 그들의 분수(비율) 또한 매우 유사할 것이라는 가정에 기반.
• 예를 들어, (C3, C4)가 매우 유사한 반면, (C1, C2)는 서로 매우 다릅니다.
• 이 경우, 단지 4개의 행만을 고려함으로써도 우리는 (C3, C4)가 유사하다는 것을 식별할 수 있습니다.
• 이것은 유사한 문서 또는 항목을 찾는 과정에서 전체 데이터를 모두 비교하는 대신, 유사성이 높을 가능성이 있는 항목들만을 빠르게 선별하여 검사하는 LSH의 접근 방식의 핵심.
• 따라서, LSH는 대규모 데이터 세트에서 유사한 항목을 효율적으로 찾는 데 있어 매우 유용한 방법입니다.

4.Candidates from MinHash

• MinHash에서 후보 쌍을 찾는 방법은 유사도 임계값 s(0 < s < 1)를 설정하는 것부터 시작합니다.
• M의 열 x와 y가 후보 쌍이 되려면, 그들의 서명이 최소한 s 비율의 열에서 일치해야 합니다.
  • 즉, 서명의 비율이 비슷하다면, 우리는 x와 y가 높은 (자카드) 유사도를 가진다고 예상할 수 있다.
• 서명이 비슷한 열들은 자카드 유사도가 높을 가능성이 크기 때문에, 이를 기반으로 후보 쌍을 선별하고, 실제 유사도를 계산하여 유사한 항목들을 찾아내는 것.

5.Building LSH for MinHash

• MinHash를 위한 LSH(Locality Sensitive Hashing) 구축 방법은 다음과 같습니다:
• 행렬 M을 b개의 밴드로 나눕니다.
• 각 밴드에는 r개의 행이 있습니다.
  • 이렇게 하면 전체 행렬이 b x r의 구조로 나뉘어집니다.
• 예를 들어, 전체 행의 수가 100개라면, 이를 적절한 b와 r에 따라 나눌 수 있습니다.
• 각 밴드의 각 열 부분을 해시 테이블에 해싱합니다.
• 이때, 해시 테이블은 k개의 버킷을 가집니다.
• 각 밴드 내에서 열의 일부분을 해시 함수를 통해 특정 버킷에 할당.
  • k를 가능한 한 크게 설정.
    • 이는 잘못된 충돌(wrong collision)을 방지하기 위함.
      • 잘못된 충돌이란 실제로는 크게 유사하지 않은 열들이 같은 버킷에 할당되는 경우.
    • k를 크게 설정하면 이러한 잘못된 충돌의 가능성을 줄일 수 있다.
• 후보 열 쌍은 같은 버킷에 할당된 쌍을 의미.
• 이 방법을 통해, 전체 행렬 M에서 유사한 열들을 효율적으로 식별.
• 각 밴드에서 해싱 과정을 통해 같은 버킷에 할당된 열 쌍은 높은 유사도를 가질 가능성이 높기 때문에, 이들을 후보 쌍으로 선정하여 더 정밀한 유사도 계산을 진행할 수 있다.

6.Assumption for LSH

• LSH(Locality Sensitive Hashing)에 대한 가정은 다음과 같다:
• 충분한 수의 버킷이 있다고 가정하여, 특정 밴드에서 완전히 동일하지 않은 경우 열이 동일한 버킷에 해시될 가능성이 낮다고 가정.
• 이는 열들이 그들의 해시 과정에서 특정 밴드 내에서 완전히 동일할 때만 같은 버킷에 할당될 가능성이 높다는 것을 의미.
• "동일한 버킷"이란 해당 밴드에서 "동일하다"는 것을 의미한다고 가정.
  • 즉, 두 열이 같은 버킷에 할당되면, 그 밴드 내에서 그들이 동일하다고 볼 수 있다.
• 이러한 가정은 분석을 단순화하기 위해 필요하지만, 알고리즘의 정확성을 위해 필수적인 것은 아님.
• 이 가정들은 LSH 알고리즘의 효율성을 높이기 위한 것으로, 실제로 유사한 항목들을 빠르고 효율적으로 찾아내는 데 도움.
• 그러나 알고리즘 자체의 정확성과 신뢰성은 이러한 가정에 의존하지 않음.

7.LSH for MinHash

• MinHash를 위한 LSH(Locality Sensitive Hashing)는 다음과 같이 작동:
• 서명 행렬 M의 열을 여러 번 해시.
• 이 과정은 각 열을 다양한 방식으로 해시하여, 비슷한 밴드끼리는 높은 확률로 같은 버킷에 할당될 수 있도록 함.
• 비슷한 밴드만이 높은 확률로 같은 버킷에 할당되도록 조정.
• 이는 비슷한 내용을 가진 열들이 같은 버킷에 할당될 확률을 증가시켜, 그로 인해 실제로 유사한 열들을 더 용이하게 찾아낼 수 있게 합니다.
• 후보 쌍은 동일한 버킷에 해시된 열들.
• 예를 들어, 2번 열과 6번 열이 동일한 버킷에 할당되었다면, 이들은 아마도 동일할 가능성이 높음(후보 쌍).
• 그러나 6번 열과 7번 열이 서로 다른 버킷에 할당되었다면, 이들은 확실히 서로 다름.

8.Example of LSH

• LSH (Locality Sensitive Hashing)의 예시를 다음과 같은 경우를 고려하여 설명해 드리겠습니다:
• 상황 가정: 100,000개의 문서(100k 열)와 100개의 정수(행)로 이루어진 서명(signature)이 있습니다.
• 따라서, 서명이 차지하는 메모리 공간은 40Mb입니다.
• 목표: 최소 0.8(s = 0.8)의 유사도를 가지는 문서 쌍을 찾는 것입니다.
• 이를 위해 b = 20개의 밴드와 r = 5개의 행을 선택합니다.
• 이 설정으로, 전체 서명 행렬을 20개의 밴드로 나누게 되며, 각 밴드는 5개의 행으로 구성됩니다.
• 이 방법을 사용함으로써, 각 밴드 내에서 유사한 열(즉, 문서)이 높은 확률로 동일한 버킷에 할당될 것입니다.
• 이렇게 동일한 버킷에 할당된 열(문서) 쌍은 후보 쌍으로 간주되며, 이 중 실제로 0.8 이상의 높은 유사도를 가진 문서 쌍을 찾는 것이 목표입니다.
• 이 예시에서, 100개의 서명을 가진 100,000개의 문서를 효율적으로 처리하여, 높은 유사도를 가진 문서 쌍을 찾는 과정이 LSH 기법을 통해 어떻게 가능해지는지 보여줍니다.
• C1과 C2가 80% 유사하다고 가정할 때(b = 20, r = 5 사용): C1과 C2의 유사도(sim)가 0.8입니다.
• 만약 C1, C2의 유사도가 s 이상이라면, C1과 C2는 후보 쌍이 되어야 합니다.
• 적어도 한 개의 공통 버킷에 해시되어야 합니다(적어도 하나의 밴드가 동일).
• b = 20 및 r = 5로 설정하는 경우: C1, C2가 한 밴드에서 동일할 확률은 (0.8)^5 = 0.328입니다.
• C1, C2가 20개의 모든 밴드에서 비슷하지 않을 확률은 (1 − 0.328)^20 = 0.00035입니다.
• 이는 80% 유사한 열 쌍의 약 1/3000이 거짓 음성(우리가 놓치는 경우)이라는 것을 의미합니다.
• 따라서, 실제로 유사한 문서 쌍의 99.965%를 찾을 수 있습니다.
• C1과 C2가 30% 유사하다고 가정했을 때 (b = 20, r = 5를 설정하는 경우): C1과 C2 사이의 유사도(sim)가 0.3입니다.
• 만약 C1과 C2의 유사도가 s보다 낮다면, 우리는 그들이 어느 공통 버킷에도 할당되지 않기를 원합니다(모든 밴드가 달라야 합니다).
• b = 20, r = 5를 설정하는 경우: C1과 C2가 한 밴드에서 동일할 확률은 (0.3)^5 = 0.00243입니다.
• C1과 C2가 적어도 20개 밴드 중 하나에서 동일할 확률은 1 − (1 − 0.00243)^20 = 0.0474입니다.
• 이는 대략 4.74%의 쌍이 후보 쌍이 되는 것을 의미합니다.
• 이들은 잘못된 긍정(false positives)입니다.
• 왜냐하면 우리는 이들을 후보 쌍으로 검사해야 하지만, 결국 그들의 유사도가 임계값 s 이하임을 알게 되기 때문.

9.Analysis of LSH

• 이상적인 LSH(Locality Sensitive Hashing)는 다음과 같은 특성을 가진 알고리즘을 말합니다:
• 높은 정확도와 효율성: 이상적인 LSH 알고리즘은 데이터 내에서 유사한 항목을 빠르고 정확하게 식별할 수 있어야 합니다.
• 이는 대규모 데이터셋 내에서 유사한 항목을 효과적으로 찾아내기 위해 필수적입니다.
• 낮은 오류율: False positives(거짓 양성)과 False negatives(거짓 음성)의 비율이 낮아야 합니다.
• 거짓 양성은 유사하지 않은 항목들이 유사한 것으로 잘못 식별되는 경우이며, 거짓 음성은 실제로 유사한 항목들이 누락되는 경우입니다.
• 이상적인 LSH는 이 두 오류율을 최소화하여 높은 정밀도와 재현율을 달성해야 합니다.
• 스케일러빌리티: 대규모 데이터셋에 적용 가능해야 하며, 데이터의 크기가 증가해도 성능이 크게 저하되지 않아야 합니다.
• 이를 위해 LSH는 메모리 사용량과 계산 복잡도 측면에서 효율적이어야 함.
• 조정 가능한 유사도 임계값: 다양한 유형의 데이터셋과 요구사항에 맞게 유사도 임계값(s)을 조정할 수 있어야 합니다.
• 이를 통해 사용자는 특정 응용 프로그램에 맞게 알고리즘의 정확도와 성능을 최적화.
• 범용성: 다양한 유형의 데이터(텍스트, 이미지, 오디오 등)에 적용할 수 있어야 하며, 서로 다른 유사도 측정 기준에 따라 유연하게 적용될 수 있어야 합니다.
• 이상적인 LSH 알고리즘은 이러한 특성을 통해 다양한 응용 분야에서의 유사 항목 탐색, 중복 탐지, 클러스터링 등과 같은 작업을 효율적으로 수행할 수 있습니다.
• LSH(Locality Sensitive Hashing)에서 1개의 밴드와 1개의 행을 사용하는 경우, 이 설정은 아주 기본적인 형태로, 각 문서나 항목의 해시값을 단일 비교를 통해 분석합니다.
• 이 경우의 주요 특징은 다음과 같습니다:
• 해시값의 동일성은 유사성을 나타냅니다: 문서나 항목이 유사할수록, 해시 함수를 통해 생성된 해시값이 같을 확률이 높다.
• 1개의 밴드와 1개의 행을 사용하는 경우, 이 확률은 직접적으로 문서나 항목의 유사성을 반영.
• 파란 영역(False Negative Rate): False negative는 실제로 유사하지만, 해시 과정에서 다른 버킷에 할당되어 유사하지 않다고 잘못 판단되는 경우입니다. 1개의 밴드와 1개의 행을 사용할 때, 매우 유사한 항목들이 다른 해시 값을 가질 확률이 존재하므로, false negative 비율이 존재하게 됩니다.
• 하지만, 이 설정에서는 유사성이 높을수록 false negative의 확률이 상대적으로 낮아집니다.
• 녹색 영역(False Positive Rate): False positive는 실제로는 유사하지 않지만, 해시 과정에서 같은 버킷에 할당되어 유사하다고 잘못 판단되는 경우입니다.
• 단 하나의 비교만으로 모든 결정을 내리기 때문에, 1개의 밴드와 1개의 행을 사용하는 설정에서 false positive의 비율이 높을 수 있습니다.
• 즉, 실제로는 크게 유사하지 않은 항목들이 같은 해시값을 가질 확률이 존재합니다.
• 따라서, 1개의 밴드와 1개의 행을 사용하는 설정은 매우 간단하고 직관적이지만, 특정 상황에서는 false positive나 false negative의 비율에 영향을 미쳐, 유사성 분석의 정확성을 저하시킬 수 있습니다. 이러한 이유로, 실제 응용에서는 더 많은 밴드와 행을 사용하여 이러한 오류의 비율을 조정하고 최적의 성능을 달성하려고 합니다.

10.b Bands of r Rows in Column

• 두 컬럼 C1과 C2가 t의 유사도를 가진다고 가정했을 때, b개의 밴드와 각 밴드에 r개의 행이 있다고 합시다. 이 설정에서 다음과 같은 확률을 계산할 수 있습니다: 밴드 내 모든 행이 동일한 확률: 두 컬럼이 유사도 t를 가지므로, 한 밴드 내 모든 행(즉, r개의 행)이 동일할 확률은 t^r입니다. 이는 유사도가 높을수록, 즉 t값이 클수록 한 밴드 내에서 모든 행이 동일할 확률이 높아진다는 것을 의미합니다. 밴드 내 어떤 행이라도 서로 다른 확률: 한 밴드 내 모든 행이 동일하지 않을 확률, 즉 최소 하나의 행이 다를 확률은 1 - t^r입니다. 이는 모든 행이 동일할 확률의 반대 개념입니다. 어떤 밴드도 동일하지 않은 확률: b개의 밴드 중 어느 하나도 동일하지 않을 확률은 (1 - t^r)^b입니다. 이는 각 밴드가 독립적으로 모든 행이 동일할 확률을 고려할 때, 모든 밴드가 동일하지 않을 종합적인 확률입니다. 최소 한 밴드가 동일한 확률: 최소 한 밴드가 동일하다는 것은 위에서 언급한 '어떤 밴드도 동일하지 않은 확률'의 반대 개념입니다. 따라서 이 확률은 1 - (1 - t^r)^b로 계산됩니다. 이 확률은 유사한 컬럼들을 식별하는 데 중요한 역할을 합니다. 유사도가 높은 컬럼들을 적어도 한 개 이상의 밴드에서 동일하게 해싱할 확률을 나타내므로, 이 값을 최대화하는 것이 LSH 알고리즘의 목표 중 하나입니다. 이러한 확률 계산을 통해, LSH 알고리즘은 유사한 항목들을 효율적으로 식별할 수 있으며, b와 r의 값을 조정함으로써 알고리즘의 정확도와 성능을 최적화할 수 있습니다.

11.LSH Involves a Tradeoff

• Locality Sensitive Hashing (LSH)에서는 유사성(s)이 주어졌을 때, 적어도 하나의 밴드가 동일할 확률을 조정하는 것이 중요한데, 이는 거짓 긍정(false positives)과 거짓 부정(false negatives) 사이의 균형을 맞추는 데 핵심적인 역할을 합니다. b가 밴드의 수를, r이 각 밴드당 행의 수를 나타낼 때, 이 두 변수를 적절히 설정하는 것이 중요합니다. 예를 들어, b = 20 및 r = 5로 설정하면, 이는 Min-Hash 함수의 총 수(즉, M의 행의 수)가 20 * 5 = 100임을 의미합니다. 이러한 설정은 다음과 같은 효과를 가집니다: 거짓 긍정(False Positives) 감소: r(각 밴드의 행 수)을 늘림으로써, 한 밴드 내의 모든 해시가 일치할 확률이 낮아지므로, 유사하지 않은 항목이 유사하다고 잘못 판단될 확률이 감소합니다. 이는 거짓 긍정 비율을 줄이는 데 도움이 됩니다. 거짓 부정(False Negatives) 조정: b(밴드의 수)를 늘리면, 적어도 하나의 밴드가 일치할 확률이 증가합니다. 이는 실제로 유사한 항목이 서로 다르다고 잘못 판단될 확률, 즉 거짓 부정 비율을 감소시킵니다. 따라서, LSH에서는 b와 r의 값을 조정함으로써 거짓 긍정과 거짓 부정 사이의 균형을 맞추려고 합니다. 일반적으로, 유사성이 높은 항목을 더 잘 찾아내기 위해서는 b를 늘리고, 거짓 긍정을 줄이기 위해서는 r을 늘립니다. 그러나, 이러한 설정은 각각의 응용 프로그램과 사용 사례의 특성에 따라 최적화되어야 합니다.

12.S-Curve: Picking r and b

• Locality Sensitive Hashing (LSH)에서 가장 유사한 쌍을 포착하면서 비슷하지 않은 쌍은 최소화하기 위해 r(각 밴드의 행 수)과 b(밴드 수)의 조정은 매우 중요합니다. 이를 통해 최적의 S-곡선을 얻어내는 것이 목표입니다. S-곡선은 유사도에 따른 짝을 매칭할 확률을 나타내며, 유사도가 높은 쌍을 잘 잡아내고 유사도가 낮은 쌍은 걸러내는 특성을 보여줍니다. 예를 들어, 만약 총 50개의 해시 함수를 사용하고, r = 5, b = 10으로 설정한다고 가정해 보겠습니다. 이 경우 총 해시 함수의 수(r * b)는 50개가 되어야 하므로, 이 설정은 각각의 밴드가 5개의 행을 가지고 있고, 총 10개의 밴드로 구성됩니다. 이러한 설정은 S-곡선을 조정하는 데 중요한 역할을 합니다: r(행의 수)을 늘릴수록: 각 밴드 내에서 완벽하게 일치하는 확률이 줄어들기 때문에, 유사도가 높은 쌍을 정확히 포착하는 데 더 효과적이지만, 동시에 비슷하지 않은 쌍이 같은 밴드에 할당될 확률도 줄어들어, 거짓 양성(false positive)의 가능성이 감소합니다. b(밴드의 수)를 늘릴수록: 적어도 하나의 밴드가 동일하게 매치될 확률이 증가하여, 유사한 아이템들이 서로 다른 밴드에 할당되어 누락될 가능성이 줄어들지만, 거짓 음성(false negative)의 가능성은 감소합니다. 따라서 r과 b의 적절한 조합을 통해 S-곡선을 최적화하면 유사한 쌍을 효과적으로 포착하면서도 비슷하지 않은 쌍을 최소화할 수 있습니다. 예에서처럼 r = 5, b = 10으로 설정하는 것은 총 50개의 해시 함수를 사용하여, 유사한 아이템들을 잘 구분하고, 동시에 비슷하지 않은 아이템들을 거를 수 있는 좋은 시작점이 될 수 있습니다.

13.Discussion on LSH

• Locality Sensitive Hashing (LSH)은 비슷한 항목들을 효율적으로 식별하기 위한 방법으로, 특히 대규모 데이터셋에서 유사한 항목 쌍을 찾는 것을 용이하게 합니다. LSH는 특정 유사도 메트릭에 기반한 해싱 함수를 사용하여 유사한 항목들이 같은 '버킷'에 할당될 확률을 높입니다. 이는 다양한 유사도 측정 기준에 적용될 수 있으며, 각각의 유사도 메트릭에 맞는 LSH 변형이 존재합니다. 해밍 거리(Hamming Distance): 해밍 거리는 두 이진 문자열이 다른 비트의 수를 측정합니다. 이 유사도 측정에는 비트 뒤집기 연산을 기반으로 하는 LSH 알고리즘이 적용될 수 있습니다. 예를 들어, 두 벡터 간의 해밍 거리가 작을수록 비슷하다고 할 수 있으며, 이를 통해 유사한 항목들이 하나의 버킷에 매핑될 수 있도록 해싱 함수를 설계할 수 있습니다. 코사인 유사도(Cosine Similarity): 코사인 유사도는 두 벡터 간의 각도를 측정하여 유사도를 평가합니다. 이 메트릭에는 차원의 저주를 줄이기 위해 랜덤 프로젝션 기법을 사용하는 LSH 변형이 적용될 수 있습니다. 랜덤 프로젝션은 고차원 데이터를 저차원으로 축소시키는 과정에서 유사한 항목들이 같은 방향을 가리키도록 합니다. 유클리디안 거리(Euclidean Distance): 유클리디안 거리는 두 점 간의 "직선" 거리를 측정합니다. 이 거리 측정에 적합한 LSH는 p-안정 분포(LSH for p-stable distributions)를 활용할 수 있습니다. p-안정 분포를 사용하는 해싱 함수는 유클리디안 거리가 작은 항목들이 같은 버킷에 할당될 확률을 높이도록 설계됩니다. 각 유사도 측정 기준에 따라 적합한 LSH 알고리즘을 선택하고 적용함으로써, 다양한 유형의 데이터와 문제 상황에서 효율적으로 유사 항목을 식별할 수 있습니다. LSH는 이처럼 유연하게 다양한 유사도 메트릭에 적용될 수 있는 강력한 도구입니다.

14.Families of Hash Functions

• 해시 함수란 두 요소를 입력으로 받아 그들이 "동등한지" 아닌지를 판별하는 함수를 의미합니다. 예를 들어, h(x) = h(y)는 함수 h가 x와 y를 동등하다고 판단한다는 것을 의미합니다. 여기서 '동등'이라는 것은 해시 함수의 결과값이 같다는 것을 의미하며, 이는 두 입력값이 같은 버킷이나 그룹에 속한다는 것을 나타냅니다. 해시 함수의 집합, 즉 해시 함수군(Family of Hash Functions)은 위에서 언급한 (1)과 같은 성질을 가진 함수들의 모임을 말합니다. 이러한 해시 함수군은 다양한 함수를 포함할 수 있으며, 각 함수는 동일한 입력 공간에서 값을 매핑할 때 서로 다른 결과를 생성할 수 있습니다. 해시 함수군의 구성은 다음과 같은 특징을 가집니다: 다양성: 해시 함수군은 다양한 해시 함수를 포함하여, 각기 다른 방식으로 데이터를 매핑할 수 있습니다. 이는 데이터를 분산시키거나 충돌을 줄이는 데 도움이 됩니다. 일관성: 같은 해시 함수를 사용할 때, 동일한 입력값은 항상 동일한 결과값을 반환해야 합니다. 이는 데이터의 검색 및 비교 과정에서 중요한 역할을 합니다. 보편성: 해시 함수군은 다양한 유형의 데이터에 적용될 수 있어야 하며, 다양한 문제 상황에 유연하게 대응할 수 있어야 합니다. 해시 함수군은 데이터베이스 검색, 데이터 분류, 보안 암호화, 데이터의 유사성 검사 등 다양한 컴퓨팅 분야에서 광범위하게 사용됩니다. Locality Sensitive Hashing (LSH)와 같은 알고리즘에서는, 유사한 데이터 항목을 효율적으로 식별하기 위해 특정 유형의 해시 함수군을 사용하기도 합니다.

15.Hamming Distance

• 해밍 거리(Hamming Distance)는 두 집합(또는 문자열)의 차이를 측정하는데 사용됩니다. 이 개념을 이해하기 위해서, 우리는 행렬을 사용하여 표현할 수 있습니다. 이 행렬에서 행은 원소(또는 shingles)를 나타내고, 열은 집합(또는 문서)를 나타냅니다. 만약 어떤 원소 e가 집합 s에 속한다면, 행렬에서 행 e와 열 s의 위치에 1이 표시됩니다. 일반적으로 이러한 행렬은 희소 행렬(sparse matrix)입니다. 예를 들어, 두 문서 C1과 C2가 있다고 가정해봅시다. 이 두 문서의 해밍 거리를 계산하는 것은, 각 문서를 나타내는 집합(열)에서 서로 다른 위치에 있는 원소(행에 해당하는 1의 값)의 개수를 세는 것입니다. 즉, C1과 C2에서 서로 다른 위치에 1을 가지는 원소의 수가 해밍 거리가 됩니다. 해밍 거리를 위한 해시 함수를 표현하는 방법 중 하나는 각 원소(또는 shingles)에 대해 고유한 해시 값이나 식별자를 할당하는 것입니다. 이 해시 함수는 두 집합 사이의 차이(즉, 해밍 거리)를 계산하는데 사용될 수 있습니다. 해시 함수는 각 원소를 독립적으로 처리하여, 원소가 특정 집합에 포함되어 있는지 여부를 판단하는 데 도움을 줍니다. 해밍 거리를 효율적으로 계산하기 위해서는, 해시 함수가 빠르고 정확하게 각 원소의 포함 여부를 판단할 수 있어야 합니다. 이를 통해, 대규모 데이터 집합에서도 빠르게 유사성을 측정하고 비교할 수 있습니다.

16.Key Idea for Hamming Distance

• 해밍 거리(Hamming Distance)의 핵심 아이디어 해밍 거리를 계산하는 핵심 아이디어 중 하나는 무작위 순열(p)을 사용하는 것입니다.
• 여기서, 각 문서(Ci)에 대한 해시 함수 (h_{pi}(Ci))는 Ci 열에서 첫 번째로 1이 나타나는 행의 인덱스를 의미합니다.
• 이 방법에서, (h_{pi}(C1) = h_{pi}(C2))인 확률은 두 문서 C1과 C2의 유사도(sim(C1, C2))와 같다는 주장이 있습니다.
• 즉, C1과 C2 열을 아래로 훑어보면서 두 열 중 하나에서 인덱스가 1이 되는 첫 번째 지점을 찾습니다.
• (h_{pi}(Ci) = h_{pi}(Cj))가 성립할 때, C1과 C2 모두 해당 위치에서 1이라는 것입니다.
• 코사인 유사도(Cosine Similarity)의 핵심 아이디어 코사인 유사도를 계산하는 핵심 아이디어는 무작위 벡터(v)를 선택하여 두 개의 버킷을 갖는 해시 함수 (h_{v})를 결정하는 것입니다. 이때, (h_{v}(x))는 (vx > 0)이면 +1을, (vx ≤ 0)이면 -1을 반환합니다.
• 이 방법으로, 임의의 벡터 v와 입력 벡터 x의 내적을 계산하여 그 결과의 부호에 따라 x를 두 개의 버킷 중 하나로 분류합니다.
• 이러한 분류 방식은 벡터 x가 벡터 v에 대해 양의 각도를 이루는지 또는 음의 각도를 이루는지를 기반으로 하기 때문에, 이를 통해 벡터들 사이의 코사인 유사도를 효과적으로 추정할 수 있습니다.