function [final_cluster,cluster_dist]=base_opti(training_bags,clustering,num_cluster,distance_matrix,initial_cluster_dist,out_mode)

% training_bags: the ith training bag is stored in training_bags{i,1}
% clustering: the current cluster result of training_bags, the indexes of the bags in the ith cluster is stored in clustering{i,1}
% num_cluster: the final number of clusters
% distance_matrix: the distance between the ith and jth bags is stored in distance_matrix(i,j)
% initial_cluster_dist: the initial distance between the ith and jth cluster is stored in initial_cluster_dist(i,j)
% out_mode: mode for measuring the distance between clusters: 1 for minimum Hausdorff; 2 for maximum Hausdorff; 3 for average distance
% final_cluster: the final result of clustering
% cluster_dist: the final distance between the ith and jth cluster is stored in cluster_dist(i,j) 

   final_cluster=clustering;
   cluster_dist=initial_cluster_dist; 
   tempsize=size(clustering);
   cur_num=tempsize(1);
   num_iter=cur_num-num_cluster;
   for i=1:num_iter
% find the indexes of the nearest clusters       
       [Y,I]=min(cluster_dist);
       [minimum,index2]=min(Y);
       index1=I(1,index2);       
       
%        minimum=min(min(cluster_dist));
%        index1=-1;
%        index2=-1;
%        min_set_size=10000;
%        [row,col]=size(cluster_dist);
%        for m=1:(row-1)
%            for n=(m+1):col
%                if(cluster_dist(m,n)==minimum)
%                    [temp,size1]=size(final_cluster{m,1});
%                    [temp,size2]=size(final_cluster{n,1});
%                    if((size1+size2)<min_set_size)
%                        min_set_size=size1+size2;
%                        index1=m;
%                        index2=n;
%                    end
%                end
%            end
%        end
       
% Update final_cluster      
       temp_cluster=cell(cur_num-1,1);
       for m=1:(index1-1)
           temp_cluster{m,1}=final_cluster{m,1};
       end
       temp_cluster{index1,1}=[final_cluster{index1,1},final_cluster{index2,1}];
       for m=(index1+1):(index2-1)
           temp_cluster{m,1}=final_cluster{m,1};
       end
       for m=index2:(cur_num-1)
           temp_cluster{m,1}=final_cluster{m+1,1};
       end
       final_cluster=temp_cluster;

% Update cluster_dist
       temp_cluster_dist=realmax*ones(cur_num-1,cur_num-1);       
       for m=1:(index1-1)
           for n=(m+1):(index1-1)
               temp_cluster_dist(m,n)=cluster_dist(m,n);
           end
           
           tempsize=size(final_cluster{m,1});
           num_bags1=tempsize(2);
           tempsize=size(final_cluster{index1,1});
           num_bags2=tempsize(2);
           temp_dist=zeros(num_bags1,num_bags2);
           for j=1:num_bags1
               for k=1:num_bags2
                   temp_dist(j,k)=distance_matrix(final_cluster{m,1}(1,j),final_cluster{index1,1}(1,k));
               end
           end
           if (out_mode==1)
               temp_cluster_dist(m,index1)=min(min(temp_dist));
           else
               if (out_mode==2)
                   dist1=max(min(temp_dist));
                   dist2=max(min(temp_dist'));
                   temp_cluster_dist(m,index1)=max(dist1,dist2);
               else
                   temp_cluster_dist(m,index1)=sum(sum(temp_dist))/(num_bags1*num_bags2);
               end
           end
           
           for n=(index1+1):(index2-1)
               temp_cluster_dist(m,n)=cluster_dist(m,n);
           end
           for n=index2:(cur_num-1)
               temp_cluster_dist(m,n)=cluster_dist(m,n+1);
           end
       end
       
       for n=(index1+1):(index2-1)
           tempsize=size(final_cluster{index1,1});
           num_bags1=tempsize(2);
           tempsize=size(final_cluster{n,1});
           num_bags2=tempsize(2);
           temp_dist=zeros(num_bags1,num_bags2);
           for j=1:num_bags1
               for k=1:num_bags2
                   temp_dist(j,k)=distance_matrix(temp_cluster{index1,1}(1,j),final_cluster{n,1}(1,k));
               end
           end
           if (out_mode==1)
               temp_cluster_dist(index1,n)=min(min(temp_dist));
           else
               if (out_mode==2)
                   dist1=max(min(temp_dist));
                   dist2=max(min(temp_dist'));
                   temp_cluster_dist(index1,n)=max(dist1,dist2);
               else
                   temp_cluster_dist(index1,n)=sum(sum(temp_dist))/(num_bags1*num_bags2);
               end
           end           
       end
       for n=index2:(cur_num-1)
           tempsize=size(final_cluster{index1,1});
           num_bags1=tempsize(2);
           tempsize=size(final_cluster{n,1});
           num_bags2=tempsize(2);
           temp_dist=zeros(num_bags1,num_bags2);
           for j=1:num_bags1
               for k=1:num_bags2
                   temp_dist(j,k)=distance_matrix(final_cluster{index1,1}(1,j),final_cluster{n,1}(1,k));
               end
           end
           if (out_mode==1)
               temp_cluster_dist(index1,n)=min(min(temp_dist));
           else
               if (out_mode==2)
                   dist1=max(min(temp_dist));
                   dist2=max(min(temp_dist'));
                   temp_cluster_dist(index1,n)=max(dist1,dist2);
               else
                   temp_cluster_dist(index1,n)=sum(sum(temp_dist))/(num_bags1*num_bags2);
               end
           end      
       end
       
       for m=(index1+1):(index2-1)
           for n=(m+1):(index2-1)
               temp_cluster_dist(m,n)=cluster_dist(m,n);
           end
           for n=index2:(cur_num-1)
               temp_cluster_dist(m,n)=cluster_dist(m,n+1);
           end
       end
       
       for m=index2:(cur_num-1)
           for n=(m+1):(cur_num-1)
               temp_cluster_dist(m,n)=cluster_dist(m+1,n+1);
           end
       end

       cluster_dist=temp_cluster_dist;

% Update cur_num       
       cur_num=cur_num-1;
   end
   
           