Technical Appendix: ECM Implementation

The following version of an ecm algorithm implementation with scilab has been done by Miguel Ayala and Gerd Doeben-Henisch.

 //Some common constants

//Conversion of radiants into grade

grad=(2*%pi)/360

//Conversion of radiants into degrees

igrad=360/(2*%pi)

INP = [1 2; 1 3; 2 2; 2 3; 4 4; 4 5; 5 4; 5 5; 6 1; 6 2; 7 1; 7 2]
INP2 = [3 3; 5 3; 3 5; 5 5; 6 9; 8 9; 8 11; 10 9; 11 4; 12 3; 12 6; 14 2; 14 7; 15 6; 16 4]

//************************************************************
// Normalize the input 2D-Input-Vektors
// Take INP as input and generate INP2 as output

function [INP2]=doNorm(INP)
  
  [r,c] = size(INP)
  INP2=[]
  printf('Length of Input Vector: %d\n',r)
  
  //Looping through the input
  for i=1:r
  v=[INP(i,1) INP(i,2)]
  printf('OLD coordinates: %d %d\n',v(1),v(2))
  printf('NORM of vector: %f\n',norm(v))
  
  v=v/norm(v)
  
  printf('NEW coordinates: %f %f\n',v(1),v(2))
  INP2(i,1)=v(1)
  INP2(i,2)=v(2)
  end
  
endfunction
//************************************************************
// Normalize the input 2D-Input-Vektors with a UNIFORM norm
// Take INP as input and generate INP3 as output

function [INP3]=doNormU(INP)
  
  [r,c] = size(INP)
  Maxnorm=0
  INP3=[]
  printf('Length of Input Vector: %d\n',r)
  
  //Looping through the input to find maximal norm
  for i=1:r
  v=[INP(i,1) INP(i,2)]
  
  if norm(v) > Maxnorm then Maxnorm=norm(v)
  printf('NORM of vector: %f %f\n',norm(v), Maxnorm)
  end
end


  //Looping through the input to normalize uniformly
  for i=1:r
  v=[INP(i,1) INP(i,2)]
  printf('OLD coordinates: %d %d\n',v(1),v(2))
  
  v=v/Maxnorm
  
  printf('NEW coordinates: %f %f\n',v(1),v(2))
  INP3(i,1)=v(1)
  INP3(i,2)=v(2)
  end
  
endfunction

//*******************************************************+
// Computes the euclidean distance between two vectors x,y

  function [d]=normEuclidean(x,y)

  lx=length(x), ly=length(y)
  if lx <> ly then error('SIZE of VECTORS DO NOT MATCH'),
  else
  s=0
  for i=1:lx
  s=s+abs(x(i)-y(i))^2, 
  end
  d=sqrt(s)/sqrt(lx)
  end

  endfunction	

function [d]=euclideanDistance(x,y)
  
  lx=length(x), ly=length(y)
  if lx <> ly then error('SIZE of VECTORS DO NOT MATCH'),
  else
    s=0
    for i=1:lx
    s=s+abs(x(i)-y(i))^2, 
  end
  d=sqrt(s/lx)
end
endfunction
function [d]=euclideanDistance2(x,y)
  
  lx=length(x), ly=length(y)
  if lx <> ly then error('SIZE of VECTORS DO NOT MATCH'),
  else
    s=0
    for i=1:lx
    s=s+abs(x(i)-y(i))^2, 
  end
  d=sqrt(s)
  end  
  endfunction

  function [piVektor]=kreisBerechnen()

  piVektor=[]
  for i=1:100
  piVektor(i,1)= ((2*%pi)/100)*i
  piVektor(i,2) = cos(pivek(i,1))
  piVektor(i,3) = sin(pivek(i,1))
end
  
endfunction
function kreisPlotten(inpu)
    [r1,c1] = size(inpu)
    pivek = kreisBerechnen()
    for i=1:r1
    plot2d(inpu(i,1)+(pivek(:,2)*inpu(i,3)),inpu(i,2)+(pivek(:,3)*inpu(i,3)), rect = [0 0 1 1])  
    end
endfunction


//***************************************************
//Evolving clusterin Method (ECM) (cf. Kasabov 2002)
//Takes the vectors x from an INPUT stream and maps these vectors into a set of categories CAT
//The vectors of the input stream are uniformly be normalized 
//using the function 'INP3=doNormU(INP)'


function[CAT]=ecm(INP)
  
  [r,c] = size(INP)
  CAT=[] //List of categories with (x,y) coordinates, radius Ra, and distance D
 
  //CAT is a cluster
  //generate first category
  threshold = 0.25 //threshold
  clusterIndex = 1
  CAT(clusterIndex,1) = INP(1,1)
  CAT(clusterIndex,2) = INP(1,2)
  CAT(clusterIndex,3) = 0 // radius
  printf('Länge des Vektors: %d\n',r)
  
  //Looping through the input
  for i=2:r
  printf('point %d\n',i)
  v=[INP(i,1) INP(i,2)]
  
  //Looping through the existing categories
  
  [r1,c1]=size(CAT)
  isInCluster = 0
  for j=1:r1
    w=[CAT(j,1) CAT(j,2)]
    CAT(j,4)=euclideanDistance2(v,w) // euclidean distance for further calculations
   end // end for
   [minDist,minDistIndex]=min(CAT(:,4)) 
printf('minDist %f minDistIndex %d\n',minDist,minDistIndex)
   if minDist < CAT(minDistIndex,3)
      printf('Point belongs to cluster %d\n',minDistIndex)
    else
      
    for j=1:r1
      CAT(j,5) = CAT(j,3) + CAT(j,4)//calculate the value of Cc + radius for each Cc and put it into the 5th pos of the CAT set
printf("%f\n",CAT(j,5))
    end //end for
    [minVal,minValIndex] = min(CAT(:,5)) //find the lowest Value
    printf('minVal: %f   Index: %d\n', minVal, minValIndex)
    if(minVal>(2*threshold)) //if lowest Value is greater than 2*threhold; add a cluster
      printf('weiter entfernt als zwei mal threshold, cluster addiert\n')
      clusterIndex = clusterIndex +1
        CAT(clusterIndex,1) = INP(i,1)
        CAT(clusterIndex,2) = INP(i,2)
        CAT(clusterIndex,3) = 0
        
    else //broaden radius and move cluster center
        
        CAT(minValIndex,3) = (minVal/2) // compute the new radius, lowest value / 2
        newCc = (CAT(minValIndex,4) - CAT(minValIndex,3)) / CAT(minValIndex,4) //we compute the distance of the new Cc from the old Cc with eucDis - newRadius and get the proportion
        newCcPoint(1) = INP(i,1) - CAT(minValIndex,1) // we compute the point - Cc
        newCcPoint(2) = INP(i,2) - CAT(minValIndex,2)
        //*****************************************************************
        newCcPoint(3) = newCcPoint(1)*newCc //we compute the to be shifted coordinates
        newCcPoint(4) = newCcPoint(2)*newCc
        //**********************************************
        CAT(minValIndex,1) = CAT(minValIndex,1)+newCcPoint(3)// we shift the center
        CAT(minValIndex,2) = CAT(minValIndex,2)+newCcPoint(4)// we shift the center        
        printf('Cc%d shifted\n',minValIndex)
    end //end if
    end //end if
      

end // end for
printf('Minimum Value of the CAT-SET: %f\n',min(CAT(:,5)))
 
endfunction

Having some input shaped as three patterns:

 
 INP2  =
 
    3.     3.   
    5.     3.   
    3.     5.   
    5.     5.   
    6.     9.   
    8.     9.   
    8.     11.  
    10.    9.   
    11.    4.   
    12.    3.   
    12.    6.   
    14.    2.   
    14.    7.   
    15.    6.   
    16.    4.

Figure 12.1: Three patterns as INP2 not normalized

Normalizing these values as follows:

-->INP3=doNormU(INP2)
  
INP3  =
 
    0.1819017    0.1819017  
    0.3031695    0.1819017  
    0.1819017    0.3031695  
    0.3031695    0.3031695  
    0.3638034    0.5457052  
    0.4850713    0.5457052  
    0.4850713    0.6669730  
    0.6063391    0.5457052  
    0.6669730    0.2425356  
    0.7276069    0.1819017  
    0.7276069    0.3638034  
    0.8488747    0.1212678  
    0.8488747    0.4244373  
    0.9095086    0.3638034  
    0.9701425    0.2425356

Figure 12.2: Three patterns as INP3 normalized

Putting these values into the ECM algorithm with two different thresholds thr=0.15 and thr=0.25 gives the following results:

Figure 12.3: Three normalized patterns classified by ecm with thr=0.15

Figure 12.4: Three normalized patterns classified by ecm with thr=0.2

If one replaces the distance measure within ECM y the modified function 'normEuclidean()' keeping the input data the same normalized vectors,

  function [d]=normEuclidean(x,y)

  lx=length(x), ly=length(y)
  s=0
  for i=1:lx
  s=s+abs(x(i)-y(i))^2, 
  end
  d=sqrt(s)/sqrt(lx)
  end

  endfunction

one gets the following results (cf. figure 12.5 and 12.6):

Figure 12.5: Three normalized patterns classified by ecm with thr=0.15 but the distance function normEuclidean within ECM

Figure 12.6: Three normalized patterns classified by ecm with thr=0.2 but the distance function normEuclidean within ECM