최근 Google Product Search와 Yahoo Pipes와 같은 엔터티 검색이 각광을 받고 있다. 특정 엔터티와 관련 있는 웹 페이지를 검색하기 위해 엔터티 검색이 사용된다. 그러나 엔터티(예를 들면, 차이나타운 영화)가 다양한 의미(예를 들면, 차이나타운 영화, 차이나타운 음식점, 인천 차이나타운 등)을 포함하고 있다면 엔터티 검색의 정확성은 크게 떨어진다. 이러한 문제를 해결하기 위해, 본 논문에서는 웹 페이지의 빈도수와 엔터티 관련성 간의 상관관계를 고려하여, Frequent Pattern (FP)-Tree에 기반을 둔 질의어의 중요도를 측정하고 베스트 질의어를 제안하는 새로운 방안을 제안한다. 본 논문의 실험 결과에 의하면, 기존 방안의 정확도가 10% 미만인데 비해, 제안 방안의 평균 정확도는 59%로, 약 5배 향상시킨다.
최근 Google Product Search와 Yahoo Pipes와 같은 엔터티 검색이 각광을 받고 있다. 특정 엔터티와 관련 있는 웹 페이지를 검색하기 위해 엔터티 검색이 사용된다. 그러나 엔터티(예를 들면, 차이나타운 영화)가 다양한 의미(예를 들면, 차이나타운 영화, 차이나타운 음식점, 인천 차이나타운 등)을 포함하고 있다면 엔터티 검색의 정확성은 크게 떨어진다. 이러한 문제를 해결하기 위해, 본 논문에서는 웹 페이지의 빈도수와 엔터티 관련성 간의 상관관계를 고려하여, Frequent Pattern (FP)-Tree에 기반을 둔 질의어의 중요도를 측정하고 베스트 질의어를 제안하는 새로운 방안을 제안한다. 본 논문의 실험 결과에 의하면, 기존 방안의 정확도가 10% 미만인데 비해, 제안 방안의 평균 정확도는 59%로, 약 5배 향상시킨다.
Nowadays, entity search such as Google Product Search and Yahoo Pipes has been in the spotlight. The entity search engines have been used to retrieve web pages relevant with a particular entity. However, if an entity (e.g., Chinatown movie) has various meanings (e.g., Chinatown movies, Chinatown res...
Nowadays, entity search such as Google Product Search and Yahoo Pipes has been in the spotlight. The entity search engines have been used to retrieve web pages relevant with a particular entity. However, if an entity (e.g., Chinatown movie) has various meanings (e.g., Chinatown movies, Chinatown restaurants, and Incheon Chinatown), then the accuracy of the search result will be decreased significantly. To address this problem, in this article, we propose a novel method that quantifies the importance of search queries and then offers the best query for the entity search, based on Frequent Pattern (FP)-Tree, considering the correlation between the entity relevance and the frequency of web pages. According to the experimental results presented in this paper, the proposed method (59% in the average precision) improved the accuracy five times, compared to the traditional query terms (less than 10% in the average precision).
Nowadays, entity search such as Google Product Search and Yahoo Pipes has been in the spotlight. The entity search engines have been used to retrieve web pages relevant with a particular entity. However, if an entity (e.g., Chinatown movie) has various meanings (e.g., Chinatown movies, Chinatown restaurants, and Incheon Chinatown), then the accuracy of the search result will be decreased significantly. To address this problem, in this article, we propose a novel method that quantifies the importance of search queries and then offers the best query for the entity search, based on Frequent Pattern (FP)-Tree, considering the correlation between the entity relevance and the frequency of web pages. According to the experimental results presented in this paper, the proposed method (59% in the average precision) improved the accuracy five times, compared to the traditional query terms (less than 10% in the average precision).
이러한 엔터티 검색에서 발생하는 문제를 해결하기 위해, 본 연구에서는 엔터티와 관련 있는 웹 페이지들을 가장 잘 찾을 수 있는 질의어를 자동으로 추출하는 알고리즘을 제안한다. 제안방안은 엔터티가 입력으로 주어지면, 가능한 모든 질의어(all possible queries)들을 생성하고, 일반 검색 엔진을 통해서 검색 결과를 얻는다.
가설 설정
1) 만일 웹 페이지 wi가 m개의 서로 다른 질의어들을 사용하여 검색된 top-10 웹 페이지 리스트에 포함된다면, wi의 빈도수는 m이다. 본 논문에서는 freq(wi) = m이라고 표기한다.
2) 만일 freq(w1) < freq(w2)이면, w2는 w1보다 엔터티와 좀 더 관련성이 있는(relevant) 웹 페이지라고 가정한다.
t-Test에는 크게 단일표본, 독립표본, 대응표본 방식이 있지만, 본 실험에서는 두 집단에서 공통적으로 가지는 독립변수인 빈도수에 대한 평균 차이를 검증하는 것이기 때문에 독립표본 t-Test를 사용한다. t-Test를 시행하기에 앞서 몇 가지 조건을 고려하는데, 첫 번째 조건은 전체 웹 페이지는 정규분포를 따른다고 가정하고, 표본 개수가 두 집단 별로 50개에 근접한 것을 고려하여 표본은 t-분포를 따른다. 두 번째 조건은 집단 1과 2의 정확한 분산을 알지 못하기 때문에 Levene의 등분산 검정을 통해 분산의 동일성 결과에 따라 t-Test 결과를 도출한다.
제안 방법
1)본 연구의 실험에 의하면, 웹 페이지의 빈도수(frequency)가 높을수록 그 웹 페이지는 해당 엔터티와 관련성이 높은 상관관계(correlation)를 관찰하였다. 따라서 웹 페이지들의 빈도수를 고려하여 Frequent Pattern (FP)—Tree를 생성하고, 이를 바탕으로 각 질의어의 중요도를 측정하는 새로운 알고리즘을 제안한다. 그리고 중요도가 가장 높은 질의어를 베스트 질의어로 출력하게 된다.
t-Test를 시행하기에 앞서 몇 가지 조건을 고려하는데, 첫 번째 조건은 전체 웹 페이지는 정규분포를 따른다고 가정하고, 표본 개수가 두 집단 별로 50개에 근접한 것을 고려하여 표본은 t-분포를 따른다. 두 번째 조건은 집단 1과 2의 정확한 분산을 알지 못하기 때문에 Levene의 등분산 검정을 통해 분산의 동일성 결과에 따라 t-Test 결과를 도출한다. 마지막으로 귀무가설(H0)과 대립가설(H1)은 아래와 같이 설정한다.
이러한 엔터티 검색에서 발생하는 문제를 해결하기 위해, 본 연구에서는 엔터티와 관련 있는 웹 페이지들을 가장 잘 찾을 수 있는 질의어를 자동으로 추출하는 알고리즘을 제안한다. 제안방안은 엔터티가 입력으로 주어지면, 가능한 모든 질의어(all possible queries)들을 생성하고, 일반 검색 엔진을 통해서 검색 결과를 얻는다.1)본 연구의 실험에 의하면, 웹 페이지의 빈도수(frequency)가 높을수록 그 웹 페이지는 해당 엔터티와 관련성이 높은 상관관계(correlation)를 관찰하였다.
대상 데이터
생성된 모든 질의어들은 파싱 라이브러리인 JSoup과 네이버 OpenAPI를 사용하여 네이버 검색 엔진으로부터 각 질의어 별로 상위 10개의 웹 페이지들을 수집한다. 이런 방식으로 수집된 모든 웹 페이지들을 매뉴얼하게 조사하여 각 웹 페이지가 해당 엔터티와 관련이 있는지를 조사한다.
제안 알고리즘의 정확성을 측정하기 위하여 영화와 휴대폰 등 2개의 다른 데이터 세트를 사용하였다. Table 5에서 보는 것처럼, 영화 데이터 세트에는 50개의 최신 영화 엔터티들이 있고, 하나의 엔터티는 8개의 애트리뷰트들을 가지고 있기 때문에, 모든 가능한 질의어의 수는 255개이다.
데이터처리
이러한 가설을 세우고 통계 소프트웨어인 SPSS 21을 사용하여 표본으로부터 t-Test를 실시하였다(유의수준 α = 0.05).
또한 연관 규칙 마이닝(association rule mining)에서 Apriori 알고리즘보다 우수한 FP-Growth 알고리즘이 많이 사용된다. 이러한 기존의 알고리즘들과 본 논문에서 제안한 FP-Tree 기반의 알고리즘의 정확도를 비교하였다. 그림에서 보는 것처럼, Endrullis et al.
성능/효과
이러한 기존의 알고리즘들과 본 논문에서 제안한 FP-Tree 기반의 알고리즘의 정확도를 비교하였다. 그림에서 보는 것처럼, Endrullis et al. 알고리즘과 FP-Growth 알고리즘의 정확도는 크게 차이가 없으며, 제안방안은 기존방안에 비해 5%의 정확도 향상을 보였다. Apriori 알고리즘을 사용한 Endrullis 방안과 FP-Growth 알고리즘과 같은 기존 방안의 경우에는 그 알고리즘의 특성상 가장 높은 빈도를 가진 소수의 웹 페이지들을 이용하지만, 제안방안의 알고리즘은 높은 빈도를 가진 대부분의 웹 페이지들을 이용하여 질의어의 중요도를 측정하기 때문에 기존 방안보다 높은 성능을 보였다.
그리고 중요도가 가장 높은 질의어를 베스트 질의어로 출력하게 된다. 영화와 휴대폰 엔터티들을 사용하여 제안방안을 실험한 결과, 기존방안에 비해 평균 5배의 정확도를 향상시켰다.
후속연구
예를 들면, FPTree에서 확률 기반의 모형 또는 다이내믹 프로그래밍 방법을 사용하여 좀 더 세밀하게 질의어의 중요도를 수치화하는 알고리즘을 개발할 예정이다. 또한 단어 중의성 해소(word sense disambiguation) 기법을 적용하거나 제안방안에서 얻은 결과를 피드백으로 사용하여 검색 키워드의 정확성을 높이는 연구를 수행할 것이다.
향후 연구로는 질의어의 중요도를 측정하는데 좀 더 정교한 알고리즘을 개발하는 것이 필요하다. 예를 들면, FPTree에서 확률 기반의 모형 또는 다이내믹 프로그래밍 방법을 사용하여 좀 더 세밀하게 질의어의 중요도를 수치화하는 알고리즘을 개발할 예정이다.
질의응답
핵심어
질문
논문에서 추출한 답변
엔터티 검색은 어떠한 경우에 검색결과의 정확성이 현저히 떨어지는가?
네이버 또는 구글 검색 엔진에서 ‘암살’과 같은 영화 엔터티를 검색하면, 그 엔터티(entity)1)와 관련 있는 웹 페이지들(relevant web pages)이 검색된다. 그러나 엔터티의 의미가 모호(ambiguous)하거나 여러 의미를 가진 경우에는 검색 결과의 정확성은 현저히 떨어진다. Fig.
GSS란?
관련 있는 웹 페이지를 수집하여 ‘골드 스탠더드 세트(gold standard set; GSS)’로 정의한다. GSS는 해당 엔터티와 관련 있는 모든 웹 페이지들을 포함하는 실제 정답 세트이다. 질의어마다 검색된 상위 10개의 웹 페이지들을 ‘검색된 문서 집합(retrieved document set; RDS)’라고 하면, 질의어들의 정확성을 평가하기 위해 정밀도(precision), 재현율(recall), 조화평균(F-measure) 값들을 측정할 수 있다.
검색된 문서 집합에서 질의어의 정확성을 평가하기 위해 측정하는 값은?
GSS는 해당 엔터티와 관련 있는 모든 웹 페이지들을 포함하는 실제 정답 세트이다. 질의어마다 검색된 상위 10개의 웹 페이지들을 ‘검색된 문서 집합(retrieved document set; RDS)’라고 하면, 질의어들의 정확성을 평가하기 위해 정밀도(precision), 재현율(recall), 조화평균(F-measure) 값들을 측정할 수 있다. 정밀도는 검색된 웹 페이지들 중 관련 있는 웹 페이지들의 비율이고, 재현율은 관련 있는 웹 페이지들 중 실제로 검색된 웹 페이지들의 비율이다.
참고문헌 (12)
K. Balog, M. Bron, and M. Rijke, "Query modeling for entity search based on terms, categories, and examples," The ACM Transactions on Information Systems, Vol.29, No.4, pp.22, 2011.
R. Blanco, P. Mika, and S. Vigna, "Effective and efficient entity search in RDF data," in Proceedings of the 10 th International Semantic Web Conference, Bonn, Germany, 2011.
T. Cheng, X. Yan, and K. Chang, "Supporting entity search: A large-scale prototype search engine," in Proceedings of ACM SIGMOD/PODS Conference, Beijing, China, 2007.
T. Cheng and K. Chang, "Entity search engine: Towards agile best-effort information integration over the web," in Proceedings of the 3 rd Biennial Conference on Innovative Data Systems Research, CA, USA, 2007.
T. Cheng, X. Yan, and K. Chang, "EntityRank: Searching entities directly and holistically," in Proceedings of the 33 rd International Conference on Very Large Data Bases, Vienna, Austria, 2007.
S. Endrullis, A. Thor, and E. Rahm, "Entity search strategies for mashup applications," in Proceedings of IEEE 28 th International Conference on Data Engineering, Washington DC, USA, 2012.
E. Elmacioglu, Y. Tan, S. Yan, M. Kan, and D. Lee, "PSNUS: Web people name disambiguation by simple clustering with rich features," in Proceedings of the 45th Annual Meeting of the Association for Computational Linguistics, Prague, Czech, 2007.
G. Hu, J. Liu, H. Li, Y. Cao, J. Nie, and J. Gao, "A supervised learning approach to entity search," Information Retrieval Technology, Vol.4182, pp.54-66, 2006.
M. Ikeda, S. Ono, I. Sato, M. Yoshida, and H. Nakagawa, "Person name disambiguation on the web by two-stage clustering," in Proceedings of the 18 th International Conference on World Wide Web, Madrid, Spain, 2009.
B. Jansen and A. Spink, "An analysis of web documents retrieved and viewed," in Proceedings of the 16 th International Conference on Internet Computing and Big Data, NV, USA, 2003.
J. Lee and S. Cheon, "Recommendation query ranking system for the search query expansion," Journal of KIISE, Vol.36, No.2(c), 2009.
S. Yoon, "Using query word senses and user feedback to improve precision of search engine," Journal of Korea Society for Information Management, Vol.26, No.4, pp.81-91, 2009.
※ AI-Helper는 부적절한 답변을 할 수 있습니다.