본 논문에서는 집합과 계층구조 개념을 이용하여 데이터스트림에서 새로운 유사 시퀀스 매칭 기법인 SHS(Set and Hierarchy-based Similar sequence matching)를 제안하였다. 데이터스트림이란 시간의 흐름에 따라서 계속해서 순차적으로 무한히 생성되는 데이터를 말한다. 이러한 데이터스트림의 환경은 대량의 데이터가 실시간으로 빠르고 무한하게 들어오는 특징을 갖는다. 인터넷과 이동통신의 발달에 힘입어 네트워크 패킷, 이동통신 통화기록, 주식시세 변화 데이터 등 다양한 데이터스트림들이 사용되고 있는데, 본 논문에서는 사용자별로 시간에 따라 선호한 영화의 평점 데이터를 주요 대상 데이터스트림으로 하였다. 최근 디지털 기기의 보급과 소셜 네트워크 서비스의 발전으로 인해 영화에 대한 평점 데이터를 사용자들이 언제 어디서나 실시간으로 계속해서 생성할 수 있게 되면서, 예전에는 정적인 데이터로 보았던 영화 평점 데이터를 동적인 데이터스트림으로 모델링 할 수 있게 되었다.
그리고 데이터스트림 처리 응용으로는 영화 평점을 사용한 추천 시스템(Recommendation Systems)에 초점을 맞춰 연구를 수행하였다. 추천 시스템은 수많은 아이템 중에서 사용자가 선호할만한 아이템을 추천해주는 시스템이다. 추천 시스템의 가장 널리 쓰이는 알고리즘은 협업 필터링(collaborative filtering)이다. 협업 필터링은 추천 서비스를 받을 액티브 사용자(active user)와 유사한 다른 사용자를 찾고, 이렇게 찾은 유사 사용자가 선호한 아이템 중에서 액티브 사용자가 선호한 적이 없는 다른 아이템을 추천하는 방식이다. 협업 필터링은 전적으로 유사한 사용자를 기반으로 추천을 수행하므로 유사 사용자를 정확하게 찾는 것이 무엇보다 중요하다. 본 논문에서는 협업 필터링의 핵심 요소인 유사 사용자 매칭 방법을 보다 정확하게 수행하기 위해 해당 문제를 데이터스트림에서의 유사 시퀀스 매칭으로 변환하여 해결하였다.
SHS는 다음의 세 가지 특징을 갖는다. 첫 번째로 시간의 흐름에 따른 사용자의 선호에 집합 개념을 도입한 “선호 아이템 집합 시퀀스” 구조를 제안하였다. 사용자의 선호에 단순히 시간 정보만을 추가하여 유사 사용자 매칭을 수행하면 두 사용자가 공통으로 선호한 아이템이 정확히 같은 순서에 존재해야 유사한 사용자로 선정되고 조금이라도 순서가 다르면 유사하지 않다고 판단되는 문제가 있다. 본 논문에서는 이러한 문제를 해결하기 위해서 시간의 흐름에 따른 사용자의 선호를 일정 시간 간격씩 모아서 집합으로 묶음으로써 해당 일정 시간 간격 안에서는 사용자의 선호 아이템의 시간 정보가 정확히 일치하지 않아도 유사한 사용자를 찾아낼 수 있는 방법을 제시하였다. 이때 아이템 집합 시퀀스 간의 유사도를 측정하기 위해 유클리디안 거리를 집합으로 확장한 유클리디안 집합 거리를 제안하였다.
두 번째로 사용자의 선호에 아이템의 계층구조를 고려한 매칭 방법을 제안하였다. 기존의 협업 필터링은 단순히 두 사용자 간의 공통되는 아이템의 정보만을 통해 시간에 따라서 더 많은 공통 선호 아이템이 존재할 경우 유사한 사용자로 선정하였다. 이러한 기존 방법은 두 사용자가 실제로는 선호도가 유사할지라도 공통적으로 선호도를 표시한 아이템의 수가 적으면 유사 사용자로 선정되지 않는 문제가 있었다. 이러한 문제를 선호 데이터 희소 문제라고 하며, 유사 사용자 매칭의 성능을 저하시키는 대표적인 이유이다. 본 논문에서는 아이템 그 자체만을 비교하는 것이 아니라, 계층구조를 갖는 아이템 속성까지도 유사도 판단에 고려함으로써 이러한 문제를 해결하는 방법을 제시하였다.
세 번째로 유사 사용자 매칭 문제를 유사 시퀀스 매칭 문제로 변환하여 사용자의 선호를 최근의 시점에서만 검색하는 것이 아니라 과거의 모든 시점에 대해서도 검색이 가능하도록 하였다. 사용자의 선호는 변화하므로 현재 액티브 사용자의 최근 선호와 유사한 선호를 과거에 가졌었던 다른 사용자가 존재할 수 있다. 본 논문에서는 과거 시점의 유사 사용자를 찾을 수 있도록 하기 위해서 액티브 사용자의 최근 선호와 다른 사용자들의 현재 시점뿐만 아니라 과거 시점까지 검색하는 서브 시퀀스 매칭 방법을 제안하였다. 또한 제안한 유사 시퀀스 매칭을 수행할 때에 실제로 유사하지만 유사하지 않다고 판단되는 착오기각이 발생하지 않음을 증명하였다.
실험 결과, 제안하는 SHS가 실제 영화 평점 데이터에서 유사 시퀀스 매칭을 수행하여 기존의 방법보다 유사한 사용자를 보다 정확히 찾아내는 것을 보였다. 이러한 결과로 볼 때 본 논문에서 제안하는 SHS가 데이터스트림 환경의 추천 시스템에서 보다 정확한 추천을 가능하게 하는데 유용하게 활용될 수 있을 것으로 판단된다.

In this thesis, we have proposed a new technique for similar sequence matching in data streams which we call it as Set and Hierarchy-based Similar Sequence Matching(SHS). A data stream is a sequence of data entries that continuously arrive in a sequential order. Due to advances in Internet and mobile communication technologies, there are many types of data streams in real applications such as network packets, mobile phone call logs, and stock quotes data. As a target data stream, we have focused on the movie rating data which reflect the preference of users over time. In the past, the movie rating data is considered as static data, but now it can be modeled as dynamic data streams because users can rate movies in real time, anytime, and anywhere due to the recent spread of digital communication devices and social network services,
As a target data stream application, we have focused on Recommendation Systems(RSs) using the movie rating data. RSs produce a list of recommended items that the active user may have an interest. The most widely used algorithm for RSs is collaborative filtering. Collaborative filtering first find similar users who have similar interests with the active user, and then recommend items that preferred by the similar users but not rated by the active user. The most important step for collaborative filtering is to exactly find similar users because recommended items are completely gleaned from the similar user. In order to improve accuracy of finding similar users, we have transformed the similar user matching problem into the similar sequence matching problem in data streams.
Our SHS has the following three characteristics. First, we have proposed the preferred item set sequence which reflects the time concept of user preference. A preferred item set sequence is an ordered list of sets where each set collects preferred items within in a specific time interval. We also have proposed a similarity measurement between item set sequences, the Euclidean set distance, which extends Euclidian distance.
Second, we have exploited the item hierarchy concept of attributes for similar sequence matching. The existing collaborative filtering method identifies similar users based on idea that the more common preferred items two users have, the more similar they are. However, this method has a problem that two users who have actually similar interests are not matched as similar users when they have only a few number of common preferred items. This is a data sparsity problem and considered as a major reason reducing the accuracy of the similar user matching. To solve the data sparsity problem, we have proposed a method for the similar user matching using not only preferred items themselves but also the attribute hierarchies of the items.
Third, in order to find the similar user not only in current time but also in past time, we have transformed the similar user matching problem into the similar subsequence matching problem. We also have proved that the method does not incur false dismissals which are actually similar to the active user but discarded in the results of the similar sequence matching.
Through experiments with real data sets, we have shown that SHS provides higher accuracy than the existing method for finding similar users. From the experiment results, we consider that our SHS is a practical and useful method for improving accuracy of RSs in data stream.