工學碩士學位論文 위치정보와의사결정트리기법을이용한개인화된추천시스템 A Personalized Recommender System using Decision Tree based on Location 2006 年 2 月 仁荷大學校大學院 컴퓨터情報工學科 李培熙
工學碩士學位論文 위치정보와의사결정트리기법을이용한개인화된추천시스템 A Personalized Recommender System using Decision Tree based on Location 2006 年 2 月 指導敎授趙根植 이論文을工學碩士學位論文으로提出함 仁荷大學校大學院 컴퓨터情報工學科 李培熙
이論文을李培熙의碩士學位論文으로認定함. 2006 年 2 月 主審 ( 印 ) 副審 ( 印 ) 委員 ( 印 )
요 약 인터넷의급속한성장에부흥하여무선인터넷에대한관심과연구가활발히이루어지고있다. 무선인터넷과모바일디바이스를이용한 m-commerce는 e-commerce에이은새로운비즈니스분야로자리잡아가고있다. 이러한무선인터넷을이용한 m-commerce의가장큰특징은기존의인터넷보다더욱개인화된서비스와사용자의이동성에기반을둔고유의정보를제공할수있는것이다. 현재상용화되고있는네비게이션시스템은사용자의위치정보를이용한대표적인서비스이며위치에기반을둔레스토랑, 호텔, 상점등의검색기능도갖추고있다. 하지만단순히위치에기반을둔검색기능은사용자의개인적, 공간적특성을고려하지않음으로써서비스로서의제기능을발휘하지못하고있다. 이를개선하기위해본논문에서는사용자의위치에기반을둠과더불어개인화된추천서비스도가능한시스템을제안한다. 개인화를위해기존의데이터마이닝기법중의하나인의사결정트리를사용하여사용자들의데이터를분석하여사용자의관심사를파악하고레스토랑과의거리를측정하여위치정보에기반을둔추천목록을생성한다. 위치기반의추천과개인화기반의추천에각각가중치를부여하여보다효과적인추천목록을제공한다. 본논문에서는실험을통하여제안된시스템의성능평가를위해위치를고려하지않은추천시스템과비교를하고위치와사용자의관심사를동시에고려한시스템과가중치까지부여한시스템과의비교를하였다. 그결과, 사용자의관심사와위치를기반으로가중치까지부여된추천시스템이기존의추천시스템보다높은성능을보임을확인할수있었다. - i -
ABSTRACT Since Internet has been rapidly developed, studies and interests show for wireless Internet are actively achieving. M-commerce which using wireless Internet and mobile device has settled in new business field followed by e-commerce. The most significant feature of m-commerce using those wireless Internet is that it has more personalized and provide characteristic informations based on user's moving capacity. The common uses of in-car satellite navigation systems is a typical service of using information of one's location that also has search function to find restaurants, hotels and stores etc. But that search capacity wouldn't be a proper service since it's simply based on the location doesn't consider of user's individual, area-wise peculiarities. To improve those service, in this paper is proposing a system using user's location with personalized recommender service. For personalizing, it uses decision tree which is one of data mining technique to analyze user's data for finding one's interests then measure the distance to certain restaurants and creates recommender list based on the locational information. By giving weight to each of location-basis recommender and personalize-basis provides more efficient recommender list. Made a comparative study with recommender system of non-locational basis, recommender system of location and individual interests counted in and recommender system of all above with given weight for a performance testing of the suggested system. As a result, user's interests and location-basis recommender system with given weight was more highly efficient than previous recommender system. - ii -
목차 요약 ⅰ ABSTRACT ⅱ 제 1 장서론 1 제 2 장관련연구 3 2.1 위치기반서비스 3 2.2 개인화된추천시스템 5 2.3 데이터마이닝을이용한예측 7 제 3 장위치기반의개인화된추천시스템 12 3.1 시스템구조 12 3.2 위치기반의추천 13 3.3 개인화된추천 14 3.4 가중치를적용한통합추천 19 제 4 장실험및결과 21 4.1 실험환경및데이터집합 21 4.2 실험평가방법 23 4.3 실험결과및분석 24 제 5 장결론및향후연구 28 참고문헌 30 - iii -
제 1 장서론 인터넷의급속한성장에부흥하여무선인터넷에대한관심과연구가활발히이루어지고있다. 무선인터넷과모바일디바이스를이용한 m-commerce는기존의유선기반의 e-commerce에서해결하지못하는이동성과개인화를충분히제공할수있어 m-commerce만의영역을확대해가고있다. 이렇듯무선인터넷을이용한 m-commerce의가장큰특징은기존의인터넷보다더욱개인화된서비스와사용자의이동성에기반을둔고유의정보를제공할수있는것이다. 개별고객의특수한요구 (needs) 를개별적으로파악하고각각의고객에게차별화된서비스를제공하는것이그핵심이다. 이를이용하여기업은개별고객과의관계증진을통해고객유지율을상승시키고차별화된서비스의제공하여신규고객의유치에나선다. 개별고객과의일대일마케팅은차별화된서비스를제공하기위한효율적인수단이되며, 이를가능하게하기위해서는고객데이터베이스, 상호작용성, 맞춤화의세가지의요소가요구된다 [9][17]. 기존의 e-crm, e-business 등에서는개인화된서비스를위해고객의프로파일정보, 구매이력데이터, 제품정보등과같은요소만을이용하여개별고객의취향을파악하고해당서비스를제공했다 [12][14]. 하지만이러한서비스는이용자의개인적, 공간적특성을고려되지않은정보가제공됨으로써사용자에게적절한정보및서비스임에도불구하고제기능을발휘하지못하는경우가발생한다. 하지만여기에최근의 GPS(Global Positioning System) 와무선데이터전송능력이있는휴대용단말기의 - 1 -
출현및이동 / 무선컴퓨팅기술의발전은모바일컴퓨팅의진보를이끌었으며이로인하여공간상의위치식별기술및 GIS 기술과결합되어이동중인클라이언트에게다양한생활정보서비스를제공할수있는모바일정보액세스와같은영역을창출하였다 [21]. 현재상용화되고있는네비게이션시스템은사용자의위치정보를이용한대표적인서비스이며위치에기반을둔레스토랑, 호텔, 상점등의검색기능도갖추고있다. 하지만단순히위치에기반을둔검색기능은사용자의개인적, 시간적특성을고려하지않음으로써서비스로의제기능을발휘하지못하고있다. 이를개선하기위해본논문에서는사용자의위치에기반을둠과더불어개인화된추천서비스도가능한시스템을제안한다. 개인화를위해기존의데이터마이닝기법중의하나인의사결정트리를사용하여사용자의데이터를분석하여사용자의관심사를파악하고레스토랑과의거리를측정하여위치정보를기반으로둔목록을생성한다. 위치기반의추천과개인화기반의추천에각각가중치를부여하여보다효과적인추천목록을제공한다. 제안된시스템의성능평가를위해위치를고려하지않은추천시스템과비교를하고위치와사용자의관심사를동시에고려한시스템과가중치까지부여한시스템과의비교하였다. 그결과, 사용자의관심사와위치를기반으로가중치까지부여된추천시스템이기존의추천시스템보다높은성능을보였다. - 2 -
제 2 장관련연구 2.1 위치기반무선인터넷서비스 무선인터넷의특징은각개인의단말기사용에따른더욱더개인화된서비스를활용할수있고, 이동하며사용할수있는이동성을지닌다는것이다. 이에따라많은연구기관들은사용자위치기반의서비스를제공하는위치기반무선인터넷을핵심적인서비스로보고있다. 이런위치기반의무선인터넷의배경으로는 2001년 10월까지사용자의위치에대하여 100m 이내의정확도로구조요청기능을각이동통신사가제공해야된다는미국통신위원회의 1996년규정, E-911에서비롯되었고, 이후, 무선통신을이용하여위치를결정하는두가지위치결정시스템, 즉 GPS(Global Positioning System) 칩셋을휴대폰에내장하는방법과통신망으로부터의파일럿신호를이용하여통화자의위치를얻는방법의발전에기인한다 [8]. 위치기반서비스의핵심적인무선측위기술인 GPS 기반무선측위기술과네트워크통신망기반무선측위기술그리고위치기반응용서비스에대하여좀더알아보도록한다. 2.1.1 GPS 기반무선측위 GPS는 24개의인공위성을이용하여위성신호를해석함으로써사용자의 3차원위치를장소와시간에관계없이얻을수있도록고안된군사적장치이다. 현재 GPS를단말기에사용하는방법은두가지로나누어진다. 첫째는저전력의 GPS 칩셋을단말기에내장하거나 PDA(Personal Digital - 3 -
Assistant) 에 GPS모듈을부착하는방식에의해서단말기자체에서위치를구하는방식이다. 둘째는 GPS의 3분 ~10분에이르는긴워밍업시간을없애기위해기지국에서위성궤도정보를단말기에전달하고, 단말기는위성으로부터의의사거리데이터를기지국에전송함으로써, 기지국에서위치를짧은시간안에구하는방식이다 [10]. 2.1.2 네트워크통신망기반무선측위 이동통신에서기지국의위치는고정되어있기때문에기지국 (BS) 에서이동국 (MS) 까지의거리를정확히알면, 이동국의위치를얻을수있다 [7]. 기지국과이동국사이의거리를알기위해서신호의전달시간을상관기와 DLL(Delay-Lock-Loop) 에의해계산하게된다. 이와같이하여동시에 3개이상의기지국에서의거리를계산하게되면삼각측량법에의하여이동국의 2 차원위치를결정하게된다. 2.1.3 위치기반서비스실례 위치기반응용서비스는앞으로큰효용가치만큼다양하다. [ 표 1] 과같이위치기반의서비스는위치기반정보서비스, 항법 / 추적서비스, 위치기반상거래, 공익서비스, 기타와같이 5가지의종류로나누어분류할수있다. 인접지역정보제공등의무선 GIS, 위치기반의광고서비스, 사용자지역을기반으로한비교쇼핑등은인터넷전자상거래 (E-Commerce) 와더불어무선인터넷에서의전자상거래 (M-Commerce) 중의핵심부문이라고볼수있다. 위치기반광고서비스는등록된사용자가특정지역에위치하여있을때, 단말기를통하여정보를제공받는것이다. 인접상점의광고, 그지역에서일 - 4 -
어나는이벤트를알려줌에의해서, 다른인터넷서비스에비해타겟화된서비 스를하게된다. [ 표 1] 위치기반응용서비스의분류 분류위치기반정보서비스항법 / 추적서비스위치기반상거래공익서비스기타 서비스지도서비스, 교통정보서비스, 여행가이드최적경로계산, 차량항법및물류관제 Mobile 전자상거래, 광고서비스, 비교쇼핑구조요청, 범죄신고, 기상예보게임 2.2 개인화된추천시스템 현재개인화는최근에많이거론되고있는 e-crm, e-business의중요한부분을차지하고있는요소로서이에대한논의는개인화가주는영향력과효과분석측면에서주로진행되고있다. 이러한개인화기술및개념은이미상당한영향력을보이며인터넷에적용될핵심기술로떠오른지오래다. Amazon.com[5] 이나 CDnow.com[6] 등의좋은선례를통해개인화가매출증대및고객확보뿐만아니라여러가지다양한혜택을제공하고있다는것을알게되었다. 현재국내에서도대형온라인쇼핑몰, Portal을중심으로이에대한적용을다각도로적용되고있다 [18][22]. 사용자들의측면에서추천시스템을이용하여개인화를원하는첫번째이유는시간의절약이다 [15]. 자신의주변에존재하는다양하고많은레스토랑중에서자신이원하는레스토랑을찾기위해서많은시간을들여야하는경우가많아진다. 만일사용자가자신이원하는레스토랑을복잡한 - 5 -
과정을거치지않고얻을수있는시스템이있다면당연히사용하려고할것이다. 두번째이유는개인화가사용자들에게자신만의선택을가능하게해주는데있다 [2]. 다수의사용자가선택하는레스토랑이아닌자신의취향에맞는레스토랑을선택하는것이다. 개인화의세번째장점은개인들이관심을갖고있는레스토랑의광고, 이벤트, 할인정보등의개인화된서비스를받을수있다는점이다 [19]. 다음은개인화를실현하기위하여사용하는방법들이다. 2.2.1 규칙기반필터링 (Rule-based filtering) 방식 개인화의방법중가장기초적이고일반적인것은규칙기반필터링 (Rule-based filtering) 이다. 이방법은사용자에게개인신상, 관심분야, 선호도등에대한몇가지질문을하는것이일반적이다. 예를들어나이, 성별, 직업, 지출액, 특정한사항에대한선호도등을묻는다. 시스템은질문을통해얻어진그사람에대한정보들로사용자프로파일 (Profile) 을생성하게된다. 추천시스템은이렇게수집된사용자의인구통계학적 / 심리적정보와사용자의선호도정보에알맞은레스토랑정보및추천을제공하는것이다. 2.2.2 협력적필터링 (Collaborative filtering) 방식 협력적필터링 (Collaborative filtering) 은사용자들의기초정보와고객들의선호도 / 관심표현을바탕으로선호도 / 관심에서비슷한패턴을보이는고객들을묶는것을통해고객서비스의방향을결정한다. 즉비슷한취향을가진고객들에게아직구매하지않은상품들을교차추천하거나분류된 - 6 -
고객의취향이나생활형태에따라관련상품을추천하는형태로서비스를 제공하게된다. Ringo[16], GroupLens[4] 와같은시스템이협력적필터 링방식에기반을둔개인화추천시스템이다. 2.3 데이터마이닝을이용한예측 데이터웨어하우스 (data warehouse) 와데이터베이스 (database) 가정보기술의도움으로급속히발달하면서고객과상품, 그리고거래에관한정보가증가하고있다. 데이터마이닝은대용량의데이터베이스로부터정보를추출하는과정이라볼수있다. 구체적으로는데이터베이스에존재하는자료에내재하고있는변수들간의숨겨진관계를패턴인식기술, 통계기법, 수학적알고리즘등을이용하여찾아내는것을의미한다 [13]. 일반적으로데이터마이닝을위해사용되고있는기법들을살펴보면분류 (classification), 연관규칙 (Association Rule), 군집화 (clustering) 등을들수있다. 이러한마이닝기법중에서분류기법중의하나인의사결정트리와연관규칙 (Association Rule) 기법의내용을기술한다. 2.3.1 의사결정트리 (Decision Tree) 의사결정트리는데이터마이닝의분류작업에주로사용되는기법으로, 과거에수집된데이터의레코드들을분석하여이들사이에존재하는패턴, 즉부류별특성을속성의조합으로나타내는분류모형을나무의형태로만드는것이다. 이렇게만들어진분류모형은새로운레코드를분류하고해당부류의값을예측하는데사용된다 [3]. 의사결정트리를만드는가장보편적인알고리즘으로는 [ 그림 1] 과같은 C4.5 Algorithm이이용된다. 그리 - 7 -
고, C4.5 Algorithm의기본적인전략은다음과같다. 트리는훈련샘플들을나타내는단일노드로시작한다. 샘플들이모두같은클래스라면노드는잎이된다. 그렇지않으면정보이득 (information gain) 이라는엔트로피 (entropy) 기반척도를사용하여샘플들을가각의클래스로가장잘분리하는속성을선택한다. 속성비교를통해분할된샘플들은의사결정트리를형성하기위해서동일한과정을재귀적으로수행한다. 노드의모든샘플들이같은클래스에속하거나남아있는속성이없는경우재귀적분할을정지한다. Function decision_tree(example_set, Properties(Attribute)) begin if all entries in example_set are in the same class then return a leaf node labeled with that class else if Properties is empty then return leaf node labeled with disjunction of all classes else begin select a property, P, to text on and make it root of current tree; delete P from properties; for each value, V, of P, begin create a branch of the tree labeled with V let partition be elements of example_set with V for property P; call induce_tree(partition, Properties), attach result to branch V end; end; end [ 그림 1] C4.5 알고리즘 정보이득 (information gain) 척도는트리의각노드에서검사속성을선 택하는데사용된다. 가장큰정보이득을가지는속성이현재노드에대한 - 8 -
검사속성으로선택되며다음과같은과정으로계산한다. S를 s개의샘플데이터를가자는집합, 클래스레이블속성은 m개의상이한클래스 C (i=1, i..., m) 을정의하는 m개의상이한값을갖는다고가정하자. 샘플 S에있는클래스 C 의 i 샘플개수를 s 라고 i 하자. 주어진샘플을분류하는데요구되는기대정보량 (expected information) 은식 (1) 과같다. m I (s 1,..., s m ) = Σi p i log 2 (p i ) (1) =1 여기서 p i 는임의의샘플이클래스 C i 에속할확률이며 s i/s 으로계산된다. 속성 A 는 v 개의상이한값 {a 1,..., a v} 을갖는다고하자. 속성 A 는 S 를 v 개의부분집합 {S 1,..., S v } 를분할하는데사용될수있다. 여기에서 S j 는 A 의값 a ij 를갖는 S 의샘플들을포함한다. 부분집합 S j 에있는클래스 C i 의샘플수를 s ij 라고하자. A 에의해부분집합으로분할하는경우의엔트 로피 (entroy), 기대정보량 (expected information) 은식 (2) 와같다. v E(A) = Σj =1 s 1j +... + s mj s I (s 1j,..., s mj ) (2) 엔트로피값이작으면작을수록분할된부분집합의순수도는증가한다. 주어진부분집합 S j 에대해서, m I (s 1j,..., s mj ) = Σi p ij log 2 (p ij ) (3) =1 이되고, 여기서 p ij = s ij S j 으로, S j 의샘플이클래스 C i 에속하는확률 이다. A 에대한분기로얻게되는부호정보량 (encoding information) 은 - 9 -
다음과같다. Gain(A) = I (s 1,..., s m ) E(A) (4) 즉, Gain(A) 는속석 A 의값을알고있음으로인해서비롯되는엔트로피 의기대감소량이다. 2.3.2 연관규칙 (Association Rules) 연관규칙 (Association Rule) 은한항목그룹과다른항목그룹사이에존재하는연관성을규칙의형태로표현한것이다 [1][11]. 즉, A B 의형태를갖는패턴으로서이러한규칙이갖는의미는 A 항목집합이나타날때는 B 항목집합도동반하여나타나는경향이있다는뜻이다. 연관규칙을탐사하는문제는기본적으로다음의두단계로구성된다. 미리결정된최소지지도이상의트랜잭션지지도를가지는항목집합들의모슨집합들인빈발항목집합들을찾아내는단계와빈발항목집합의부분집합 A에대하여, 만약 Support(A) 에대한 Support(L) 의비율이적어도최소신뢰도이상이면 (support(l)/support(a) min confidence), A (L-A) 의형태의규칙을출력하는단계이다. 이때, 이규칙의지지도는 Support(L) 이고신뢰도는 Support(L)/Support(A) 이다. 연관규칙은주로장바구니분석 (Market Basket Analysis) 에주로사용되며구체적인예는다음과같다. 분유를구매하는사람의 30% 는기저귀를구매하며전체트랜잭션의 2% 는분유와기저귀를포함하고있다. 여기서 30% 는이규칙의신뢰도 (confidence) 라고불리며 2% 는이규칙의지지도 (support) 라고불린다. 이와같이생성된연관규칙은개인구매도 - 10 -
분석, 상품의교차매매 (Cross-Marketing), 카탈로그디자인, 염가매출품 (Loss Leader) 분석, 상품진열, 구매성향에따른고객분류등등다양하 게사용된다 [3]. - 11 -
제 3 장위치기반의개인화된추천시스템 3.1 시스템구조 이동중인모바일디바이스사용자에게레스토랑을추천하기위해서기존의개인화추천시스템과위치기반의서비스를결합시킨다. 이러한시스템은사용자개인의취향에따라레스토랑을선택할수있는기능을가지고있으며레스토랑까지의거리도고려하여사용자의시간적, 공간적욕구도충족시키게된다. 위치기반의개인화된추천을위해서 [ 그림 2] 에서보는바와같이세단계의작업이이루어진다. [ 그림 2] 위치기반의개인화된추천시스템 - 12 -
첫번째단계는기존사용자들의개인정보와상황정보를바탕으로레스토랑추천목록을작성하는것이다. 두번째단계는사용자의현재위치를기반으로레스토랑추천목록을작성하고마지막으로두추천목록에각각가중치를적용하여최종추천목록을완성하여사용자에게제공한다. 우선기존사용자들의개인정보를이용한추천목록은개인화추천시스템중규칙기반필터링방식을참고하여작성하게된다. 이러한규칙은예측데이터마이닝기법중의사결정트리를이용하여얻어진다. 다음으로위치를기반으로한추천목록은무선인터넷서비스중 GPS 기반무선측위기술을이용하여현재사용자의위치와레스토랑사이의거리를얻게된다. 이렇게생성된추천목록에실험을통해얻어진최적의가중치값을적용하여최종레스토랑추천목록을생성하게된다. 위의 [ 그림 2] 에나타난추천시스템의각단계에대하여더욱자세히알아보도록하자. 3.2 위치기반의추천 사용자에게레스토랑을추천하기위해서사용자와레스토랑과의거리나걸리는시간을고려한다. 사용자의위치를파악하기위해서는인공위성을이용한 GPS 기반무선측위법이나네트워크통신망기반의무선측위방법을사용한다. 본논문에서는사용자의위치가이미파악되었다는가정하에사용자의위치를좌표평면상에서원점으로놓고주변의레스토랑들과의거리를측정한다. 현재상용화되고있는 GPS 기반의서비스를이용하여각각다른종류의레스토랑을검색하여목록으로만들었다. 사용자의개인정보와레스토랑까지의거리가레스토랑을선택함에있어서어떤작용을하는지를알아보기위해서다섯개의레스토랑만을고려하였다. 아래의 [ 표 2] 에서사용자의 - 13 -
위치에서레스토랑까지의거리와시간을기반으로추천목록을나타내었다. [ 표 2] 위치기반의추천목록 종류 이름 거리 & 시간 추천목록 포인트 한식 농가마을 5Km, 7분 인하각 50 일식 참치사냥 2Km, 4분 참치사냥 40 중식 인하각 1Km, 1분 농가마을 30 양식 아웃백 12Km, 13분 롯데리아 20 카페 롯데리아 10Km, 11분 아웃백 10 3.3 개인화된추천 개인화된레스토랑추천목록을작성하기위해서본논문에서는인구통계적변수인성별, 나이, 지출액, 결혼여부, 직업의개인정보와날씨, 온도, 기분같은상황정보를분석을위한속성으로고려한다. 사전에조사된사용자들의개인정보와상황정보에따른레스토랑선택의자료를추천목록을작성하기위해분석한다. 분석에사용된데이터셋의예는아래의 [ 표 3] 와같다. 분석작업의편의성을위해조사되어진데이터는모두숫자로변환하여저장하였다. [ 표 3] 사용자별레스토랑선택의예 번호 성별 나이 지출 결혼 직업 날씨 온도 기분 레스토랑 1 1 20 30 1 1 2 7 9 3 167 2 28 50 1 2 1 7 8 3 325 2 25 50 2 2 3 6 4 1 480 1 37 70 1 1 1 9 6 2 위의 [ 표 3] 에서번호는데이터의순서일뿐분석과는관련이없으며, 성별 (sex) 은남자는 1, 여자는 2 로나타내었으며, 나이 (age) 는만으로, 지출 (expenditure) 은한달에지출하는금액을만원단위로표현하였다. 결혼유무 - 14 -
(marriage) 는미혼일경우 1, 기혼일경우 2로나타내었고, 직업 (job) 은학생은 1, 직장인은 2로표현하였다. 개인정보에속하는앞의다섯가지속성은객관적인자료이지만상황정보에속하는뒤의세가지속성은정보의성격면에서나개인의판단에따른조사임을감안할때다소주관적임을밝힌다. 날씨 (weather) 는맑음은 1로흐림은 2로표현하였고, 온도 (temperature) 와기분 (feeling) 은개인이판단하여최상일경우는 9로최하일경우는 0으로나타내었다. 끝으로레스토랑 (C i, i =1,...,5) 의경우는한식, 일식, 중식, 양식, 카페테리아 ( 이하카페 ) 순으로값을부여하였다. 이렇게조사된데이터들의분석을위해서데이터마이닝기법중에의사결정트리를이용하였다. 의사결정트리는이미분석과정에서자주이용되고있는기법이며속성간의연관규칙과레스토랑선택과는관련이적으므로분석의도구로의사결정트리를이용하게되었다. 우선의사결정트리를구성하기위해서는최상위의노드가되는속성을찾아내야한다. 최상위노드는정보이득 (information gain) 값이가장큰속성이선택되어진다. [ 그림 3] 는정보이득을계산하기위한알고리즘이다. - 15 -
#define ATTRNUM 7 CString attr[attrnum] = {"Sex", "Age",..., "Feeling"}; void C4_5View::Entropy(double Entro_Acc){ double entropy[] = {0, 0, 0, 0, 0, 0, 0}; // 속성의엔트로피저장 double esex, eage,..., efeeling; int NUM, valnum; // 엔트로피구하기 for(int j=0; j<totalnum; j++){ for(int i=0; i< ATTRNUM; i++){ NUM = Count[j][i]; valnum = AttCount[j][i]; if(num==0 valnum==0) entropy[j] += 0; else entropy[j] += (double)num/totalnum *(-(((double)valnum/num)*(log10((double)valnum/ NUM))/(log10(2.)))-(((double)(NUM - valnum)/num) *(log10((double)(num - valnum)/num))/(log10(2.)))); } } // Information Gain 구하기 esex = Entro_Acc - entropy[0]; eage = Entro_Acc - entropy[1];... efeeling = Entro_Acc - entropy[6]; } [ 그림 3] 정보이득알고리즘각속성에대한정보이득을계산하기위해, 먼저 ( 식1) 를사용하여주어진샘플을분류하는데필요한기대정보량 (expected information) 을계산한다. I (s 1,...,s 5 ) = I (141, 104, 109, 88, 58 ) = 2.27 다음에각속성의엔트로피를계산한다. 속성중에서성별 (sex) 로부터계산하여보자. 각분포에대한기대정보량을계산하여보면다음과같다. For sex = 1 : s 11 = 56,..., s 51 = 32 I (s 11, s 51) = 2.27 For sex = 2 : s 12 = 49,..., s 52 = 37-16 -
I (s 12, s 52) = 2.25 ( 식 2) 를사용하여, 만약샘플들이성별 (sex) 에따라분할되는경우주어진샘 플을분류하는데요구되는기대정보량은다음과같다. E (sex ) = 275 500 I (s 11,..., s 51 ) + 225 500 I (s 12,..., s 52 ) = 0.694 따라서분할로인한정보이득은다음과같다. Gain(sex ) = I (s 11,..., s 51 ) E (sex ) = 0.316 같은방법으로나머지속성들의정보이득을계산하여가장높은정보이득 을가진속성을검사속성으로선택한다. 본논문에서는날씨 (weather) 가첫 번째검사속성으로선택되었다. 새노드가생성되고날씨 (weather) 라는레이 블을갖게되며가지들이속성의각값들에대해서생성된다. 그리고샘플들 은 [ 그림 4] 에서보이는것과같이분할된다. [ 그림 4] 개인화된추천을위한의사결정트리 - 17 -
이렇게의사결정트리를생성하게되면어떤사용자의요청에대하여개인화 된추천목록을작성할수있게된다. 예를들어, [ 표 4] 과같은개인정보와 상황정보를가진사용자에게레스토랑추천을한다고가정하자. 사용자의데 이터로부터추천목록을작성하기위해서는 [ 그림 4] 의트리를따라내려간 다. [ 표 4] 사용자의개인정보와상황정보 성별나이지출결혼직업날씨온도기분레스토랑 1 32 60 1 1 2 7 9? 첫번째노드에서고려된날씨에대한속성이사용자의경우흐림이므로오른 쪽으로내려간다. 두번째노드에서고려된직업에대한속성이사용자의경 우학생이므로왼쪽으로내려가게된다. 이러한방식으로트리의마지막노드 까지다다르게되면 ( 마지막레벨의 6 번째노드 ) 레스토랑의비율을참고하여 추천목록을생성하게된다. 가장높은비율을차지하는레스토랑이일식, 중 식, 양식, 한식, 카페의순서이므로추천목록을이에따라생성하게되고가중 치적용단계에서사용하기위해각각의레스토랑에포인트를부여한다. 분석 결과와추천목록, 그리고포인트적용에대한내용을 [ 표 5] 에나타내었다. [ 표 5] 개인화된추천목록 레스토랑 분석결과 추천목록 포인트 한식 11.7% 일식 50 일식 35.3% 중식 40 중식 29.4% 양식 30 양식 17.7% 한식 20 카페 5.9% 카페 10-18 -
3.4 가중치를적용한통합추천 개인화된추천목록과위치기반의추천목록을가중치를적용하여통합하는단계이다. [ 표 2] 와 [ 표 5] 에서나타난추천목록각각의포인트에가중치값을적용한다. 이단계에서가중치의정도는개인화추천목록과위치기반추천목록에 0.3과 0.7의값을부여하였다. 최적의가중치값을찾기위해 0.1 단위로증감시켜각각에 0.7과 0.3의값이부여될때까지실험한다. 가장적절한가중치의값은추천에대한정확도를평가하여가장높은정확성을나타낼때의값이다. 가중치를적용하여레스토랑에대한포인트를부여하는계산은 ( 식 5) 과같다. S i = P i * W p + L i * W l (5) S i 는번째 i 레스토랑에부여되는점수이고 P 는 i 개인화추천목록에서얻은포인트이고 W p 는개인화추천목록에적용될가중치값이다. 또한 L 는 i 위치기반추천목록에서얻은포인트이고 W 1 은위치기반추천목록에적용될가중치값이다. 적용되는가중치값이각각 0.3과 0.7일때, [ 표 2] 와 [ 표 5] 로부터한식레스토랑인농가마을의최종포인트는다음과같이계산된다. S 1 = 20 * 0.3 + 30 * 0.7 = 27 개인화추천목록으로부터포인트 20을가져오고, 위치기반추천목록으로부터포인트 30을가져온다. 가중치와의곱을통해서최종포인트 36을얻게되고다른레스토랑들도이와같은방식으로최종포인트를계산한다. 아래의 [ 표 6] 에서는최적의가중치값을설정하기위해개인화추천목록에대해서는가중치를 0.1씩감소시키고, 위치기반추천목록에대해서는 0.1씩증가시키면서최종포인트를계산하였다. - 19 -
[ 표 6] 가중치에따른최종포인트 레스토랑종류 추천목록 가중치및최종포인트 개인화위치 0.3/0.7 0.4/0.6 0.5/0.5 0.6/0.4 0.7/0.3 한식 20 30 27 26 25 24 23 일식 50 40 43 44 45 46 47 중식 40 50 47 46 45 44 43 양식 30 10 16 18 20 22 24 카페 10 20 17 16 15 14 13 가중치를적용하여최종포인트가산출되면포인트가높은순서대로레스토랑을추천하게된다. [ 표 7] 에서는가중치변화에따른추천목록의차이를나타내고있다. 본논문의제 4장의실험에서각각의가중치에대한사용자의만족도를평가하였다. 그결과개인화추천목록에 0.4의가중치를그리고위치기반추천목록에는 0.6의가중치를적용하였을때가장좋은평가를얻었다. 즉, 사용자에게는최종추천목록중두번째의추천목록을제공하게된다. [ 표 7] 가중치에따른최종추천목록 추천순위 가중치및최종추천목록 0.3/0.7 0.4/0.6 0.5/0.5 0.6/0.4 0.7/0.3 1 인하각 인하각 참치사냥 참치사냥 참치사냥 2 참치사냥 참치사냥 인하각 인하각 인하각 3 농가마을 농가마을 농가마을 농가마을 농가마을 4 롯데리아 아웃백 아웃백 아웃백 아웃백 5 아웃백 롯데리아 롯데리아 롯데리아 롯데리아 - 20 -
제 4 장실험및결과 4.1 실험환경및데이터집합 본논문의실험은 JBuilder 9.0 과 Microsoft Windows XP 를사용하여이 루어졌으며실험환경은펜티엄 Ⅳ 2.8GHz, 512MB RAM 의시스템이었다. 훈련및테스트에사용된데이터들은 2005 년 5 월 20 일부터 6 월 20 일까지 설문조사를통해수집되었다. 설문조사는인하대학교부근의레스토랑에관 한지식이있는학생및일반인을대상으로하였으며총 500 부의설문을실시 하여데이터화하였다. 개인화된추천을위해서사용자의개인정보와상황 정보를조사하였고위치기반의추천을위해서사용자주변의알려진레스토 랑을선정하여조사였다. 위치정보를포함하지않은설문과포함한설문을 동시에실시함으로써제안하는시스템의효율성을실험을통해증명한다. [ 표 8] 에서는위치를고려하지않은데이터와고려한데이터를나타내고있다. [ 그림 5] 은설문에사용된현재사용자의위치와레스토랑의위치를나타낸 지도이다. 그리고실험에사용된추천시스템인터페이스는 [ 그림 6] 와같다. [ 표 8] 위치정보고려에따른레스토랑선택의변화 레스토랑위치를고려하지않았을때 성별 나이 지출 결혼 직업 날씨 온도 기분 레스토랑 1 20 30 1 1 2 7 9 4 레스토랑위치를고려하였을때 성별 나이 지출 결혼 직업 날씨 온도 기분 레스토랑 1 20 30 1 1 2 7 9 1-21 -
[그림 5] 현재 위치 및 레스토랑 위치 [ 그림 6] JAVA로 구현된 추천 시스템의 인터페이스 - 22 -
4.2 실험평가방법 개인화와위치정보를동시에고려한추천시스템의정확성을증명하기위해서 K-중첩교차조사 (k-fold cross-validation) 방법을이용하여수집된데이터셋을학습데이터와테스트데이터로분류하고실험한다. K-중첩교차조사방법에서는초기데이터를크기가대략적으로같은 S 1,..., S k 인 k 개의상호배반부분집합으로임의분할한다. 학습과테스트는 k 번반복수행한다. 반복 i 번째에서부분집합 S 는 i 테스트집합으로사용하고나머지부분집합들은학습데이터로사용한다. 정확도추정은 k 번의반복으로부터정확하게분류가된전체수를초기데이터의샘플수로나눈것 ( 재현율, Recall) 이된다 [3]. 재현율 R 은식 (6) 과같다 [20]. R = overall number of correct recommendation total number of samples (6) 또한 k 번의실험에서평균절대오차율 (Mean Absolute Error) 을측정해서성능을평가한다. 평균절대오차율은예측된평가값이최소화되어야정확도가높다고할수있다. 대상집합의실제포인트값을 {r 1,..., r n} 이라한다면, 예측포인트값은 {p 1,..., p n } 으로표현하고, 오차 E = {e 1,..., e n } = {p 1 - r 1,..., p n - r n} 이라면, 평균절대오차율은아래의식 (7) 과같다. N Σ e i i =1 E = N (7) 4.3 실험결과및평가 실험은우선, 기존의개인정보와상황정보만을고려한개인화된추천시스 - 23 -
템과본논문에서제안한위치기반의개인화된추천시스템사이의성능비교를하였다. 그리고가중치를고려한추천시스템과단순추천시스템과의정확성비교를위해최적의가중치를얻기위한실험도시행하였다. 끝으로기존추천시스템과제안한추천시스템, 그리고가중치를적용한추천시스템의성능비교를통해본논문에서제안한시스템의우수성을증명한다. 4.3.1 추천시스템비교 전통적인레스토랑추천시스템은기존의샘플데이터로부터유사한사용자들을분류해내는단계를첫단계로한다. 사용자의개인정보나상황정보를바탕으로의사결정트리같은분류도구를이용하여추천목록을생성함으로써개인화된추천의역할을한다. 하지만최근에는무선인터넷을통한사용자의위치와레스토랑의위치를파악할수있게됨으로써시간적, 공간적요소를추천에이용하게된다. 즉레스토랑까지의위치와거리가사용자의레스토랑선택에영향을미치므로위치기반의추천또한필요하게되었다. 본실험에서는단순개인화된추천시스템과위치기반의개인화된추천시스템을비교함으로써위치정보의중요성과함께제안하는시스템의우수성을증명하고자한다. 실험과정에서 K-중첩교차조사를방법을이용하였으며 K=10으로설정하였다. 개인정보와상황정보만을이용한개인화된추천시스템 (Recommendation based on Personalization, RP) 과위치기반의개인화된추천시스템 (Recommendation based on Personalization and Location, RPL) 을정확성과오차율을통해비교하였다. 두시스템의성능의차이를 [ 표 9] 과 [ 그림 7] 에나타내었다. - 24 -
[ 표 9] 재현율과 MAE 를통한 RP 와 RPL 시스템비교 시행 개인화된추천 위치기반의개인화된추천 횟수 재현율 MAE 재현율 MAE 1 76 34 80 32 2 78 36 80 32 3 78 38 82 34 4 76 36 80 32 5 76 36 82 34 6 80 40 84 36 7 76 34 80 32 8 78 36 82 30 9 76 36 82 32 10 78 38 84 32 평균 77.2 36.4 81.6 32.6 실험결과제안된추천시스템이재현율에서약 4.4% 의높은정확도와평균절대오차율에서약 7.4% 의낮은오차율을나타낸다. 즉사용자와레스토랑의위치를고려했을때더욱정확한추천의결과를가져옴을알수있다. 이번실험에서가중치는고려하지않았다. 재현율 & MAE(%) 90 80 70 60 50 40 30 20 10 0 1 2 3 4 5 6 7 8 9 10 시행횟수 (k=10) [ 재현율 ] 개인화된추천시스템 [ 재현율 ] 위치기반의개인화된추천시스템 [MAE] 개인화된추천시스템 [MAE] 위치기반의개인화된추천시스템 [ 그림 7] 재현율과 MAE 를통한추천시스템비교 - 25 -
4.3.2 가중치결정 레스토랑선택에있어서개인정보와상황정보등의개인화요소가미치는영향과사용자나레스토랑의위치가미치는영향을알아내기위해가중치를설정한다. [ 그림 8] 에서는개인화된추천목록에 0.3의가중치를위치기반추천목록에는 0.7의가중치를적용한후에재현율과평균절대오차율을구한다. 가중치값을 0.1씩증감시켜서최적의가중치값을찾아낸다. 90 80 70 60 50 40 30 20 10 0 0.3/0.7 0.4/0.6 0.5/0.5 0.6/0.4 0.7/0.3 가중치 ( 개인화 / 위치기반 ) 재현율 (%) 평균절대오차율 (%) [ 그림 8] 가중치에따른재현율과평균절대오차율실험결과개인화된추천목록에 0.4, 위치기반추천목록에 0.6의가중치를적용하였을때, 83% 의재현율과 28% 의오차율을기록하였다. 즉, 사용자들의레스토랑선택시의관심사가위치에좀더치우쳐있음을알게되었다. 4.3.3 성능비교평가 위의두실험을통해위치기반의개인화된추천시스템의우수성과개인정 보나상황정보보다위치정보가레스토랑선택에많은영향을미친다는것을 - 26 -
증명하였다. [ 표 10] 과 [ 그림 9] 에서는가중치가적용된위치기반의개인화 추천시스템 (Recommendation based on Personalization and Location with Weightiness, RPLW) 과기존추천시스템을비교한다. 가중치를 0.4 와 0.6 으로부여한제안된시스템이재현율은가장높고오차율은가장낮게나 타남을알수있다. [ 표 10] 재현율과 MAE 를통한 RP, RPL, RPLW 추천시스템비교 시행 RP RPL RPLW 횟수 재현율 MAE 재현율 MAE 재현율 MAE 1 76 34 80 32 84 26 2 78 36 80 32 86 28 3 78 38 82 34 86 30 4 76 36 80 32 82 26 5 76 36 82 34 86 28 6 80 40 84 36 88 32 7 76 34 80 32 82 26 8 78 36 82 30 82 28 9 76 36 82 32 84 28 10 78 38 84 32 86 30 평균 77.2 36.4 81.6 32.6 84.6 28.2 100 재현율 & MAE (%) 90 80 70 60 50 40 30 20 10 0 1 2 3 4 5 6 7 8 9 10 11 시행횟수 (k=10) [ 재현율 ] RP [ 재현율 ] RPL [ 재현율 ] RPLW [MAE] RP [MAE] RPL [MAE] RPLW [ 그림 9] RP, RPL, RPLW 추천시스템비교 - 27 -
제 5 장결론및향후연구 본논문에서는사용자의이동성을고려하여위치를기반으로한개인화된레스토랑추천시스템을제안하고실험을통하여성능을평가하였다. 기존의사용자의개인정보분석을통한단순한추천시스템은사용자의시간적, 공간적사항을고려하지않음으로써사용자에게적절한정보및서비스임에도불구하고제기능을발휘하지못하였다. 최근무선인터넷의발전에힘입어 GPS와무선데이터전송능력이있는휴대용기기및무선컴퓨팅기술의발전은사용자와레스토랑의위치정보를서비스에이용할수있도록하였다. 따라서개인의취향에따른레스토랑추천과함께위치정보를바탕으로한거리와시간에따른추천을시도하게되었다. 개인화된추천을위해서사용자의성별, 나이, 직업같은개인정보와날씨, 온도등의상황정보를분석하여레스토랑선택과의관계를찾아내었다. 분석과정에서가장널리알려진데이터마이닝기법중의하나인의사결정트리기법을이용하였다. 또한위치정보를기반으로한레스토랑추천목록을생성함으로써사용자의이동성을고려하게되었다. 이에더불어개인화와위치기반의추천을결합한최적의추천서비스제공을위하여각각의추천목록에가중치를도입하였다. [ 그림 7] 의실험을통해서레스토랑선택에있어서개인정보보다위치정보가미치는영향이컸음을알수있었고기존의개인화를바탕으로한추천보다위치까지고려한추천시스템이향상된성능을나타내었다. [ 그림 9] 에서와같이본논문에서제안한시스템이단순개인화바탕의추천시스템과가중치가고려안된시스템보다재현율에서 7.2%, 7.8% 높은정확성을나타내었고, 오차율에서는 3.0%, 4.4% 낮게평가되었다. - 28 -
이러한실험결과를바탕으로제안하는시스템의장점을정리하면다음과같다. 첫째, 사용자의개인적인관심사뿐만아니라위치까지고려함으로써추천의정확성을높이고오차율을낮추게되었다. 둘째, 개인정보와위치정보에가중치를적용하여최적의추천서비스를제공하게되었다. 향후연구로는, 첫째, 본논문에서개인화과정에서고려하였던상황정보에대한폭넓은이해와연구가필요하며, 둘째, 의사결정기법에서변수의증가가정확도의상승을가져오는것은사실이나수없이많은변수들을고려하기엔한계가있다. 그리하여레스토랑선택과더욱밀접한변수를찾아내는과정이요구된다. 마지막으로, 실제모바일기기사용자들이사용할수있는시스템을개발하여실제이용과정에서발생하는문제점의파악과개선을통해시스템의성능을향상시킬수있을것이다. - 29 -
참고문헌 [1] Agrawal, R., Srikant, R., "Fast Algorithms for Mining Association Rules," In Proceedings of the 20th International Conference on Very Large Data Bases, pp.487-499, 1994. [2] Goren, D., Kuflik, T., "Recommending restaurants through an adaptive mobile system," In Proceedings of the 9th international conference on Intelligent User Interface, 2004. [3] Han, J., Kamber, M., "Data Mining: Concepts and Techniques," Morgan Kaufman, 2001. [4] Herlicker, J.L., Konstan, J.A., Borchers, A., Riedl, J., "An Algorithmic framework for performing collaborative filtering," In Proceedings of the Twenty Second Annual International ACM SIGIR Conference, ACM Press, pp.230-237, 1999. [5] http://www.amazon.com [6] http://www.cdnow.com [7] James, C., Gordon, L., "Subscriber Location in CDMA Cellular Networks," IEEE Transactions on Vehicular Technology, 1998. [8] Jeffrey, H., Kevin, J., Brian, D., and Theodore, S., "An Overview of the Challenges and Progress in Meeting the E-911 Requirement for Location Service," IEEE Communication Magazine, 1998. [9] Kasanoff, B., "Are You Ready for Mass Customization?," - 30 -
Training Vol.35, No.23, pp.23-34, 1998. [10] Mark, M., Norman, K., "An Introduction to Snaptrack Server-Aided GPS Technology," ION-GPS98, 1998. [11] Mobasher, B., Dai, H., "Effective Personalization Based on Association Rule Discovery from Web Usage Data," In Proccedings Web Information and Data Management, pp.9-15, 2001. [12] Park, K., Lee, H., "Study on Family Restaurant Recommendation for Customers based on Benefit Sought and Demographical Variables," In Proceedings on The Korea Academic Society of Tourism and Leisure, 2003. [13] Sachin, S., Pravin, V., Yugyung, L., "Context-aware Data Mining using Ontologies," LNCS 2813, 2003. [14] Schafer, J.B., Konstan, J.A., Riedl, J., "Recommender Systems in E-Commerce," In ACM Conference on Electronic Commerce, pp.158-166, 1999. [15] Seneff, S., Polifroni, J., "A New Restaurant Guide Conversational System: Issue In Rapid Prototyping For Specialized Domains," In Proceedings of Fourth International Conference on ICSLP, Vol.2, 1996. [16] Shardanand, U., Maes, "Social Information filtering: Algorithms for automating word of mouth," In Conference on Human Factors in Computing System, 1995. [17] Shih, G., Shim, S., "A service management framework for - 31 -
M-commerce applications," In Proceedings of Mobile Networks and Applications, Vol.7, 2002. [18] Srivastava, J., Cooley, R., Deshpande, M., Tan, P.N., "Web-Usage Mining: Discovery and Application of Usage Patterns for Web data," In ACM SIGKDD Exploration, Vol.1, pp.12-23, 2000. [19] Tung, H., Soo, V., "A personalized restaurant recommender agent for mobile e-service," e-commerce and e-service, 2004. IEEE International Conference on 28-31, 2004. [20] Yang, Y., Liu, X., "A re-examination of text categorization methods," In Proceedings of SIGIR-99, 1999. [21] 김욱, 지규인, 이장규, " 위치기반무선인터넷서비스," Telecommunications Review 제 10권 6호, pp.1260-1269, 2000. [22] 윤현준, " 개인화의전개와지형점," Web Leader Magazine, 2001년 6월특집기사, 2001. - 32 -