평균 이동 군집화 (r1)

커널 함수는 데이터 공간에서 각 점의 영향력을 정의하는 비음수 함수이다. 이 함수는 점으로부터의 거리에 따라 가중치를 부여하며, 일반적으로 거리가 증가할수록 가중치는 감소한다. 대표적인 커널 함수로는 가우시안 커널, 에파네치니코프 커널, 직사각형 커널 등이 있다. 커널의 선택은 최종 군집의 형태와 경계에 영향을 미친다.

대역폭은 커널 함수의 영향 범위를 결정하는 핵심 매개변수이다. 이는 커널의 '폭'을 조절하며, 실질적으로 군집화의 세부 수준을 통제한다. 넓은 대역폭을 사용하면 커널의 영향 범위가 커져 적은 수의 크고 일반화된 군집이 형성되는 반면, 좁은 대역폭을 사용하면 많은 수의 작고 세분화된 군집이 생성된다. 따라서 대역폭 선택은 과소적합과 과대적합 사이의 균형을 잡는 문제가 된다.

커널 함수와 대역폭의 관계는 다음 표로 요약할 수 있다.

실제 알고리즘에서, 대역폭 h가 주어지면 점 x 주변의 커널 밀도 추정치는 주변 모든 점 x_i에 대해 K((x - x_i)/h) 형태의 커널 함수 값의 합으로 계산된다. 평균 이동 벡터는 이 밀도 함수의 기울기 방향을 따라 움직이도록 설계되어, 결국 밀도가 가장 높은 지점인 정상점으로 수렴하게 한다.

밀도 기울기 추정은 평균 이동 군집화 알고리즘의 수학적 기반을 제공하는 핵심 개념이다. 이는 주어진 데이터 공간에서 확률 밀도 함수의 기울기를 추정하여, 데이터 포인트들이 밀집된 지역, 즉 지역적 최대 밀도 지점을 찾아내는 과정을 의미한다. 알고리즘은 각 데이터 점을 시작점으로 하여, 추정된 밀도 기울기의 방향으로 점진적으로 이동시켜 최종적으로 수렴하는 지점을 군집의 중심으로 결정한다.

밀도 기울기 추정은 커널 밀도 추정을 통해 수행된다. 데이터 공간의 임의의 점 x에서의 확률 밀도 함수 f(x)는 주변 데이터 점들에 커널 함수를 적용하여 추정한다. 이때, 밀도 함수의 기울기 ∇f(x)는 밀도가 가장 가파르게 증가하는 방향을 가리킨다. 평균 이동 알고리즘은 이 기울기 방향을 따라 데이터 점을 이동시키는데, 실제 계산은 추정된 밀도 함수의 대수 기울기를 사용하여 단순화된다. 이는 결국 '평균 이동 벡터'라는 형태로 나타나며, 현재 위치 주변의 데이터 점들의 가중 평균 위치와 현재 위치의 차이로 계산된다.

이 과정을 통해 각 데이터 점은 반복적으로 밀도 기울기 방향, 즉 평균 이동 벡터 방향으로 이동하게 되고, 결국 밀도 기울기가 0이 되는 지점, 즉 지역적 밀도 최대점에 도달하게 된다. 따라서 밀도 기울기 추정은 데이터의 자연스러운 군집 구조를 발견하기 위한 방향과 경로를 제공하는 내비게이션 역할을 한다고 볼 수 있다.

평균 이동 군집화 알고리즘의 첫 단계는 데이터 공간에서 군집 중심이 될 가능성이 있는 후보점들을 선정하는 것이다. 이 과정은 알고리즘의 효율성과 최종 군집의 질에 직접적인 영향을 미친다.

가장 간단한 초기화 방법은 데이터셋의 모든 점을 후보점으로 사용하는 것이다. 각 데이터 포인트에서 알고리즘이 독립적으로 시작되어 밀도 기울기를 따라 이동한다. 이 방법은 계산 비용이 높지만, 데이터의 모든 세부 구조를 탐색할 가능성을 최대화한다. 계산 효율성을 높이기 위해 무작위로 샘플링된 데이터 포인트의 부분집합만을 후보점으로 사용하기도 한다. 또는 그리드 기반 샘플링을 통해 데이터 공간을 규칙적인 간격으로 나누고 각 그리드 셀의 중심점을 후보점으로 삼을 수 있다.

후보점이 선정되면, 각 후보점은 군집 중심을 찾기 위한 탐색의 시작점이 된다. 각 후보점 주변의 커널 함수와 대역폭에 정의된 지역 내 데이터 포인트들의 가중 평균 위치를 반복적으로 계산하며, 이 위치로 후보점을 이동시킨다. 초기 후보점의 선택은 알고리즘의 수렴 속도에 영향을 주지만, 평균 이동 과정의 특성상 최종적으로 동일한 정상점에 수렴하는 시작점들은 하나의 군집으로 병합되므로, 초기화의 정확도보다는 포괄성이 더 중요할 수 있다.

평균 이동 벡터는 각 데이터 점이 위치한 곳의 확률 밀도 함수의 기울기 방향을 따라 가장 가까운 정상점(peak)으로 이동하도록 하는 방향 벡터입니다. 이 벡터는 현재 점 주변의 데이터 분포를 기반으로 계산됩니다.

벡터 계산은 주어진 점 x에 대해, 그 주변 대역폭 h 내에 있는 모든 이웃 점들의 가중 평균 위치와 현재 점 x의 차이로 정의됩니다. 수식으로 표현하면 다음과 같습니다.

M_h(x) = ( Σ_i K( (x - x_i)/h ) * x_i ) / ( Σ_i K( (x - x_i)/h ) ) - x

여기서 K는 커널 함수이며, x_i는 데이터셋 내의 점들입니다. 분모는 정규화 항으로, 가중치의 합을 나타냅니다. 이 계산은 본질적으로 현재 점 주변의 확률 밀도의 기울기 방향을 추정하는 과정입니다[2].

계산된 평균 이동 벡터는 항상 지역적 밀도가 가장 증가하는 방향을 가리킵니다. 알고리즘은 이 벡터를 반복적으로 적용하여 점의 위치를 업데이트합니다(x <- x + M_h(x)). 이 과정을 통해 각 점은 점차 주변 데이터가 가장 밀집된 지역, 즉 확률 밀도 함수의 지역적 최대값(모드)을 향해 이동하게 됩니다. 벡터의 크기가 사전에 정의된 임계값보다 작아지면 해당 점의 이동이 수렴한 것으로 판단합니다.

각 데이터 포인트에 대해 평균 이동 벡터를 반복적으로 적용하면, 포인트는 확률 밀도 함수의 국부적 최댓값, 즉 모드(mode)를 향해 이동한다. 이 과정은 이동 거리가 미리 설정된 임계값(보통 매우 작은 값)보다 작아질 때까지 계속된다. 이 시점에서 해당 포인트는 수렴했다고 판단하며, 그 최종 위치를 수렴점(convergence point) 또는 모드로 기록한다.

모든 데이터 포인트가 각자의 수렴점에 도달한 후, 유사한 수렴점을 가진 포인트들을 하나의 군집으로 묶는다. 일반적으로 두 수렴점 사이의 유클리드 거리가 사용자가 지정한 병합 임계값(merging threshold)보다 작으면 동일한 군집으로 간주하고 병합한다. 이 병합 과정은 알고리즘의 최종 출력인 군집 레이블을 생성한다.

수렴과 병합 과정은 알고리즘이 데이터의 자연스러운 군집 개수와 형태를 자동으로 발견할 수 있게 해주는 핵심 단계이다. 아래 표는 이 과정의 주요 요소를 요약한다.

이 방식은 초기에 군집 개수(K)를 지정해야 하는 K-평균 알고리즘과 달리, 데이터 분포에 기반하여 군집의 수를 데이터로부터 추정한다는 점이 특징이다. 그러나 대역폭과 병합 임계값이라는 매개변수 선택이 최종 군집 결과에 큰 영향을 미친다.

평균 이동 군집화는 데이터의 형태나 분포에 대한 사전 가정 없이도 작동하는 비모수적 방법이다. 이는 데이터가 특정 분포를 따르지 않거나, 군집의 모양이 구형이 아닌 복잡한 형태를 가질 때 유리하다.

군집의 개수를 사전에 지정할 필요가 없다는 점이 주요 장점이다. 알고리즘은 데이터의 밀도 분포를 기반으로 군집을 자연스럽게 발견하며, 대역폭 매개변수가 군집의 규모를 간접적으로 조절한다. 또한 잡음과 이상치에 비교적 강건한 편이다. 밀도가 낮은 지역의 데이터 포인트는 큰 군집으로 수렴하지 않거나, 독립적인 군집으로 형성되지 않아 효과적으로 걸러내는 경우가 많다.

수렴이 보장되는 이론적 토대를 가지고 있으며, 국소 밀도 최댓값을 향해 반복적으로 이동하는 과정을 통해 안정적인 결과를 제공한다. 구현이 직관적이고, 다양한 커널 함수를 적용할 수 있어 유연성이 높다.

평균 이동 군집화는 커널 밀도 추정에 기반한 방법으로, 데이터의 밀도 분포를 따라 군집을 형성한다는 장점이 있지만 몇 가지 명확한 단점을 지닌다.

가장 큰 단점은 대역폭 매개변수 선택에 결과가 매우 민감하다는 점이다. 대역폭이 너무 작으면 각 데이터 포인트가 개별적인 군집으로 수렴하여 과도하게 세분화된 결과를 초래한다. 반대로 대역폭이 너무 크면 서로 다른 군집들이 하나로 병합되어 중요한 구조를 놓칠 수 있다. 최적의 대역폭을 사전에 알기 어렵기 때문에, 이는 사용상의 주요 난제로 작용한다. 또한 알고리즘의 계산 복잡도가 높은 편이다. 각 반복에서 모든 데이터 포인트 또는 많은 후보점에 대해 커널 함수를 평가해야 하며, 수렴까지 많은 반복이 필요할 수 있어 대규모 데이터셋에는 비효율적이다.

알고리즘은 군집의 개수를 자동으로 결정한다는 장점이 있지만, 이는 동시에 단점이 될 수도 있다. 사용자가 원하는 군집 수를 사전에 지정할 수 없으며, 결과는 전적으로 데이터의 밀도 분포와 선택한 매개변수에 의존한다. 따라서 사전 지식이나 특정 개수의 군집이 필요한 응용 분야에는 적합하지 않을 수 있다. 마지막으로, 알고리즘은 일반적으로 구형 또는 타원형의 밀도 봉우리를 가정하는 커널을 사용하기 때문에, 매우 불규칙한 형태나 얽혀 있는 형태의 군집을 잘 포착하지 못할 수 있다.

대역폭은 평균 이동 군집화의 성능을 결정하는 가장 중요한 매개변수이다. 대역폭이 너무 작으면 데이터의 국부적 변동에 과도하게 민감해져 군집의 수가 불필요하게 많아지고, 너무 크면 중요한 세부 구조를 잃어버려 군집 수가 지나치게 적어질 수 있다[3]. 따라서 적절한 대역폭을 선택하는 것은 군집화 결과의 질을 보장하는 핵심 과제이다.

대역폭 선택을 위한 일반적인 방법은 다음과 같다.

실제 응용에서는 데이터의 규모와 복잡도, 계산 자원, 요구되는 정확도에 따라 방법을 선택한다. 많은 경우, 규칙 기반 방법으로 초기 값을 설정한 후, 경험적 시행착오를 통해 미세 조정하는 하이브리드 접근법이 사용된다. 또한, 데이터 공간의 특성에 따라 대역폭을 가변적으로 설정하는 적응형 평균 이동 알고리즘도 연구되었다.

평균 이동 군집화에서 커널 함수는 각 데이터 포인트의 영향력을 결정하는 핵심 요소이다. 일반적으로 사용되는 커널은 가우시안 커널, 에파네치니코프 커널, 균일 커널 등이 있다. 이들 커널은 모두 방사 대칭 커널의 특성을 가지며, 데이터 포인트로부터의 거리에 따라 가중치를 부여한다.

커널 선택은 알고리즘의 성능과 결과에 직접적인 영향을 미친다. 가우시안 커널은 모든 거리에 대해 0이 아닌 가중치를 부여하여 부드러운 밀도 추정을 가능하게 하지만, 계산 비용이 상대적으로 높다. 에파네치니코프 커널은 특정 대역폭 내의 점에만 균일한 가중치를 주고 그 외에는 0을 주어 계산 효율이 좋지만, 추정된 밀도 함수가 미분 불가능한 지점을 가질 수 있다. 균일 커널은 가장 단순한 형태이나, 실제로는 자주 사용되지 않는다.

이론적으로, 커널 함수의 정확한 형태보다 대역폭 매개변수의 값이 결과에 훨씬 더 큰 영향을 미치는 것으로 알려져 있다[4]. 따라서 많은 실무 응용에서는 계산 효율이 좋은 에파네치니코프 커널이 선호되는 경향이 있다. 최종 군집화 결과는 선택한 커널에 관계없이 유사한 패턴을 보이는 경우가 많지만, 수렴 속도와 계산 복잡도에는 차이가 발생한다.

평균 이동 군집화는 컴퓨터 비전 및 영상 처리 분야에서 널리 활용되는 군집화 기법이다. 특히 데이터의 형태나 군집 수에 사전 정보가 필요하지 않으며, 이미지 분할과 객체 추적 같은 작업에 효과적이다.

이 기법의 대표적인 응용은 이미지 분할이다. 색상 공간에서 각 픽셀의 색상값(예: RGB, L*a*b*)과 공간 좌표(x, y)를 결합한 5차원 특징 벡터를 구성하여 평균 이동 알고리즘을 적용한다. 알고리즘은 유사한 색상과 공간적으로 인접한 픽셀들을 동일한 군집으로 수렴시켜, 이미지를 의미 있는 영역으로 분할한다. 이는 잡음에 강건하며, 군집의 개수를 자동으로 결정한다는 장점이 있다.

또 다른 주요 응용 분야는 객체 추적이다. 비디오 시퀀스에서 추적하고자 하는 대상의 색상 히스토그램을 목표 모델로 정의하고, 이후 프레임에서 평균 이동 절차를 반복하여 목표 모델과 가장 유사한 영역을 찾아낸다. 이 방법은 계산 효율성이 높아 실시간 추적에 적합하며, 대상의 부분적 가림이나 형태 변화에 어느 정도 강인성을 보인다. 이 외에도 영상 필터링이나 특징점 군집화 등의 작업에도 사용된다.

평균 이동 군집화는 데이터 마이닝 분야에서 군집 분석을 수행하는 데 널리 활용되는 비모수적 방법이다. 데이터 마이닝의 핵심 목표 중 하나는 대용량 데이터셋에서 의미 있는 패턴, 구조 또는 군집을 발견하는 것이며, 평균 이동 알고리즘은 데이터 공간에서 확률 밀도 함수의 정점을 찾아 군집 중심을 자동으로 식별한다는 점에서 이 목표에 부합한다.

이 기법은 사전에 군집의 개수를 지정할 필요가 없으며, 임의의 모양을 가진 군집을 탐지할 수 있다는 장점을 지닌다. 이는 K-평균 군집화와 같은 다른 방법이 가지는 제약을 극복하게 해준다. 데이터 마이닝 작업에서 데이터의 분포에 대한 사전 지식이 부족한 경우가 많으므로, 이러한 유연성은 매우 유용하다. 평균 이동은 이상치에 비교적 강건하게 동작하며, 노이즈가 포함된 실세계 데이터를 분석하는 데 적합하다.

주요 응용 사례로는 고객 세분화, 이상 거래 탐지, 문서 군집화 등이 있다. 예를 들어, 고객 데이터에서 유사한 구매 패턴이나 인구통계학적 특성을 가진 그룹을 발견하여 시장 세분화를 수행할 수 있다. 알고리즘이 데이터의 밀도가 높은 지역으로 점을 이동시켜 군집을 형성하기 때문에, 결과 군집은 종종 데이터의 자연스러운 그룹핑을 반영한다.

그러나 대규모 데이터셋에 적용할 경우 계산 비용이 높을 수 있으며, 대역폭 매개변수 선택이 결과에 미치는 영향이 크다는 점은 데이터 마이닝 작업에서 고려해야 할 제약 사항이다.

평균 이동 군집화와 K-평균 군집화는 모두 데이터 포인트를 그룹으로 묶는 대표적인 군집화 알고리즘이지만, 접근 방식과 특징에서 뚜렷한 차이를 보인다.

K-평균 군집화는 사전에 사용자가 지정한 K개의 군집 중심을 초기화하고, 각 데이터 포인트를 가장 가까운 중심에 할당한 후, 할당된 포인트들의 평균으로 중심을 업데이트하는 과정을 반복한다. 이 알고리즘은 군집의 모양이 구형(Spherical)이고 크기가 비슷할 때 잘 동작하며, 계산 효율이 매우 높다는 장점이 있다. 그러나 군집의 개수 K를 미리 지정해야 하며, 초기 중심의 위치에 따라 결과가 크게 달라질 수 있다는 단점이 있다.

반면, 평균 이동 군집화는 사전에 군집의 개수를 지정할 필요가 없다. 대신 대역폭이라는 매개변수를 사용하여 데이터 공간 내의 확률 밀도 함수를 추정하고, 밀도가 가장 높은 방향으로 점을 이동시켜 최종적으로 수렴하는 지점을 군집 중심으로 삼는다. 이 방법은 군집의 모양과 크기에 제약을 두지 않으며, 이상치에 덜 민감한 특징을 가진다. 하지만 대역폭 선택이 결과에 미치는 영향이 크고, 일반적으로 K-평균보다 계산 비용이 높다.

다음 표는 두 알고리즘의 주요 차이점을 요약한다.

결론적으로, K-평균은 빠르고 직관적이며 군집 구조가 명확할 때, 평균 이동은 군집의 개수를 모르거나 형태가 복잡할 때 유리한 알고리즘이다.

DBSCAN (Density-Based Spatial Clustering of Applications with Noise)은 밀도 기반 군집화 알고리즘의 대표적인 예시이다. 이 알고리즘은 데이터 공간에서 데이터 포인트가 조밀하게 모여 있는 영역을 군집으로 식별하며, 밀도가 낮은 영역의 포인트들은 잡음으로 간주한다. 평균 이동 군집화와 마찬가지로 사전에 군집의 개수를 지정할 필요가 없다는 공통점을 지닌다.

두 알고리즘의 근본적인 차이는 군집을 정의하는 방식에 있다. 평균 이동은 확률 밀도 함수의 정점을 찾아 군집 중심을 결정하는 반면, DBSCAN은 사용자가 정의한 반경(ε)과 최소 포인트 수(MinPts)를 기준으로 직접적인 밀도 연결성을 통해 군집을 형성한다. DBSCAN의 핵심 개념은 핵심점, 경계점, 잡음점으로 분류하는 것이다. 주변 반경 ε 내에 MinPts 개 이상의 이웃을 가진 점은 핵심점이 되며, 핵심점들끼리 서로 도달 가능할 때 하나의 군집을 구성한다.

DBSCAN의 주요 장단점은 다음과 같이 정리할 수 있다.

결론적으로, DBSCAN은 데이터의 밀도 분포가 비교적 균일하고 군집의 형태가 복잡할 때, 그리고 잡음 포인트를 명시적으로 구분하고자 할 때 유용하게 적용된다. 반면, 평균 이동은 데이터의 확률 밀도 분포 자체를 추정하고 그 정점을 찾는 데 더 초점을 맞추는 알고리즘이다.