협력적 필터링 추천 시스템의 성능 향상 = Performance Improvement of a Collaborative Filtering Recommender System

국문 초록 (Abstract)

정보기술과 인터넷 기술의 발전은 정보의 양을 크게 증가시키고 있다. 그러나 정보량의 증가는 사용자가 원하는 정보를 찾기 위한 노력과 시간을 증가시킨다. 데이터마이닝은 이와 같은 대량의 정보 중에서 사용자가 원하는 정보를 적은 노력으로 단시간에 찾을 수 있도록 도와준다. 데이터마이닝은 마케팅, 생산관리, 의료 등의 다양한 분야에서 응용되고 있다. 마케팅 분야에서 추천 시스템은 데이터마이닝을 이용하여 사용자나 상품 등과 같은 정보를 분류하고 분석하여 목표고객의 기호에 맞는 상품을 추천해준다.
추천에는 내용기반 필터링과 협력적 필터링의 두 가지 기법이 있다. 내용 기반 필터링은 상품의 특징을 나타내는 속성과 목표고객의 기호를 가지고 있는 프로파일을 비교하여 이 두 가지 요소가 일치하는 상품을 찾아서 추천한다. 반면에 협력적 필터링은 목표고객에 대해서 유사한 기호를 가진 이웃사용자를 찾고 그 이웃사용자가 평가한 상품의 선호도를 이용하여 목표고객에게 상품을 추천한다. 협력적 필터링은 내용 기반 필터링으로 찾을 수 없는 잠재적인 추천 상품을 발견할 수 있기 때문에 추천 시스템에서 많이 사용되는 방법이다.
협력적 필터링에서 추천의 정확도를 향상시키기 위해서는 목표고객에 대한 이웃사용자를 정확하게 선정해야하고 상품에 대한 목표고객의 선호도를 정확하게 예측하며 예측된 선호도를 이용하여 목표고객의 기호에 맞는 추천목록을 정확하게 생성해야한다.
본 연구에서는 협력적 필터링을 기법을 적용한 추천 시스템에서 추천의 정확도를 향상시키기 위해 다음과 같은 세 가지 방법을 제시하였다.
첫째, 사용자를 유사도에 따라 정확하게 군집할 수 있는 중심이동확장(EMC ; Expanded Moving Center) 휴리스틱 군집 알고리즘을 고안하였다. EMC 휴리스틱 군집 알고리즘은 초기에 군집의 중심배치 방법을 개선함으로써 초기해보다 개선된 해를 찾을 수 있는 확률을 증가시켰고 군집의 중심간 간격을 변경해나가면서 최적해에 근사한 해를 체계적으로 탐색할 수 있다. 한편으로 군집에 소요되는 계산량을 줄여서 군집의 효율을 향상시켰다. EMC 휴리스틱 군집 알고리즘의 성능은 실제로 고객의 선호도를 조사한 MovieLens 데이터를 사용하여 실험하였다. 군집의 수를 변화시키면서 EMC 휴리스틱 군집 알고리즘의 성능을 실험한 결과, 모든 군집 수에서 EMC 휴리스틱 군집 알고리즘에 대한 제곱오차(군집의 성능을 평가하는 척도)는 타 알고리즘의 제곱오차에 비해 항상 좋은 결과를 나타내었다. 그리고 군집의 수가 많아질수록 타 알고리즘에 비해서 제곱오차의 개선 폭이 점차적으로 증가하였다. 이 군집 알고리즘이 추천 시스템의 추천 정확도를 향상시킬 수 있는지 확인하기 위해 이 군집 알고리즘을 추천 시스템에 적용한 결과, 추천의 정확도는 기존의 알고리즘을 적용했을 경우에 비해서 향상되었다.
둘째, 기존의 선호도 예측방법을 개선한 이웃사용자 중심의 선호도 예측방법을 제시하였다. 이웃사용자 중심의 선호도 예측방법은 기존의 선호도 예측방법에 비해서 선호도 예측의 정확도를 높일 수 있다. 기존의 선호도 예측방법은 목표고객이 입력한 선호도 정보를 선호도 예측에 사용한다. 그러나 입력한 선호도 정보가 적을 경우 선호도 예측의 정확도가 낮아지는 문제가 발생한다. 본 연구에서 제시한 이웃사용자 중심의 선호도 예측방법은 목표고객의 이웃사용자가 입력한 선호도를 바탕으로 선호도를 예측한다. 이웃사용자의 선호도 정보량은 목표고객에 비해서 항상 많기 때문에 정보량이 증가하여 선호도 예측의 정확도를 높일 수 있다. 본 연구의 이웃사용자 중심 선호도 예측방법을 추천 시스템에 적용한 결과, 추천의 정확도는 기존의 선호도 예측방법을 사용했을 경우에 비해서 향상되었다.
셋째, 연령속성을 반영한 추천순위 결정방법을 고안하였다. 기존 추천 시스템에서는 상품의 추천순위를 결정할 때 예측 선호도가 높은 순서로 추천순위를 결정하였다. 그러나 본 연구에서는 예측 선호도 외에도 목표고객과 이웃사용자의 연령속성을 반영한 추천순위 결정방법을 사용하여 추천목록을 생성하기 때문에 보다 정확한 추천목록을 생성할 수 있다. 본 연구에서 제시한 추천순위 결정방법을 추천 시스템에 적용한 결과, 추천의 정확도는 기존의 예측 선호도만을 반영한 추천순위 결정방법에 비해서 향상되었다.
본 연구에서 제시한 세 가지 방법을 적용한 추천 시스템의 실험결과는 본 연구와 동일한 MovieLens 데이터를 사용한 기존 연구의 추천 실험결과와 비교하였다. 그 결과 본 연구의 추천 정확도는 기존의 연구에 비해서 향상되었음을 확인하였다.

다국어 초록 (Multilingual Abstract)

The development of information and internet technology has added great amount of information. However, this mass information causes users to spend much effort and time to find information they need. Data mining is a technology which helps the user to find information they need in a short time with low effort out of mass information. Data mining is applied in various fields such as marketing, product management and medical treatment. In marketing, a recommender system recommends some items to a target customer using data mining by classifying and analysing information concerning the customers or the items.
There are two methods of recommendation. One is content-based filtering, and the other is collaborative filtering. In content-based filtering, the system compares characteristics of an item and the profile of the target customer's preference and recommends some items which fit to the target customer's preference. In collaborative filtering, the system searchs for the user groups sharing similar preferences, predicts the preference of the target customer based on the preferences of the neighbour customers, and recommends the items. Collaborative filtering is applied in many recommender systems because it can find potential items which can not be selected by content-based filtering.
Selection of the correct target customer is necessary to raise the accuracy of the recommendation in collaborative filtering. The accurate estimation of the target customer's preference for the item and creating a proper recommend list of the items which fit to the target customer's preference should be proceeded.
In this paper, the author proposed following three methods to improve the accuracy of the recommender system.
First, the author devised a clustering algorithm, that is, EMC(Expanded Moving Center) heuristic algorithm, which can classify the users more accurately according to preferences. The developed EMC heuristic algorithm increases probability to find better solution than the initial solution by the improving method to assign the cluster center at the beginning of clustering process, and it can search for the optimal solution systematically by changing interval from the center of clusters. Additionally, the efficiency of clustering is increased by reducing the computing complexity in clustering. Performance of EMC heuristic algorithm was tested using actual data surveyed from customers, MovieLens. In the experiments of changing the number of clusters, the Squared-error(evaluation value of clustering) of the EMC heuristic algorithm always showed good results than other clustering algorithms in all cluster numbers, and the Squared-errors are improved gradually than other algorithms as the numbers of clusters increased. Also, in the recommender system, the recommendation accuracy is improved when the EMC heuristic algorithm was applied to cluster users than other clustering algorithms.
Second, the author proposed the Neighborhood-oriented preference prediction method that improved the conventional preference prediction methods. Neighborhood-oriented preference prediction can improve the accuracy of the preference prediction than the conventional preference prediction methods. The current preference prediction method has used the target customer's preference for preference prediction. It can cause the low accuracy in preference prediction if the data of the target customer's preference is not enough. But, the preference prediction method suggested in this paper can improve the accuracy of the preference prediction because the quantity of the preference information increased by using neighborhood's preference instead of the target customer's. By applying the Neighborhood-oriented preference prediction method to the recommender system, the accuracy of recommendation improved more than the current preference prediction method.
Third, the author devised a new recommendation ordering method attributed by the user's age. In the conventional recommendation system, the recommendation order is decided according to the high preference prediction. However, in this paper, the recommendation accuracy is improved by the decision recommendation order method that reflects the age attributes of the target customer and neighborhood in preference prediction. By applying the decision recommendation order method to the recommender system, the recommendation accuracy is improved more than that of the conventional ordering method of recommendation.
The test result of the recommendation system which adapted the above three methods suggested in this paper was compared with the result from the conventional recommendation when sharing the same MovieLens data. The recommendation method that was proposed in this paper confirmed the improvement of the recommendation accuracy compared with other studies.

목차 (Table of Contents)

• 요약 Ⅰ
• Abstract Ⅳ
• 표 목차 Ⅸ
• 그림 목차 Ⅺ
• 제 1 장 서론 1
• 제 2 장 이론적 배경 4
• 2.1 군집 알고리즘 4
• 2.1.1 k-means 알고리즘 5
• 2.1.2 타부 탐색 알고리즘 7
• 2.2 추천 시스템 10
• 2.2.1 협력적 필터링 11
• 2.2.2 이웃사용자 선정 16
• 2.2.3 유사도 가중치 17
• 2.2.4 선호도 예측 19
• 제 3 장 연구목적 및 방법 22
• 3.1 연구목적 22
• 3.2 연구방법 및 구성 23
• 제 4 장 EMC 휴리스틱 군집 알고리즘 25
• 4.1 EMC(Expanded Moving Center) 휴리스틱 군집 알고리즘 25
• 4.1.1 초기 군집의 중심 등간격 배치 26
• 4.1.2 군집의 중심간 간격 설정 32
• 4.1.3 EMC 알고리즘 34
• 4.1.4 군집의 계산효율 향상 38
• 4.1.5 EMC 알고리즘 실행 예 39
• 4.2 EMC 휴리스틱 군집 알고리즘 성능평가 44
• 4.2.1 실험방법 44
• 4.2.2 군집 프로그램 44
• 4.2.3 실험 데이터 46
• 4.2.4 실험결과 49
• 제 5 장 추천 시스템 54
• 5.1 추천 시스템 54
• 5.1.1 사용자 군집 및 이웃사용자 선정 56
• 5.1.2 추천영화 후보선정 57
• 5.1.3 이웃사용자 중심 선호도 예측방법 58
• 5.1.4 연령속성을 반영한 추천순위 결정방법 61
• 5.2 추천 시스템 성능평가 65
• 5.2.1 실험방법 66
• 5.2.2 추천 프로그램 69
• 5.2.3 실험 데이터 70
• 5.2.4 성능평가 지표 78
• 5.2.5 실험결과 80
• 제 6 장 결 론 111
• 참고문헌 114