"나그넷길"의 두 판 사이의 차이

2020년 6월 27일 (토) 20:52 판 (원본 보기) 나그넷길 (토론 | 기여) (→‎프로젝트 github 주소) ← 이전 편집		2020년 6월 27일 (토) 20:52 판 (원본 보기) 나그넷길 (토론 | 기여) (→‎이론적 계산 및 시뮬레이션) 다음 편집 →
217번째 줄:		217번째 줄:
	|그림2		|그림2
	|}		|}
−
−	===이론적 계산 및 시뮬레이션===
−	내용
	===상세설계 내용===		===상세설계 내용===

---

2020년 6월 27일 (토) 20:52 판

프로젝트 개요

기술개발 과제

국문 : CodeTour(사용자 맞춤 여행일정계획 앱)

영문 : Code Tour

과제 팀명

나그넷길

지도교수

김성환 교수님

개발기간

2020년 3월 ~ 2020년 6월 (총 4개월)

구성원 소개

서울시립대학교 컴퓨터과학부 2017920022 맹유진(팀장)

서울시립대학교 컴퓨터과학부 2013560033 이태현

서울시립대학교 컴퓨터과학부 2017920006 김대양

서울시립대학교 컴퓨터과학부 2017920007 김바다

서론

개발 과제의 개요

개발 과제 요약

◇ 사용자가 원하는 지역의 여행장소 추천
◇ 사용자가 원하는 테마의 여행장소 주전
◇ 여행일정 자동계획
◇ 여행장소 위치, 여행경로 안내
◇ 지도를 이용한 여행경로 시각화

개발 과제의 배경

오늘날에는 여행지역과 관련된 정보를 인터넷검색을 통해 쉽게 얻을 수 있다. 그러나 여행지에 대한 정보들은 인터넷 여기저기에 파편적으로 위치하며, 사용자가 장소들의 정보들을 직접 모아 여행일정을 계획해야한다. 이러한 방법은 인터넷검색에서 상위에 뜨는 장소만을 추천 해 인기있는 특정장소 이외의 정보는 찾기가 힘들고, 오랜 시간이 소요된다. CodeTour는 사용자에게 자동여행계획기능을 제공하여 시간 단축과 다양한 여행지 추천효과를 목표로 한다.

개발 과제의 목표 및 내용

현재는 사용자가 직접 검색을 통해 정보를 얻고 계획해야하는 어려움이 있다. CodeTour는 사용자가 기본적인 정보만 입력한다면 추가적인 행동 없이 여행일정을 계획해준다. 이를 위해 사용자가 입력한 여행을 원하는 지역, 원하는 테마 등의 정보에 부합하는 관광지들을 Tour API를 이용하여 자동으로 모아주고, 클러스터링을 이용한 내부 시스템의 추천을 통해 일정을 계획해 보여준다. 또한 Tmap API를 통해 추천된 일정의 경로와 관광지 위치를 시각적으로 쉽게 확인 가능하도록 한다.

관련 기술의 현황

관련 기술의 현황 및 분석(State of art)

• 전 세계적인 기술현황

◇ Clustering (군집화)

● Clustering은 주어진 개체들을, 몇 개의 부분 그룹으로 나누는 과정을 의미한다. 이렇게 개체들을 나누는 과정을 통해서 클러스터 내부 개체들 사이의 거리는 가깝게, 서로 다른 두 클러스터의 개체들 사이의 거리는 멀게 하는 것이 clustering의 목표이다.

● 위 문장에서 개체 사이의 &거리&는 유클리드, 코사인, 자카드 등으로 클러스터링의 대상이 되는 개체의 특성에 따라 다양하게 정의될 수 있다.

● 데이터의 차원이 높아질수록 클러스터링이 어려워 진다. 따라서 고차원 데이터를 2-3차원으로 차원축소 후에 클러스터링을 진행하게 될 수도 있다.

  Hierarchical Clustering

 특정 알고리즘에 의해 데이터들을 연결하여 계층적으로 클러스터를 구성해나가는 방법이다. 클러스터의 개수를 가정할 필요가 없다는 것이 장점이다.

 클러스터 간의 거리를 계산하기 위해서 centroid라는 개념을 이용한다. 유클리드 공간에서는, 클러스터의 중간점이 centroid가 되는데, 그 외에 공간에서는 centroid 대신에 clustroid를 이용 한다. clustroid는 클러스터 내의 점들 중에 대표 점을 의미한다. clustroid를 찾는 방법은 다양 하지만, 보통 클러스터 내의 각 점으로부터 해당 점까지의 거리의 최댓값을 최소화 하는 점을 선택하거나, 평균을 최소화하는 점을 선택한다.

 divisive

- 데이터 전체의 멤버를 담고 있는 하나의 클러스터에서 시작하여 개별데이터로 분리 해나가는 식으로 클러스터를 구성하는 방법이다.

 Agglomerative (bottom-up)

- 주어진 데이터에서 개체 하나를 하나의 독립된 클러스터라고 가정한 후, 제일 가까운 두 개의 클러스터씩 붙여나가는 방식으로 진행된다.

 Point assignment clustering 

 k means clustering

- 처음에 클러스터의 개수인 k를 정하고, 데이터 중에 임의로 k개의 점을 선택한 후에 초기 클러스터로 삼는다. 그 후에 클러스터를 계속 변화시켜나가면서 클러스터링을 완 료하는 방법이다.

- 초기에 k개의 점을 선택하는 방법으로는 완전히 랜덤하게 선택하는 방법이 있고, 처음에 한 점만 랜덤하게 선택 후에 두번째 점부터는 이전에 선택한 점으로부터 가장 멀리 떨어진 점을 순차적으로 선택해나가는 방법도 있다. 후자의 경우 전자보다 클러스터링이 잘 이루어질 확률 이 높다는 장점이 있다.
- 처음에 선택한 k개의 점을 centroid로 하는 초기의 클러스터 k를 만든 후, 전체 점들에 대해 각 점마다 가장 가까운 centroid를 찾아서 해당 클러스터로 그 점을 넣는다. 이렇게 만들어진 클러스터의 경우 centroid를 새로 계산해주어야 한다. 새로 찾은 centroid를 바탕으로 이 과정 을 클러스터링한 결과가 달라지지 않을 때 까지 반복한다.
- 가장 가까운 centroid를 찾는 과정과 조정하는 과정에서 유클리드 거리를 사용하게 되므로 유클리드 공간에서만 사용할 수 있다.
- 최적의 k를 찾는 방법

1. 좋은 품질의 클러스터링 결과를 얻기 위해서는 k를 잘 선택하는 것이 중요하다. k를 너무 작게 설정하면 실제로는 다른 클러스터에 있어야 할 것 같은 점들이 같은 클러스 터 내에 위치하게 되고, k를 너무 크게 설정하면 거리가 충분히 가까운 두 점이 다른 클러스터에 속하게 되어 비효율적일 수 있다.

2. 클러스터링의 품질을 centroid와 다른 점들 사이의 평균 거리를 이용해서 표현한다 고 가정하면, 평균거리가 급격히 작아지다가 그 이후부터 큰 차이를 보이지 않는 k를 최적의 k라고 할 수 있다.

- 문제점

1. 유클리드 거리를 사용하기 때문에 주로 원 형태로 된 클러스터가 생성된다. 따라서 클러스터의 모양이 원 모양이 아닐 때는, 최적의 결과를 얻을 수 없다.

- 시간복잡도

1. 처음에 k개의 점을 찾는 것은 상수시간 동안에 수행할 수 있다. 그 후 각 점에서 가 장 가까운 centroid를 찾는 과정의 시간복잡도는 O(Nk)이고, centroid를 조정하는데에 O(n)만큼의 시간복잡도가 소요된다. 이러한 과정을 t번 반복하게 된다면 전체 시간복잡 도는 O(Nkt)가 된다. k와 t값에 따라 수행시간이 달라지지만 대체적으로 수행 속도가 빠른 편에 속한다.

2. 최적의 k값을 찾는 과정에서 k-means 클러스터링을 O(logN)번 수행하게 된다. 따라 서 최적의 k값을 찾으면서, k-means 클러스터링을 하는 과정의 전체 시간복잡도는 O(NktlogN)이 된다.

CURE (Clustering Using REpresentatives)

- 클러스터의 모양이 정규화 되어있지 않은 데이터를 대상으로 클러스터링 하기에 효율적 인 방식이다 .
- 2 pass algorithm으로 구성된다

 초기 클러스터 찾기

- 메인메모리에 올린 데이터로 일단 클러스터링을 진행한다.

 클러스터 내 대표값 뽑기

- 각 클러스터별로 n개의 대표값들을 최대한 흩어져있게 sampling한 후에 centroid 쪽으로 20%이동해서 사용한다. 어떠한 점에 대해서 centroid가 아니라 대표값과의 거리 기준으로 가장 가까운 대표값이 존재하는 클러스터에 점을 넣는 방식으로 진 행된다. (이 부분이 k-means clustering과의 차이점을 불러오는 부분이다.)

 Open API

 API란 Application Programming Interface의 약자로, 운영체제와 응용프로그램 사이의 통신에 사용되는 언어나 메시지 형식을 말한다. 말 그대로 Application의 Programming을 위한 Interface라고 할 수 있다. 을 위한 Interface라고 할 수 있다.
 내부 API는 디바이스를 제어할 수 있는 기능들을 의미하며, 외부 API는 디바이스에 저장되어 있는 기능이 아니라, 서비스회사의 API를 통해 사용하는 기능들을 말한다.
 사람들은 Open API를 이용해 무료로 다양한 컨텐츠를 쉽게 개발할 수 있다. 즉 누구나 사용할 수 있도록 공개된 API를 Open API라고 부른다. 유용한 API들을 잘 이용하면 지도나 번역기 등의 기능들을 직접 개발하지 않고 가져다 사용할 수 있다.
 구글, 카카오, 네이버 등의 기업들은 개발자들을 위한 API를 제공하는 사이트를 운영하고 있다. 또한 국가에서도 공공데이터포털을 운영하여 다양한 데이터 및 기능을 활용할 수 있도록 돕고 있다.

 지도 API

- 각 api별로 제공하는 기능은 거의 비슷하다.

- 지도에 마커를 띄우거나 경로를 표시할 수 있고, 키워드를 이용하여 원하는 장소를 검색할 수 있다. 또한 GPS를 이용하여 현재 위치 기반 기능도 이용할 수 있다.

즉, 사용자의 정보를 기반으로한 인터렉티브한 기능을 제공한다.

- 카카오, 네이버 구글 등 다양한 기업들에서 지도 API를 제공하고 있다. 총 4개 (카카 오지도, 네이버지도, 티맵, 구글지도) API의 장 단점을 비교하여 이번 프로젝트에 사용 할 API를 결정하였다.

- 아래의 표와 같이 비교한 후에, TmapAPI를 사용하기로 결정했다.

 Tour API

- 국내 유일의 실시간 다국어 관광정보를 제공하는 API이다.

- 한국관광공사가 보유하고 있는 전국의 다양한 관광정보, 사진정보를 실시간으로 제공 받을 수 있으며, 국내 최대 관광정보 포털 사이트 Visitkorea(www.visitkorea.or.kr) 홈페 이지에서 제공하는 관광정보 중 저작권 등에 구애 없이 자유롭게 활용 가능한 정보만 을 선별하여 홈페이지와 동일한 최신정보를 제공한다.

- 이 API에서 받아온 관광지들을 대상으로 추천을 진행한다.

• 기술 로드맵

내용

시장상황에 대한 분석

• 경쟁제품 조사 비교

내용

• 마케팅 전략 제시

내용

개발과제의 기대효과

기술적 기대효과

◇ 정보수집을 위한 검색횟수가 줄어들며 일정계획시 필요한 시간이 단축된다.

◇ 여행장소정보수집, 여행경로확인, 스케쥴링등 여러 앱을 이용해야했던 일정계획이 하나의 앱으로 가능해진다.

경제적, 사회적 기대 및 파급효과

◇ 일정계획에 어려움을 느껴 패키지 여행을 이용하던 사용자가 줄어든다.

◇ 인기있는 몇개의 여행지가 아닌 비교적 지역의 다양한 여행장소를 추천하여 비교적 인기가 없던 여행지가 활성화 된다.

기술개발 일정 및 추진체계

개발 일정

구성원 및 추진체계

설계

설계사양

제품의 요구사항

번호	요구사항	D or W	비고
1	추천 여행 스케줄을 생성하여야 한다.	D
2	생성된 스케줄을 사용자에게 시각적으로 보여줘야 한다.	D
3	종합적인 사용자 정보(여행지역, 여행일자, 여행테마, 식당 취향 등)를 입력받아 추천에 반영해야 한다.	W
4	여행 스케줄 생성시 5~10초 이상 걸리면 안된다.	D
5	만들어진 여행 스케줄을 사용자 임의로 편집할 수 있어야 한다.	W

• 목적 계통도

TODO: 이미지 파일 업로드

개념설계안

프로그램 구상

그림1

• 사용자의 정보를 받아 적합한 일정을 자동으로 계획한다.
• 계획된 일정은 지도와 일정표를 통해 제공된다.
• 사용자는 계획된 일정을 편집할 수 있다.
• 계획된 일정은 저장되어 불러오기, 삭제가 가능하다.

기능 구상

• 추천 여행지 선택

1. 인기순 추천: 해당 지역에서 인기있는 장소들을 추천한다.
2. 거리 기반 추천: 출발지와 위치를 비교하여 가까운 거리에 있는 장소들을 우선으로 추천한다.
3. 그룹화 후 추천: 장소들을 클러스터링한 후 출발지와 위치를 비교하여 가장 가까운 그룹의 장소들을 추천한다. 요일마다 다른 클러스터의 장소를 추천한다.

• 경로 생성 방법

1. 거리 기반 추천: 사용자가 입력한 출발지를 기준으로 거리를 계산해, 가까운 장소부터 먼 장소 순으로 경로를 생성한다.
2. 사분할 추천: 출발지를 기준으로 구역을 나눠 한 구역씩 이동하도록 경로를 생성한다.
3. TSP 알고리즘: TSP 문제를 풀기 위한 여러 휴리스틱 알고리즘을 이용하여 경로를 생성한다.

거리 기반 추천	사분할 추천	TSP 알고리즘
그림1	그림2	그림3

• 사용자에게 일정 보여주기

리스트 형태	지도 경로 형태
그림1	그림2

상세설계 내용

내용

결과 및 평가

완료 작품의 소개

프로토타입 사진 혹은 작동 장면

앱의 메인 화면과 일정확인 화면입니다.

실행(RUN)

1. 메인페이지에서 일정 짜러가기 버튼을 누른다.
2. 여행 조건을 모두 입력한다.(가는 날, 오는 날, 활동 예산, 숙소 예산, 음식 취향, 테마, 인원, 활동 시간)
3. 날짜별로 여행의 출발지 도착지를 입력한다. (숙소 또는 지역 이동을 고려하여 입력한다)
4. 세부적인 여행일정에 대한 정보와 경로를 확인한다
5. 저장된 여행 일정을 확인하며, 여행 일정을 선택하여 해당 일정을 확인, 수정한다.

성과물

프로젝트 github 주소

https://github.com/neilsonT/CodeTour

관련사업비 내역서

없음.

완료작품의 평가

내용

향후계획

내용

특허 출원 내용

내용