질의어단위프로파일링을이용한북마크기반개인화검색 153 질의어단위프로파일링을이용한북마크기반개인화검색 (Bookmark-Based Personalized Search through Query-Level User Profiling) 김현지 배동환 (Hyun Ji Kim) (Dong Hwan Bae) 고민삼 이문용 (Minsam Ko) (Mun Yong Yi) 요약본논문에서는개인화검색시사용자의단일프로파일이개인의다양한정보요구를만족시키지못하는문제를개선하고자, 질의어에따라프로파일을조정하는방법을제안한다. 특히, 제안하는방법은질의어에관해사용자가중요하게생각하는단어들을북마크데이터로부터추출하여프로파일조정에활용한다. 유명북마크서비스제공자인 CiteULike 의데이터를활용한실험에서, 본연구에서제안하는방법이단일프로파일에기반한기존의방법보다더뛰어난개인화검색결과를제공함을확인할수있었다. 키워드 : 사용자프로파일, 개인화검색, 북마크 Abstract The approach of a single user profiling for 본연구는 2011년도정부 ( 교육과학기술부 ) 의재원으로한국연구재단의지원을받아수행된연구임 (No. 2011-0029185) 이논문은 2012 한국컴퓨터종합학술대회에서 질의어단위사용자프로파일을이용한북마크기반개인화검색방법 의제목으로발표된논문을확장한것임 학생회원 : KAIST 지식서비스공학과 jacehyun@gmail.com bdhwan@gmail.com minsam.ko@gmail.com 정회원 : KAIST 지식서비스공학과교수 munyi@kaist.ac.kr (Corresponding author임 ) 논문접수 : 2012년 8월 20일심사완료 : 2012년 11월 19일 CopyrightC2013 한국정보과학회 ː개인목적이나교육목적인경우, 이저작물의전체또는일부에대한복사본혹은디지털사본의제작을허가합니다. 이때, 사본은상업적수단으로사용할수없으며첫페이지에본문구와출처를반드시명시해야합니다. 이외의목적으로복제, 배포, 출판, 전송등모든유형의사용행위를하는경우에대하여는사전에허가를얻고비용을지불해야합니다. 정보과학회논문지 : 컴퓨팅의실제및레터제19권제3호 (2013.3) personalized search does not satisfy a person s diverse information needs. This paper presents a new approach, query-level user profiling, for personalized search in order to improve the situation. Our proposed method extracts query-related words from each user s bookmarking data and makes use of them in the process of adjusting the user s profile. We tested our approach using the field data obtained from CiteULike, a popular bookmarking service provider on the Web. Our experiment results show that the proposed approach through querylevel user profiling outperforms the existing personalized search method based on single user profiling. Keywords: user profile, personalized search, bookmark 1. 서론 최근개인의정보요구에맞춤화된검색결과를제공하는개인화검색이주목을받고있다 [1]. 개인화검색은같은질의어라해도개인의관심사에따라다른검색결과를반환한다. 일반적으로개인화검색은 (1) 사용자의관심사를표현하는단어들로구성된사용자프로파일을만들고, (2) 해당프로파일에서입력된질의어와관련된문서들의가중치를높여주는재정렬순서로진행된다. 대부분의개인화검색방법들은사용자별로하나의프로파일만을만들어사용한다. 그러나여러영역에걸친사용자의다양한관심사는단일프로파일에모두표현하기에한계가있다. 예를들어, 오랜기간데이터마이닝에관심있던사람이새롭게 HCI에관심을가지게되었다고하자. 데이터마이닝에관한사용자의행동기록이많기때문에, 프로파일은데이터마이닝을중심으로구축되어있을것이다. 그결과, HCI 관련단어들은상대적으로프로파일에서소외되고, 결국 HCI 관련검색에대한개인화효과는떨어지게된다. 본논문에서우리는단일프로파일에기반한방법의문제를개선하기위해질의어에따라프로파일을조정하여개인화검색에사용하는방법을제안한다. 사용자가질의어를입력하면, 제안하는방법은입력된질의어와연관하여사용자가중요하게생각하는단어들이개인화과정에서더중요하게고려되도록프로파일을조정한다. 따라서원래의프로파일에서는상대적으로소외되었던단어들도특정질의어에대해서는더중요하게고려될수있게된다. ( 본논문에서질의어와관련하여사용자가중요하게생각하는단어는 질의어관련단어 라표기되고, 조정된프로파일은 질의어단위프로파일 이라표기된다.) 특히, 제안하는방법은질의어관련단어를추출하기
154 정보과학회논문지 : 컴퓨팅의실제및레터제 19 권제 3 호 (2013.3) 위해북마크데이터를사용한다. 북마크데이터에서사용자, 태그, 그리고문서를각각사용자, 질의어, 그리고사용자에게적합한문서로가정한다. 이가정에기반하여어떤사용자가단어 A 로태그를단문서들로부터단어들을추출하고, 추출된단어들을단어 A 에대한이사용자의질의어관련단어들로사용한다. 북마크는사용자의관심사를직접적으로표현하기때문에기존의검색방법들 [2,3] 에서사용된클릭데이터보다정확하게사용자의의도를알수있다. 우리는유명한북마크서비스인 CiteULike의데이터를사용하여제안하는방법의성능을기존방법과비교해보았다. 실험결과는제안하는방법이단일프로파일에기반한기존의개인화검색방법보다더뛰어난성능을가진것을보여준다. 2. 관련연구 2.1 사용자프로파일개인화검색에서프로파일은질의어에대한사용자의정보요구를알아내는데사용된다. 질의어들은길이가짧고 [4] 그뜻이모호한경우 [5] 가많다. 따라서사용자의정보요구에맞는개인화검색을위해서는정확한프로파일을구성하는것이필수이다. 그동안프로파일구축을위해클릭 [2,3,6], 북마크 [7], 사회적관계 [8] 등과같은다양한데이터가사용되었다. 본논문이제안하는방법은북마크데이터를활용한다. 북마크데이터는사용자가선호하는문서에단태그들을포함하며, 기존연구들에서는문서의특징과사용자의관심사를알아내는데주로사용되어왔다 [7]. 본논문에서는북마크데이터의태그를사용자가입력할법한질의어로간주하여, 개인화검색을위한질의어단위프로파일을만드는데활용한다. 2.2 질의어단위프로파일많은개인화검색방법이단일프로파일에기반하고있는반면, 클릭데이터로질의어단위프로파일을구축한개인화검색연구들도있었다 [2,3,6]. 이들은검색결과중사용자가클릭한문서들을질의어에적합한문서라가정하고, 이문서들에서추출된단어들을질의어관련단어들로사용하였다. 하지만클릭한문서전부가사용자에게적합한문서는아닐수있다 [2]. 단순히문서의검색순위가높아서클릭했을수도있고, 제목과스니펫 (Snippet) 을보고클릭했으나본문은만족스럽지않았을수도있다. 본연구는사용자가본문을직접확인하고저장한북마크를사용하기때문에, 보다정확한질의어단위프로파일을만들수있다. 2.3 검색결과의재정렬 프로파일에기반한검색결과재정렬방법에는크게콘텐트기반방법과협업기반방법이있다. 먼저콘텐트기반방법은개인의프로파일과문서사이간유사도에따라검색된문서의순위를결정한다. 프로파일과문서를비교하기위해 Chirita[9] 는문서에대한 Open Directory Project(ODP) 데이터를사용했고, Tan[3] 은통계적언어모델을사용했다. 반면협업기반방법은사용자들의프로파일간유사도에근거하여, 나와비슷한관심을가지는사람들이만족한정도에따라문서들의검색순위를결정한다. 대표적으로는추천시스템에서사용하는협업필터링을통해검색순위를결정하는방법 [10] 과기존협업필터링에질의어를더고려한방법인 CubeSVD[6] 가있다. 본논문이제안하는질의어단위프로파일은두방법모두에쉽게적용될수있으나, 본논문에서는계산비용이상대적으로적은콘텐트기반방법에먼저적용해보았다. 앞으로질의어단위프로파일을협업기반방법에도적용해볼예정이다. 3. 질의어단위사용자프로파일을이용한북마크기반개인화검색방법 3.1 전체수행과정그림 1은제안하는방법이수행되는전체과정을보여준다. 그림 1 제안하는방법의전체흐름도제안하는방법은 문서모델링, 사용자프로파일구축, 질의어단위프로파일구축, 그리고 검색결과재정렬 의네단계로진행된다. 다음장에서는각과정에대한자세한설명이이어진다. 3.2 문서모델링먼저문서들을연산가능한형태로변환하기위해문서모델링을수행한다. 이과정을통해문서에서중요한단어들이뽑혀지고각문서가하나의단어벡터형태로변환된다. 단어벡터는문서를표현하는단어들과그단어들이해당문서에서중요한정도를나타내는가중치들로구성된다. 문서를표현하는단어들은문서의본문이나서지정보를이용해도되지만, 본논문에서는문서에대해
질의어단위프로파일링을이용한북마크기반개인화검색 155 사람들이단모든태그들을사용한다. 단어들의가중치로는 tf-idf (Term Frequency - Inverse Document Frequency) 에의해계산된값을사용한다. 식 (1) 은문서 d에대한단어벡터를나타낸다. t n 은문서 d에포함된단어들이며, n은문서 d가포함하고있는단어들의총수를의미한다. tfidf tn d는 d에서 t n 이가지는 tf-idf 값을나타낸다. (1) 이렇게모델링된문서들은사용자프로파일구축및검색결과재정렬과정의기본재료가된다. 3.2 사용자프로파일구성이어서사용자의전반적인관심사및성향을표현하는사용자프로파일을구축한다. 전체사용자프로파일구축과정없이질의어가입력되었을때질의어단위프로파일을동적으로구축하는것도가능하다. 하지만미리전체사용자프로파일을만들어놓으면질의어입력때마다프로파일을다시구축할필요없이미리구축해놓은프로파일에서질의어와관련된단어들의가중치들만조정하면되기때문에연산효율이향상되는장점이있다. 사용자프로파일은사용자가태그를단문서들에등장한단어들의가중치들이합쳐져하나의단어벡터로표현된다. 결과적으로사용자가태그를단문서들에서자주발견되는단어일수록더높은가중치를가지게된다. 식 (2) 는사용자 u의프로파일 P u 를나타낸다. (2) 그리고다음식 (3) 을통해사용자 u의프로파일에서단어 t의가중치 w t,u 를계산한다. 식 (3) 에서 D u 는사용자 u의북마크목록에있는모든문서들의집합이다. (3) 예를들어 Machine Learning과 HCI분야에관심이있는사용자 u 1 의북마크목록은표 1과같을수있다. 북마크목록에기반하여 u 1 에대한사용자프로파일 은 {(classification, 5.5), (SVM, 1.1), (Bayes, 1.2), (interaction, 6.3), (usability, 1.8), (interface, 1.4)} 과같은형태로구축될것이다. 그결과프로파일내에서 Machine Learning 과 HCI 관련단어들이비슷한가중치를가지게된다. 표 1 사용자북마크목록예시 문서단어벡터태그 d 1 {(classification,3.2),, (SVM,1.1)} Machine Learning d 2 {(classification,2.3),, (Bayes,1.2)} Machine Learning d 3 {(interaction,2.5),, (usability 1.8)} HCI d 4 {(interaction,3.8),, (interface,1.4)} HCI 3.3 질의어단위사용자프로파일구성사용자가검색을위해질의어를입력하면, 사용자의프로파일은질의어단위프로파일로변환된다. 이과정을통해프로파일내질의어관련단어들의가중치가높아지고, 검색순위결정시이단어들이더중요하게고려된다. 질의어관련단어는사용자의북마크데이터에서추출된다. 사용자가특정태그를단문서들을, 그태그가질의어로사용되었을때이사용자에게적합한문서로여긴다. 그리고질의어에적합한문서들에등장한단어들을질의어관련단어로사용한다. 식 (4) 는사 용자 u의질의어 q에대한질의어단위프로파일 P u q 을나타낸다. (4) w t u q는질의어단위프로파일내단어들의조정된가중치를의미하며식 (5) 를통해계산된다. (5) 식 (5) 에서 d f (t, D u,q) 는사용자 u가질의어 q를태그로단문서집합 D u,q 에서단어 t가등장한문서의수를반환하는함수다. 는 D u,q 에서한번도등장하지않는단어들 ( 즉, df(t, D u,q =0) 이질의어단위프로파일에서가중치가 0이되어완전히제외되는것을방지하기위한변수이다. 질의어관련단어가아닌단어들도전체적으로봤을때사용자에게의미가있을수있다. 따라서단어들을완전히제외하는것보다는가중치를상대적으로낮추지만질의어관련단어들과함께사용하여사용자의전반적인관심사가같이고려되도록하였다. 값이커질수록프로파일내에서질의어관련단어들의영향력이높아지며, 반대로이값이 0에가까울수록프로파일이질의어에맞게조정되는효과가미비해진다. 본논문에서는이값을 0.5로사용하였다. 그리고만약입력된질의어가사용자의태그목록에존재하지않을경우에는질의어단위프로파일을구축하는것이불가능하기때문에조정과정없이처음에구성한사용자프로파일을다음단계에서그대로사용한다. 위의예제 ( 표 1) 의사용자 u1이질의어로 HCI를사용했다면, 질의어단위프로파일에서는 HCI로태그된문서들에서나온단어들인 interaction, usability, interface 등에더높은가중치가부여된다. 원래전체프로파일에서는 machine learning에대한단어들과 HCI에대한단어들이비슷한가중치로프로파일이구성되었지만질의어 HCI에대한프로파일은 HCI에구체화되어있어사용자 u1의 HCI에대한관심사를더잘표현하게된다. 3.4 검색결과재조정마지막으로일반검색방법을통해반환된, 입력된질의어에적합한문서들을, 질의어단위프로파일 P u q
156 정보과학회논문지 : 컴퓨팅의실제및레터제 19 권제 3 호 (2013.3) 과비교하여보다유사한문서를상위검색순위에올려준다. 각문서들과질의어단위프로파일간의코사인유사도 (Cosine similarity) 를계산하여유사도값이높은문서를상위순위에놓는다. 식 (6) 은문서 d와사용자 u 의질의어 q에대한질의어단위프로파일 P * u,q 간의유사도를구하는식이다. Sim d P 4. 실험결과및분석 (6) 4.1 실험데이터우리는 2011년에생성된 CiteULike의북마크데이터를실험에사용하였다. 전체데이터의양이방대하기때문에실험세팅및결과해석이용이하도록컴퓨터공학관련태그를많이사용한사람들을평가대상으로샘플링했다. 이샘플링을위해컴퓨터공학의주제어들 ( social network, semantic, machine learning, mobile ) 을선택하였고, 주제어별로주제어를태그로많이사용한상위 30명씩을선택했다. 중복선택된경우를제외하여총 109명의사용자들이선택되었다. 선택된사용자들은 44,038개문서들에 160,374개태그들을달았다. 각사용자의북마크들은북마크된시간에따라반반씩나누어져학습데이터와평가데이터로사용되었다. 4.2 평가절차평가는다음의순서로진행되었다. 먼저사용자별로학습데이터를사용해프로파일을구성하였다. 그리고사용자별로각평가질의어에대해 CiteULike의일반검색이반환한문서들중상위 50개문서들을개인화방법에따라재정렬하였다. 평가질의어로는 10명이상의사용자들이사용한태그들 ( 총 216 단어 ) 을사용하였다. 마지막으로평가척도를사용해재정렬된검색결과를점수화하여, 사용자에게적합한문서가얼마나상위순위에있는지를보았다. 평가척도로는 MRR, NDCG, 그리고 Precision이사 용되었다. 세척도모두적합한문서가높은순위에있을수록높은수치를가진다. NDCG와 Precision은검색결과중상위 5개문서에대해측정하였고, 각각 NDCG@5와 P@5로표기한다. 우리는문서가사용자에게적합한지여부를판단하기위하여 회상 과 발견 이라는두기준을정의하였다. 회상은사용자가전에본적합한문서를다시찾은것을의미한다. 회상의관점에서는검색된문서들가운데사용자의학습데이터에존재하는문서들이사용자에게 적합한문서로판단된다. 그리고발견은사용자가새롭게적합한문서를찾은것을의미한다. 발견의관점에서는검색된문서들가운데사용자의평가데이터에존재하는문서들이사용자에게적합한문서로판단된다. 4.3 비교방법우리는두가지비교방법들을준비했다. 첫번째비교방법은 CiteULike에서제공하는일반검색방법이다 ( 베이스라인 ). 그리고다른하나는단일프로파일기반개인화검색방법이다 ( 단일프로파일방법 ). 단일프로파일방법은질의어를고려하지않고사용자당하나의프로파일을사용한다. 질의어에따라프로파일을조정하는단계를제외하고는제안하는방법과같은과정을따른다. 4.4 실험결과실험결과는제안하는방법이회상과발견모두에대해서비교하는기존의방법들에비해더뛰어난성능을가진것을보여준다 ( 그림 2, 그림 3, 그리고그림 4 참고 ). 특히회상에대한평가에서큰격차를보였다. 제안하는방법은 회상 면에서베이스라인의성능을 8 1%~191% 향상시켰고, 단일프로파일방법의성능을 16%~26% 향상시켰다. 단일프로파일방법도베이스라그림 2 Mean Reciprocal Rank (MRR) 그림 3 NDCG@5
질의어단위프로파일링을이용한북마크기반개인화검색 157 그림 4 Precision@5 인에비해향상된결과를보여줬지만, 제안하는방법에비해서는성능이떨어지는것을볼수있었다. 발견에대한평가에서도제안하는방법은가장좋은성능을보였다. 하지만회상에비해성능향상이작았다. 본논문에서사용자프로파일은한사용자의과거기록만을참고하여만들어졌기때문에개인화검색시그사람의과거기록에편향된결과를보여주기쉽다. 우리는이러한점을보완하기위하여다른사람들과의관계성을고려하여질의어단위프로파일을확장하는방법에대해연구하고있다. Web Search Engine Query Log," ACM SIGIR Forum, vol.33, Issue1, 1999. [5] R. Krovetz, W. B. Croft, "Lexical Ambiguity and Information Retrieval," Information Systems, vol.10, Issue2, 1992. [6] J. Sun, et al., "CUBESVD: a Novel Approach to Personalized Web Search," in proc. of WWW, 2005. [7] D. Vallet, et. al., "Exploiting Social Tagging Profiles to Personalize Web Search," in proc. of FQAS, 2009. [8] D. Carmel, et al., "Personalized Social Search Based on the User s Socizal Network," in proc. of CIKM, 2009. [9] P. A. Chirita, et al., "Using ODP Metadata to Personalize Search," in proc. of SIGIR, 2005. [10] K. Sugiyama, et al., "User-Oriented Adaptive Web Information Retrieval Based on Implicit Observations," in proc. of APWeb, 2004. 5. 결론및향후연구 본논문은북마크데이터를이용해형성한질의어단위프로파일링을개인화검색에적용하는방법을제안하였다. CiteULike 데이터를사용한성능평가실험을통해단일프로파일에비하여개인화검색의성능을향상시킨것을확인하였다. 우리사회가통섭의시대로접어들면서다양한영역에관심을가지는사람들의수는날로늘어나고있다. 개인의다양한정보요구들을잘반영하는질의어단위프로파일은개인화검색은물론추천시스템이나협업시스템등에매우유용할것이다. 참고문헌 [1] N. J. Belkin, "Some(what) Grand Challenges for Information Retrieval," ACM SIGIR Forum, vol.42, Issue1, 2008. [2] Z. Dou, et al., "Evaluating the Effectiveness of Personalized Web Search," IEEE Transactions on Knowledge and Data Engineering, vol.21, Issue8, 2009. [3] B. Tan, X. Shen, C. Zhai, "Mining Long-Term Search History to Improve Search Accuracy," in proc. of KDD, 2006. [4] C. Silverstein, et al., "Analysis of a Very Large