MORPHEUS: 확장성이 있는 비교쇼핑 에이전트

Abstract

비교 쇼핑은 웹 상에 존재하는 웹 상점으로부터 구매를 원하는 상품에 대해 저렴한 가격을 찾아주는 일종의 판매자 중개 방법이다. 확장 가능한 비교 쇼핑 시스템을 생성하기 위해서 에이전트는 각각의 준 구조화된 상점으로부터 필요한 정보만을 추출할 수 있는 wrapper를 자동으로 생성해 낼 수 있어야 한다. 웹 문서를 작성하기 위한 HTML은 포함하고 있는 정보의 의미가 아닌 브라우저를 통한 정보의 표현에 대해서만 정의하고 있다. 또한 각 웹 상점들은 사용자의 다양한 삼품 검색 요구를 수용하기 위해 다양한 상품 검색 방법과 검색 결과의 출력 형태를 가진다. 따라서 자동으로 필요한 정보만을 추출하는 wrapper의 생성은 어려운 작업이다. wrapper의 귀납적인 생성은 이러한 이질적인 환경을 극복하기 위한 기술이다. 그러나 Shopbot과 같은 기존의 확장 가능한 비교 쇼핑 에이전트는 원하는 상품 정보를 추출하기 위해 강한 바이어스에 의존한다. 따라서 Shopbot은 바이어스를 따르지 않는 많은 웹 상점으로부터 wrapper를 생성할 수 없다. 본 논문에서는 강한 바이어스를 사용하지 않고 wrapper를 생성해 낼 수 있는 비교 쇼핑 에이전트 시스템인 모피우스를 제안하다. 모피우스는 간단하면서 견고한 학습 알고리즘을 바탕으로 wrapper를 생성한다. 제안한 학습 알고리즘의 핵심은 상품 검색 결과를 논리적 라인으로 나누고 여기서 나타나는 상품 설명 단위의 패턴으로 wrapper를 생성하는 것이다. 모피우스는 대부분의 웹 상점에 대한 wrapper를 정확하게 생성해 낸다. 또한 학습하려는 검색 결과에 노이즈가 존재하는 경우에도 wrapper를 정확하게 추출할 수 있다. 모피우스는 헤더나 광고와 같은 불필요한 정보들을 제거하는 별도의 단계를 거치지 않으므로 wrapper를 빠르게 생성한다. 궁극적으로 모피우스는 새로운 웹 상점을 사용자가 자유롭게 추가, 삭제할 수 있는 환경을 제공한다.

Comparison shopping is a merchant brokering process that finds the best price for the desired product from several Web-based online stores. To get a scalable comparison shopper, we need an agent that automatically constructs a simple information extraction procedure, called a wrapper, for each semi-structured store. Automatic construction of wrappers for HTML-based Web stores is difficult because HTML only defines how information is to be displayed, not what it means, and different stores employ different ways of manipulating customer queries' and different presentation formats for displaying product descriptions. Wrapper induction has been suggested as a promising strategy for overcoming this heterogeneity. However, previous scalable comparison-shoppers such as ShopBot rely on a strong bias in the product descriptions, and as a result, many stores that do not confirm to this bias were unable to be recognized. This paper proposes a more scalable comparison-shopping agent named MORPHEUS. MORPHEUS presents a simple but robust inductive learning algorithm that automatically constructs wrappers. The main idea of the proposed algorithm is to recognize the position and the structure of a product description unit by finding the most frequent pattern from the sequence of logical line information in output HTML pages. MORPHEUS successfully constructs Correct wrappers for most stores by weakening a bias assumed in previous systems. It also tolerates some noises that might be present in production descriptions such as missing attributes. MORPHEUS generates the wrappers rapidly by excluding the pre-processing phase of removing redundant fragments in a page such as a header, a tailer, and advertisements. Eventually, MORPHEUS provides a framework from which a customized comparison-shopping agent can be organized for a user by facilitating the dynamic addition of new stores.