동일한 요소로 클러스터링
일련의 관찰이 있다고 가정합니다. $\mathbf{X} = \{x_{1}, \dots, x_{n}\}\subseteq \mathbb{R}^{d}$, 포함 $n$ 고정 차원에 대한 관찰 $d$. 고정 된 정수가 있다고 가정합니다.$k$. k- 평균 군집화 (l2 거리)는 군집의 중심을 찾는 문제입니다.$S_{1}, \dots, S_{k}$ 최소화하는 $$ cost(S_{1}, \dots, S_{1}) = \sum_{j=1}^{k}\sum_{x\in S_{j}}||x - q_{j}||^{2}, $$ 어디 $q_{1}, \dots, q_{k} \in \mathbb{R}^{d}$ 중심입니다. 즉 $q_{j} = \frac{1}{|S_{j}|}\sum_{x\in S_{j}}x$.
거기에 $\mathbf{X} = \{x_{1}, \dots, x_{n}\}$ 같은 요소가있다 $\{x\} \subset \mathbf{X}$.
글로벌 (이론적) 솔루션에서 이들이 서로 같은 요소가 될 수 있습니까? $\{x\}$ 다른 클러스터에 속합니까?
답변
먼저 전역 적으로 최적 인 k- 평균 솔루션과 k- 평균 알고리즘에서 얻은 결과를 구별해야합니다. 주변에는 상당히 많은 수의 데이터가 있으며 데이터 세트가 매우 작지 않으면 반드시 글로벌 것이 아닌 로컬 최적을 제공합니다. (귀하의 질문에 "글로벌"이라고 말 했으므로 전 세계적으로 최적의 솔루션을 의미한다고 가정합니다. 확인하기 위해.)
귀하의 질문에 대한 답변은 "정상적이지 않음"으로 시작됩니다. 그들의$\|x-q_j\|$-값은 분명히 모두 동일합니다. $q_j$이므로 알고리즘이 수렴되면 (또는 전 세계적으로 최적의 $q_j$ 알려진), 그들은 모두 가장 가까운 $q_j$, 모두 동일합니다.
위의 주장에서 다루지 않는 예외적 인 상황은 $x$ 동일하지만 둘 이상의 거리에 있습니다. $q_j$. 이 경우 다른 클러스터에 할당 할 수있는 알고리즘은 실제로 알지 못하지만 그러한 구현이 존재한다는 것을 배제 할 수는 없습니다.
사실 나는 그것을 증명하려고 시도하지 않았지만 전역 최적이 동일한 관측치를 결코 분리하지 않을 것이라고 생각합니다. 왜냐하면 동일한 관측치가 분리되면 더 나은 솔루션을 얻을 수 있기 때문에 모든 관측치를 다수가있는 군집에 넣을 수 있기 때문입니다. (또는 균등하게 분산 된 경우 모든 클러스터). 이러한 obsrvations가 하나 이상의 군집 평균에 영향을주는 것은 이치에 맞지 않는 것 같습니다 (해당 군집의 다른 관측치 대부분에 대해 잠재적으로 더 나빠질 수 있음). 오후에 수학을하면서이 시간을 보낸다는 것을 증명할 수는 있겠지만 여기서는 보장 할 수 없습니다.
내가 살펴본 것은 1,2,3,3,4,5와 같은 데이터의 두 반쪽 사이에 동일한 점이있는 수많은 1-d 예제입니다. 실제로 더 나은 솔루션 ($k=2$) 두 개의 3을 모두 왼쪽과 오른쪽이 아닌 1,2 또는 4,5 클러스터에 넣으면 비용 측면에서 (비용 함수를 명시 적으로 계산하여 확인할 수 있습니다) .