Comment fonctionne exactement k-means++ travail?
J'ai du mal à comprendre pleinement la k-means++ de l'algorithme. Je suis intéressé, exactement comment la première k centroïdes sont cueillis (le reste, c'est comme dans l'original k-means).
- Est la fonction de probabilité utilisée en fonction de la distance ou de Gauss?
- Dans le même temps, la plus longue distance du point (à partir de l'autre centroïdes) est choisi pour un nouveau centre de gravité.
Je vais apprécier une explication étape par étape, et un exemple. L'un dans Wikipédia n'est pas assez clair. Également très bien commenté le code source serait également aider. Si vous êtes à l'aide de 6 tableaux alors s'il vous plaît dites-nous qui est pour ce.
- Probablement un bon candidat pour stats.stackexchange.com
Vous devez vous connecter pour publier un commentaire.
Question intéressante. Merci d'apporter ce document à mon attention. PDF lien de l'article original.
En termes simples, les centres de cluster sont d'abord choisis au hasard à partir de l'ensemble d'entrée d'observation des vecteurs, où la probabilité de choisir le vecteur
x
est élevé six
n'est pas près de tout choisi précédemment centres.Ici est d'une dimension d'exemple. Nos observations sont [0, 1, 2, 3, 4]. Laissez-le premier centre,
c1
, être 0. La probabilité que la prochaine cluster centre,c2
, est x est proportionnelle à||c1-x||^2
. Donc, P(c2 = 1) = 1a, P(c2 = 2) = 4a, P(c2 = 3) = 9, P(c2 = 4) = 16a, où un = 1/(1+4+9+16).Supposons que c2=4. Alors, P(c3 = 1) = 1a, P(c3 = 2) = 4a, P(c3 = 3) = 1a, où un = 1/(1+4+1).
J'ai codé la procédure d'initialisation en Python, je ne sais pas si cela vous aide.
MODIFIER avec précision: La sortie de
cumsum
nous donne les limites à la partition de l'intervalle [0,1]. Ces partitions ont une longueur égale à la probabilité correspondant au point d'être choisi en tant que centre de. Alors, depuisr
est uniformément choisi entre [0,1], il va tomber dans exactement un de ces intervalles (en raison debreak
). Lefor
boucle de contrôle pour voir la partition quir
est en.Exemple:
Un Liner.
Dire que nous avons besoin de sélectionner 2 centres de cluster, au lieu de sélectionner tous au hasard{comme nous le faisons dans de simples k signifie}, nous allons sélectionner le premier un au hasard, puis de trouver les points qui sont les plus éloignés de la première center{Ces points, plus probablement, n'appartiennent pas à la première cluster centre comme ils sont loin de} et affecter la deuxième cluster centre à proximité de ces points éloignés.
J'ai préparé une source complète de la mise en œuvre des k-means++ basé sur le livre "l'Intelligence Collective" par Toby Segaran et le k-menas++ initialisation fournies ici.
En effet, il existe deux fonctions de distance ici. Pour la première centroïdes un standard est utilisé en fonction numpy.intérieure et puis pour les centroïdes de la fixation de l'Pearson est utilisé. Peut-être Pearson pour l'un peut être utilisé aussi pour la première centroïdes. Ils disent que c'est mieux.
data.txt: