k-modes聚类算法1.rar

function [C,T]=hungarian(A) %HUNGARIAN Solve the Assignment problem using the Hungarian method. % %[C,T]=hungarian(A) %A - a square cost matrix. %C - the optimal assignment. %T - the cost of the optimal assignment. %s.t. T = trace(A(C,:)) is minimized over all possible assignments. % Adapted from the FORTRAN IV code in Carpaneto and Toth, "Algorithm 548: % Solution of the assignment problem [H]", ACM Transactions on % Mathematical Software, 6(1):104-111, 1980. % v1.0 96-06-14. Niclas Borlin, niclas@cs.umu.se. % Department of Computing Science, Ume?University, % Sweden. % All standard disclaimers apply. % A substantial effort was put into this code. If you use it for a % publication or otherwise, please include an acknowledgement or at least % notify me by email. /Niclas [m,n]=size(A); if (m~=n) error('HUNGARIAN: Cost matrix must be square!'); end % Save original cost matrix. orig=A; % Reduce matrix. A=hminired(A); % Do an initial assignment. [A,C,U]=hminiass(A); % Repeat while we have unassigned rows. while (U(n+1)) % Start with no path, no unchecked zeros, and no unexplored rows. LR=zeros(1,n); LC=zeros(1,n); CH=zeros(1,n); RH=[zeros(1,n) -1]; % No labelled columns. SLC=[]; % Start path in first unassigned row. r=U(n+1); % Mark row with end-of-path label. LR(r)=-1; % Insert row first in labelled row set. SLR=r; % Repeat until we manage to find an assignable zero. while (1) % If there are free zeros in row r if (A(r,n+1)~=0) % ...get column of first free zero. l=-A(r,n+1); % If there are more free zeros in row r and row r in not % yet marked as unexplored.. if (A(r,l)~=0 & RH(r)==0) % Insert row r first in unexplored list. RH(r)=RH(n+1); RH(n+1)=r; % Mark in which column the next unexplored zero in this row % is. CH(r)=-A(r,l); end else % If all rows are explored.. if (RH(n+1)<=0) % Reduce matrix. [A,CH,RH]=hmreduce(A,CH,RH,LC,LR,SLC,SLR); end % Re-start with first unexplored row. r=RH(n+1); % Get column of next free zero in row r. l=CH(r); % Advance "column of next free zero". CH(r)=-A(r,l); % If this zero is last in the list.. if (A(r,l)==0) % ...remove row r from unexplored list. RH(n+1)=RH(r); RH(r)=0; end end % While the column l is labelled, i.e. in path. while (LC(l)~=0) % If row r is explored.. if (RH(r)==0) % If all rows are explored.. if (RH(n+1)<=0) % Reduce cost matrix. [A,CH,RH]=hmreduce(A,CH,RH,LC,LR,SLC,SLR); end % Re-start with first unexplored row. r=RH(n+1); end % Get column of next free zero in row r. l=CH(r); % Advance "column of next free zero". CH(r)=-A(r,l); % If this zero is last in list.. if(A(r,l)==0) % ...remove row r from unexplored list. RH(n+1)=RH(r); RH(r)=0; end end % If the column found is unassigned.. if (C(l)==0) % Flip all zeros along the path in LR,LC. [A,C,U]=hmflip(A,C,LC,LR,U,l,r); % ...and exit to continue with next unassigned row. break; else % ...else add zero to path. % Label column l with row r. LC(l)=r; % Add l to the set of labelled columns. SLC=[SLC l]; % Continue with the row assigned to column l. r=C(l); % Label row r with column l. LR(r)=l; % Add r to the set of labelled rows. SLR=[SLR r]; end end end % Calculate the total cost. T=sum(orig(logical(sparse(C,1:size(orig,2),1)))); function A=hminired(A) %HMINIRED Initial reduction of cost matrix for the Hungarian method. % %B=assredin(A) %A - the unreduced cost matris. %B - the reduced cost matrix with linked zeros in each row. % v1.0 96-06-13. Niclas Borlin, niclas@cs.umu.se. [m,n]=size(A); % Subtract column-minimum values from each column. colMin=min(A); A=A-colMin(ones(n,1),:); % Subtract row-minimum values from each row. rowMin=min(A')'; A=A-rowMin(:,ones(1,n)); % Get positions of all zeros. [i,j]=find(A==0); % Extend A to give room for row zero list header column. A(1,n+1)=0; for k=1:n % Get all column in this row. cols=j(k==i)'; % Insert pointers in matrix. A(k,[n+1 cols])=[-cols 0]; end function [A,C,U]=hminiass(A) %HMINIASS Initial assignment of the Hungarian method. % %[B,C,U]=hminiass(A) %A - the reduced cost matrix. %B - the reduced cost matrix, with assigned zeros removed from lists. %C - a vector. C(J)=I means row I is assigned to column J, % i.e. there is an assigned zero in position I,J. %U - a vector with a linked list of unassigned rows. % v1.0 96-06-14. Niclas Borlin, niclas@cs.umu.se. [n,np1]=size(A); % Initalize return vectors. C=zeros(1,n); U=zeros(1,n+1); % Initialize last/next zero "pointers". LZ=zeros(1,n); NZ=zeros(1,n); for i=1:n % Set j to first unassigned zero in row i. lj=n+1; j=-A(i,lj); % Repeat until we have no more zeros (j==0) or we find a zero % in an unassigned column (c(j)==0). while (C(j)~=0) % Advance lj and j in zero list. lj=j; j=-A(i,lj); % Stop if we hit end of list. if (j==0) break; end end if (j~=0) % We found a zero in an unassigned column. % Assign row i to column j. C(j)=i; % Remove A(i,j) from unassigned zero list. A(i,lj)=A(i,j); % Update next/last unassigned zero pointers. NZ(i)=-A(i,j); LZ(i)=lj; % Indicate A(i,j) is an assigned zero. A(i,j)=0; else % We found no zero in an unassigned column. % Check all zeros in this row. lj=n+1; j=-A(i,lj); % Check all zeros in this row for a suitable zero in another row. while (j~=0) % Check the in the row assigned to this column. r=C(j); % Pick up last/next pointers. lm=LZ(r); m=NZ(r); % Check all unchecked zeros in free list of this row. while (m~=0) % Stop if we find an unassigned column. if (C(m)==0) break; end % Advance one step in list. lm=m; m=-A(r,lm); end if (m==0) % We failed on row r. Continue with next zero on row i. lj=j; j=-A(i,lj); else % We found a zero in an unassigned column. % Replace zero at (r,m) in unassigned list with zero at (r,j) A(r,lm)=-j; A(r,j)=A(r,m); % Update last/next pointers in row r. NZ(r)=-A(r,m); LZ(r)=j; % Mark A(r,m) as an assigned zero in the matrix . . . A(r,m)=0; % ...and in the assignment vector. C(m)=r; % Remove A(i,j) from unassigned list. A(i,lj)=A(i,j); % Update last/next pointers in row r. NZ(i)=-A(i,j); LZ(i)=lj; % Mark A(r,m) as an assigned zero in the matrix . . . A(i,j)=0; % ...and in the assignment vector. C(j)=i; % Stop search.