최근 궤적 정보를 이용한 많은 연구들이 진행되고 있으나, 이들 대부분의 연구는 유클리드 공간 내의 궤적들을 대상으로 하고 있다. 그러나 실제 응용에서 대부분의 이동 객체들은 도로 네트워크 공간상에 존재하므로, 유클리드 공간을 대상으로 한 연구들을 도로 네트워크 공간에 적용시키는 것은 적합하지 않다. 본 논문에서는 도로 네트워크 내 이동 객체들의 대용량 궤적 정보를 대상으로 하는 효과적인 클러스터링 기법에 대하여 논한다. 이를 위하여 우선 본 논문에서는 궤적을 각 이동 객체가 시간에 따라 지나온 도로 세그먼트들의 연속으로 정의한다. 다음, 도로 세그먼트들의 길이와 식별자 정보를 이용한 새로운 유사도 측정 함수를 제안하고, 이를 이용하여 측정된 궤적간의 유사도 정보를 기반으로 FastMap과 계층 클러스터링(hierarchical clustering)기법을 이용하여 전체 궤적들을 클러스터링하는 방식을 제안한다. 또한, 본 논문에서는 실제 응용에서 대부분의 이동 객체는 최단 거리를 이용하여 움직인다는 특성을 반영한 새로운 궤적 생성 기법을 제안하고, 이렇게 생성된 궤적 데이터를 이용하여 제안된 클러스터링 기법에 대한 다양한 성능 평가 결과를 보인다. 실험 결과에 따르면 제안된 기법은 사람에 의하여 유사 궤적들을 클러스터링한 결과와 비교하여 95%이상의 높은 정확도를 보였다.
최근 궤적 정보를 이용한 많은 연구들이 진행되고 있으나, 이들 대부분의 연구는 유클리드 공간 내의 궤적들을 대상으로 하고 있다. 그러나 실제 응용에서 대부분의 이동 객체들은 도로 네트워크 공간상에 존재하므로, 유클리드 공간을 대상으로 한 연구들을 도로 네트워크 공간에 적용시키는 것은 적합하지 않다. 본 논문에서는 도로 네트워크 내 이동 객체들의 대용량 궤적 정보를 대상으로 하는 효과적인 클러스터링 기법에 대하여 논한다. 이를 위하여 우선 본 논문에서는 궤적을 각 이동 객체가 시간에 따라 지나온 도로 세그먼트들의 연속으로 정의한다. 다음, 도로 세그먼트들의 길이와 식별자 정보를 이용한 새로운 유사도 측정 함수를 제안하고, 이를 이용하여 측정된 궤적간의 유사도 정보를 기반으로 FastMap과 계층 클러스터링(hierarchical clustering)기법을 이용하여 전체 궤적들을 클러스터링하는 방식을 제안한다. 또한, 본 논문에서는 실제 응용에서 대부분의 이동 객체는 최단 거리를 이용하여 움직인다는 특성을 반영한 새로운 궤적 생성 기법을 제안하고, 이렇게 생성된 궤적 데이터를 이용하여 제안된 클러스터링 기법에 대한 다양한 성능 평가 결과를 보인다. 실험 결과에 따르면 제안된 기법은 사람에 의하여 유사 궤적들을 클러스터링한 결과와 비교하여 95%이상의 높은 정확도를 보였다.
Recently, there have been many research efforts proposed on trajectory information. Most of them mainly focus their attention on those objects moving in Euclidean space. Many real-world applications such as telematics, however, deal with objects that move only over road networks, which are highly re...
Recently, there have been many research efforts proposed on trajectory information. Most of them mainly focus their attention on those objects moving in Euclidean space. Many real-world applications such as telematics, however, deal with objects that move only over road networks, which are highly restricted for movement. Thus, the existing methods targeting Euclidean space cannot be directly applied to the road network space. This paper proposes a new clustering scheme for a large volume of trajectory information of objects moving over road networks. To the end, we first define a trajectory on a road network as a sequence of road segments a moving object has passed by. Next, we propose a similarity measurement scheme that judges the degree of similarity by considering the total length of matched road segments. Based on such similarity measurement, we propose a new clustering algorithm for trajectories by modifying and adjusting the FastMap and hierarchical clustering schemes. To evaluate the performance of the proposed clustering scheme, we also develop a trajectory generator considering the observation that most objects tend to move from the starting point to the destination point along their shortest path, and perform a variety of experiments using the trajectories thus generated. The performance result shows that our scheme has the accuracy of over 95% in comparison with that judged by human beings.
Recently, there have been many research efforts proposed on trajectory information. Most of them mainly focus their attention on those objects moving in Euclidean space. Many real-world applications such as telematics, however, deal with objects that move only over road networks, which are highly restricted for movement. Thus, the existing methods targeting Euclidean space cannot be directly applied to the road network space. This paper proposes a new clustering scheme for a large volume of trajectory information of objects moving over road networks. To the end, we first define a trajectory on a road network as a sequence of road segments a moving object has passed by. Next, we propose a similarity measurement scheme that judges the degree of similarity by considering the total length of matched road segments. Based on such similarity measurement, we propose a new clustering algorithm for trajectories by modifying and adjusting the FastMap and hierarchical clustering schemes. To evaluate the performance of the proposed clustering scheme, we also develop a trajectory generator considering the observation that most objects tend to move from the starting point to the destination point along their shortest path, and perform a variety of experiments using the trajectories thus generated. The performance result shows that our scheme has the accuracy of over 95% in comparison with that judged by human beings.
* AI 자동 식별 결과로 적합하지 않은 문장이 있을 수 있으니, 이용에 유의하시기 바랍니다.
문제 정의
2절에서 제안한 유사도 측정 함수를 이용하여 주어진 질의 궤적과 유사한 궤적을 가지는 이동 객체를 검색할 수 있다. 그러나 본 연구의 주목적은 검색된 유사 궤적을 클러스터링하여 보다 유용한 정보를 사용자에게 제공하는 것이다.
따라서, 본 연구에서는 도로 네트워크 공간을 대상으로 하는 새로운 궤적 데이터 생성 기법을 제안한다. 제안된 기법에서는 실제 이동 객체의 움직임과 비슷한 궤적을 생성하기 위하여 이동 객체는 출발지에서 목적지까지 최단 경로에 근접하게 움직인다는 현실 세계의 특징을 반영한다.
본 논문에서는 데이터베이스에 저장된 이들 대용량 궤적정보를 대상으로 하는 효과적인 클러스터링 기법에 대하여 논한다. 이를 위하여 먼저 궤적들 간의 유사도를 측정하기 위한 유사도 측정 함수를 제안한다.
본 논문에서는 도로 네트워크 공간내 이동 객체들에 대한 대용량 궤적 정보를 대상으로 하는 효과적인 클러스터링 기법에 대하여 논한다. 이를 위하여 먼저, 이동 객체의 궤적이 2차원 공간 좌표 (x,y)의 연속으로 표현되는 유클리드 공간과는 달리, 본 논문에서는 궤적을 하나의 이동 객체가 지나온 도로 세그먼트들의 연속으로 표현한다.
본 논문에서는 도로 네트워크 공간상에서의 이동 객체들을 대상으로 하는 효과적인 유사 궤적 검색을 위한 유사도 측정 함수 및 클러스터링 기법에 대하여 논하였다. 이를 위하여 먼저 궤적을 각 이동 객체가 시간에 따라 지나간 도로 세그먼트들의 리스트로 정의하고, 궤적을 이루는 도로 세그먼트들의 길이와 식별자 정보를 이용한 새로운 유사도 측정 함수를 제안하였다.
따라서 두 궤적의 유사도를 세그먼트의 개수만을 이용하여 판단하는 방식은 적절하지 않다. 본 논문에서는 이러한 문제점을 해결하기 위하여 세그먼트의 길이를 이용한 유사도 측정 함수 DSL(dissimilarity with length)를 제안한다.
가설 설정
또한, 제안된 방식은 세그먼트를 나누는 기준에 따른 세그먼트 개수의 변화에 영향을 받지 않는다. 예를 들어, 궤적 T1, T2의 유사도 측정 시 s6의 세그먼트를 3개로 분할할 경우에도 분할된 세 개의 세그먼트의 길이를 합한 전체의 길이는 4로 분할 전과 길이면에서는 변함이 없다.
제안 방법
FastMap을 이용하여 각 궤적을 k차원의 한 점으로 변환한 후, 변환된 k차원 점들을 대상으로 클러스터링을 수행한다.
}가 주어지면 Q를 구성하는 각 세그먼트에 대하여 클러스터의 세그먼트 요약 정보를 검색한다. 각 세그먼트와 비교된 각 클러스터의 세그먼트 요약 정보내의 해당 세그먼트의 가중치 값들의 합을 구하고, 그 중 가장 높은 가중치 값을 갖는 클러스터를 검색한다. 예에서 Q내의 세그먼트 s1, s2, s10, s9, s8은 클러스터 C1에 존재하므로, 이때의 s1, s2, s10, s9, s8의 가중치를 모두 합하면 1+0.
이를 위하여 먼저, 이동 객체의 궤적이 2차원 공간 좌표 (x,y)의 연속으로 표현되는 유클리드 공간과는 달리, 본 논문에서는 궤적을 하나의 이동 객체가 지나온 도로 세그먼트들의 연속으로 표현한다. 다음, 도로 세그먼트의 식별자 및 길이 정보를 이용한 유사도 측정 방식을 제안한다. 유클리드 거리를 두 궤적간의 유사도의 척도로 이용하는 기존의 방식을 도로 네트워크 공간상에 적용하는 것은 적합하지 않다.
구성된 클러스터와 연관된 사용자 정보, 도로 정보 등을 함께 사용자에게 제공하는 프로토타입 시스템을 제시함으로써 제안된 기법이 실제 응용에 유용하게 사용될 수 있음을 보인다. 또한, 본 논문에서 제안된 유사도 함수를 이용한 클러스터링 수행의 정확도 측정을 위한 실험을 수행하고, 제안하는 기법의 우수성을 검증한다.
다음, 이를 이용하여 측정된 모든 궤적 쌍 간의 유사도와 FastMap 방식[10]을 이용하여 궤적들을 k차원의 점들로 매핑한 후, 이들에 대하여 클러스터링을 수행한다. 마지막으로, 주어진 질의 궤적에 대하여 해당 클러스터를 신속하게 검색하기 위한 질의 처리 기법을 제안한다.
실험 1과 실험 2에서는 클러스터링을 수행하기 전에 FastMap을 위한 최적의 차원수를 결정하는 실험을 수행한다. 먼저 실험 1에서는 제안된 유사도 함수 DSL을 이용하여 측정된 실제 궤적간의 거리 차이와 FastMap을 이용하여 궤적을 k차원 공간상의 점으로 변환했을 때 궤적들 간의 거리 차이를 이용한 오차율을 다음과 같이 정의하여 사용한다.
본 연구에서는 클러스터링 과정을 통하여 얻어진 클러스터에 대한 정보를 각 클러스터 C에 대하여 세그먼트 요약정보 S={, ..., }와 사용자 요약 정보 U={u1, ..., um}을 구성하여 함께 저장 관리한다.
본 장에서는 실험에 의한 평가를 통하여 제안된 클러스터링 기법에 의하여 구성된 클러스터의 정확도를 정량적으로 검증한다. 제 4.
실험 1과 실험 2에서는 클러스터링을 수행하기 전에 FastMap을 위한 최적의 차원수를 결정하는 실험을 수행한다. 먼저 실험 1에서는 제안된 유사도 함수 DSL을 이용하여 측정된 실제 궤적간의 거리 차이와 FastMap을 이용하여 궤적을 k차원 공간상의 점으로 변환했을 때 궤적들 간의 거리 차이를 이용한 오차율을 다음과 같이 정의하여 사용한다.
실험 1과 실험 2의 결과에 따라 본 실험에서는 FastMap의 변환 차원을 50차원으로 고정하고 이후 클러스터링 실험을 수행한다.
실험 2에서는 실제 궤적들 간의 유사도 순위가 FastMap으로 변환 후에 변화가 있는지를 실험한다. 이를 위하여 참고 문헌 [8, 13]에서 정의된 KSim을 사용한다.
이러한 문제점을 해결하기 위하여 본 연구에서는 FastMap[10]을 이용하여 각 궤적을 k차원 공간 상의 한 점으로 표현한 후, 전체 궤적들과 대응되는 점들을 대상으로 클러스터링을 수행한다. 이때, 서로 다른 길이를 갖는 궤적들을 하나의 차원으로 매핑시키기 위하여 본 연구에서는 제 3.2절에서 제안된 DSL 방식에 의해 측정된 두 궤적간의 유사도 값을 이용한다. 여기서, 측정된 DSL 값은 두 궤적간의 거리를 의미한다.
따라서 궤적간의 상대적인 거리로 클러스터를 구성한다면 중심점이라는 기준이 모호해 진다. 이러한 문제점을 해결하기 위하여 본 연구에서는 FastMap[10]을 이용하여 각 궤적을 k차원 공간 상의 한 점으로 표현한 후, 전체 궤적들과 대응되는 점들을 대상으로 클러스터링을 수행한다. 이때, 서로 다른 길이를 갖는 궤적들을 하나의 차원으로 매핑시키기 위하여 본 연구에서는 제 3.
본 논문에서는 데이터베이스에 저장된 이들 대용량 궤적정보를 대상으로 하는 효과적인 클러스터링 기법에 대하여 논한다. 이를 위하여 먼저 궤적들 간의 유사도를 측정하기 위한 유사도 측정 함수를 제안한다. 다음, 이를 이용하여 측정된 모든 궤적 쌍 간의 유사도와 FastMap 방식[10]을 이용하여 궤적들을 k차원의 점들로 매핑한 후, 이들에 대하여 클러스터링을 수행한다.
본 논문에서는 도로 네트워크 공간상에서의 이동 객체들을 대상으로 하는 효과적인 유사 궤적 검색을 위한 유사도 측정 함수 및 클러스터링 기법에 대하여 논하였다. 이를 위하여 먼저 궤적을 각 이동 객체가 시간에 따라 지나간 도로 세그먼트들의 리스트로 정의하고, 궤적을 이루는 도로 세그먼트들의 길이와 식별자 정보를 이용한 새로운 유사도 측정 함수를 제안하였다. 클러스터링을 위하여는 측정된 궤적 쌍간의 유사도를 기반으로 궤적을 FastMap을 이용하여 k차원 공간상의 점들로 사상한 후, 이들을 클러스터링하는 기법을 제안하였다.
본 논문에서는 도로 네트워크 공간내 이동 객체들에 대한 대용량 궤적 정보를 대상으로 하는 효과적인 클러스터링 기법에 대하여 논한다. 이를 위하여 먼저, 이동 객체의 궤적이 2차원 공간 좌표 (x,y)의 연속으로 표현되는 유클리드 공간과는 달리, 본 논문에서는 궤적을 하나의 이동 객체가 지나온 도로 세그먼트들의 연속으로 표현한다. 다음, 도로 세그먼트의 식별자 및 길이 정보를 이용한 유사도 측정 방식을 제안한다.
제안된 기법에서는 실제 이동 객체의 움직임과 비슷한 궤적을 생성하기 위하여 이동 객체는 출발지에서 목적지까지 최단 경로에 근접하게 움직인다는 현실 세계의 특징을 반영한다. 이를 위하여, 먼저 출발지 노드와 목적지 노드가 주어지면 이들 간의 최단 경로를 검색하고, 검색된 최단 경로를 구성하는 각 노드들과 연결되어 있는 근접 세그먼트들을 이용하여 목적지 노드까지 도달할 수 있는 근접 최단 경로를 검색하여 이를 궤적 데이터로 생성한다. 이때, 실제 최단 경로와 검색된 근접 최단 경로간의 거리 차가 얼마나 발생하는 지를 확률 값으로 계산하여 궤적 생성 과정에서의 이동 노드를 선택하기 위한 값으로 사용한다.
1절에서는 도로 네트워크를 대상으로 하는 이동 객체의 궤적을 정의하고, 제안하는 기법의 기본 개념을 설명한다. 제 3.2절에서는 두 궤적간의 유사도 측정을 위하여 도로 세그먼트들의 길이와 식별자 정보를 이용한 새로운 유사도 측정 방식을 제안한다. 제 3.
2절에서는 두 궤적간의 유사도 측정을 위하여 도로 세그먼트들의 길이와 식별자 정보를 이용한 새로운 유사도 측정 방식을 제안한다. 제 3.3절에서는 측정된 궤적간의 유사도 정보를 기반으로 FastMap을 이용한 클러스터링 방식을 제안한다. 마지막으로 제 3.
따라서, 본 연구에서는 도로 네트워크 공간을 대상으로 하는 새로운 궤적 데이터 생성 기법을 제안한다. 제안된 기법에서는 실제 이동 객체의 움직임과 비슷한 궤적을 생성하기 위하여 이동 객체는 출발지에서 목적지까지 최단 경로에 근접하게 움직인다는 현실 세계의 특징을 반영한다. 이를 위하여, 먼저 출발지 노드와 목적지 노드가 주어지면 이들 간의 최단 경로를 검색하고, 검색된 최단 경로를 구성하는 각 노드들과 연결되어 있는 근접 세그먼트들을 이용하여 목적지 노드까지 도달할 수 있는 근접 최단 경로를 검색하여 이를 궤적 데이터로 생성한다.
3절에서 구성된 클러스터의 세그먼트 요약 정보와 사용자 요약 정보를 이용한 질의 처리 기법을 제안하여 제안된 기법이 실제 응용에 유용하게 사용될 수 있음을 보인다. 제안된 기법에서는 주어진 질의 궤적 내에 포함된 각 세그먼트를 각 클러스터의 세그먼트 요약 정보내의 해당 세그먼트의 가중치 값과 비교한다.
제안된 기법의 성능 평가를 위하여 본 논문에서는 도로 네트워크 공간상에서 이동 객체는 출발지에서 목적지까지의 최단 경로에 근접하여 움직인다는 현실 세계의 특징을 반영한 궤적 생성기를 제안하였다. 이를 이용하여 생성된 궤적 데이터들을 대상으로 클러스터링을 수행한 실험 결과에 따르면 제안된 기법은 사람에 의하여 유사 궤적들을 클러스터링한 결과와 비교하여 95%이상의 높은 정확도를 보였다.
제안하는 기법에서 궤적은 문자열로 표현되는 세그먼트 식별자들의 리스트로 구성된다. 주어진 두 궤적간의 유사도 측정을 위하여 문자열간의 거리 함수로 많이 사용되는 ED(edit distance) 방식을 이용할 수 있다.
이를 위하여 먼저 궤적을 각 이동 객체가 시간에 따라 지나간 도로 세그먼트들의 리스트로 정의하고, 궤적을 이루는 도로 세그먼트들의 길이와 식별자 정보를 이용한 새로운 유사도 측정 함수를 제안하였다. 클러스터링을 위하여는 측정된 궤적 쌍간의 유사도를 기반으로 궤적을 FastMap을 이용하여 k차원 공간상의 점들로 사상한 후, 이들을 클러스터링하는 기법을 제안하였다. 또한, 구성된 클러스터와 연관된 사용자 정보, 도로 정보 등을 함께 사용자에게 제공하는 질의 처리 기법을 제시하여 제안된 기법이 실제 응용에 유용하게 사용될 수 있음을 보였다.
대상 데이터
궤적 데이터 생성을 위하여 출발지 노드와 목적지 노드는 임의 선택하여 총 100개를 사용하였으며, 생성된 궤적 데이터들의 평균 세그먼트의 개수는 25개이며, 평균 궤적의 길이는 300이다.
본 연구에서는 실험을 위하여 개발된 도로 네트워크 기반의 궤적 데이터 생성기를 이용하여 100개와 10,000개의 궤적 데이터를 생성하여 사용하였다. 도로 네트워크 데이터로는[9]에서 7,035개의 세그먼트로 구성된 올덴버그(Oldenburg) 도로 네트워크를 다운로드 받아 사용하였다. 궤적 데이터 생성을 위하여 출발지 노드와 목적지 노드는 임의 선택하여 총 100개를 사용하였으며, 생성된 궤적 데이터들의 평균 세그먼트의 개수는 25개이며, 평균 궤적의 길이는 300이다.
따라서, 제안된 확률식은 앞에서 언급한 확률 값 부여 시 고려해야 할 세 가지 조건을 모두 만족시킨다. 본 실험에서는 제안된 궤적 생성기를 이용하여 100개와 10,000개의 궤적을 생성하여 사용한다.
본 연구에서는 실험을 위하여 개발된 도로 네트워크 기반의 궤적 데이터 생성기를 이용하여 100개와 10,000개의 궤적 데이터를 생성하여 사용하였다. 도로 네트워크 데이터로는[9]에서 7,035개의 세그먼트로 구성된 올덴버그(Oldenburg) 도로 네트워크를 다운로드 받아 사용하였다.
(그림 3)은 FastMap의 차원수 변화에 따른 오차율을 측정한 결과를 보인다. 실험 데이터로는 100개와 10,000개의 궤적 데이터를 사용하였으며, X축은 FastMap의 변환 차원수, Y축은 오차율을 나타낸다. 실험 결과에 따르면, 차원이 커질수록 오차율이 작아지는 것을 볼 수 있다.
실험을 위한 플랫폼으로는 MS Windows XP Professional을 운영 체제로 사용하고, 1GB의 주기억 장치, 120GB 디스크를 갖는 Pentium IV 3GHz의 PC를 사용한다.
실험 3에서는 정답 집합과 제안하는 기법을 이용하여 얻어진 클러스터링 결과 집합을 비교 분석한다. 정답 집합은 일반인 5명을 대상으로 본 실험에서 사용하고 있는 10,000개의 궤적 데이터를 5개부터 50개까지의 클러스터로 구성하게 하여 얻어진 집합이다. 제안된 기법의 클러스터링 결과에 대한 정확도 측정을 위한 기본 척도로 참고 문헌 [11]에서 제안된 정답 집합과 구성된 클러스터들간의 중심 값들을 비교하는 clusterdistance를 사용한다.
데이터처리
실험 3에서는 정답 집합과 제안하는 기법을 이용하여 얻어진 클러스터링 결과 집합을 비교 분석한다. 정답 집합은 일반인 5명을 대상으로 본 실험에서 사용하고 있는 10,000개의 궤적 데이터를 5개부터 50개까지의 클러스터로 구성하게 하여 얻어진 집합이다.
계층 클러스터링 방식은 가장 유사한 객체들을 동일 클러스터로 그룹화하는 방식으로 단계적인 병합 과정을 수행하여 모든 객체들이 하나의 클러스터에 속할 때까지 클러스터링 과정을 반복하는 방식이다. 제안된 기법의 성능 평가를 위하여 유사도 함수의 오차율과 클러스터링의 정확도를 비교 분석한다. 정확도 분석을 위한 비교 대상으로는 사람에 의하여 구성된 클러스터 집합을 사용한다.
이론/모형
FastMap[10]을 통하여 k차원 상의 점들로 변환된 궤적들을 대상으로 계층 클러스터링(hierarchical clustering) 방식[12]을 이용하여 클러스터링 수행한다. 계층 클러스터링 방식은 가장 유사한 객체들을 동일 클러스터로 그룹화하는 방식으로 단계적인 병합 과정을 수행하여 모든 객체들이 하나의 클러스터에 속할 때까지 클러스터링 과정을 반복하는 방식이다.
이를 위하여 먼저 궤적들 간의 유사도를 측정하기 위한 유사도 측정 함수를 제안한다. 다음, 이를 이용하여 측정된 모든 궤적 쌍 간의 유사도와 FastMap 방식[10]을 이용하여 궤적들을 k차원의 점들로 매핑한 후, 이들에 대하여 클러스터링을 수행한다. 마지막으로, 주어진 질의 궤적에 대하여 해당 클러스터를 신속하게 검색하기 위한 질의 처리 기법을 제안한다.
따라서 ED 방식에 의하여 유사 궤적을 검색하는 것은 적합하지 않다. 본 논문에서는 궤적 Ti와 Tj간의 유사도를 식(1)의 측정 함수 DSN(disimilarity with number)을 이용하여 계산한다.
이때, 실제 최단 경로와 검색된 근접 최단 경로간의 거리 차가 얼마나 발생하는 지를 확률 값으로 계산하여 궤적 생성 과정에서의 이동 노드를 선택하기 위한 값으로 사용한다. 본 연구에서는 최단 경로 검색을 위하여는 다익스트라 알고리즘(Dijkstra algorithm)을 사용한다[7]. <표 1>에 제안된 궤적 생성 알고리즘을 보인다.
실험 2에서는 실제 궤적들 간의 유사도 순위가 FastMap으로 변환 후에 변화가 있는지를 실험한다. 이를 위하여 참고 문헌 [8, 13]에서 정의된 KSim을 사용한다.
정답 집합은 일반인 5명을 대상으로 본 실험에서 사용하고 있는 10,000개의 궤적 데이터를 5개부터 50개까지의 클러스터로 구성하게 하여 얻어진 집합이다. 제안된 기법의 클러스터링 결과에 대한 정확도 측정을 위한 기본 척도로 참고 문헌 [11]에서 제안된 정답 집합과 구성된 클러스터들간의 중심 값들을 비교하는 clusterdistance를 사용한다.
제안된 유사도 함수에 의하여 측정된 궤적간의 유사도 정보를 기반으로 기존의 FastMap[10]과 계층 클러스터링 기법[12]을 이용하여 궤적들을 클러스터링 한다. 구성된 클러스터와 연관된 사용자 정보, 도로 정보 등을 함께 사용자에게 제공하는 프로토타입 시스템을 제시함으로써 제안된 기법이 실제 응용에 유용하게 사용될 수 있음을 보인다.
성능/효과
1) 세그먼트 식별자의 매치 여부와 개수만을 가지고 유사도를 측정하므로 매치되는 세그먼트의 길이 정보를 무시하게 된다. 예를 들어, DSN 방식에 의하여 궤적 T1과 T2의 유사도와 궤적 T1과 T4의 유사도가 같은 값을 갖는다.
실험 결과에 따르면, 차원이 커질수록 오차율이 작아지는 것을 볼 수 있다. 100개의 궤적 데이터인 경우에는 10차원 이상에서 0.1 이하의 오차율을 보이며, 10,000개의 궤적 데이터의 경우에는 50차원 이상에서 0.1 이하의 오차율을 보였다.
2) 동일한 도로라 하더라도 세그먼트를 나누는 기준에 따라 궤적에 포함된 세그먼트의 개수가 달라지므로 유사도가 달라질 수 있다. 제안된 DSN 방식은 세그먼트의 개수에 영향을 받기 때문에 하나의 세그먼트가 다수의 세그먼트로 분할되어 표현될 경우, 유사도 값이 전혀 다른 값을 갖게 된다.
실험 결과에 따르면 클러스터의 개수가 작을수록 높은 정확도를 보였으며, 클러스터의 개수가 많아지면 정확도가 다소 낮아짐을 알 수 있다. 그러나 제안하는 기법은 95%이상의 높은 정확도를 나타냄으로써, 비교적 정확한 클러스터링의 결과를 얻을 수 있음을 알 수 있다.
이는 확률의 기본 개념인 모든 확률 값의 합은 1이 되어야 한다는 조건을 만족시키기 위함이다. 둘째, 최단 경로와 유사한 경로의 세그먼트일수록 높은 확률 값을 가져야 한다. 또한 최단 경로에 포함되는 세그먼트의 확률 값은 다른 세그먼트들에 비해 상대적으로 높은 값을 가져야 한다.
16과 2차 변환하여 얻어진 점 T21= 0으로 구성된 것이다. 또한 클러스터링 결과를 보면, 유사도가 가장 높은 T1과 T3가 같은 클러스터로 그룹화되어 있는 것을 확인할 수 있다.
클러스터링을 위하여는 측정된 궤적 쌍간의 유사도를 기반으로 궤적을 FastMap을 이용하여 k차원 공간상의 점들로 사상한 후, 이들을 클러스터링하는 기법을 제안하였다. 또한, 구성된 클러스터와 연관된 사용자 정보, 도로 정보 등을 함께 사용자에게 제공하는 질의 처리 기법을 제시하여 제안된 기법이 실제 응용에 유용하게 사용될 수 있음을 보였다.
이는 최단 경로와 근접한 경로로 움직이려는 이동 객체의 특성을 반영하기 위함이다. 마지막으로, 목적지 노드에 가까워질수록 최단 경로를 선택할 확률이 높아야 한다. 목적지 노드에 가까워질수록 이동 가능한 경로의 수는 적어지고, 제한적이게 되므로 최단 경로를 구성하는 경로와 동일하게 움직여야 하기 때문이다.
본 절에서는 제 3.3절에서 구성된 클러스터의 세그먼트 요약 정보와 사용자 요약 정보를 이용한 질의 처리 기법을 제안하여 제안된 기법이 실제 응용에 유용하게 사용될 수 있음을 보인다. 제안된 기법에서는 주어진 질의 궤적 내에 포함된 각 세그먼트를 각 클러스터의 세그먼트 요약 정보내의 해당 세그먼트의 가중치 값과 비교한다.
이때 정확도는 구성된 클러스터내의 궤적들을 대상으로 동일 클러스터로 구성된 궤적의 비율을 나타낸다. 실험 결과에 따르면 클러스터의 개수가 작을수록 높은 정확도를 보였으며, 클러스터의 개수가 많아지면 정확도가 다소 낮아짐을 알 수 있다. 그러나 제안하는 기법은 95%이상의 높은 정확도를 나타냄으로써, 비교적 정확한 클러스터링의 결과를 얻을 수 있음을 알 수 있다.
X축은 FastMap의 차원수를 나타내며, Y축은 유사도 순위가 변하는 궤적의 비율을 나타낸다. 실험 결과에 따르면, 변환 차원이 증가됨에 따라 유사도 순위가 변하는 궤적의 수가 확연히 감소하는 것을 알 수 있다.
제안된 기법의 성능 평가를 위하여 본 논문에서는 도로 네트워크 공간상에서 이동 객체는 출발지에서 목적지까지의 최단 경로에 근접하여 움직인다는 현실 세계의 특징을 반영한 궤적 생성기를 제안하였다. 이를 이용하여 생성된 궤적 데이터들을 대상으로 클러스터링을 수행한 실험 결과에 따르면 제안된 기법은 사람에 의하여 유사 궤적들을 클러스터링한 결과와 비교하여 95%이상의 높은 정확도를 보였다.
즉, DSL 방식에 의하여 궤적 T2가 궤적 T4보다 궤적 T1과 더 유사함을 파악할 수 있다. 제안된 DSL 방식은 두 궤적 간에 공통 세그먼트의 개수가 많고, 세그먼트의 길이의 차가 적은 궤적들을 보다 유사하다고 판단한다.
후속연구
제안된 유사도 함수에 의하여 측정된 궤적간의 유사도 정보를 기반으로 기존의 FastMap[10]과 계층 클러스터링 기법[12]을 이용하여 궤적들을 클러스터링 한다. 구성된 클러스터와 연관된 사용자 정보, 도로 정보 등을 함께 사용자에게 제공하는 프로토타입 시스템을 제시함으로써 제안된 기법이 실제 응용에 유용하게 사용될 수 있음을 보인다. 또한, 본 논문에서 제안된 유사도 함수를 이용한 클러스터링 수행의 정확도 측정을 위한 실험을 수행하고, 제안하는 기법의 우수성을 검증한다.
질의응답
핵심어
질문
논문에서 추출한 답변
EU 방식은 무엇인가?
EU 방식은 길이 k의 두 궤적이 주어졌을 때, 궤적을 구성하는 두 k차원 시공간 좌표들 간의 유클리드 거리를 구하는 방식이다. 이 방식은 유사도를 측정하기가 쉽고 계산이 빠르다는 장점이 있는 반면, 비교하는 두 궤적의 길이가 동일해야 한다는 제약이 있다.
유클리드 공간상에서 이동 객체 궤적들 간의 유사도 측정을 위하여 어떤 거리함수를 이용한 기법들에 제안되었나?
유클리드 공간상에서 이동 객체 궤적들 간의 유사도 측정을 위하여 EU(Euclidean distance), DTW(dynamic time warping distance), ERP(edit distance with real penalty), LCSS(longest common sub-sequences), EDR(edit distance in real sequence) 등의 거리 함수를 이용한 기법들이 제안된 바 있다[4-6, 24].
EU 방식의 장단점은?
EU 방식은 길이 k의 두 궤적이 주어졌을 때, 궤적을 구성하는 두 k차원 시공간 좌표들 간의 유클리드 거리를 구하는 방식이다. 이 방식은 유사도를 측정하기가 쉽고 계산이 빠르다는 장점이 있는 반면, 비교하는 두 궤적의 길이가 동일해야 한다는 제약이 있다. 실제 응용에서는 궤적들의 길이가 동일하지 않기 때문에 이 방법은 사용 범위가 제한적이다.
참고문헌 (26)
V. Almeida and R. Guting, 'Indexing the Trajectories of Moving Objects in Networks,' Geoinformatica, Vol.9, No.1, pp.33-60, 2005
S. Brakatsoulas, D. Pfoser, and N. Tryfona, 'Modeling, Storing, and Mining Moving Object Databases,' In Proc. Int'l. Symp. on Database Engineering and Applications, pp.68-77, 2004
T. Brinkhoff, 'A Framework for Generating Network-Based Moving Objects,' GeoInformatica, Vol.6, No.2, pp.153-180, 2002
L. Chen and R. Ng, 'On the Marriage of Lp-norms and Edit Distance,' In Proc. Int'l. Conf. on Very Large Data Bases, VLDB, pp.1040-1049, 2004
L. Chen, M. Ozsu, and V. Oria, 'Robust and Fast Similarity Search for Moving Object Trajectories,' In Proc. Int'l. Conf. on Management of Data, ACM SIGMOD, pp.491-502, 2005
S. Chu et al., 'Iterative Deepening Dynamic Time Warping for Time Series,' In Proc. SIAM Int'l. Conf. on Data Mining, 2002
E. Dijkstra, 'A Note on Two Problems in Connection with Graphs,' Numeriche Mathematik, Vol.1, pp.269-271, 1959
R. Fagin, R. Kumar, and D. Sivakumar, 'Comparing top k lists,' In Proc. Int'l. Symp. on Discrete algorithms, ACM SIAM, pp.28-36, 2003
FH Oldenburg/Ostfriesland/Wilhelmshaven, Network-based Generator of Moving Objects, http://www.fh-oow.de/institute/iapg/personen/brinkhoff/generator/, 2005
C. Faloutsos and K. Lin, 'Fastmap: A Fast Algorithm for Indexing, Data-Mining, and Visualization of Traditional and Multimedia Datasets,' In Proc. Int'l. Conf. on Management of Data, ACM SIGMOD, pp.163-174, 1995
D. Goldin, R. Mardales, and G. Nagy, 'In Search of Meaning for Time Series Subsequence Clustering: Matching Algorithms Based on a New Distance Measure,' In Proc. Int'l. Conf. on Information and Knowledge Management, pp.347-356, 2006
J. Han and M. Kamber, Data Mining: Concepts and Techniques, Academic Press, 2001
T. Haveliwala, 'Topic-Sensitive PageRank,' In Proc. Int'l. Conf. on World Wide Web, WWW, pp.517-526, 2002
X. Huang et al., 'The Islands Approach to Nearest Neighbor Querying in Spatial Networks,' In Proc. Int'l. Symp. on Spatial and Temporal Databases, SSTD, pp.73-90, 2005
K.-S. Kim et al., 'Fast Indexing and Updating Method for Moving Objects on Road Networks,' In Proc. IEEE Int'l. Conf. on Web Information Systems Engineering, pp.34-42, 2003
M. Kolahdouzan and C. Shahabi, 'Voronoi-Based K-Nearest Neighbor Search for Spatial Network Databases,' In Proc. Int'l. Conf. on Very Large Data Bases, VLDB, pp.840-851, 2004
J. Lee, J. Han, and K. Whang, 'Trajectory Clustering: A Partition-and-Group Framework,' In Proc. Int'l. Conf. on Management of Data archive, ACM SIGMOD, pp.593-604, 2007
D. Papadias et al., 'Query Processing in Spatial Network Databases,' In Proc. Int'l. Conf. on Very Large Data Bases, VLDB, pp.802-813, 2003
D. Pfoser, C. Jensen, and Y. Theodoridis, 'Novel Approaches to the Indexing of Moving Object Trajectories,' In Proc. Int'l. Conf. on Very Large Databases, pp.395-406, 2000
D. Pfoser and C. Jensen, 'Indexing of Network Constrained Moving Objects,' In Proc. Int'l. Symp. on Advances in Geographic Information Systems, ACMGIS, pp.25-32, 2003
Y. Theodoridis and M. Nascimento, 'Generating Spatiotemporal Datasets on the WWW,' ACM SIGMOD Record, Vol.29, No.3, pp.39-43, 2000
Y. Theodoridis, J. Silva, and M. Nascimento, 'On the Generation of Spatiotemporal Datasets,' LNCS, pp.147-164, 1999
T. Tzouramanis, M. Vassilakopoulos, and Y. Manolopoulos, 'On the Generation of Time -Evolving Regional Data,' GeoInformatica, Vol.3, No.3, pp.207-231, 2002
M. Vlachos, G. Kollios, and D. Gunopulos, 'Discovering Similar Multidimensional Trajectories,' In Proc. Int'l. Conf. on Data Engineering, IEEE ICDE, pp.673-684, 2002
O. Wolfson et al., 'Moving Object Databases: Issues and Solutions,' In Proc. Int'l. Conf. on Scientific and Statistical Database Management, SSDBM, pp.111-122, 1998
Y. Yanagisawa, J. Akahani, and T. Satoh, 'Shape-Based Similarity Query for Trajectory of Mobile Objects,' In Proc. Int'l. Conf. on Mobile Data Management, pp.63-77, 2003
※ AI-Helper는 부적절한 답변을 할 수 있습니다.