키 - 값 쌍의 클러스터링

Question

이 문제가 있습니다. 특정 고유 ID를 키로 사용하고 문자열을 값으로 사용하는 매우 큰 세트 (수백만)의 키 - 값 쌍이 있습니다 (두 개 이상의 키에 대해 문자열이 정확히 같을 수 있음). 그룹 1은 신분증 문자열 쌍 그룹 2 그룹핑 실제로 쌍 값인 문자열 사이의 유사성을 수행해야 다른 쌍 등 포함 포함 함께 같이 I 그룹화 이러한 키 - 값 쌍을 갖는다. 나는 이미이 문자열들 사이에 Levenshtein Distance를 구현하고 임계 거리보다 적은 거리를 가진 쌍을 함께 그룹화했습니다. 그리고 저는 이것을 전통적인 (매우 나쁜) 방식으로 구현했습니다 : 각 문자열을 다른 모든 것과 비교하십시오.

나는이를 최적화하는 방법에 대한 몇 가지 도움말이 필요합니다. Hadoop의 Map-Reduce를 사용하여 키 - 값 쌍을 실제로 그룹화 할 수 있습니까? map과 reduce 함수에 대한 입력은 개별적이고 독립적이어서 '그룹화'할 수 없다고 생각합니다. 그리고 이것은 k-means 클러스터링 문제입니까? 다른보다 빠르고 효율적인 기술을 제안 할 수 있습니까? 감사합니다. .

Answer 1

맞춤법 검사기는 부르크 하르트 - 켈러 나무 (BK-트리) 예를 들어 여기에 https://github.com/mkarlesky/csharp-bk-tree 발견을 사용한다. 이것은 기존 목록에 대해 새 단어를 테스트 할 때 매우 빠르지 만 문자열을 다음 문자열로 변경하는 데 필요한 작업 수를 기반으로 "거리"측정을 제공합니다. 부울을 제공하는 간단한 "포함"테스트와 달리이 옵션을 사용하면 사용 가능한 옵션을 구성 할 수 있습니다. 여기에 대한 자세한 내용은 http://blog.notdot.net/2007/4/Damn-Cool-Algorithms-Part-1-BK-Trees을 참조하십시오. 클러스터링에 도움이되는 거리를 사용할 수 있다고 생각합니다.

나는 BK 나무에 대한 중요한 것은 당신이 Levenshtein 거리를 계속 사용할 수 있다는 것입니다 같아요. 하지만 그걸 이미 사용하고 계신 겁니까? 이 기법은 k-means처럼 임의의 수의 클러스터를 선택하는 데 이상적이지 않습니다. 문자열을 사용하지 않는

http://www.codethinked.com/multi-threaded-k-means-clustering-in-net-40

예를 :하지만 여기에 C#으로 당신이 일을 좀 더 빠르게 할 수있는 K-수단의 맥락에서 몇 가지 새로운 병렬 처리 활용에 대한 흥미로운 기사를 참조했다 하지만 AsParallel 개념은 이미 가지고있는 솔루션의 성능 향상에 도움이됩니까?