eşit elemanlarla kümeleme

Question

Bir dizi gözlemimiz olduğunu varsayalım: $\mathbf{X} = \{x_{1}, \dots, x_{n}\}\subseteq \mathbb{R}^{d}$, kapsamak $n$ sabit bir boyutluluk için gözlemler $d$. Varsayalım, sabit bir tamsayımız var$k$. K-ortalamalı kümeleme (l2 mesafesi ile), kümelerin merkez noktalarını bulma sorunudur$S_{1}, \dots, S_{k}$ küçültmek $$ cost(S_{1}, \dots, S_{1}) = \sum_{j=1}^{k}\sum_{x\in S_{j}}||x - q_{j}||^{2}, $$ nerede $q_{1}, \dots, q_{k} \in \mathbb{R}^{d}$ centroidler, yani $q_{j} = \frac{1}{|S_{j}|}\sum_{x\in S_{j}}x$.

Varsayalım, orada $\mathbf{X} = \{x_{1}, \dots, x_{n}\}$ eşit unsurlar var $\{x\} \subset \mathbf{X}$.

Küresel (teorik) bir çözümde bunların birbirine eşit olması mümkün mü? $\{x\}$ farklı kümelere mi ait?

Answer 1

Öncelikle, küresel olarak en uygun k-ortalama çözümü ile k-ortalamalı bir algoritmadan aldığınız sonucu ayırt etmemiz gerekir. Etrafta bunlardan epeyce var ve veri kümesi çok küçük olmadığı sürece, mutlaka küresel olmayan yerel bir optimum sağlayacaklar. (Sorunuzda "küresel" diyorsunuz, bu yüzden küresel olarak en uygun çözümü kastettiğinizi varsayıyorum; sadece emin olmak için.)

Sorunuzun cevabı "normal değil" ile başlıyor; onların$\|x-q_j\|$-değerler açıkça herkes için eşittir $q_j$, yani algoritma yakınsandığında (veya küresel olarak optimum $q_j$ biliniyor), hepsi en yakınlarına atanacak $q_j$, bu hepsi için aynı.

Yukarıdaki argüman tarafından kapsanmayan istisnai bir durum, yalnızca birkaç $x$ eşittir, ancak aynı zamanda iki veya daha fazla $q_j$. Aslında bu durumda onları farklı kümelere atayabilecek herhangi bir algoritma bilmiyorum, ancak bu tür uygulamaların var olduğunu dışlayamam.

Aslında bunu kanıtlamaya çalışmadım, ancak küresel optimumun asla eşit gözlemleri ayırmayacağından şüpheleniyorum, çünkü muhtemelen eşit gözlemler ayrılırsa, hepsini çoğunluğa sahip kümeye koyarak daha iyi bir çözüm elde edilebilir. bunlardan (veya eşit olarak dağıtılmışlarsa herhangi bir küme). Bu gözlemlerin birden fazla küme ortalamasını etkilemesi mantıklı görünmüyor (bu kümedeki diğer gözlemlerin çoğu için potansiyel olarak daha kötü hale getiriyor). Bir öğleden sonrayı matematik yaparak geçirdiğimizi muhtemelen ispatlayabiliriz, ama burada garanti yok, sadece bir tahmin.

Baktığım şey, 1,2,3,3,4,5 gibi verilerin iki yarısı arasında duran eşit noktaları olan bir dizi 1-d örneklerdir. Gerçekten de daha iyi bir çözüm elde edersiniz ($k=2$) maliyet açısından, eğer iki 3'ü biri sola ve diğeri sağa değil, hem 1,2 hem de 4,5 ile bir kümeye koyarsanız (bunu, maliyet fonksiyonlarını açıkça hesaplayarak kontrol edebilirsiniz) .