시맨틱링크를사용한페이지순위알고리즘개선 843 시맨틱링크를사용한페이지순위알고리즘개선 (Improvement of PageRank Algorithm using Semantic Link) 전희국 임동혁 김형주 (Hee-Gook Jun) (Dong-Hyuk Im) (Hyoung-Joo Kim) 요약페이지랭크는웹정보검색의중요도를평가하는대표적방법이다. 그러나페이지랭크가가진중요도판단의특성상의미없는문서지만인링크개수가많아중요한문서로인식될수있는가능성이존재한다. 기존방법들이링크를차등평가하는대안을제시했으나하이퍼링크기반웹구조의성격상링크의중요성을직접평가할수없는문제가있다. 이러한문제를해결하기위해본논문에서는시맨틱링크를사용하여웹구조를의미를가진링크기반의웹구조로변경해링크의중요성을직접판단하도록중요도계산방법을개선했다. 실험결과제안한방법이상위순위에보다많은관련문서를제시해더높은적합도를가지는것을보였다. 키워드 : 온톨로지, 페이지랭크, 시맨틱웹, RDFa Abstract PageRank is a representative method to evaluate the importance of web pages for web information retrieval. However, it is possible for meaningless pages that have many inlinks to be recognized as important pages because of characteristics of PageRank. Existing papers that provide methods to stratify weight of links still have a problem these methods cannot evaluate the weight of links directly in hyperlink based web structure. We propose a new approach that changes the hyperlink based web structure to the semantic link based web structure to evaluate the weight of links directly by using semantic links. Experiment shows that our approach performs better than the existing PageRank in terms of evaluating the importance of web pages. Key words : Ontology, PageRank, Semantic Web, RDFa 1. 서론 페이지랭크 [1] 는웹정보검색을위해문서의중요도를 본연구는 BK-21 정보기술사업단의연구결과로수행되었음 이논문은 2012년도정부 ( 교육과학기술부 ) 의재원으로한국연구재단의지원을받아수행된연구임 (No. 20120009186) 비회원 : 서울대학교컴퓨터공학부 hgjun@idb.snu.ac.kr (Corresponding author임 ) 비회원 : 서울대학교컴퓨터연구소객원연구원 dhim@idb.snu.ac.kr 종신회원 : 서울대학교컴퓨터공학부교수 hjk@snu.ac.kr 논문접수 : 2012년 7월 24일심사완료 : 2012년 9월 8일 CopyrightC2012 한국정보과학회 ː개인목적이나교육목적인경우, 이저작물의전체또는일부에대한복사본혹은디지털사본의제작을허가합니다. 이때, 사본은상업적수단으로사용할수없으며첫페이지에본문구와출처를반드시명시해야합니다. 이외의목적으로복제, 배포, 출판, 전송등모든유형의사용행위를하는경우에대하여는사전에허가를얻고비용을지불해야합니다. 정보과학회논문지 : 컴퓨팅의실제및레터제18권제12호 (2012.12) 평가하는대표적인방법이다. 페이지랭크는문서간링크에기반해중요도를계산하며, 이전키워드매치에기반한방법보다더나은검색결과를보인다. 그러나페이지랭크는인링크를많이가지고있으면실제의내용에상관없이중요한문서로인식될가능성이높아지는구조적취약점이있다. 이러한문제를개선하기위해문서간링크를차등평가해중요도를계산하는방법들이제안되어왔다. 그러나월드와이드웹의하이퍼링크는단순한연결기능만가지고있으므로차등평가를위한링크의중요도는직접판단할수없는문제가있다. 이러한이유때문에지금까지의개선방법들은링크구조를분석하거나 [2], 저자신뢰도네트워크를구축 [3] 하는등추가정보를이용해링크의중요도를추정하는방법을사용했다. 본논문에서는직접링크의의미를판단할수있도록시맨틱링크를활용한새로운페이지랭크방법을제시한다. 기존연구들이하이퍼링크기반웹구조는유지한채페이지랭크를개선해온반면, 본논문에서는웹에서
844 정보과학회논문지 : 컴퓨팅의실제및레터제 18 권제 12 호 (2012.12) RDFa[5] 를활용해시맨틱정보를추출해내어의미를가진링크 (Semantically labeled link) 기반의웹구조영역으로문제를가져와해결한다. 그결과링크의의미를직접평가해문서의중요도를계산하는것이가능해진다. 또한중요도를단순히링크개수로평가하는것에서더나아가문서가얼마나중요한정보를가지고있는가로평가하는기준을제시할수있게되었다. 논문의구성은다음과같다. 2장에서는페이지랭크를개선한기존방법들을살펴보고 3장에서는제안하는시맨틱링크기반페이지랭크알고리즘에대해설명한다. 4장에서는실험방법및결과를제시하고 5장에서결론및향후연구에대해언급한다. 2. 관련연구 2.1 PageRank 페이지랭크 [1] 는웹문서의중요도를계산하는알고리즘이다. 한문서의페이지랭크값은자신을가리키는링크를가진문서들의페이지랭크값의합이다. 반대로자신은다른문서로향하는아웃링크의개수만큼균등하게페이지랭크값을나누어분배한다. 그림 1을예로들면, 문서 A는자신의페이지랭크값 20을 B, C에각각 10씩전달한다. 문서 D는 B, C에각각 30씩전달한다. 따라서문서 B의페이지랭크값은 40이된다. 식 (1) 은링크고립문제를다루기위한상수 d가추가된페이지랭크수식이다. 그러나링크기반의중요도계산방법으로인해의미없는문서지만인링크가많아높은페이지랭크값을가질수있는문제가발생할수있다. 그림 2 Weighted PageRank 의예 W in (A, B) = I B /(I B + I C)=2/3 아웃링크비율도마찬가지방법으로계산한다. W out (A, B) = O B / (O B + O C)=2/5 그러나이알고리즘도역시링크의의미보다는개수에기반을두고있다는한계가있다., (2) 2.3 PageRank with Author Trust Network [3] 은각문서를작성한저자들의신뢰도네트워크를별도로구축한다. 이를통해저자들이작성한문서를평가할수있음과동시에저자들간의신뢰도를사용하여페이지랭크값을개선할수있다. 그러나저자신뢰도네트워크의관리비용이추가로발생하며, 문서의가치에대한평가는시간이지남에따라진부화 (Obsolete) 될수있다는문제점이있다. 2.4 Weighted Page Content Rank [4] 는 Weighted PageRank[3] 에웹컨텐츠마이닝기법을도입해페이지랭크알고리즘을개선했다. 링크가중치를계산할뿐만아니라, 주어진검색어에문서가얼마나관련있는지를컨텐츠마이닝기법으로측정한다. 하지만두문서사이의링크에대한의미를측정하는방법은여전히링크개수에기반을두고있으며, 문서의관련성을위해컨텐츠마이닝과정을거쳐야한다는추가비용이발생한다. 3. 시맨틱링크기반페이지랭크 그림 1 PageRank의예 (1) 2.2 Weighted PageRank Weighted PageRank[2] 는식 (2) 처럼문서의인링크비율과아웃링크비율을사용해링크에가중치를계산한다. 예를들면, 그림 2에서 B의 A에대한인링크가중치는 A와연결된 B와 C의인링크총합 3으로 B의인링크개수 2를나눈값이다. 본절에서시맨틱링크에기반한개선된페이지랭크알고리즘을설명한다. 이방법은단순히인링크의개수가아닌실제문서가얼마나중요한정보를많이가지고있는지로문서의중요도를평가하는새로운기준을제안한다. 시스템은크게 4가지로분류된다 ( 그림 3). 첫번째단계는웹문서를돌아다니며시맨틱정보를추출한다. 두번째단계에서추출한정보들을병합해 RDF 그래프를구축한다. 세번째단계는구축한 RDF 그래프에서자원 (Resource) 들의랭크값을계산한다. 마지막으로네번째단계에서자원들의랭크값을활용하여웹문서의페이지랭크값을구한다.
시맨틱링크를사용한페이지순위알고리즘개선 845 그림 5 RDFa 가선언된 HTML 문서의 RDF 파싱 그림 3 시맨틱링크기반페이지랭크시스템 3.1 의미정보추출본논문에서는웹문서가 RDFa[5] 를이용해 Semantic Annotation이추가된상태라고가정 1) 을한다. RDFa는일반 XHTML 페이지에 RDF정보를정의할수있도록하는기술이다. RDF[6] 는표현의대상이되는자원 (Resource) 간의시맨틱관계정보를그림 4처럼 주어부 (Subject)-서술부(Predicate)-목적부(Object) 형태의트리플 (Triple) 로표현하므로, 이를이용해의미있는단위인자원을가지고문서의중요도를측정할수있게되고, 트리플구조에의해의미있는서술부를가지고링크의가중치를측정할수있다. 그림 4 RDF 트리플의예우선첫단계로웹문서를크롤링하면서 RDF 파싱을진행한다. 그림 5는 RDFa가선언된 HTML문서에서 RDF 파싱을하는예를보여준다. 3.2 RDF 그래프구축첫번째단계에서모든웹문서의 RDF 파싱이끝나면, 두번째단계로만들어진 RDF 트리플들을모두병합한다. RDF 자원은 URI라는유일한값을가지고있으므로, 서로다른트리플에 URI가동일한자원이각각있다면그두자원은동일한것으로보고 RDF 트리플들을합쳐나갈수있다 ( 그림 6). 1) RDFa 는 2004년 W3C에의해만들어져 2008년표준으로채택되었다. RDFa 가적용된 XHTML 문서는브라우저에보일수있을뿐아니라 RDF 파싱이가능하다. 더나아가 [7,8] 과같이웹문서에자동으로 RDFa 를작성해주는방법들이제안되고있다. RDFa 는시맨틱웹으로의발전을가속화할수있는기술로서추후활용도는더욱높아질것으로보이며, 이에근거하여본논문의연구도 RDFa 가적용된웹문서를이용해연구및실험을하였다. 그림 6 RDF 트리플병합과정 3.3 ResourceRank 두번째단계에서만들어진 RDF 그래프를사용해자원의랭크 (ResourceRank) 를계산한다. 계산방법은페이지랭크알고리즘의기본원리와비슷하나자원간의링크는의미가있는 Predicate으로연결되어있으므로링크의가중치를직접계산할수있다. 링크의가중치계산방법은직접적 (Manually) 혹은반자동적 (Semi-automatically) 인방식이있다. 반자동적인방식은 TF- IDF 를이용한방법 [9] 등이있다. 본논문에서는직접적으로링크의가중치를계산했다. 이렇게계산된가중치를이용해자원의랭크를계산하는방법은식 (3) 과같다. (3) 3.4 PageRank 세번째단계에서구한자원들의랭크값을원래자원이추출된웹문서로보내웹문서의페이지랭크값을최종계산한다. 계산방법은식 (4) 와같으며웹문서의 Page- Rank는웹문서가가지고있는모든자원의 Resource- Rank값의합이다. (4) 4. 실험결과 4.1 실험데이터실험을위해 400개의웹문서가포함된가상의웹환경을구축하였다. 각웹문서안에는 440개의자원 (Re-
846 정보과학회논문지 : 컴퓨팅의실제및레터제 18 권제 12 호 (2012.12) source) 에대한 RDF 트리플이선언되어있다. 웹문서의내용은위키피디아데이터의일부를발췌하여작성하였다. 페이지랭크와시맨틱링크기반페이지랭크의수행결과를보다직관적으로비교할수있도록각웹문서는 영국문학 과관련한주제로만작성하는것으로실험에제약을두었다. 4.2 실험결과본절에서는구축한웹환경에대해페이지랭크와시맨틱링크기반페이지랭크를수행한결과를비교한다. 검색어는 이상한나라의앨리스 ( 이하 앨리스 ) 를사용하였다. 그림 7은결과문서개수별관련문서의개수를비교한그래프이다. x축은결과로제시하는문서의개수, y 축은그중실제로검색어와관련된문서의개수이다. 결과문서개수가많을수록페이지랭크와시맨틱링크기반페이지랭크가제시하는관련문서개수는비슷해지나결과문서개수가적을때는시맨틱링크기반페이지랭크가제시하는관련문서개수가상대적으로많다. 즉시맨틱링크기반페이지랭크방법을사용하면사용자가원하는결과를상위문서로보다많이제시할수있음을알수있다. 그림 8은페이지랭크와시맨틱링크기반페이지랭크의적합도 [2] 를비교한결과이다. x축은결과로제시하는문서의개수, y축은적합도의로그값이다. 적합도는관련문서들이결과문서의상위순위로제시될수록값이커진다. 한가지주목할점은결과문서개수가 200개인경우두방법모두동일한개수인 107개의관련문서를제시했지만 ( 그림 7), 적합도는시맨틱링크기반페이지랭크가더높은값 ( 그림 8) 을가지고있다. 두방법이제시한관련문서의개수는같으나시맨틱링크기반페이지랭크가관련문서들을보다상위순위에나오도록제시해주었기때문이다. 표 1은문서에대한중요도판단방법의차이를볼 그림 8 결과문서개수별적합도비교수있는실험결과이다. 페이지랭크에서 앨리스 의출판사인 Macmillan과미국의랭킹결과는 33위, 5위로미국의중요도가더높다. 그러나시맨틱링크기반페이지랭크에서는 15위, 16위로 Macmilllan의중요도가올라간다. 위결과를자세히살펴보기위해표 2로출판사와미국문서가포함한자원에대해비교하였다. 시맨틱링크기반페이지랭크의세번째단계인자원의랭킹 (ResourceRank) 에의한순위를살펴보면다음과같다. Macmillan 웹문서에는두자원 macillan 과 publish company 가있으며각각의자원랭킹값은 0.659, 0.468 이다. 반면웹문서미국안의자원 unitedstate 의자원랭킹값은 1.107이다. 개별자원의자원랭킹값으론 unitedstate 가 macmillan 과 publish company 보다높지만, 웹문서는자신안의모든자원의자원랭킹값의총합으로계산되므로 ( 식 (4)) 최종적으로계산된미국의시맨틱링크기반페이지랭크값 1.107보다 Macmillan의값 1.127이더커져순위가바뀌게된것을관찰할수있다. 이결과는시맨틱링크기반페이지랭크가전통적방법의페이지랭크보다검색어에대해더욱관련있는문서를중요한문서로판단함을보인다. 앞서언급한 Macmillan은 앨리스 의출판사이므로많은다양한일반적개념들과연결되는미국보다검색어 앨리스 에밀접한관련이있는개념이다. 그러므로기존페이지랭크와반대로 Macmillan을미국보다상위랭크로계산한시맨틱링크기반페이지랭크가더의미있는중요도판단결과를제시했음을알수있다. 표 1 출판사와미국문서에대한순위결과비교 그림 7 결과문서개수별관련문서개수비교 문서 페이지랭크 시맨틱링크기반페이지랭크 Macmillan 33위 15위 미국 5위 16위
시맨틱링크를사용한페이지순위알고리즘개선 847 표 2 출판사와미국문서내자원에대한비교 문서문서내자원자원랭크 Macmillan macillan 0.659 publish company 0.468 시맨틱링크기반페이지랭크 1.127 미국 unitedstate 1.107 1.107 5. 결론및향후연구 온톨로지언어인 RDF는의미있는연결관계를가진트리플로자원을정의할수있다. 본논문에서는이러한특성을활용해페이지랭크를개선하였다. 시맨틱링크기반페이지랭크는웹문서가얼마나중요한자원을많이가지고있냐에따라중요도를결정하므로기존페이지랭크에비해상대적으로의미있는랭킹결과를도출할수있다. 또한기존페이지랭크는링크기반의중요도계산으로인해상위순위의웹문서임에도불구하고사용자가원하는내용이없을수있는상황이발생할수있지만, 시맨틱링크기반페이지랭크는자원에대한랭킹을기반으로웹문서의랭킹을결정하므로상위순위에있는웹문서는의미있는자원을가진내용을사용자에게제공하는것을보장해준다. 향후연구로는의미를가진연결의가중치를계산하는방법을독자적으로개발할계획이다. 그리고웹문서에자동으로 RDFa 주석을다는기술을사용해 RDFa 가정의되지않은웹문서에도시맨틱링크기반페이지랭크를사용할수있도록기능을개선하고자한다. 참고문헌 [1] S. Brin, L. Page, "The Anatomy of a Large-scale Hypertextual Web Search Engine," Computer Networks and ISDN Systems, vol.30, no.1-7, pp.107-117, 1998. [2] W. Xing, A. Ghorbani, "Weighted PageRank Algorithm," In proceedings of the 2nd Annual Conference on Communication Networks & Services Research, pp.305-314, 2004. [3] K. Stein, C. Hess, "Information Retrieval in Trust- Enhanced Document Networks," Lecture Notes in Computer Science, vol.4289, pp.65-81, 2006. [4] P. Sharma, D. Tyagi, P. Bhadana, "Weighted Page Content Rank for Ordering Web Search Result," International Journal of Engineering Science and Technology, vol.2, no.12, pp.7301-7310, 2010. [5] RDFa Taskforce, RDFa-W3C Semantic Web Deployment Wiki, http://www.w3.org/2006/07/swd/ wiki/rdfa.html [6] RDF Working Group, Resource Description Framework, W3C, http://www.w3.org/rdf [7] R. De Virgilio, F. Frasincar, W. Hop, S. Lachner, "A Reverse Engineering Approach for Automatic Annotation of Web Pages," Multimedia Tools and Applications, Published online, 2011. [8] M. Duma, "RDFa Editor for Ontological Annotation," In proceedings of the Student Research Workshop associated with RANLP, pp.54-59, 2011. [9] N. Toupikov, J. Umbrich, R. Delbru, M. Hausenblas, G. Tummarello, "DING! Dataset Ranking Using Formal Descriptions," In Proceedings of the WWW 2009 Workshop on Linked Data on the Web, 2009. 전희국 2004 년동국대학교컴퓨터공학과학사 2007 년고려대학교전자컴퓨터공학과석사. 2011 년 ~ 현재서울대학교컴퓨터공학부박사과정재학중. 관심분야는데이터베이스, 시맨틱웹, 온톨로지, 빅데이터 임동혁 2003년고려대학교컴퓨터교육과학사 2005년서울대학교컴퓨터공학부석사 2011년서울대학교컴퓨터공학부박사 2012년서울대학교치학연구소선임연구원. 2012년~현재서울대학교컴퓨터공학부박사후과정. 관심분야는데이터베이스, 시맨틱웹, 온톨로지, 빅데이터 김형주정보과학회논문지 : 컴퓨팅의실제및레터제 39 권제 4 호참조