JOURNAL OF THE KOREAN SOCIETY OF CIVIL ENGINEERS. June 2019. 461-467
https://doi.org/10.12652/Ksce.2019.39.3.0461


ABSTRACT


MAIN

  • 1. 서 론

  • 2. 선행 연구 고찰

  • 3. 연구 방법

  •   3.1 실험 데이터

  •   3.2 군집 분석

  •   3.3 순차 패턴 분석

  • 4. 결 론

1. 서 론

위치 인식 기술의 발전과 IoT (Internet of Things) 기술의 발달은 방대한 이동 데이터를 생성하고 있다. 대용량 이동 데이터의 분석을 통하여 이동 객체들의 모델링 혹은 숨겨진 패턴을 파악하여 도시 계획, 도시 흐름 파악, 지속가능한 도시관리 시스템, 환경 및 안전 등에 활용되고 있다(Mazimpaka and Timpf, 201610). 특히 대용량 이동 데이터의 기종점(Origin-Destination) 분석은 도시 흐름과 운송 수요 및 지역간 연계성에 대한 풍부한 정보를 제공한다.

실례로 Kakao(2018)9는 다년간의 Kakao 사용자들의 모빌리티 데이터를 분석하여 실시간 교통정보 제공하고, 정확한 예측을 통하여 보다 나은 이동 정보를 사용자에게 제공하려고 노력하고 있다. 하지만, 이러한 분석 방법은 대부분 단순 통계에 의한 방법에 의존하고 있다. 본 연구는 택시 이동데이터의 승차 패턴을 분석 후 승차 패턴이 지속적으로 발생하는 순차 빈번 패턴을 분석하였다. 따라서, 단순 스냅샵 기반의 분석이 아닌 택시 승차가 발생하는 구간이 어떻게 순차적으로 빈번하게 발생하는지를 살펴보았다.

최근 이동 데이터 분석을 위한 방법의 연구는 크게 네 가지 범주 -- 군집 분석(Clustering), 분류 분석(Classification), 빈도 분석(Frequent pattern mining), 외도 분석(Outlier detection) -- 로 분류 할 수 있다(Zheng, 201513). 본 연구는 이동 데이터 분석을 위하여 위와 같은 방법들의 조합을 통한 이동 데이터의 택시 승차 빈번 패턴을 분석하였다. 택시 승차 지점들의 군집 분석을 통하여 어느 지역에서 택시 승차지점들이 군집 되는지를 분석한 후 이러한 군집 분석 결과를 기종점 분석의 기본 유닛(Base unit)으로 사용하였다. 다음으로 군집에 기반하여 택시 승차가 연속적으로 빈번하게 일어나는 패턴을 분석하였다.

본 논문의 구성은 이동 데이터 분석을 위한 기존 연구의 방향과 본 논문과의 차이점에 대하여 논의한 후 본 연구의 방법과 실험 결과에 대하여 3장 연구 방법에 서술 하였으며 마지막으로 연구 결과의 토의와 향후 연구과제 등에 대하여 4장 결론에서 논의하였다.

2. 선행 연구 고찰

대용량 이동 데이터의 분석은 기계학습(Machine learning) 분야와 공간분석(Spatial analysis) 분야에서 다양하게 발달되어 왔다. 기계학습 방법 중 군집 분석(Clustering analysis)은 이동 데이터의 특성에 따라서 이동 데이터를 그룹화하여 이동 데이터를 묘사하기 위해 사용한다. 전통적인 군집 분석 방법인 DBSCAN (Density based spatial clustering of applications with noise) (Esteret al.,19965)과 OPTICS (Ordering points to identify the clustering structure) (Ankerst et al., 19992) 방법이 이동 데이터의 유사성 분석을 위한 함수(유사 이동 경로, 유사 이동 출발지 및 목적지, 유사 방향 등)와 함께 이동 데이터의 군집 분석을 위해 사용되었다(Rokach, 200912).

그러나 군집 분석 방법이 이동 데이터의 유사성을 분석하여 그룹화 하기에는 좋지만 이러한 패턴이 어떻게 지속적으로 발생하는지를 알기에는 한계가 있다. 따라서, 본 연구는 DBSCAN을 통해 택시 승차점들의 군집을 분석한 후 빈번 패턴 마이닝(Frequent pattern mining)을 접목시켜 발견된 군집을 기준으로 택시 승차 이동 지역이 어떻게 변해가는지를 분석하였다. 빈번 패턴 마이닝은 이동 데이터에서 이동 객체에 의하여 빈번하게 발생되는 이동 경로를 추출하기 위해서 사용하는 방법이다. 빈번 이동 패턴은 이동 경로의 공간적 혹은 시공간적 특징을 사용하여 분석할 수 있다(Cao et al., 20054). 본 연구는 이동 경로의 시퀀스 유사성을 분석하여 택시 이동 경로의 순차 이동 패턴을 분석하였다. 예로, 시퀀스 분석이란 택시가 강남지역에서 승객을 승차한 후 다음에는 서울역 근처, 다음으로는 용산역 근처 등 택시의 승차 위치의 연속적인 정보를 분석하여 이동 패턴을 분석하는 것을 말한다.

또한, 본 연구의 택시 이동 데이터는 택시의 승차와 하차 지점의 위치를 이용하여 분석하는 기종점 분석(Origin-Destination analysis)이다. 기종점 분석은 정확한 이동 데이터의 경로 정보 없이 출발점과 도착점의 정보를 가지고 이동 데이터를 분석하는 형태의 분석 방법이다. 기존 공간분석 방법 중 기종점 분석으로는 전체 기종점 데이터에서 예외적인 패턴(예: 이동 데이터 양)이 발생하는 Outlier trajectories를 Robust statistics 방법을 이용하여 발견하는 연구(Jeong et al., 20188)와 Spatial scan 방법을 적용하여 기종점 패턴이 전체 주요 패턴과 다른 것들을 찾아내는 연구(Gao et al., 20186)로 진행되었다. 혹은 자기공간상관분석법(Local spatial autocorrelation) (Anselin, 19952; Ord and Getis, 199511)을 이용하여 이동 데이터의 핫스팟을 찾기 위한 분석이 진행되었다. 그러나 위에 논의된 연구들은 스냅샷 기반의 데이터 분석방법이다. 스냅샵 분석은 시간적 변화의 분석을 고려하지 않고 특정 시간에 해당하는 현상을 분석하는 것을 말한다. 본 연구는 기종점 이동 패턴이 시간이 지남에 따라서 순차적으로 어떻게 발생하는지를 발견하는 것을 목표로 하였다.

그리고 기종점 분석은 가변적 공간단위 문제(Modifiable areal unit problem)를 포함하고 있다. 가변적 공간단위 문제란 위치에 의해 결정된 분석을 위한 기본 단위(영역)의 변경으로 인해 일관되지 않는 결과를 도출하는 문제점이다. 이러한 문제점을 해결하기 위하여 Kernel 기반의 이동 흐름 측정과 평활화(Smoothing) 방법이 사용되었다(Guo and Zhu, 20146). 본 연구에서는 기종점 분석의 기본 단위 추출을 위하여 군집분석에 의하여 형성되는 영역을 기본 단위로 사용하였다.

3. 연구 방법

3.1 실험 데이터

본 연구는 서울특별시 택시 운행 데이터인 2016년 1월 25일부터 31일까지의 일주일 택시 운행 데이터를 사용하였다. 택시 이동 정보는 차량번호, 시간, 운전자 ID, 위치 정보, 승빈차 코드(공차→공차:0, 공차→승차:1, 승차→공차:2, 승차→승차:3)를 포함한다. 택시 이동 데이터는 약4천만건의 4 GB데이터가 기록되어 있다. 본 연구에서는 전체 데이터 중 아침 출근 시간인 7시부터 9시 사이의 택시 승차 이동 패턴을 분석하였다. 대용량의 데이터에 대한 Data cleaning process를 위하여 본 연구는 Amazon Web Service (AWS)의 Hadoop 서비스인 Elastic MapReduce (EMR)을 사용하여 실험에서 필요한 택시 기종점 데이터를 추출 하였다. 본 연구를 위한 시스템 아키텍처는 Fig. 1과 같다. 택시 데이터를 AWS의 S3 bucket에 로딩 후 key-value기반의 데이터 시스템인 AWS의 Hadoop 시스템인 EMR을 통하여 데이터 cleaning프로세스를 거친 후 추출된 데이터들은 R프로그램을 사용하여 군집분석 및 순차 패턴 분석을 구현하여 데이터를 분석하였다.

http://static.apub.kr/journalsite/sites/ksce/2019-039-03/N0110390310/images/Figure_KSCE_39_3_10_F1.jpg
Fig. 1.

System Architecture and Data Analysis Process

3.2 군집 분석

본 연구는 택시 기종점 데이터의 승차 지점 군집 분석을 통하여 이동 순차 패턴 분석을 위한 이동 데이터의 기본 단위를 설정하였다. 군집 분석 방법으로는 공간분석에 자주 사용되는 밀도기반 군집분석 방법인DBSCAN 방법을 사용하였다. DBSCAN 방법은 임의 모양의 객체를 식별할 수 있고, 사전에 군집의 수 등을 요구하지 않기 때문에 공간 데이터 분석 등에 자주 사용된다.

DBSCAN 방법은 이웃간의 최대 반경(eps)과 반경 안에 최소 객체의 수(minPts)를 파라미터로 사용한다. 이 두 매개 변수를 사용하여 이동 객체간의 도달 가능성을 정의할 수 있다. 예를 들어, 객체 P1 이 eps내에 있고, minPts가 사용자 정의 임계값보다 크면 객체 P1 은 객체 Q에 직접 밀도 도달(Density-reachable) 가능하다고 표현한다(Ester et al., 19965). 그 다음 그러한 점들이 eps내에 있고 군집의 일부가 되어 연결된다면, 우리는 객체 P1, P2,…, Pn이 점 Q에서 밀도 도달 가능하다고 말할 수 있다.

Fig. 2는 2016년 1월 28일(목요일) 오전 7시부터 9시 사이의 택시 승차지점에 대한 군집 분석 결과이다. Fig. 2는 군집이 되지않고 산발적으로 분포된 정보는 노이즈로 간주하여 제거한 후 표시하였으며 각 색상은 서로 다른 군집을 표현하는 것이다. DBSCAN 알고리즘을 사용하기 위해서는 두개의 파라미터 값을 이용해야하는 데 이 파라미터 값을 정하는 기준은 Ester et al.(1996)5가 제안한 군집의 갯수가 일정하게 유지되는 임계점을 기준을 파라미터를 세팅하였다.

http://static.apub.kr/journalsite/sites/ksce/2019-039-03/N0110390310/images/Figure_KSCE_39_3_10_F2.jpg
Fig. 2.

Taxi Pick-Up Location Clustering using DBSCAN on Jan. 28, 2016

Fig. 3은 반경(eps)을 50 m, 80 m, 100 m, 120 m, 150 m, 200 m, 250 m, 300 m로 변경함에 따라서 군집의 개수가 변경되는 것을 보여주고 있다. Fig. 3에 80 m와 100 m 반경에서 군집의 수가 일정한 반면(약, 113개) 다른 반경에서는 급격하게 군집의 수가 변경되는 것을 볼 수 있다. 따라서, 일정한 군집의 개수를 보여주는 100 m를 군집분석 반경 파라미터로 설정하였으며 반경 안에 객체 수는 동일한 과정을 통하여 20개로 설정하였다.

http://static.apub.kr/journalsite/sites/ksce/2019-039-03/N0110390310/images/Figure_KSCE_39_3_10_F3.jpg
Fig. 3.

Number of Clusters by Varying Eps

3.3 순차 패턴 분석

본 연구는 군집분석을 통하여 추출된 영역을 기준으로 택시 승차 패턴이 어떻게 지속적으로 발생하는지를 분석하였다. 빈번 패턴 마이닝의 한 종류인 순차 패턴 분석(Sequence pattern analysis)은 시간에 따른 발생 이벤트를 찾는 방식으로 마케팅 분야에서 사용되는 분석 방법이다(Agrawalet al., 19931). 즉, 시퀀스데이터에 대해 일정비율 이상의 지지도를 갖는 모든 시퀀스를 찾는 것을 순차 패턴 분석이라 한다. 이는 빈번한 시퀀스 집합과 나타나는 순서를 발견하는데 도움이 된다. 예로 시퀀스 정보에 대한 효율적인 데이터베이스 및 색인 구축, 자주 발생하는 패턴 추출, 유사성에 대한 시퀀스 비교, 누락 된 시퀀스 구성원 복구를 수행 할 수 있다. 이를 수행하기 위해 시퀀스 데이터베이스에 최소 지원 임계 값(minimum support threshold) 혹은 최소 발생건수(count) 매개변수를 지정해야 한다. 최소 지원 임계 값은 전체 발생 시퀀스 중에서 해당 시퀀스가 발생하는 비율을 말하며 최소 발생건수는 해당 시퀀스가 발생하는 건수를 말한다. 본 실험에서는 시퀀스의 최소 발생건수를 20건으로 설정하였다.

Fig. 4는 전체 군집 중에서 상위 20개의 순차 패턴 결과를 지도상에 군집 정보와 막대그래프로 보여주고있다. 막대그래프에 숫자는 각 군집의 번호를 뜻하는 것으로 9:강남지역, 6:용산역, 15:서울시청, 7:동대문, 21:여의도를 뜻한다. 또한 막대그래프의 세로축은 각 시퀀스가 발생하는 최소 지원 임계 값을 나타낸다. Fig. 4에서 보이는 것과 같이 강남 지역에서 7시에서 9시사이 한번의 승차를 하는 패턴이 가장 많이 발생하며 강남지역에서 두번, 세번, 네번, 혹은 5번의 승차를 연속적으로 하는 패턴도 자주 발생하는 것을 발견하였다. 또한, 강남에서 서울시청 방향, 용산역에서 서울시청, 강남역에서 용산역 방향의 승차 패턴도 자주 발생하는 패턴으로 발견되었다. 또한, 2016년 1월 25일(월요일), 26(화요일), 27(수요일), 29(금요일)의 주중 데이터에 대한 승차 패턴을 Fig. 5에 표시하였다. 비록 군집 분석 후 각 지역의 군집 번호는 바뀌었어도 주중의 승차 패턴이 비슷하게 발생 하는 것을 알 수 있었다.

http://static.apub.kr/journalsite/sites/ksce/2019-039-03/N0110390310/images/Figure_KSCE_39_3_10_F4.jpg
Fig. 4.

Top 20 Frequent Event Sequences on Jan. 28, 2016

http://static.apub.kr/journalsite/sites/ksce/2019-039-03/N0110390310/images/Figure_KSCE_39_3_10_F5.jpg
Fig. 5.

Top 20 Frequent Event Sequences on Jan. 25, 26, 27, and 29, 2016

Table 1은 1월 28일날 강남지역(9)이 포함되는 순차 패턴 중에서 상위 10개의 순차 패턴을 추출하여 정리한 표이다. 강남지역이 포함된 승차 패턴은 대부분 강남지역 안에서 연속적으로 발생하였으며 강남과 서울시청주변(15), 용산역(6), 동대문(7) 지역과 연속적인 승차 패턴이 자주 발생하는 것을 발견 할 수 있었다. 그러나 최소 지원 임계 값(support)과 발생 건수(count)에서 볼 수 있듯이 주도하는 대부분의 시퀀스는 강남지역 안에서 연속적으로 발생하는 승차 패턴이 주도적으로 발생하였다.

Table 1. Top 10 Subsequences Contains Given Gagnam Events

Subsequence Support Count
(9) 0.380 920
(9)-(9) 0.217 525
(9)-(9)-(9) 0.124 301
(9)-(9)-(9)-(9) 0.080 193
(9)-(15) 0.062 150
(6)-(9) 0.052 127
(9)-(6) 0.050 121
(9)-(9)-(9)-(9)-(9) 0.049 119
(15)-(9) 0.045 108
(7)-(9) 0.032 78

Fig. 6은 주말의 택시 승차의 순차 빈번 패턴을 분석한 결과이다. 막대그래프의 숫자들은 8:신사-강남역, 12:삼성-역삼, 2:홍대, 19:강동역, 6:건대, 28:동대문 지역을 표현한다. Fig. 4의 주중 택시 승차 패턴과는 많이 다른 패턴을 보이는 것을 파악할 수 있다. 가령 주중에 여의도 지역에서 자주 발생하는 승차 패턴은 주말에서는 주요 순차 패턴에 포함되지 않는다. 또한, 주말에는 지역간 이동(예: 강남-서울시청, 용산역-서울시청, 강남역-용산역)의 순차 패턴은 발생하지 않으며 한 지역 내에서만 자주 발생하는 패턴들이 주로 이루고 있다. 주중에는 주요 패턴이 발생하는 지역이 아니었던 건대 주변 등에서의 승차 패턴이 발생하는 것도 다른 현상이었다.

본 연구는 승차 패턴 분석을 위해서 군집 분석으로 탐색된 영역을 기본 단위로 설정 하였는데 본 연구와의 비교분석을 위하여 기본 단위를 행정동 경계로 순차 패턴 분석을 실시하였다.

http://static.apub.kr/journalsite/sites/ksce/2019-039-03/N0110390310/images/Figure_KSCE_39_3_10_F6.jpg
Fig. 6.

Top 20 Frequent Event Sequences on Jan. 30, 2016

Fig. 7은 행정동 경계를 기본 단위로 택시 승차 순차 패턴 분석을 실시한 결과이다. Fig. 7에서 표시하는 번호는 각 행정동 경계 번호를 뜻한다(예: 1123064 - 서울특별시 강남구 역삼1동, 1119054 – 서울특별시 영등포구 여의도, 1122054 – 서울특별시 서초구 서초4동). Fig. 4의 결과와 달리 행정동 경계를 기준으로 택시 승차 분석 시 지역간의 이동에 대한 결과를 찾을 수가 없었다. 또한 순차 패턴 분석이 택시 승차를 위한 고객이 많은 행정동을 위주로 주요 패턴이 발생하는 것을 발견할 수 있었다.

http://static.apub.kr/journalsite/sites/ksce/2019-039-03/N0110390310/images/Figure_KSCE_39_3_10_F7.jpg
Fig. 7.

Top 20 Frequent Event Sequences on Jan. 28, 2016 using a Different Base Unit

4. 결 론

본 연구는 서울특별시 택시 승차 위치에 대한 군집 분석을 수행 후 탐색된 영역에 기반하여 택시 승차가 연속적으로 발생하는 순차 패턴 분석을 실시하여 다음과 같은 결론을 얻었다.

실험 결과는 주중의 택시 분석은 강남지역에서 가장 많은 택시 순차 패턴이 발생하였으며, 강남과 서울시청 등 서로 다른 지역의 순차 패턴도 주요 승차 패턴 중에 하나로 발견되었다. 하지만 주말의 택시 승차 순차 패턴에서 주중에 승차가 많이 발생하는 여의도 근처의 승차 패턴은 주요 패턴으로 발생하지 않았으며 지역간 연계되는 승차 패턴도 찾을 수가 없었다. 이와 같은 결과는 주말에 회사 등이 주로 위치한 곳에서의 출근을 위한 승차 패턴이 주말에는 발생하지 않기 때문에 생긴다고 추측할 수 있다.

또한 본 연구는 순차 패턴의 기본 단위로 행정동 경계를 사용하여 택시 승차 순차 패턴을 분석하였다. 군집 분석을 이용한 기본 단위 설정과 다르게 행정동 경계에 따른 분석에서는 지역간 연계되는 순차 패턴을 찾을 수가 없었다. 행정동 경계에 의한 분석의 결과는 전체 교통 흐름을 파악하기 위한 교통 수요를 반영한 올바른 경계 설정이라고 볼 수 없다,

향후 보다 정확한 교통 예측을 위해서는 인구수, 교통 시설 등을 고려한 교통 분석 영역(Traffic analysis zone)을 설정하여 순차 패턴 분석을 실시하는 것이 의미 있을 것 같다. 현재는 이와 같은 교통 분석 영역의 정보가 부재하여 택시 승차 정보를 활용한 군집 분석을 통하여 교통 분석 영역을 설정하였다.

본 연구의 활용 방안은 기존 승차 순차 패턴 분석 결과를 바탕으로 택시 공차율을 줄이는데 활용할 수 있으며 교통계획 및 도시 흐름 파악 분야에도 활용할 수 있을 것으로 판단된다.

Acknowledgements

본 연구는 중소벤처기업부에서 지원하는 2018년도 산학연협력 기술개발사업(No. S2600206)의 연구수행으로 인한 결과물임을 밝힙니다.

본 논문은 2018 CONVENTION 논문을 수정·보완하여 작성되었습니다.

References

1 

Agrawal, R., Imieliski, T. and Swami, A. (1993). "Mining association rules between sets of items in large databases." In Proc. of the ACM SIGMOD International Conference on Management of Data, Washington, D.C., ACM, pp. 207-216.

10.1145/170036.170072
2 

Ankerst, M., Breunig, M. M., Kriegel, H. P. and Sander, J. (1999). "OPTICS: ordering points to identify the clustering structure." In Proc. of ACM Sigmod record, ACM, Vol. 28, No. 2, pp. 49-60.

10.1145/304181.304187
3 

Anselin, L. (1995). "Local indicators of spatial association-LISA." Geographical Analysis, Vol. 27, No. 2, pp. 93-115.

10.1111/j.1538-4632.1995.tb00338.x
4 

Cao, H., Mamoulis, N. and Cheung, D. W. (2005). "Mining frequent spatio-temporal sequential patterns." In Proc. of Fifth IEEE International Conference Data Mining, IEEE, pp. 82-89.

5 

Ester, M., Kriegel, H. P., Sander, J. and Xu, X. (1996). "A density- based algorithm for discovering clusters in large spatial databases with noise." In Proc. of 2nd International Conference on Knowledge Discovery and Data Mining, Vol. 96, pp. 226-231.

6 

Gao, Y., Li, T., Wang, S., Jeong, M. H. and Soltani, K. (2018). "A multidimensional spatial scan statistics approach to movement pattern comparison." International Journal of Geographical Information Science, Vol. 32, No. 7, pp. 1304-1325.

10.1080/13658816.2018.1426859
7 

Guo, D. and Zhu, X. (2014). "Origin-destination flow data smoothing and mapping." IEEE Transactions on Visualization and Computer Graphics, Vol. 20, No. 12, pp. 2043-2052.

10.1109/TVCG.2014.234627126356918
8 

Jeong, M. H., Wang, S. and Yin, J. (2018). "Outlier detection and comparison of origin-destination flows using data depth." In Proc. of 10th International Conference on Geographical Information Science, pp. 6:1-6:14.

9 

Kakao (2018). 2018 Kakaomobility Report. Available at: (Accessed: January 12, 2019).

10 

Mazimpaka, J. D. and Timpf, S. (2016). "Trajectory data mining: A review of methods and applications." Journal of Spatial Information Science, Vol. 13, pp. 61-99.

10.5311/JOSIS.2016.13.263
11 

Ord, J. K. and Getis, A. (1995). "Local spatial autocorrelation statistics: distributional issues and an application." Geographical Analysis, Vol. 27, No. 4, pp. 286-306.

10.1111/j.1538-4632.1995.tb00912.x
12 

Rokach, L. (2009). A survey of clustering algorithms. In Data mining and knowledge discovery handbook, Springer, Boston, MA, pp. 269-298.

10.1007/978-0-387-09823-4_14
13 

Zheng, Y. (2015). "Trajectory data mining: an overview." ACM Transactions on Intelligent Systems and Technology (TIST), Vol. 6, No. 3, p. 29.

10.1145/2743025
페이지 상단으로 이동하기