arXiv:2307.04904

Fast dynamic time warping and clustering in C++

Volkan Kumtepeli, Rebecca Perriment, David A. Howey

제출 2023-07-10

원문 초록

We present an approach for computationally efficient dynamic time warping (DTW) and clustering of time-series data. The method frames the dynamic warping of time series datasets as an optimisation problem solved using dynamic programming, and then clusters time series data by solving a second optimisation problem using mixed-integer programming (MIP). There is also an option to use k-medoids clustering for increased speed, when a certificate for global optimality is not essential. The improved efficiency of our approach is due to task-level parallelisation of the clustering alongside DTW. Our approach was tested using the UCR Time Series Archive, and was found to be, on average, 33% faster than the next fastest option when using the same clustering method. This increases to 64% faster when considering only larger datasets (with more than 1000 time series). The MIP clustering is most effective on small numbers of longer time series, because the DTW computation is faster than other approaches, but the clustering problem becomes increasingly computationally expensive as the number of time series to be clustered increases.

함께 살펴볼 논문

공통 태그를 근거로 연결했습니다. 실제 인용 관계나 논문의 우수성을 뜻하지 않습니다.

arXiv:2609.24223v1cs.CV공통 태그 Clustering, Time Series, Dynamic Time Warping

DiaSeg: 해석 가능한 보행 분석을 위한 DTW 경로에서의 대각 세그먼트 추출

DiaSeg: Diagonal Segment Extraction from DTW Paths for Interpretable Gait Analysis

동적 시간 워핑(Dynamic Time Warping, DTW)은 시계열 간 유사도를 측정하는 데 지배적으로 사용되는 방법이지만, 표준적인 방식은 단일 거리 값을 계산한 후 최적 워핑 경로를 폐기함으로써 임상 진단과 가장 관련이 깊은 지역적 정렬 정보를 잃는다. 본 논문은 제어된 단절을 허용하며 DTW 경로에서 대각 세그먼트를 추출하는 프레임워크인 DiaSeg를 소개한다. DiaSeg는 각 세그먼트를 다섯 가지 기하학적 특징(유효 길이, 단절 횟수, 비용 변동, 시간적 위치, 경로 맥락)으로 특성화하며, 도메인 특화 특징 공학(feature engineering) 없이 비지도 패턴 발견을 가능하게 한다. 6가지 임상 상태(건강한 노화, 파킨슨병, 헌팅턴병, 근위축성 측삭경화증(ALS), 뇌종양, 뇌졸중)에 걸친 91명의 피험자를 대상으로 검증한 결과, 세 가지 결과가 도출되었다. 첫째, 대각 세그먼트는 생체역학적 단계 주석과 일치하는 일관된 비지도 패턴을 형성하며(실루엣 계수 0.33), 레이블 기반 검증을 통해 건강한 보행과 병리적 보행 간 거의 완벽한 분리를 확인하였다(조정 랜드 지수(ARI) 최대 0.986). 둘째, 세그먼트는 지도 학습에서 69%, 환자 수준 클러스터링에서 75%의 정확도로 병리를 구분하며, 병리는 세그먼트 길이의 분포적 변화를 통해 나타난다. 세그먼트 특징과 주기(cycle) 수준 특징을 결합하면 분류(classification) 정확도가 91.7%까지 향상된다. 셋째, 주기 기반 방법이 더 높은 정확도(91%)를 달성하지만, 대각 세그먼트는 전역적 표현으로는 얻을 수 없는 단계별 해석 가능성을 제공하여 보행 주기 내에서 협응이 무너지는 위치를 국소화할 수 있다. 이처럼 DiaSeg는 DTW를 블랙박스 거리 척도에서 신경퇴행성 질환 평가를 위한 해석 가능한 시간적 특징의 원천으로 전환한다.

arXiv:2607.22508v1cs.LG공통 태그 Clustering, Time Series

bag-of-waves를 이용한 해석 가능한 EEG 바이오마커: 저데이터 환경을 위한 공간·시간 파형 사전

Interpretable EEG biomarkers with bag-of-waves: Spatial and temporal waveform dictionaries for low-data regimes

EEG(전기뇌파)는 신경학적 질환 진단에 널리 사용되지만, 그 분석은 보통 사전 정의된 스펙트럼 특징이나 심층 신경망에 의존한다. 사전 정의된 특징은 정보적 가치가 있는 것을 미리 고정하기 때문에 강한 바이어스를 수반하며, 심층 신경망과 파운데이션 모델은 해석하기 어렵고 대량의 데이터와 연산 자원이 필요하다. 우리는 bag-of-waves를 제안한다. 이는 레이블 없이 shift-invariant k-means를 사용하여 반복되는 EEG 파형 템플릿(atom이라고 함)의 작은 사전을 학습하는 해석 가능한 프레임워크이다. 연속 EEG 신호는 atom 토큰의 시퀀스로 변환되며, 그 토큰의 빈도는 간단한 하류 분류기 또는 클러스터링 단계에 입력된다. 이 표현을 두 가지 방식으로 확장한다: 시간적 구조를 포착하기 위해 atom 간 전이(n-gram이라고 부름)를 추가하고, 다채널 경우를 위해 단일 채널 atom에서 지역 및 채널 간 공간 atom으로 확장한다. 세 가지 상호 보완적인 데이터셋에서 방법을 검증한다. 각 데이터셋은 서로 다른 측면을 탐구한다: 동물 16마리만으로 수행한 단일 채널 마우스 유전형 클러스터링(저데이터 및 시간적 사례), 휴식 상태 치매 분류(공간적 사례), 그리고 임상 EEG 이벤트의 6분류를 위한 TUEV 벤치마크(강력한 심층 및 파운데이션 기준선과의 고데이터 비교). 세 데이터셋 모두에서 bag-of-waves는 최첨단 심층 및 파운데이션 모델과 경쟁력 있는 성능을 달성한다. 그러나 매개변수 수의 극히 일부만으로 동작하며 완전한 해석 가능성을 제공한다. 모든 atom이 검사 가능한 파형에 대응하기 때문에, 이 방법은 신경생리학자가 직접 검증할 수 있는 알려진 임상 형태학을 명시적으로 복원한다. 주요 장점은 더 무거운 모델이 적합하지 않은 저데이터 환경에서도 잘 작동한다는 점이다.

arXiv:2607.14190v1cs.LG공통 태그 Clustering, Time Series

ALS 진행 및 의료 서비스 이용 예측을 위한 시간적 머신러닝 기반 시간-이벤트 모델

A Temporal Machine Learning-Based Time-to-Event Model for Predicting ALS Progression and Healthcare Utilization

근위축성측索경화증(ALS)은 진행성이며 이질적인 신경퇴행성 질환으로, 보조 기기 사용과 같은 임상적으로 의미 있는 이정표를 예측하는 것은 여전히 어렵다. 우리는 종단적 ALS 기능 평가 척도-개정판(ALSFRS-R) 궤적과 생존 모델링(survival modeling)을 통합하여 기능 저하와 보조 기기 이용에 대한 개인화된 예측을 지원하는 시간-이벤트(time-to-event), 디지털 트윈(digital twin) 영감의 프레임워크를 개발했다. 진단 기록, ALSFRS-R 평가, 일상생활 활동, 인구통계학적 정보를 통합하여 조화된 종단 데이터셋을 구축한 뒤, 데이터 품질, 시간적 정렬, 코호트 일관성을 보장하기 위한 전처리를 수행했다. 상관 기반 클러스터링은 연하, 상지, 체간, 하지, 호흡계에 걸친 일관된 기능 영역을 식별했다. 일반화 가법 혼합 모델(generalized additive mixed models)은 모든 영역에서 비선형적이고 영역 특이적인 기능 저하를 특성화했다. 또한 종단적 기능 저하를 예측하고 단계 의존적 질병 진행을 포착하기 위해 시간적 머신러닝 모델을 개발했다. Cox 비례 위험 모델링(Cox proportional hazards modeling)은 또한 하지 기능, 특히 보행과 계단 오르기를 더 이른 휠체어 사용의 가장 강력한 예측 변수로 식별했다. 이러한 결과를 바탕으로, 개인화된 생존 곡선을 생성하고 휠체어 없이 생존하는 기간을 동적으로 예측하는 디지털 트윈 영감의 시간적 머신러닝 기반 시간-이벤트(TTE) 모델을 구현했다. 이 프레임워크는 ALS 진행을 개인화된 의사결정 지원과 연결하는 확장 가능하고 해석 가능하며 임상적으로 실행 가능한 접근법을 제공하며, 선제적 돌봄 계획, 임상시험 층화, 정밀 의학(precision medicine)에 적용할 수 있다.

토론

이 논문과 연결된 포럼 글이 아직 없습니다.