겹치는 식별자를 기반으로 문서를 클러스터하는 방법은 무엇입니까?

Question

3.5M 문서가 있고 각 문서에는 k 개의 고유 식별자가 있습니다. 유사성에 따라 문서를 클러스터해야합니다. m 개의 중복 식별자가 있으면 두 개의 문서가 유사합니다. m < k

클러스터에서 두 개의 문서를 선택하면 (클러스터 크기가 1보다 큰 경우) 최소한 m-overlapping 식별자가 있어야합니다.

빠른 방법은 무엇입니까? 또한 클러스터 수를 최소화하고 싶습니다.

Answer 1

정확하게 이해한다면 그래프 클러스터링을 찾고 해결하기가 어렵습니다.

Here is an article 그래프 클러스터링에 대한 것이지만 Google에서 더 많은 정보를 얻을 수 있습니다.

"가장 빠른 방법"은 무엇입니까? 데이터 집합이나 환경에 대한 정보를 제공하지 않으면 대답하기가 불가능합니다. 그러나, 그래프 클러스터링 기능이 내장 된 그래프 데이터베이스에로드하는 것이 어떻게 든 매우 빠르게 진행될 것으로 생각됩니다. 우리가 지금은 "모든 -에 - 어떤"이중 해시의 관계는, 우리가 어떤을 찾을 수 있습니다 가지고 있기 때문에

define calculate_similarity(doc1, doc2) 
    score = 0 
    foreach identifier in doc1.identifiers 
     score += 1 if doc2.identifiers.contain(identifier) 
    return score 

similarity_double_hash = new hash(default = new Hash) 
foreach document1 in all_documents 
    foreach document2 in all_document 
     next if document1 == document2 
     similarity = calculate_similarity(document1,document2) 
     similarity_double_hash[document1][document2] = similarity 
     similarity_double_hash[document2][document1] = similarity 

:이 문제를 해결하는 일반적인 절차는

는 여기에 몇 가지 의사 코드 그 문서의 "m"을 보는 것만으로 문서가 클러스터링됩니다. 동일한 m 번호를 가진 두 개가 클러스터에 있습니다. 이러한 일 개 그룹의

예 :

define get_groups_from_document(doc, similarity_double_hash) 
    groups = new hash(default = new list) 
    foreach sim_score, hash_key in similarity_double_hash[doc] 
     groups[sim_score].append(hash_key) #Remember, hash_key is the other document 
    return groups 

그룹 리턴되는 문서로부터 그 그룹, 원래의 일부인 문서 m의 값에 대한 포인터 해시. 다른 문서는 그룹 내의 다른 문서에 대한 점수가 이상이고m 이상인 것으로 보증됩니다. 정확하게 m 인 것은 보증되지 않습니다.

다른 문서에서 시작하는 경우 동일한 m 값은 목록에 다른 문서를 포함 할 수 있으며, 아마도 포함하게됩니다.

주어진 m에 대해 가장 큰 클러스터를 가져 오려면 가장 큰 클러스터를 가져올 원본 문서를 찾아야합니다. 또한 문서는 여러 클러스터의 일부가 될 수 있습니다. 당신이 원하지 않는다면, 그래프 클러스터링의 어려운 문제로 처음에는 다시 돌아온 것입니다.

이제

all_groups = new hash 
foreach document in all_documents 
    all_groups[document] = get_groups_from_document(document, similarity_double_hash) 

max_groups = new hash 
foreach group in all_groups 
    foreach score, document_list in group 
     if max_groups[score].length < document_list.length 
      max_groups[score] = document_list 

foreach score, document_list in max_groups 
    print "Largest group for " + score + " is " + document_list.to_string 

당신이 어떤 주어진 m의 가장 큰 그룹의 벌금 목록을 가지고 있지만, 내가 말했듯이, 문서 일 수 있습니다

가 각각의 주어진 m의 가장 큰 그룹을 찾으려면, 당신은이 작업을 수행 할 수 있습니다 여러 개의 목록과 여기에있는 "m"그룹은 "정확히 m"이 아니라 실제로 "m-or-greater"입니다.