차원의 저주

차원의 저주(次元의 詛呪, 영어: Curse of dimensionality)는 데이터의 차원이 높아질 수록 알고리즘의 실행이 아주 까다로워지는 일이다.

차원의 저주는 일상 경험의 3차원 물리적 공간과 같은 저차원 환경에서는 발생하지 않는 고차원 공간에서 데이터를 분석하고 정리할 때 발생하는 다양한 현상을 말한다. 이 표현은 리처드 E. 벨맨(Richard E. Bellman)이 동적 프로그래밍의 문제를 고려할 때 만들었다.

차원의 저주 현상은 수치 분석, 샘플링, 조합, 기계 학습, 데이터 마이닝 및 데이터베이스와 같은 영역에서 발생한다. 이러한 문제의 공통 주제는 차원이 증가하면 공간의 부피가 너무 빨리 증가하여 사용 가능한 데이터가 희소해진다는 것이다. 신뢰할 수 있는 결과를 얻기 위해 필요한 데이터의 양이 차원에 따라 기하급수적으로 증가하는 경우가 많다. 또한 데이터 구성 및 검색은 종종 개체가 유사한 속성을 가진 그룹을 형성하는 영역을 감지하는 데 의존한다. 그러나 고차원 데이터에서는 모든 객체가 여러 면에서 희소하고 유사하지 않아 공통 데이터 구성 전략이 효율적이지 못하다.