Extracting Typical User's Moving Patterns Using Deep Learning

Extracting Typical User's Moving Patterns Using Deep Learning

딥러닝을 사용한 사람들의 이동패턴의 추출

Globecom 2012 - Wireless Networking Sysposium

Nam Tuan Nguyen, Yichuan Wang, Husheng Li, Xin Liu, Zhu Han

ECS Department, University of Houston, Houston, TX

CS Department, University of California, Davis, CA

EECS Department, University of Tennessee, Knoxville, TN

Abstract

  여러 GPS 장치들이 스마트폰으로 통합되었을 때, 연구원들은 거대한 위치 데이터를 모을 수 있는 큰 기회와 맞닥드리게 되었다. 이것은 사용자들의 이동 행동과 유저의 다음 위치를 예측하는데 필수적이다. 일단 유저의 다음 지역을 결정할 수 있다면, 이것은 많은 응용에 사용되어질 수 있을 것이다. 위치기반서비스나 모바일 네트워크 또는 집에서 스케쥴링 하는 것과 같은 것에 사용되어 질 수 있을 것이다. 다음 위치를 예측하는 일에 가장 중요한 작업은 사용자의 패턴들을 분명히 하는 것이다. 이 논문에서, 우리는 딥러닝을 이용해서 패턴을 추출하는 방법을 제안할 것이다. 실험결과 기존의 요소분석적인 방법과 비교해서 제안된 방식은 만족할만한 성능의 향상을 보여주었다.

1. INTRODUCTION

  사용자의 이동패턴을 예측하는 것은 과거 몇 십년간의 연구자들의 항상 흥미있는 주제였다. 그러나, 스마트한 소규모 장치의 부족 때문에 최근에 스마트폰에 GPS가 들어가기 전까지는 절때 공급되지 않았다. 하지만 위치 예측을 위한 많은 작업들이 있었다. 대부분은 마코브모델에 기초하였다. 마코브 모델은 강력했다. 하지만 다양한 시간 또는 인간의 행동 패턴에서의 빈도를 이용하는 것에는 문제가 있었다. 예를들어 주중동안 6시에, 회사원들은 일반적으로 회사에 간다. 하지만 주말의 같은 시간대에 그는 집에 더욱 머무른다. 마코브 모델은 이러한 2가지 상황을 같은 방식으로 다룬다. 주말 아침 6시에 회사에가는 확률은 주중에 가는 확률만큼 높다. 게다가 만약 전형적인 사용자들의 이동패턴이 추출될 수 있다면, 그 것들은 다른 날동안의 이동패턴과 함께 마코프모델로 결합될 것이다. 제안된 방식은 만약 우리가 다음에 방문할 위치를 주어진 자정에서 아침까지의 위치정보를 가지고 예측하기 원한다면 하나의 독립적인 해결방안을 제공할 수 있다.

  사람의 이동패턴을 분명하게하기위한 존재하는 노력들은 2개의 주요한 접근방식으로 나뉘어질 수 있다. 첫번째방식은 빈도를 통한 전략이다. [6][7]은 가장 많이 방문한 방문지의 이동 시퀀스를 추출했다. 그럼에도 불구하고 이러한 접근은 유연함이 부족하다. 예를들어서, 사용자가 집에서 회사로가는 길에 마트에 잠깐들렸을때, 사용자는 이동 시퀀스를 저장하는 것을 멈춘다. e.g. [Home -> Office], 그리고 결과적으로 다음 위치를 예측하는데 시스템은 실패한다. 이와 더불어서, 만약 그들이 같은 시간 slot에 있다면 위치는 단지 같은 시퀀스에서 고려되어진다[7]. 이러한 조건은 실제 시나리오를 만족할 수 없다. 많은 요소들은 사용자들의 스케쥴에 영향을 미친다. 

  다른 접근 방식은 eigenbehavior(고유행동)이나 eigenplace(고유장소)를 추출하기위해 요소분석(PCA)에 기초하는 것이다. 고유행동은 우리의 매일 이동패턴의 주용한 요소이다. [5]에서 PCA를 사용하여 주말, 주중, 그리고 no-signal을 포함하는 3개의 주요한 이동패턴이 추출되었다. 저자들은 관찰된 데이터와 획득한 좋은 실험결과들을 가지고 미래의 위치를 예측하려고 시도하였다. 하지만 다 계층을 가진 딥러닝과 비교해서, PCA는 얕은 구조라는 거대한 단점을 가지고 있다. 다 계층의 딥러닝은 더 강력하며 유연하다. 왜냐하면 관찰한 것을 생성해내기 위해 많은 계층을 결합했기 때문이다. 더욱이, 단지 3개의 고유행동은 다양한 사람들의 이동패턴을 만들기에는 충분하지 않기 때문이다. 우리는 결과가 더 많은 일반적인 패턴들과 더 깊은 구조의 모델을 통해 더 개선 될 수 있을 것이라고 믿는다.

  인간의 관점에서 볼 때, 주어진 유저의 매일의 경로들에서, 우리는 대략적으로 몇개정도의 일반적인 패턴이 있는지 말할 수 있다. 우리의 뇌는 경로에 대해 다계층의 표현을 추출할 수 있다. 질문은 어떻게 표현들에 대해 다계층을 가진 인간의 뇌를 어떻게 엔지니어가 바꿀 것인가이다. 이론적인 결과들은 복잡한 추출 과정을 모델하기 위해서 깊은 구조를 사용해야 한다는 것을 제안한다. 그럼에도 불구하고, 딥러닝에서의 추론을 위한 솔루션은 형성되지 않았다. 왜냐하면 복잡한 구조와 최근까지 최초의 가중치를 설정하는효과적인 알고리즘의 부족했기 때문이다. 힌튼교수는 모델의 계층간의 pretrain 방식과 떨어진 부분에서의 영향을 상쇄하는 prior 설정을 제안했다. DBN은 PCA와 같은 얕은 구조보다 더 많은 응용에서 더 좋은 결과를 냄을 증명했다.[12]. 우리는 우리의 방법을 다음과 같은 측면에서 구분해 보았다.:

  첫번째로, 우리 지식을 최선을 다해서, 이것은 사람의 일반적인 이동패턴을 딥러닝을 적용해 추출하는 첫번째 시도였다. 딥러닝은 PCA보다 더 좋기 때문에, 우리는 더 좋은 결과를 얻을 수 있을 것이라 기대했다. 둘째로 패턴을 추출하기 위한 우리의 접근방식은, 유저들은 그들의 논리적인 위치를 수동적으로 레이블 할 필요 없다는 것이다. 마지막으로, 우리는 딥러닝을 유저들의 경로를 수집한 것에 적용시켰ㄷ. 그리고 PCA와 비교해서 딥러닝을 적용하여 더 적은 오류의 경로를 다시 생성할 수 있음을 증명하였다.

  이 논문의 나머지 부분은 다음과 같이 구성되었다. Section2에서는, 수집한 것에 대한 처리와 딥러닝에 입력하기 위한 경로를 표현했다. Section3에서, 우리는 딥러닝과 기본적인 요소인 RBM에 대해 논의 할 것이다. 실험결과는 Section4에서 있으며, 마지막으로 Section5에 결론이 있다.

2. DATA COLLECTION

 안드로이드 어플리케이션을 작성하고 GPS 신호를 30초마다 수집하기 위해서 HTC Wildfire S에 설치하였다. 데이터는 GPS 위치와 타임스템프로 구성되어있다. 다른 도시에서 사는 사람들의 그룹을 선택하고 그들의 일상의 루틴을 핸드폰을 통하여 수집하였다. GPS는 항상 켜져있는 핸드폰을 통해 수집하였고 지역들은 주기적으로 충전기에 연결되지 않았을 때 수집하였다. 데이터는 자동적으로 드롭박스 계정에 저장되었다. 유저의 경로는 그림1에서 보는 것 처럼 38일 동안 수집되었다.

  타임스템프에 기초하여, 같은 날의 GPS 데이터는 하나의 데이터 셋으로 그룹화하였다. 그림1에서 보는 것처럼 모든 측정된 지역은 784개의 작은 셀로 나뉘어졌다, (28x28) 픽셀의 이미지와 같은 형식으로. 그림2는 하루으 이동경로에 대한 예를 보여주고 있다. 여기서 왼쪽의 raw  trace는 오른쪽의 binary 이미지로 바뀐다. 이제 우리는 이미지 픽셀 값들이 binary하다고 추정할 수 있다. 하루동안, 만약 유저가 특별한 셀에서 발견되었다면, 그 셀은 1을 할당했다. 반면에, 나머지 셀의 값은 0으로 할당한다. 한 이미지는 하나의 1x784의 벡터로 만든다. 이 벡터는 다음 섹션에서 묘사하는 딥러닝을 위한 입력으로 제공할 것이다.

3. DEEP LEARNING BASICS

  이 부분은 요약하겠습니다. 이 논문에서는 RBM과 DAE에 대해서 매우 간략이 적어 놓았습니다. RBM과 DAE에 대해서 미리 학습한 후 읽는 것이 좋을 것 같습니다. 

  이동경로 추출을 위해서 저자들이 사용한 방식은 Deep Autoencoder(DAE)라는 딥러닝 방식 중 하나를 사용하였습니다. DAE는 RBM을 여러계층 쌓은 것을 DAE라고 합니다.

A. Restricted Boltzmann Machine

  RBM의 기본적인 내용과 어떻게 훈련 되어지는지 설명합니다. 이 논문보다 RBM에 대한 논문을 읽기는 것이 낳습니다. 

B. A Deep Auto-Encoder for Typical User's Moving Pattern Extraction

  그림4와 같이 Deep Auto-Encoder Network를 구성했습니다. 최상위 계층의 히든 유닛의 수가 7인 것은 사람이 일주일 동안의 이동패턴을 가지기 때문이라고 합니다.(월, 화, 수, 목, 금, 토, 일로 이동패턴을 나눴습니다.) 그리고 그림5에서 RBM에서의 훈련과 실제 어떻게 DAE를 구성했는지 그려 놓았습니다. 

C. Pretraining Phase

  Pretraining과정에 대해서 설명해 놓았습니다. 기본적인 내용으로 각 레이어를 RBM 훈련 시키듯 훈련 시켰다는 내용입니다.

D. Fine-tuning Phase

  Fine-tuning(미세조정)의 과정에 대해서 설명합니다. 여기서 사용한 방법은 Backpropagation을 사용하여 훈련시켰습니다. 훈련은 threshold 아래로 에러율이 감소 할 때까지 훈련시켰다고 합니다. 

E. Typical Pattern Extraction Algorithm

  알고리즘 1에서 보이는 것을 설명해 놓았습니다. 알고리즘 내용은 최소 가중치 W를 [-0.1,0.1] 사이의 값으로 초기화하고 pretraining합니다. 그리고 fine-tuning한 후, 네트워크의 최상위 계층의 7개의 히든 유닛 값을 저장합니다. 이 저장한 값이 일반적인 유저의 이동패턴이라고 말하고 있습니다.

4. EXPERIMENT RESULTS

  이번 섹션에서 우리는 딥러닝을 이용한 유저의 이동 경롤를 재생성하는 것을 평가할 것이다. 졸업한 학생들의 38일간의 이동 경로를 서택했다. , 30일은 학습에 사용했고, 나머지 8일은 테스팅에 사용하였다. 학습이 종료된 후, 가중치는 학습되어졌다. 테스트 경로은 네트워크의 입력으로 적용되었다. 그리고 모델의 경로를 재생성하는데 사용하였다. 우리는 히든유닛의 학습된 가중치를 가지고 성공적으로 테스트된 경로를 재생성했다는 것을 증명할 것이다. 그리고 결과를 평균 제곱근 오차를 기반으로 PCA와 비교할 것이다. 두 알고리즘의 mean square error(평균 제곱근 오차)는 입력된 경로와 재생성된 경롤 사이의 픽셀을 이용하여 계산할 것이다. 

  그림6은 입력된 경로를 딥러닝에 의해 재생성된 것과 대비하여 보여준다. 28x28 크기의 공간은 7로 줄었다. 비교율은 원래 경로를 표현하기위한 차원의 수와 최상위 래벨에서의 추출된 차원의 비율이다. 우리는 충분히 큰 압축률을 볼 수 있었다, 특히 PCA와 비교했을 때, 딥러닝의 성능은 여전히 주목할 만하다. 재생성된 경로는 원래의 것에 비해 크게 벗어나지 않았다. 두 경로의 평균 제곱근 오차는 5.3127이다.

  PCA의 결과와 비교해서, training과 testing data는 같은 것을 사용했다. 7개의 주요한 요소들은 경로를 재생성하기위해 추출되었다. 그림7에서 표현된 것 처럼, 딥러닝에 비해 좋은 않은 성능을 보여주고 있다. PCA 방식은 평균 제곱근 에러가 6.282*10^3으로, 딥러닝을 사용한 것에 비해 5.3127배나 높다. 분명히 PCA보다 딥러닝 방식이 더 좋은 성능을 보여준다. 딥러닝에서의 주목할만한 성능의 향상은 PCA가 2계층의 얇은 구조를 가지는 반면에 딥러닝이 깊은 구조를 가지기 때문이다.

  우리는 상위 계층에서의 히든 유닛을 다양하게 하여 더 테스트를 진행하였고 얻은 결과를 그림8에 나타내었다. 우리가 관찰 할 수 있는 것 처럼, 각 계층(layer)에서 히든 유닛의 수가 증가할 때, 성능도 증가한다는 것을 보여준다. deep network는 다른 경로의 집합을 생성하기 위한 더 많은 branch(부분)을 가질 수 있기 때문에 더욱 유연하고 강력하다. 하지만 복잡도도 동시에 증가한다. 이런 이유로, 응용에서, deep network는 성능의 요구조건과 복잡도의 요구조건을 둘 다 충족하도록 변경이 가능하다.

A. Possible Future Applications

 우리의 예비된 작업에서, 우리는 단지 일반적인 유저들의 이동패턴만을 추출했다. 그러나 많은 응용들은 우리의 결과에 기초하여 발전되어 질 수 있다. 예를 들어, 하루를 시작할 때, 우리는 학습된 이동 패턴을 오늘 방문할 수도 있는 지역의 확률의 집합을 생성에 이용할 수 있다. 수집된 지역에서의 강한 신호의 profile과 결합하여, 우리는 효과적으로 네트워크에 접근하기위한 효과적인 스케쥴링이 가능하다. 지연된 tolerant packet 전달은 패킷을 즉시 보내는 것과 비교해서 강한 신호를 유저가 가졌을 때까지 지연시킬 수 있다. 

  다른 응용은 주어진 지역에서 그날 시작부터 현태 시간까지 방문할 만한 지역을 예측하는 것이다. 새로운 데이터를 수집하자 마자, 그들은 deep network에 일반적인 패턴의 가중치를 학습하기 위해 전달한다. 가중치들은 저장된 다른 날들의 가중치와 매칭될 것이다. 그리고 그날의 나머지 시간 동안의 가증한  미래의 위치를 생성하여 가장의 유사한 이동패턴을 선택할 것이다. 이 테스트는 특별히 [5]에서 테스트 되었다. 딥러닝은 PCA에 비해 더 좋은 성능을 내기 때문에, [5]에서 사용한 PCA에 비해 우리의 알고리즘이 더 좋게 성능의 향상 시킬 것이라고 믿는다.

5. CONCLUSION

  

  이 논문에서, 우리는 일반적인 유저들의 이동패턴을 학습시키기 위해 4 계층의 deep network를 사용했다. 처음 단계로, 우리는 RBM의 학습알고리즘을 사용하여 각 계층을 pretraining 시켰다. 그리고나서 backpropagation은 네트워크를 finetuning 하였다. 실제 경로를 수집하여 이진파일로 바꾸었다. 기존의 방식과 비교하여 충분히 향상된 성능을 보여주었다. 우리의 예비의 결과는 또한 몇개의 유망한 응용분야를 제안 했으며 또한 더 많은 응용분야로 확장될 수 있을 것이다.

6. ACKNOWLEDGEMENTS

  저자들은 알고리즘을 테스팅하는데 사용하는 데이터를 Sophia Tsang이 도와주었음을 알린다.

7. REFERENCES

[1] H. Abu-Ghazaleh and A.S. Alfa, "Application of Mobility Prediction in

Wireless Networks Using Markov Renewal Theory;'  IEEE Transactions

on Vehicular Technology,  vol. 59, no. 2., pp. 788-802, February 2010.

[2] D. Katsaros and Y. Manolopoulos, "Prediction in wireless networks by

markov chains;'  Journal IEEE Wireless Communications,  vol. 16, issue

2, pp. 56-63, April 2009.

[3] J. K. Le and J. C. Hou, "Modeling Steady-state and Transient Be­

haviors of User Mobility: Formulation, Analysis, and Application;' in

proceedings of  the 7th ACM international symposium on Mobile ad hoc

networking and computing,  pp. 85-96, Florence, Italy, May 2006.

[4] B. Clarkson, "Life Patterns: structure from wearable sensors,"  PhD

thesis,  MIT Media Lab, 2002.

[5] N. Eagle and A. Pentland, "Eigenbehaviors: identifying structure in

routine,"  Behavioral Ecology and Sociobiology,  vol. 63, no. 7, pp. 1057-

1066, Apr. 2009.

[6] W. C. Peng and M. S. Chen, "Mining user moving patterns for personal

data allocation in a mobile computing system," in proceedings of  the

29th Int. Con! Parallel Processing,  Toronto, Canada, pp. 573-580, 2000.

[7] J. W. Lee, O. H. Paek, and K. H. Ryu, ''Temporal moving pattern mining

for location-based service,"  Journal of Syst. Software,  vol. 73, no. 3, pp.

481-490, Dec. 2004.

[8] F. Calabrese, J. Reades, and C. Ratti, "Eigenplaces: analyzing cities us­

ing the space-time structure of the mobile phone network,"  Environment

and Planning B,  vol. 36, no. 5, pp. 824836, Sep. 2009

[9] F. Calabrese, J. Reades, and C. Ratti, "Eigenplaces: segmenting space

through digital signatures,"  IEEE Pervasive Computing,  vol. 9, no. 1,

pp. 78-84, Jan.-Mar. 2011

[10] Y. Bengio, "Learning deep architectures for AI,"  Foundations and Trends

in Machine Learning,  vol. 2: no. 1, pp 1-127, Jan. 2009.

[11] I. Arel, D. Rose, and T. Karnowski, "Deep machine learning - a

new frontier in artificial intelligence research,"  IEEE Computational

Intelligence Magazine,  vol. 5, issue 4, pp. 13-18, Nov. 2010.

[12] G. E. Hinton and R. R. Salakhutdinov, "Reducing the dimensionality of

data with neural networks,"  Science,  vol. 313. no. 5786, pp. 504 - 507,

July 2006.

[13] D. H. Ackley, G. E. Hinton, and T. J . Sejnowski, "A learning algorithm

for Boltzmann machines,"  Cognitive Sci.  , vol. 9 , pp. 147-169, Jan.

1985.

[14] G. E. Hinton, S. Osindero and Y. Teh, "A fast learning algorithm for

deep belief nets,"  Neural Computation,  vol. 18, no.7, pp 1527-1554, Jul.

2006