표제지
목차
Abstract 14
제1장 서론 16
제1절 연구배경 16
제2절 연구내용 및 논문의 구성 19
제2장 관련 연구 21
제1절 궤적 데이터 마이닝 21
제2절 궤적 분석 방법에 따른 마이닝 기법 22
1. 궤적 데이터 클러스터링 기반 알고리즘 22
2. 궤적 데이터 분류 기반 알고리즘 23
3. 궤적 연관 규칙 기반 알고리즘 24
제3절 궤적 데이터 마이닝 Tool과 분석 방법 24
1. MinUS 24
2. T-pattern miner 27
제4절 궤적 데이터 마이닝 활용 분야 29
제3장 통계적 궤적 분석과 군집 최적화 방법을 이용한 HMM 기반 시간대별 이동 패턴 마이닝 32
제1절 통계적 분석 방법을 이용한 Stay Point 추출 알고리즘 33
1. 실험 Data set 34
2. 기존 Stay Point 추출 방법 35
3. 통계적 분석 방법을 이용한 실내 및 실외 Stay Point 추출 42
4. 구글지도를 이용한 시각화 62
5. 결과 값 Output 형식 63
제2절 군집 최적화 방법을 이용한 RoI 추출 알고리즘 64
1. DBSCAN 65
2. DBSCAN을 이용한 SP 군집화 67
3. 결과 값 Output 형식 71
제3절 HMM 기반 시간대별 이동 패턴 추출 알고리즘 72
1. 은닉 마르코프 모델 73
2. HMM을 이용한 이동 패턴 추출 76
제4장 실험 및 성능평가 92
제1절 실험 환경 92
제2절 통계적 분석 방법을 이용한 Stay Point 추출 알고리즘 92
1. SP 추출 결과 92
제3절 군집 최적화 방법을 이용한 RoI 추출 알고리즘 100
1. DBSCAN을 통한 SP 군집화 100
2. 기존 군집화 알고리즘과의 비교 102
제4절 HMM 기반 시간대별 이동 패턴 추출 알고리즘 105
1. HMM을 이용한 시간대별 이동 패턴 추출 105
2. T-pattern mining 알고리즘 111
3. T-pattern mining 알고리즘과의 성능 비교 평가 115
제5장 결론 120
참고문헌 122
국문초록 128
〈표 2-1〉 궤적 데이터 마이닝 활용 분야 29
〈표 3-1〉 Geolife 데이터셋 구성 34
〈표 3-2〉 기존 연구에서 사용한 임계값 설정 37
〈표 3-3〉 2번 유저의 날짜별 SP 궤적 분석 39
〈표 3-4〉 2번 유저의 날짜별 전체 궤적 분석 40
〈표 3-5〉 10번 유저의 이동 수단 46
〈표 3-6〉 가우시안 혼합 모델의 데이터 집합과 매개변수의 초기화 48
〈표 3-7〉 10번 유저 6월 18일 가우시안 평균값들 49
〈표 3-8〉 각 유저들의 이동수단 51
〈표 3-9〉 outdoor SP와 correction SP의 좌표 비교 60
〈표 3-10〉 outdoor SP와 correction SP의 데이터 크기 비교 62
〈표 3-11〉 추출된 SP 저장 형식 63
〈표 3-12〉 각 임계값에 따른 클러스터 개수와 품질 70
〈표 3-13〉 추출된 RoI 저장 형식 72
〈표 3-14〉 HMM 구성 요소 74
〈표 3-15〉 HMM의 확률 추론 방법 74
〈표 3-16〉 HMM를 적용할 때 해결해야할 문제 75
〈표 3-17〉 유저들이 각각의 상태로 이동할 확률 77
〈표 3-18〉 HMM의 매개변수 set 78
〈표 3-19〉 각 유저의 RoI 이동 순서 79
〈표 3-20〉 하루 동안의 RoI 이동 순서 79
〈표 3-21〉 초기 확률 벡터 계산 결과 80
〈표 3-22〉 각 유저들이 RoI에서 머물렀던 시각 81
〈표 3-23〉 quantile을 이용한 시간대 분할 83
〈표 3-24〉 관측 확률 계산 83
〈표 3-25〉 각 유저들의 하루 동안 이동한 RoI 이동 순서 84
〈표 3-26〉 상태 전이 확률 계산 84
〈표 3-27〉 계산 가능한 모든 상태열 85
〈표 3-28〉 동적프로그래밍을 통한 중복 계산 제거 86
〈표 3-29〉 전향 계산 방법 87
〈표 3-30〉 전향 계산을 통한 이동 확률 계산 87
〈표 3-31〉 viterbi 알고리즘을 통한 상태열 최적화 계산 방법 89
〈표 3-32〉 viterbi 알고리즘을 통한 최적 상태열 계산 90
〈표 4-1〉 실험 환경 92
〈표 4-2〉 각 알고리즘을 통해 생성된 SP 개수 93
〈표 4-3〉 각 알고리즘을 통해 생성된 SP 개수 비교 94
〈표 4-4〉 각 날짜별 SP 추출 개수 95
〈표 4-5〉 피어슨 상관계수를 통한 유사도 분석 95
〈표 4-6〉 추출된 SP 데이터 크기 비교 99
〈표 4-7〉 각 임계값에 따른 클러스터 개수와 품질 101
〈표 4-8〉 MinUS Tool에서 사용하는 임계값 수치 103
〈표 4-9〉 0번 유저의 데이터 105
〈표 4-10〉 0번 유저의 RoI 정보 105
〈표 4-11〉 0번 유저의 상태전이 확률 106
〈표 4-12〉 0번 유저의 관측 확률 107
〈표 4-13〉 0번 유저의 이동 패턴(시간대별) 108
〈표 4-14〉 0~100번 유저들의 데이터 110
〈표 4-15〉 0~100번 유저들의 이동 패턴 110
〈표 4-16〉 10-fold cross validation을 통한 이동 패턴 일치도 111
〈표 4-17〉 T-pattern miner parameter 112
〈표 4-18〉 0번과 4번 유저의 RoI 112
〈표 4-19〉 T-pattern miner를 이용한 0번, 4번 유저의 빈발 패턴 113
〈표 4-20〉 임계값 변경을 통한 0번과 4번 유저의 이동 패턴 114
〈표 4-21〉 임계값 변동으로 인한 빈발 이동 패턴 개수 변화 115
〈표 4-22〉 T-pattern miner와 제안 알고리즘의 패턴 비교 115
〈표 4-23〉 각 유저별 의미 있는 지점 상위 3곳 118
〈표 4-24〉 T-pattern miner와 제안 알고리즘의 정확도 비교 118
〈표 4-25〉 T-pattern miner와 제안 알고리즘 비교 요약 119
〈그림 2-1〉 유클리디언 공간을 이동하는 궤적 데이터 22
〈그림 2-2〉 도로 네트워크를 이동하는 궤적 데이터 22
〈그림 2-3〉 궤적 데이터 클러스터링 및 분류 기법 23
〈그림 2-4〉 궤적 연관 규칙 24
〈그림 2-5〉 MinUS 아키텍처 25
〈그림 2-6〉 User similarities by three methods (Geolife) 26
〈그림 2-7〉 User similarity w.r.t. temporal semantics (Geolife) 26
〈그림 2-8〉 유사도가 높은 유저들의 GPS 궤적 26
〈그림 2-9〉 궤적 패턴(x0,y0) →α1(x1,y1)에서 입력 시퀀스의 시공간 포함(이미지참조) 28
〈그림 3-1〉 제안 알고리즘 아키텍처 32
〈그림 3-2〉 제안 Stay Point 추출 알고리즘 33
〈그림 3-3〉 GPS 기록, GPS 궤적과 Stay Point 35
〈그림 3-4〉 Stay Point가 생성되는 조건 36
〈그림 3-5〉 서로 다른 임계값을 통해 SP를 추출한 결과 38
〈그림 3-6〉 평균 속력이 같은 부분 궤적 39
〈그림 3-7〉 평균 속력과 방위각 표준편차의 상관관계 41
〈그림 3-8〉 실내에서 머물렀을 때 생성되는 Stay Point 42
〈그림 3-9〉 실외 SP와 실내 SP의 생성 위치 43
〈그림 3-10〉 각 유저의 날짜별 속도 분포 45
〈그림 3-11〉 1차원 데이터에 대한 GMM 모델링 47
〈그림 3-12〉 각 유저의 날짜별 GMM을 이용한 속도 분포 49
〈그림 3-13〉 속도 임계값보다 낮은 구간 탐색 50
〈그림 3-14〉 각 유저의 날짜별 방위각 편차 분포 51
〈그림 3-15〉 시간의 순서에 따른 속도와 방위각 편차 52
〈그림 3-16〉 방위각 편차의 Outlier 검출 53
〈그림 3-17〉 속도와 방위각 편차를 이용한 outdoor SP 추출 55
〈그림 3-18〉 실내에서 머문 장소 예측 56
〈그림 3-19〉 10번 유저의 GPS 포인트간 시간과 거리의 차 57
〈그림 3-20〉 85번 유저의 GPS 포인트간 시간과 거리의 차 58
〈그림 3-21〉 10번 유저의 outlier detection을 통한 실내 SP 추출 59
〈그림 3-22〉 85번 유저의 outlier detection을 통한 실내 SP 추출 59
〈그림 3-23〉 correction SP 추출 과정 61
〈그림 3-24〉 outdoor SP와 correction SP의 위치 비교 61
〈그림 3-25〉 0번 유저의 GPS 궤적 62
〈그림 3-26〉 outdoor SP와 indoor SP 63
〈그림 3-27〉 제안 군집 최적화 알고리즘 65
〈그림 3-28〉 DBSCAN 알고리즘 66
〈그림 3-29〉 0~4번 유저의 GPS 궤적과 SP 및 군집화 결과 67
〈그림 3-30〉 군집화 결과 비교 68
〈그림 3-31〉 sorted k-dist graph 69
〈그림 3-32〉 군집 품질 비교 71
〈그림 3-33〉 제안 이동 패턴 추출 알고리즘 73
〈그림 3-34〉 어고딕 모델과 좌우 모델 75
〈그림 3-35〉 HMM으로 모델링된 유저들의 이동 확률 76
〈그림 3-36〉 HMM 기반 이동 패턴 추출 과정 77
〈그림 3-37〉 유저들이 하루 동안 RoI에서 머물렀던 횟수 81
〈그림 3-38〉 유저들이 머물렀던 시각 및 quantile을 통한 시간 분할 82
〈그림 3-39〉 트렐리스를 이용한 확률 계산 86
〈그림 3-40〉 전향 계산 86
〈그림 3-41〉 전향계산을 통한 이동 확률 88
〈그림 3-42〉 viterbi 알고리즘 89
〈그림 3-43〉 viterbi를 이용한 최적 상태열 90
〈그림 4-1〉 SP 추출 개수 비교 93
〈그림 4-2〉 임계값에 따른 SP 위치 변화 96
〈그림 4-3〉 기존 알고리즘으로는 추출되지 않는 장소 97
〈그림 4-4〉 기존 알고리즘으로만 추출되는 SP 98
〈그림 4-5〉 실내 SP 추출 98
〈그림 4-6〉 각 알고리즘을 통해 생성된 SP 100
〈그림 4-7〉 군집 결과 비교 101
〈그림 4-8〉 DBSCAN을 통한 RoI 추출 102
〈그림 4-9〉 각 군집화 알고리즘을 통해 생성된 RoI 103
〈그림 4-10〉 각 유저들의 머문 지점 비교 104
〈그림 4-11〉 0번 유저의 각 시간대별 이동 패턴 109
〈그림 4-12〉 제안 알고리즘을 통한 0~100번 유저들의 이동 패턴 추출 110
〈그림 4-13〉 0번, 4번 유저의 GPS 궤적, SP, RoI 112
〈그림 4-14〉 0번 유저가 자주 머물렀던 지역 116
〈그림 4-15〉 T-pattern miner와 제안 알고리즘의 이동 패턴 결과 비교 117