function X = kmeans(A, S, M)
%Input:	- Datenpunkte als Zeilen in Matrix A, 
%	- Clusterpunkte als Zeilen in Matrix S,
% 	- Anzahl der Durchlaeufe M des Algorithmus
%Output: Matrix X, in der jeder Datenpunkt durch den 
% 	 naechstgelegenen Clusterpunkt ersetzt wurde

N=size(A,1);		%Def. Anzahl der Datenpunkte
X=zeros(size(A));	%Def. Outputmatrix

for m=1:M		%Durchlaufschleife des Algorithmus
    
    K=size(S,1);	%Def. Anzahl Clusterpunkte
    D=zeros(N,K); 	%Def. einer ``Distanzmatrix''
    L=zeros(N,1);	%Def. eines ``Labelvektors''
    Z=zeros(N,1);	%Def. eines Hilfsvektors

    %Clustering
    for i=1:N	% Bestimme naechstgelegenen 
    		% Clusterpunkt zum i-ten Datenpunkt
        for k=1:K 	% Bestimme Distanz vom i-ten Datenpunkt
        		% zum k-ten Clusterpunkt
            D(i,k)=norm(A(i,:)-S(k,:));
        end
        [Z(i) L(i)]=min(D(i,:)); % Setze L(i) als den Index des
        		% Abstands-minimierenden Clusterpunkts
    end   
    
    % Berechnung der neuen Clusterpunkte
    S=zeros(size(S));	% Loesche alte Clusterpunkte
    n=zeros(K,1);	% Def. ``Zaehlvektor''
    
    for i=1:N % Summiere alle Datenpunkte mit gleichem Label
        l=L(i); % Def. Label des i-ten Datenpunktes
        S(l,:)=S(l,:)+A(i,:);
        n(l)=n(l)+1; % Erhoehe Zaehler zum l-ten Label
    end

    for k=1:K % Teile die Summen durch die Anzahl der Summanden
        S(k,:)=1/n(k)*S(k,:);    
    end    
    
end    
    
    for i=1:N	% Def. i-te Zeile der Outputmatrix durch den zum
    		% i-ten Datenpunkt naechstliegenden Clusterpunkt
   	l=L(i);
    	X(i,:)=S(l,:);
    end 
    
end


