아키텍처 중심의 인수 테스트 자동화 기법

류동국 서강대학교 정보통신대학원 2015 국내석사

In the past days, the acceptance test was the last means to secure the qualiy by verifying requirements after the past development. Then, its importance has been gradually increased, since it is the specifics as the fundamental target of development through the cooperation between business manager, developer, and tester from the beginning. It also describes viable tests, and from then on, methodologies such as ATDD and BDD which perform development have been on the rise. It means it has been studied to be improved as viable specifics, being specifics and test, and furthermore, a living documentation system that can be utilized constantly throughout the product life cycle. As a practical method to establish a physical basis for the development, architecture centric acceptance test automation method is suggested in this study. It first draws an architecture driver, centering on “Specification by Example” the essential concept of ATDD. Then, it presents a design of architecture fitting for securing legibility for specifics and test and maintenability. Lastly, it suggests methods to select tools based on specifics-based test automation which is suitable for the suggested architecture. Based on the architecture, in addition, the process that is applied to an actual project is introduced and evaluated. Our study will be able to contribute to realizing Test Driven Development on the basis of business centric communication by presenting architecture as a basis that is applicable to conceptual Agile development methodologies in practical and common ways. 인수 테스트가, 과거 개발 후 요구사항의 검증을 통한 마지막 품질 확보 수단에서, 초기부터 비즈니스 담당자와 개발자, 테스터 간의 협업을 통하여 개발의 궁극적인 목표로서의 명세이며 실행 가능한 테스트를 기술하고 이를 중심으로 한 개발을 수행하는 ATDD 또는 BDD와 같은 방법론이 대두되면서 그 중요성이 점차 증대되고 있다. 명세이자 테스트인 실행 가능한 명세, 그리고 더 나아가 제품 life cycle 전반에서 지속적으로 활용될 수 있는 리빙 도큐멘테이션 시스템으로서의 발전이 모색되고 있는 것이다. 이를 위한 물리적 기반을 마련하는 데 있어서의 실천적인 방법으로서 아키텍처 중심의 인수 테스트 자동화 기법을 제안하였다. 이는 ATDD의 중요 개념인 ‘예제를 활용한 명세’ 중심으로 아키텍처 드라이버를 도출하여, 명세 및 테스트로서의 가독성과 유지보수성 확보에 적합한 아키텍처의 설계, 그리고 제안된 아키텍처에 적합한 명세 기반 테스트 자동화 기반 도구의 선정 방법 순으로 제안되었다. 또한, 제안된 아키텍처를 기반으로 실제 프로젝트에 적용하는 프로세스를 소개하고 평가를 수행하였다. 본 연구는 개념적인 테스트 주도 애자일 개발방법론의 적용에 있어, 공통적으로 반복 활용 가능한 기반으로서의 big picuture인 아키텍처를 제시함으로써, 비즈니스 중심 소통에 기반한 테스트 주도 개발방법 (Test Driven Development) 실천에 기여할 것이다.

확장된 질의 처리를 위해 고안된 경로간 의미적 유사도를 고려한 XML 문서 순위화 기법

김현주 서강대학교 일반대학원 2009 국내석사

XML은 정보를 효율적으로 저장하고 처리 할 수 있는 언어로써 현재 널리 사용되고 있다. XML은 구조적인 특성을 가지고 있는데 XML로 작성된 문서에서 원하는 정보를 얻고자 할 때 사용자는 구조적 정보를 이용한 XPath를 사용하여 질의한다. XPath질의는 XML문서와 비교하여 양측에서 사용하는 용어와 그 용어들의 구조가 동일할 시에만 정상적으로 처리될 수 있는데 최근의 Web환경에서는 다양한 내용의 정보가 다양한 구조를 가진 XML문서로 작성되므로 사용자가 모든 문서에서 사용한 용어와 구조를 알 수 없다. 따라서 사용자는 정상적으로 처리되기 어려운 형태의 질의를 작성하기 쉬운데 이 경우 문서 측에서 사용자가 얻고자 하는 정확한 정보 혹은 유사한 정보를 가지고 있는 경우가 적지 않음에도 질의 측과 문서 측의 용어적, 구조적 차이 때문에 번번히 해당 질의가 거절된다면 정보의 낭비와 이로 인한 질의 처리의 비효율이 발생된다. 따라서 본 연구에서는 이러한 문제를 해결하기 위해 다수의 문서를 대상으로 사용자가 특정한 정보를 얻기 위해 질의한 경우, 사용자 질의 측에서 사용한 태그(tag) 노드(node)들과 문서 측에서 사용한 태그 노드들의 용어와 구조가 동일한 경우 해당 문서를 사용자 질의에 대한 최 상위 문서로 판단하고 이러한 문서가 없을 시, 사용자 질의와 문서 측에서 사용한 용어가 상이(相異)하더라도 질의 측의 용어를 문서 측에서 처리해 줄 수 있는 형태로 변환해 주고, 이후 질의 측과 문서 측의 구조가 상이한 경우에도 사용자가 요구하는 정보 즉, 질의가 가지는 의미와 유사한 정보를 제공할 수 있는 문서들을 제안하는 경로 유사도 기법으로 찾아 다수의 문서들을 대상으로 사용자 질의와 의미적으로 유사한 순으로 순위화된 정보를 사용자 측에 제공한다. 따라서 사용자는 특별한 질의 재 작성 과정 없이 자신이 질의를 통해 요청한 정확한 정보는 물론 자신이 얻고자 한 정보와 의미적으로 유사한 순으로 순위화 된 결과를 제공 받을 수 있으며 본 연구에서는 사용자 질의와 문서간의 의미적 유사성을 측정하고 이를 이용해 사용자 질의에 의미적으로 가까운 순으로 문서를 순위화 하는 기법을 제시한다. XML is broadly using for data storing and processing. XML is specified its structural characteristic and user can quering with XPath when they want some information from data document. XPath query can process when the term and structure of document and query is matched with each other. However, nowadays there are lots of data documents which are made by using different terminology and structure therefore user can not know the exact idea of target data. Actually there are many possibilities that target data document has information which user is find or a similar ones. Accordingly user query should be processed when their term usage or structural characteristic is slightly different with data document. In order to do that we suggest a XML document ranking method based on path similarity. The method can measure a semantic similarity between user query and data document using three steps which are position, node, relaxation factors.

차분 프라이버시가 적용된 사용자 위치 기반의 최대 영향력 위치 선택 기법

박세화 서강대학교 대학원 2021 국내박사

During the past decades, it is possible to collect an individual location data due to the widespread use of mobile devices and social network services. The location based service providers have a great opportunity to provide more user friendly services through the data analysis. Especially, the optimal location selection queries have been of intense interest to the spatial database community. The location information of each client should be collected to process such a query. However, client location is considered sensitive information. Therefore, a privacy protection technique should be applied to optimal location selection problems. In this thesis, we propose a optimal location selection query-processing technique with differentially private client location information. Differential privacy is a de-facto standard privacy protection technique that applies a randomized mechanism to add controlled noise into statistical query results. Differential privacy has immunity from the linkage attack, while the existing techniques such as k-anonymity and l-diversity are vulnerable to it. Also, differential privacy can quantify the degree of privacy protection level using a privacy budget. Therefore, this study aims to propose an efficient optimal location selection query processing technique while protecting user's location with differentially private manner. Optimal location selection query is a traditional problem that identifies the most influential object in a given database which consists of potential objects $P$, existing facilities $F$, and client locations $C$. At this time, it is necessary to collect individual differentially private data, or to apply the differential privacy mechanism during the query processing of optimal location selection. In the former case, it is inevitable to decrease the query accuracy, so we propose a framework to apply a Laplace mechanism to an objective function of optimal location selection query. In addition, we present the influence region overlapping problem while applying differential privacy using the conventional approach. To remedy this problem, we propose a Voronoi region partitioning method to guarantee query accuracy. Furthermore, we present a network Voronoi region-based technique for the road network data. A Voronoi region partitioning method divides the Voronoi region of a potential location according to the combination of overlapping area, and it counts the number of clients in the partitioned region with differentially private manner. Then, it changes a sequential composition to a parallel composition while applying differential privacy to the optimal location selection query. Thus, it mitigates the degradation of accuracy due to the sequential composition. However, it needs more query processing time to compute the combination of overlapping area. In addition, we cannot exploit the existing pruning techniques because we cannot use the information of clients to prevent low accuracy problem. To address this issue, we propose a Voronoi envelope-based pruning heuristic to improve query performance. The Voronoi envelope-based pruning method which exploits existing facilities instead of the client's location. Also, we perform experiments of a real social network service and a real road network dataset to present that our proposed methods are enough to apply to real application services. 최근 모바일 환경의 보급과 기술 발전으로 인해 서비스 제공자가 사용자들의 위치 데이터를 직접 수집하고 분석하는 것이 가능해졌다. 그로 인해, 서비스 제공자들은 수집된 데이터를 이용해 사용자들에게 만족도 높은 서비스를 제공할 수 있게 되었다. 그 중에서도 최적장소 선택 질의(optimal location selection query)는 사용자들에게 영향을 가장 많이 끼칠 수 있는 최적장소를 찾아주는 질의로 상권 분석이나 공공기관 설치와 같은 실용적인 응용서비스에 적용될 수 있어 많은 연구자들의 관심이 집중되고 있다. 최적장소 선택 질의를 처리하기 위해서는 우선 개별 사용자들의 위치 정보를 수집해 분석해야 한다. 그러나 개인 위치 정보는 민감한 정보로 취급되기 때문에 무분별한 위치 정보 수집은 심각한 개인정보 노출 문제를 야기할 수 있다. 이와 같은 프라이버시 문제를 해결하기 위해서는 최적장소 선택 질의를 처리할 때 개인정보 보호 기법을 적용할 필요가 있다. 본 연구에서는 최적장소 선택 질의 중 가장 보편적인 최대 영향력 문제에 개인 위치정보를 보호하기 위한 차분 프라이버시(differential privacy)를 적용해 처리하는 방법에 대해 소개한다. 차분 프라이버시는 개인정보 보호기법 중 사실상의 표준으로 자리 잡고 있는 기술로서, 개별 사용자의 정보를 가린 채 전체 사용자 집단의 통계적인 정보를 제공할 수 있다는 장점을 지닌다. 특히, 다른 개인정보보호 기법들이 연결공격(linkage attack)에 취약한 반면, 차분 프라이버시는 연결공격으로부터 안전하다는 것이 기술적으로 증명되었다. 또한, k-익명화(k-anonymity), l-다양화(l-diversity)로 대표되는 개인정보보호 기법들이 데이터의 보호 정도와 유용성에 대한 정량화가 불가능했던 반면, 차분 프라이버시는 프라이버시 예산을 통해 질의 정확도와 개인정보 보호 정도에 대한 정량화가 가능하다는 장점도 지니고 있다. 그러나 차분 프라이버시를 적용할 경우 기존의 질의처리 기법을 그대로 사용하기 어렵다는 문제점이 있다. 따라서, 본 연구에서는 최대 영향력 위치 선택 과정 중에 차분 프라이버시를 적용해 사용자들의 위치정보를 보호하면서도 효율적으로 질의를 처리할 수 있는 방법을 제안하는 것을 목표로 한다. 최대 영향력 위치 선택 문제는 사용자들의 위치와 기존시설들의 집합이 주어진 상황에서 질의 요청자가 제시한 후보위치 집합 중 가장 적합한 위치를 찾는 질의를 말한다. 이 때, 사용자들의 개인정보를 보호하기 위해서는 처음부터 차분 프라이버시 기법이 적용된 개별 사용자의 정보를 수집하거나 질의처리 과정 중에 차분 프라이버시 매커니점을 적용해야 한다. 그러나 전자의 경우 질의 정확도가 매우 크게 하락하므로 본 연구에서는 질의처리 과정 중에 차분 프라이버시 기법을 적용한다. 또한, 차분 프라이버시 기법을 최대 영향력 문제에 단순하게 적용할 경우 후보위치들의 영향지역(influence region)이 중첩됨으로 인해 사용자 정보가 중복 노출되는 문제가 발생한다. 이런 문제를 해결하기 위해 보로노이 영역 분할 방법 기반의 빠르면서도 정확한 최적장소 질의처리를 수행하는 방법을 제안한다. 아울러 공간 데이터는 크게 유클리드 공간과 도로망 환경 데이터로 구분되므로 각각의 환경에 맞는 질의처리 방법을 제시한다. 보로노이 영역 분할 기법은 후보위치의 영향지역을 중첩 영역의 조합에 따라 분할하고, 분할된 영역마다의 사용자 수에 차분 프라이버시 기법을 적용한다. 이를 통해, 최대 영향력 위치 선택 문제에 차분 프라이버시를 적용할 때 발생하는 순차구성 문제(sequential composition)를 병렬구성(parallel composition)으로 변경함으로써 정확도를 향상시킬 수 있다. 그러나 이 과정에서 영역 조합을 구성하기 위해 필연적으로 질의처리 비용이 증가하게 되고, 순차구성으로 인한 정확도 하락을 방지하기 위해 질의처리 과정 동안 사용자 정보를 이용할 수 없기 때문에 기존의 사용자 정보 기반 가지치기 기법들을 사용할 수 없다. 본 연구에서는 사용자 정보 없이 질의처리 시간을 단축시키기 위해 공개 데이터인 기존시설 집합 기반의 확장 보로노이 영역을 새롭게 정의하고 이를 이용한 질의처리 기법을 제안한다. 아울러, 웹에 공개된 실제 소셜 네트워크 서비스 사용자들의 데이터와 도로망 데이터를 바탕으로 실험을 수행함으로써 제안 기법들이 실제 응용 서비스에 사용될 수 있는 수준의 정확도와 질의처리 시간을 지니고 있음을 보인다.

추천 시스템에서 차분 프라이버시 기반 사용자 그룹화를 이용한 유용도 향상 기법

김태완 서강대학교 대학원 2019 국내석사

모바일 기기와 인터넷 서비스의 급증으로 인터넷 사용자는 감당할 수 없이 많은 정보를 받아들이게 된다. 따라서, 사용자의 취향을 고려해 물품을 추천 해주는 추천 시스템이 필요하다. 하지만, 추천 시스템은 사용자의 개인 정보를 필요로 한다. 이를 지키기 위해 기존의 연구들에서 평점 정보에 차분 프라이버시를 만족시키는 노이즈를 삽입해 줬다. 하지만, 기존 연구에서는 두 가지 측면을 고려하지 않았다. 첫째, 사용자와 물품 사이의 희소성을 전혀 고려하지 않았다. 대부분의 인터넷 서비스는 사용자가 물품에 평점을 주는 횟수에 비해 새로운 사용자와 물품이 서비스에 유입되는 빈도가 월등히 많기 때문에, 평점의 개수에 비해 사용자와 물품이 훨씬 많게 된다. 따라서, 사용자와 물품에 대해 평점 행렬을 만들게 되면, 이 평점 행렬은 현저하게 희소성이 매우 높게 된다. 희소성이 높아 지면 추천 시스템에서 추천을 할 때 잠재적인 패턴을 파악하기 힘들다. 따라서, 평점 행렬의 밀집도를 고려한 추천 시스템이 필요하다. 둘째로, 기존의 프라이버시를 추천 시스템에 적용한 연구에서는 사용자들이 평점을 매긴 물품 목록에 대한 프라이버시를 보호하지 않았다. 사용자들의 평가 물품 목록은 또한 지켜야 할 프라이버시이므로, 이 또한 지킬 수 있는 추천 시스템이 필요하다. 따라서, 본 논문은 그룹화 기법을 통해 평점 행렬의 밀집도를 올림과 동시에, 사용자들의 평점 정보뿐만 아니라 사용자들의 평가 물품 목록에 대한 프라이버시를 지킬 수 있는 기법을 제안한다. 마지막으로, 실제 영화 평점 데이터를 가지고 제안 기법이 기존 차분 프라이버시를 추천 시스템에 적용한 연구들의 기법에 비해 추천 성능이 향상 됨을 보인다.

한정된 프라이버시 예산에서 배치 전략을 통한 차분 프라이버시 질의 처리 기법

강민석 서강대학교 대학원 2018 국내석사

최근 차분 프라이버시는 개인정보 보호 기법 분야의 사실상의 표준이 되었으며, 질의 처리에 이를 적용하는 기법들은 활발히 연구되고 있다. 차분 프라이버시는 공격자의 사전 지식과 무관하게 정보를 보호할 수 있다는 장점이 있지만, 이를 위해 매 질의마다 프라이버시 예산 소모가 발생한다. 질의에 적용된 프라이버시 예산이 클수록 질의의 결과는 정확해지지만 빠르게 프라이버시 예산이 고갈되어 많은 질의를 처리 할 수 없다. 많은 수의 질의를 처리하기 위해 각 질의에 대하여 프라이버시 예산을 지나치게 작게 할당하면 매우 높은 수준의 노이즈가 삽입되어 질의 결과의 정확도가 감소하고 이는 데이터 유용성을 저하시킨다. 때문에 매우 많은 질의를 처리해야 할 때, 프라이버시 예산은 적절하게 분배되어 할당되어야 한다. 그러나 한정된 프라이버시 예산 하에서 질의 결과의 정확도를 고려한 프라이버시 예산의 할당은 매우 어려운 일이다. 이를 위해 프라이버시 예산을 소모하지 않는 가상 데이터를 활용하여, 질의의 결과를 도출하는 방식의 연구가 진행되었다. 그러나 이와 같은 방식은 동일한 질의들을 처리한다 할지라도 질의의 순서에 따라 프라이버시 예산 소모량이 다르다는 문제점이 있다. 본 논문에서는 반응형 환경에서 질의를 처리할 때, 배치 전략을 통한 질의 순서를 재배열하여 처리를 하는 방식으로 프라이버시 예산 소모의 감소를 도모한다. 또한 기존의 기법에서 고려하지 않고 있는 질의의 중요도를 고려하여 배치 전략을 통해 절약된 프라이버시 예산을 중요도가 높은 질의에 우선적으로 할당한다. 이를 통해 기존 기법보다 적은 프라이버시 예산의 사용하며, 또한 높은 데이터 유용성을 보이는 기법을 제안한다.

XML 데이터가 동적으로 업데이트되는 환경에 적합한 원 개념을 사용한 레이블링 방법

김진영 서강대학교 일반대학원 2009 국내석사

XML has become the new standard for storing and exchanging data in the Internet and the Ubiquitous environment. As demand for efficiency in handling XML document grows, labeling scheme has become an important topic in data storage and the need to provide controlled access to such information is issued. Labeling schemes can be classified into Static Labeling Schemes and Dynamic Labeling Schemes. Static Labeling Schemes provide compact storage size but are not efficient for frequent update. Dynamic Labeling Schemes have nice update performance in Dynamic XML environment. However these schemes have several problems such as large storage space due to increase of length of labels, and re-labeling existing nodes. In this thesis, we propose a new labeling scheme called the Circle Labeling Scheme (CLS) which solves the problems of the previous Dynamic Labeling Schemes. In the CLS, XML document is represented in a circular form and the concepts of Radius, Rotation Number and Parent Circle/Child Circle are introduced. The notion of Radius is applied to support inclusion of new nodes at arbitrary positions in the XML tree. This eliminates the need for re-labeling existing nodes and prevents the label length from growing. Furthermore, the efficient storage of labels is supported by the use of concepts Rotation Number and Parent Circle/Child Circle. Hence the CLS is the efficient labeling scheme for memory space and dynamic XML environment. Previous research on access control mechanisms for XML data considered the efficiency of control the access only. Therefore, the performance of these access control mechanisms is depend on the performance of query processing systems. To solve these problems, the mechanism for integrating access control and query processing is proposed. Since this mechanism only considers read action for each user in authorization and is based on the Range-based Labeling Scheme, the mechanism is not inefficient for dynamic XML environment. In this thesis, we show practical use of the CLS. The proposed application is derived from the previous mechanism for integrating access control and query processing. To engance the adoptability for dynamic XML environment, we apply the CLS to the previous integrating mechanism and propose new action types in authorization. In this thesis, we propose the new labeling scheme called the Circle Labeling Scheme, which is efficient for dynamic environment and storage space. Moreover the application based on CLS is introduced. This application is an advanced mechanism for integrating access control and query processing, which is suitable for dynamic XML environment. XML은 인터넷과 유비쿼터스 환경의 데이터에 대한 저장과 교환, 출판의 목적으로 광범위하게 표준으로 사용되고 있다. XML 데이터 모델의 광범위한 사용으로 데이터의 효율적인 저장과 활용을 위한 레이블링 방법과 안전한 접근제어 방법에 대한 연구가 이슈화되고 있다. XML 문서에 대한 레이블링 방법은 데이터를 효율적으로 저장하고 활용하기 위한 목적으로 연구되고 있다. 초기 질의처리 시스템은 문서 전체를 탐색하는 문제점을 갖는다. 레이블링 방법은 구조적 조인을 빠르게 수행할 수 있게 함으로써 이러한 문제점을 해결했다. 초기 레이블링 방법은 레이블 크기가 작아 레이블 저장을 위해 적은 저장공간을 사용한다. 그러나 XML 데이터의 업데이트가 발생하면 기존 레이블들을 재작성해야 하는 문제점이 있다. 이러한 문제점 해결을 위해 최근 XML 데이터의 업데이트가 빈번한 환경에 적합한 동적 레이블링 방법들이 제시되고 있다. 그러나 1) 큰 레이블 크기, 2) 길어지는 레이블 길이, 3) 기존 레이블 재작성 필요 등의 문제점을 갖는다. 본 논문에서는 기존 동적 레이블링 방법의 문제점들을 해결하기 위해 개선된 레이블링 방법인 원형 레이블링 방법을 제시한다. 원형 레이블링 방법은 XML 문서를 원으로 이해하는 새로운 시도를 하였고 반지름과 회전수, 부모원/자식원 개념을 사용한다. 반지름 개념을 사용함으로써 새로운 데이터가 삽입될 경우 기존 데이터들의 레이블 재작성이 불필요하고 레이블 길이의 증가가 제한된다. 또한 레이블 구조에 반지름이라는 추가적인 정보가 필요하기 때문에 레이블의 크기를 줄이기 위한 방법으로 회전수 개념과 부모원/자식원 개념을 사용한다. 원형 레이블링 방법은 반지름, 회전수, 부모원/자식원 개념을 사용함으로써 XML 문서의 업데이트가 빈번한 환경에 효율적이며 레이블 저장공간에 효율적이다. XML 데이터 모델에 대한 접근제어 방법의 기존 연구들은 단순히 접근제어의 효율성을 증가시키는데 중점을 두었다. 이러한 연구들의 성능은 접근제어 후 질의처리기의 성능에 종속된다. 이러한 문제점에 대한 해결책으로 접근제어와 질의처리를 병행 처리하는 메커니즘이 제시됐다. 그러나 기존 병행 수행 메커니즘은 사용자가 XML 문서를 읽는 행위에 대해서만 고려하고 있고 ‘범위 기반 레이블링 방법’을 사용하기 때문에 실제 XML 문서의 업데이트가 빈번한 환경에 적합하지 않다. 원형 레이블링 방법의 활용 방안으로 XML 문서의 업데이트까지 고려하는 질의처리와 접근제어를 병행 수행하는 개선된 메커니즘을 제시한다. 원형 레이블링 방법을 사용하여 XML 문서를 레이블링 하여 XML 문서가 업데이트 되는 환경을 지원하기 때문에 업데이트를 위한 사용자들의 접근제어가 가능하다. 본 논문에서는 XML 문서의 업데이트가 빈번한 환경에 효율적이며 레이블 저장공간 효율적인‘원형 레이블링 방법’을 제시한다. 그리고 원형 레이블링 방법의 활용 방안으로 기존의 질의처리와 접근제어를 병행 수행하는 메커니즘에 원형 레이블링 방법을 적용하여 XML 문서의 업데이트가 요구되는 환경에 사용할 수 있는 개선된 메커니즘을 제시한다.

체류시간을 고려한 개인화된 여행 일정 추천 시스템

박세화 서강대학교 2015 국내석사

Recently development in transportation technology has made travel becoming major leisure activities. However, trip itinerary planning are challenging tasks for tourists, due to their need to select Points of Interest(POI) to visit in unfamiliar cities. In the meanwhile, due to the mobile device loaded with a GPS, such as a smartphone or a tablet PC made it possible to collect user's position in real time. Based on these circumstances, the research on the automatic itinerary planning system was carried out briskly to help trip planning. Nevertheless, existing studies including a schedule of itineraries focus on finding out the shortest path considering the constraints on cost and time budget or recommending the most popular travel route in the destination area. Therefore, we propose a personalized itinerary recommendation system considering the stay time preference of the individual user as part of personalized service. 최근 교통 기술의 발전과 여가생활에 대한 관심이 늘어남에 따라 여행이 주요 여가 활동으로 자리 잡고 있다. 또한, 스마트폰이나 태블릿PC와 같이 GPS를 탑재한 모바일 기기 보급으로 인해 사용자의 위치를 실시간으로 수집하는 것이 가능해졌다. 이런 환경을 바탕으로 번거로운 여행 일정 계획을 대신 수립해주는 여행 일정 추천 시스템에 대한 연구가 활발하게 진행되었다. 그러나 기존의 연구들은 사용자들의 비용이나 시간에 대한 제약사항을 고려해 짧은 경로를 포함하는 여행 일정을 추천하거나 여행 목적지에서 가장 인기 있는 지역을 가장 많이 포함하는 일정을 추천하는 것을 목적으로 하기 때문에 개인의 만족도를 높이기 위한 개인화된 여행 일정 추천시스템에 대한 연구는 많지 않았다. 따라서 본 연구에서는 사용자들의 만족도를 높이기 위한 개인화 서비스 연구의 일환으로 그 동안 다른 연구에서는 간과되었던 사용자들의 체류시간을 고려한 여행 일정 추천 시스템을 제안한다.

한정된 자원을 고려한 집단 여행 계획 질의 처리 기법

이준규 서강대학교 대학원 2020 국내석사

도시 간 운송 문제인 집단 여행 계획 질의는 질의 사용자들을 모아서 목적지까지 이동하는 전체 비용을 최소화하는 만남 장소들의 집합을 제공한다. 서비스 제공자는 사용자들에게 집단 여행 계획 질의를 이용하여 최적의 승차 위치를 제공할 수 있다. 그러나 서비스 제공자의 자원이 한정되어 있다면 집단 여행 계획 질의를 가지고 최적의 승차 위치를 제공할 수 없다. 본 논문은 서비스 제공자가 가지고 있는 차량의 용량, 차량의 수, 사용자와 차량 사이의 최대 허용 거리라는 세 가지 유형으로 구성된 자원 한계를 고려하여 최적의 여행 경로를 제공하는 한정된 자원을 고려한 집단 여행 계획 질의를 제안한다. 한정된 자원을 고려한 집단 여행 계획 질의는 질의 결과의 정확성을 보장하는 세 단계의 가지치기 기법을 제안한다. 또한 지역 탐색 휴리스틱 방법을 적용하고 지역 변경 연산의 성능 개선을 위한 가지치기 기법도 제안한다. 추가적으로, 지역 탐색 방법보다 효과적인 질의 수행 시간을 갖는 반복 탐욕 기법이라는 새로운 방법을 제안한다. 마지막으로 실험을 통해 본 연구에서 제안하는 세 가지 가지치기 방법이 기본적인 기법보다 성능을 개선할 수 있음을 보이고, 제안하는 근사 알고리즘이 지역 탐색 기법과 비슷한 정확도를 보이지만 개선된 질의 수행 시간을 갖는다는 것을 보인다. Collective Travel Planning (CTP), as an intercity transportation problem provides a subset of meeting points which minimize the total cost of distances to travel to a destination by gathering query users. Service agents can provide an optimal set of vehicle locations using the CTP query for customers. However, it is not possible to provide an optimal result in the CTP if there are resource capacities of service agents. In this thesis, we present a novel query called Resource Capacitated Collective Travel Planning (RCCTP) that provides the optimal travel route considering resource capacities of service agents which consist of three types such as vehicle capacity, maximum number of vehicles, and maximum distance bound between users and meeting points in the RCCTP query. We propose three level pruning rules that guarantee the query correctness. We also apply the local search heuristic and develop pruning rules for local change operations. Furthermore, we propose Repeated Greedy Method (RGM) which has better query running time than the local search. Finally, in experiments, we show that the performance improvement of the proposed three level pruning rules compared with the baseline method, and the proposed approximation algorithm has similar accuracy to the local search, but has improved query running time.

커뮤니티 특성을 고려한 편향치 협업필터링 기반의 광고 키워드 추출

박진용 서강대학교 정보통신대학원 2019 국내석사

Implementing an advertising strategy that reflects inherent insights on the basis of the subject issues with particular viewpoint on the online community users who are active and assertive is effective on company promotion by means of enhancing sympathy about target customers and reliability of advertisement. The technique- keyword extraction is very important because it reflects community insight for effectiveness of advertisement strategies by enhancing sympathy and reliability. Although the extracting techniques have been studies in various ways, collaboration filtering techniques which recommend keywords in view of the similarity of user preference is in use frequently. However, in case of collaborative filtering recommendation systems, the initial cost (time space complexity) for extracting keywords is not as efficient as the input of various preference conditions. There were several studies about its improvement. Based on the existing research cases about the rating base bias weight collaboration filtering which emphasizes its effectiveness, in this paper, it is named the core characteristics of community as value information and is aimed to study keyword extracting techniques that reflect user similarity weight. To this end, community posts are extracted by using TF-IDF and TextRank technique, then key characteristic information (Value Information) in rating format are normalized. Sequentially, advertisement keyword recommendation techniques which improves runtime effectiveness called VIBBP (Value Information Bias-Based Predictor) has been studied. By giving member levels which are the core characteristics in community weighted value and reflecting user similarity weight of keyword during the collaborative filtering process, some improved performance have been confirmed comparing to previous existing researches and the direction in the similarity among extracted keywords from SNS Twitter also has been confirmed as well. 능동적이고 적극적인 성향의 커뮤니티(보배드림) 사용자들을 대상으로 특정시점의 주제 이슈(신차 출시)를 기준으로 내재된 인사이트를 반영한 광고 전략을 집행하는 것은 타깃 고객층에 대한 공감도와 광고의 신뢰도를 높임으로써 기업의 홍보에 효과적이다. 공감도와 신뢰도를 높이는 광고전략의 효과성을 위해 커뮤니티의 인사이트를 반영한 키워드 추출은 중요도가 무척 높다. 이를 위한 추출기법이 다양하게 연구되고 있으나 사용자 선호도의 유사성을 감안하여 키워드를 추천하는 협업 필터링 기법이 자주 이용되었다[21]. 그러나 협업 필터링 추천시스템의 경우 여러 선호도 조건의 투입에 비하여 키워드를 추출하기 위한 초기비용 (시 공간 복잡도 측면)이 효율적이지 못한 문제가 있다. 이를 개선하기 위한 여러 연구가 진행되었으나 효율성을 강조한 평점기반 편향치 협업 필터링 기존 연구사례를 기반으로 본 연구에서는 커뮤니티의 주요 특성을 가치정보라고 명명하여 평점화 시키고, 사용자 유사도 가중치를 반영하여 키워드를 추출하는 기법을 연구하고자 한다. 커뮤니티의 게시글을 TF-IDF와 TextRank 기법으로 추출하고 주요 특성정보(가치정보)를 평점형태로 정규화 한 후, 평점화 된 가치정보와 사용자 유사도 가중치를 부여한 편향 가중치 협업 필터링 기법을 VIBBP (Value Information Bias-Based Predictor)라고 가칭하여 실행시간 성능 효율성을 개선한 광고 키워드 추천 기법을 연구하였다.

도로 교통망에 대한 사용자의 선호도 변화를 반영한 경로 추천

정주원 서강대학교 대학원 2018 국내석사

위치기반 서비스는 지도 및 주변 정보를 제공하거나 특정 목적지까지 가기 위한 경로를 제공한다. 그중 경로 추천 시스템은 각 사용자의 경로에 대한 평가 기준에 가장 적합한 경로를 추천하는 시스템이다. 기존의 개인화된 경로 추천 시스템은 시간대의 변화와 관계없이 사용자의 선호도가 일정하다는 가정하에서 추천한다는 단점이 존재한다. 하지만 이는 오전 시간대에는 이동 거리를 중시하고, 오후 시간대에는 위험도를 중시하는 것처럼 시간대마다 중요하게 생각하는 요소가 다른 다양한 사용자의 요구사항을 반영하지 못하는 문제가 존재한다. 본 논문은 해당 문제를 해결하기 위해 먼저 시간 속성을 고려한 다익스트라 기법을 제안한다. 하지만 이 기법은 그래프의 노드 수가 많아지거나 사용자의 선호도가 자주 변하는 경우 계산이 복잡해지는 한계가 존재한다. 이를 줄이기 위해 도로 교통망을 효과적으로 표현하는 G-Tree 인덱스 구조를 사용하여 시간대에 따른 선호 요소 가중치 변화를 반영한 경로를 탐색할 수 있는 효율적인 알고리즘을 제안한다. 또한, 실제 도로 교통망 기반의 데이터를 수집하고 이를 바탕으로 기존의 기법과 제안기법의 질의 처리 수행 시간과 사용자의 경로에 대한 만족도를 비교하는 실험을 수행함으로써 제안하는 인덱스 구조와 질의 처리 알고리즘이 해당 문제를 해결하기에 적합함을 보인다.