웹검색의과거와링크분석
웹검색엔진의과거 출처 : http://en.wikipedia.org/wiki/web_search_engine
웹검색엔진의시장점유율 출처 : http://en.wikipedia.org/wiki/web_search_engine * 네이버가국내검색시장의약 70% 점유
웹검색엔진의과거 * The next generation Web Search and the demise of the classic IR model, A. Broder, Yahoo Research, 2007 참조 1995 1997: 1 세대 use only on page text data 웹문서내의데이터 / 단어만을이용해사용자질의에대답 웹문서내의단어빈도수, 단어들의위치를참조 Altavista, Lycos, Excite, Infoseek, Inktomi, WebCrawler, Open Text, Hotbot 돈을받고높은검색결과순위에올려줌 : Goto.com Overture.com Yahoo 1998 2003? : 2 세대 페이지밖의정보, web-specific data 활용 웹문서들간의 Link (connectivity) 분석을통해웹문서의중요순위를매김 구글이대표적. 현재는대부분의검색엔진이 link 데이터활용 구글은검색결과의순위와광고를분리 : 광고란을검색옆에별도로두어광고비를많이받아도검색결과의높은순위에올려주지않음 이전의검색엔진들을완전히제압 Click-through data (What results people click on) Anchor-text (How people refer to this page) 이시기 Goto/Overture 의연매출이 $10 억에이르렀음 Yahoo 가 Overture 와 Inktomi 를매입
2004 현재 : 3 세대 Vertical Search, 통합검색, Universal search 웹문서, 이미지, 비디오, 뉴스, 블로그, 쇼핑, 지도, 책등다양한컨텐츠종류들을통합하여고객에게보여줌. 다양한컨텐츠종류와주제에대한검색을특정컨텐츠종류와주제에특화된 vertical search engine 을활용 동시에 informational, navigational, and transactional 정보를취합해보여줌. 검색어에따라검색결과의보여지는패턴이다름. 우리나라의네이버지식인과통합검색이선도적인서비스임. http://en.wikipedia.org/wiki/list_of_search_engines 에가면많은검색엔진이종류별로분류되어있음.
현재웹검색결과 :
검색결과클릭율및시간 http://www.seopedia.org/wp-content/uploads/2006/10/click-distribution-serp.jpg 처음몇개의검색결과가대부분의클릭을차지하지만, long tail 특성도함께보인다 ; Power law 특성?
미래의웹검색엔진은? Answering the need behind the query 개인경험 & implicit 경험및지식이용 - 개인적취향, 검색패턴 - 유저의검색행동자동취합 & 피드백적용, 사용자들의참여유도 Intelligent - 고객이검색하고자하는진짜목적 / 의도를파악해답을제공 - 때로는 long tail 을활용한 비상식적 인측면도고려 - 적절한기술을이용한 recommendation과논리적추론결과제공 - 직관적인 UI 를통해고객에게빨리답을가르쳐줌 Social Search, 사용자참여검색, AB search ( 일명, 알바검색 ^v^) Hard & soft matches Context 정보활용 ( 위치, 시간, 환경등 ) Pervasive but invisible Always connected
웹검색의활용 -1 : 출처 : A taxonomy of web search, 2002, A. Broder, IBM Research 정보취득 want to learn about something (~39%) 알렉스신애 가왜요즈음인기지? Users want to learn about a topic They want to explore relevant pages 내비게이션 want to go to that page (~25%) 현대자동차 웹페이지가어디지? Users want to visit a particular Web site or page They already know what they want Transactional want to do something (web-mediated) (~36%) - Access a service - 다운로드 - 쇼핑 Web Search Challenges and Progress, Junghoo Cho, 2007 에의하면현재가장많은검색요구는웹페이지를찾는 Navigation 이라고함. 따라서이요구를가장잘대응하는것이검색엔진의목표임.
사람들은웹검색에서무엇을찾으려하지? 출처 : Determining the User Intent of Web Search Engine Queries, Bernard J. Jansen, Danielle L. Booth, Amanda Spink, http://www2007.org/posters/poster989.pdf, 방법 : 3개의검색엔진에질의된 500백만이상의검색질의를활용 사용자의질의를 3 가지카테고리로나눔 1. 네비게이션형질의 queries containing company/business/organization/people names queries containing domains suffixes queries with web as the source queries length (i.e., number of terms in query) less than 3 searcher viewing the first search engine results page
2. 정보형질의 uses question words (i.e., ways to, how to, what is, etc.) queries with natural language terms queries containing informational terms (e.g., list, playlist, etc.) queries that were beyond the first query submitted queries where the searcher viewed multiple results pages queries length (i.e., number of terms in a query) greater than 2 queries that do not meet criteria for navigational or transactional 3. 트랜즈액션형질의 queries containing terms related to movies, songs, lyrics, recipes, images, humor, and porn queries with obtaining terms (e.g., lyrics, recipes, etc.) queries with download terms (e.g., download, software, etc.) queries relating to image, audio, or video collections queries with audio, images, or video as the source queries with entertainment terms (pictures, games, etc.) queries with interact terms (e.g., buy, chat, etc.) queries with movies, songs, lyrics, images, and multimedia or compression file extensions (jpeg, zip, etc.) 앞의 Broder, 2002 결과와다름
Link Analysis of the Web 자료 : 1. Mining the Link Structure of the World Wide Web (1999) - S. Chakrabarti, B. Dom, D. Gibson, J. Kleinberg, R. Kumar, P. Raghavan, S. Rajagopalan, A. Tomkins 2. Authoritative Sources in a Hyperlinked Environment (1997) - Jon M. Kleinberg * 위저자들의이름을잘기억하라. 웹공부하다보면많이나옴.
검색엔진의문제점 : Search engines are index-based and limited to keyword searches. Keyword search, even very narrowed, not always return expected results. Problem with correctness of results or too wide range. 페이지내용중에그페이지를잘설명하는키워드 / 단어를갖고있지않는경우가많다 - 현대자동차 홈페이지에자동차제작회사라는말이많이나오지않는다 - 구글, 네이버에 검색엔진 이라는말이많이나오지않는다
목표 : Design algorithms for mining link information. Develop techniques that take advantage of social organisation of the Web. Effectively find authorative pages in some field. Point knowledge hubs in some field.
HITS algorithm 개관 페이지 -p 의저자가페이지내에페이지 - q 로의링크를포함했으면페이지 -q에 authority를부여했다고할수있다. 많은수의링크들은단순히웹내비게이션용으로만들어졌다 많은수의링크들은광고성이다 Computes hubs and authorities for search topic - Authority : In link 를많이받는페이지. Page rank 가높은페이지. - Hub : Authority 가큰곳으로많은 Out-link 를보내는페이지. - Certain natural type of equilibrium exists between hubs and authorities in the graph dened by the link structure Components Sampling : It is processed on a small subset of relevant documents, not all documents as was the case with PageRank - focused collection of pages likely to have many relavant authories weight-propagation : It computes two scores per document, hub and authority - determine weights of hubs and authorities in iterative process
HITS algorithm Web representation - directed graph 알고리즘을적용할웹의일부분 sub graph 를구한다. - 검색어 (query string) 을갖고있는웹페이지들중에서구함. Concentrate on links that go to other domains. - Local links have mainly navigational purposes. 따라서같은도메인내의다른페이지를가리키는링크는제외함. Apply iterations of algorithm to reduced set of web pages.
HITS steps 1 - root and base set HITS는다음과같은조건을만족하는웹페이지들의집합 (S σ, base set) 을대상으로 대상으로 HITS 알고리즘을적용한다. (i) S σ is relatively small. 즉, base set S σ 내의웹페이지들의숫자가많으면곤란하다. HITS 계산이장난아니기에. (ii) S σ is rich in relevant pages. 즉, 물론 base set 내의있는페이지들이검색어와관련깊으면좋다. (iii) S σ contains most (or many) of the strongest authorities. Authority 값이높을가능성이많은페이지일수록좋다. σ: query string, 검색어 Q σ : Set of of all pages containing the query string σ, 검색어를갖고있는페이지들. 검색엔진이 return 해주는페이지들 R σ : Root set. t highest-ranked pages returned from the query of a text-based search. The links between the nodes in the R σ is small. 즉단순 text based 검색엔진에서상위로랭크된페이지들인 R σ 내의페이지들간에는서로링크가별로없는경우가많다. S σ : Root Set 를확장한것. Root set 내의페이지가가리키는페이지들과와 Root set 내의페이지를가리키는페이지들의합집합. 단, Root set 내의페이지를가리키는모든페이지들을포함하는것이아니라일부만포함시킨다. set set
HITS steps 2 - what to count? Distinguish the pattern of relevant pages 단순히 in-degree 만감안하면강한 authority 페이지와단순히인기가많은노드가구별되지않는다 good hub is a page that points to many good authorities; a good authority is a page that is pointed to by many good hubs.
HITS - calculating weights Authority weight : Hub weight : If p points to many pages with large x-values, then it should receive a large y- value; and if p is pointed to by many pages with large y-values, then it should receive a large x-value.
HITS steps - how to count? Count OUT links Count IN links Hub weight Authority weight Authority weight를구해야 Hub weight를계산하고, Hub weight가있어야 Authority weight를계산할수있다. 이사이클을반복한다.
Matrix notation: A - adjacency matrix - A[i, j] = 1 if i-th page points to j-th page - A[i, j] = 0 if i- 페이지에서 j- 페이지로의링크가없으면 X = [x 1, x 2,,,,, x n ] T Y = [y 1, y 2,,,,, y n ] T 로하면 X A T Y Y AY
HITS - 결과 결과 Applying iterative multiplication (power iteration) will lead to calculating eigenvector of any non-degenerate initial vector. Hubs and auhtorities as outcome of process. Eigenvector/Hub & authority 값 --> not a process artifact. Hub 나 authority 들의초기값에관계없이순전히 link 구조에따라결정됨 HITS 적용후높은 Hub 값과 Authority 값을나타내는페이지들의링크관계는높은 Hub 값을갖는페이지들로부터높은 Authority 값을갖는페이지들로향하는링크들이빽빽이있는구조를나타낸다. HITS 에서검색어가사용되는것은 root set 을구할때까지이다. 이이후로는링크관계만사용되고검색어는더이상 Hub 값과 Authority 값을구할때사용되지않는다. 그렇지만 HITS 는꽤괜찮은검색결과를나타낸다. 예를들어 search engines 로검색했더니 Yahoo!, Excite, Magellan, Lycos, and AltaVista 가높은순위로나왔다.
HITS 문제점 From narrow topic, HITS tends to end in more general one. 세부적인질의어를던지면보다일반적인결과를가져올경우가있다. Specific of hub pages - many links can cause algorithm drift. They can point to authorities in different topics. A 란주제에대해높은허브값을갖는페이지 _A 가다른주제 B 나 C 에관한내용도있어, 이 B, C 들이해당페이지 _B 와페이지 _C 들을가리킬때, 페이지 _B 와페이지 _C 에 A 란주제에관련해 authority 값을높여주게된다. 이러면사실페이지 _B 와페이지 _C 들은 A 주제와관계가없는데에도 A 에힘입어 authority 값이높아지게되어문제가된다. Pages from single domain / website can dominate result, if they point to one page - not necessary a good authority. 같은도메인 / 웹사이트에있는페이지들이어쩌다 base set 에많이포함되고, 이페이지들이 ( 같은사람에게서만들어졌을가능성이많기에 ) 특정한페이지를많이가리키면별로의미가없는그페이지가높은 authority 값을갖게된다.
HITS Algorithm 의개선 Use weighted sums for link calculation. Take advantage of anchor text - text surrounding link itself. 링크의 anchor text 는자신이가리키는페이지의특징 /tag 를나타낼경우가많다. 즉, 자동차 페이지를가리키는 anchor text 로 요리 를쓸가능성이많지않다. 따라서, 검색어에대해 authority 가높은페이지들은 in-link 의 anchor text 가검색어와관련있는단어일경우가많겠다. 이를이용해 authority 계산에 inlink 의 anchor text 의미가유사하면그 weight 를높인다. Break hubs into smaller pieces. Analyze each piece separately, instead of whole hub page as one. 앞에서보았듯이한페이지에많은주제가있을시, 그허브값이분산되어 out-link 페이지들의 authority 계산에쓰인다. 이럴경우하나의페이지를버츄얼하게주제에따라분할한다. Disregard or minimize influence of links inside one domain.
Usage: trawling the Web 잘보이지않는사이버커뮤니티의발견 group of content creators sharing a common interest with set of Web pages large number of small communities with narrow topic even not registered in newsgroups or other catalogs
How to find cyber communities Community - small group that has a dense pattern of linkage. Each community has similar linkage signature. Graph structure - directed bipartite graph
검색에서 Link 분석음미 이논문들은 1997-99 년경에발표된것이다. 따라서이즈음에검색품질을높이는방법으로 페이지내의링크관계를이용하려는생각이활발했음을알수있다. 우리는구글검색엔진에서페이지랭크를보았고또비슷한시대의 HITS 를보았다. 대학원생이던 Page 와 Brin 은구글을만들었고교수이던 Kleinberg 는논문을썼다. 어떤사람들은 HITS 가 페이지랭크에게영감을주었다고한다. 페이지랭크값은검색어와관련없이순수하게링크연결이의미하는 voting 지표에따라나온값이지만 HITS 의 HUB 값과 AUTHORITY 값은검색어와관계가있다. 그러니, 같은 hub-authority 값을지닌페이지들이라도주제가다르면절대적인잣대로중요성을비교할수없을것이다. 검색어가다르지만 각각의검색어내에서 hub-authority 값이같은페이지는그검색어내에서상대적인중요성레벨이 같다고생각할수있을것같다. HITS 에서 base set 을선정시우선기본적으로순수 text based search 를해서그중가능성있는 페이지들로 base set 를결정하는데, 이때 root set 를갖고 connected component 특성을갖는 방향으로성장시킨다. 앞서우리는 A. Broder 일당들의논문에서웹의그래프구조를보았다. 거기에서웹의약 ¼ 정도가 strongly connected component라고보았다. 그러면, 검색어에대해순수 text based search 한결과인 Q σ 에대해가장큰 strongly connected component 를구해여기에 HITS 를적용하면어떻게될까? 이때에 strongly connected component 크기가 ¼ 이넘을까? 너무 size 가큰가? HITS 를검색어와상관없이페이지랭크와같이전체웹에적용하면어떨까? 한페이지에 Hub 값과 Authority 값이동시에존재하는데, 이것을갖고랭킹을한다면이값들을어떻게 조합해서쓰는것이좋을까? 검색어에따라달라질수있나? 컨텐츠종류에따라달라질수있나?