선택한 단어 수는 입니다.
최소 단어 이상 선택하여야 합니다.
최소 단어 이상 선택하여야 합니다.
선택한 단어 수는 30입니다.
최대 10 단어까지만 선택 가능합니다.
최대 10 단어까지만 선택 가능합니다.
문제 정의
- 반면, 음악 데이터는 하루에도 전세계적으로 매우 많은 양이 새로 발생하며 이에 대한 허밍 검색을 지원하기 위해서는 검색 속도 측면의 고려가 필요하다. 본 논문에서는 DTW 기반의 거리측정 방법을 이용해서 검색 속도를 높일 수 있는 색인 방법을 제안한다.
- 본 본문에서는 시퀀스 데이터 필터링에 적용할 수 있는 새로운 거리 측정 방식을 제안한다. 제안하는 색인 기법은 기존의 시퀀스 클러스터링 기법 등을 통해 유사한 시퀀스들을 하나의 그룹으로 묶고, 그룹을 대표하는 최소 하한 시퀀스 (MBS, Minimum Bounding Sequence)를 생성한다.
제안 방법
- 또한, MBS 와 최소 DTW 거리를 이용하여 KNN 질의 및 범위 질의를 처리하는 방법을 제안하였다. MP3 로부터 추출한 데이터 시퀀스들 및 메타데이터를 저장 및 검색하기 위한 색인 기법을 제안하여 구현하였다. 데이터 시퀀스와 질의 시퀀스간의 유사도를 비교하여 내용기반 검색을 지원할 수 있도록 한다.
- 개발하는 음악 데이터 관리시스템에는 DTW 기반의 유사도 검색 성능을 높이기 위한 색인 기술을 새롭게 제안하여 구현하였다. 색인 기술은 시퀀스 그룹에 대한 MBS 를 정의하고, MBS 와 질의 시퀀스와의 거리를 계산하기 위한 최소 DTW 거리 기법을 포함한다.
- 제안하는 색인 기법은 기존의 시퀀스 클러스터링 기법 등을 통해 유사한 시퀀스들을 하나의 그룹으로 묶고, 그룹을 대표하는 최소 하한 시퀀스 (MBS, Minimum Bounding Sequence)를 생성한다. 그리고, 질의 시퀀스와 각 그룹을 대표하는 MBS 들과의 최소 DTW 거리를 측정하여 질의와 유사한 시퀀스를 포함할 가능성이 있는 그룹을 찾아내고 그룹내의 시퀀스와의 DTW 거리 측정을 통해서 가장 유사한 시퀀스를 찾아낸다.
- 색인 기술은 시퀀스 그룹에 대한 MBS 를 정의하고, MBS 와 질의 시퀀스와의 거리를 계산하기 위한 최소 DTW 거리 기법을 포함한다. 또한, MBS 와 최소 DTW 거리를 이용하여 KNN 질의 및 범위 질의를 처리하는 방법을 제안하였다. MP3 로부터 추출한 데이터 시퀀스들 및 메타데이터를 저장 및 검색하기 위한 색인 기법을 제안하여 구현하였다.
- 본 논문에서 제안하는 것은 유사한 그룹을 대표하는 Minimum Bounding Sequence (MBS) 와 MBS 와 시퀀스 간의 최소 DTW 거리 측정 방식이다. 또한, 이를 이용한 색인 구축 방법 및 질의 처리 방식을 제안한다.
- 본 논문에서 제안하는 것은 유사한 그룹을 대표하는 Minimum Bounding Sequence (MBS) 와 MBS 와 시퀀스 간의 최소 DTW 거리 측정 방식이다. 또한, 이를 이용한 색인 구축 방법 및 질의 처리 방식을 제안한다.
- 본 논문에서는 제안하는 색인 기법을 검증하기 위해서 기존의 PAA 및 하한 거리를 이용한 색인 기법과 실험을 통해 비교하였다. 성능평가 척도로는 불필요한 DTW 연산의 수행횟수를 선정하였으며, 검색과정에서 수행되는 DTW 연산 횟수를 측정하였다.
- 각 시퀀스 데이터의 차원은 750 이었다. 성능 비교를 위하여 제안하는 방법과 PAA 및 하한거리를 이용한 색인 방법을 Mac OS 10.7.2, gcc 4.1.1을 기반으로 구현하였다. 이 실험에서는 별도의 클러스터링 방법을 사용하지 않았고 단순히 같은 곡에 대해서 허밍 한 노래는 같은 그룹으로 하였다.
- 본 논문에서는 제안하는 색인 기법을 검증하기 위해서 기존의 PAA 및 하한 거리를 이용한 색인 기법과 실험을 통해 비교하였다. 성능평가 척도로는 불필요한 DTW 연산의 수행횟수를 선정하였으며, 검색과정에서 수행되는 DTW 연산 횟수를 측정하였다. 실험에 사용된 데이터는 사람이 특정 노래의 일부분을 노래한 것으로부터 특징을 추출한 시퀀스 데이터 이다.
- 이러한 문제를 해결하기 위해서 다양한 색인 기법들에 대한 연구가 진행되어왔다[1, 2, 3, 4, 5]. 이 방법들을 요약하면, 착오 기각 (False Negative)을 발생 시키지 않으면서 시퀀스 데이터베이스를 필터링 할 수 있는 방법을 이용하여 후보 집합을 찾아낸 후에 DTW 를 이용해 최종 결과를 찾아낸다. 기존에 제안된 필터링 방법들 중 가장 대표적인 것은 하한 거리 (Lower Bound)와 PAA (Piece-wise Aggregate Approximation) 이다.
- 데이터 시퀀스와 질의 시퀀스간의 유사도를 비교하여 내용기반 검색을 지원할 수 있도록 한다. 이때 검색 성능을 향상시키기 위한 색인을 설계하고 구현하였다. 100%의 정확도를 유지할 때 약 21%의 검색시간을 줄일 수 있었다.
- 이를 보완하기 위해서 구간을 값의 분포에 따라서 동적 구간을 이용한 시퀀스 추상화 기법인 Dynamic Sequence Abstraction (DSA)을 제안한다. 그림 3 은 기본 구간의 크기를 4 로 하고 한 구간의 상한 및 하한 값의 차이를 2 보다 작게하면서 추상화를 수행한 결과 이다.
- 본 본문에서는 시퀀스 데이터 필터링에 적용할 수 있는 새로운 거리 측정 방식을 제안한다. 제안하는 색인 기법은 기존의 시퀀스 클러스터링 기법 등을 통해 유사한 시퀀스들을 하나의 그룹으로 묶고, 그룹을 대표하는 최소 하한 시퀀스 (MBS, Minimum Bounding Sequence)를 생성한다. 그리고, 질의 시퀀스와 각 그룹을 대표하는 MBS 들과의 최소 DTW 거리를 측정하여 질의와 유사한 시퀀스를 포함할 가능성이 있는 그룹을 찾아내고 그룹내의 시퀀스와의 DTW 거리 측정을 통해서 가장 유사한 시퀀스를 찾아낸다.
- 최소 DTW 거리는 대용량의 시퀀스 데이터로부터 적절한 클러스터링 방법을 통해 유사한 시퀀스 데이터 그룹을 생성하고 이를 기반으로 DTW 거리를 측정한다. 시퀀스 클러스터링 방법 K-means 알고리즘을 사용한다.
대상 데이터
- 성능 및 정확도를 측정하기 위해서 2000 개의 데이터 시퀀스와 20 개의 질의 시퀀스를 가지고 실험을 수행하였다. HW 는 AMD 2.
- 성능평가 척도로는 불필요한 DTW 연산의 수행횟수를 선정하였으며, 검색과정에서 수행되는 DTW 연산 횟수를 측정하였다. 실험에 사용된 데이터는 사람이 특정 노래의 일부분을 노래한 것으로부터 특징을 추출한 시퀀스 데이터 이다. 총 200개의 시퀀스 데이터를 실험에 사용하였다.
- 이 실험에서는 별도의 클러스터링 방법을 사용하지 않았고 단순히 같은 곡에 대해서 허밍 한 노래는 같은 그룹으로 하였다. 질의는 총 1204 개의 서로 다른 질의를 수행하였으며, 1024 개의 질의 중 198 개는 시퀀스 데이터베이스에 저장되어 있는 시퀀스를 이용하였다. 질의의 형태는 K 의 값은 2, 5, 8, 11, 20 으로 바꿔가며 실험하였다.
- 실험에 사용된 데이터는 사람이 특정 노래의 일부분을 노래한 것으로부터 특징을 추출한 시퀀스 데이터 이다. 총 200개의 시퀀스 데이터를 실험에 사용하였다. 각 시퀀스 데이터의 차원은 750 이었다.
이론/모형
- 최소 DTW 거리는 대용량의 시퀀스 데이터로부터 적절한 클러스터링 방법을 통해 유사한 시퀀스 데이터 그룹을 생성하고 이를 기반으로 DTW 거리를 측정한다. 시퀀스 클러스터링 방법 K-means 알고리즘을 사용한다. 생성한 시퀀스 그룹과 질의시퀀스 사이의 유사도를 측정할 수 있다면 가장 가까운 시퀀스 그룹내의 시퀀스 데이터와 질의 시퀀스를 우선적으로 비교하여 유사한 시퀀스를 빠르게 검색 할 수 있다.
- 따라서, 대부분의 클러스터의 MBS 가전체 데이터 영역을 포함하게 되어 MBS 간의 변별력이 떨어지게 된다. 이 문제를 해결하기 위해서 도입한 방법은 시퀀스 추상화 Sequence Abstraction (SA) 기법이다.
성능/효과
- 이때 검색 성능을 향상시키기 위한 색인을 설계하고 구현하였다. 100%의 정확도를 유지할 때 약 21%의 검색시간을 줄일 수 있었다. 또한, 색인의 파라미터인 a 를 변화시킴에 따라 정확도와 검색성능에 변화가 있는데, 약 90%의 검색 정확도를 유지하면서 검색 시간을 50% 이상 향상 시킬 수 있다.
- 100%의 정확도를 유지할 때 약 21%의 검색시간을 줄일 수 있었다. 또한, 색인의 파라미터인 a 를 변화시킴에 따라 정확도와 검색성능에 변화가 있는데, 약 90%의 검색 정확도를 유지하면서 검색 시간을 50% 이상 향상 시킬 수 있다.
- 실제로 실험을 통해서 살펴본 결과 데이터 시퀀스들과 질의 시퀀스간의 MinDTWDist 의 최대값이 DTW 의 최소 값보다 작은 경우를 많이 볼 수 있었다. 이것은 모든 데이터 시퀀스들이 후보집합으로 선정된다는 뜻으로 MinDTWDist 를 수행하는 비용이 DTW 를 수행하는 비용에 고스란히 더해 지게 된다.
후속연구
- k 는 전체 데이터 시퀀스 수보다 훨씬 작기 때문에 대부분의 DTW 계산의 경우에 중간 누적 값이 k-distance 보다 커지게 될 것이다. 이렇게 중간에 계산을 멈추게 할 수 있다면 계산비용을 상당히 줄일 수 있는 상한 값 기반 Upper Bound DTW, UBDTW (UBDTW) 알고리즘을 제안한다. UBDTW 에서는 다음 단계에서 계산하지 않아도 되는 영역을 설정하고 이 영역 안에서만 warping path 계산을 수행하도록 제한한다.
※ AI-Helper는 부적절한 답변을 할 수 있습니다.