Home

POI 추출을 위해서는 체류 지점을 식별하는 기법이 요구된다. 이에 따라 본 논문은 사용자의 GPS 좌표들을 분석하고 체류 지점을 식별하는 기법을 이용한다. 따라서 GPS 좌표들을 클러스터링하여 사용자 체류 지점을 식별한다.

[13]은 GPS 좌표를 이용하여 단일 혹은 다중 사용자의 의미 있는 지점을 찾고 위치 이동을 예측하는 연구로서 체류 지점 식별을 위하여 K-means 알고리즘을 이용한다. 하지만 K-means 알고리즘은 클러스터 수를 사전에 결정해야 하는 한계가 있다.

[14]는 K-means가 지니는 한계를 극복하기 위하여 클러스터의 수를 자동으로 결정하는 G-means 클러스터링 기법을 이용한다. 이 연구는 스마트폰 사용자의 의미 있는 방문 POI 추출을 위하여 Naive Bayes classifier를 사용해 체류 지점을 추출하고 분할된 장소에 G-means 클러스터링 기법을 통해 관심 지점을 식별한다. 하지만 G-means 클러스터링 기법은 K-means를 반복적으로 수행해야 하므로 수행시간이 다른 기법에 비해 오래 걸린다는 단점이 있다.

[15]는 GPS 좌표를 기반으로 체류 지점과 이동 패턴을 분석하는 연구이다. 이 연구는 일정 시간 이상 머문 지역을 탐지한 후 체류 지점 식별을 위해 밀도 기반 군집화 알고리즘인 DBSCAN 기법을 이용한다. DBSCAN 기법은 본 논문의 제안 기법에서도 체류 지점 식별을 위하여 사용하는 알고리즘이다.

[16]은 임계값을 만족하는 구간의 가장 가까운 곳에 있는 좌표를 체류 지점으로 지정하는 nearSP 기법과 시간 계산으로 실내에 머무른 위치를 추출하는 indoorSP 기법을 제안한다. 이 연구는 일반적으로 사용자가 건물 안에 들어가면 GPS 좌표 데이터는 수신받지 못하므로 해당 시간부터는 데이터가 없는 것을 전제로 한다. 하지만 실제로 데이터를 수집 시 발생하는 잡음 등을 고려하지 않는다는 문제를 지닌다.

[17]은 GPS 좌표 정보를 기반으로 관심 지점과 이동 경로를 자동 추출하는 방법을 제안한다. 이 연구는 관심 지점 탐지를 위해 밀도 기반 DBSCAN 알고리즘을 사용한다. 하지만 이 연구는 GPS 위치정보만을 이용하여 POI를 추출하기 때문에 POI의 의미적 정보를 알 수 없다.

[18]은 모바일 사용자의 대용량 이동 궤적 정보를 기반으로 시맨틱 POI 발견 방법을 제안한다. 이 연구는 WiFi 맵을 이용한 GPS 클러스터링 알고리즘을 통해 체류 지점으로 식별되면 이를 시맨틱 노드로 추출한다. 하지만 이 연구는 시맨틱 POI를 3가지 부류로만 구별할 수 있고 해당 POI가 실제 어떤 장소인지는 알 수 없다.

[19]는 GPS 로그 데이터에서 K-means 알고리즘과 수정한 Canopy 알고리즘을 적용하여 후보 POI를 뽑아 가장 오래 머문 GPS 지점을 최종 POI를 추출하는 방안을 제안한다. 또한, POI 추출에 있어 GPS 좌표와 시간, 행동 데이터 중 멈춤 상태를 특징으로 사용한다. 하지만 이 연구는 단순한 행동 상태와 가장 오래 머문 지점으로 POI로 추출하기 때문에 이를 사용자의 POI로 볼 수 없다.

이러한 연구들은 대부분 사용자의 POI를 추출하지만, 해당 POI에 대한 물리적 위치정보만 파악할 수 있고 의미적 정보가 없어 실제 사용자가 어떤 장소에 머물렀는지는 알 수 없다.

따라서 본 논문은 사용자 POI가 실제 장소의 상호와 같이 의미 있는 정보를 제공하여 사용자의 이동 경로를 분석하는 것을 목표로 한다.

그림 1은 본 논문에서 제안하는 사용자 POI 기반 이동 경로의 분석 기법의 프로세스를 보이며 이는 크게 체류 지점 식별, POI 후보 리스트 생성, 이를 이용한 POI 기반 사용자 경로 분석으로 구성된다.

Fig. 1. 
A process of user route analysis based on POI through stay point identification

사용자의 이동 경로를 분석하기 위해서는 먼저 사용자의 데이터를 기반으로 체류 지점을 식별해야 한다.

이를 위해 모바일 디바이스에 내장된 GPS 센서를 이용하여 사용자의 이동 궤적을 수집한다. 수집된 이동 궤적은 데이터 정제 기법 등을 통하여 노이즈를 제거하고 날짜별로 구분하여 저장된다. 이후 DBSCAN 기법을 적용하여 사용자가 체류한 지점을 식별한다.

이러한 체류 지점들은 어떤 위치만을 나타낼 뿐 실제 상호나 의미적인 정보가 포함된 POI로 표현할 수 없다. 따라서 제안 기법은 식별된 체류 지점으로부터 정확한 POI를 매칭하기 위해서 POI 후보 리스트를 이용한다. POI 후보 리스트는 사용자가 이전에 방문했던 POI 정보, 카드 사용 내역, 사용자 직접 입력 정보를 활용하여 생성된다.

POI 후보 리스트는 먼저 기존에 사용자가 이동했던 POI 분석 결과를 활용하여 생성한다. 또한, 사용자의 카드 사용 내역을 받아와 사용자가 이전에 방문했던 장소의 실제 상호를 추출하여 POI 후보 리스트에 추가한다. 집, 회사와 같이 상호 등으로 추출할 수 없는 정보들은 사용자로부터 위치정보와 함께 직접 입력받아 사용자 개인의 POI 후보 리스트를 보완한다. 이러한 후보 리스트는 사용자의 위치정보만 가지고 추출할 수 없는 실제 머무른 장소를 의미적 정보로써 도출하는 역할을 한다.

사용자의 POI에 기반한 이동 경로 분석은 앞서 식별한 체류 지점과 POI 후보 리스트를 매칭시킴으로 이루어진다. 식별된 체류 지점은 GPS 위치정보로 표현되고 POI 후보 리스트는 상호 및 의미적인 이름으로 표현되므로 두 정보의 매칭을 위해서는 각각을 주소(Address) 정보로 변환하는 것이 필요하다.

이를 위하여 먼저 사용자의 이동 궤적으로부터 식별된 체류 지점의 좌표를 Open API를 이용하여 주소로 변경하고 해당 주소로 검색되어 나오는 상호 리스트를 생성한다. 이렇게 생성된 사용자 체류 지점의 상호 리스트와 사용자 POI 후보 리스트를 비교한다. 이 두 개 리스트의 주소와 상호를 기반으로 매칭시켜 POI를 선정한다. 마지막으로 사용자의 이동 경로 분석 결과는 하루 동안 사용자가 이동한 순차적인 POI 리스트로 도출된다.

사용자의 이동 궤적을 생성하기 위해 모바일 디바이스에 내장되어있는 GPS 센서를 기반으로 사용자의 GPS 좌표를 수집한다. 이는 수집한 날짜의 이름으로 텍스트 파일이 생성되며 모바일 디바이스 내부저장소에 저장된다. 저장된 텍스트 파일을 받아와 DB에 저장하고 해당 날짜의 데이터에 노이즈를 제거하는 정제 기법 등을 적용하여 사용자 이동 궤적으로 생성한다.

그림 2는 실제 수집한 사용자의 이동 궤적 중 일부분을 나타낸 그림이다. 이는 사용자가 건물 내부와 같이 어느 한 지점에 머무르기 위해 들어가거나 나올 때, 위성으로부터 신호를 수신받지 못해 그림 2와 같이 다량의 잡음을 포함하여 데이터가 수집된다. 이러한 데이터에 클러스터링 기법을 사용하여 잡음 부분을 사용자가 체류한 지점으로 식별할 수 있다.

Fig. 2. 
Noise generated while staying in the building

사용자 이동 궤적에서 체류 지점을 식별하기 위해 체류 지점 식별 클러스터링 기법 중 DBSCAN 기법을 이용한다. DBSCAN은 데이터의 밀도에 기반하는 클러스터링 알고리즘으로 클러스터의 반경(Eps)과 최소 점의 개수(Minpts)가 매개변수로 주어진다[20]. 이는 하나의 점으로부터 EPS 내에 Minpts 만큼 점이 있으면 하나의 클러스터로 묶는다. 만약 클러스터에 속하지 않은 점들은 잡음(Noise)이라고 분류한다. 이처럼 DBSCAN의 두 가지 매개변수는 클러스터를 결정짓는 중요한 역할을 한다.

따라서 적절한 매개변수의 값을 찾기 위해 Elbow 기법의 군집 사이의 제곱 오차의 합(SSE)을 활용한다.

Elbow 기법이란 K-means 알고리즘의 적정 K값을 찾아주는 기법으로 K의 수를 하나씩 늘려 SSE 값이 감소하는 정도가 낮아질 때의 K를 구하는 기법이다[21]. 이와 같이 DBSCAN 기법의 적절한 매개변수를 찾아 사용자가 체류한 지점을 식별한다.

그림 3은 실제 수집된 사용자의 이동 궤적과 식별된 체류 지점을 보인다. 이는 사용자 이동 궤적에 DBSCAN 기법을 적용하여 클러스터링 된 지점을 시각화한 것이다. 이렇게 식별된 체류 지점에서 정확한 POI를 추출하여 사용자의 이동 경로를 분석할 수 있다.

Fig. 3. 
Identification of the stay point in the collected trajectory

식별된 사용자의 체류 지점은 GPS 좌표만을 가지고 있다. 그러므로 사용자의 의미적 정보를 포함하는 POI를 추출하기 위해서 사용자 개인의 POI 후보 리스트를 사용해야 한다. 이를 위해 제안 기법은 사용자가 이전에 방문했던 POI 정보, 카드 사용 내역, 사용자 직접 입력 정보를 활용한다. 이는 사용자로부터 카드 사용 내역을 파일로 받아 자동으로 분석하여 사용자가 카드를 사용한 장소에 대한 내용을 받아온다.

Maps 기반 Open API를 활용하여 카드를 사용한 장소의 실제 상호, 유형(Type), 주소, 위도(Latitude), 경도(Longitude)와 같은 정보를 추가한다. 이를 사용자가 이전에 방문했던 장소들에 대한 사용자 POI 후보 리스트라고 명칭하고 생성한다. 이 리스트는 개별적 관리를 위해 CSV 파일로 저장된다.

표 1은 사용자의 카드 사용 내역을 기반으로 생성한 사용자 POI 후보 리스트의 스키마를 보인다. 장소는 상호와 같은 대표 이름을 나타내고 유형은 해당 장소의 카테고리를 나타낸다. 또한, 주소는 행정구역상 지번 주소, 위도와 경도는 해당 장소의 GPS 좌표를 나타낸다.

그림 4는 사용자의 다양한 정보를 기반으로 생성한 사용자 POI 후보 리스트의 예시이다. 이 리스트를 활용하여 사용자 체류 지점에서 사용자의 POI를 추출할 수 있다.

Fig. 4. 
Example of user POI candidate list

사용자가 추가하고자 하는 장소가 있을 시 사용자 POI 후보 리스트에 추가할 수 있어 좀 더 보완된 리스트를 생성할 수 있다. 만약 Open API를 통해 추출할 수 없는 개인적인 장소는 사용자로부터 위치정보와 장소 이름, 주소와 같은 추가적인 정보를 직접 입력받아 사용자 개인의 POI 후보 리스트를 보완한다.

하지만 상업적인 장소는 사용자로부터 해당 장소의 이름만 입력받아 Open API를 통해 자동으로 실제 상호, 유형, 주소, 좌표를 얻어와 리스트를 보완한다. 이러한 사용자 POI 후보 리스트는 사용자의 체류 지점에서 정확한 POI를 추출하여 실제 머무른 장소를 도출하는 역할을 한다.

사용자의 POI에 기반한 이동 경로 분석은 앞에서 식별된 체류 지점과 사용자 POI 후보 리스트를 매칭시킴으로 이루어진다. 식별된 체류 지점은 GPS 위치정보만 가지고 있어 해당 건물의 위치만 알 수 있고 사용자가 실제 어떤 매장을 이용했는지는 알 수 없다. 따라서 식별된 체류 지점의 상호 리스트를 생성해야 한다.

식별된 체류 지점의 상호 리스트를 얻기 위해 카카오 Open API 중 지도 Local API를 사용하여 해당 체류 지점의 좌표를 지번 주소로 변환한다. 키워드로 장소 검색을 하는 API를 사용하여 앞에서 변환한 체류 지점의 주소를 기반으로 체류 지점의 상호 리스트를 생성한다.

그림 5는 Open API로 받아온 사용자의 체류 지점 좌표의 상호 리스트를 보인다. 먼저, 체류 지점의 좌표를 주소로 변경한 후 해당 주소에 있는 상호 리스트를 추출한다. 이는 사용자 체류 지점의 상호 리스트로 사용자가 머무른 장소의 주소에 대한 상호 후보군을 제공하고 있다.

Fig. 5. 
List of business names of stay points

체류 지점의 상호 리스트에서 실제 사용자가 머문 장소를 추출하기 위해 앞에서 생성한 사용자 체류 지점의 상호 리스트와 사용자 POI 후보 리스트를 비교하여 해당 체류 지점의 상호 리스트에서 POI를 추출한다.

먼저 생성된 사용자 체류 지점의 상호 리스트와 사용자 POI 후보 리스트를 비교한다. 두 리스트의 주소와 상호를 기반으로 매칭시킨다. 식 (1)의 Haversine 공식을 사용하여 사용자 체류 지점(S)의 좌표와 매칭된 사용자 POI 후보 리스트(P)에 있는 장소의 좌표 간 거리를 구하여 가장 가까운 장소를 최적의 POI로 추출한다.

Haversine 공식이란 둥근 지구에 있는 두 지점의 위도, 경도를 이용하여 측정한 가장 짧은 거리를 구하는 공식을 말한다[22].

추출된 사용자의 POI에 머무른 시간, 상호, 유형, 주소, 위도, 경도와 같이 다양한 정보를 추가하여 의미 있는 정보를 가진 POI로 생성한다. 이렇게 생성된 POI를 기반으로 사용자의 이동 경로를 분석할 수 있다.

그림 6은 추출된 POI에 다양한 정보를 추가하여 생성된 의미 있는 POI 테이블을 보인다. ‘p_num’은 사용자의 POI가 추출된 순서로 해당 장소를 방문한 순서를 의미한다. 이를 통해 사용자의 이동 경로를 도출해 낼 수 있다. ‘time’은 해당 장소에 사용자가 머무른 시간을 의미하며 식별된 체류 지점의 시간 정보를 나타낸다. ‘place’는 해당 장소의 실제 상호를 의미하고 ‘type’은 해당 장소의 유형, 카테고리를 의미한다. ‘addr’은 해당 장소의 지번 주소를 의미하고 ‘lat’과 ‘lon’은 해당 장소의 위치 좌표를 의미한다.

Fig. 6. 
Created meaningful POI table

그림 7은 최종적으로 도출된 POI 기반 사용자 이동 경로를 보인다. 사용자의 POI를 마커로 표시하고 해당 마커에 팝업창을 띄워 사용자 방문 순서와 실제 장소의 상호를 보여준다. 이를 통해 시각적으로 사용자의 이동 경로를 확인할 수 있다.

Fig. 7. 
Deduction of POI based user route

따라서 사용자의 이동 경로는 사용자 이동 궤적에 클러스터링 기법을 사용하여 체류 지점을 식별하고, 사용자의 POI가 추출되는 순서를 기반으로 분석할 수 있다.

먼저 사용자의 이동 궤적을 수집하기 위해 자체 개발한 모바일 앱을 사용하여 모바일 디바이스에 내장된 센서로 사용자의 GPS 좌표를 수집하였다. 또한, 성능 측정을 위하여 사용자가 직접 이동 경로 및 머물렀던 장소와 그 수를 기록하는 것으로 데이터셋을 구성한다.

그림 8은 실험을 자원한 피실험자들의 스마트폰을 이용하여 5초 주기로 수집된 데이터셋의 일부분을 보인다. 수집된 데이터는 모바일 디바이스에 내장된 센서로부터 측정한 위도, 경도, 3축 가속도(x, y, z) 데이터 및 데이터의 수집 시간을 포함하고 있다. 그 결과, 총 40일 동안 7명이 실험을 위해 자유롭게 이동하면서 수집하였으며 수집된 데이터는 총 44개의 이동 궤적이며 34,997행으로 이루어져 있다.

Fig. 8. 
Data collection results

표 2는 실험 동안 사용자가 직접 머무른 장소의 위치와 수를 기록한 표 중 일부를 보인다.

이는 제안 기법을 통해 추출된 사용자의 POI와 정확성을 검증하기 위해 사용자로부터 직접 수집하였으며, 실험 동안 총 113개의 POI에 체류하였음을 확인할 수 있다.

이 실험은 수집된 사용자 이동 궤적에서 사용자 체류 지점을 식별하기 위한 4가지 체류 지점 식별 기법(K-means, G-means, DBSCAN, Sequenced DBSCAN)을 조사하고 실제 데이터에 적용해 본 결과를 바탕으로 비교 평가를 수행한다. 이때 4가지 체류 지점 식별 기법은 기존 연구에서 체류 지점 식별을 위해 쓰인 클러스터링 기법들로 선정하였다.

K-means는 임의의 K를 결정하여 데이터를 K개의 군집으로 형성하는 클러스터링 알고리즘이다[13]. 지정된 K개의 임의의 중심점으로부터 점들의 거리를 구해 가까운 점들을 하나의 클러스터로 생성하고, 각 클러스터에 속한 점들을 기반으로 중심점을 업데이트하는 방식이다.

G-means는 K-means를 반복적으로 수행하여 단점을 극복한 군집화 방법으로 데이터에 대해 임의의 K, 즉 클러스터의 수를 자동으로 결정하여 군집화하는 알고리즘이다[14].

DBSCAN은 본 논문에서 활용하는 기법으로 데이터의 밀도에 기반하여 밀도가 높은 부분을 클러스터링한다. 이 기법은 본 논문의 3.2절에서 자세히 기술하였다.

Sequenced DBSCAN은 기존에 있는 DBSCAN에서 시간이나 순서를 고려하여 클러스터링을 수행한다. 이는 처음에 무작위로 한 점을 선택한 후 그 점을 기준으로 슬라이딩 윈도우를 수행한다. 이웃 반경을 설정하고 설정된 이웃 반경과 반경 내에 최소 점 개수를 매개변수로 설정해 클러스터링하는 알고리즘이다[23].

성능 평가를 위하여, 각 기법의 정밀도(Precision), 재현율(Recall), F-measure를 측정하고, 어떤 기법이 가장 성능이 우수한지를 실험한다. 정밀도는 해당 기법이 식별한 체류 지점 중 사용자가 실제로 체류한 지점과 일치하는지 비율을 계산하며 식 (2)와 같다. 재현율은 사용자가 실제로 체류 지점의 정답 중 해당 기법이 맞춘 체류 지점 개수의 비율을 계산하며 식 (3)과 같다. F-measure는 정확률과 재현율의 조화를 평가하며 식 (4)와 같다.

그림 9는 각 기법의 정밀도, 재현율, F-measure를 측정한 결과를 보인다. 실험 결과 DBSCAN 기법의 정밀도는 90.78%, 재현율은 93.85%, F-measure은 92.27%로 다른 클러스터링 기법들보다 가장 우수한 성능을 보였다. 따라서 본 논문은 가장 좋은 성능을 보이는 DBSCAN 기법을 체류 지점 식별 기법으로 선정하였다.

Fig. 9. 
An evaluation results of clustering algorithms

이 실험은 체류 지점 식별 실험 결과에 따라 수집된 사용자 이동 궤적에 DBSCAN 기법을 적용하여 체류 지점을 식별한다. 이후 식별된 체류 지점에서 제안 기법을 통해 사용자의 POI를 추출하여 사용자의 이동 궤적을 분석한다. 이때 제안 기법의 정확성을 검증하기 위해 추출된 사용자의 POI와 실제 사용자가 기록한 POI를 비교하여 정밀도, 재현율을 측정한다.

표 3은 제안 기법을 사용하여 추출한 POI와 사용자가 직접 기록한 실제 POI를 비교하여 나타낸 일부를 보인다. 이를 통해 제안 기법을 사용하여 추출된 POI가 실제 사용자의 POI를 도출할 수 있는지 검증하였다.

그림 10은 제안 기법을 사용하여 추출한 날짜별 POI의 정밀도와 재현율을 측정한 결과를 보인다. 정밀도는 해당 기법을 통해 추출된 POI 중 제안 기법을 통해 추출된 POI가 맞춘 개수의 비율을 계산하며 식 (5)와 같다. 재현율은 실제 사용자의 POI 중 제안 기법을 통해 추출된 POI가 맞춘 개수의 비율을 계산하며 식 (6)과 같다. 그 결과 평균 정밀도는 92.08%, 재현율은 96.21%를 보였다.

Fig. 10. 
Measurement results of precision and recall by date of the proposed method