DBPIA-NURIMEDIA

Size: px

Start display at page:

Download "DBPIA-NURIMEDIA"

희령 허
5 years ago
Views:

1 ISSN X(Print) / ISSN (Online) Journal of KIISE, Vol. 41, No. 12, pp , 질의어의근접성정보및그래프프로파일링기법을이용한태그기반개인화검색 (Exploiting Query Proximity and Graph Profiling Method for Tag-based Personalized Search in Folksonomy) 한기준 장진철 이문용 (Keejun Han) (Jincheul Jang) (Mun Yong Yi) 요약최근폭소노미라고불리는데이터들이사용자의의도파악및흥미를분석하는데에매우유용하게쓰이고있다. 본논문은폭소노미데이터를이용한개인화검색에서, 기존의벡터기반프로파일링및유사도계산모델의한계점을지적하고, 이러한한계를극복하기위한방법으로그래프기반의프로파일링및유사도계산법을제안한다. 최종적으로그래프기반의개인화검색모델에추가적으로질의어간의근접성까지고려한보다발전된개인화검색기법을제안하였다. 본연구에서는복수의데이터셋을사용한객관적인성능평가실험을통해제안한모델이기존의벡터스페이스모델에기반한프로파일링기법및프로파일간의유사도계산기법보다더뛰어난개인화검색결과를제공함을확인하였다. 또한추가적인파라미터실험을통하여, 제안하는모델은어떠한형태의데이터셋에도쉽게적용가능함을보였다. 키워드 : 협업적태깅시스템, 개인화검색, 사용자프로파일, 문서프로파일 Abstract Folksonomy data, which is derived from social tagging systems, is a useful source for understanding a user s intention and interest. Using the folksonomy data, it is possible to create an accurate user profile which can be utilized to build a personalized search system. However there are limitations in some of the traditional methods such as Vector Space Model(VSM) for user profiling and similarity computation. This paper suggests a novel method with graph-based user and document profile which uses the proximity information of query terms to improve personalized search. We demonstrate the performance of the suggested method by comparing its performance with several state-of-the-art VSM based personalization models in two different folksonomy datasets. The results show that the proposed model constantly outperforms the other state-of-the-art personalization models. Furthermore, the parameter sensitivity results show that the proposed model is parameter-free in that it is not affected by the idiosyncratic nature of datasets. Keywords: collaborative tagging systems, personalized search, user profile, document profile 본연구는 2014년도정부 ( 미래창조과학부 ) 의재원으로한국연구재단의지원을받아수행된연구임 (No ) 이논문은 2014 한국컴퓨터종합학술대회에서 질의어의근접성정보및그래프프로파일링기법을이용한태그기반개인화검색 의제목으로발표된논문을확장한것임 학생회원 : 한국과학기술원지식서비스공학과 keejun.han@kaist.ac.kr 비회원 : 한국과학기술원지식서비스공학과 jcjang@kaist.ac.kr 종신회원 : 한국과학기술원지식서비스공학과교수 (KAIST) munyi@kaist.ac.kr (Corresponding author 임 ) 논문접수 : 2014년 7월 15일 (Received 15 July 2014) 논문수정 : 2014년 9월 15일 (Revised 15 September 2014) 심사완료 : 2014년 9월 16일 (Accepted 16 September 2014) CopyrightC2014 한국정보과학회ː 개인목적이나교육목적인경우, 이저작물의전체또는일부에대한복사본혹은디지털사본의제작을허가합니다. 이때, 사본은상업적수단으로사용할수없으며첫페이지에본문구와출처를반드시명시해야합니다. 이외의목적으로복제, 배포, 출판, 전송등모든유형의사용행위를하는경우에대하여는사전에허가를얻고비용을지불해야합니다. 정보과학회논문지제41권제12호 ( )

2 1118 정보과학회논문지제 41 권제 12 호 ( ) 1. 서론개인화검색은동일한질의어에대해사용자의선호도에따라서로다른분석결과를제공하는검색기법으로다양한개인의정보요구에맞춤화된검색결과를제공하여사용자의검색만족도를높이는기법이다 [1]. 개인화검색의일반적인수행과정은다음과같다. (1) 사용자의관심사를표현하는단어들로구성된사용자프로파일을구축하고, (2) 문서에대해설명하는단어들로구성된문서프로파일을구축한뒤, (3) 이를바탕으로사용자및문서프로파일의유사도를측정하여그유사도가높은문서들의검색순위를높여주는재정렬순서로진행된다. 따라서, 효과적인개인화검색을위해서는각프로파일을이루는단어들의품질이중요하며, 프로파일간의유사도측정기법이정교할수록그개인화검색의성능은증가하게된다. 본논문에서는사용자및문서프로파일을구성하는단어셋을폭소노미에의해형성된사용자태그정보를활용하여구축하고자한다. 폭소노미는다중의사용자가특정콘텐츠에협업적으로태그를달아그콘텐츠의성격을규명하고분류를돕는행위또는시스템을일컫는말로협업적태깅이라고도불린다. 이러한폭소노미데이터를축적하여활용하는서비스에는여러종류가있다. 대표적으로사용자가흥미있는주제를몇개의단어로표현하여나타내는 Del.icio.us, 사용자가좋아하는노래를태그하는 Last.fm, 사용자가좋아하는사진을업로드하거나태그로표현할수있는 Flicker, 해당영화에대해사용자들이영화를표현하는태그를입력할수있게하는 IMDB 등의서비스에서이러한데이터를활발히이용하고있다. 해외는물론국내에서도이러한태그기능을활용하는서비스들이증가하고있다. 이렇게서비스를이용하여사용자가직접남긴태그데이터, 즉폭소노미데이터는사용자의의도를명시적으로파악할수있으며문서에달린태그를분석하면해당문서를보다효과적으로설명하는데에사용될수있음이알려져있다 [2]. 또한이러한폭소노미데이터를활용하면기존검색성능의향상뿐만이아니라 [3], 개인화검색의성능향상에도기여할수있다 [4]. 일반적인폭소노미데이터를활용한개인화검색에서, 사용자와문서의프로파일은사용자가직접쓴태그와각태그의가중치들의집합으로구성된벡터로표현된다. 이때, 각태그의가중치들은 TF(term frequency)[5], TF-IDF(term frequency-inverse document frequency) [4], BM25[6] 등의방법으로계산된다. 하지만, 이러한기술들은프로파일을구성하는각태그사이의근접성 (proximity) 정보를고려하지않아질의어에대한사용 자의정보요구를정확하게파악하는것에한계를지닌다. 대부분의사용자질의어들은그길이가짧고, 뜻이모호하여, 질의어자체만이아니라주어진질의어간의숨겨진관계를분석하여정보검색요구에반영하면사용자의검색만족도를향상시킬수있다 [7]. 따라서본논문에서우리는사용자와문서의프로파일을기존의벡터형태가아닌그래프형태로표현하고이를개인화검색에이용하는방법을제안한다. 그래프형태의프로파일링기법은기존의기법과는달리단어간의시맨틱정보를표현할수있어각단어간의거리정보를측정할수있게된다. 이는주어진질의어들이해당프로파일에서어떠한관계를지니고있는지파악하는단초를제공하여최종적으로근접성정보를검색에반영할수있도록해준다. 하지만이러한그래프기반의접근법은기존관련연구에서제안된프로파일간의유사도를계산하는방식에도변화가필요함을암시한다. 기존의관련연구에서는벡터형태로이루어진두프로파일간의유사도를계산하기위해두벡터사이의유사도를측정하는코사인유사도 [4], 스칼라유사도 [6] 등의방법을사용했으나, 본연구에서제안하는프로파일은벡터기반이아닌그래프기반이므로, 두그래프간의유사도를측정하는새로운유사도측정법이필요하다. 따라서우리가제안하는방법은 (1) 질의어와관련된문서들이반환된초기검색결과에서 (2) 반환된문서의프로파일과해당사용자의프로파일이얼마나유사한지그래프기반유사도기법으로계산하고, (3) 이를최종적으로문서내프로파일에서해당질의어들이얼마나긴밀한관계를맺고있는지측정한근접성값과융합하여최종적으로개인화된검색결과를사용자에게제공한다. 본연구는사용자및문서프로파일을모두그래프로나타내며, 특히문서내에위치한질의어의근접성정보를검색결과의성능향상에활용하는것으로, 폭소노미데이터를활용하여태그기반의개인화검색에서처음으로제안하는그래프기반의개인화검색방법으로기존연구와비교하여독창성이있다. 본연구에서제안한기법은기존의개인화방법들과비교하였을때월등한성능향상을보였으며, 또한질의어간의근접성정보를활용하여제안하는방법에결합하면그개인화검색성능이일관되게진보하는것을복수개의폭소노미데이터셋상에서검증하였다. 2. 관련연구본장에서는, 본연구와관련된여러관련문헌들을 1) 개인화검색 2) 폭소노미를이용한개인화검색으로분류하여소개한다. 이어지는본장의세부부분은해당

3 질의어의근접성정보및그래프프로파일링기법을이용한태그기반개인화검색 1119 분류에따른관련문헌들을소개한다. 2.1 개인화검색현재개인화검색은크게두개의연구방향으로나누어져있는데, 첫번째는질의어확장 (Query Expansion) 방법이며두번째는검색결과재정렬 (Result Reranking) 이다 [1]. 본논문에서는검색결과재정렬개인화방식을활용하여연구를진행하였다. 질의어확장은사용자에의해입력된초기질의어를수정하거나검색결과향상을위해새로운질의어를시스템에서추가하는방법이다. 또한, 사용자의특성을추가적으로반영하기위해초기질의어의가중치를조정하는방식도크게질의어확장에해당한다고볼수있다 [8]. 그에반해검색결과재정렬은질의어와문서와의적합성 (Relevance) 만이반영된초기의결과가주어졌을때, 각각의사용자선호도를반영하기위해초기검색결과를재정렬하는방법이다. 대부분의개인화재정렬방법들은다양한사용자데이터로부터개인의선호도를추출하여이를바탕으로사용자프로파일을구축하고, 해당프로파일에적합한문서들을상위에올리고, 해당프로파일과관련이없는문서를초기검색결과에서제외하는과정으로개인화검색을진행한다. 관련문헌 [9] 에서는 ODP(Open Directory Project) 구조를이용하여사용자와문서를벡터로표현하여두벡터간의거리를측정하여개인화검색을수행하는방식을제안하였고, 관련문헌 [10] 에서는통계적언어모델을사용하기도하였다. 또한, 관련문헌 [11] 에서는해당사용자의과거데이터만이아니라사용자와유사한행태를가지는사용자들의데이터까지추가적으로고려하기위해추천시스템에서주로사용되는협업필터링 (Collaborative Filtering) 을활용하여사용자프로파일을구축하는방식이제안되기도하였으며, 관련문헌 [12] 에서는이차행렬을특정한구조로분해하는기존의특이값분해방법 (Singular Vector Decomposition 혹은 SVD) 을사용자, 질의어, 문서의세가지특성을반영할수있는삼차행렬에서사용할수있게확장한 CubeSVD 방식을도입하여개인화검색의성능을향상시켰다. 관련문헌 [13] 에서는이러한다양한검색기법들을실제사용자들이축적한대용량로그데이터를활용하여검증함으로써, 이러한검색기법들이실제서비스에서도사용자의검색만족도향상에기여할수있음을보였다. 2.2 폭소노미를활용한개인화검색태그기능을제공하는서비스들이최근증가함에따라, 이러한폭소노미데이터를개인화검색에활용하는방식이최근증가하였다. 관련문헌 [5] 는사용자와문서의태그들중에서가장많이사용된태그정보 (TF) 를활용하여사용자와문서의벡터프로파일을구축하고, 이를 바탕으로초기의검색결과를재정렬하는방식을제안하였다. 이에반하여, 관련문헌 [4] 에서는사용자프로파일을구성하는각태그의가중치를 TF-IDF에기반하여제안된 term frequency-inverse user frequency (TF-IUF) 방법을통하여다음과같이계산하였다. (1) 식 (1) 에서 tf는사용자가해당태그를사용한횟수이며, N은총사용자의수, n t 는해당태그를사용한사용자의수이다. 이와유사하게문서프로파일도 TF-IDF를활용하여 term frequency-inverse resource frequency (TF-IRF) 로나타낼수있다. 또한, 관련문헌 [6] 에서는기존의 BM25 랭킹모델을개인화검색에활용하기위해사용자프로파일내각태그의가중치를다음과같이계산하였다. (2) 식 (2) 에서 k 1 과 b는 2와 0.75로정의된파라미터값이며, u l 은사용자프로파일벡터의길이, avgu l 은전체사용자프로파일벡터길이의평균을의미한다. 이와유사하게문서프로파일도 BM25를이용하여표현할수있다. 관련문헌 [6] 은벡터스페이스기반의 TF-IDF와통계적기법인 BM25를동시에활용하여개인화검색의성능을보다더향상시키기위한하이브리드기법을제안하였다. 최근에는기존의제안된 TF, TF-IDF, BM25보다더발전된모델인 Normalized Term Frequency (NTF) 모델이관련문헌 [14] 에서제안되었다. NTF 모델에서사용자프로파일내태그 t x 의가중치는다음과같이계산된다. (3) 식 (3) 에서 N c 는사용자 c 에의하여태그된문서들의개수이고, N c,x 는사용자 c 가태그 t x 를활용한횟수를의미한다. 이와유사하게문서의프로파일도 NTF를활용하여계산된다. 이와같은기법으로계산된사용자와문서의벡터프로파일은코사인유사도 [4] 나, 코사인유사도에기반을둔여러벡터기반유사도계산기법을활용하여 [6,14], 두프로파일이어느정도유사한지계산하게된다. 만약두프로파일간의유사도가높다면해당문서는사용자가주로관심있는주제들과유사한문서일확률이높

4 1120 정보과학회논문지제 41 권제 12 호 ( ) 을것이며, 반대로두프로파일간유사도가낮다면해당문서는사용자의질의어와관련이높은문서라고할지라도, 사용자가관심있는주제와는관련성이상대적으로떨어질수있음을의미한다. 관련연구 [15] 은그래프기반의유사도측정방식을개인화검색에활용한사례이다. 본연구에서는여러사용자에의해협업적으로구축된폭소노미데이터와질의어의근접성정보를추가로활용하여그래프기반개인화검색의성능을향상시키고자하였다. 3. 연구동기 본장에서는기존폭소노미데이터를활용한개인화검색기법의한계점을분석함과동시에이를바탕으로본연구에서제안하는기법과기존기법과의차이점을기술한다. 3.1 사용자및문서프로파일구축상기에서언급한바와같이, 기존폭소노미기반의개인화검색에서자주사용되는기법인 TF, TF-IDF, BM25등은사용자가남긴태그와그태그의가중치만을고려하여사용자프로파일을구축한다. 또한, 여러사용자가리소스에남긴태그들과, 그태그들의가중치를고려하여리소스프로파일을구축한다. 그러나이러한방법은실제사용자의정보검색요구와맞지않는경우가존재한다. 예를들어, 영화검색및태깅서비스에서제공되는영화중에는미래를그린공상과학영화이지만가족간의사랑의의미도일정부분담겨있는영화인 A 가있다고가정해볼수있다. 해당영화를시청한사용자들이남긴태그들에기반하여기존검색방식중에서 TF 기반의프로파일방식으로표현된영화 A의프로파일은다음과같다. R A ={( 미래,56),( 과학,36),,( 가족,18),( 사랑,3)} 기존의방식은해당영화에대한상대적인주제를비교적잘설명하고있기는하지만, 각주제들간의관계에대해서는명확하게설명하고있지않다. 이는 A를검색하기위해 미래, 사랑 을질의어로입력할경우해당영화프로파일중사랑의가중치가크지않기때문에최종검색결과에서 A가상위에검색될확률을감소시키는요인이된다. 이는유사한기법인 TF-IDF, NTF 등에도적용되며, BM25 역시 TF와 IDF값을변수로포함하기에동일한한계를지닌다. 이에반하여, 본연구에서제안하는방법은기존기술과는달리사용자및리소스를태그기반의그래프로표현한다. 이를통하여표현된그래프기반의영화 A의프로파일을이용하면, 사랑 의가중치가적더라도, 또다른질의어인 미래 와어느정도의근접성을가지고있는지파악할수있어, 이정보를통하여해당영화를 검색결과에서상위로올리는재정렬과정이가능해진다. 실제로이러한질의어의근접성을이용하여검색프로세스에반영하게되면전체적인검색성능향상에도움을주는것으로관련문헌 [7,16] 에나타나있다. 사용자및리소스에서그래프기반의프로파일을추출하는방법및근접성정보를고려한재정렬과정은다음장에서자세히설명한다. 3.2 사용자및문서프로파일간유사도계산기존의개인화검색방법에서, 개인화는사용자프로파일과리소스프로파일간의유사도를측정하여이루어진다. 두개의프로파일이벡터형식으로이루어져있기때문에, 이들간의유사도는주로코사인유사도 [4], 스칼라유사도 [6] 등의방법을통하여측정되었다. 이외에도폭소노미데이터의특성을반영한여러측정법들이제안되었으나 [14], 이는모두프로파일의형식을벡터기반으로표현하는것을가정하여제안되어그래프기반프로파일의유사도를비교하는데사용하는것은한계를지닌다. 따라서, 개인화를위해두프로파일간의유사도를계산할때상기설명된기존의유사도기법들을사용하는것은그래프상에서주어진단어간의시맨틱정보및그래프의구조활용이불가능하고, 결국태그의가중치정보만을이용하므로, 그래프기반의프로파일을활용하는방식에는적절하지않다. 이에우리는그래프기반의프로파일에특성화된유사도기법을활용하여사용자와문서간의관련정도를측정하고자한다. 4. 제안하는방법본장에서제안하는방법은크게다음과같은단계로이루어진다. 1) 사용자의질의어와연관된리소스들의초기검색결과를반환한다. 2) 사용자가남긴태그정보를바탕으로사용자의프로파일과초기검색결과내리소스의프로파일을그래프기반으로구축한다. 3) 초기검색결과내리소스들의프로파일과사용자의프로파일간의유사도를계산하고리소스내질의어간의근접성정보와융합하여최종개인화검색결과를반환한다. 이어지는본장의세부부분에서는각과정에대하여자세히설명한다. 4.1 초기검색결과획득개인화검색을위해선먼저, 주어진질의어 q 1, q 2,, q n 의집합 Q와어느정도연관이있는리소스들을찾아초기검색결과를얻어내야한다. 만약이러한과정을거치지않고바로사용자와문서간의선호도만을고려하여최종검색결과를제공한다면사용자의질의어와관련이없는문서도단순히사용자가선호할만한주제라는이유로검색결과에상위에반영되는문제가발생하게된다.

5 질의어의근접성정보및그래프프로파일링기법을이용한태그기반개인화검색 1121 본논문에서는, 기존의여러검색방법중에서도 BM25 모델을질의어와문서간의관련성을측정하여초기결과를반영하는방법으로사용하였다. 이는관련문헌 [7] 에서 BM25 모델이근접성을고려하는모델의베이스라인으로사용하였기때문에, 관련연구와의비슷한실험조건을형성하기위하여해당기법을선정하였다. 주어진문서 r 과주어진질의어집합 Q에관련정도를나타내는점수 NS(Non-personalized Score) 를구하는식은다음과같다. (4) 식 (4) 에서 k 1 과 b 는 2와 0.75로정의된파라미터값이며 r 은문서프로파일벡터의길이, avgdl 은전체문서프로파일벡터길이의평균을의미한다. 최종적으로전체문서들중질의어집합 Q에관한 NS점수가높은문서부터내림차순으로초기검색결과상위에반환되게된다. 이때, 반환된초기의검색결과는사용자의질의어집합 Q문서들간의적합도만을고려하며, 사용자의선호도는해당초기문서랭킹에반영되어있지않다. 따라서, 이초기검색결과를재정렬하여최종개인화가반영된검색결과를사용자에게제공하게된다. 본연구에는상위에위치한 50개의문서를대상으로재정렬을실시하였다. 4.2 사용자및문서프로파일의구축본연구에서구축하려고하는사용자및문서프로파일은그래프형태이다. 예를들어, 어떤사용자 u의프로파일은해당사용자가남긴태그를그래프의노드집합 (Vertex) 으로표현하고, 각태그사이의관계는링크집합 (Edge) 으로표현하여 G u =(V, E) 로나타낸다. 이그래프 G u 는방향성이없고각링크는해당링크에연결된두노드 tag i 와 tag j 가서로얼마나가까운지를나타내는가중치값 w i,j 를갖는그래프이다. 가중치값 w i,j 는다음과같이정의된다. (5) 식 (5) 에서이때 co-occur u 는태그 tag i 와 tag j 가사용자 u에의해함께사용된횟수로, 그횟수가클수록사용자 u는두태그의관련성을높게정의함을의미한다. 또한문서 r 의그래프기반프로파일 G r =(V, E) 에서 V 는리소스 r 에사용자들이남긴태그들을의미하는노드들의집합을의미하며, E 는 V 에속하는점들을연결하는링크로, V 에속하는태그 tag x 와 tag y 의가중치값 w x,y 는다음과같이정의된다. (6) 이때의 co-occur r 은태그 tag i 와 tag j 를리소스 r에 동시에사용한사용자의총수로그수가클수록두태그의관련성이높은것을의미한다. 구축된그래프 G u 와 G r 은계산편의를위하여 V V 차원을갖는정사각형행렬형태로변환되어저장된다. 4.3 사용자및문서프로파일간유사도계산본논문에서는사용자프로파일 G u 와리소스프로파일 G r 간의유사도값인 D(Distance) 를구하기위해 Closeness[17], Maximum Common Subgraph(MCS) [18], Edit Distance[15] 기법들을활용한다. Closeness는두그래프간의형태적유사성을집합론적인관점에서측정하는방법으로, 두그래프간에공통인노드가많을수록두그래프간의유사도는 1에가까운값을갖게되며, 반대의경우는 0에가까운값을갖게된다. 두그래프 G u 와 G r 의유사도값 D를 Closeness로구하는식은다음과같다. (7) 식 (7) 에서, G u G r 은두그래프 G u, G r 에공통되게속한노드 v 와연결된이웃노드들 (neighborhood) 의합집합이며, G u G r 은이웃노드들의교집합, n은 G u G r 의크기를의미한다. MCS는주어진두그래프에공통인부분그래프중가장많은노드의개수를지닌부분그래프를의미한다. 두그래프 G u 와 G r 의유사도값 D를 MCS로구하는식은다음과같다. (8) 식 (8) 에서, G u 와 G r 은그래프 G u 와 G r 의노드의개수이고, MCS(G u, G r) 는 G u 와 G r 의부분그래프중가장큰그래프의노드의개수, max ( G u, G r ) 는두그래프 G u 와 G r 중노드의개수가더많은그래프를의미한다. 그러나상기의두알고리즘은두그래프간의노드간유사도만을고려하며링크정보를고려하지못한다는한계를지니고있다. 이를고려하여제안하는마지막알고리즘은노드및노드를연결하는링크들의연결정보까지모두고려하는 Edit Distance이다. Edit Distance 는한그래프가다른그래프로변형될때까지필요한노드및링크의삭제, 추가및교환등의작업의최소개수를의미한다. 두그래프 G u 와 G r 의유사도값 D 를 Edit distance로구하는식은다음과같다. (9) 식 (9) 에서, C(ε) 는그래프 G u 가 G r 로 ( 혹은 G r 에서 G u 로 ) 변형되는데필요한작업의개수를의미한다. 두그래프 G u 와 G r 의유사도값 D는식 (7) 에서 (9)

6 1122 정보과학회논문지제 41 권제 12 호 ( ) 중선택된그래프유사도계산법에따라각각다른값을갖게되며이는본논문에서제안하는방법의최종성능에크게영향을미친다. 각식에따른실험결과변화분석은다음장에언급되어있다. 4.4 근접성정보를반영한최종개인화검색결과본논문에서제안하는알고리즘은어떤문서 r 이사용자 u 의관심과얼마나일치하는지를 4.3장에소개한방법으로측정함에동시에, 사용자 u 의질의어 q 1, q 2,, q n 의집합 Q 가문서 r 속에서얼마나긴밀한관계를갖는지를측정하여개인화검색결과에반영한다. 질의어집합 Q 에속하는질의어 q 1, q 2,, q n 들의문서프로파일 G r 내에서의근접성값 P(Q, G r) 은다음과같다. 질의어 q 1, q 2,, q n 의집합 Q들의리소스프로파일 G r 속에서의근접성값 P(Q, G r) 은다음과같다. (10) (11) 식 (11) 에서, Distance(q 1, q 2) 는질의어 q 1 과 q 2 간의최단거리이며, n은질의어의개수, maxdistance(g r) 는리소스프로파일 G r 내에서의가장먼거리로정규화 (Normalization) 를위한값이다. 관련문헌 [7] 에따르면, 어떤두노드간의근접성정보는다음과같은두개의특성을지닌다. 첫째, 그래프상에서노드간의거리가작을수록해당노드간의근접성정보는급격히커진다. 둘째는단어들간의거리가멀더라도여전히어느정도느슨한관계를갖게되므로, 근접성점수가급격하게낮아지지않는다. 이러한두가지조건을만족하는두노드간의거리정보와근접성정보의관계는볼록곡선 (Convex curve) 의형태로표현할수있다. 따라서, 이러한볼록곡선의형태를갖는근접성점수를얻기위해 DS(Q, G r) 점수를음수로변환하고, 실제단어간의거리의특성을잘반영하기위해식 (10) 과같이 Convex 함수로변환한다. 이때볼록도의정도를조절하는 는실험을통하여 0.6으로고정되었다 (5.3장참조 ). 최종적으로, 우리는사용자와문서간의유사도와각문서에서주어진질의어들이갖는근접성정보를다음과같이융합하여최종개인화점수 PS(Personalized Score) 를제안하고, 이점수가높은리소스부터최종개인화검색결과상위에반환된다. (12) 식 (12) 에서, 근접성정보의반영도를조절하는 는 0과 1 사이의값으로 값이 0인경우질의어의근접성정보는최종개인화검색점수에반영되지않으며, 반대 로 1에가까워질수록최종개인화검색에질의어의근접성점수가영향을미치는정도가증가한다. 본논문에서는 값이 0.4인경우가장효과적인성능을보임을실험을통해알아내었다 (5.3장및그림 2 의 (b) 참조 ). 5. 실험본장에서는제안하는방법의성능평가를위한성능평가프레임워크를제안하고, 실험을위해사용한데이터및실험환경을소개한후최종적으로본실험의결과를설명한다. 5.1 성능평가프레임워크개인화검색의성능을평가하는것은 (1) 실제시스템을이용할사용자를고용하여평가하는방식과 (2) 검색시스템의로그데이터를분석하는방법, 크게 2가지로분류할수있다. 첫번째방법의경우객관적인성능평가를위해많은사용자를고용하고, 오랫동안시스템을사용하게하는비용의문제가크게발생하여, 본논문에서는실제이용가능한데이터들을분석하여실험에이용하는방법을채택하였다. 그러나, 온라인상에서접근가능한폭소노미데이터를개인화검색의성능평가를위해바로사용하는것은여러가지어려움이따른다. 그중에서도가장큰어려움은, 그러한폭소노미데이터셋의경우질의어에대해어떠한문서의적합성을표현하는데이터를획득하기어렵다는것에있다. 로그데이터를분석하여검색성능을평가하는경우, 일반적으로연구자들은주어진질의어에의해반환된검색결과에서클릭된문서들은그질의어의관련있는정답셋이라고가정한다. 이와비슷하게, 폭소노미데이터셋에서사용자가태그를단문서는해당사용자가찾고자하는문서라고볼수있다. 예를들어, 사용자가어떠한문서에 개인화 라는태그를달았다면, 우리는그문서를해당사용자가 개인화 를질의어로입력했을때찾기원하는문서로가정할수있다. 따라서, 만약해당문서의순위가개인화되지않은검색결과보다개인화된검색결과에서더높다면우리는제안하는방법의검색성능이잘작동한다고정의할수있다. 실제로이러한성능평가프레임워크는객관적인개인화성능평가를위해여러폭소노미기반의개인화검색관련문헌 [4,6,14] 에서사용되었다. 본논문에서는해당사용자가리소스에입력한태그중상위 3개를질의어로선정하여이를초기검색결과를얻는데사용하였다. 이를위하여, 90% 의태그정보가사용자및리소스프로파일을구축하는데사용되었고, 10% 의태그정보가실험용으로사용되었다. 5.2 실험환경우리는여러폭소노미데이터셋들중데이터의밀도

7 질의어의근접성정보및그래프프로파일링기법을이용한태그기반개인화검색 1123 표 1 실험데이터셋소개 Table 1 Description of Datasets Used in Experiment Data Set # of Users # of Resources # of tags Avg. # of tags in user profiles Avg. # of tags in resource profiles CiteULike MovieLens 가그래프기반의알고리즘에가장큰영향을미침을고려하여 [19], 데이터밀집도가상대적으로낮은 CiteULike 북마크데이터셋 ( 리소스당평균태그수 2.87) 과상대적으로높은편인 MovieLens 영화데이터셋 ( 리소스당평균태그수 9.06) 을실험데이터셋으로선정하였다. CiteULike은사용자들이관심있는논문에대해직접태그를달아활용할수있게한서비스이며 MovieLens는영화에대해사용자들이태그를직접작성할수있게한서비스로해당서비스에서배포된데이터셋들은관련연구 [14,20] 에서실험데이터로사용되었다. 다음표 1은선정된두데이터셋의속성을소개하는표이다. 기존기법과의평가를위하여우리는비교대상으로 1) BM25로얻은초기검색결과 (baseline) 및 2) BM25 및코사인유사도로개인화된검색결과 (BM25), 3) 근접성정보가고려되지않은그래프기반의검색기법 ( 공식 (6) 에서 =0 인경우, 이하 graph only) 들을우리가제안하는 4) 그래프기반의개인화검색및근접성정보를모두고려한알고리즘 (graph+proximity) 과비교하였다. 2, 3번및최종우리가제안하는방법의경우, 1 번베이스라인방법을통해질의어에적합한리소스최대 50개를초기검색결과로반환한결과를바탕으로각각의알고리즘을적용한재정렬과정을통해최종검색결과를반환하였다. 개인화검색의성능평가척도로는주로 MRR, MAP, NDCG, 등이사용된다. 하지만본연구에서사용하는프레임워크의경우주어진질의어셋에적합한문서는전체문서중하나이므로, 복수개의적합문서가있는실험환경에주로사용되는 NDCG와 MAP 는사용할수없다. 따라서, 우리는첫번째평가척도로 MRR을사용한다. MRR은제안하는방법이얼마나빠르게사용자가주어진질의에적합한문서에도달할수있는지를측정하는척도이다. MRR은다음과같이계산된다. (12) 식 (12) 에서, n은평가에사용된질의어집합의개수이며, q i 는쿼리, rank(r qi ) 는해당질의어에적합한문서의최종검색결과내순위이다. 또한제안하는기법의정확성을측정하기위한척도 로우리는 P@N을사용하였다. (13) (14) 식 (13) 에서, N은최종검색결과내상위 N개의문서이고, 이를바탕으로, 평균 P@N 은식 (14) 와같이얻어진다. 본논문에서는상위 5, 10, 20 개의문서에서의 P@N 을측정하였다 ( 즉, N=5, 10, 20). 5.3 실험결과및분석먼저, 3.3에서제안한프로파일간의유사도를계산하는여러방법중에제안하는알고리즘에가장적합한방법을찾아내기위한실험을실시하여표 2와같은 MRR 척도결과를얻었다. 이때식 (10) 과식 (12) 의 및 값은파라미터민감도실험을통해각각 0.6과 0.4로고정되었다 ( 그림 2 참조 ). 기존의개인화검색방법인 BM25와비교했을때, Edit Distance ( 표 2의 ED) 기반유사도계산법은사용된데이터셋에관계없이통계적으로유의한우수한성능을보였다 (Wilcoxon test, p< 0.05). 그러나그외에 Closeness와 MCS 그래프유사도계산법은오히려 CiteULike에서는기존의방법보다더낮은성능을보였고, MovieLens에서는성능향상의정도가통계적으로유의하지않은것으로나타났다. 이와같은결과를이해하기위해선, Closeness와 MCS, 그리고 Edit Distance의그래프유사도를측정하는차이를이해해야한다. Closeness와 MCS의경우, 그세부적인알고리즘은차이가있으나본질적으로두개의그래프가유사한지를판단할때에는노드간의구조적유사도만을주로고려한다. 이는두개의그래프가동일한노드를많이가지고있다면그정확도가향상된다는장점이있으나, 본연구에서사용하는두개의그래프는각각사용자데이터에서추출된사용자그래프와, 표 2 두프로파일간유사도계산법에따른성능차이 Table 2 Performance of Different Similarity Schemes to Measure Two Profiles Non-graph based Graph-based Data Set Baseline BM25 Closeness MCS ED CiteULike MovieLens

1124 정보과학회논문지제 41 권제 12 호 (2014. 12) 문서에달린태그로부터추출된문서그래프로동일한노드집합을갖게될확률이상대적으로적어, 노드간의유사성만을고려하는기법은개인화검색성능의향상을크게기대할수없는것으로보인다.

8 1124 정보과학회논문지제 41 권제 12 호 ( ) 문서에달린태그로부터추출된문서그래프로동일한노드집합을갖게될확률이상대적으로적어, 노드간의유사성만을고려하는기법은개인화검색성능의향상을크게기대할수없는것으로보인다. 게다가, 두그래프의공통된부분인서브그래프의유사도를비교하는 MCS와달리, Closeness의경우개념적으로두개의그래프가서로동일한노드를지니고있을때에만확실한유사도비교가가능하여, MCS보다데이터특성에훨씬의존적인경향을보인다. 이에반하여, Edit Distance는그알고리즘의간편함에비하여그래프의구조적특성및각링크들의가중치까지모두고려할수있게되어데이터셋에관계없이실제적인그래프기반의개인화검색성능향상을보이는것으로나타난다. 이에우리는각데이터셋에서균일한향상정도를보이는 Edit Distance를본그래프기반의프로파일의유사도를계산하는방법으로최종채택하였다. 이를바탕으로, 그림 1의 (a) 와 (b) 는각각 CiteULike 와 MovieLens 데이터셋에대한최종개인화성능을나타내는 MRR 척도의결과이고, (c) 와 (d) 는정확성척도의결과이다. 이를토대로개인화검색에관한다음과같은분석결과를도출할수있다. 두데이터셋에서모두개인화검색을적용하는것은일반적인검색결과와비교했을때, 큰성능의향상을보였다. 이는태그정보를활용하여개인화검색에적용하는것을통해사용자의검색만족도를향상시킬수있음을의미한다. 기존에폭소노미기반의개인화검색기법에서주로사용된벡터기반의프로파일링모델및유사도계산기법과본논문에서제안하는그래프기반의프로파일링모델및유사도계산기법을비교하였을때, 우 (a) parameter ( ) (b) parameter ( ) 그림 2 파라미터변화에따른 MRR 척도의변화 Fig. 2 MRR Performance by Varying Parameters 리가제안한그래프기반의개인화모델이기존의모델보다더좋은성능을보여주었다. 또한비교적데이터가균일하지않아프로파일구축이쉽지않은경우에도, 제안하는모델이더좋은성능을보였다. 마지막으로, 그래프기반의개인화모델과더불어질의어의근접성정보를모두고려하는우리의방식이데이터셋에관계없이두개의평가척도모두에서비교된대상들에비해더뛰어난성능을가진것을보여주고있다. 즉, 우리가제안하는방법은다른기법들과비교하여 MRR기준으로비교대상에비하여평균적으로약 7~43% 의유의한향상 (Wilcoxon test, p<0.05) 을보였고, 정확성기준으로는평균적으로약 10~58% 의유의한향상 (Wilcoxon test, p < 0.05) 을보였다. 최종적으로, 그림 2는우리가제안하는방법에서사용되는파라미터들의값에따라변하는 MRR을기록한것이다. 값을 0으로고정하고 에대한민감도실험을수행했을때, 두데이터셋모두에서 가 0.6정도일때가장최적의결과를얻을수있었으며, 이를토대로 를 0.6으로고정한후수행한 에관한민감도실험에서는 0.4정도에서최적값에수렴함을확인할수있었다. 이러한결과는제안하는모델이데이터셋에관계없이항상일정한값에서최적의성능향상을보일수있다는것을의미하여, 이를토대로제안하는모델은데이터셋에독립적이며파라미터에도독립적인알고리즘으로향후실제서비스에쉽게적용가능함을의미한다. 6. 결론및향후연구 그림 1 개인화모델에따른 MRR 및정확성변화 Fig. 1 MRR and Precision Performance of Different Personalization Models 본논문은단어간의근접성을측정할수있는그래프기반의프로파일링기법및유사도측정법을기반으로질의어간의근접성까지고려한보다발전된태그기반의개인화검색기법을제안하였다. 객관화된개인화성능평가실험을통해우리가제안한모델이기존의벡터기반의모델에비해개인화성능을향상시킨것을확인하였다.

질의어의근접성정보및그래프프로파일링기법을이용한태그기반개인화검색 1125 또한, 그래프기반프로파일링기법은데이터의크기가커질경우복잡도가증가할수있으나, 향후연구에서제안하는모델을실제서비스환경에적용하고이를통하여제안하는모델의확장성및효용성을검증하는것이필요하다.

Turnbull, A. Edmonds, E. Adar, and T. Breuel, "Personalized Search," Communications of the ACM, Vol. 45, No. 9, pp. 50-55, 2002. [2] C. M. A. Yeung, N. Gibbins, and N.

Su, "Optimizing Web Search Using Social Annotations," Proc. of WWW, pp. 501-510, 2007. [4] S. Xu, S. Bao, B. Fei, Z. Su, and Y. Yu, "Exploring Folksonomy for Personalized Search," Proc. of SIGIR, pp.

9 질의어의근접성정보및그래프프로파일링기법을이용한태그기반개인화검색 1125 또한, 그래프기반프로파일링기법은데이터의크기가커질경우복잡도가증가할수있으나, 향후연구에서제안하는모델을실제서비스환경에적용하고이를통하여제안하는모델의확장성및효용성을검증하는것이필요하다. 한편, 본연구에서는여러그래프기반의유사도기법중에서 Closeness, MCS, Edit distance만을사용했으나, 향후연구에서는보다다양한그래프기반의유사도기법을비교하며제안하는모델의성능을보다향상시킬수있는유사도기법을찾으려는노력역시지속되어야할것이다. References [1] J. Pitcow, H. Schutze, T. Cass, R. Cooley, D. Turnbull, A. Edmonds, E. Adar, and T. Breuel, "Personalized Search," Communications of the ACM, Vol. 45, No. 9, pp , [2] C. M. A. Yeung, N. Gibbins, and N. Shadbolt, "A Study of User Profile Generation from Folksonomies," Proc. of the Social Web and Knowledge Management Workshop, WWW Conf., [3] S. Bao, G. Xue, X. Wu, Y, Yu, B. Fei, and Z. Su, "Optimizing Web Search Using Social Annotations," Proc. of WWW, pp , [4] S. Xu, S. Bao, B. Fei, Z. Su, and Y. Yu, "Exploring Folksonomy for Personalized Search," Proc. of SIGIR, pp , [5] M. G. Noll, and C. Meinel, "Web Search Personalization Via Social Bookmarking and Tagging," Proc. of ISWC, pp , [6] D. Vallet, I. Cantador, and J. M. Jose, "Personalizing Web Search with Folksonomy-based User and Document Profiles," Proc. of ECIR, pp , [7] T. Tao, and C. Zhai, "An Exploration of Proximity Measures in Information Retrieval," Proc. of SIGIR, pp , [8] P. A. Chirita, C. S. Firan, and W. Nejdl, "Personalized Query Expansion for the Web," Proc. of SIGIR, pp. 7-14, [9] P. A. Chirita, W. Nejdl, R. Paiu, and C. Kohlschutter, "Using ODP Metadata to Personalized Search," Proc. of SIGIR, pp , [10] B. Tan, X. Shen, and C. Zhai, "Mining Long-term Search History to Improve Search Accuracy," Proc. of KDD, pp , [11] K. Sugiyama, K. Hatano, M. Yoshikawa, and S. Uemura, "User-Oriented Adaptive Web Information Retrieval Based on Implicit Observations," Proc. of ApWeb, pp , [12] J. T. Sun, H. J. Zeng, H. Liu, Y. Lu, and Z. Chen, "CubeSVD: A Novel Approach to Personalized Web Search," Proc. of WWW, pp , [13] Z. Dou, R. Song, J. R. Wen, "A Large-scale Evaluation and Analysis of Personalized Search Strategies," Proc. of WWW, pp , [14] Y. Cai, Q. Li, "Personalized Search by Tagbased User Profile and Resource Profile in Collaborative Tagging Systems," Proc. of CIKM, pp , [15] M. Daoud, L. Tamine, M. Bouhanem, "A Personalized Graph-based Document Ranking Model Using a Semantic User Profile," Proc. of UMAP, pp , [16] J. Zhao, Y. Yun, "A Proximity Language Model for Information Retrieval," Proc. of SIGIR, pp , [17] G. Levi, "A Note on the Derivation of Maximal Common Sub-graphs of Two Directed or Undirected Graphs," Calcolo, Vol. 9, No. 4, pp , [18] H. Bunke, X. Jiang, and A. Kandel, "On the Minimum Common Supergraph of Two Graph," Computing, Vol. 65, No. 1, pp , [19] A. Shepitsen, J. Gemmell, B. Mobasher, R. Burke, "Personalized Recommendation in Social Tagging Systems Using Hierarchical Clustering," Proc. of RecSys, pp , [20] S. Lee, M. Ko, K. Han, J. Lee, "On Finding Fine- Granularity User Communities by Profile Decomposition," Proc. of ASONAM, pp , 한기준 2010년호주국립대학교정보통신공학과 ( 학사 ). 2013년한국과학기술원지식서비스공학과 ( 석사 ). 2013년~현재한국과학기술원지식서비스공학과박사과정재학관심분야는정보검색및개인화서비스 장진철 2010년연세대학교정보산업공학과 ( 학사 ) 2012년한국과학기술원지식서비스공학과 ( 석사 ). 2013년~현재한국과학기술원지식서비스공학과박사과정재학. 관심분야는개인화를위한사용자경험연구 이문용 1998년 University of Maryland 정보시스템 ( 박사 ). 1998년~2004년 University of South Carolina 조교수. 2005년~ 2009년 University of South Carolina 부교수 (tenured). 2009년~2013년한국과학기술원지식서비스공학과부교수 년~현재한국과학기술원지식서비스공학과교수 (tenured) 관심분야는 Knowledge Engineering, Semantic Web, Personalization, User Experience

DBPIA-NURIMEDIA

DBPIA-NURIMEDIA 질의어단위프로파일링을이용한북마크기반개인화검색 153 질의어단위프로파일링을이용한북마크기반개인화검색 (Bookmark-Based Personalized Search through Query-Level User Profiling) 김현지 배동환 (Hyun Ji Kim) (Dong Hwan Bae) 고민삼 이문용 (Minsam Ko) (Mun Yong Yi) 요약본논문에서는개인화검색시사용자의단일프로파일이개인의다양한정보요구를만족시키지못하는문제를개선하고자,