본 논문은 은닉 마코브 모델을 이용한 인터넷 정보 추출 방법을 제안하고, 인터넷상의 웹 사이트에서 상품가격을 효율적으로 추출하는 문제에 적용되었다. 제안된 방법에서 시스템으로 입력되는 데이터는 검색엔진의 인터페이스URL 인데, 상품의 이름을 포함하며, 시스템의 출력은 추출된 각 상품의 상품명, 가격, 사진, 그리고 URL을 목록형태로 보여준다. 주어진 관찰 데이터를 이용해, 은닉 마코브 모델의 학습단계에서는 Maximum Likelihood알고리듬과 Baum-Welch 알고리듬이 학습에 사용되었으며, 학습된 은닉 마코브 모델을 이용하여 시스템의 출력을 찾는 방법으로는 Viterbi 알고리듬이 사용되었다. 제안된 HMM기반의 정보 검출기는 실제상황에서 수집된 관찰데이터에 대해 실험이 수행되었는데, 기존의 PEWEB 알고리듬에 비해 검출도와 정확도에서 매우 향상된 결과를 보이고 있으며, 특히 정확도에서는 99%이상의 높은 결과를 보여주고 있다. 한편, 보다 충실한 학습을 위해 학습 데이터의 수를 800개 이상으로 증가시켰을 패 검출도 역시 약 93%로 향상된 성능을 보여주었다.
본 논문은 은닉 마코브 모델을 이용한 인터넷 정보 추출 방법을 제안하고, 인터넷상의 웹 사이트에서 상품가격을 효율적으로 추출하는 문제에 적용되었다. 제안된 방법에서 시스템으로 입력되는 데이터는 검색엔진의 인터페이스 URL 인데, 상품의 이름을 포함하며, 시스템의 출력은 추출된 각 상품의 상품명, 가격, 사진, 그리고 URL을 목록형태로 보여준다. 주어진 관찰 데이터를 이용해, 은닉 마코브 모델의 학습단계에서는 Maximum Likelihood 알고리듬과 Baum-Welch 알고리듬이 학습에 사용되었으며, 학습된 은닉 마코브 모델을 이용하여 시스템의 출력을 찾는 방법으로는 Viterbi 알고리듬이 사용되었다. 제안된 HMM기반의 정보 검출기는 실제상황에서 수집된 관찰데이터에 대해 실험이 수행되었는데, 기존의 PEWEB 알고리듬에 비해 검출도와 정확도에서 매우 향상된 결과를 보이고 있으며, 특히 정확도에서는 99%이상의 높은 결과를 보여주고 있다. 한편, 보다 충실한 학습을 위해 학습 데이터의 수를 800개 이상으로 증가시켰을 패 검출도 역시 약 93%로 향상된 성능을 보여주었다.
A Hidden Markov Model(HMM)-based information extraction method is proposed in this paper. The proposed extraction method is applied to extraction of products' prices. The input of the proposed IESHMM is the URLs of a search engine's interface, which contains the names of the product types. The outpu...
A Hidden Markov Model(HMM)-based information extraction method is proposed in this paper. The proposed extraction method is applied to extraction of products' prices. The input of the proposed IESHMM is the URLs of a search engine's interface, which contains the names of the product types. The output of the system is the list of extracted slots of each product: name, price, image, and URL. With the observation data set Maximum Likelihood algorithm and Baum-Welch algorithm are used for the training of HMM and The Viterbi algorithm is then applied to find the state sequence of the maximal probability that matches the observation block sequence. When applied to practical problems, the proposed HMM-based system shows improved results over a conventional method, PEWEB, in terms of recall ration and accuracy.
A Hidden Markov Model(HMM)-based information extraction method is proposed in this paper. The proposed extraction method is applied to extraction of products' prices. The input of the proposed IESHMM is the URLs of a search engine's interface, which contains the names of the product types. The output of the system is the list of extracted slots of each product: name, price, image, and URL. With the observation data set Maximum Likelihood algorithm and Baum-Welch algorithm are used for the training of HMM and The Viterbi algorithm is then applied to find the state sequence of the maximal probability that matches the observation block sequence. When applied to practical problems, the proposed HMM-based system shows improved results over a conventional method, PEWEB, in terms of recall ration and accuracy.
* AI 자동 식별 결과로 적합하지 않은 문장이 있을 수 있으니, 이용에 유의하시기 바랍니다.
문제 정의
실험의 결과는 PEWEB의 결과와 비교하였다. 성능분석을 위해 OMINI[2'3], IEPAD 回, MDRra, PEWEB"등의 기법들과의 성능비교가 중요하지만, 이미 기존의 연구 결과에서 IEPAD 과 OMNI 보다 MDR이 월등한 성능 향상이 보고되었고回, PEWEB는 MDR에 비해 검출도와 정확도에서 더욱 향상된 결과를 보고하였으므로(3), 본 논문에서는 HMM 기반의 방법과 PEWEB의 성능 비교 분석에 주안점을 두고자한다. 본연구에서 PEWEB에 관련된 실험은 일반에게 개방되어있는 실행코드를 이용하여 HMM기반의 모델과 동일한학습/검증 환경에서 실행하였다®.
본 논문에서는 사용자의 편의성과 검색 속도를 최대로 보장하면서, 결과의 정확도에서 선행연구의 방법들과 차별되는 은닉 마코브 모델에 기반한 인터넷 정보추출 방법을 제안한다. 제안된 방법은 인터넷 상에 있는 어떤 상품의 가격과 관련된 수많은 웹 페이지에서 목적하는 상품의 규격에 최대한의 정확도를 지니는 상품의 목록을 추출하기위한 방법이다.
가설 설정
1) 모든 노드는 같은 부모 노드를 갖을 것
2) 모든 노드들은 서로 인접할 것
3) 각 노드는 상품명 또는 가격을 가지고 있을 것
제안 방법
본 논문에서 제안되는 시스템의 대략적인 구성도는 그림 1과 같은데, Page retrieval, Segmentation and Parser, Segment 필터, 관측 생성기, 그리고 추출기 (extractor) 의 다섯 가지 부분으로 구성되어 있다. 시스템으로 입력되는 데이터는 검색엔진의 인터페이스 URL 인데, 상품의 이름을 포함하며, 시스템의 출력은 추출된 각 상품의 상품명, 가격, 사진, 그리고 URL을 목록형태로 보여준다.
본 논문에서는 은닉 마코브 모델 기반의 인터넷 정보추출 방법이 제안되었는데, 인터넷 웹 사아트에서 상품가격을 효율적으로 추출하는 문제에 적용되었다. 제안된 방법은 상품의 레코드를 포함하는 데이터의 범위를 정확하게 인식해낼 수 있는 장점이 있다.
성능분석을 위해 OMINI[2'3], IEPAD 回, MDRra, PEWEB"등의 기법들과의 성능비교가 중요하지만, 이미 기존의 연구 결과에서 IEPAD 과 OMNI 보다 MDR이 월등한 성능 향상이 보고되었고回, PEWEB는 MDR에 비해 검출도와 정확도에서 더욱 향상된 결과를 보고하였으므로(3), 본 논문에서는 HMM 기반의 방법과 PEWEB의 성능 비교 분석에 주안점을 두고자한다. 본연구에서 PEWEB에 관련된 실험은 일반에게 개방되어있는 실행코드를 이용하여 HMM기반의 모델과 동일한학습/검증 환경에서 실행하였다®;.
제안되는 HMM 을 이용한 인터넷 정보추출 방법에 대해, 그 유용성을 평가하기 위하여, 실제 데이터를 이 용해실험을 수행하였다. 실험의 결과는 PEWEB의 결과와 비교하였다.
제안된 방법은 상품의 레코드를 포함하는 데이터의 범위를 정확하게 인식해낼 수 있는 장점이 있다. 대부분의 전통적인 방법에서는 데이터 범위가 한 개의 데이터 레코드로 구성되었을 때, 데이터 범위를 인식하지 못 하는 경우가 많다.
방법을 제안한다. 제안된 방법은 인터넷 상에 있는 어떤 상품의 가격과 관련된 수많은 웹 페이지에서 목적하는 상품의 규격에 최대한의 정확도를 지니는 상품의 목록을 추출하기위한 방법이다.
PEWEB에서 결과는 엔트로피 비율이 큰 sub-tree node들로 주어진다. 한편, MDRe edit distance를 사용하는 스트링 매칭 방법을 이용하여 일반화된 노드를 가지는 데이터 구역을 찾아내고, 각각의 일반화된 노드에서 휴리스틱을 사용해 원하는 데이터 레코드를 찾아낸다. 그러나, MDRe edit distance를 사용하기 때문에 속도가 느리고, 휴리스틱의 정교함에 의해 정확도가 매우 좌우되는 경향이 있다区
대상 데이터
PEWEB와의 성능비교 실험을 위해, 각각의 상품에 대해 상업용 일반 검색엔진인 Goggle로부터 먼저, 총 200개의 URL을 관측자료로 수집하였다. 표 1은 이렇게 수집한 웹사이트를 보여주는데, 이 리스트상의 각 웹사이트는 상품의 특징자료와 가격을 충분히 포함하고 있었는데, 여기에 없는 두 개의 사이트는 부정확한 검색으로 관련정보를 포함하고 있지 않아서, 리스트에서 제거 되었다.
HMM의 학습에서는 8개의 상태를 가지는 모델을 사용하였다. 실험에서 무작위로 추출된 100개의 관측자료를 HMM의 학습 데이터로 사용하고, 나머지 100개의 관측자료는 학습된 HMM을 검증하는 테스트데이터로 사용하였다.
이들 웹 사이트는 Google로 검색한 결과로 얻어진 것들로, 각 웹 페이지는 usb 메모리, 노트북 컴퓨터, 웹 카메라 등의 상품에 대한 가격, 사진, 설명 등의 충분한 정보를 가지고 있다. 실험에서는 컴퓨터와 관련된 몇 개의 상품을 queiy로 사용하여 정보추출 시스템의 성능을 평가하는데 사용하였다. 3번째 열은 해당되는 URL에 있는 목표 상품의 수를 나타낸다.
실험의 대상은 다른 포맷과 상품정보를 갖고 있는 총 18 개의 웹 사이트이다. 표 1에서 2번째 열은 각 웹 사이트의 URL 주소인데, 일부는 URL이 너무 길어서 생략한 부분도 있다.
데이터처리
수행하였다. 실험의 결과는 PEWEB의 결과와 비교하였다. 성능분석을 위해 OMINI[2'3], IEPAD 回, MDRra, PEWEB"등의 기법들과의 성능비교가 중요하지만, 이미 기존의 연구 결과에서 IEPAD 과 OMNI 보다 MDR이 월등한 성능 향상이 보고되었고回, PEWEB는 MDR에 비해 검출도와 정확도에서 더욱 향상된 결과를 보고하였으므로(3), 본 논문에서는 HMM 기반의 방법과 PEWEB의 성능 비교 분석에 주안점을 두고자한다.
이론/모형
본 논문에서는 노트북 컴퓨터, USB 메모리, 웹 카메라 등의 각각의 상품 에 대한 HMM 을 학습시키기 위하여, 일반적인 상업용 검색엔진을 이용해 각 상품에 대해 추출된 HTML 페이지를 관측자료로 사용하였으며, Maximum Likelihood (ML) 알고리듬과 Baum- Welch 알고리듬이 학습에 사용되었다. HMM의 학습 과정에는 다음의 세 가지 파라메터가 결정된다.
성능/효과
따라서 유용한 데이터 필드만을 가지는 데이터 레코드를 추출하지 못할 가능성이 있다. PEWEB 와는 다르게, 제안되는 HMM 기반의 정보추출 시스템은 노이즈에 해당되는 정보들을 제외한 필요한 내용만을 가지는 데이터 레코드를 추출하므로, 웹페이지를 좀 더 충실하게 다룰 수 있다.
따라서 이렇게 저장되는 추출 데이터는 필요에 따라 여러가지 형태의 지식검색에 쉽게 응용될 수 있다는 장점이 있다. 실제 상황의 실험 결과에서 보듯이 제안된 HMM 기반의 정보 검출기는 PEWEB에 비해 검출도와 정확도에서 매우 향상된 결과를 보이고 있으며, 특히 정확도에서는 99% 이상의 높은 결과를 보여주고 있다. 한편, 보다 충실한 학습을 위해 학습 데이터의 수를 800개 이상으로 증가시켰을 때 검출도 역시 약 93%의 성능을 보여주었다.
그러나 위의 두 문제에 대해, 제안된 방법은 문제가 되지 않음이 밝혀졌다. 제안된 HMM 기반의 추출기에서의 독특한 장점으로는 추출된 데이터 레코드가 relational DB에 쉽게 저장될 수 있는 형태로 저장될 수 있다는 것이다. 따라서 이렇게 저장되는 추출 데이터는 필요에 따라 여러가지 형태의 지식검색에 쉽게 응용될 수 있다는 장점이 있다.
5%를 나타내었다的. 즉, HMM 기반의 검출기가 PEWEB에 비해 평균적으로 약 18.8%의 검출도 향상을 보여주고 있다. 한편, 정확도의 측면에서는 PEWEB가 평균 62, 1%를 보이는데 비해, HMM 기반의 검출기는 99.
표 1의 결과에서 보듯이, PEWEB의 경우 평균 검출 도가 65.7%인 것에 비해, HMM 기반의 검출기는 84.5%를 나타내었다的. 즉, HMM 기반의 검출기가 PEWEB에 비해 평균적으로 약 18.
실제 상황의 실험 결과에서 보듯이 제안된 HMM 기반의 정보 검출기는 PEWEB에 비해 검출도와 정확도에서 매우 향상된 결과를 보이고 있으며, 특히 정확도에서는 99% 이상의 높은 결과를 보여주고 있다. 한편, 보다 충실한 학습을 위해 학습 데이터의 수를 800개 이상으로 증가시켰을 때 검출도 역시 약 93%의 성능을 보여주었다. HMM 의 구조를 보다 다양한 형태로 변화시켜, 정확한 학습에 의해 검출도를 높일 수 있는 방안에 대한 연구가 계속되어야 할 것이다.
8%의 검출도 향상을 보여주고 있다. 한편, 정확도의 측면에서는 PEWEB가 평균 62, 1%를 보이는데 비해, HMM 기반의 검출기는 99.3%의 정확도를 보이고 있어, 제안된 HMM 기반의 검출기가 매우 정확한 검출 결과를 보이고 있음을 알 수 있다. 이는 HMM의 기본적인 특성인 학습의 성능에 따른 기대되는 정확한 인식능력에 기인한다고 할 수 있다.
후속연구
한편, 보다 충실한 학습을 위해 학습 데이터의 수를 800개 이상으로 증가시켰을 때 검출도 역시 약 93%의 성능을 보여주었다. HMM 의 구조를 보다 다양한 형태로 변화시켜, 정확한 학습에 의해 검출도를 높일 수 있는 방안에 대한 연구가 계속되어야 할 것이다.
참고문헌 (15)
D. Embley, Y. Jiang, Y and Y. Ng, 'Record-boundary discovery in Web documents,' Proc. of SIGMOD-99, 1999
D. Buttler, S. Liu, and C. Pu, 'A Fully Automated Extraction System for the World Wide Web', Proc. of IEEE ICDCS, pp. 361-370, 2001.
http://omini.sourceforge.net/
K. Lerman, S. Minton, and C. Knoblock, 'Wrapper Maintenanc: A machine learning approach,' J. of Artificial Intelligence Research, V. 18, pp. 149-181, 2003
B. Liu, R. Grossman, and Y. Zhai, 'Mining Data Records in Web Pages,' IEEE Intelligent Systems, V. 19, No.6, pp. 49-5, 2004
C. Chang, C. Hsu, and S. Lui, 'Automatic information extraction from semi-structured Web pages by pattern discovery', Decision Support Systems, Vol. 35, No.1, pp. 129-147, 2004
X. H. Phan, S. Horiguchi, and T. Ho, 'PEWEB: Product Extraction from the Web Based on Entropy Estimation', Proc. of the 2004 IEEE/WIC/ACM International Conference on the Web Intelligence, pp. 590-593, 2004
http://www.jaist.ac.jp/~hieuxuan/softwares/peweb/
노수호, 박병준, 'Stochastic 프로세스 모델을 이용한 웹 페이지 추천 기법,' 전자공학회논문지, 제42권 CI편 제6호, pp. 37-46, 2005
D. Gusfield, Algorithms on strings, tree, and sequence. 1997
석현택, 곽경섭, '인체에 투사된 스트라이프 파형의 HMM을 이용한 인식방안,' 전자공학회논문지, 제42권 CI편 제1호, pp. 51-58, 2005
양욱일, 손광훈, '방사 기저 함수 신경망을 이용한 3차원 얼굴인식,' 전자공학회논문지, 제 44권 SP편, 제2호, pp. 82-92, 2007
박창현, 송명선, '인지 무선 시스템을 위한 채널 집합 관리기의 개발 및 성능 분석,' 전자공학회논문지, 제45권 CI편 제5호, pp. 8-14, 2008
L. R. Rabiner, 'A Tutorial on Hidden Markov Models and Selected Applications in Speech Recognition', Proc. of IEEE, Vol.7, No. 2, 57-286, 1989
D.-C. Park, et al., 'Information Extraction System Based on Hidden Markov Model', Proc. of ISNN 2009, (accepted for presentation).
※ AI-Helper는 부적절한 답변을 할 수 있습니다.