2019/05/25/minhash-algorithm-explained

[utterances-bot]

쉽게 설명한 Minhash 알고리즘, Haandol

Minhash concept and implementation

http://blog.haandol.com/2019/05/25/minhash-algorithm-explained.html

[dbwodlf3]

Minhash 에서

3. 처음 선택된 permutation index 는 항상 1 이고, Matrix 의 5번째 row 를 가리키고 있다. 이 부분이 정확히 무슨말을 하는지 잘 이해가 안갑니다. 다른 것들을 보면은. 무슨 인덱스를 선택하는게 아니라, 그냥. 순열값중에서 가장 최소로 하는 값이 1인 경우에 해당 값을 Signature Matrix로 하는 것 아닌가요?

[haandol]

이해하신 내용이 맞는 것 같은데요, 순열값중 최소값만 쓰는게 아니라 작은 값부터 순서대로 진행한다고 보시면 됩니다.

[2,3,7,6,1,5,4] 라는 순열을 생성한 상태에서 작은값부터 순서대로 사용하게 되고, 가장 작은 값이 1이니 항상 1 을 사용하겠죠. 1은 5번째 row 에 있으니 5번째 row 를 기준으로 계산하고, 계산되지 않은 값이 남아있거나 순열이 끝날 때까지 순열 값을 하나씩 증가하면서 계산하게됩니다.

[dbwodlf3]

답변 감사합니다.

"[2,3,7,6,1,5,4] 라는 순열을 생성한 상태에서 작은값부터 순서대로 사용하게 되고, 가장 작은 값이 1이니 항상 1 을 사용하겠죠. 1은 5번째 row 에 있으니 5번째 row 를 기준으로 계산하고," 라는 말씀은. 순열의 값중 가장 작은 값 1을 기준으로 방향성을 가지고 계산이 진행된다는 말씀이신가요?

"계산되지 않은 값이 남아있거나 순열이 끝날 때까지 순열 값을 하나씩 증가하면서 계산하게됩니다." 모든 값이 계산되었다는건, 비교할 모든 집합이 "1"인 경우를 마지했다는 의미인건가요? "순열이 끝날 때까지 순열 값을 하나씩 증가하면서 계산하게됩니다." 라는 말은 맨 위에서부터 [2] => [3] => [7] => [6] 이런 식으로 가는게 아니라. 1,2,3,4,5,6,7 이런식으로 증가한다는 말씀이신가요?

제가 이해하기로는. "[2,3,7,6,1,5,4]" 라는 순열값이 있을 때에. [2] => [3] => [7] => [6] => [1] => [5] => [4] 순으로 그냥 차례대로 진행하고.(모든 순열을 순회하고) 이 중에서. 해당 순열에 해당하는 원소의 값이 1인 경우. 그리고 그 값이 가장 작은 경우를 Signature의 Matrix 값으로 한다는 것으로 알고 있습니다. 값이 없는 경우에는 무한대로 두고요.

ㅠㅠ. 맞는지 모르겠네요. 저는 맞다고 생각하는데..

[haandol]

글에 대한 개개인의 이해에는 차이가 있기 때문에 제가 그부분에 대해서 설명드리기는 어려울 것 같습니다.

다만 원문은 말씀하신 내용과 다르게, 제가 말한 내용대로, 설명하고 있다고 생각합니다. 원문과 다르게 설명된 내용이 있다면 알려주세요, 바로 수정하겠습니다.

그리고 signature maxtrix 가 해쉬역할을 하는데 해쉬 값이 무한대를 가지는 것은 좀 어색(?)하다고 생각합니다.

signature matrix 의 값은 순열의 인덱스입니다. 저는 순열의 인덱스가 1부터 시작하는 이유도 탈출조건이 끝났는데도 signature matrix 가 업데이트 되지 않으면 0으로 세팅되기 편하게 하려고 한다고 이해했습니다.

[haandol]

위에 구현파트 바로 위의 그림을 보시면 3개의 순열이 있습니다. 3개의 순열로 구현 결과인 signature matrix 를 어떻게 만들 수 있는지, 이해하신 내용으로 만들어보시면 바로 알 수 있을 것 같습니다.

말씀하신 내용대로 순열을 진행하면 해당 signature 가 만들어지지 않을 것 같다고 생각되네요.

[dbwodlf3]

답변 감사합니다.

"3. 처음 선택된 permutation index 는 항상 1 이고, Matrix 의 5번째 row 를 가리키고 있다." 에 해당하는 내용은 없는 것 같습니다. "Step 2: Hash function is the index of the first (in the permuted order) row in which column C has value 1. Do this several time (use different permutations) to create signature of a column." 본문을 살펴봤을 때에 이 부분과 유사한데. 제가 해당 문장을 해석하기로는. minhash 를 사용하기위한 hash function 으로는. 순열의 인덱스 값을 기준으로, 해당 컬럼이 1의 값을 갖게 되는 경우. 해당 순열의 값이 hash function의 값이 된다. 라는 표현인 것 같습니다.

Mining of Massive Datasets 책의 PPT 자료를 사용한 것으로 보입니다! 해당 책의 83page 3.3.5 Computing Minhash Signatures 에 해당하는 내용으로 보입니다.

귀결하자면. 본문에서 "3. 처음 선택된 permutation index 는 항상 1 이고, Matrix 의 5번째 row 를 가리키고 있다." "두번째 index 는 항상 2 이고, 해당하는 Matrix 의 C1, C3 이 1 이므로, signature matrix 의 1, 3 번째에 permutation index 인 2 를 채워서 permutation 하나의 signature 를 만들어냈다." 이라는 표현은 제가 잘못이해하여 틀린게 아니라면 다소 이상한 표현으로 보입니다.

[dbwodlf3]

아.. 음! 네. 곰곰히 생각해보니. 말씀하신게 틀리지 않으신 것 같습니다. min 값을 가지기는 하는데. 이 때 min 값이 1,2,3,4,5,6,7,8,9 이런식으로 증가하게 되니. 가장 작은 min의 값을 우선으로 해서 순회를 하게되면... 으로 이해할 수 있을 것 같습니다. 전부다 순회하기는 하는데. 이 때. 가장 작은값의 순서대로. 그러니까 1,2,3,4,5,6,7,8,9의 값으로 순서대로 진행하게 되고. 만약에 Signature를 전부다 만들면 순회를 거기에서 종료. 음..

답변 감사합니다! ^^..

[dbwodlf3]

"3. 처음 선택된 permutation index 는 항상 1 이고, Matrix 의 5번째 row 를 가리키고 있다." => "순열의 가장 작은값 1은 5번째의 row를 가리키고 있다."

"5. 두번째 index 는 항상 2 이고, 해당하는 Matrix 의 C1, C3 이 1 이므로, signature matrix 의 1, 3 번째에 permutation index 인 2 를 채워서 permutation 하나의 signature 를 만들어냈다." => "순열의 두번째로 작은 값은 2이고, ~"

으로 내용을 수정하면 조금 더 매끄럽지 않을까. 의견을 남겨봅니다. Reply. 감사합니다 ^^.

[haandol]

피드백 감사합니다. 수정했습니다. :D

[ej-han]

안녕하세요. 유용한 알고리즘을 쉽게 풀어써주셔서 도움을 많이 받았습니다. 질문이 하나 있어서 코멘트를 남깁니다. 구현 코드를 보니 document1, document2의 jaccard similarity를 구하게 되어있는데, 실제로는 단순히 몇 가지의 문서가 아니라 수백만개의 문서의 유사도를 구하는 경우가 많을거 같습니다. 예를 들면 백만개 문서의 유사도를 구한다면 반복 수가 엄청나게 많아질텐데 실제로는 어떻게 처리하나요?

[haandol]

안녕하세요, 어떤 방식을 써야하는지는 항상 비즈니스 요구사항에 따라 결정하게 됩니다. 어떠한 경우든 데이터가 많을 경우 사용하는 일반적인 방식들을 쓰시면 됩니다.

실시간 작업이면 주로 샤딩을 통해 연산을 분산하게 되고, 배치 작업이면 더 다양한 옵션들이 있습니다.

https://haandol.github.io/2020/02/28/elasticsearch-dense-vector-consinesimilarity.html 여기서 1초안에 이미지를 검색해야할 경우 엘라스틱서치를 사용해서 검색하는 방법을 간략히 소개하고 있습니다.