구조화 된 데이터의 퍼지 매칭

Question

데이터베이스에 앉아있는 구조화 된 레코드의 상당히 작은 코퍼스가 있습니다. 웹 양식 (테이블 스키마와 같은 방식으로 구조화)을 통해 제출 된 단일 레코드에 포함 된 정보의 작은 부분 (테스트 레코드라고 부르겠습니다). 테스트 레코드와 가장 일치 할 가능성이 가장 높은 레코드는 물론 검색어가 레코드와 얼마나 밀접하게 일치하는지에 대한 신뢰 추정을 제공합니다. 이 검색의 주요 목적은 누군가가 코퍼스에있는 레코드를 복제하는 레코드를 입력하려고하는지 여부를 발견하는 것입니다. 테스트 레코드가 속임수가 될 가능성이 합리적이며, 테스트 레코드가 속임수가 될 수있는 합리적인 기회가 있습니다.

레코드의 폭은 약 12000 바이트이며 총 레코드 수는 약 150,000입니다. 테이블 스키마에는 110 개의 열이 있으며 검색의 95%가 가장 일반적으로 검색되는 열 5%에 있습니다.

데이터는 이름, 주소, 전화 번호 및 기타 산업 별 숫자와 같은 것입니다. 코퍼스와 테스트 레코드 모두에서 손으로 입력되며 개별 필드 내에서 반 구조화됩니다. 처음에는 홍당무가 "손으로 컬럼의 무게와 그 안에 단어 토큰을 일치시킨다"고 말할 수 있지만 쉽지는 않습니다. 나도 그렇게 생각했다 : 전화 번호를 얻으면 완벽한 일치를 나타낼 것이라고 생각했다. 문제는 토큰 주파수가 크기에 따라 다르지 않는 형태의 단일 필드가 없다는 것입니다. 전화 번호는 코퍼스에서 100 회 또는 코퍼스에서 1 회 나타날 수 있습니다. 다른 필드도 마찬가지입니다. 이것은 현장 수준에서의 가중치가 비현실적입니다. 괜찮은 일치를 얻으려면 더 세밀한 접근 방식이 필요합니다.

나의 초기 계획은 해시 해시를 만드는 것이며, 최상위 레벨은 필드 이름입니다. 그런 다음 주어진 필드에 대한 코퍼스에서 모든 정보를 선택하고, 포함 된 데이터를 정리하고, 위생화 된 데이터를 토큰 화하고, 두 번째 레벨에서 토큰을 해시하고, 토큰을 키로 키와 주파수로 값으로 값으로 사용합니다.

나는 주파수를 가중치로 사용합니다. 참조 코퍼스의 토큰 주파수가 높을수록 테스트 레코드에서 발견되면 그 토큰에 부착 된 무게가 줄어 듭니다.

첫 번째 질문은 방의 통계 학자를위한 것입니다. 주파수를 어떻게 무게로 사용합니까? n, 레코드 수, f (t), 토큰 t가 코퍼스에 나타나는 주파수, 레코드가 원본이고 복제가 아닌 확률 O 사이에 정확한 수학적 관계가 있습니까? 테스트 레코드는 실제로 테스트가 주어진 레코드 X이며 X는 동일한 필드에 동일한 t를 포함합니까? 여러 필드에서 여러 토큰 경기의 관계는 어떻습니까?

나는 진심으로 의심의 여지가 있기 때문에, 나를 가까이하게하는 것이 있지만 마법의 요인으로 가득 찬 완전히 임의의 해킹보다 낫습니까?

그 금지, 누군가가 이것을 할 방법이 있습니까?

특히 토큰 주파수 조회 테이블과 같은 데이터베이스에서 다른 테이블을 유지하지 않는 다른 제안에 특히 관심이 있습니다.

Answer 1

아마도이 다르지만 비슷한 질문에서 몇 가지 아이디어를 얻을 수 있습니다.계산-컨텍스트 감지 텍스트-상관.

당면한 문제에 더 구체적으로, 여기에 몇 가지 생각과 아이디어가 있습니다.

우선, 매우 비뚤어진 사용법을 인정하면 (6 ~ 10 개의 속성 만 사용의 95%를 커버 할 때) 속성에 비대칭 노력을 적용 할 수 있습니다. 즉, 프로그래밍 시간과 런타임 측면에서 더 많은 투자 CPU 할당량은 100-oDD 추가 속성보다 이러한 소수의 속성을 다루는 것입니다.

데이터베이스에서 가능한 중복을 일치시키기위한 입력으로 제공되는 비교적 적은 양의 데이터, 일반적으로 사용되는 비교적 작은 속성 세트, 그리고이 (전화 번호, 주소, 이름 ...)의 일반적인 의미론은 손으로 만들어진 솔루션을 제안합니다. 하나보다는 완전히 기계 학습을 기반으로합니다.

참고 : 그 후 많은 제안을 모든 속성에 적용 할 필요는 없습니다 (사실상 모든 사용법 중 수십 미만이므로 처음에는 다른 속성에 많은 투자를 할 필요가 없습니다.

• 데이터를 정규화하십시오
  원래 필드 값을 변경할 수없는 경우 해당 열을 XXX가 원래 이름 인 "Norm_XXX"Coluumn에 해당 열을 복제 할 수 있습니다.
  무엇, 정규화하는 방법은 각 속성에 따라 다를 수 있습니다. "무료 텍스트"와 같은 데이터의 경우, 선행 또는 후행 공간이없고 단어 사이에 하나의 공간, 탭 및 인쇄 할 수없는 문자가 없는지 확인하십시오. 모든 대문자 또는 모든 소문자를 사용하십시오 (이벤트는 원본 / 디스플레이 텍스트에는 믹스가 포함될 수 있습니다. 균일 한 케이싱을 가정하여 처리가 더 빨라집니다). 보다 구체적으로 주소 및/또는 회사 이름의 경우 일반적인 용어가 표준 양식 (st for Street, ST 및 ST 등)으로 변환 할 수 있습니다 (이 목록을 유지하십시오.이 목록은 사용자 검색 기준에도 적용됩니다. ). 정규화의 일부는 일부 소음 단어를 완전히 떨어 뜨리는 것일 수 있습니다 (회사 이름 끝에 Co, Inc, Gmbh).
• 계산 된 몇 가지 열을 만듭니다
  예를 들어 텍스트가있는 것과 같은 것과 같은 것과 같은 것과 같은 것과 같은 것과 같은 것과 같은 것과 같은 것과 같은 것과 같은 것과 같은 것과 같은 것과 같은 것과 같은 것과 같은 것과 같은 것과 같은 것과 같은 텍스트가있는 것과 같은 것과 같은 것, 후행 와일드 카드로 검색 할 수있는 속성에 대해
• 일부 속성에 대해 Soundex와 유사한 변환을 고려하십시오.
• 전체 텍스트 색인, 개별적으로 모든 텍스트와 같은 열
• 6 ~ 10 개의 많이 사용 된 열에서 일반 (SQL) 인덱스 작성

위의 모든 것은 실제로 경기를 수행하기위한 오프라인 시간 준비입니다. 이제 .. 사용자는 쿼리를 입력합니다 ... 여기에 처리하는 방법에 대한 몇 가지 아이디어가 있습니다.

• 그것을 보증하는 검색 기준을 정상화하십시오
• 여러 검색을 실행합니다 ...
  이것은 약간 까다 롭습니다. 이러한 검색을 수행하기위한 몇 가지 부분적으로 상충되는 목표가 있습니다. 우리는 "잠재적 일치"의 수를 현저히 줄이고 싶습니다. 150,000 개의 레코드를 사용자가 제공 한 기준과 전체 일대일로하는 것은 효과적으로 실용적이지 않습니다. 예를 들어, 일치하는 논리 중 일부는 주어진 데이터베이스 레코드 필드와 검색 기준 사이의 편집 거리를 계산할 수 있습니다. 또한 회사 이름의 오타로 인해 "잠재적 일치"목록에서 레코드를 제외하지 않도록하고자합니다. 마지막으로 잠재적 인 매치 목록을 순위로운 방식으로 제공하고자합니다.
  이러한 검색을 수행하는 방법은 사전 정의 된 휴리스틱을 따릅니다 (전략 디자인 패턴이이를 위해 잘 작동하여 사용자가 제공 한 입력에 따라 검색이 실행되는 방식으로 Flexibilty가 가능하다는 것을 알았습니다). 간단히 말해서 우리는 가장 선택적이고 관련된 속성에서 가장 선택적인 단어를 검색하고 "Hits"Found '(우리가 우리가 찾은) 또는 "(Union) 또는"다른 검색 결과와 함께 "몇 가지가있을 때까지 몇 가지가 있습니다. 백 레코드.
• "전위 일치"레코드의 각 속성과 해당 검색 기준 사이의 유사성 값을 계산합니다. 이 값에 계수를 적용 할 수 있습니다 (회사 이름 [부분]이 도시 경기와 일치하는 것이 더 많은 무게를 내도록 허용)
• 완전한 레코드에 대한 Overal 유사성 값을 기록하십시오 (전체 검색 기준 vs. 전체 검색 기준)

• 검토를 위해 최종 사용자와 유사성 값의 특정 임계 값을 초과하는 레코드를 표시하십시오.

  마지막으로 부분적으로 자동화 된 프로세스가 제공되므로 최종 사용자가 제공 한 일부 피드백을 기반으로 일부 매개 변수를 변경할 수 있습니다. (이것은 매우 까다 롭습니다. 다른 게시물을 위해 이것을 유지하겠습니다 ;-))