2개 이상 세트의 유사성 추정하기

Snowflake에서는 2개 이상 데이터 세트 사이의 대략적인 유사성을 추정하기 위해 MinHash를 사용합니다. MinHash 방식에서는 세트의 교집합이나 합집합을 계산하지 않고 집합을 비교하므로 효율적이고 효과적인 추정이 가능합니다.

이 항목의 내용:

개요

일반적으로 Jaccard 유사성 계수(또는 인덱스)는 두 세트 사이의 유사성을 비교하기 위해 사용됩니다. 두 세트 A 및 B 에 대해 Jaccard 인덱스는 교집합 크기와 합집합의 크기의 비율로 정의됩니다.

J(A,B) = (A ∩ B) / (A ∪ B)

그러나 이러한 계산을 위해서는 상당한 리소스 및 시간이 사용될 수 있으므로, 대규모 데이터 세트에는 적합하지 않습니다.

대조적으로, MinHash 방식의 목표는 교집합이나 합집합을 계산하지 않고 J(A,B) 를 빠르게 추정하는 것입니다.

SQL 함수

MinHash를 사용하여 대략적인 유사성을 추정하기 위해서는 다음 집계 함수 가 제공됩니다.

  • MINHASH: 길이가 k 인 MinHash 배열(입력 인자)이 포함된 MinHash 상태를 반환합니다.

  • MINHASH_COMBINE: 2개(또는 이상)의 입력 MinHash 상태를 단일 출력 MinHash 상태로 결합합니다.

  • APPROXIMATE_SIMILARITY (또는 APPROXIMATE_JACCARD_INDEX): MinHash 상태를 기반으로 입력 세트의 유사성(Jaccard 인덱스) 추정치를 반환합니다.

구현 세부 정보

Wikipedia의 MinHash 에서 제공되는 자세한 설명과 같이:

“H 는 A 및 B 의 구성원을 고유 정수값으로 매핑하는 해시 함수이며, S 세트의 경우 H_min(S) 를 H 에 대한 S 의 최소 구성원, 즉 최소값이 H(s) 인 S 의 s 구성원으로 정의해 보겠습니다. 그러면 이는 다음 방정식으로 표현할 수 있습니다.

H_min(S) = argmin_{s in S} (H(s))

H_min 을 A 및 B 에 적용하면, 최소 해시 값을 갖는 A ∪ B 합집합의 요소가 A ∩ B 교집합에 위치하면 정확히 동일한 값을 얻을 수 있습니다. 이러할 확률은 위의 비율이므로,

Pr[H_min(A) = H_min(B)] = J(A,B)

즉, 임의로 선택한 A 및 B 세트를 가정할 때 H_min(A) = H_min(B) 의 확률은 J(A,B) 와 같습니다. 다시 말해, X 가 임의 변수이고 H_min(A) = H_min(B) 인 경우 1 및 그렇지 않은 경우 0의 값을 갖는 경우, X 는 J(A,B) 의 편향되지 않은 추정치입니다. X 는 분산이 너무 커서 자체적으로 Jaccard 인덱스를 추정하기에 적합하지 않음에 유의하십시오(항상 0 또는 1이므로).

MinHash 방식에서는 k 개의 서로 다른 해시 함수를 사용하여 동일한 방식으로 구성된 여러 변수를 평균화하는 방식으로 이러한 분산을 줄입니다.”

이를 달성하기 위해 MINHASH 함수는 초기에 k 개의 서로 다른 해시 함수를 생성한 후 각 입력 세트의 모든 요소에 적용하고 각각을 최소값으로 유지하여 각 세트에 대한 MinHash 배열(MinHash 상태 라고 함)을 생성합니다. 보다 구체적으로 살펴보면, i = 0 to k-1 의 경우 A 세트(MinHash_A 로 표시됨)에 대한 MinHash의 H_i 입력은 A 세트의 모든 요소에 적용된 i 해시 함수의 최소값에 해당합니다.

마지막으로 두 세트 A 및 B 의 유사값에 대한 근사치는 다음과 같이 계산됩니다.

J_apprx(A,B) = (# of entries MinHash_A and MinHash_B agree on) / k

예

다음 예에서는 두 요소 세트의 유사성을 대략적으로 구하기 위해 이 방식 및 해당 기능의 사용 방법을 보여줍니다.

우선, 샘플 테이블을 2개 만들고 샘플 데이터를 몇 개 삽입합니다.

CREATE OR REPLACE TABLE mhtab1(c1 NUMBER,c2 DOUBLE,c3 TEXT,c4 DATE);
CREATE OR REPLACE TABLE mhtab2(c1 NUMBER,c2 DOUBLE,c3 TEXT,c4 DATE);

INSERT INTO mhtab1 VALUES
    (1, 1.1, 'item 1', to_date('2016-11-30')),
    (2, 2.31, 'item 2', to_date('2016-11-30')),
    (3, 1.1, 'item 3', to_date('2016-11-29')),
    (4, 44.4, 'item 4', to_date('2016-11-30'));

INSERT INTO mhtab2 VALUES
    (1, 1.1, 'item 1', to_date('2016-11-30')),
    (2, 2.31, 'item 2', to_date('2016-11-30')),
    (3, 1.1, 'item 3', to_date('2016-11-29')),
    (4, 44.4, 'item 4', to_date('2016-11-30')),
    (6, 34.23, 'item 6', to_date('2016-11-29'));
Copy

그리고 MinHash 상태를 사용하여 두 세트(mhtab1 및 mhtab2 테이블)의 유사성을 대략적으로 구합니다.

SELECT APPROXIMATE_SIMILARITY(mh) FROM
    ((SELECT MINHASH(100, *) AS mh FROM mhtab1)
    UNION ALL
    (SELECT MINHASH(100, *) AS mh FROM mhtab2));

+----------------------------+
| APPROXIMATE_SIMILARITY(MH) |
|----------------------------|
|                       0.79 |
+----------------------------+
Copy

이러한 두 테이블의 유사성 인덱스는 0.79로 근사화되지만, 정확한 값은 0.8(즉, 4/5)입니다.

언어: 한국어