선택한 단어 수는 입니다.
최소 단어 이상 선택하여야 합니다.
최소 단어 이상 선택하여야 합니다.
선택한 단어 수는 30입니다.
최대 10 단어까지만 선택 가능합니다.
최대 10 단어까지만 선택 가능합니다.
문제 정의
- 이 논문에서는 데이터 시퀀스 필터링에 적용할 수 있는 새로운 거리 측정 방식을 제안한다. 제안하는 색인기법은 기존의 시퀀스 클러스터링 기법 등을 통해 유사한 시퀀스들을 하나의 그룹으로 묶고, 그룹을 대표하는 최소 하한 시퀀스 (MBS, Minimum Bounding Sequence)를 생성한다.
- 이 논문에서는 필터링 효과를 높여 불필요한 DTW 연산을 줄이기 위한 시퀀스 색인 기법을 제안하였다. 유사한 데이터 시퀀스가 클러스터링이 되었을 때 생성되는 시퀀스 그룹을 대표하는 MBS를 정의하였다.
제안 방법
- 이러한 문제를 해결하기 위해서 다양한 색인 기법들에 대한 연구가 진행되어왔다[1-7]. 이 방법들을 요약하면, 착오 기각 (flase negative)을 발생 시키지 않으면서 시퀀스 데이터베이스를 필터링 할 수 있는 방법을 이용하여 후보 집합을 찾아낸 후에 DTW를 이용해 최종 결과를 찾아낸다.
- 이 논문에서는 데이터 시퀀스 필터링에 적용할 수 있는 새로운 거리 측정 방식을 제안한다. 제안하는 색인기법은 기존의 시퀀스 클러스터링 기법 등을 통해 유사한 시퀀스들을 하나의 그룹으로 묶고, 그룹을 대표하는 최소 하한 시퀀스 (MBS, Minimum Bounding Sequence)를 생성한다. 그리고, 질의 시퀀스와 각 그룹을 대표하는 MBS들과의 최소 DTW 거리를 측정하여 질의와 유사한 시퀀스를 포함할 가능성이 있는 그룹을 찾아내고 그룹 내의 시퀀스와의 DTW 거리 측정을 통해서 가장 유사한 시퀀스를 찾아낸다.
- 제안하는 색인기법은 기존의 시퀀스 클러스터링 기법 등을 통해 유사한 시퀀스들을 하나의 그룹으로 묶고, 그룹을 대표하는 최소 하한 시퀀스 (MBS, Minimum Bounding Sequence)를 생성한다. 그리고, 질의 시퀀스와 각 그룹을 대표하는 MBS들과의 최소 DTW 거리를 측정하여 질의와 유사한 시퀀스를 포함할 가능성이 있는 그룹을 찾아내고 그룹 내의 시퀀스와의 DTW 거리 측정을 통해서 가장 유사한 시퀀스를 찾아낸다.
- 이 논문에서 제안하는 것은 유사한 그룹을 대표하는 MBS (Minimum Bounding Sequence) 와 MBS 와 시퀀스 간의 최소 DTW 거리 측정 방식이다. 또한, 이를 이용한 색인 구축 방법 및 질의 처리 방식을 제안한다.
- 이 논문에서 제안하는 것은 유사한 그룹을 대표하는 MBS (Minimum Bounding Sequence) 와 MBS 와 시퀀스 간의 최소 DTW 거리 측정 방식이다. 또한, 이를 이용한 색인 구축 방법 및 질의 처리 방식을 제안한다.
- 언급한 것처럼, PAA 는 시퀀스의 차원을 축소하여 계산 시간을 더욱더 줄이기 위한 차원 축소 방안이다. PAA 로 차원을 축소한 후 하한 거리 기법을 결합하여 필터링 속도를 높인다. 하한 거리에 의해서 선택된 데이터 시퀀스들은 최종 결과가 아니며 DTW를 이용해서 최종 결과를 만들어 내는 정제 과정이 필요하다.
- 즉, 근사 거리 측정 방법을 통해 후보 집합을 선정하고 최종 결과를 정제하는 방법을 사용하지 않는다. 이 문헌에서는 대신, 다수의 참조 시퀀스를 선정하고 모든 데이터 시퀀스와 참조 시퀀스들 간의 DTW 거리를 계산하여 각 시퀀스와 참조 시퀀스들 간의 DTW 거리를 그 시퀀스의 특징으로 부여한다. 이와 같은 특징 변환 방식으로 DTW 거리 대신 유클리디언 거리를 이용해서 거리를 측정할 수 있도록 해서 처리 속도를 높인다.
- 이 문헌에서는 대신, 다수의 참조 시퀀스를 선정하고 모든 데이터 시퀀스와 참조 시퀀스들 간의 DTW 거리를 계산하여 각 시퀀스와 참조 시퀀스들 간의 DTW 거리를 그 시퀀스의 특징으로 부여한다. 이와 같은 특징 변환 방식으로 DTW 거리 대신 유클리디언 거리를 이용해서 거리를 측정할 수 있도록 해서 처리 속도를 높인다.
- 최소 DTW 거리는 데이터 시퀀스 그룹에 대한 거리 측정을 위한 것 이다. 본 논문에서는 대용량의 데이터 시퀀스로부터 적절한 클러스터링 방법을 통해 유사한 데이터 시퀀스 그룹을 생성하는 것을 전제로 한다. 시퀀스 클러스터링 방법은 기존에 개발된 어떠한 것도 사용이 가능하다.
- 제안하는 최소 DTW 거리는 유사한 시퀀스들의 그룹과 질의 시퀀스 사이의 최소 거리를 구기 위한 거리 측정 방법이다. 시퀀스 그룹과의 거리를 측정하기 위해서 시퀀스 그룹에 대한 MBS (Minimum Bounding Sequnce)를 정의한다.
- , Q) 보다 항상 작거나 같다. 제안하는 MinDTWDist 는 MBS의 각 요소와 Q의 각 요소간에 구할 수 있는 거리 중 가장 가까운 거리를 취하므로, M(Q, MBS)의 (m, n)이 M(Q, S) 의 (m, n) 보다 항상 작거나 같다. 따라서, MinDTWDist(Q, MBS(SG)) 는 DTW(Si, Q) 보다 항상 작거나 같다.
- 읽어온 데이터 시퀀스들과 Q와의 DTW를 거리를 계산하여 가장 가까운 K개의 시퀀스를 결과 집합에 저장한다. 우선순위 큐에서 그 다음으로 가까운 그룹의 엔트리와 거리를 꺼내서 결과 집합의 K 번째 데이터와의 거리와 비교한다. 만일 K번째의 거리가 그룹과의 거리보다 작다면 더 이상 검색을 진행할 필요가 없다.
- VA-파일에서 순차검색을 통해 모든 그룹과 Q 사이의 MinDTWDist를 계산한다. 이들 중, 질의로 주어진 거리보다 작은 그룹들을 걸러내고, 각 그룹에 포함되어 있는 모든 데이터 시퀀스들을 읽어온 후 실제 DTW 거리를 계산하여 최종적으로 주어진 거리보다 거리가 작은 데이터 시퀀스들을 찾아낸다.
- 이 논문에서는 제안하는 색인 기법을 검증하기 위해서 기존의 PAA 및 하한 거리를 이용한 색인 기법과 실험을 통해 비교하였다. 성능평가 척도로는 불필요한 DTW 연산의 수행횟수를 선정하였으며, 검색과정에서 수행되는 DTW 연산 횟수를 측정하였다.
- 이 논문에서는 제안하는 색인 기법을 검증하기 위해서 기존의 PAA 및 하한 거리를 이용한 색인 기법과 실험을 통해 비교하였다. 성능평가 척도로는 불필요한 DTW 연산의 수행횟수를 선정하였으며, 검색과정에서 수행되는 DTW 연산 횟수를 측정하였다. 실험에 사용된 데이터는 사람이 특정 노래의 일부분을 노래한 음성파일로부터 특징을 추출한 데이터 시퀀스 이다.
- 성능 비교를 위하여 제안하는 방법과 PAA 및 하한거리를 이용한 색인 방법을 Mac OS 10.7.2, gcc 4.1.1을 기반으로 구현하였다. 이 실험에서는 별도의 클러스터링 방법을 사용하지 않았고 단순히 같은 곡에 대해서 허밍한 노래는 같은 그룹으로 하였다.
- 또한, 이 실험에서는 VA-파일과 같은 별도의 색인 구조를 이용하지 않았다. 즉, 모든 데이터 시퀀스 및 MBS를 순차검색을 통해서 질의를 처리하도록 하였다. 즉, 모든 MBS를 순차적으로 질의 시퀀스와 비교한 후 가장 작은 거리의 MBS 가 대표하는 시퀀스 그룹내의 데이터 시퀀스들과 순차 비교를 하도록 구현하였다.
- 즉, 모든 데이터 시퀀스 및 MBS를 순차검색을 통해서 질의를 처리하도록 하였다. 즉, 모든 MBS를 순차적으로 질의 시퀀스와 비교한 후 가장 작은 거리의 MBS 가 대표하는 시퀀스 그룹내의 데이터 시퀀스들과 순차 비교를 하도록 구현하였다.
- 유사한 데이터 시퀀스가 클러스터링이 되었을 때 생성되는 시퀀스 그룹을 대표하는 MBS를 정의하였다. 그리고, MBS 와 질의 시퀀스와의 거리를 계산하기 위한 최소 DTW 거리를 정의하였다. 또한, MBS와 최소 DTW 거리를 이용하여 K-NN 질의 및 범위 질의를 처리하는 방법을 제안하였다.
- 그리고, MBS 와 질의 시퀀스와의 거리를 계산하기 위한 최소 DTW 거리를 정의하였다. 또한, MBS와 최소 DTW 거리를 이용하여 K-NN 질의 및 범위 질의를 처리하는 방법을 제안하였다.
- 제안하는 방법을 검증하기 위해서 기존에 제안된 하한 거리 및 PAA를 이용한 색인 기법과 제안하는 기법을 구현하고 실험을 통해 K-NN 질의를 처리하기 위해 수행하는 DTW 연산의 횟수를 측정하였다. 비록 소규모의 데이터 시퀀스를 기반으로 하는 실험이었지만, 제안하는 방법이 기존방법에 비해 DTW 연산을 적게 함을 볼 수 있었다.
- 향후 연구에서는 이런 기존방법들과의 결합을 통해 얼마나 성능을 향상 할 수 있는지에 대해서 연구한다. 또한, 실제 응용에서 발생하는 데이터를 이용한 실험을 통해 제안하는 방법의 확장성 및 실세계의 응용에 적합한지를 분석한다.
대상 데이터
- 성능평가 척도로는 불필요한 DTW 연산의 수행횟수를 선정하였으며, 검색과정에서 수행되는 DTW 연산 횟수를 측정하였다. 실험에 사용된 데이터는 사람이 특정 노래의 일부분을 노래한 음성파일로부터 특징을 추출한 데이터 시퀀스 이다. 총 200개의 데이터 시퀀스를 실험에 사용하였다.
- 실험에 사용된 데이터는 사람이 특정 노래의 일부분을 노래한 음성파일로부터 특징을 추출한 데이터 시퀀스 이다. 총 200개의 데이터 시퀀스를 실험에 사용하였다. 각 데이터 시퀀스의 차원은 750 이었다.
- 질의는 총 1024개의 서로 다른 질의를 수행하였으며, 1024개의 질의중 198개는 데이터 시퀀스베이스에 저장되어 있는 시퀀스를 이용하였다. 질의의 형태는 k-nn 질의를 사용했으며 k의 값은 2, 5, 8, 11, 20 으로 바꿔가며 실험하였다.
성능/효과
- 그림에서 보는 것처럼 K가 커질수록 제안하는 방법과 기존 방법의 DTW 계산 횟수 차이가 커짐을 알 수 있다. 제안하는 방법의 경우 그룹이 20개 일 때는 항상 20회의 최소 DTW 거리를 계산해야 하며 이는 DTW 계산 횟수에 포함되었다. 만일 그룹을 대표하는 MBS 들을 다시 클러스터링 하여 계층화 한다면 DTW 연산 횟수를 더 줄일 수 있을 것으로 기대한다.
- 제안하는 방법을 검증하기 위해서 기존에 제안된 하한 거리 및 PAA를 이용한 색인 기법과 제안하는 기법을 구현하고 실험을 통해 K-NN 질의를 처리하기 위해 수행하는 DTW 연산의 횟수를 측정하였다. 비록 소규모의 데이터 시퀀스를 기반으로 하는 실험이었지만, 제안하는 방법이 기존방법에 비해 DTW 연산을 적게 함을 볼 수 있었다.
후속연구
- 제안하는 방법의 경우 그룹이 20개 일 때는 항상 20회의 최소 DTW 거리를 계산해야 하며 이는 DTW 계산 횟수에 포함되었다. 만일 그룹을 대표하는 MBS 들을 다시 클러스터링 하여 계층화 한다면 DTW 연산 횟수를 더 줄일 수 있을 것으로 기대한다.
- 향후에는 제안하는 방법을 바탕으로 계층적으로 색인 구조를 구축하는 방안을 고려할 것이다. 계층적으로 구성하게 되면 보다 높은 필터링 효과를 기대할 수 있다.
- 또한, 제안하는 방법은 기존에 개발된 다른 방법들[7, 2]과 같이 사용할 수 있는 측면이 있다. 향후 연구에서는 이런 기존방법들과의 결합을 통해 얼마나 성능을 향상 할 수 있는지에 대해서 연구한다. 또한, 실제 응용에서 발생하는 데이터를 이용한 실험을 통해 제안하는 방법의 확장성 및 실세계의 응용에 적합한지를 분석한다.
※ AI-Helper는 부적절한 답변을 할 수 있습니다.