dominantsetclustering.m

一种 较新的聚类算法 Dominant-set 的代码

function [N, L, u, fu] = dominantSetClustering(AMofCM_One)
  % this program is used after the similarity matrix is computed
  % when computing the similarity matrix, make sure (i,i) elements of the
  % similarity matrix is equal to 0
  
  % the similarity matrix is stored in a matrix called AMofCM_One 
  % and the matrix is saved in a .mat file called AMofCM_One.mat
 
    %the .mat file path
    % simfilename = '.\AMofCM_One.mat';
    % load(simfilename);
    sampleNum = size(AMofCM_One,1); % the number of the samples
     
    sampleUnclustered = sampleNum; % the number of unclustered samples
    clusterNum = 0;                % the number of formed clusters
    
    % set the number of free samples and max number of clusters,
    % you can reset it
    freesampleNum = 0.001 * sampleNum;

    %the max number of samples,you can reset it
    clusterMaxNum = 52;

    %when get a dominant,three below parameters effects the performance
    %of the dominant-set  clustering greatly
    %you can ajust them 
    epsilong = 1e-6; % judge when x converges
    iterMaxNum = 1000;% the max number of iteration 
    delta = 1e-7; %judge whether greater than zero
    
    %the cluster label for every sample. if the label is -1, the sample is
    %unclustered
    clusterLabel = -1 *ones(sampleNum,1);
    
    %the index of sample unclustered
    sampleLabel = 1:sampleNum;
    
    %begin clustering
    while (1)
        
        % when there are few sample,you can stop the clustering process
        if (sampleUnclustered <= freesampleNum)
            break;
        end
        
        % or when the cluster number are reached a prior value, the process
        % can be stopped
        
        if(clusterNum >= clusterMaxNum )
            break;
        end
        
        %begin to get a dominant set of the graph
        
        %initize x by random or barycenter 
        x = rand(sampleUnclustered,1);
        x = x/sum(x);
        %initialize x with the barycenter
        % x=1/sampleUnclustered *ones(sampleUnclustered,1);
        %
        fxold=0;
        %use replicator equation to solve the quadaric problem
        for i = 1:iterMaxNum
            xtemp = x.*(AMofCM_One*x);
            fx = sum(xtemp);
            xtemp = xtemp/fx;
            dif = x-xtemp;
            
            x = xtemp;
            fxold = fx;
            % if (dif'*dif < epsilong* sampleUnclustered)
            if (dif'*dif < epsilong)
                break;
            end
%             fprintf(fid,'%d %1.7f \n',i,fxold);    
        end
%         fprintf(fid,'%s','create a new cluster!');
%        fclose(fid);
      
        %get dominant set
        DominantSet = find(x > delta);
        lengthDominantSet = length(DominantSet);
        clusterNum = clusterNum +1;
        
        for i = 1:lengthDominantSet
            index = DominantSet(i);
            sampleindex = sampleLabel(index);
            clusterLabel(sampleindex) = clusterNum;
        end
        
        u{clusterNum} = x(DominantSet);
        fu(clusterNum) = fx;
        
        fprintf('\n %s %d %s %d','the ',clusterNum,'cluster has the number of samples: ',lengthDominantSet);
        
        %update  similarity matrix
        other = find( x<= delta); 
        
        sampleUnclustered = length(other);
        sampleLabel = sampleLabel(other);
        AMofCM_One = AMofCM_One(other,other);   
    end
    %{
    % output the clustering result
     resultfile = '.\result.m';
     fid = fopen(resultfile,'w');
     for i=1: clusterNum
        fprintf(fid,'%s %d %s\n','the ',i,'cluster has samples:'); 
         for j=1:sampleNum
             if  clusterLabel(j) == i
                 fprintf(fid,'%d ',j);
             end
         end
         fprintf(fid,'\n');
     end
     
     fprintf(fid,'%s\n','the unclustered samples are: ');
     for j=1:sampleNum
             if  clusterLabel(j) == -1
                 fprintf(fid,'%d ',j);
             end
     end
     
     fclose(fid);
    %}
    N = clusterNum;
    L = clusterLabel;