주변 차량 위치 좌표의 고속 클러스터링을 위한 휴리스틱 알고리즘

국문 초록 (Abstract)

분할 계층적 클러스터링(Divisive Hierarchical Clustering)은 하나의 클러스터에서 시작하여 각각의 데이터가 독립된 클러스터에 속할 때까지 각 클러스터를 분할하고 분할된 클러스터 간에 데이터를 이동하는 과정을 반복 수행한다. 하지만, 이러한 일련의 재귀적 호출 과정에서 입력 데이터가 임의적으로 선택되는 경우, 클러스터 내 데이터의 많은 이동을 야기할 수 있다. 이로 인해 주변 차량의 위치를 추정하여 수집된 위치 좌표 정보를 고속으로 클러스터링 할 필요가 있는 로컬 맵 생성 과정에서 사용하기 어렵다는 단점이 있다. 본 논문에서는 주변 차량 위치 추정 과정에서 차량의 주행 방향 정보를 활용하여 분할된 클러스터를 구성하는 데이터의 임의성을 제거함으로써, 클러스터링 연산 속도를 평균 40% 가량 향상시킬 수 있는 새로운 고속의 분할 계층적 클러스터링 방법을 제안한다.

다국어 초록 (Multilingual Abstract)

Divisive hierarchical clustering algorithms iterate the process of decomposition and clustering data recursively. In each recursive call, data in each cluster are arbitrarily selected and thus, the total clustering time can be increased, which causes a problem that it is difficult to apply the process of clustering neighbor vehicular position data in vehicular localization. In this paper, we propose a new heuristic algorithm for speeding up the clustering time by eliminating randomness of the selected data in the process of generating the initial divisive clusters.

목차 (Table of Contents)

• 요약
• ABSTRACT
• Ⅰ. 서론
• Ⅱ. 로컬 맵 생성 개요
• Ⅲ. 데이터 클러스터링을 위한 휴리스틱 알고리듬
• Ⅳ. 고속의 클러스터링을 위한 휴리스틱 알고리듬
• Ⅴ. 성능 분석
• Ⅵ. 결론
• References

참고문헌 (Reference)

1 Adhitya Bhawiyuga, "자동차 센서와 자동차 간 통신의 융합 측위 알고리듬" 한국통신학회 37 (37): 544-553, 2012

2 A. Boukerche, "Vehicular ad hoc networks : a new challenge for localization-based systems" 31 (31): 2838-2849, 2008

3 R. Rajamani, "Vehicle Dynamics and Control" Springer Press 2006

4 J. B MacQueen, "Some methods for classification and analysis of multivariate observations" University of California Press 281-297, 1967

5 D. Boley, "Principal direction divisive partitioning" 2 (2): 1998

6 M. Ankerst, "OPTICS : Ordering points to identify the clustering structure" 28 (28): 49-60, 1999

7 J. Du, "Next-generation automated vehicle location systems : positioning at the lane level" 9 (9): 48-57, 2008

8 G. Weber, "Networked transport of RTCM via internet protocol(Ntrip)–IP-streaming for real-time GNSS applications" 2243-2247, 2005

9 "IEEE standard for information technology-telecommunications and information exchange between systems-local and metropolitan area network-specific requirements, part11:wireless lan medium access control (MAC)and physical layer (PHY) specification, amendment 6: wireless access in vehicular environment"

10 S. Fujii, "Cooperative vehicle positioning via V2V communications and onboard sensors" 1-5, 2011

11 R. Parker, "Cooperative vehicle position estimation" 5837-5842, 2007

12 H. Li, "Cooperative multi-vehicle localization using split covariance intersection filter" 211-216, 2012

13 P. Drineas, "Clustering large graphs via the singular value decomposition" 56 (56): 9-33, 2004

14 M. Ester, "A Density-based algorithm for discovering clusters in large spatial databases with noise" 226-231, 1996