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)입니다.

언어: 한국어