군집 노이즈 필터링 기반 이동 궤적 정제 기법

2.1 이동 궤적 추출 및 노이즈 필터링 연구

사용자의 경로를 학습하기 위해서는 수집된 GPS 좌표로부터 이동 궤적을 추출하고 노이즈를 제거하는 기법이 요구된다[11]-[13].

3-필터 기반 노이즈 제거 기법은 속도 필터, 각도 필터, 와이파이 필터를 이용하여 이동 궤적으로부터 노이즈를 제거한다[11].

또한 기존의 3-필터에 POI를 추출한 결과를 적용하여 효과적으로 노이즈를 제거한 연구도 진행되었다[12]. 하지만 이러한 연구들은 와이파이 필터를 이용하였으며, 와이파이 접속 정보를 이용한 필터는 본 논문에서 목적으로 하는 웨어러블 디바이스를 활용하는 환경과 맞지 않고, 와이파이에 접속하지 못하는 지역의 경우 이러한 필터를 사용하지 못한다는 문제를 지닌다.

한편, 경로 예측을 위한 CRPM(Countinuous Route Pattern Mining) 알고리즘은 사용자의 이동경로 정제를 위하여 중복 필터, 속도 필터, 가속 필터, 총 거리 필터 그리고 각도 필터와 같은 5가지 필터를 적용한다[13].

그러나 이러한 연구들은 다양한 필터들을 적용하여 노이즈를 효과적으로 제거하지만, 머무르는 지점에 대한 노이즈를 제거하지 않는다.

2.2 군집 위치 식별 관련 연구

GPS 좌표로부터 머무르는 위치를 찾아내기 위한 연구들은 주로 군집화 기법을 이용한다.

Ashbrook et al.[14]은 사용자의 이동 후의 위치를 예측을 위하여 K-means 알고리즘을 이용하여 클러스터링 한다. 하지만 이러한 위치 예측은 일정 시간 후 사용자의 위치만을 예측해 줄 뿐 이동 경로까지 알 수는 없다.

Kang et al.[15]은 사용자의 머무르는 지점을 찾아내기 위하여 K-means와 혼합 가우시안을 적용한 기법과 시간 기반 클러스터링을 적용한 기법과 같이 두 가지 클러스터링 방식을 활용한다.

밀도 기반 클러스터링 기법은 DBSCAN을 이용하여 머무는 지점을 파악한다[16]. 사용자의 방문 빈도에 따라 머무는 지점 탐지, 임계범위 설정, 관심 지점 군집화와 같은 3 단계를 통해 비슷한 유형의 이동 궤적들을 클러스터링 한다.

이러한 연구들은 이동 궤적 기반 군집화를 통하여 POI를 추출하고 사용자에게 의미 있는 위치를 찾는다. 하지만 이러한 군집된 위치를 찾는 기법들이 사용자의 이동 궤적을 정제하는데 사용되지는 않는다.

따라서 본 논문은 기존 연구들이 사용하는 이동 궤적 추출 및 노이즈 제거를 위한 필터를 활용하고 사용자의 군집된 위치를 찾아 제거함으로써 사용자가 이동하는 궤적만을 명확하게 추출하는 것을 목표로 한다.

3.1 전처리 방법

그림 1은 사용자의 이동 경로 분석을 위한 라이프로그 수집 및 전처리 과정을 보인다. 먼저, 스마트 워치 및 스마트폰을 이용하여 사용자의 GPS 위치 정보를 포함한 라이프로그를 수집한다. 수집된 라이프로그는 스마트폰에서 파일로 저장되며, 해당 로그 파일은 라이프로그 Collector로 전송된다.

Fig. 1.

Lifelog collection and preprocessing for user’s path analysis

서버로 전송된 이후 라이프로그는 두 단계의 전처리 과정을 거친다. 첫 번째 단계는 서버로 전송된 로그 파일을 파싱하여 데이터베이스에 저장한다. 이 과정에서 라이프로그들은 사용자가 이동한 궤적별로 아이디가 부여되어 저장된다. 두 번째 단계는 다양한 필터를 이용하여 명확한 이동 궤적을 추출하기 위해 노이즈를 제거한다.

이후 정제된 라이프로그는 명확한 이동 궤적이 요구되는 경로 학습이나 분석 분야에서 활용될 수 있다.

3.2 기본 필터

이동 궤적의 노이즈를 제거하기 위해 사용된 기본 필터는 시간 필터, 범위 필터, 속도 필터, 가까운 거리 필터, 먼 거리 필터, 각도 필터이다. 표 1은 기본 필터들의 설명이다.

Table 1.

Description of basic filters

시간 필터는 현재 위치와 이전 위치의 시간 차를 이용하여 새로운 이동 궤적 인지를 구분한다. 만약 이전 위치의 시간이 현재 위치의 시간보다 일정 시간 차이가 있다면 이는 사용자가 새로운 궤도를 따라 이동한다고 판단하여 다른 이동 궤적으로 식별한다. 이 연구에서는 시간 차를 10분으로 정의한다.

범위 필터는 위도와 경도의 일정 범위를 부여하여 해당 지역 안에서의 데이터만 추출한다. 이 연구에서는 한 대학과 그 주변 대학로를 범위로 설정한다.

속도 필터는 현재 위치와 이전 위치의 속도 차를 이용하여 노이즈를 판단한다. 제한 값은 사용자가 자동차를 타는 상황을 고려하여 정의하며, 이 연구에서는 속도 차를 120km/h로 정의한다.

가까운 거리 필터와 먼 거리 필터는 이전 위치와 현재 위치의 거리 차를 이용한다. 가까운 거리 필터는 거리 차가 5m 미만이면 현재 위치가 이전 위치에서 멀지 않은 것을 의미하며 여전히 남아있다고 가정하여 노이즈로 판단한다. 먼 거리 필터는 이전 위치와 현재 위치의 거리 차가 있다면 이는 사용자가 새로운 궤도를 따라 이동한다고 판단하여 다른 이동 궤적으로 식별한다. 이 연구에서는 거리 차를 100m 이상으로 정의한다.

각도 필터는 이전 위치, 현재 위치, 다음 위치를 연결한 선의 각도 차를 측정하여 일정 각도를 넘지 않을 경우 현재 위치를 노이즈로 판단한다. 이 연구는 각도 필터의 각도 차를 45°이하로 정의한다.

3.3 군집 노이즈 제거 기법

기본 필터를 거쳐 노이즈를 제거한다. 하지만 여전히 사용자가 머물러있을 때 발생하는 노이즈들로 인해 군집된 형태의 노이즈가 발생한다. 명확한 이동 궤적을 추출하기 위해서는 군집된 형태의 노이즈 제거가 필요하다.

따라서 본 논문에서는 사용자의 군집된 위치를 파악하기 위해 클러스터링 기법 중 하나인 DBSCAN (Density-based Spatial Clustering of Applications with Noise)[15]을 이용하여 이동 궤적에서 군집된 위치를 파악하고 이를 제거한다. 그림 2는 DBSCAN 기반 필터링의 예를 보인다. 그림 2(a)는 사용자의 이동 궤적 중 하나로 가운데 마킹된 부분이 머무르는 지점으로 판단된다. 그림 2(b)는 DBSCAN을 통하여 군집된 지점으로 파악된 점들을 삭제한 결과이다. 군집된 점들이 삭제됨으로써 이동 궤적이 단순하고 명료해진 것을 알 수 있다.

Fig. 2.

An example of DBSCAN-based filetering, (a) Before the filtering, (b) After the filtering

하지만 DBSCAN은 위치에 대한 정보만을 이용하기 때문에 왕복하는 이동 궤적에 대하여 머무르는 지점을 구분하지 못하고 모두 삭제되는 경우가 발생한다. 즉 그림 2(a)의 경우 마킹된 부분은 위로 올라가는 경로와 내려오는 경로가 모두 군집된 지점으로 식별되어 삭제되기 때문에 실제로 내려오는 경로만 봤을 때 사용자가 머무르는 지점이 없다고 하더라도 모두 삭제해버리는 문제를 지닌다. 따라서 본 논문은 경로가 겹쳐져 모두 삭제되는 문제를 해결하기 위하여 Sequenced DBSCAN을 제안한다.

Sequenced DBSCAN은 DBSCAN과 다르게 랜덤으로 한 점을 선택 후 선택된 점으로부터 슬라이딩 윈도우를 이용하여 이웃 반경을 설정한다. 또한 설정 파라미터 이웃 반경 내 최소 점 개수를 통해 밀집 영역을 결정한다. 표 2는 제안하는 Sequenced DBSCAN 알고리즘의 pseudo-code를 보인다.

Table 2.

Sequenced DBSCAN algorithm

제안 알고리즘은 기존의 DBSCAN 알고리즘[16]에서 슬라이딩 윈도우를 적용하는 방식으로 개선한다. 입력 값은 설정 파라미터 최소 점 개수(minPts), 이웃 반경(r), 슬라이딩 윈도우 크기(winSize)이며, 알고리즘을 통해 생성된 클러스터(C)를 반환한다. 반환된 클러스터는 머무는 지점이라고 파악되므로 해당 클러스터들을 제거한다. 이 연구에서는 minPts를 15로 설정하고 이웃 반경을 20m로 설정하였다.

그림 3은 Sequenced DBSCAN 기반 필터링의 예를 보인다. 그림 3(a)는 Sequenced DBSCAN을 통하여 군집된 지점으로 파악된 점들을 삭제한 결과이다. 군집된 점들을 삭제할 때, 일정 반경 내의 모든 점들이 삭제되므로 이동 궤적에서 해당 반경 내의 결측값이 발생한다. 만약 군집된 지점의 반경이 넓다면 삭제되는 지점의 양이 많아지므로 사용자의 이동 궤적은 그만큼 끊기는 지점이 넓어진다.

Fig. 3.

An example of sequenced DBSCAN-based filtering, (a) Occurence of missing value, (b) Imputation result

따라서 본 논문은 이러한 결측값을 대체하기 위해 두 가지 방법을 이용한다. 첫 번째 결측값 대체 방법은 군집된 점들을 삭제할 때 군집 지점으로 안으로 들어간 직후의 점들과 군집 지점 밖으로 나가기 직전의 점들을 남겨둠으로 반경의 공백을 메운다. 이때 남겨두는 점들의 수는 사용자의 평균 이동 속도를 군집의 반경으로 나누는 것으로 구한다. 두 번째 결측값 대체 방법으로는 군집된 점들을 삭제할 때 일정 시간마다 점 한 개씩을 남겨 군집된 지점을 채운다. 그림 3(b)는 결측값을 대체한 결과를 보인다.

3.4 이동 궤적 정제 프로세스

명확한 이동 궤적의 정제를 위해서는 기존 필터 및 제안 필터의 적용 순서를 최적화해야 할 필요가 있다. 그림 4는 본 논문에서 제안하는 이동 궤적 정제 프로세스를 보인다. 제안 프로세스는 최적화된 필터 적용 순서를 의미한다.

Fig. 4.

Trajectory refinement process

필터 적용 순서는 1~3번을 통하여 우선 수집된 위치 정보들의 나열로부터 이동 궤적들을 구분한다. 이는 범위 필터로 정해진 범주 이외의 점들을 제거한 후, 시간 필터와 먼 거리 필터를 적용하여 현재 위치가 이전 위치와 시간적, 거리적 차이가 있을 경우 새로운 이동 궤적을 생성하도록 한다. 이후, 4~7번을 통해 모든 이동 궤적들에 대하여 속도 필터, 짧은 거리 필터, 첫 번째 결측값 대체를 적용한 Sequenced DBSCAN, 각도 필터를 순서대로 적용한다.

4.1 실험 방법

본 논문은 제안 프로세스의 우수성을 검증하기 위하여 기본 필터 및 제안 필터의 조합들 중 최적의 필터 조합을 찾는다. 비교를 위하여 기본 필터 및 제안 필터들의 조합들을 데이터셋에 적용하여 정제한 후, 수작업 정제를 통해 각 필터 조합의 효율성을 비교 평가한다.

이 실험에 사용하는 데이터셋 DSEM-Traj2018은 총 39명을 대상으로 170일 동안 GPS, 심박수, 3축가속도 데이터를 수집한 라이프로그 데이터셋이다. 이 중 실험을 위하여 100개의 이동 궤적을 추출하여 사용한다.

이 실험에서 사용하는 필터는 총 12개로 그 종류는 표 3과 같다. ①번은 기본 필터 중 범위, 시간, 긴거리 필터를 순서대로 적용시킨 방법(3filter)이다. ②번은 기본 필터 중 범위, 시간, 긴거리, 속도, 짧은거리 필터를 순서대로 적용시킨 방법(5filter)이다. ③번은 앵글 필터, ④번은 DBSCAN, ⑦번은 Squenced DBSCAN (Seq_DBSCAN)을 의미한다. ④번과 ⑦번은 각각 DBSCAN을 수행하면서 삭제되는 부분의 결측값이 발생하는데 ⑤ DBSCAN_f&b, ⑥ DBSCAN_30s, ⑧ Seq_DBSCAN_f&b, ⑨ DBSCAN_30s는 각각 3.3절에서 설명한 결측값 대체 기법을 DBSCAN과 Sequenced DBSCAN에 적용시킨 필터이다.

Table 3.

Types of filter

본 논문에서 제안하는 필터의 적용 순서는 3.4절에서 제안하는 바와 같이 ②, ⑧, ③이다. 이 실험은 제안 필터인 첫 번째 결측값 대체 방법을 사용한 Sequenced DBSCAN (Seq_DBSCAN_f&b)의 우수성 검증과 제안 필터 적용 순서가 최적화된 프로세스임을 검증하기 위하여 다양한 필터들의 조합을 이용하여 비교 평가를 수행한다. 표 4는 이러한 필터들의 조합을 보이며, 본 논문은 제안하는 필터들의 조합은 6번과 같다.

Table 4.

Combinations of filters for experiment

이 실험은 11개의 필터 조합의 효율성을 평가하기 위하여 수작업 정제를 통한 각각의 데이터셋을 만드는 것으로 이루어진다. 수작업 정제는 사람이 수집된 이동 궤적들을 직접 보며 머무르는 지점이나 노이즈를 일일이 제거하는 방법을 의미한다. 따라서 이 실험은 수작업 정제를 거친 데이터셋을 일종의 정답셋으로 설정한다. 만약 어떤 데이터셋을 수작업으로 정제할 때 많은 작업양이 발생한다면, 그 데이터셋을 정답셋으로 만들기 위한 노력은 수작업의 작업양만큼 요구된다고 볼 수 있다. 또한, 동일한 데이터셋에 두 필터 조합을 각각 적용한다고 할 때, 필터를 거친 결과로 생성된 두 데이터셋을 다시 수작업 정제를 거칠 경우, 각각의 작업양은 해당 필터 조합이 얼마나 효율적으로 노이즈를 제거했는지를 판단할 수 있는 기준이 될 수 있다.

수작업 정제 시 작업 양의 측정을 위하여 자체 개발한 이동 궤적 정제 도구를 이용한다.

그림 5는 이동 궤적 정제 도구의 스크린샷을 보이며, 이 도구는 정제를 위한 행동을 할 때 발생한 이벤트를 로그로 기록한다.

Fig. 5.

A screenshot of a trajectory refinement tool

로그의 종류로는 delete_point, delete_before, delete_after, delete_set, split의 총 5가지로 구분된다. delete_point는 선택된 점을 지우는 행위로 하나의 점만 지워진다. delete_before는 선택된 점부터 이전 점들을 전부 지우는 행위, delete_after는 선택된 점부터 이후 점들을 전부 지우는 행위이며, delete_set은 현재의 이동 궤적을 전부 지우는 행위이다. split 경우는 현재 점을 기준으로 이전 점들과 이후 점들을 다른 이동 궤적으로 구분한다. 이러한 도구를 이용하여 정제 시 발생한 로그의 수와 로그 종류별로 지워진 점들의 개수를 집계한다. 또한, 정제 후 남은 이동 궤적 수도 집계한다.

4.2 실험 결과 및 평가

표 5는 27,266개의 점으로 이루어진 100개의 이동 궤적에 11개의 필터 조합을 적용시킨 후, 생성된 11개의 데이터셋을 이동 궤적 정제 도구를 이용하여 수작업 정제를 수행하였을 때의 로그 수, 총 삭제된 레코드 수, 로그 당 선택된 레코드 수, 로그 종류를 나타낸다. 7번 조합의 경우 로그 수가 179개, 총 삭제된 레코드 수 475개로 전체 필터 조합들 중 로그가 가장 적게 발생하였다. 또한, 6번, 11번 조합도 각각 로그 수가 221개, 220개이며 삭제된 레코드 수도 613, 645개로 다른 조합들에 비해 비교적 적은 수의 수작업 정제가 이루어진 것으로 확인되었다. 이는 7, 6, 11번의 조합들이 그만큼 더 효율성이 높다고 볼 수 있다.

Table 5.

Number of deleted records by log

표 6은 수작업 정제 후 남은 점 개수, 남은 궤적 수, 궤적 당 점 개수를 보인다. 앞서 높은 효율을 보였던 6번, 7번, 11번 조합을 보았을 때 각각 5556개, 5104개, 5124개의 점이 남았고, 하나의 궤적 당 각각 46.689개, 42.891개, 43.795개의 점이 남은 것으로 측정되었다. 수작업 정제 후 남은 점의 개수는 최종적으로 경로 학습에 이용될 데이터의 양을 의미하며, 남은 점의 개수가 적을수록 해당 필터들의 조합 및 수작업 정제가 더 많은 데이터를 삭제했다는 것을 의미한다.

Table 6.

Remaining number after refinement

적용된 필터 조합의 우수성을 평가하기 위해서는 단순히 수작업의 로그 수와 함께 수작업 정제 이후 남아있는 점들의 개수도 함께 확인해 보아야 한다. 만약 어떤 필터 조합이 노이즈와 관계없이 점들을 삭제한다고 한다면, 많이 삭제할수록 노이즈가 삭제되는 양도 증가할 것이다. 이는 수작업 정제 시 노이즈의 삭제 양이 많으므로 효율적인 필터 조합으로 보일 수 있다. 하지만 노이즈가 아닌 명백한 이동 궤적에 포함되는 점들도 함께 삭제되기 때문에, 필터 조합의 평가는 수작업 정제 후 최종적으로 남아있는 데이터의 양도 함께 고려해야 한다.

표 7은 실험 결과를 토대로 기존 필터와 제안하는 필터간의 정성 평가를 보인다. 비교를 위하여 2, 11, 7, 6번 필터 조합을 선정하였다. 이 필터 조합들은 동일한 기본 필터 조합의 5번째 순서에 DBSCAN, Seq_DBSCAN, Seq_DBSCAN_f&b 기법을 각각 삽입한 조합들이다. 이를 통하여 기존의 기본 필터, DBSCAN 기법과 제안 알고리즘인 Seq_ DBSCAN, Seq_DBSCAN_f&b 기법들의 상대적인 성능 차이를 명확히 확인할 수 있다.

Table 7.

Qualitative evaluation among basic filters and proposed filter

평가 결과 기본 필터들만을 이용할 경우 수작업 정제 시 다른 기법들에 비해 여전히 많은 노이즈가 존재하여 필터의 효율성이 떨어지는 것을 볼 수 있다. 또한, DBSCAN과 Seq_DBSCAN_f&b는 각각 노이즈를 제거하는 수가 많아 높은 효율성을 보이며, 특히 Seq_DBSCAN은 가장 적은 로그 수를 지니므로 매우 높은 효율성을 보인다.

하지만, 노이즈 제거의 정확성으로 보았을 때는 Seq_DBSCAN_f&b는 다른 필터들에 비해 노이즈가 아닌 점들을 덜 지우는 것을 알 수 있다. 이는 반대로 DBSCAN이나 Seq_DBSCAN이 군집된 점들의 제거 시 필요 이상으로 지운다는 것을 의미하며, 결측값 대체 기법이 효과적으로 작용한다고 볼 수 있다.

결론적으로, 제안 기법인 Seq_DBSCAN_f&b를 적용한 6번 필터 조합이 다른 필터들에 비해 상대적으로 필터의 효율성과 노이즈 제거의 정확도가 높아 최적의 성능을 지님을 알 수 있다.