KR101828995B1

KR101828995B1 - Method and Apparatus for clustering keywords

Info

Publication number: KR101828995B1
Application number: KR1020170057280A
Authority: KR
Inventors: 오흥선; 이석형; 설재욱; 김진영; 정유철; 김광영; 윤정선
Original assignee: 한국과학기술정보연구원
Priority date: 2017-05-08
Filing date: 2017-05-08
Publication date: 2018-02-14
Anticipated expiration: 2037-05-08

Abstract

키워드 클러스터링 방법이 제공된다. 본 발명의 일 실시예에 따른 키워드 클러스터링 방법은, 키워드 클러스터링 장치에 의해 수행되는 복수의 키워드상에 대한 키워드 클러스터링 방법에 있어서, 상기 복수의 키워드를 이용하여 복수의 클러스터가 포함된 초기 클러스터셋을 구성하는 단계, 상기 초기 클러스터셋에서, 단일 키워드에서 추출된 특징에 기반한 특징 벡터(feature vector) 간 유사도가 임계 값 이상인 클러스터를 병합하는 과정을 반복하여, 중간 클러스터셋을 구성하는 단계 및 상기 중간 클러스터셋에서, 동일 문서에 포함된 복수의 키워드에서 추출된 특징에 기반한 특징 벡터 간 유사도가 임계 값 이상인 클러스터를 병합하는 과정을 반복하여, 최종 클러스터셋을 구성하는 단계를 포함할 수 있다.A keyword clustering method is provided. A method for clustering keywords according to an embodiment of the present invention is a method for clustering keywords on a plurality of keywords performed by a keyword clustering apparatus, the method comprising: constructing an initial cluster set including a plurality of clusters , Constructing an intermediate cluster set by repeating a process of merging clusters having a similarity degree between feature vectors based on features extracted from a single keyword in the initial cluster set equal to or greater than a threshold value, And repeating the process of merging the clusters having similarities between the feature vectors based on the features extracted from the plurality of keywords included in the same document to a threshold value or more to construct a final cluster set.

Description

BACKGROUND OF THE INVENTION 1. Field of the Invention The present invention relates to a keyword clustering method,

본 발명은 키워드 클러스터링 방법 및 장치에 관한 것이다. 보다 자세하게는, 각종 디지털 문서(digital document)에 포함된 대량의 키워드로부터 정확도 높은 클러스터를 고속으로 구축하는 키워드 클러스터링 방법 및 장치에 관한 것이다.The present invention relates to a keyword clustering method and apparatus. More particularly, the present invention relates to a keyword clustering method and apparatus for constructing high-accuracy clusters at high speed from a large number of keywords contained in various digital documents.

대부분의 디지털 문서(e.g. 논문, 특허문헌, 연구보고서 등)에는 문서의 저자가 직접 작성한 키워드가 포함되어 있다. 해당 키워드는 문서의 주제를 함축적으로 나타내는 것이기 때문에, 동일한 키워드를 가지고 있는 문서들은 동일한 주제를 포함하고 있을 가능성이 매우 높다. 따라서, 디지털 문서에 포함되어 있는 키워드를 이용하면 문서의 모든 내용을 분석하지 않더라도 문서 간의 연관성을 쉽고 정확하게 분석할 수 있다.Most digital documents (eg, papers, patent literature, research reports, etc.) contain keywords written by the author of the document. Since the keyword represents the subject of the document implicitly, it is very likely that the documents with the same keyword contain the same subject. Therefore, by using the keywords included in the digital document, it is possible to easily and accurately analyze the correlation between the documents without analyzing all the contents of the document.

문서에 대한 연관성 검색, 정보 요약, 정보 시각화 등의 다양한 기능을 제공하기 위한 기반 기술로 키워드 클러스터링 기술이 주로 활용된다. 예를 들어, 문서에 포함된 키워드를 대상으로 키워드 클러스터가 구축되면, 동일 클러스터 내에 포함된 키워드를 공유하는 문서 간에 연관성이 있다는 추론을 할 수 있다.Keyword clustering technology is mainly used as an underlying technology to provide various functions such as relevance search for documents, information summaries, and information visualization. For example, when a keyword cluster is constructed for a keyword included in a document, it can be inferred that there is a correlation between documents sharing keywords included in the same cluster.

그러나, 대량의 키워드로부터 정확도 높은 클러스터를 고속으로 구축하는 것은 쉽지 않은 문제이며, 구체적으로 다음과 같은 문제를 해결하여야 한다.However, it is not easy to construct a high-accuracy cluster from a large number of keywords at high speed, and specifically, the following problems must be solved.

첫 번째는, 이음동의어와 동음이의어로 인해 야기되는 클러스터의 정확도 저하 문제이다. 동음이의어는 실제로 다른 의미를 갖고 있으나, 키워드 문자열이 동일하기 때문에 동일한 클러스터에 소속되어 클러스터의 정확도를 저하시키며, 이음동의어는 실제로 동일한 의미를 갖고 있으나, 문자열이 상이하기 때문에 서로 다른 클러스터에 소속되어 클러스터의 정확도를 저하시키는 문제가 있다.The first is the problem of cluster accuracy degradation caused by synonyms and homonyms. Although the homonym has a different meaning, the keyword string belongs to the same cluster and degrades the accuracy of the cluster because the keyword string is the same. The synonym synonym actually has the same meaning, but because the string is different, There is a problem in that the accuracy of the display device is deteriorated.

두 번째는, 띄어쓰기 오류와 오탈자로 인해 야기되는 클러스터의 정확도 저하 문제이다. 디지털 문서에서 포함된 대부분의 키워드는 해당 디지털 문서의 저자에 의해 생성되기 때문에, 키워드 작성 시에 저자의 잘못된 입력으로 인해서 각종 띄어쓰기 오류, 오탈자 등이 존재할 수 있다. 이로 인해, 동일한 키워드가 서로 다른 클러스터에 소속되는 오류가 발생할 수 있다.The second is the problem of cluster accuracy degradation caused by spacing errors and mislatches. Since most of the keywords contained in the digital document are generated by the author of the digital document, there may be various spacing errors and misreporting due to the author's wrong input when creating the keyword. This may cause an error that the same keyword belongs to different clusters.

세 번째는, 언어의 다양성 문제이다. 논문과 연구 보고서와 같은 디지털 문서에는 대부분 한글 키워드와 그에 대응되는 영어 키워드가 존재한다. 따라서, 서로 다른 언어로 구성된 키워드쌍 리스트가 주어진 경우에도 키워드 클러스터가 정확하게 구축될 필요가 있다.The third is language diversity. Most digital documents such as papers and research reports have Hangul keywords and corresponding English keywords. Therefore, even when a list of keyword pairs configured in different languages is given, the keyword cluster needs to be correctly constructed.

네 번째는, 클러스터링 성능에 관한 문제이다. 현재, 기 축적된 디지털 문서는 매우 방대하기 때문에, 대량의 키워드를 효율적으로 클러스터링하는 방법이 필수적으로 요구된다. 성능 문제를 해결하기 위해 반복적인 클러스터 합병을 통해 새로운 클러스터를 구축하는 상향식 계층적 클러스터링 알고리즘(bottom-up agglomerative hierarchical clustering algorithm)이 제안된 바 있다. 그러나, 해당 알고리즘을 이용하더라도 클러스터 병합 때마다 모든 클러스터 간의 유사도를 계산해야 하기 때문에 여전히 키워드 클러스터링에 관한 성능 문제는 해결되지 않고 있다.The fourth is a problem with clustering performance. At present, since accumulated digital documents are very large, a method of effectively clustering a large number of keywords is indispensable. To solve the performance problem, a bottom-up agglomerative hierarchical clustering algorithm has been proposed to construct a new cluster through iterative cluster merging. However, even if the algorithm is used, the performance problem of keyword clustering is still not solved because the similarity between all the clusters must be calculated every time the clusters are merged.

따라서, 상술한 문제점을 해결하기 위한 키워드 클러스터링 방법이 요구된다.Therefore, a keyword clustering method for solving the above problems is required.

한국등록특허 105641호 (2010.09.02 공개)Korean Patent No. 105641 (published on September 2, 2010)

본 발명이 해결하고자 하는 기술적 과제는, 이음동의어 및 동음이의어가 포함된 복수의 키워드에 대하여 정확도 높은 클러스터를 구축하는 키워드 클러스터링 방법 및 장치를 제공하는 것이다.SUMMARY OF THE INVENTION It is an object of the present invention to provide a keyword clustering method and apparatus for constructing a cluster with high accuracy for a plurality of keywords including a synonym and homonyms.

본 발명이 해결하고자 하는 다른 기술적 과제는, 띄어쓰기 오류 및 오탈자가 포함된 복수의 키워드에 대하여 정확도 높은 클러스터를 구축하는 키워드 클러스터링 방법 및 장치를 제공하는 것이다.It is another object of the present invention to provide a keyword clustering method and apparatus for constructing a cluster with high accuracy for a plurality of keywords including a spacing error and a punctuation.

본 발명이 해결하고자 하는 또 다른 기술적 과제는, 서로 다른 언어로 구성된 키워드쌍의 리스트로부터 클러스터를 구축하는 키워드 클러스터링 방법 및 장치를 제공하는 것이다.It is another object of the present invention to provide a keyword clustering method and apparatus for constructing a cluster from a list of keyword pairs configured in different languages.

본 발명이 해결하고자 하는 또 다른 기술적 과제는, 대량의 키워드로부터 클러스터를 효율적으로 구축하는 키워드 클러스터링 방법 및 장치를 제공하는 것이다.It is another object of the present invention to provide a keyword clustering method and apparatus for efficiently constructing a cluster from a large number of keywords.

본 발명의 기술적 과제들은 이상에서 언급한 기술적 과제들로 제한되지 않으며, 언급되지 않은 또 다른 기술적 과제들은 아래의 기재로부터 본 발명의 기술분야에서의 통상의 기술자에게 명확하게 이해 될 수 있을 것이다.The technical objects of the present invention are not limited to the above-mentioned technical problems, and other technical subjects not mentioned can be clearly understood by those skilled in the art from the following description.

상기 기술적 과제를 해결하기 위한, 본 발명의 일 실시예에 따른 키워드 클러스터링 방법은, 키워드 클러스터링 장치에 의해 수행되는 복수의 키워드상에 대한 키워드 클러스터링 방법에 있어서, 상기 복수의 키워드를 이용하여 복수의 클러스터가 포함된 초기 클러스터셋을 구성하는 단계, 상기 클러스터셋에서, 단일 키워드에서 추출된 특징에 기반한 특징 벡터(feature vector) 간 유사도가 임계 값 이상인 클러스터를 병합하는 과정을 반복하여, 중간 클러스터셋을 구성하는 단계 및 상기 중간 클러스터셋에서, 동일 문서에 포함된 복수의 키워드에서 추출된 특징에 기반한 특징 벡터 간 유사도가 임계 값 이상인 클러스터를 병합하는 과정을 반복하여, 최종 클러스터셋을 구성하는 단계를 포함할 수 있다.According to an aspect of the present invention, there is provided a method for clustering keywords on a plurality of keywords performed by a keyword clustering apparatus, the method comprising: Constructing an initial cluster set including the set of intermediate clusters, repeating a process of merging clusters having similarities between feature vectors based on features extracted from a single keyword to a threshold value or more in the cluster set, And repeating the process of merging the clusters whose similarities between the feature vectors based on the features extracted from the plurality of keywords included in the same document are equal to or greater than the threshold value in the intermediate cluster set to construct the final cluster set .

일 실시예에서, 상기 초기 클러스터셋을 구성하는 단계는, 상기 복수의 키워드에 포함된 각각의 키워드를 하나의 클러스터로 생성하는 과정을 반복하여, 복수의 클러스터가 포함된 제1 클러스터셋을 구성하는 단계, 상기 제1 클러스터셋에서, 동일한 키워드를 공유하는 클러스터를 병합하는 과정을 반복하여, 상기 클러스터셋을 구성하는 단계를 포함할 수 있다.In one embodiment, the step of configuring the initial cluster set may include generating a first cluster set including a plurality of clusters by repeating the process of generating each of the keywords included in the plurality of keywords as one cluster And constructing the cluster set by repeating a process of merging clusters sharing the same keyword in the first cluster set.

일 실시예에서, 상기 복수의 키워드에 포함된 각각의 키워드는 제1 키워드 및 제2 키워드를 포함하는 키워드쌍이고, 상기 제2 키워드는 상기 제1 키워드와 다른 언어로 표현되고 의미가 대응되는 키워드이되, 상기 중간 클러스터셋을 구성하는 단계는, 상기 초기 클러스터셋에 포함된 각각의 클러스터에 대하여, 상기 제1 키워드를 기초로 제1 특징을 추출하고, 상기 제1 특징을 기초로 제1 특징 벡터를 생성하는 단계, 상기 초기 클러스터셋에 포함된 각각의 클러스터에 대하여, 상기 제2 키워드를 기초로 제2 특징을 추출하고, 상기 제2 특징을 기초로 제2 특징 벡터를 생성하는 단계 및 상기 초기 클러스터셋 중에서, 상기 제1 특징 벡터 간 유사도와 상기 제2 특징 벡터 간 유사도를 기초로 산출된 평균 유사도가 임계 값 이상인 클러스터를 병합하는 과정을 반복하여, 상기 중간 클러스터셋을 구성하는 단계를 포함할 수 있다.In one embodiment, each of the keywords included in the plurality of keywords is a keyword pair including a first keyword and a second keyword, and the second keyword is a keyword that is expressed in a language different from the first keyword, Wherein the step of constructing the intermediate cluster set includes the steps of: extracting a first characteristic on the basis of the first keyword for each cluster included in the initial cluster set; Extracting a second feature based on the second keyword for each cluster included in the initial cluster set and generating a second feature vector based on the second feature, The process of merging the clusters having the average similarity calculated based on the similarity degree between the first characteristic vectors and the second characteristic vectors in the cluster set equal to or greater than the threshold value, Clothing and may include the step of configuring the intermediate cluster set.

일 실시예에서, 상기 중간 클러스터셋을 구성하는 단계는, 상기 초기 클러스터셋에 포함된 각각의 클러스터에 대하여, 상기 각각의 클러스터에 포함된 키워드로부터 특징을 추출하는 단계, 상기 특징 별로, 각 특징이 포함된 클러스터를 가리키는 역 인덱스(inverted index)을 구축하는 단계, 상기 중간 클러스터셋에서, 아직 선정되지 않은 어느 하나의 클러스터를 병합 기준 클러스터로 선정하는 제1 단계, 상기 역 인덱스를 이용하여, 상기 병합 기준 클러스터의 특징을 공유하는 클러스터를 검색하고, 상기 검색된 클러스터 중에서 병합 후보 클러스터를 선정하는 제2 단계, 상기 병합 후보 클러스터 중에서, 상기 병합 기준 클러스터와 상기 병합 후보 클러스터 간의 제1 유사도가 제1 임계 값 이상인 클러스터를 병합 대상 클러스터로 선정하는 제3 단계, 상기 병합 기준 클러스터와 상기 병합 대상 클러스터를 병합하는 제4 단계 및 상기 제1 단계 내지 상기 제4 단계를 반복하여, 상기 중간 클러스터셋을 구성하는 단계를 포함할 수 있다.In one embodiment, the step of configuring the intermediate cluster set may include the steps of: extracting a feature from each keyword included in each cluster included in the initial cluster set; Constructing an inverted index pointing to an included cluster, selecting a cluster not yet selected in the intermediate cluster set as a merging reference cluster, and using the inverse index, A second step of searching for clusters that share characteristics of the reference cluster and selecting a merging candidate cluster from among the searched clusters, a second step of selecting, from among the merging candidate clusters, a first similarity degree between the merging reference cluster and the merging candidate cluster, A third step of selecting a cluster to be merged as a target cluster, Merging, based Repeat step and the first step to the second step 44 of merging the merged cluster and the cluster, it may comprise the step of configuring the intermediate cluster set.

키워드 클러스터링 장치에 의해 수행되는 계층적 클러스터링 기반의 키워드 클러스터링 방법에 있어서, 복수의 키워드를 이용하여, 복수의 클러스터가 포함된 제1 클러스터셋을 구성하는 단계, 상기 제1 클러스터셋에 포함된 각각의 클러스터에 대하여, 상기 각각의 클러스터에 포함된 키워드로부터 특징을 추출하는 단계, 상기 특징 별로, 각 특징이 포함된 클러스터를 가리키는 역 인덱스(inverted index)을 구축하는 단계, 상기 제1 클러스터셋에 포함된 클러스터 중에서, 아직 선정되지 않은 어느 하나의 클러스터를 병합 기준 클러스터로 선정하는 제1 단계, 상기 역 인덱스를 이용하여, 상기 병합 기준 클러스터의 특징을 공유하는 클러스터를 검색하고, 상기 검색된 클러스터 중에서 병합 후보 클러스터를 선정하는 제2 단계, 상기 병합 후보 클러스터 중에서, 상기 병합 기준 클러스터와 상기 병합 후보 클러스터 간의 제1 유사도가 임계 값 이상인 클러스터를 병합 대상 클러스터로 선정하는 제3 단계, 상기 병합 기준 클러스터와 상기 병합 대상 클러스터를 병합하는 제4 단계 및 상기 제1 단계 내지 상기 제4 단계를 반복하여, 제2 클러스터셋을 구성하는 단계를 포함할 수 있다.A hierarchical clustering-based keyword clustering method performed by a keyword clustering apparatus, the method comprising: constructing a first cluster set including a plurality of clusters using a plurality of keywords; The method comprising the steps of: extracting a characteristic from a keyword included in each of the clusters; constructing an inverted index indicating a cluster including the features according to the characteristic; A first step of selecting one of the clusters not yet selected from the clusters as a merging reference cluster, searching clusters sharing features of the merging reference clusters using the inverse index, A second step of selecting the merging candidate cluster, A third step of selecting a cluster having a first similarity degree between the merging reference cluster and the merging candidate cluster equal to or greater than a threshold value as a merging target cluster, a fourth step of merging the merging reference cluster and the merging target cluster, And the fourth step may be repeated to configure the second cluster set.

상술한 기술적 과제를 해결하기 위한 본 발명의 다른 실시예에 따른 키워드 클러스터링 장치는, 하나 이상의 프로세서, 네트워크 인터페이스, 상기 프로세서에 의하여 수행되는 컴퓨터 프로그램을 로드(Load)하는 메모리 및 복수의 키워드쌍 및 상기 컴퓨터 프로그램을 저장하는 스토리지를 포함하되, 상기 컴퓨터 프로그램은, 상기 복수의 키워드를 이용하여 복수의 클러스터가 포함된 초기 클러스터셋을 구성하는 오퍼레이션, 상기 클러스터셋에서, 단일 키워드에서 추출된 특징에 기반한 특징 벡터(feature vector) 간 유사도가 임계 값 이상인 클러스터를 병합하는 과정을 반복하여, 중간 클러스터셋을 구성하는 오퍼레이션 및 상기 중간 클러스터셋에서, 동일 문서에 포함된 복수의 키워드에서 추출된 특징에 기반한 특징 벡터 간 유사도가 임계 값 이상인 클러스터를 병합하는 과정을 반복하여, 최종 클러스터셋을 구성하는 오퍼레이션을 포함할 수 있다.According to another aspect of the present invention, there is provided a keyword clustering apparatus including at least one processor, a network interface, a memory for loading a computer program executed by the processor, And a storage for storing a computer program, the computer program comprising: an operation of configuring an initial cluster set including a plurality of clusters using the plurality of keywords; The method of claim 1, further comprising: repeating the process of merging clusters having a similarity degree between a vector (feature vector) and a feature vector to obtain a feature vector based on a feature extracted from a plurality of keywords included in the same document, If the liver similarity is greater than or equal to the threshold The process of merging the clusters may be repeated to include operations that constitute the final cluster set.

상술한 기술적 과제를 해결하기 위한 본 발명의 또 다른 실시예에 따른 키워드 클러스터링 컴퓨터 프로그램은, 컴퓨팅 장치와 결합되어, 상기 복수의 키워드를 이용하여 복수의 클러스터가 포함된 초기 클러스터셋을 구성하는 단계, 상기 클러스터셋에서, 단일 키워드에서 추출된 특징에 기반한 특징 벡터(feature vector) 간 유사도가 임계 값 이상인 클러스터를 병합하는 과정을 반복하여, 중간 클러스터셋을 구성하는 단계 및 상기 중간 클러스터셋에서, 동일 문서에 포함된 복수의 키워드에서 추출된 특징에 기반한 특징 벡터 간 유사도가 임계 값 이상인 클러스터를 병합하는 과정을 반복하여, 최종 클러스터셋을 구성하는 단계를 실행시키기 위하여 기록 매체에 저장될 수 있다.According to another aspect of the present invention, there is provided a computer program for a keyword clustering method, comprising: configuring an initial cluster set including a plurality of clusters using a plurality of keywords, In the cluster set, repeating a process of merging clusters having a similarity degree between feature vectors based on features extracted from a single keyword to a threshold value or more to construct an intermediate cluster set, and in the intermediate cluster set, May be stored in the recording medium to repeat the process of merging the clusters having similarities between feature vectors based on the features extracted from the plurality of keywords included in the plurality of keywords, which are equal to or greater than the threshold value, to construct the final cluster set.

상술한 본 발명에 따르면, 동일 문서에 포함된 복수의 키워드에서 추출된 특징에 기초하여 클러스터 병합이 수행된다. 즉, 동일 문서에 포함된 복수의 키워드로부터 문맥이 반영된 특징이 추출되고, 상기 특징에 기초하여 클러스터 병합이 수행될 수 있다. 이에 따라, 이음동의어 및 동음이의어가 존재하는 경우라도 정확도 높은 클러스터가 구축되는 효과가 있다.According to the present invention described above, cluster merging is performed based on features extracted from a plurality of keywords included in the same document. That is, a feature reflecting a context is extracted from a plurality of keywords included in the same document, and cluster merging can be performed based on the feature. Accordingly, even when there is a synonym and homonym, there is an effect that a highly accurate cluster is constructed.

상술한 본 발명에 따르면, 전처리 과정을 통해 키워드에 포함된 부호문자(e.g. 공백 문자, 특수 문자, 구두점 등)가 제거된다. 또한, 키워드에서 q-gram을 이용하여 음절 단위의 특징이 추출되거나 자소 단위로 특징이 추출되고, 상기 특징에 기초하여 클러스터 병합이 수행된다. 이에 따라, 키워드 내에 띄어쓰기 및 오탈자가 존재하는 경우에도 정확도 높은 클러스터가 구축되는 효과가 있다.According to the present invention, a sign character (e.g., a space character, a special character, a punctuation mark, etc.) included in a keyword is removed through a preprocessing process. In addition, features of a syllable unit are extracted using a q-gram in a keyword or features are extracted on a per-character basis, and cluster merging is performed based on the feature. Accordingly, even when there is a space and a punctuation in the keyword, an accurate cluster can be constructed.

상술한 본 발명에 따르면, 서로 다른 언어로 표현된 키워드쌍을 기초로 클러스터가 구축된다. 또한, 제1 키워드 및 제2 키워드 각각에 대한 특징 벡터가 산출되고, 평균적인 특징 벡터의 유사도를 고려하여 클러스터의 병합이 수행된다. 이에 따라, 복수의 언어로 구성된 키워드쌍이 주어진 경우에도 정확도 높은 클러스터가 구축되는 효과가 있다.According to the present invention described above, clusters are constructed based on keyword pairs expressed in different languages. In addition, the feature vectors for the first and second keywords are calculated, and the merging of the clusters is performed in consideration of the similarity of the average feature vectors. Thereby, even when a keyword pair composed of a plurality of languages is given, there is an effect that a highly accurate cluster is constructed.

상술한 본 발명에 따르면, 클러스터의 초기 병합 단계에 키워드 문자열의 완전 매칭(exact matching)을 통해 별도의 유사도 계산 없이 클러스터 병합이 수행된다. 또한, 역 인덱스(inverse index)를 빠르게 병합 후보 클러스터가 검색되고, 검색된 병합 후보 클러스터에서만 클러스터 유사도 계산이 수행된다. 이에 따라, 대량의 키워드가 주어진 경우에도 고속으로 클러스터가 구축되는 효과가 있다. 또한, 키워드 클러스터링에 소요되는 시간 비용 및 컴퓨팅 비용이 모두 절감되는 효과가 있다.According to the present invention, cluster merging is performed without performing another similarity calculation through exact matching of a keyword string to an initial merging step of a cluster. In addition, a candidate cluster in which an inverse index is quickly merged is searched, and the cluster similarity calculation is performed only in the searched merging candidate cluster. Thereby, even when a large number of keywords are given, there is an effect that a cluster is constructed at a high speed. In addition, the time cost and the computing cost required for keyword clustering are all reduced.

상술한 본 발명에 따라 구축된 키워드 클러스터는 정보 검색, 자연어 처리, 정보 시각화, 주제 분석 등 다양한 분야에서 활용될 수 있다는 효과가 있다.The keyword cluster constructed according to the present invention can be utilized in various fields such as information retrieval, natural language processing, information visualization, and topic analysis.

본 발명의 효과들은 이상에서 언급한 효과들로 제한되지 않으며, 언급되지 않은 또 다른 효과들은 아래의 기재로부터 통상의 기술자에게 명확하게 이해될 수 있을 것이다.The effects of the present invention are not limited to the effects mentioned above, and other effects not mentioned can be clearly understood to those of ordinary skill in the art from the following description.

도 1은 본 발명이 적용될 수 있는 예시적인 시스템의 구성도이다.
도 2a 내지 도 2c는 본 발명의 일 실시예에 따른 키워드 클러스터링 장치의 기능 블록도이다.
도 3a 및 도 3c는 키워드 클러스터링 장치의 입력 및 출력 데이터의 예시도이다.
도 4는 본 발명의 다른 실시예에 따른 키워드 클러스터링 장치의 하드웨어 구성도이다.
도 5 내지 도 7은 본 발명의 또 다른 실시예에 따른 키워드 클러스터링 방법을 설명하기 위한 도면이다.
도 8은 도 5에 도시된 키워드 클러스터링 방법을 구성하는 세부 단계(S200)를 설명하기 위한 상세 순서도이다.
도 9a 내지 도 9c는 도 5에 도시된 키워드 클러스터링 방법을 구성하는 세부 단계(S300)를 설명하기 위한 상세 순서도이다.
도 10은 본 발명의 몇몇 실시예에서 참조될 수 있는 역 인덱싱 기법을 설명하기 위한 도면이다.
도 11은 본 발명의 몇몇 실시예에서 참조될 수 있는 특징 벡터의 예시도이다.
도 12는 도 5에 도시된 키워드 클러스터링 방법을 구성하는 세부 단계(S500)를 설명하기 위한 상세 순서도이다.
도 13은 본 발명의 몇몇 실시예에 따라 구축된 키워드 클러스터가 활용되는 예를 설명하기 위한 도면이다.1 is a block diagram of an exemplary system to which the present invention may be applied.
2A to 2C are functional block diagrams of a keyword clustering apparatus according to an embodiment of the present invention.
Figures 3A and 3C are illustrations of input and output data of a keyword clustering device.
4 is a hardware block diagram of a keyword clustering apparatus according to another embodiment of the present invention.
5 to 7 are views for explaining a keyword clustering method according to another embodiment of the present invention.
FIG. 8 is a detailed flowchart for explaining detailed steps (S200) constituting the keyword clustering method shown in FIG.
FIGS. 9A to 9C are detailed flowcharts for explaining detailed steps S300 constituting the keyword clustering method shown in FIG.
10 is a diagram illustrating a reverse indexing technique that may be referred to in some embodiments of the present invention.
Figure 11 is an illustration of a feature vector that may be referenced in some embodiments of the present invention.
FIG. 12 is a detailed flowchart for explaining a detailed step S500 of constructing the keyword clustering method shown in FIG.
13 is a diagram for explaining an example in which a keyword cluster constructed according to some embodiments of the present invention is utilized.

이하, 첨부된 도면을 참조하여 본 발명의 바람직한 실시예들을 상세히 설명한다. 본 발명의 이점 및 특징, 그리고 그것들을 달성하는 방법은 첨부되는 도면과 함께 상세하게 후술되어 있는 실시예들을 참조하면 명확해질 것이다. 그러나 본 발명은 이하에서 개시되는 실시예들에 한정되는 것이 아니라 서로 다른 다양한 형태로 구현될 수 있으며, 단지 본 실시예들은 본 발명의 개시가 완전하도록 하고, 본 발명이 속하는 기술분야에서 통상의 지식을 가진 자에게 발명의 범주를 완전하게 알려주기 위해 제공되는 것이며, 본 발명은 청구항의 범주에 의해 정의될 뿐이다. 명세서 전체에 걸쳐 동일 참조 부호는 동일 구성 요소를 지칭한다.Hereinafter, preferred embodiments of the present invention will be described in detail with reference to the accompanying drawings. BRIEF DESCRIPTION OF THE DRAWINGS The advantages and features of the present invention, and the manner of achieving them, will be apparent from and elucidated with reference to the embodiments described hereinafter in conjunction with the accompanying drawings. The present invention may, however, be embodied in many different forms and should not be construed as limited to the embodiments set forth herein. Rather, these embodiments are provided so that this disclosure will be thorough and complete, and will fully convey the scope of the invention to those skilled in the art. To fully disclose the scope of the invention to those skilled in the art, and the invention is only defined by the scope of the claims. Like reference numerals refer to like elements throughout the specification.

다른 정의가 없다면, 본 명세서에서 사용되는 모든 용어(기술 및 과학적 용어를 포함)는 본 발명이 속하는 기술분야에서 통상의 지식을 가진 자에게 공통적으로 이해될 수 있는 의미로 사용될 수 있다. 또 일반적으로 사용되는 사전에 정의되어 있는 용어들은 명백하게 특별히 정의되어 있지 않는 한 이상적으로 또는 과도하게 해석되지 않는다. 본 명세서에서 사용된 용어는 실시예들을 설명하기 위한 것이며 본 발명을 제한하고자 하는 것은 아니다. 본 명세서에서, 단수형은 문구에서 특별히 언급하지 않는 한 복수형도 포함한다.Unless defined otherwise, all terms (including technical and scientific terms) used herein may be used in a sense commonly understood by one of ordinary skill in the art to which this invention belongs. Also, commonly used predefined terms are not ideally or excessively interpreted unless explicitly defined otherwise. The terminology used herein is for the purpose of illustrating embodiments and is not intended to be limiting of the present invention. In the present specification, the singular form includes plural forms unless otherwise specified in the specification.

명세서에서 사용되는 "포함한다 (comprises)" 및/또는 "포함하는 (comprising)"은 언급된 구성 요소, 단계, 동작 및/또는 소자는 하나 이상의 다른 구성 요소, 단계, 동작 및/또는 소자의 존재 또는 추가를 배제하지 않는다.It is noted that the terms "comprises" and / or "comprising" used in the specification are intended to be inclusive in a manner similar to the components, steps, operations, and / Or additions.

이하, 도면들을 참조하여 본 발명의 몇몇 실시예들을 설명한다.Some embodiments of the present invention will now be described with reference to the drawings.

도 1은 본 발명이 적용될 수 있는 예시적인 시스템의 구성도이다.1 is a block diagram of an exemplary system to which the present invention may be applied.

도 1을 참조하면, 본 발명의 일 실시예에 따른 키워드 클러스터링 장치(100)는 검색 서버(200), 수집 서버(300) 등과 협력하여 검색 시스템을 구성할 수 있다. 또한, 상기 검색 시스템은 사용자 단말(400)의 검색 요청에 응답하여 다양한 검색 결과를 제공할 수 있다. 예를 들어, 상기 검색 시스템은 사용자 단말(400)로부터 특정 주제를 가리키는 검색 키워드의 수신에 응답하여, 상기 특정 주제와 관련된 다양한 디지털 문서를 검색 결과로 제공할 수 있다.Referring to FIG. 1, a keyword clustering apparatus 100 according to an exemplary embodiment of the present invention may configure a search system in cooperation with a search server 200, a collection server 300, and the like. In addition, the search system may provide various search results in response to a search request of the user terminal 400. For example, the search system may provide various digital documents related to the particular topic as search results, in response to receiving a search keyword from a user terminal 400 that indicates a particular topic.

상기 검색 시스템에서, 검색 서버(200)는 키워드 클러스터링 장치(100)가 제공하는 클러스터 기반으로 검색 기능을 제공하는 컴퓨팅 장치이다. 사용자 단말(400)로부터 검색 키워드와 함께 검색 요청을 수신하는 경우, 검색 서버(200)는 키워드 클러스터링 장치(100)가 제공한 클러스터셋을 이용하여 검색 결과를 제공할 수 있다. 이에 대한 간략한 예시는 도 13을 참조하도록 한다.In the search system, the search server 200 is a computing device that provides a search function based on a cluster provided by the keyword clustering apparatus 100. When receiving a search request together with a search keyword from the user terminal 400, the search server 200 may provide a search result using the cluster set provided by the keyword clustering apparatus 100. A brief example of this will be described with reference to FIG.

상기 검색 시스템에서, 수집 서버(300)는 키워드 클러스터링 장치(100)에 입력되는 각종 디지털 문서(digital document)를 수집하는 컴퓨팅 장치이다. 상기 디지털 문서는 예를 들어 논문, 특허문헌, 연구 보고서 등을 포함할 수 있다. 수집 서버(300)는 웹 크롤링(web crawling) 기술을 이용하여 수집 대상 웹 사이트에 게시된 디지털 문서를 자동으로 수집할 수 있다. 또한, 수집 서버(300)는 수집된 디지털 문서에서 자동으로 키워드를 추출할 수 있다. 예를 들어, 수집된 디지털 문서가 제공하는 한글 키워드 및 영문 키워드를 자동으로 추출할 수 있다. 키워드를 별도로 제공하지 않는 경우, 수집 서버(300)는 TF-IDF(Term Frequency-Inverse Document Frequency) 등 당해 기술 분야에서 널리 알려진 적어도 하나의 알고리즘을 이용하여 키워드를 자동으로 추출할 수도 있다.In the search system, the collection server 300 is a computing device that collects various digital documents input to the keyword clustering apparatus 100. The digital document may include, for example, a paper, a patent document, a research report, and the like. The collection server 300 can automatically collect digital documents posted on the collection target website using web crawling technology. In addition, the collection server 300 can automatically extract keywords from the collected digital documents. For example, the Korean and English keywords provided by the collected digital document can be automatically extracted. If the keyword is not separately provided, the collection server 300 may automatically extract the keyword using at least one algorithm widely known in the art such as a TF-IDF (Term Frequency-Inverse Document Frequency).

본 발명의 일 실시예에 따른 키워드 클러스터링 장치(100)는 복수의 키워드를 입력 받고, 키워드 클러스터를 구축하는 컴퓨팅 장치이다. 여기서, 상기 컴퓨팅 장치는 데스크톱(desktop), 랩탑(laptop) 등이 될 수 있으나, 이에 국한되는 것은 아니고, 연산 수단이 구비된 장치라면 어떠한 장치로 구현되더라도 무방하다. 단, 대량의 키워드로부터 고속으로 클러스터를 구축하기 위해서는 고성능의 서버로 구현되는 것이 바람직할 수 있다.The keyword clustering apparatus 100 according to an embodiment of the present invention is a computing apparatus that receives a plurality of keywords and constructs a keyword cluster. Here, the computing device may be a desktop, a laptop, or the like, but the present invention is not limited thereto, and any device having computing means may be used. However, in order to construct a cluster at a high speed from a large number of keywords, it may be desirable to be implemented as a high-performance server.

이하 본 발명의 몇몇 실시예들에서, 키워드 클러스터링 장치(100)에 입력되는 개별 키워드는 (제1 키워드, 제2 키워드)와 같이 복수의 키워드로 구성된 키워드쌍이라고 가정한다. 여기서, 상기 제1 키워드 및 상기 제2 키워드는 서로 다른 언어로 표현되고, 의미가 서로 대응되는 키워드이다. 키워드쌍에 대한 예는 도 3a 또는 도 6b를 참조하도록 한다. 참고로, 상기 제1 키워드 및 상기 제2 키워드는 하나의 어절 또는 복수의 어절이 포함된 어구가 될 수도 있다.Hereinafter, in some embodiments of the present invention, it is assumed that an individual keyword input to the keyword clustering apparatus 100 is a keyword pair composed of a plurality of keywords, such as a first keyword and a second keyword. Here, the first keyword and the second keyword are keywords that are expressed in different languages and correspond to each other in meaning. An example of a keyword pair will be described with reference to FIG. 3A or FIG. 6B. For reference, the first keyword and the second keyword may be phrases including one word or a plurality of phrases.

별도의 언급이 없는 한, 이해의 편의를 제공하기 위해 상기 제1 키워드는 한글 키워드이고, 상기 제2 키워드는 상기 제1 키워드에 대응되는 영어 키워드라고 가정하여 설명하도록 한다. 단, 당해 기술 분야의 통상의 기술자라면, 본 발명의 기술적 사상은 언어의 종류, 키워드쌍에 포함된 키워드의 개수가 달라지더라도 핵심적인 기술적 사상의 변경 없이 키워드 클러스터를 구축할 수 있음을 이해할 수 있을 것이다. 키워드 클러스터링 장치(100)가 키워드 클러스터를 구축하는 방법에 대한 자세한 설명은 도 5 내지 도 12를 참조하여 후술하도록 한다.Unless otherwise noted, the first keyword is a Hangul keyword and the second keyword is an English keyword corresponding to the first keyword, for convenience of understanding. However, it will be understood by those of ordinary skill in the art that the technical idea of the present invention is that keyword clusters can be constructed without changing key technical ideas even if the type of language or the number of keywords included in the keyword pair is changed There will be. A detailed description of how the keyword clustering apparatus 100 constructs the keyword cluster will be described below with reference to FIGS. 5 to 12. FIG.

도 1에 도시된 예시적인 시스템에서, 사용자 단말(400)과 검색 시스템은 네트워크를 통해 통신할 수 있다. 또한, 검색 시스템을 구성하는 키워드 클러스터링 장치(100), 검색 서버(200) 및 수집 서버(300) 또한 네트워크를 통해 통신할 수 있다. 여기서, 상기 네트워크는 근거리 통신망(Local Area Network; LAN), 광역 통신망(Wide Area Network; WAN), 이동 통신망(mobile radio communication network), Wibro(Wireless Broadband Internet) 등과 같은 모든 종류의 유/무선 네트워크로 구현될 수 있다.In the exemplary system shown in FIG. 1, the user terminal 400 and the search system may communicate over a network. In addition, the keyword clustering apparatus 100, the search server 200, and the collection server 300 constituting the search system can also communicate via the network. Here, the network may be any kind of wired / wireless network such as a local area network (LAN), a wide area network (WAN), a mobile radio communication network, a wibro Can be implemented.

참고로, 도 1에서 키워드 클러스터링 장치(100)와 검색 서버(200) 및 수집 서버(300)는 물리적으로 상호 독립된 장치로 도시되어 있다. 그러나, 다른 실시예에 따르면, 키워드 클러스터링 장치(100)와 검색 서버(200) 및 수집 서버(300)는 동일한 장치 내에 서로 다른 로직(logic)의 형태로 구현될 수도 있다. 또한, 실시예에 따라, 키워드 클러스터링 장치(100)는 수집 서버(300)가 제공하는 수집 기능 및 검색 서버(200)가 제공하는 검색 기능 중 적어도 하나의 기능을 포함하도록 구현될 수도 있다.For reference, in FIG. 1, the keyword clustering apparatus 100, the search server 200 and the collection server 300 are physically separated from each other. However, according to another embodiment, the keyword clustering apparatus 100, the search server 200, and the collection server 300 may be implemented in the form of different logic in the same apparatus. Further, according to the embodiment, the keyword clustering apparatus 100 may be implemented to include at least one of a collection function provided by the collection server 300 and a search function provided by the search server 200. [

지금까지 도 1을 참조하여 본 발명이 적용될 수 있는 예시적인 시스템의 구성에 대하여 설명하였다. 다음으로, 본 발명의 일 실시예에 따른 키워드 클러스터링 장치(100)의 구성 및 동작에 대하여 도 2a 내지 도 4를 참조하여 설명한다.The configuration of an exemplary system to which the present invention can be applied has been described with reference to FIG. Next, the configuration and operation of the keyword clustering apparatus 100 according to an embodiment of the present invention will be described with reference to FIG. 2A to FIG.

도 2a는 본 발명의 일 실시예에 따른 키워드 클러스터링 장치(100)의 기능 블록도이다.FIG. 2A is a functional block diagram of a keyword clustering apparatus 100 according to an embodiment of the present invention.

도 2a를 참조하면, 키워드 클러스터링 장치(100)는 키워드 리스트 및/또는 문서 리스트를 입력 받고, 자동으로 키워드 클러스터를 구축할 수 있다. 입력되는 키워드 리스트의 실례는 도 3a를 참조하고, 출력되는 키워드 클러스터의 실례는 도 3b를 참조하도록 한다.Referring to FIG. 2A, the keyword clustering apparatus 100 receives a keyword list and / or a document list, and can automatically construct a keyword cluster. An example of the input keyword list is shown in FIG. 3A, and an example of the output keyword cluster is shown in FIG. 3B.

상기와 같은 기능을 수행하기 위해, 키워드 클러스터링 장치(100)는 클러스터 생성부(110), 병합부(130) 및 대표 키워드 선정부(150)를 포함하도록 구성될 수 있다. 다만, 도 2a에는 본 발명의 실시예와 관련 있는 구성요소들만이 도시되어 있다. 따라서, 본 발명이 속한 기술분야의 통상의 기술자라면 도 2a에 도시된 구성요소들 외에 다른 범용적인 구성 요소들이 더 포함될 수 있음을 알 수 있다.The keyword clustering apparatus 100 may be configured to include the cluster generating unit 110, the merge unit 130, and the representative keyword selecting unit 150 in order to perform the functions as described above. However, only the components associated with the embodiment of the present invention are shown in Fig. Accordingly, those skilled in the art will appreciate that other general-purpose components other than the components shown in FIG. 2A may be further included.

각 구성 요소를 살펴보면, 클러스터 생성부(110)는 키워드 리스트로부터 복수의 클러스터를 포함하는 클러스터셋을 생성한다. 예를 들어, 클러스터 생성부(110)는 키워드 리스트에 포함된 각각의 키워드쌍을 하나의 클러스터로 생성하는 과정을 반복하여, 상기 클러스터셋을 구성할 수 있다.Referring to each component, the cluster generating unit 110 generates a cluster set including a plurality of clusters from the keyword list. For example, the cluster generating unit 110 may construct the cluster set by repeating the process of generating each keyword pair included in the keyword list into one cluster.

병합부(130)는 클러스터 생성부(110)에 의해 생성된 복수의 클러스터를 병합하여 최종 클러스터셋을 구성한다. 클러스터 병합의 효율성 및 클러스터링 결과의 정확성을 위해 클러스터 병합부(130)는 제1 클러스터 병합부(131), 제2 클러스터 병합부(133) 및 제3 클러스터 병합부(135)를 포함하도록 구성될 수 있다.The merging unit 130 merges the plurality of clusters generated by the cluster generating unit 110 to construct a final cluster set. The cluster merge unit 130 may be configured to include the first cluster merge unit 131, the second cluster merge unit 133, and the third cluster merge unit 135 for efficiency of cluster merge and accuracy of the clustering result have.

제1 클러스터 병합부(131)는 클러스터 생성부(110)에 의해 구성된 클러스터셋에서 동일한 키워드를 공유하는 클러스터에 대한 병합을 수행한다. 이를 통해, 이후 병합 단계에서 병합 대상이 되는 클러스터의 개수가 줄어들기 때문에, 보다 빠르게 클러스터 병합 과정이 진행될 수 있다. 상기와 같은 동작을 수행하기 위해, 제1 클러스터 병합부(131)는 전처리부(131a), 클러스터 조회부(131b) 및 클러스터 병합부(131c)를 포함하도록 구성될 수 있다.The first cluster merging unit 131 merges clusters sharing the same keyword in the cluster set constituted by the cluster generating unit 110. [ Accordingly, since the number of clusters to be merged is reduced in the merging step, the cluster merging process can be performed more quickly. In order to perform the above operation, the first cluster merging unit 131 may include a preprocessing unit 131a, a cluster inquiry unit 131b, and a cluster merging unit 131c.

전처리부(131a)는 각 클러스터에 포함된 키워드에 대한 전처리를 수행한다. 예를 들어, 전처리부(131a)는 각 키워드에서 부호 문자(e.g. 공백 문자, 특수 문자, 구두점 등)를 제거하고, 스테밍(stemming) 기술을 이용하여 어근을 추출한다. 이를 통해, 띄어쓰기 오류, 일부 오탈자가 존재하는 경우에도 키워드 매칭을 통해 동일 키워드를 공유하는 클러스터 간의 병합이 수행될 수 있다.The preprocessing unit 131a preprocesses keywords included in each cluster. For example, the preprocessing unit 131a removes a sign character (e.g., a space character, a special character, a punctuation mark) from each keyword, and extracts a root using a stemming technique. In this way, merging between clusters sharing the same keyword through keyword matching can be performed even in the case of a spacing error or some punctuation.

클러스터 조회부(131b)는 전처리된 키워드를 기초로 동일한 키워드를 공유하는 클러스터를 조회한다. 예를 들어, 클러스터 조회부(131b)는 어느 하나의 클러스터를 기준으로, 해당 클러스터의 키워드와 동일한 키워드를 공유하는 다른 클러스터를 조회할 수 있다. 클러스터에 포함된 키워드가 (한글 키워드, 영어 키워드)와 같이 키워드쌍으로 구성된 경우, 클러스터 조회부(131b)는 한글 및 영어 키워드가 모두 동일한 클러스터, 한글 또는 영어 키워드 중 어느 하나의 키워드가 동일한 클러스터를 조회할 수 있다.The cluster inquiry unit 131b queries a cluster sharing the same keyword based on the preprocessed keyword. For example, the cluster inquiry unit 131b can refer to any other cluster that shares the same keyword as the keyword of the corresponding cluster, based on any one cluster. When the keyword included in the cluster is composed of a pair of keywords such as (Korean keyword, English keyword), the cluster inquiry unit 131b determines that the cluster in which both the Korean and English keywords are the same, .

클러스터 병합부(131c)는 클러스터 조회부(131b)에 의해 조회된 클러스터를 병합한다. 제1 클러스터 병합부(131)가 클러스터 병합을 수행하는 동작에 관한 보다 상세한 설명은 도 8을 참조하도록 한다.The cluster merging unit 131c merges the clusters inquired by the cluster inquiring unit 131b. A more detailed description of the operation in which the first cluster merging unit 131 performs cluster merging will be described with reference to FIG.

제2 클러스터 병합부(133)는 단일 키워드에서 추출된 특징 기반의 특징 벡터의 유사도에 기초하여 클러스터 병합을 수행한다. 키워드쌍이 (한글 키워드 영어 키워드)로 구성된 경우, 제2 클러스터 병합부(133)는 한글 키워드에서 추출된 특징 기반의 특징 벡터의 유사도에 기초하여 제1 클러스터 병합을 수행하고, 영어 키워드에서 추출된 특징 기반의 특징 벡터의 유사도에 기초하여 제2 클러스터 병합을 수행할 수 있다.The second cluster merging unit 133 performs cluster merging based on the similarity of feature-based feature vectors extracted from a single keyword. The second cluster merging unit 133 performs the first cluster merging based on the similarity of the feature-based feature vectors extracted from the Hangul keywords, and extracts features extracted from the English keywords The second cluster merging can be performed based on the degree of similarity of the feature vectors based on the feature vectors.

이를 위해, 제2 클러스터 병합부(133)는 특징 추출부(133a), 특징 벡터 생성부(133b), 역 인덱스 생성부(133c), 후보 클러스터 선정부(133d) 및 클러스터 병합부(133e)를 포함하도록 구성될 수 있다.To this end, the second cluster merging unit 133 includes a feature extracting unit 133a, a feature vector generating unit 133b, an inverse index generating unit 133c, a candidate cluster selecting unit 133d, and a cluster merging unit 133e . &Lt; / RTI >

특징 추출부(133a)는 키워드로부터 특징(feature)을 추출한다. 예를 들어, 특징 추출부(133a)는 q-gram 방식으로 특징을 추출할 수 있다. 여기서, 상기 특징은 당해 기술 분야에서 자질 등의 용어와 혼용되어 사용될 수 있으나, 동일한 의미를 지칭하는 것임에 유의하도록 한다.The feature extracting unit 133a extracts a feature from the keyword. For example, the feature extracting unit 133a can extract the feature by the q-gram method. It should be noted that the above-mentioned characteristics may be used in combination with terms such as qualities and the like in the technical field, but have the same meaning.

특징 벡터 생성부(133b)는 특징 추출부(133a)에 의해 추출된 특징을 이용하여 특징 벡터를 생성한다. 예를 들어, 특징 벡터 생성부(133b)는 TF-IDF를 이용하여 각 특징 별로 가중치 값을 부여함으로써, 특징 벡터를 생성할 수 있다. 특징 벡터의 예는 도 11을 참조하도록 한다. 여기서, 상기 특징 벡터는 당해 기술 분야에서 자질 벡터, 센트로이드(centroid) 벡터, 중심 벡터 등의 용어와 혼용되어 사용될 수 있으나, 동일한 의미를 지칭하는 것임에 유의하도록 한다. 또한, TF-IDF는 이미 당해 기술 분야에서 널리 알려진 기술 인바 이에 대한 설명은 생략하도록 한다.The feature vector generator 133b generates a feature vector using the feature extracted by the feature extractor 133a. For example, the feature vector generator 133b may generate a feature vector by assigning a weight value to each feature using the TF-IDF. An example of the feature vector will be described with reference to Fig. Here, it should be noted that the feature vector may be used in combination with terms such as a feature vector, a centroid vector, a center vector, and the like, but has the same meaning in the art. Further, the TF-IDF is already well known in the art, and a description thereof will be omitted.

역 인덱스 생성부(133c)는 각 클러스터 별로 추출된 특징을 이용하여, 각 특징이 포함된 클러스터를 가리키는 역 인덱스를 생성한다. 이에 대한 사항은 도 10을 참조하여 후술하도록 한다.The inverse index generator 133c generates an inverse index indicating a cluster including the features using the features extracted for each cluster. This will be described later with reference to FIG.

후보 클러스터 선정부(133d)는 병합 기준 클러스터가 선정되면, 상기 역 인덱스를 이용하여 상기 병합 기준 클러스터와 제1 유사도 계산이 수행되는 제1 병합 후보 클러스터를 선정한다. 또한, 후보 클러스터 선정부(133d)는 상기 제1 후보 클러스터 중에서, 상기 제1 유사도가 높은 일부 클러스터를 제2 후보 클러스터로 선정한다. 이에 대한 자세한 설명은 도 9a 내지 도 9c를 참조하여 후술하도록 한다.When the merging reference cluster is selected, the candidate cluster selecting unit 133d selects the first merging candidate cluster in which the first similarity calculation is performed using the inverse index. Further, the candidate cluster selection unit 133d selects, among the first candidate clusters, a partial cluster having the first similarity degree as the second candidate cluster. A detailed description thereof will be described later with reference to Figs. 9A to 9C.

클러스터 병합부(133f)는 병합 기준 클러스터와 제2 후보 클러스터 사이의 제2 유사도를 산출하고, 상기 제2 유사도가 가장 높은 후보 클러스터를 병합 대상 클러스터로 결정하며, 상기 병합 기준 클러스터와 상기 병합 대상 클러스터를 병합한다. 이에 대한 자세한 설명은 도 9a 내지 도 9c를 참조하여 후술하도록 한다.The cluster merging unit 133f calculates a second similarity degree between the merging reference cluster and the second candidate cluster, determines the candidate cluster having the second highest degree of similarity as the merging target cluster, . A detailed description thereof will be described later with reference to Figs. 9A to 9C.

제2 클러스터 병합부(133)가 클러스터 병합을 수행하는 동작에 관한 자세한 설명은 도 9a 내지 도 11을 참조하도록 한다.A detailed description of the operation of the second cluster merging unit 133 to perform cluster merging will be made with reference to FIGS. 9A to 11.

제3 클러스터 병합부(135)는 키워드의 문맥을 고려하기 위해 동일 문서에 포함된 복수의 키워드로부터 특징을 추출한다. 예를 들어, 제3 클러스터 병합부(135)는 복수의 키워드로부터 어절 단위로 특징을 추출할 수 있다. 제3 클러스터 병합부(135)의 구성 및 동작은 특징 추출을 제외하고 제2 클러스터 병합부(133)와 동일한 바, 구성에 관해서는 도 2c를 참조하고, 동작에 관해서는 도 9a 내지 도 11을 참조하도록 한다.The third cluster merging unit 135 extracts features from a plurality of keywords included in the same document in order to consider the context of the keyword. For example, the third cluster merging unit 135 may extract features from a plurality of keywords in units of the word. The configuration and operation of the third cluster merging unit 135 are the same as those of the second cluster merging unit 133 except for the feature extraction. The configuration and operation of the third cluster merging unit 135 are the same as those of the second cluster merging unit 133, Please refer to.

대표 키워드 선정부(150)는 최종 클러스터셋에 포함된 클러스터 각각에 대하여, 대표 키워드를 선정하고, 상기 대표 키워드를 해당 클러스터의 레이블(label)로 설정한다. 대표 키워드 선정부(150)가 대표 키워드를 선정하는 동작에 관한 자세한 설명은 도 12를 참조하도록 한다.The representative keyword selection unit 150 selects a representative keyword for each cluster included in the final cluster set, and sets the representative keyword as a label of the corresponding cluster. The detailed description of the operation in which the representative keyword selection unit 150 selects the representative keyword is described with reference to FIG.

한편, 본 발명의 다른 실시예에 따르면, 키워드 클러스터링 장치(100)는 수집부(미도시) 및/또는 키워드 추출부(미도시)를 더 포함하여 구성될 수도 있다. 수집부(미도시)는 네트워크를 통해 각종 디지털 문서를 자동으로 수집한다. 예를 들어, 수집부(미도시)는 웹 크롤링을 이용하여 각종 디지털 문서를 수집할 수 있다.Meanwhile, according to another embodiment of the present invention, the keyword clustering apparatus 100 may further include a collecting unit (not shown) and / or a keyword extracting unit (not shown). A collection unit (not shown) automatically collects various digital documents through the network. For example, a collection unit (not shown) can collect various digital documents using web crawling.

키워드 추출부(미도시)는 수집부(미도시)에 의해 수집된 디지털 문서 또는 기 저장된 디지털 문서에서 자동으로 키워드를 추출한다. 키워드 추출부(미도시)는 디지털 문서에 저자에 의해 삽입된 키워드가 존재하는 경우, 해당 키워드를 추출하고, 상기 키워드가 존재하지 않는 경우, TF-IDF 등의 기법을 이용하여 키워드를 추출할 수 있다.A keyword extracting unit (not shown) automatically extracts a keyword from a digital document or a previously stored digital document collected by a collecting unit (not shown). When there is a keyword inserted by the author in the digital document, the keyword extracting unit (not shown) extracts the keyword and if the keyword does not exist, the keyword can be extracted using a technique such as TF-IDF have.

본 실시예에서, 키워드 클러스터링 장치(100)는 수집부(미도시) 및 키워드 추출부(미도시)를 이용하여 자동으로 디지털 문서를 수집하고, 키워드를 추출하며, 키워드 클러스터를 구축할 수 있다. In this embodiment, the keyword clustering apparatus 100 can automatically collect digital documents, extract keywords, and construct keyword clusters using a collecting unit (not shown) and a keyword extracting unit (not shown).

도 2a 내지 도 2c의 각 구성 요소는 소프트웨어(Software) 또는, FPGA(Field Programmable Gate Array)나 ASIC(Application-Specific Integrated Circuit)과 같은 하드웨어(Hardware)를 의미할 수 있다. 그렇지만, 상기 구성 요소들은 소프트웨어 또는 하드웨어에 한정되는 의미는 아니며, 어드레싱(Addressing)할 수 있는 저장 매체에 있도록 구성될 수도 있고, 하나 또는 그 이상의 프로세서들을 실행시키도록 구성될 수도 있다. 상기 구성 요소들 안에서 제공되는 기능은 더 세분화된 구성 요소에 의하여 구현될 수 있으며, 복수의 구성 요소들을 합하여 특정한 기능을 수행하는 하나의 구성 요소로 구현될 수도 있다.2A to 2C may refer to software or hardware such as an FPGA (Field Programmable Gate Array) or an ASIC (Application-Specific Integrated Circuit). However, the components are not limited to software or hardware, and may be configured to be addressable storage media, and configured to execute one or more processors. The functions provided in the components may be implemented by a more detailed component, or may be implemented by a single component that performs a specific function by combining a plurality of components.

도 4는 본 발명의 또 다른 실시예에 따른 키워드 클러스터링 장치(100)의 하드웨어 구성도이다.4 is a hardware block diagram of a keyword clustering apparatus 100 according to another embodiment of the present invention.

도 4을 참조하면, 키워드 클러스터링 장치(100)는 하나 이상의 프로세서(101), 버스(105), 네트워크 인터페이스(107), 프로세서(101)에 의하여 수행되는 컴퓨터 프로그램을 로드(load)하는 메모리(103)와, 키워드 클러스터링 소프트웨어(109a)를 저장하는 스토리지(109)를 포함할 수 있다. 다만, 도 4에는 본 발명의 실시예와 관련 있는 구성요소들만이 도시되어 있다. 따라서, 본 발명이 속한 기술분야의 통상의 기술자라면 도 4에 도시된 구성요소들 외에 다른 범용적인 구성 요소들이 더 포함될 수 있음을 알 수 있다.4, the keyword clustering apparatus 100 includes one or more processors 101, a bus 105, a network interface 107, a memory 103 for loading a computer program executed by the processor 101 And a storage 109 for storing the keyword clustering software 109a. 4, only the components related to the embodiment of the present invention are shown. Accordingly, those skilled in the art will recognize that other general-purpose components may be included in addition to those shown in FIG.

프로세서(101)는 키워드 클러스터링 장치(100)의 각 구성의 전반적인 동작을 제어한다. 프로세서(101)는 CPU(Central Processing Unit), MPU(Micro Processor Unit), MCU(Micro Controller Unit), GPU(Graphic Processing Unit) 또는 본 발명의 기술 분야에 잘 알려진 임의의 형태의 프로세서를 포함하여 구성될 수 있다. 또한, 프로세서(101)는 본 발명의 실시예들에 따른 방법을 실행하기 위한 적어도 하나의 애플리케이션 또는 프로그램에 대한 연산을 수행할 수 있다. 키워드 클러스터링 장치(100)는 하나 이상의 프로세서를 구비할 수 있다.The processor 101 controls the overall operation of each configuration of the keyword clustering apparatus 100. The processor 101 includes a central processing unit (CPU), a microprocessor unit (MPU), a microcontroller unit (MCU), a graphics processing unit (GPU), or any type of processor well known in the art . The processor 101 may also perform operations on at least one application or program to perform the method according to embodiments of the present invention. The keyword clustering apparatus 100 may include one or more processors.

메모리(103)는 각종 데이터, 명령 및/또는 정보를 저장한다. 메모리(103)는 본 발명의 실시예들에 따른 키워드 클러스터링 방법을 실행하기 위하여 스토리지(109)로부터 하나 이상의 프로그램(109a)을 로드할 수 있다. 도 6에서 메모리(103)의 예시로 RAM이 도시되었다.The memory 103 stores various data, commands and / or information. The memory 103 may load one or more programs 109a from the storage 109 to perform the keyword clustering method according to embodiments of the present invention. RAM is shown as an example of the memory 103 in Fig.

버스(105)는 키워드 클러스터링 장치(100)의 구성 요소 간 통신 기능을 제공한다. 버스(105)는 주소 버스(Address Bus), 데이터 버스(Data Bus) 및 제어 버스(Control Bus) 등 다양한 형태의 버스로 구현될 수 있다.The bus 105 provides the inter-component communication function of the keyword clustering apparatus 100. The bus 105 may be implemented as various types of buses such as an address bus, a data bus, and a control bus.

네트워크 인터페이스(107)는 키워드 클러스터링 장치(100)의 유무선 인터넷 통신을 지원한다. 또한, 네트워크 인터페이스(107)는 인터넷 통신 외의 다양한 통신 방식을 지원할 수도 있다. 이를 위해, 네트워크 인터페이스(107)는 본 발명의 기술 분야에 잘 알려진 통신 모듈을 포함하여 구성될 수 있다.The network interface 107 supports wired / wireless Internet communication of the keyword clustering apparatus 100. In addition, the network interface 107 may support various communication methods other than Internet communication. To this end, the network interface 107 may comprise a communication module well known in the art.

스토리지(109)는 키워드 클러스터링 소프트웨어의 입력 데이터인 키워드셋(109b), 하나 이상의 프로그램(109a) 및 클러스터링 소프트웨어의 출력 데이터인 클러스터셋(109c)을 비임시적으로 저장할 수 있다. 도 4에서 상기 하나 이상의 프로그램(109a)의 예시로 키워드 클러스터링 소프트웨어(109a)가 도시되었다.The storage 109 may non-provisionally store the keyword set 109b, which is input data of the keyword clustering software, one or more programs 109a, and the cluster set 109c, which is the output data of the clustering software. In FIG. 4, the keyword clustering software 109a is illustrated as an example of the one or more programs 109a.

스토리지(109)는 ROM(Read Only Memory), EPROM(Erasable Programmable ROM), EEPROM(Electrically Erasable Programmable ROM), 플래시 메모리 등과 같은 비휘발성 메모리, 하드 디스크, 착탈형 디스크, 또는 본 발명이 속하는 기술 분야에서 잘 알려진 임의의 형태의 컴퓨터로 읽을 수 있는 기록 매체를 포함하여 구성될 수 있다.The storage 109 may be a nonvolatile memory such as ROM (Read Only Memory), EPROM (Erasable Programmable ROM), EEPROM (Electrically Erasable Programmable ROM), flash memory, etc., hard disk, removable disk, And any form of computer-readable recording medium known in the art.

키워드 클러스터링 소프트웨어(109a)는 본 발명의 실시예에 따라 복수의 키워드쌍 데이터를 가리키는 키워드셋(109b)을 입력으로 키워드 클러스터링을 수행하고 적어도 하나의 키워드 클러스터를 가리키는 클러스터셋(109c)을 출력할 수 있다.The keyword clustering software 109a performs keyword clustering by inputting a set of keywords 109b indicating a plurality of keyword pair data and outputs a cluster set 109c indicating at least one keyword cluster according to an embodiment of the present invention have.

구체적으로, 키워드 클러스터링 소프트웨어(109a)는 메모리(103)에 로드되어, 하나 이상의 프로세서(101)에 의해, 상기 복수의 키워드를 이용하여 복수의 클러스터가 포함된 클러스터셋을 구성하는 오퍼레이션, 상기 클러스터셋에서, 단일 키워드에서 추출된 특징에 기반한 특징 벡터(feature vector) 간 유사도가 임계 값 이상인 클러스터를 병합하는 과정을 반복하여, 중간 클러스터셋을 구성하는 오퍼레이션 및 상기 중간 클러스터셋에서, 동일 문서에 포함된 복수의 키워드에서 추출된 특징에 기반한 특징 벡터 간 유사도가 임계 값 이상인 클러스터를 병합하는 과정을 반복하여, 최종 클러스터셋을 구성하는 오퍼레이션을 포함할 수 있다.More specifically, the keyword clustering software 109a is loaded into the memory 103 and used by one or more processors 101 to configure a cluster set including a plurality of clusters using the plurality of keywords, , A process of merging clusters having a similarity degree between feature vectors based on features extracted from a single keyword is equal to or greater than a threshold value is repeated so that operations in an intermediate cluster set and in the intermediate cluster set, It may include an operation of constructing the final cluster set by repeating the process of merging the clusters having similarities between feature vectors based on the features extracted from the plurality of keywords to a threshold value or more.

지금까지, 도 2a 내지 도 4를 참조하여 본 발명의 일 실시예에 따른 키워드 클러스터링 장치(100)의 구성 및 동작에 대하여 설명하였다. 다음으로, 도 5 내지 도 12를 참조하여 본 발명의 다른 실시예에 따른 키워드 클러스터링 방법에 대하여 상세하게 설명한다.Up to now, the configuration and operation of the keyword clustering apparatus 100 according to an embodiment of the present invention have been described with reference to FIGS. Next, a keyword clustering method according to another embodiment of the present invention will be described in detail with reference to FIG. 5 to FIG.

본 발명의 실시예에 따른 키워드 클러스터링 방법의 각 단계는, 컴퓨팅 장치에 의해 수행될 수 있다. 예를 들어, 상기 컴퓨팅 장치는 본 발명의 일 실시예에 따른 키워드 클러스터링 장치(100)일 수 있다. 단, 설명의 편의를 위해, 키워드 클러스터링 방법에 포함되는 각 동작의 수행 주체는 그 기재가 생략될 수 있다. 또한, 키워드 클러스터링 방법의 각 단계는 키워드 클러스터링 소프트웨어(109a)가 프로세서(101)에 의해 실행됨으로써, 키워드 클러스터링 장치(100)에서 수행되는 오퍼레이션일 수 있다.Each step of the keyword clustering method according to an embodiment of the present invention can be performed by a computing device. For example, the computing device may be a keyword clustering device 100 according to an embodiment of the present invention. However, for the sake of convenience of description, the subject of each operation included in the keyword clustering method may be omitted. In addition, each step of the keyword clustering method may be an operation performed in the keyword clustering apparatus 100 by the keyword clustering software 109a being executed by the processor 101. [

도 5는 키워드 클러스터링 방법의 순서도이다. 단, 이는 본 발명의 목적을 달성하기 위한 바람직한 실시예일뿐이며, 필요에 따라 일부 단계가 추가되거나 삭제될 수 있음은 물론이다.5 is a flowchart of a keyword clustering method. However, it should be understood that the present invention is not limited thereto and that some steps may be added or deleted as needed.

도 5를 참조하면, 키워드 클러스터링 장치(100)는 키워드 리스트 및 각 키워드가 포함된 문서 리스트를 입력 받는다(S110). 실시예에 따라, 상기 키워드 리스트 및 문서 리스트는 기 정의된 형식에 맞게 전처리가 수행된 데이터(e.g. 도 3a 참조)일 수 있다. 단, 본 발명의 다른 실시예에 따르면, 키워드 클러스터링 장치(100)는 웹 크롤링을 통해 자동으로 디지털 문서를 수집하고, 상기 디지털 문서에서 자동으로 키워드를 추출하며, 기 정의된 형식에 맞게 전처리를 수행하여 상기 키워드 리스트 및 문서 리스트를 생성할 수도 있다.Referring to FIG. 5, the keyword clustering apparatus 100 receives a keyword list and a document list including each keyword (S110). According to an embodiment, the keyword list and the document list may be pre-processed data (see FIG. 3A) according to a predefined format. However, according to another embodiment of the present invention, the keyword clustering apparatus 100 automatically collects a digital document through web crawling, automatically extracts keywords from the digital document, and performs preprocessing according to a predefined format And generate the keyword list and the document list.

본 발명의 실시예에 따르면, 상기 키워드 리스트에 포함된 각각의 키워드(kwd₁, kwd₂, …)는 도 6a에 도시된 바와 같이 (한글 키워드, 영어 키워드)로 구성될 수 있고, 키워드 식별자(id)가 부가될 수도 있다. 또한, 문서 리스트는 각 키워드가 포함된 문서의 집합으로 구성될 수 있다.According to the embodiment of the present invention, each keyword (kwd ₁ , kwd ₂ , ...) included in the keyword list may be composed of (Korean keyword, English keyword) as shown in FIG. 6A, id) may be added. In addition, the document list can be composed of a set of documents each containing a keyword.

본 발명의 몇몇 실시예들에서, 각 키워드쌍은 도 6b와 같이 한글 키워드와 영어 키워드로 구성된다고 가정한다. 단, 한글 키워드 및 영어 키워드 중 어느 하나의 키워드가 공백 문자로 입력되더라도 무방하다.In some embodiments of the present invention, it is assumed that each keyword pair is composed of a Hangul keyword and an English keyword as shown in FIG. 6B. However, any one of the Korean keyword and the English keyword may be input as a blank character.

다시 도 5를 참조하면, 키워드 클러스터링 장치(100)는 키워드 리스트에 포함된 복수의 키워드쌍을 이용하여 초기 클러스터셋을 구성하고(S200), 상기 초기 클러스터셋에 포함된 클러스터를 상향식으로 병합해가며 최종 클러스터셋을 구성한다. 예를 들어, 도 7을 참조하여 간략히 설명하면, 키워드 클러스터링 장치(100)는 초기 클러스터셋(501)에 포함된 적어도 일부의 클러스터를 병합하여 중간 클러스터셋(503)을 구성하고, 중간 클러스터셋(503)에 포함된 적어도 일부의 클러스터를 병합하여 최종 클러스터셋(505)를 구성하게 된다. 단, 본 발명의 실시예에 따르면, 초기 클러스터셋(501)도 클러스터 병합을 통해 구성된 클러스터셋일 수도 있다.Referring again to FIG. 5, the keyword clustering apparatus 100 constructs an initial cluster set using a plurality of keyword pairs included in the keyword list (S200), merges the clusters included in the initial cluster set in a bottom-up manner Configure the final cluster set. 7, the keyword clustering apparatus 100 constructs an intermediate cluster set 503 by merging at least some of the clusters included in the initial cluster set 501, 503 are merged to constitute the final cluster set 505. However, according to the embodiment of the present invention, the initial cluster set 501 may also be a cluster set configured through cluster merging.

일 실시예에서, 키워드 클러스터링 장치(100)는 복수의 키워드쌍에 포함된 각각의 키워드쌍을 하나의 클러스터로 생성하는 과정을 반복함으로써, 초기 클러스터셋을 구성할 수 있다.In one embodiment, the keyword clustering apparatus 100 may construct an initial cluster set by repeating the process of generating each keyword pair included in a plurality of keyword pairs into one cluster.

다른 실시예에서, 키워드 클러스터링 장치(100)는 초기 클러스터셋에 포함된 클러스터의 개수를 최소화하기 위해 동일 키워드를 공유하는 클러스터를 빠르게 병합하여 상기 초기 클러스터셋을 구성할 수 있다. 본 실시예에 대하여 도 8을 참조하여 구체적으로 설명한다.In another embodiment, the keyword clustering apparatus 100 may construct the initial cluster set by quickly merging clusters sharing the same keywords to minimize the number of clusters included in the initial cluster set. This embodiment will be described in detail with reference to Fig.

도 8을 참조하면, 키워드 클러스터링 장치(100)는 상술한 실시예와 같이 각각의 키워드쌍을 하나의 클러스터로 생성하는 과정을 반복하여 제1 클러스터셋을 구성하고(S210), 제1 클러스터셋에서, 한글 키워드 및 영어 키워드를 모두 공유하는, 즉 두 키워드의 문자열이 완전 매칭(exact matching)되는 클러스터를 병합하는 과정을 반복하여, 제2 클러스터셋을 구성할 수 있다(S230). 또한, 키워드 클러스터링 장치(100)는 제2 클러스터셋에서, 한글 키워드를 공유하는, 즉 한글 키워드가 완전 매칭되는 클러스터를 병합하는 과정을 반복하여, 초기 클러스터셋을 구성할 수 있다(S250). 참고로, 단계(S250)에서, 한글 키워드에 대한 클러스터 병합을 수행하였으나, 중심 언어가 영어인 경우에는, 영어 키워드에 대하여 클러스터 병합이 수행될 수 있을 것이다.Referring to FIG. 8, the keyword clustering apparatus 100 constructs a first cluster set by repeating the process of generating each keyword pair into one cluster as in the above-described embodiment (S210) A second cluster set can be constructed by repeating the process of merging clusters in which both the Korean keyword and the English keyword are shared, that is, the clusters in which the strings of the two keywords are perfectly matched (step S230). In operation S250, the keyword clustering apparatus 100 may construct an initial cluster set by repeating the process of merging the clusters in which the Korean keywords are shared, that is, the clusters in which the Korean keywords are perfectly matched, in the second cluster set. In step S250, cluster merging is performed for the Hangul keyword. However, if the central language is English, the cluster merging may be performed for the English keyword.

본 실시예에서, 키워드 매칭을 수행하기 전에, 키워드 문자열에 포함된 부호문자(e.g. 특수 문자, 공백 문자, 구두점 등)를 제거하고, 스테밍(stemming) 기술을 이용하여 단어의 어근(stem)를 추출하며, 영어의 경우 대문자를 소문자로 변환하는 전처리 과정이 수행될 수 있다. 상기 전처리 과정을 수행함으로써, 사용자 실수로 인해 키워드에 띄어쓰기 오류가 포함된 경우에도 정확하게 키워드 매칭이 수행될 수 있다.In this embodiment, before the keyword matching is performed, the sign characters (e.g., special characters, blank characters, punctuation marks, etc.) included in the keyword string are removed, and the stem of the word is extracted using a stemming technique And in the case of English, a preprocessing process of converting an uppercase character to a lowercase character can be performed. By performing the preprocessing process, keyword matching can be accurately performed even when a mistake is made in a keyword due to a user mistake.

상술한 실시예에 따르면, 동일 키워드를 공유하는 클러스터의 병합을 통해 초기 클러스터셋에 포함되는 클러스터의 개수를 줄일 수 있다. 이에 따라, 이후의 클러스터 병합 단계의 반복 횟수가 감소되고, 클러스터 간의 유사도 계산 또한 최소화될 수 있다. 본 실시예에 따르면, 클러스터 병합 성능이 향상되고, 클러스터 구축에 소요되는 시간 비용 및 컴퓨팅 비용이 크게 절감되는 효과가 있다.According to the above-described embodiment, the number of clusters included in the initial cluster set can be reduced through merging clusters sharing the same keywords. Thus, the number of iterations of the subsequent cluster merging step is reduced, and the similarity calculation between the clusters can be minimized. According to the present embodiment, there is an effect that the performance of cluster merging is improved, and the time cost and the computing cost required for cluster construction are greatly reduced.

다시 도 5를 참조하면, 키워드 클러스터링 장치(100)는 초기 클러스터셋에 포함된 복수의 클러스터 중에서, 제1 유사도가 임계 값 이상인 클러스터를 병합하여 중간 클러스터셋을 구성한다(S300). 여기서, 상기 제1 유사도는 단일 키워드에서 추출된 특징 기반의 특징 벡터를 이용하여 산출된다. 이에 대한 자세한 설명은 도 9a 내지 도 9c를 참조하여 상세하게 설명하도록 한다.Referring again to FIG. 5, the keyword clustering apparatus 100 constructs an intermediate cluster set by merging clusters having a first similarity degree equal to or higher than a threshold value among a plurality of clusters included in the initial cluster set (S300). Here, the first degree of similarity is calculated using feature-based feature vectors extracted from a single keyword. A detailed description thereof will be described with reference to Figs. 9A to 9C.

다음으로, 키워드 클러스터링 장치(100)는 중간 클러스터셋에 포함된 복수의 클러스터 중에서, 제2 유사도가 임계 값 이상인 클러스터를 병합하여 최종 클러스터셋을 구성한다(S400). 여기서, 상기 제2 유사도는 동일 문서에 포함된 복수의 키워드에서 추출된 특징 기반의 특징 벡터를 이용하여 산출된다. 예를 들어, 키워드 클러스터링 장치(100)는 동일 문서 내 포함된 복수의 키워드에 대하여 어절(단어) 단위로 특징을 추출하거나, n-gram 방식으로 특징을 추출할 수 있다. 이에 따라, 해당 키워드와 다른 키워드 관의 관계, 즉 문맥을 고려한 특징 벡터가 생성되기 때문에, 문맥을 고려하여 클러스터의 병합이 수행될 수 있다. 이에 따라, 동음 이의어에 해당하는 두 키워드가 동일한 클러스터에 포함되거나, 이음 동의어에 해당하는 두 키워드가 서로 다른 클러스터에 포함되는 것이 방지될 수 있는 바, 정확도 높은 클러스터가 구축될 수 있다.Next, the keyword clustering apparatus 100 constructs a final cluster set by merging clusters having a second similarity value equal to or higher than a threshold value among a plurality of clusters included in the intermediate cluster set (S400). Here, the second degree of similarity is calculated using feature-based feature vectors extracted from a plurality of keywords included in the same document. For example, the keyword clustering apparatus 100 may extract features in units of words (words) or extract features in n-grams for a plurality of keywords included in the same document. Accordingly, since the feature vector is generated in consideration of the relationship between the keyword and another keyword, that is, the context, the merging of the clusters can be performed in consideration of the context. As a result, two keywords corresponding to the homonym can be included in the same cluster, or two keywords corresponding to the synonym synonyms can be prevented from being included in different clusters, so that a highly accurate cluster can be constructed.

단계(S400)는 단계(S300)와 특징 추출 기준이 상이하나, 세부 단계는 동일하게 수행될 수 있다. 따라서, 본 단계(S400)에 대한 상세한 설명 또한 도 9a 내지 도 9c를 참조하도록 한다.In step S400, the feature extraction criteria are different from the step S300, but the detailed steps may be performed in the same manner. Therefore, a detailed description of this step (S400) will also be made with reference to Figs. 9A to 9C.

최종 클러스터셋이 구축되면, 키워드 클러스터링 장치(100)는 상기 최종 클러스터셋에 포함된 각각의 클러스터에 대한 대표 키워드를 선정하고, 선정된 대표 키워드를 해당 클러스터의 레이블(label)로 설정한다(S500). 본 단계에 대한 자세한 설명은 도 12를 참조하여 후술하도록 한다.When the final cluster set is constructed, the keyword clustering apparatus 100 selects a representative keyword for each cluster included in the final cluster set, and sets the selected representative keyword to the label of the corresponding cluster (S500) . A detailed description of this step will be given later with reference to Fig.

지금까지, 본 발명의 실시예에 따른 키워드 클러스터링 방법에 대하여 설명하였다. 상술한 바에 따르면, 동일 문서에 포함된 복수의 키워드에서 추출된 특징에 기초하여 클러스터 병합이 수행된다. 즉, 동일 문서에 포함된 복수의 키워드로부터 문맥이 반영된 특징이 추출되고, 상기 특징에 기초하여 클러스터 병합이 수행될 수 있다. 이에 따라, 이음동의어 및 동음이의어가 존재하는 경우라도 정확도 높은 클러스터가 구축되는 효과가 있다.Up to now, a keyword clustering method according to an embodiment of the present invention has been described. According to the above description, cluster merging is performed based on features extracted from a plurality of keywords included in the same document. That is, a feature reflecting a context is extracted from a plurality of keywords included in the same document, and cluster merging can be performed based on the feature. Accordingly, even when there is a synonym and homonym, there is an effect that a highly accurate cluster is constructed.

다음으로, 도 9a 내지 도 11을 참조하여, 중간 클러스터셋 구성 단계(S300)에 대하여 상세하게 설명하도록 한다.Next, the middle cluster set configuration step (S300) will be described in detail with reference to FIGS. 9A to 11.

도 9a 내지 도 9c는 중간 클러스터셋 구성 단계(S300)의 상세 순서도이다.9A to 9C are detailed flowcharts of the intermediate cluster set configuration step S300.

전술한 바와 같이, 중간 클러스터셋 구성 단계(S300)는 단일 키워드에서 추출된 특징 기반의 특징 벡터에 기초하여 클러스터를 병합하는 단계이다. 본 발명의 실시예에 따르면, 키워드쌍에 서로 다른 언어로 표현된 키워드가 포함되므로, 키워드 클러스터링 장치(100)는 각 키워드에 대하여 특징 벡터를 추출하고 클러스터 병합을 수행하게 된다.As described above, the intermediate cluster set configuration step S300 is a step of merging clusters based on feature-based feature vectors extracted from a single keyword. According to the embodiment of the present invention, the keyword pair includes keywords expressed in different languages. Therefore, the keyword clustering apparatus 100 extracts feature vectors for each keyword and performs cluster merging.

예를 들어, 키워드쌍이 한글 키워드 및 영어 키워드로 구성되는 경우, 키워드 클러스터링 장치(100)는 초기 클러스터셋에 포함된 복수의 클러스터 중에서 한글 키워드에서 추출된 특징 기반의 특징 벡터의 유사도가 임계 값 이상인 적어도 일부의 클러스터를 병합하여 제1 클러스터셋을 구성하고(S310), 제1 클러스터셋에 포함된 복수의 클러스터 중에서, 영어 키워드에서 추출된 특징 기반의 특징 벡터의 유사도가 임계 값 이상인 적어도 일부의 클러스터를 병합하여 중간 클러스터셋을 구성한다(S330).For example, when a keyword pair is composed of a Hangul keyword and an English keyword, the keyword clustering apparatus 100 determines whether the similarity of feature-based feature vectors extracted from Hangul keywords among a plurality of clusters included in the initial cluster set is at least The clusters are merged to form a first cluster set (S310), and at least some clusters in which the similarity of feature-based feature vectors extracted from the English keywords among the plurality of clusters included in the first cluster set is equal to or greater than the threshold value And merges to form an intermediate cluster set (S330).

실시예에 따라, 단계(S330)와 단계(S310)의 선후가 변경될 수 있으나, 중심 언어가 한국어인 경우에는 단계(S310)를 먼저 수행하는 것이 바람직할 수 있다. 왜냐하면, 중심 언어가 한국어인 경우 한글 키워드 기준으로 클러스터의 병합이 우선 수행될 필요가 있기 때문이다.According to the embodiment, it is possible to change the end of steps S330 and S310, but it may be preferable to perform step S310 first if the central language is Korean. This is because, if the central language is Korean, merging of clusters needs to be performed first on the basis of a Hangul keyword.

이하에서는, 도 9b 및 도 9c를 참조하여, 단계(S310)의 세부 동작에 대하여 설명하도록 한다. 단계(S330)의 세부 동작은 단계(S310)와 동일한 바, 도 9b 및 도 9c를 참조하도록 한다.Hereinafter, the detailed operation of step S310 will be described with reference to Figs. 9B and 9C. The detailed operation of step S330 is the same as that of step S310, and reference is made to Figs. 9B and 9C.

도 9b 및 도 9c를 참조하면, 키워드 클러스터링 장치(100)는 각 클러스터에 포함된 한글 키워드를 이용하여 각 클러스터의 특징을 추출한다(S311).Referring to FIGS. 9B and 9C, the keyword clustering apparatus 100 extracts characteristics of each cluster using Hangul keywords included in each cluster (S311).

본 발명의 몇몇 실시예에서, 상기 특징은 q-gram 방식으로 추출될 수 있다. 예를 들어, 한글 키워드가 "우리나라"이고, q가 2인 경우, "우리", "리나", "나라"가 특징으로 추출될 수 있다. q의 값은 기 설정된 고정 값 또는 키워드의 평균 길이에 따라 달라지는 변동 값일 수 있다. 본 실시예에 따르면, q-gram을 통해 음절 단위로 세분화된 특징이 추출되기 때문에, 오탈자에 강인한 특징이 추출되는 장점이 있다. 다만, 본 발명의 다른 실시예에 따르면, 어절 단위로 연속된 n개의 단어를 특징으로 추출하는 n-gram 방식이 이용될 수 있고, 다른 방식으로 특징이 추출될 수도 있다.In some embodiments of the invention, the feature may be extracted in a q-gram fashion. For example, if the Korean keyword is "Korea" and q is 2, "us", "lina", "country" can be extracted. The value of q may be a predetermined fixed value or a variation value depending on the average length of the keyword. According to the present embodiment, since features segmented in units of syllables are extracted through the q-gram, there is an advantage that robust features are extracted. However, according to another embodiment of the present invention, an n-gram method of extracting consecutive n words in character units may be used, and features may be extracted in other manners.

다음으로, 키워드 클러스터링 장치(100)는 추출된 특징을 기초로, 각 특징이 포함된 클러스터를 가리키는 역 인덱스를 생성한다. 역 인덱스는 예를 들어 도 10에 도시된 바와 같이 생성될 수 있다. 도 10을 참조하면, 표(511)와 같이, 각 클러스터(C₁, C₂, …)에 대하여 특징(q₁, q₂, …)이 추출되었을 때, 역 인덱스는 표(513)와 같이 구축될 수 있다. 표(513)와 같이 역 인덱스가 구축되면, 특징(q₁)이 포함된 클러스터를 검색할 때, 상기 역 인덱스를 참조하여 클러스터(C₁, C₂, C₃)가 검색 결과로 빠르게 제공될 수 있다. 예를 들어, 상기 역 인덱스가 해시 테이블과 같은 자료구조로 구축되는 경우, O(1)의 시간 복잡도 클러스터 검색이 가능하므로, 클러스터 검색 속도가 크게 향상될 수 있다.Next, the keyword clustering apparatus 100 generates an inverse index indicating a cluster including each feature based on the extracted feature. The inverse index may be generated, for example, as shown in FIG. Referring to FIG. 10, when features q ₁ , q ₂ , ... are extracted for each cluster C ₁ , C ₂ , ... as shown in table 511, Can be constructed. When the inverse index is constructed as shown in the table 513, the clusters C ₁ , C ₂ , and C ₃ are quickly provided as the search results by referring to the inverse index when searching for clusters including the feature q ₁ . For example, when the inverse index is constructed with the same data structure as the hash table, the time complexity cluster search of O (1) can be performed, so that the cluster search speed can be greatly improved.

역 인덱스가 구축되면, 키워드 클러스터링 장치(100)는 초기 클러스터셋에서 임의의 어느 하나의 병합 기준 클러스터를 선정하고(S313), 상기 역 인덱스를 이용하여, 상기 초기 클러스터셋에서 유사도 산출 대상 클러스터를 검색한다(S313).When the inverse index is established, the keyword clustering apparatus 100 selects any one of the merge reference clusters in the initial cluster set (S313), and searches for the similarity degree calculation target cluster in the initial cluster set using the inverse index (S313).

예를 들어, 도 10을 참조하면, 병합 기준 클러스터가 "C₁"인 경우, 병합 기준 클러스터(C₁)는 "g₁", "g₄"를 특징으로 포함한다. 역 인덱스를 참조하면, 클러스터(C₁, C₂, C₃, C₆)가 특징(g₁, g₄)를 포함하는 클러스터로 검색되므로, 클러스터(C₁, C₂, C₃, C₆)가 유사도 산출 대상 클러스터로 선정되게 된다. 이와 같이, 키워드 클러스터링 장치(100)는 기 구축된 역 인덱스를 이용하여, 신속하게 유사도 산출 대상 클러스터를 검색할 수 있다.For example, referring to FIG. 10, when the merge reference cluster is "C ₁ ", the merge reference cluster C ₁ includes "g ₁ ", "g ₄ ". Referring to the station index, the cluster _{_{(C 1, C 2, C}} 3, C 6) is characterized by (g _1, g ₄₎ because the search in the cluster, including a cluster _{_{(C 1, C 2, C}} 3, C 6 ) Is selected as the similarity degree calculation target cluster. As described above, the keyword clustering apparatus 100 can quickly search the similarity degree calculation target cluster using the built-in inverse index.

다시, 도 9b를 참조하면, 키워드 클러스터링 장치(100)는 병합 기준 클러스터와 각각의 유사도 산출 대상 클러스터와의 제1 유사도를 산출한다(S315). 상기 제1 유사도는 예를 들어 하기의 수학식 1과 같이 각 특징 별 IDF 가중치의 합을 이용하여 산출될 수 있다. 하기의 수학식 1에서, c_i는 병합 기준 클러스터를 가리키고, c_j는 유사도 산출 대상 클러스터를 가리키며, g는 특징을 가리킨다. IDF 가중치를 계산하는 수식은 당해 기술 분야에서 이미 널리 알려진 것이므로 이에 대한 사항은 생략하도록 한다.Referring again to FIG. 9B, the keyword clustering apparatus 100 calculates a first similarity degree between the merging reference cluster and each similarity calculation target cluster (S315). The first degree of similarity may be calculated using, for example, the sum of IDF weights for each feature as shown in Equation (1) below. In the following equation (1), c _i indicates a merging reference cluster, c _j indicates a cluster to be subjected to similarity calculation, and g indicates a characteristic. The formula for calculating the IDF weight is already well known in the art, so that the description thereof will be omitted.

상기 제1 유사도를 산출되면, 키워드 클러스터링 장치(100)는 상기 제1 유사도와 기 설정된 임계 값을 비교한다(S316). 비교 결과, 상기 제1 유사도가 임계 값 이상인 경우, 키워드 클러스터링 장치(100)는 해당 클러스터를 병합 후보 클러스터로 선정한다(S317). 단, 실시예에 따라, 키워드 클러스터링 장치(100)는 상대적 기준을 적용하여 상기 제1 유사도가 높은 상위 k개의(단, k는 1 이상의 자연수) 클러스터를 병합 후보 클러스터로 선정할 수 있고, 상기 제1 유사도가 임계 값 이상인 상위 k개의 클러스터를 병합 후보 클러스터로 선정할 수도 있다.When the first similarity is calculated, the keyword clustering apparatus 100 compares the first similarity with a predetermined threshold (S316). If the first similarity is equal to or greater than the threshold, the keyword clustering apparatus 100 selects the cluster as a merging candidate cluster (S317). However, according to the embodiment, the keyword clustering apparatus 100 can select the upper k k-th clusters (k is a natural number of 1 or more) having the first similarity degree as the merging candidate cluster by applying the relative criterion, 1 top k clusters whose similarity is greater than or equal to the threshold value may be selected as the merging candidate clusters.

상기 제1 유사도가 임계 값 이상인 클러스터가 존재하지 않는 경우, 키워드 클러스터링 장치(100)는 다른 클러스터를 병합 기준 클러스터로 선정하고, 상술한 단계를 반복할 수 있다(S328). 물론, 클러스터셋 내에 병합 기준 클러스터로 선정되지 않은 클러스터가 존재하지 않는 경우, 단계(S300)는 종료된다.If the cluster having the first similarity degree is not equal to or greater than the threshold value, the keyword clustering apparatus 100 selects another cluster as the merging reference cluster and repeats the above-described steps (S328). Of course, if there is no cluster not selected as the merge reference cluster in the cluster set, step S300 ends.

병합 후보 클러스터가 적어도 하나 존재하는 경우, 키워드 클러스터링 장치(100)는 병합 기준 클러스터와 병합 후보 클러스터 간의 제2 유사도를 산출한다(S321). 상술한 제1 유사도는 병합 후보 클러스터를 선별하여 클러스터 구축의 성능을 향상시키기 위한 목적이라면, 상기 제2 유사도는 클러스터 구축의 정확도를 향상시키기 위한 목적으로 산출하는 것으로 이해될 수 있다.If there is at least one merging candidate cluster, the keyword clustering apparatus 100 calculates a second similarity degree between the merging reference cluster and the merging candidate cluster (S321). If the first degree of similarity is to improve the performance of cluster construction by selecting the merging candidate cluster, the second degree of similarity may be calculated for the purpose of improving the accuracy of cluster construction.

구체적으로, 키워드 클러스터링 장치(100)는 한글 키워드에서 추출된 특징을 이용하여 제1 특징 벡터를 생성하고, 영어 키워드에서 추출된 특징을 이용하여 제2 특징 벡터를 생성한다. 여기서, 상기 제1 특징 벡터 및 상기 제2 특징 벡터는 하기의 수학식 2와 같이 TF-IDF 가중치를 이용하여 생성될 수 있다. 하기의 수학식 2에서, w(f,c)는 클러스터 c에서 특징 f가 갖는 가중치를 가리키고, tf(f,c)는 클러스터 c에서 특징 f의 빈도를 가리키며, idf(N, n_c)는 클러스터의 개수가 N이고, 모든 클러스터에서 특징 f의 빈도가 n_c일 때 산출되는 IDF 가중치를 의미한다. IDF의 수식은 당해 기술 분야에서 이미 널리 알려진 것인 바 생략한다. 특징 벡터의 예는 도 11을 참조하도록 한다.Specifically, the keyword clustering apparatus 100 generates the first feature vector using the feature extracted from the Hangul keyword, and generates the second feature vector using the feature extracted from the English keyword. Here, the first feature vector and the second feature vector may be generated using a TF-IDF weight as shown in Equation (2). (F, c) denotes the frequency of the feature f in the cluster c, and idf (N, n _c ) denotes the weight of the feature f in the cluster c. Means the IDF weight which is calculated when the number of clusters is N and the frequency of feature f in all clusters is n _c . The IDF expression is well known in the art and is omitted here. An example of the feature vector will be described with reference to Fig.

한글 키워드 및 영어 키워드 각각에 대하여 특징 벡터가 생성되면, 키워드 클러스터링 장치(100)는 예를 들어 하기의 수학식 3을 이용하여 제2 유사도를 산출한다. 하기 수학식 3에서 각 특징 벡터의 유사도를 산출하기 위해 코사인 유사도가 이용되었으나, 실시예에 따라 얼마든지 다른 유사도가 적용될 수 있다. 또한, 하기 수학식 3에서, 상기 제2 유사도는 각 요소에 동일한 가중치가 부여되는 산술 평균으로 산출되는 것을 예로 들었으나, 실시예에 따라 서로 다른 가중치가 부여되는 가중 평균으로 산출될 수도 있다.When a feature vector is generated for each of the Korean and English keywords, the keyword clustering apparatus 100 calculates the second similarity using, for example, the following equation (3). In the following Equation (3), cosine similarity is used to calculate the similarity of each feature vector, but any similarity may be applied according to the embodiment. In the following Equation (3), the second degree of similarity is calculated as an arithmetic average in which the same weight is given to each element, but may be calculated as a weighted average given different weights according to the embodiment.

제2 유사도가 산출되면, 키워드 클러스터링 장치(100)는 상기 제2 유사도와 기 설정된 제1 임계 값과 비교한다(S322). 비교 결과, 상기 제2 유사도가 상기 제1 임계 값 이상인 경우, 키워드 클러스터링 장치(100)는 해당 클러스터를 저장하고, 저장된 병합 후보 클러스터 중에서, 제2 유사도가 가장 높은 클러스터를 병합 대상 클러스터로 선정하며, 상기 병합 대상 클러스터와 병합 기준 클러스터를 병합한다(S323).When the second degree of similarity is calculated, the keyword clustering apparatus 100 compares the second similarity with a predetermined first threshold value (S322). If the second similarity degree is equal to or greater than the first threshold value, the keyword clustering apparatus 100 stores the corresponding cluster, selects the cluster having the second highest similarity among the stored merging candidate clusters as the merging target cluster, The merge target cluster and the merge reference cluster are merged (S323).

비교 결과, 상기 제2 유사도가 상기 제1 임계 값 미만인 경우, 키워드 클러스터링 장치(100)는 상기 제2 유사도가 상기 제1 임계 값보다 작은 제2 임계 값 이상인지 비교한다. 실제로 두 클러스터에 포함된 키워드는 유사하나, 오탈자 등으로 인해 제2 유사도가 낮게 산출될 수도 있기 때문이다.As a result of the comparison, if the second similarity is less than the first threshold, the keyword clustering apparatus 100 compares the second similarity with a second threshold value smaller than the first threshold value. In fact, the keywords included in the two clusters are similar, but the second similarity may be calculated to be low due to misreporting.

비교 결과, 상기 제2 유사도가 상기 제2 임계 값 미만인 경우, 해당 클러스터는 병합 대상 클러스터에서 제외된다(S327).If the second degree of similarity is less than the second threshold value, the corresponding cluster is excluded from the merging target cluster (S327).

비교 결과, 상기 제2 유사도가 상기 제2 임계 값 이상인 경우, 키워드 클러스터링 장치(100)는 한글 키워드 및 영어 키워드에서 자소 단위로 특징을 추출하고, 특징 벡터를 다시 생성하여 제2 유사도를 다시 계산한다. 특징의 추출 단위가 작아질수록, 오탈자에 대한 제2 유사도의 신뢰도가 향상될 수 있기 때문이다. 다시 말하면, 본 단계는 키워드에서 더 작은 단위로 특징이 추출되면 오탈자가 존재하더라도 의미가 동일한 두 키워드 사이에 동일한 특징이 더 많이 발견될 수 있다는 점을 고려한 것으로 이해될 수 있다.If the second degree of similarity is equal to or greater than the second threshold value, the keyword clustering apparatus 100 extracts features in the Korean and English keywords on a per-character basis, and generates the feature vectors again to calculate the second similarity again . The smaller the extraction unit of the feature is, the more reliable the second similarity to the misrecognition can be. In other words, this step can be understood as taking into consideration that if a feature is extracted in a smaller unit of a keyword, even if there is a punctuation, more identical features can be found between two keywords having the same meaning.

제2 유사도가 재산출되면, 키워드 클러스터링 장치(100)는 재산출된 제2 유사도가 상기 제1 임계 값 이상인지 판단하고, 상기 제1 임계 값 이상인 경우 해당 클러스터를 병합 후보 클러스터로 계속 유지하고, 상기 제1 임계 값 미만인 경우 병합 후보 클러스터에서 제외한다(S327).If the second degree of similarity is re-calculated, the keyword clustering apparatus 100 determines whether the re-calculated second degree of similarity is greater than or equal to the first threshold value. If the second similarity degree is greater than or equal to the first threshold value, If it is less than the first threshold value, it is excluded from the merging candidate cluster (S327).

키워드 클러스터링 장치(100)는 최종적으로 저장된 병합 후보 클러스터 중에서 제2 유사도가 가장 높은 클러스터와 병합 기준 클러스터를 병합하게 된다(S323). 또한, 클러스터 셋에서 병합 기준 클러스터로 선정되지 않은 클러스터가 존재하지 않을 때까지 상술한 단계를 반복하게 된다(S328).The keyword clustering apparatus 100 merges the merged reference cluster with the cluster having the second highest similarity among the finally stored merging candidate clusters (S323). In addition, the above steps are repeated until there is no cluster not selected as the merge reference cluster in the cluster set (S328).

한편, 최종 클러스터셋 구성 단계(S400)는 중간 클러스터셋 구성 단계(S300)와 동일하게 수행된다. 다만, 단계(S400)에서는 키워드의 문맥을 고려하기 위해 동일한 문서에 포함된 복수의 키워드로부터 특징이 추출되는 차이가 있다. 예를 들어, 키워드 클러스터링 장치(100)는 동일한 문서에 포함된 복수의 키워드로부터 어절 단위로 특징을 추출하거나, n-gram 방식으로 특징을 추출할 수 있다. 보다 자세한 예를 들어, 복수의 키워드가 "사과 문제 실수"이고 n-gram 방식(n=2, bigram)으로 특징이 추출되는 경우, "사과 문제", "문제 실수"가 특징으로 추출된다. 또한, 어절 단위로 특징을 추출하는 경우, "사과", "문제", "실수"가 특징으로 추출된다. 이때, 과일의 한 종류를 가리키는 동음이의어 "사과"는 "문제", "실수" 등과 같은 키워드를 수반할 가능성은 매우 적으므로, 동음이의어인 두 "사과"가 동일한 클러스터에 포함되는 것이 예방될 수 있는 것이다.The final cluster set configuration step (S400) is performed in the same manner as the intermediate cluster set configuration step (S300). However, in step S400, there is a difference in that the feature is extracted from a plurality of keywords included in the same document in order to consider the context of the keyword. For example, the keyword clustering apparatus 100 may extract features from a plurality of keywords included in the same document in units of phrases, or extract features in an n-gram manner. More specifically, when a plurality of keywords are "apple trouble" and features are extracted by n-gram method (n = 2, bigram), "apple problem" and "problem error" are extracted. In addition, when the features are extracted in the unit of the word, "apple", "problem" and "mistake" are extracted. At this time, it is very unlikely that the homophone "apple" indicating one kind of fruit will be accompanied by keywords such as "problem" or "mistake", so that two "apples" with the same homonym can be prevented from being included in the same cluster It is.

지금까지, 도 9a 내지 도 11을 참조하여, 중간 클러스터셋을 구성하는 단계(S300)에 대하여 설명하였다. 상술한 바에 따르면, 한글 키워드에서 추출된 특징 기반의 특징 벡터 간의 유사도와 영어 키워드에서 추출된 특징 기반의 특징 벡터 간의 유사도의 평균인 제2 유사도에 기초하여 클러스터의 병합이 수행된다. 이에 따라, 복수의 언어로 구성된 키워드쌍이 주어지더라도 정확하게 클러스터가 구축될 수 있다. 다음으로, 도 12를 참조하여, 클러스터의 대표 키워드를 선정하는 단계(S500)에 대하여 설명하도록 한다.Up to now, the step S300 of constructing the intermediate cluster set has been described with reference to Figs. 9A to 11. Fig. According to the above description, the merging of the clusters is performed based on the second similarity which is an average of the similarities between the feature-based feature vectors extracted from the Hangul keywords and the feature vectors based on the feature vectors extracted from the English keywords. Thus, even if a keyword pair composed of a plurality of languages is given, the cluster can be constructed accurately. Next, with reference to FIG. 12, description will be made of a step S500 of selecting a representative keyword of a cluster.

도 12는 대표 키워드 선정 단계(S500)의 상세 순서도이다. 도 12는 임의의 클러스터에서 한글 키워드를 대표 키워드로 선정하는 것을 가정하여 도시한 순서도이다. 따라서, 도 12에 도시된 단계를 모든 클러스터에 대하여 반복하면, 모든 클러스터에 대표 키워드가 선정될 수 있다. 또한, 영문 키워드를 대표 키워드로 선정하는 경우에는 영문 키워드로 도 12에 도시된 단계가 수행될 수 있다.12 is a detailed flowchart of the representative keyword selection step (S500). 12 is a flowchart illustrating the assumption that a Hangul keyword is selected as a representative keyword in an arbitrary cluster. Therefore, if the steps shown in FIG. 12 are repeated for all clusters, representative keywords can be selected for all clusters. When an English keyword is selected as a representative keyword, the steps shown in FIG. 12 may be performed using an English keyword.

도 12를 참조하면, 키워드 클러스터링 장치(100)는 클러스터에 포함된 각각의 한글 키워드로부터 특징을 추출하고, 추출된 특징을 기초로 각각의 한글 키워드에 대한 키워드 특징 벡터를 산출한다(S510). 다음으로, 키워드 클러스터링 장치(100)는 한글 키워드 별로 생성된 키워드 특징 벡터를 평균하여 클러스터 특징 벡터를 산출한다(S530). 다음으로, 키워드 클러스터링 장치(100)는 키워드 특징 벡터 중에서 클러스터 특징 벡터 간의 유사도가 가장 높은 특징 벡터를 대표 키워드 특징 벡터를 선정한다(S550). 상기 유사도는 상술한 바와 같이 코사인 유사도가 이용될 수 있으나, 다른 방식의 유사도가 이용되더라도 무방하다. 마지막으로, 키워드 클러스터링 장치(100)는 대표 키워드 특징 벡터에 대응되는 키워드를 해당 클러스터의 대표 키워드로 결정하고(S570), 상기 대표 키워드를 해당 클러스터의 레이블로 설정할 수 있다.Referring to FIG. 12, the keyword clustering apparatus 100 extracts a feature from each Hangul keyword included in the cluster, and calculates a keyword feature vector for each Hangul keyword based on the extracted feature (S510). Next, the keyword clustering apparatus 100 calculates a cluster feature vector by averaging the keyword feature vectors generated for each Hangul keyword (S530). Next, the keyword clustering apparatus 100 selects a representative keyword feature vector having the highest similarity among the cluster feature vectors among the keyword feature vectors (S550). As described above, the degree of similarity may be used, but similarity in other ways may be used. Finally, the keyword clustering apparatus 100 may determine the keyword corresponding to the representative keyword feature vector as the representative keyword of the cluster (S570), and set the representative keyword to the label of the corresponding cluster.

지금까지 도 12을 참조하여, 대표 키워드 선정 단계(S500)에 대하여 설명하였다. 다음으로, 도 13을 참조하여, 본 발명의 실시예에 따라 구축된 키워드 클러스터를 이용하여 디지털 문서 간의 연관 정보를 제공하는 본 발명의 활용예에 대하여 간략하게 설명한다.Up to now, referring to FIG. 12, the representative keyword selection step S500 has been described. Next, an application example of the present invention for providing association information between digital documents using a keyword cluster constructed according to an embodiment of the present invention will be briefly described with reference to FIG.

도 13에 도시된 바와 같이, 키워드 클러스터 구축 결과, 클러스터 #1에는 키워드A, 키워드 D가 포함되고, 클러스터 #2에는 키워드 B 및 키워드 C가 포함되었다고 가정하자. 또한, 키워드 A 내지 D는 다양한 디지털 문서(논문 A 내지 논문 C, 리포트 A 내지 C, 특허문헌 A 내지 C)에 삽입된 키워드라고 가정하자.As shown in Fig. 13, assume that the keyword cluster A includes keyword A and keyword D in cluster # 1, and keyword B and keyword C in cluster # 2. It is also assumed that keywords A to D are keywords embedded in various digital documents (articles A to C, reports A to C, and documents A to C).

예를 들어 검색 시스템에서, 키워드 A가 검색어로 주어진 경우, 기 구축된 키워드 클러스터를 이용하여, 키워드 D가 연관 검색어로 제공될 수 있다. 또한, 키워드 A가 포함된 논문 A, 보고서 A 및 특허문헌 A를 검색 결과로 제공하고, 더불어 보고서 B가 연관 디지털 문서로 더 제공될 수 있다.For example, in the search system, when the keyword A is given as a search term, the keyword D can be provided as an associated search term using the pre-built keyword cluster. In addition, the article A, the report A and the patent document A including the keyword A can be provided as a search result, and the report B can be further provided as an associated digital document.

또 다른 예를 들어 주제 분석 또는 문서 분류를 수행하는 분석 시스템에서, 키워드 A를 이용하여 논문 A, 보고서 A 및 특허문헌 A가 특정 주제를 갖는 문서로 분류될 수 있고, 보고서 B 또한 상기 특정 주제를 갖는 문서로 분류될 수 있다. 또한, 클러스터 #2와 매핑된 논문 B, 논문 C, 보고서 C, 특허문헌 B 및 특허문헌 C가 다른 주제를 갖는 문서로 분류될 수 있다.In another example, in an analysis system that performs subject analysis or document classification, articles A, A, and A can be classified into a document having a specific subject by using keyword A, and report B can also be classified into a document And the like. In addition, the paper B, the paper C, the report C, the patent document B, and the patent document C mapped to the cluster # 2 can be classified into documents having different subjects.

이외에도 본 발명의 실시예에 따라 구축된 키워드 클러스터는 자연어 처리, 정보 시각화 등 다양한 분야에서 활용될 수 있다.In addition, the keyword cluster constructed according to the embodiment of the present invention can be utilized in various fields such as natural language processing, information visualization, and the like.

지금까지 도 1 내지 도 13을 참조하여 설명된 본 발명의 개념은 컴퓨터가 읽을 수 있는 매체 상에 컴퓨터가 읽을 수 있는 코드로 구현될 수 있다. 상기 컴퓨터로 읽을 수 있는 기록 매체는, 예를 들어 이동형 기록 매체(CD, DVD, 블루레이 디스크, USB 저장 장치, 이동식 하드 디스크)이거나, 고정식 기록 매체(ROM, RAM, 컴퓨터 구비 형 하드 디스크)일 수 있다. 상기 컴퓨터로 읽을 수 있는 기록 매체에 기록된 상기 컴퓨터 프로그램은 인터넷 등의 네트워크를 통하여 다른 컴퓨팅 장치에 전송되어 상기 다른 컴퓨팅 장치에 설치될 수 있고, 이로써 상기 다른 컴퓨팅 장치에서 사용될 수 있다.The concepts of the present invention described above with reference to Figures 1 to 13 can be implemented in computer readable code on a computer readable medium. The computer readable recording medium may be, for example, a removable recording medium (CD, DVD, Blu-ray disk, USB storage device, removable hard disk) . The computer program recorded on the computer-readable recording medium may be transmitted to another computing device via a network such as the Internet and installed in the other computing device, thereby being used in the other computing device.

도면에서 동작들이 특정한 순서로 도시되어 있지만, 반드시 동작들이 도시된 특정한 순서로 또는 순차적 순서로 실행되어야만 하거나 또는 모든 도시 된 동작들이 실행되어야만 원하는 결과를 얻을 수 있는 것으로 이해되어서는 안 된다. 특정 상황에서는, 멀티태스킹 및 병렬 처리가 유리할 수도 있다. 더욱이, 위에 설명한 실시예들에서 다양한 구성들의 분리는 그러한 분리가 반드시 필요한 것으로 이해되어서는 안 되고, 설명된 프로그램 컴포넌트들 및 시스템들은 일반적으로 단일 소프트웨어 제품으로 함께 통합되거나 다수의 소프트웨어 제품으로 패키지 될 수 있음을 이해하여야 한다.Although the operations are shown in the specific order in the figures, it should be understood that the operations need not necessarily be performed in the particular order shown or in a sequential order, or that all of the illustrated operations must be performed to achieve the desired result. In certain situations, multitasking and parallel processing may be advantageous. Moreover, the separation of the various configurations in the above-described embodiments should not be understood as such a separation being necessary, and the described program components and systems may generally be integrated together into a single software product or packaged into multiple software products .

이상 첨부된 도면을 참조하여 본 발명의 실시예들을 설명하였지만, 본 발명이 속하는 기술분야에서 통상의 지식을 가진 자는 본 발명이 그 기술적 사상이나 필수적인 특징을 변경하지 않고서 다른 구체적인 형태로 실시될 수 있다는 것을 이해할 수 있다. 그러므로 이상에서 기술한 실시예들은 모든 면에서 예시적인 것이며 한정적인 것이 아닌 것으로 이해해야만 한다.While the present invention has been described in connection with what is presently considered to be practical exemplary embodiments, it is to be understood that the invention is not limited to the disclosed embodiments, but, on the contrary, I can understand that. It is therefore to be understood that the above-described embodiments are illustrative in all aspects and not restrictive.

Claims

A keyword clustering method performed by a keyword clustering device,
Constructing an initial cluster set using a plurality of keywords contained in a plurality of documents;
Constructing an intermediate cluster set by merging a first initial cluster and a second initial cluster having a similarity degree between initial clusters of a plurality of initial clusters constituting the initial cluster set equal to or greater than a threshold value; And
Merging a first intermediate cluster and a second intermediate cluster having a similarity degree between the intermediate clusters of the intermediate clusters to a final cluster set among the plurality of intermediate clusters constituting the intermediate cluster set,
Wherein the degree of similarity between the first initial cluster and the second initial cluster,
Wherein the first cluster is calculated based on a similarity between a first feature extracted from a keyword belonging to the first initial cluster and a second feature extracted from a keyword belonging to the second initial cluster,
Wherein the degree of similarity between the first intermediate cluster and the second intermediate cluster is calculated by:
Is calculated based on the degree of similarity between the 2-1 characteristic for the first intermediate cluster and the 2-2 characteristic for the second intermediate cluster,
The 2-1th feature is extracted from a combination of a 1-1 keyword belonging to the first intermediate cluster and a 1-2 keyword included in the same document as the 1-1 keyword,
Wherein the second-2 feature is extracted from a combination of a 2-1 keyword belonging to the second intermediate cluster and a 2-2 keyword included in the same document as the 2-1 keyword.
Keyword clustering method.

The method according to claim 1,
Wherein configuring the initial cluster set comprises:
Constructing a first cluster set including a plurality of clusters by generating each of the keywords included in the plurality of keywords as one cluster;
And constructing the initial cluster set by merging clusters sharing the same keyword among a plurality of clusters constituting the first cluster set.
Keyword clustering method.

3. The method of claim 2,
Wherein each of the keywords is a keyword pair including a first keyword and a second keyword, the second keyword is a keyword expressed in a language different from the first keyword,
Wherein the step of merging the clusters sharing the same keyword to construct the initial cluster set comprises:
Constructing a second cluster set by merging clusters sharing both the first keyword and the second keyword among a plurality of clusters constituting the first cluster set; And
And constructing the initial cluster set by merging clusters sharing only the first keyword among a plurality of clusters constituting the second cluster set.
Keyword clustering method.

The method according to claim 1,
Wherein each of the keywords included in the plurality of keywords is a keyword pair including a first keyword and a second keyword, the second keyword is a keyword expressed in a different language from the first keyword,
Wherein configuring the intermediate cluster set comprises:
Constructing a first cluster set by merging clusters having a similarity degree between feature vectors extracted from the first keyword to a threshold value or more among a plurality of initial clusters constituting the initial cluster set; And
And constructing the intermediate cluster set by merging clusters having a similarity degree between feature vectors extracted from the second keyword to a threshold value or more among a plurality of clusters constituting the first cluster set.
Keyword clustering method.

The method according to claim 1,
The feature 1-1 and feature 1-2 are extracted based on a q-gram (where q is a natural number of 1 or more)
Characterized in that the second feature (2-1) and the second feature (2-2)
Keyword clustering method.

The method according to claim 1,
Wherein each of the keywords included in the plurality of keywords is a keyword pair including a first keyword and a second keyword, the second keyword is a keyword expressed in a different language from the first keyword,
Wherein configuring the intermediate cluster set comprises:
Generating a first feature vector for each initial cluster included in the initial cluster set based on the first keyword;
Generating a second feature vector based on the second keyword for each initial cluster included in the initial cluster set; And
Wherein the first clusters include a plurality of initial clusters included in the initial cluster set, merging clusters having an average similarity calculated based on the similarity between the first characteristic vectors and the second characteristic vectors equal to or greater than a threshold value, Lt; RTI ID = 0.0 > 1, < / RTI >
Keyword clustering method.

The method according to claim 6,
Wherein the first feature vector and the second feature vector are generated based on a TF-IDF (Term Frequency-Inverse Document Frequency) weight.
Keyword clustering method.

The method according to claim 1,
Wherein configuring the intermediate cluster set comprises:
Extracting a characteristic from a keyword included in each cluster for each initial cluster constituting the initial cluster set;
Constructing an inverted index indicating an initial cluster including each feature according to the feature;
A first step of selecting one of the plurality of initial clusters constituting the initial cluster set as a merging reference cluster;
A second step of searching for an initial cluster sharing characteristics of the merging reference cluster using the inverse index, and selecting a merging candidate cluster from the searched initial clusters;
A third step of selecting, among the merging candidate clusters, a cluster having a first similarity degree between the merging reference cluster and the merging candidate cluster equal to or greater than a first threshold value as a merging target cluster;
A fourth step of merging the merging reference cluster and the merging target cluster; And
And repeating the first step to the fourth step to construct the intermediate cluster set.
Keyword clustering method.

9. The method of claim 8,
The second step of selecting the merging candidate cluster comprises:
Computing a second similarity between each of the clusters sharing characteristics of the merging reference cluster and the merging reference cluster; And
(K is a natural number equal to or greater than 1) clusters having the second similarity degree among the respective clusters sharing characteristics of the merging reference clusters as the merging candidate clusters.
Keyword clustering method.

10. The method of claim 9,
Wherein the first similarity is calculated through the sum of IDF weights for each feature between the merging reference cluster and other clusters for all features of the merging reference cluster.
Keyword clustering method.

9. The method of claim 8,
Designating a merging candidate cluster having a first similarity degree lower than the first threshold value and a second threshold value lower than the first threshold value as the similarity re-calculation target cluster;
Extracting features of the merge reference cluster and the similarity re-calculation target cluster again on a per-character basis;
Re-generating a feature vector of the merge reference cluster and the similarity re-calculation target cluster using the re-extracted feature, and calculating the first similarity again; And
And merging the merge reference cluster and the similarity re-calculation target cluster when the re-calculated first similarity is equal to or larger than the first threshold value.
Keyword clustering method.

The method according to claim 1,
Determining a representative keyword for a cluster included in the last cluster set,
Wherein the step of determining the representative keyword comprises:
Generating a keyword feature vector for each of the clusters constituting the final cluster set for each keyword included in each cluster;
Generating a cluster feature vector by averaging the keyword feature vectors;
Selecting, as a representative keyword feature vector, a keyword feature vector having the highest degree of similarity to the cluster feature vector among the keyword feature vectors; And
And determining a keyword corresponding to the selected representative keyword feature vector as a representative keyword of the corresponding cluster.
Keyword clustering method.

A method for clustering keywords based on hierarchical clustering performed by a keyword clustering apparatus,
Constructing a first cluster set including a plurality of clusters using a plurality of keywords;
Extracting a feature from a keyword included in each of the clusters included in the first cluster set;
Constructing an inverted index indicating a cluster including each feature by the feature;
A first step of selecting one of the clusters included in the first cluster set as a merging reference cluster;
A second step of searching clusters sharing characteristics of the merging reference cluster using the inverse index and selecting a merging candidate cluster from the searched clusters;
A third step of selecting, from among the merging candidate clusters, a cluster having a first similarity degree between the merging reference cluster and the merging candidate cluster equal to or greater than a threshold value as a merging target cluster;
A fourth step of merging the merging reference cluster and the merging target cluster; And
And repeating the first step to the fourth step to construct a second cluster set.
Keyword clustering method.

14. The method of claim 13,
The second step of selecting the merging candidate cluster comprises:
Computing a second similarity between each of the clusters sharing characteristics of the merging reference cluster and the merging reference cluster; And
(K is a natural number equal to or greater than 1) clusters having the second similarity degree among the respective clusters sharing characteristics of the merging reference clusters as the merging candidate clusters.
Keyword clustering method.

15. The method of claim 14,
Wherein the first degree of similarity is calculated based on a degree of similarity between a feature vector of the merging reference cluster and a feature vector of the merging candidate cluster,
Wherein the second degree of similarity is calculated through a sum of inverse document frequency (IDF) weights for each feature between the merging reference cluster and other clusters with respect to all features of the merging reference cluster.
Keyword clustering method.

14. The method of claim 13,
Wherein configuring the first cluster set comprises:
Constructing an initial cluster set including a plurality of clusters by generating each of the keywords included in the plurality of keywords as one cluster; And
And constructing the first cluster set by merging clusters sharing the same keyword among a plurality of clusters constituting the initial cluster set.
Keyword clustering method.

One or more processors;
Network interface;
A memory for loading a computer program executed by the processor; And
And a storage for storing the plurality of documents and the computer program,
The computer program comprising:
An operation of configuring an initial cluster set using a plurality of keywords included in the plurality of documents;
An operation of merging a first initial cluster and a second initial cluster having a similarity degree between initial clusters of a plurality of initial clusters constituting the initial cluster set equal to or greater than a threshold value to constitute an intermediate cluster set; And
Merging a first intermediate cluster and a second intermediate cluster having a similarity degree between intermediate clusters of a plurality of intermediate clusters constituting the intermediate cluster set to a threshold value or more to construct a final cluster set,
Wherein the degree of similarity between the first initial cluster and the second initial cluster,
Wherein the first cluster is calculated based on a similarity between a first feature extracted from a keyword belonging to the first initial cluster and a second feature extracted from a keyword belonging to the second initial cluster,
Wherein the degree of similarity between the first intermediate cluster and the second intermediate cluster is calculated by:
Is calculated based on the degree of similarity between the 2-1 characteristic for the first intermediate cluster and the 2-2 characteristic for the second intermediate cluster,
The 2-1th feature is extracted from a combination of a 1-1 keyword belonging to the first intermediate cluster and a 1-2 keyword included in the same document as the 1-1 keyword,
Wherein the second-2 feature is extracted from a combination of a 2-1 keyword belonging to the second intermediate cluster and a 2-2 keyword included in the same document as the 2-1 keyword.
Keyword clustering device.

Coupled to the computing device,
Constructing an initial cluster set using a plurality of keywords contained in a plurality of documents;
Constructing an intermediate cluster set by merging a first initial cluster and a second initial cluster having a similarity degree between initial clusters of a plurality of initial clusters constituting the initial cluster set equal to or greater than a threshold value; And
Merging a first intermediate cluster and a second intermediate cluster having a similarity degree between the intermediate clusters of the intermediate clusters to a final cluster set among the plurality of intermediate clusters constituting the intermediate cluster set,
Wherein the degree of similarity between the first initial cluster and the second initial cluster,
Wherein the first cluster is calculated based on a similarity between a first feature extracted from a keyword belonging to the first initial cluster and a second feature extracted from a keyword belonging to the second initial cluster,
Wherein the degree of similarity between the first intermediate cluster and the second intermediate cluster is calculated by:
Is calculated based on the degree of similarity between the 2-1 characteristic for the first intermediate cluster and the 2-2 characteristic for the second intermediate cluster,
The 2-1th feature is extracted from a combination of a 1-1 keyword belonging to the first intermediate cluster and a 1-2 keyword included in the same document as the 1-1 keyword,
Wherein the second-2 feature is extracted from a combination of a 2-1 keyword belonging to the second intermediate cluster and a 2-2 keyword included in the same document as the 2-1 keyword, Lt; RTI ID =
Computer program.