Meine Implementierung von k-means gibt verschiedene Ergebnisse

Question

Ich habe versucht, Lloyds Algorithmus zu implementieren und es schien gut, bis ich es mehrmals ausgeführt habe. Manchmal gibt es die Ergebnisse, die ich will, manchmal gibt es seltsame Zentren. Ich habe versucht, die Bedingung zu ändern, so dass es aufhört, wenn es konvergiert ist, aber es hilft nicht. Tut mir leid, dass ich keine Kommentare ins Englische übersetzt habe, ich hoffe, es ist klar genug.

Die einzige Zufälligkeit, die ich im Code habe, ist in der Situation, in der mein Cluster leert, also ersetze ich es durch einen zufälligen Punkt. Ich habe keine andere Idee was zu tun ist, wenn das passiert.

Ich kann das Problem nicht sehen. Können Sie mir eine Idee geben, was das Problem an den Ergebniszahlen sein könnte?

Dies ist mein Code: (A ist eine Matrix, deren Zeilen sind meine Punkte)

% initialization of centroids; further-first method 
n=size(A,1); 
dim=size(A,2); 
centri=zeros(k,dim); %matrix of centroids 
for i=1:n 
    centri(1,:)=centri(1,:)+A(i,:); 
end 
centri(1,:)=centri(1,:)/n; 
for j=2:k %u svakom koraku postavljamo za centar onu tocku koja je najdalje od centra 1,..j-1 
    maks=zeros(1,n); 
    %maks(i) je najveca udaljenost te tocke do centra =max d(x(i),c), c centri 
    for i=1:n 
     dist=zeros(1,j-1); 
     for l=1:j-1 
      dist(l)=norm(A(i,:)-centri(l,:)); 
     end 
     if(size(dist,2)==1) maks(i)=dist; 
     else 
      maks(i)=max(dist); 
     end 
     %maks(i)=0; 
     %for l=1:j-1 
      % if(maks(i)<dist(l)) maks(i)=dist(l); 
      % end 
     %end 
    end 
    [maksi, ind]=max(maks); 
    centri(j,:)=A(ind(1),:); 
end 

indeksi=zeros(1,n); 
for i=1:n 
    indeksi(i)=randi(k,1); 
end 
% u centrima je postavljena pocetna inicijalizacija 
br_iter=0; 
tic 

while br_iter<=1000 
    br_iter=br_iter+1; 

    for i=1:n 
     dist=zeros(1,k); % udaljenosti od tocke x do centra j 
     for j=1:k 
      dist(j)=norm(A(i,:)-centri(j,:)); 
     end 
     [mini, ind]=min(dist); % ind je vektor za koji se poprima minimalna vrijednost 
     indeksi(i)=ind(1); % uzmemo prvi po redu 
    end 
    % sad radimo nove centroide koji su aritmetička sredina svih vektora koji mu pripadaju 
    for j=1:k 
     centri(j,:)=zeros(1,dim); 
     brojac=0; 
     for i=1:n 
      if indeksi(i)==j 
       centri(j,:)=centri(j,:)+A(i,:); 
       brojac=brojac+1; 
      end 
     end 
     if brojac 
      centri(j,:)=centri(j,:)/brojac; 
     else 
      ind=randi(n, 1); 
      centri(j,:)=A(ind,:); 
     end 
    end 
end 
toc 
for i=1:n 
    plot(A(i,1), A(i,2), '.b'); 
    if(i==1) hold on; 
    end 
end 

for i=1:k 
    plot(centri(i,1), centri(i,2), '+r'); 
end 
hold off 

Answer 1

mit Zentren starten alle Null ist keine empfohlene Ansatz. Nach der ersten Iteration sind alle bis auf eines dieser Zentren leer. So hat Zufälligkeit hat einen Effekt auf Ihr Ergebnis.

Die Ergebnisse, die Sie anzeigen, sind typisch für k-means. Es kann nicht garantiert werden, das Optimum zu bevorzugen, aber es kann in einem "lokalen Optimum" hängen bleiben.

Also ich glaube nicht, dass ein Fehler in Ihrem Code ist. Nur die Startbedingung ist nicht sehr weise gewählt & Sie sind falsch zu erwarten, k-bedeutet, immer gute Ergebnisse zu geben.