E-means 3분 소요

E-means가 10번 만에 끝난다면, k-means보다 10배 빠를까요?

핵심 요약

  • 반복 횟수가 10분의 1이어도 한 번에 얼마나 계산하느냐에 따라 실제 속도는 달라집니다.
  • 기본적인 k-means의 반복당 계산량은 데이터 수, 군집 수, 차원 수에 따라 달라집니다.
  • 전체 실행 시간을 잴 때는 반복 계산뿐 아니라 초기화와 알고리즘별 준비 작업에 걸리는 시간도 포함해야 합니다.
  • E-means의 성능을 판단하려면 같은 데이터에서 비슷한 품질의 결과를 얻기까지 걸리는 시간을 비교해야 합니다.

“100번 반복하던 계산을 10번으로 줄였다”는 설명을 들으면 계산이 훨씬 빨라졌다고 생각하기 쉽습니다. 데이터가 많을수록 처리 시간을 줄이는 일이 중요하니까요. 그런데 E-means와 k-means의 성능을 비교할 때, 이 숫자를 곧바로 “10배 빠르다”로 읽어도 될까요?

반복 횟수는 시간의 단위가 아닙니다

알고리즘마다 ‘한 번’에 하는 작업량은 다릅니다. 한 번 반복할 때 간단한 거리 계산만 할 수도 있고, 여러 후보를 검토하느라 추가 계산을 할 수도 있습니다.

실행 시간은 대략 이렇게 나눠볼 수 있습니다.

전체 시간 ≈ 초기화·준비 시간 + 반복 횟수 × 평균 반복당 시간

그래서 반복 횟수 기준 수렴 속도와 실제 실행 속도를 구분해야 합니다. 여기서 수렴은 알고리즘이 정해진 종료 조건에 도달했다는 뜻입니다. 반드시 가장 좋은 답을 찾았다는 뜻은 아닙니다.

E-means가 반복 횟수를 줄이더라도 한 번에 하는 작업이 늘어나면, 실제로 줄어드는 시간은 적을 수 있습니다. 반대로 한 번 반복할 때 드는 비용까지 줄었다면 시간을 더 많이 아낄 수 있습니다.

k-means는 한 바퀴 돌 때 무엇을 할까요?

k-means는 데이터를 k개의 군집으로 나누는 방법입니다. 기본적인 Lloyd 방식은 다음 두 작업을 번갈아 합니다.

  1. 각 데이터를 가장 가까운 군집 중심에 배정합니다.
  2. 각 군집에 속한 데이터의 평균으로 중심을 다시 계산합니다.

데이터가 n개이고 군집이 k개이며, 데이터마다 d개의 특징이 있다고 해보겠습니다. 모든 데이터와 모든 중심 사이의 거리를 직접 계산하는 배정 단계에서는 대략 O(nkd)만큼 연산합니다. 데이터 수, 군집 수, 특징 수가 늘수록 계산량도 늘어난다는 뜻입니다.

예를 들어 구매액, 방문 횟수 같은 특징으로 고객을 묶는 경우를 생각해보면 됩니다. 고객 수나 나눌 고객군 수가 많아지면 한 번 반복할 때 할 계산도 늘어납니다. 비교할 특징이 늘어날 때도 마찬가지입니다.

다만 이 설명은 기본 구현을 기준으로 합니다. 실제 구현에서는 불필요한 거리 계산을 건너뛰기도 하고, 병렬 처리 여부에 따라서도 실행 시간이 달라집니다. ‘k-means와 비교했다’는 설명을 볼 때는 어떤 구현을 사용했는지도 확인해야 합니다.

10분의 1만 반복해도 10배 빠르지 않은 이유

아래는 원리를 설명하기 위한 가상 계산입니다. E-means의 성능을 실제로 측정한 수치는 아닙니다. 초기화와 준비 시간은 제외했습니다.

비교 상황반복 횟수평균 반복당 시간반복 계산 총시간
k-means 기준100회10밀리초1초
E-means 가정 A10회60밀리초0.6초
E-means 가정 B10회120밀리초1.2초

가정 A에서는 반복 횟수가 10분의 1이지만, 실행 시간은 40% 줄어듭니다. 속도로 비교하면 약 1.67배 빠른 셈입니다.

가정 B에서는 반복을 훨씬 적게 하고도 시간이 20% 더 걸립니다. 한 번 반복할 때 드는 비용이 12배이기 때문입니다.

여기에 알고리즘별 준비 시간까지 더하면 결과는 또 달라집니다. 시작 전에 후보를 만들거나 보조 자료구조를 구성해야 한다면, 그동안에도 사용자는 기다려야 합니다.

반복 횟수는 유용한 지표입니다. 하지만 그 숫자만으로 전체 실행 시간을 계산할 수는 없습니다.

공정한 비교의 기준은 ‘비슷한 품질까지 걸린 시간’입니다

더 빨리 끝났다고 해서 더 효율적이라고 단정할 수는 없습니다. 종료 조건이 느슨해서 일찍 멈췄을 수도 있기 때문입니다.

k-means에서 흔히 확인하는 값은 각 데이터와 소속 군집 중심 사이의 제곱거리 합입니다. 같은 데이터와 같은 군집 수에서는 이 값이 작을수록 해당 목적함수를 더 잘 최소화했다고 볼 수 있습니다. 다만 그렇게 얻은 군집이 실제 업무에 유용한지는 따로 판단해야 합니다.

E-means와 k-means가 같은 목적함수를 쓴다면, 비슷한 목적함수 값에 도달하기까지 걸린 시간을 비교할 수 있습니다. 목적함수가 다르다면 두 결과의 품질을 어떤 기준으로 평가할지부터 정해야 합니다.

성능을 비교할 때는 다음 조건도 확인해야 합니다.

  • 입력 조건: 같은 데이터, 군집 수, 전처리를 사용했는지 확인합니다.
  • 측정 범위: 초기화와 알고리즘별 준비 작업에 걸린 시간을 전체 시간에 포함했는지 봅니다.
  • 실행 환경: 하드웨어와 병렬 처리 조건을 맞췄는지 확인합니다.
  • 결과의 변동: 무작위 초기화를 사용한다면 여러 번 실행한 시간과 결과의 품질을 함께 비교합니다.

메모리 사용량도 영향을 줍니다. 중간 계산 결과를 저장해두면 계산은 줄일 수 있지만, 저장 공간은 더 필요할 수 있습니다. 작은 데이터에서 유리했던 방식이 큰 데이터에서도 같은 이점을 보일지는 따로 살펴봐야 합니다.

E-means가 더 빠른지 판단하려면 원하는 품질의 결과를 얻는 데 드는 전체 비용을 비교해야 합니다. “반복 횟수가 10분의 1”이라는 설명만으로는 부족합니다. “한 번에 얼마나 계산하고, 최종 결과는 얼마나 좋으며, 실제로 몇 초가 걸렸나요?”라는 질문에도 답할 수 있어야 합니다.

E-means k-means 알고리즘 성능

댓글

    댓글을 불러오는 중...