Search

KR-102961813-B1 - METHOD AND APPARATUS FOR DETERMINING SIMILARITY OF POI NAMES

KR102961813B1KR 102961813 B1KR102961813 B1KR 102961813B1KR-102961813-B1

Abstract

적어도 하나의 프로세서에 의해 동작하는 장소명 유사도 판단 장치의 동작 방법으로서, 대량의 장소명들에서 분리된 형태소들을 기초로, 임의 장소명에 포함된 형태소의 형태소 속성들을 판단하기 위한 형태소 사전을 구축하는 단계, 상기 형태소 사전을 이용하여, 훈련용 장소명쌍의 형태소 속성들을 추출하고, 각 장소명쌍에서 형태소 속성들의 일치 여부를 나타내는 문자열 특징 벡터를 훈련 데이터로 생성하는 단계, 그리고 상기 훈련 데이터를 이용하여, 임의 장소명쌍의 문자열 특징 벡터로부터 상기 임의 장소명쌍의 장소명 유사도를 출력하는 유사도 판단 모델을 훈련시키는 단계를 포함한다.

Inventors

  • 박은호

Assignees

  • 주식회사 카카오

Dates

Publication Date
20260506
Application Date
20220817

Claims (20)

  1. 적어도 하나의 프로세서에 의해 동작하는 장소명 유사도 판단 장치의 동작 방법으로서, 대량의 장소명들에서 분리된 형태소들의 출현 빈도를 기초로 형태소 속성들을 부여하고, 임의 장소명에 포함된 형태소의 형태소 속성들을 판단하기 위한 형태소 사전을 구축하는 단계, 상기 형태소 사전을 이용하여, 훈련용 장소명쌍의 형태소 속성들을 추출하고, 각 장소명쌍에서 형태소 속성들의 일치 여부를 나타내는 문자열 특징 벡터를 훈련 데이터로 생성하는 단계, 그리고 상기 훈련 데이터를 이용하여, 임의 장소명쌍의 문자열 특징 벡터로부터 상기 임의 장소명쌍의 장소명 유사도를 출력하는 유사도 판단 모델을 훈련시키는 단계를 포함하며, 상기 형태소 속성들은 출현 빈도가 미리 설정된 기준 이상인 일반 형태소, 그리고 출현 빈도가 미리 설정된 기준 미만인 고유 형태소를 포함하는, 동작 방법.
  2. 제1항에서, 상기 형태소 속성들은 지역명 형태소, 그리고 해당 형태소에 매핑된 카테고리 중 적어도 하나를 더 포함하는, 동작 방법.
  3. 제1항에서, 상기 문자열 특징 벡터는 상기 형태소 사전을 기초로, 상기 임의 장소명쌍의 형태소 속성별로 일치 비율과 불일치 비율을 포함하는 벡터인, 동작 방법.
  4. 제1항에서, 상기 훈련 데이터를 생성하는 단계는 대량의 장소명 데이터에서 두 장소명을 랜덤 추출하고, 각 장소명쌍의 문자열 특징 벡터에 비동일 장소에 해당하는 정답을 레이블링하여 비동일 장소명쌍에 대한 훈련 데이터를 생성하는, 동작 방법.
  5. 제4항에서, 상기 훈련 데이터를 생성하는 단계는 문자열 유사도 구간별로 일정 수의 장소명쌍을 랜덤 추출하여, 상기 비동일 장소명쌍에 대한 훈련 데이터를 생성하는, 동작 방법.
  6. 삭제
  7. 제1항에서, 상기 형태소 사전을 구축하는 단계는 상기 대량의 장소명들에서 분리한 형태소별로, 각 장소명에 해당하는 카테고리를 매핑하고, 임의 카테고리와 상관 관계가 있는 적어도 하나의 형태소를 상기 형태소 사전에 등록하고, 상기 임의 카테고리에 매핑된 복수의 형태소들은 상기 임의 카테고리를 형태소 속성으로 가지는, 동작 방법.
  8. 제1항에서, 상기 형태소 사전을 구축하는 단계는 상기 대량의 장소명들에서 분리한 형태소들 중에서, 임의 지역명과 상관 관계가 있는 적어도 하나의 형태소를 상기 형태소 사전에 등록하고, 상기 임의 지역명에 매핑된 형태소는 지역명 형태소를 형태소 속성으로 가지는, 동작 방법.
  9. 제1항에서, 상기 형태소 사전을 이용하여 입력 장소명쌍의 형태소 속성들을 추출하는 단계, 상기 입력 장소명쌍의 형태소 속성들을 기초로 상기 유사도 판단 모델의 입력 벡터를 생성하는 단계, 그리고 상기 유사도 판단 모델로부터 상기 입력 벡터에 해당하는 장소명 유사도를 획득하는 단계 를 더 포함하는, 동작 방법.
  10. 적어도 하나의 프로세서에 의해 동작하는 장소명 유사도 판단 장치의 동작 방법으로서, 대량의 장소명들이 포함된 장소 데이터를 수집하고, 상기 대량의 장소명들을 형태소 단위로 분리하는 단계, 상기 대량의 장소명들에서 출현하는 형태소별 출현 빈도를 기초로 형태소 속성들을 부여하여 형태소 사전을 구축하는 단계, 상기 형태소 사전을 이용하여, 임의 장소명쌍에서 분리된 각 형태소를 출현 빈도가 미리 설정된 기준 미만인 고유 형태소 또는 출현 빈도가 미리 설정된 기준 이상인 일반 형태소로 판단하는 단계, 상기 임의 장소명쌍에서 상기 고유 형태소 또는 상기 일반 형태소의 일치 여부를 포함하는 문자열 특징 벡터를 생성하는 단계, 그리고 상기 문자열 특징 벡터를 기초로, 상기 임의 장소명쌍의 장소명 유사도를 판단하는 단계 를 포함하는 동작 방법.
  11. 제10항에서, 상기 형태소 사전을 구축하는 단계는 상기 대량의 장소명들에서 분리한 형태소별로, 각 장소명에 해당하는 카테고리를 매핑하고, 임의 카테고리와 상관 관계가 있는 적어도 하나의 형태소를 상기 형태소 사전에 등록하며, 상기 임의 카테고리에 매핑된 복수의 형태소들은 상기 임의 카테고리를 형태소 속성으로 가지는, 동작 방법.
  12. 제11항에서, 상기 형태소 사전을 구축하는 단계는 상기 대량의 장소명들에서 출현한 형태소별로, 대응하는 장소명의 카테고리를 매핑하고, 각 형태소에 매핑된 카테고리가 상기 임의 카테고리에 일치하는 빈도를 이용하여, 상기 임의 카테고리와 상관 관계가 있는 적어도 하나의 형태소를 결정하는, 동작 방법.
  13. 제11항에서, 상기 문자열 특징 벡터를 생성하는 단계는 상기 형태소 사전을 이용하여 상기 임의 장소명쌍의 형태소들에 매핑된 카테고리를 추출하고, 상기 임의 장소명쌍의 카테고리 일치 여부를 더 포함하는 상기 문자열 특징 벡터를 생성하는, 동작 방법.
  14. 제10항에서, 상기 형태소 사전을 구축하는 단계는 상기 대량의 장소명들에서 분리한 형태소들 중에서, 임의 지역명과 상관 관계가 있는 적어도 하나의 형태소를 상기 형태소 사전에 등록하고, 상기 임의 지역명에 매핑된 형태소는 지역명 형태소를 형태소 속성으로 가지는, 동작 방법.
  15. 제14항에서, 상기 문자열 특징 벡터를 생성하는 단계는 상기 형태소 사전을 이용하여 상기 임의 장소명쌍의 형태소들 중에서 임의 지역명에 매핑된 지역명 형태소를 추출하고, 상기 지역명 형태소의 일치 여부를 더 포함하는 상기 문자열 특징 벡터를 생성하는, 동작 방법.
  16. 적어도 하나의 프로세서에 의해 동작하는 장소명 유사도 판단 장치로서, 대량의 장소명들에서 분리된 형태소들의 출현 빈도를 기초로 형태소 속성들을 부여하고, 임의 장소명에 포함된 형태소의 형태소 속성들을 판단하기 위한 형태소 사전을 구축하는 형태소 사전 구축기, 상기 형태소 사전을 이용하여 임의 장소명쌍의 형태소 속성들을 추출하고, 형태소 속성별로 일치 비율과 불일치 비율을 포함하는 문자열 특징 벡터를 생성하는 특징 추출기, 그리고 상기 임의 장소명쌍의 문자열 특징 벡터로부터 상기 임의 장소명쌍의 장소명 유사도를 출력하도록 훈련된 유사도 판단 모델을 포함하며, 상기 형태소 속성들은 출현 빈도가 미리 설정된 기준 이상인 일반 형태소, 그리고 출현 빈도가 미리 설정된 기준 미만인 고유 형태소를 포함하는, 장소명 유사도 판단 장치.
  17. 제16항에서, 상기 형태소 사전 구축기는 상기 대량의 장소명들을 형태소 단위로 분리하고, 상기 대량의 장소명들에서 출현하는 형태소별 출현 빈도를 누적해서 출현 빈도 사전을 구축하는, 장소명 유사도 판단 장치.
  18. 제16항에서, 상기 형태소 사전 구축기는 상기 대량의 장소명들에서 분리한 형태소별로, 각 장소명에 해당하는 카테고리를 매핑하고, 임의 카테고리와 상관 관계가 있는 적어도 하나의 형태소가 매핑된 카테고리 사전을 구축하는, 장소명 유사도 판단 장치.
  19. 제16항에서, 상기 형태소 사전 구축기는 상기 대량의 장소명들에서 분리한 형태소들 중에서, 임의 지역명과 상관 관계가 있는 적어도 하나의 형태소가 매핑된 지역명 사전을 구축하는, 장소명 유사도 판단 장치.
  20. 제16항에서, 대량의 장소명 데이터에서 문자열 유사도 구간별로 일정 수의 비동일 장소명쌍들을 랜덤 추출하고, 동일 장소명쌍들 및 상기 비동일 장소명쌍들의 문자열 특징 벡터, 그리고 해당 문자열 특징 벡터의 정답으로 구성된 훈련 데이터를 생성하며, 상기 훈련 데이터를 이용하여 상기 유사도 판단 모델을 훈련시키는 훈련기 를 더 포함하는 장소명 유사도 판단 장치.

Description

장소명 유사도 판단 방법 및 장치{METHOD AND APPARATUS FOR DETERMINING SIMILARITY OF POI NAMES} 본 개시는 장소명 유사도 판단에 관한 것이다. 지도 서비스 제공자는 지도에 장소(Point of Interest, POI)를 표시하기 위해, 장소와 관련된 다양한 원천 데이터를 수집하는데, 원천 데이터에 동일 장소의 데이터가 중복해서 수집된다. 사용자의 혼란을 막기 위해 중복 장소를 제거해야 하는데, 사람이 모든 데이터를 검수할 수 없으므로 일정 반경 이내에서 장소간 유사도를 측정하는 알고리즘이 사용된다. 장소간 유사도를 측정할 때 장소명이 가장 중요한 특징으로 사용된다. 지금까지는 편집 거리라고 불리는 레번슈타인 거리(levenshtein distance) 기반의 리벤슈테인 점수(levenshtein score)를 장소명 유사도로 사용하였다. 레번슈타인 거리는 두 문자열이 동일해지기 위해 요구되는 최소 문자 편집 횟수로서, 레번슈타인 점수가 클수록 유사도가 높다고 판단하기 위해, 레번슈타인 점수는 문자 길이로 정규화된 레번슈타인 거리를 1에서 뺀 값(levenshtein score=1-levenshtein distance/text length)으로 정의된다. 하지만, 레번슈타인 점수는 두 문자열을 비교하기 때문에, 사람이 보기에는 의미적으로 동일한 장소를 가리키는 장소명(예를 들면, 서울부동산과 서울공인중개사, 부성해물아구와 부성식당, 반디모텔과 호텔반디 등)이지만, 문자열이 다른 경우 레번슈타인 점수가 낮아서 다른 장소로 분류되는 한계가 있다. 이를 보완하기 위해, 문자열 이외에 다른 정보(예를 들면, 전화번호, 대표자명 등)를 활용하여 동일 장소인지를 판단할 수 있으나, 수집한 데이터에 전화번호 등이 포함되어 있지 않을 수 있어서, 동일 장소 판단이 쉽지 않다. 도 1은 한 실시예에 따른 장소명 유사도 판단 장치의 구성도이다. 도 2는 한 실시예에 따른 훈련 데이터를 위한 장소명쌍 랜덤 추출 방법을 설명하는 도면이다. 도 3은 한 실시예에 따른 유사도 판단 모델의 훈련 방법 흐름도이다. 도 4는 한 실시예에 따른 장소명 유사도 판단 방법의 흐름도이다. 도 5는 한 실시예에 따른 장소명 유사도 판단 방법의 흐름도이다. 아래에서는 첨부한 도면을 참고로 하여 본 개시의 실시예에 대하여 본 개시가 속하는 기술 분야에서 통상의 지식을 가진 자가 용이하게 실시할 수 있도록 상세히 설명한다. 그러나 본 개시는 여러 가지 상이한 형태로 구현될 수 있으며 여기에서 설명하는 실시예에 한정되지 않는다. 그리고 도면에서 본 개시를 명확하게 설명하기 위해서 설명과 관계없는 부분은 생략하였으며, 명세서 전체를 통하여 유사한 부분에 대해서는 유사한 도면 부호를 붙였다. 명세서 전체에서, 어떤 부분이 어떤 구성요소를 "포함"한다고 할 때, 이는 특별히 반대되는 기재가 없는 한 다른 구성요소를 제외하는 것이 아니라 다른 구성요소를 더 포함할 수 있는 것을 의미한다. 또한, 명세서에 기재된 "…부", "…기", "모듈" 등의 용어는 적어도 하나의 기능이나 동작을 처리하는 단위를 의미하며, 이는 하드웨어나 소프트웨어 또는 하드웨어 및 소프트웨어의 결합으로 구현될 수 있다. 장치는 하나 이상의 프로세서, 프로세서에 의하여 수행되는 컴퓨터 프로그램을 로드하는 메모리, 컴퓨터 프로그램 및 각종 데이터를 저장하는 저장 장치, 통신 인터페이스를 포함하는 컴퓨팅 장치일 수 있다. 이외에도, 장치는 다양한 구성 요소가 더 포함될 수 있다. 프로세서는 장치의 동작을 제어하고, 컴퓨터 프로그램에 포함된 명령어들을 처리하는 다양한 형태의 프로세서일 수 있고, 예를 들면, CPU(Central Processing Unit), MPU(Micro Processor Unit), MCU(Micro Controller Unit), GPU(Graphic Processing Unit) 또는 본 개시의 기술 분야에 잘 알려진 임의 형태의 프로세서 중 적어도 하나를 포함하여 구성될 수 있다. 메모리는 각종 데이터, 명령 및/또는 정보를 저장한다. 메모리는 본 개시의 동작을 실행하도록 기술된 명령어들이 프로세서에 의해 처리되도록 해당 컴퓨터 프로그램을 저장 장치로부터 로드할 수 있다. 메모리는 예를 들면, ROM(read only memory), RAM(random access memory) 등 일 수 있다. 저장 장치는 컴퓨터 프로그램, 각종 데이터를 비임시적으로 저장할 수 있다. 저장 장치는 ROM(Read Only Memory), EPROM(Erasable Programmable ROM), EEPROM(Electrically Erasable Programmable ROM), 플래시 메모리 등과 같은 비휘발성 메모리, 하드 디스크, 착탈형 디스크, 또는 본 개시가 속하는 기술 분야에서 잘 알려진 임의의 형태의 컴퓨터로 읽을 수 있는 기록 매체를 포함하여 구성될 수 있다. 통신 인터페이스는 유/무선 통신을 지원하는 유/무선 통신 모듈일 수 있다. 컴퓨터 프로그램은, 프로세서에 의해 실행되는 명령어들(instructions)을 포함하고, 비일시적-컴퓨터 판독가능 저장매체(non-transitory computer readable storage medium)에 저장되며, 명령어들은 프로세서가 본 개시의 동작을 실행하도록 만든다. 도 1은 한 실시예에 따른 장소명 유사도 판단 장치의 구성도이고, 도 2는 한 실시예에 따른 훈련 데이터를 위한 장소명쌍 랜덤 추출 방법을 설명하는 도면이다. 도 1을 참고하면, 적어도 하나의 프로세서에 의해 동작하는 장소명 유사도 판단 장치(간단히, 장치라고 한다)(10)는 장소명쌍의 문자열 특징 벡터를 기초로 장소명 유사도를 판단한다. 이를 위해, 장치(10)는 형태소 사전 구축기(100), 형태소 사전을 기초로 장소명쌍의 문자열 특징 벡터를 생성하는 특징 추출기(200), 그리고 장소명쌍의 문자열 특징 벡터로부터 장소명 유사도를 출력하도록 훈련된 유사도 판단 모델(300)을 포함할 수 있다. 장치(10)는 훈련 데이터를 기초로 유사도 판단 모델(300)을 훈련시키는 훈련기(400)를 더 포함할 수 있다. 장치(10)는 본 개시의 동작이 기술된 컴퓨터 프로그램을 실행할 수 있는 컴퓨팅 장치이다. 설명을 위해, 형태소 사전 구축기(100), 특징 추출기(200), 유사도 판단 모델(300), 훈련기(400)로 명명하여 부르나, 적어도 하나의 프로세서에 의해 실행되는 소프트웨어 모듈들일 수 있다. 설명을 위해, 형태소 사전 구축기(100), 특징 추출기(200), 유사도 판단 모델(300), 훈련기(400)가 장치(10)에 포함된다고 설명하나, 형태소 사전 구축기(100), 특징 추출기(200), 유사도 판단 모델(300), 그리고 훈련기(400) 중 적어도 일부는 장치(10)와 연동하는 별도의 컴퓨팅 장치에 분산될 수 있다. 문자열에는 의미 정보가 내포되어 있지 않으므로, 컴퓨팅 장치가 레번슈타인 점수와 같이 문자열을 비교하여 유사도를 판단하는 경우, 동일한 장소인데 문자열이 다른 경우 동일한 장소를 가리키는 장소명으로 판단하지 못하거나, 다른 장소인데 문자열이 비슷해서 동일 장소명으로 판단하게 될 수 있다. 반면, 사람은 학습한 지식을 통해 장소명의 의미를 이해하기 때문에, 예를 들면, 서울부동산과 서울공인중개사, 부성해물아구와 부성식당, 반디모텔과 호텔반디와 같이 레번슈타인 점수가 낮은 장소명이라도 동일 장소를 가리키는 장소명이라고 판단할 수 있다. 또한 사람은 두리부동산과 우리부동산, 호수식당과 호남식당과 같이 레번슈타인 점수가 높은 장소명이라도 장소명 식별에 중요한 영향을 주는 형태소와 그렇지 않은 형태소를 구분할 수 있어서, 다른 장소를 가리키는 장소명이라고 판단할 수 있다. 이처럼 컴퓨팅 장치가 문자열만으로 장소명 유사도를 판단하기 어려운 문제를 해결하기 위해, 장치(10)는 장소명쌍의 문자열에 포함된 형태소가 가지는 의미를 복수의 특징들로 구성된 문자열 특징 벡터로 표현함으로써, 장소명쌍의 문자열 특징 벡터를 기초로 장소명 유사도를 판단할 수 있다. 이러한 문자열 특징 벡터를 생성하기 위해, 형태소가 장소명에 출현하는 빈도, 형태소에 매핑된 카테고리, 형태소에 매핑된 지역명이 사용될 수 있다. 형태소 사전 구축기(100)는 대량의 장소명들이 포함된 장소 데이터로부터, 문자열 특징 벡터를 생성하는데 필요한 형태소별 속성을 사전으로 구축한다. 형태소 사전은 예를 들면, 출현 빈도 사전(110), 카테고리 사전(130), 그리고 지역명 사전(150)을 포함할 수 있다. 사전으로 구축되는 형태소 정보를 구분하기 위해, 출현 빈도 사전(110), 카테고리 사전(130), 그리고 지역명 사전(150)으로 구분하여 설명하나, 사전들이 반드시 구분될 필요는 없다. 형태소 사전 구축기(100)는 장소명이 포함된 대량의 장소 데이터를 수집한다. 형태소 사전 구축기(100)는 수집한 장소명들을 형태소 단위로 분리한다. 형태소 사전 구축기(100)는 각 형태소가 장소명에 출현하는 빈도를 누적해서, 출현 빈도 사전(110)을 구축할 수 있다. 예를 들면, '부성식당', '호수식당', '호남식당'의 장소명 각각이 '부성', '호수', '호남', '식당'의 형태소로 분리되고, 이 중 '식당'의 출현 빈도는 3으로 누적될 수 있다. 형태소 사전 구축기(100)는 표 1과 같이 형태소별 출현 빈도를 누적한 후, 출현 빈도가 미리 설정된 기준 이상인 형태소들을 일반 형태소로 분류하고, 출현 빈도가 미리 설정된 기준 미만인 형태소들을 고유 형태소로 분류할 수 있다. 형태소의 고유성은 '일반' 또는 '고유'일 수 있으나, 출현 빈도에 따라 세분화될 수 있다. 이때, 형태소 사전 구축기(100)는 형태소별 출현 빈도를 기초로 해당 형태소가 일반 형태소인지 고유 형태소인지를 매핑해서 출현 빈도 사전(110)을 구축할 수 있다. 또는, 형태소 사전 구축기(100)는 출현 빈도가 미리 설정된 기준 이상인 일반 형태소만으로 출현 빈도 사전(110)을 구축하고, 고유 형태소는 출현 빈도 사전(110)에 미등록할 수 있다. 형태소출현 빈도고유성식당88,756일반대리점14,381일반라벤더156고유만덕이네10고