복잡도-불변 거리(Complexity-Invariant Distance, CID)

복잡도-불변 거리(Complexity-Invariant Distance, CID)는 시간 계열 데이터의 분류 및 유사성 측정 시 복잡도 차이로 인한 오류를 보정하기 위해 설계된 거리 측정 방법입니다. 기존 유클리드 거리(Euclidean Distance)나 DTW(Dynamic Time Warping)와 같은 방법들은 시계열의 형태적 차이는 고려하지만, 복잡도(예: 피크, 밸리의 수) 차이는 반영하지 못해 복잡한 형태의 시계열을 단순한 클래스로 오분류하는 문제가 있었습니다. CID는 이러한 문제를 해결하기 위해 복잡도를 보정하는 인자를 도입했습니다[1][3].

핵심 개념

1. 복잡도 추정(Complexity Estimate, CE)  

  

시계열 T의 복잡도는 연속된 데이터 포인트 간 차이의 제곱합 제곱근으로 계산됩니다:

이 값이 클수록 시계열의 형태 변화가 심해 복잡도가 높음을 의미합니다[1].

2. 보정 인자(Complexity Factor, CF)  

  
두 시계열 $$ Q $$와 $$ C $$의 복잡도 차이를 반영하는 인자로, 다음과 같이 정의됩니다:  
  

복잡도 차이가 클수록 CF 값이 증가하여 거리를 확대합니다[1].

3. CID 공식

  
기존 유클리드 거리(ED)에 CF를 곱해 최종 거리를 계산합니다:

   이는 복잡한 시계열 간 거리를 상대적으로 축소하고, 단순-복잡 시계열 간 거리를 확대합니다[1][3].

주요 특징

- 효율성: CE 계산은 $$ O(n) $$ 시간 복잡도를 가지며, 기존 유클리드 거리 기반 인덱싱 기법과 호환됩니다[1].

- 실험적 검증: 43개 데이터셋에서 CID는 32개에서 정확도 향상, 8개에서 감소, 3개에서 동일한 성능을 보였습니다. 특히 87.54%의 경우 CID가 복잡도가 더 비슷한 이웃을 선택했습니다[1].

- 응용 분야:  
  > 분류: 복잡도 차이로 인한 오분류 감소.  
  > 클러스터링/모티프 탐색: 복잡도 보정을 통한 군집화 정확도 개선[1][3].  
  > 의료/기상 데이터 분석: 복잡한 패턴을 포함하는 시계열의 유사성 측정[3].

비교 실험 예시

CID는 복잡도 차이를 명시적으로 고려함으로써 기존 방법의 한계를 극복하며, 구현이 간단하고 계산 효율성이 높아 실제 응용에서 유용하게 활용됩니다[1][3].



Citations:
[1] https://www.cs.ucr.edu/~eamonn/Complexity-Invariant%20Distance%20Measure.pdf
[2] https://ai4ce.github.io/CID/
[3] http://www.jmest.org/wp-content/uploads/JMESTN42350863.pdf
[4] https://rdrr.io/cran/TSclust/man/diss.CID.html
[5] https://rdrr.io/cran/TSdist/man/CIDDistance.html
[6] https://www.semanticscholar.org/paper/Distinct-Distances-with-$%5Cell_p$-Spaces-AlQady-Chabot/eb4471b06585654ae607b0980342ee4a60a5fd8b
[7] https://proceedings.neurips.cc/paper_files/paper/1993/file/4b0a59ddf11c58e7446c9df0da541a84-Paper.pdf
[8] https://www.mysciencework.com/publication/download/comparing-efficiency-cid-distance-cort-coefficient-finding-similar-subsequences-time-series-1/8f8d2b93a594fb7a4e8a68f0d4489ebd
[9] https://dl.acm.org/doi/10.1007/s10618-013-0312-3
[10] https://search.ebscohost.com/login.aspx?direct=true&profile=ehost&scope=site&authtype=crawler&jrnl=13845810&AN=94420418&h=McLykgE%2BeLHAHM6bARY6tDObtrwp2Te1wt6i6QH%2BTSOCfJlykEbJ3eEFXAiikcUf285uj%2FIo7HUQq5nSC7FgxQ%3D%3D&crl=c
[11] https://www.academia.edu/49401343/Comparing_the_efficiency_of_CID_distance_and_CORT_coefficient_for_finding_similar_subsequences_in_time_series
[12] https://www.academia.edu/92439121/CID_an_efficient_complexity_invariant_distance_for_time_series
[13] https://fs.unm.edu/neut/DistanceMeasuresBetween.pdf
[14] https://papers.nips.cc/paper/1581-classification-in-non-metric-spaces
[15] https://epubs.siam.org/doi/10.1137/1.9781611972818.60
[16] https://en.wikipedia.org/wiki/Total_variation_distance_of_probability_measures
[17] http://pascal-usc.primo.exlibrisgroup.com/discovery/fulldisplay?docid=cdi_proquest_miscellaneous_1520929195&context=PC&vid=01PASCAL_USCCOL%3ASOM&lang=en&search_scope=MyInst_and_CI&adaptor=Primo+Central&tab=Everything&query=null%2C%2CCID%2CAND&mode=advanced&offset=0
[18] https://www.sciencedirect.com/science/article/abs/pii/S0031320319301918
[19] http://www.csam.or.kr/journal/view.html?doi=10.29220%2FCSAM.2020.27.6.589
[20] https://search.r-project.org/CRAN/refmans/TSdist/html/CIDDistance.html
[21] https://www.ams.org/notices/200005/fea-krantz.pdf
[22] https://www.sciencedirect.com/science/article/pii/0031320394901562
[23] https://www.proquest.com/conference-papers-proceedings/complexity-invariant-distance-measure-time-series/docview/881212033/se-2
[24] https://www.degruyter.com/document/doi/10.1515/9783110253863/html
[25] https://publikationen.bibliothek.kit.edu/1000100198/48552071
[26] https://www.rdocumentation.org/packages/TSclust/versions/1.3.1/topics/diss.CID
[27] https://www.degruyter.com/document/doi/10.1515/9783110870312/html
[28] https://openreview.net/forum?id=4JB42GBxGs&noteId=stdVq47g6M
[29] https://openaccess.thecvf.com/content_CVPRW_2019/papers/PBVS/Chakraborty_Sur-Real_Frechet_Mean_and_Distance_Transform_for_Complex-Valued_Deep_Learning_CVPRW_2019_paper.pdf