等しい要素でのクラスタリング
一連の観測値があると仮定します。 $\mathbf{X} = \{x_{1}, \dots, x_{n}\}\subseteq \mathbb{R}^{d}$、含む $n$ 固定次元の観測 $d$。いくつかの固定整数があると仮定します$k$。k-meansクラスタリング（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-meansソリューションと、k-meansアルゴリズムから得られる結果を区別する必要があります。これらはかなりの数あり、データセットが非常に小さい場合を除いて、必ずしもグローバルなものではないローカルな最適値を提供します。（質問で「グローバル」と言っているので、念のため、グローバルに最適なソリューションを意味していると思います。）
あなたの質問への答えは「普通ではない」から始まります。彼らの$\|x-q_j\|$-値は明らかにすべてに等しい $q_j$、したがって、アルゴリズムが収束すると（またはグローバルに最適 $q_j$ 既知）、それらはすべて最も近いものに割り当てられます $q_j$、これはすべて同じです。
上記の議論でカバーされていない例外的な状況は、いくつかではない場合に発生します $x$ 等しいが、2つ以上と等距離にある $q_j$。この場合、それらを異なるクラスターに割り当てることができるアルゴリズムを実際には知りませんが、そのような実装が存在することを排除することはできません。
実際、私はそれを証明しようとはしていませんが、グローバル最適値が等しい観測値を分離することは決してないだろうと思います。等しい観測値が分離された場合、それらすべてを過半数を持つクラスターに入れることでより良い解決策を達成できる可能性があるからです。それらの（または、均等に分散されている場合は任意のクラスター）。これらの観測が複数のクラスター平均に影響を与えることは意味がないようです（そのクラスター内の他の観測の大部分にとっては潜在的に悪化します）。午後に数学をすることを証明できるかもしれませんが、ここでは保証はなく、推測にすぎません。
私が見たのは、1、2、3、3、4、5など、データの2つの半分の間に等しい点がある1次元の例の数です。確かにあなたはより良い解決策を得る（$k=2$）2つの3を、1つを左に1つを右にではなく、1,2または4,5のクラスターに配置した場合のコストの観点から（これは、コスト関数を明示的に計算することで確認できます） 。