Having created a Javascript k-means function to process a single dimentional array I moved on to working out how to process a multi-dimentional array. The basic premise is the same, but you have to loop through the additional arrays and use a more advanced Euclidean n-space formula to calculate which cluster to allocate the point to.

Below is my k-means clustering learning machine algorithm.

function kmeans( arrayToProcess, centroids, clusters )
{	
	
	Groups=Array();
	iterations=0;
	
	function getType(o)
	{
		var _t;
		return ((_t = typeof(o)) == "object" ? o==null && "null" || Object.prototype.toString.call(o).slice(8,-1):_t).toLowerCase();
	}
	
	function deepCopy(target,source)
	{
		for(var p in source)
		{
			if(getType(source[p])=="array"||getType(source[p])=="object")
			{
				target[p]=getType(source[p])=="array"?[]:{};
				arguments.callee(target[p],source[p]);
			}
			else
			{
				target[p]=source[p];
			}
		}
	}						
	
	tempdistance=0;
	oldcentroids=[];
	deepCopy( oldcentroids, centroids );
	
	do
	{	

		for( reset=0; reset < clusters; reset++ )
		{

			Groups[reset]=Array();

		}
		
		changed=false;
		
		for( i=0; i < arrayToProcess.length; i++)
		{	  

			lowdistance=-1;
			lowclusters=0;	

			for( clustersloop=0; clustersloop < clusters; clustersloop++ )
			{	    

				dist=0;	  

				for( j=0;  j < arrayToProcess[i].length; j++ )
				{

					dist+=Math.pow( Math.abs( arrayToProcess[i][j] - centroids[clustersloop][j] ), 2 );

				}

				tempdistance=Math.sqrt( dist );

				if ( lowdistance==-1 )
				{

					lowdistance=tempdistance;
					lowclusters=clustersloop;

				}
				else if ( tempdistance <= lowdistance )
				{

					lowclusters=clustersloop;
					lowdistance=tempdistance;

				}

			}

			Groups[lowclusters].push( arrayToProcess[i].slice() );  

		}

		for( clustersloop=0; clustersloop < clusters; clustersloop++)
		{

			for( i=0, totalGroups=Groups[clustersloop].length; i < totalGroups; i++ )
			{

				for( j=0, totalGroupsSize=Groups[clustersloop][i].length; j < totalGroupsSize; j++ )
				{
				  
					centroids[clustersloop][j]+=Groups[clustersloop][i][j]

				}
					
			}

			for( i=0; i < centroids[clustersloop].length; i++ )
			{

				centroids[clustersloop][i]=( centroids[clustersloop][i]/Groups[clustersloop].length );

				if ( centroids[clustersloop][i]!=oldcentroids[clustersloop][i] )
				{

					changed=true;
					oldcentroids=[];
					deepCopy( oldcentroids, centroids );

				}

			}
		
		}
		
		iterations++;
		
	}
	while(changed==true);

	return Groups;
	
}

Download the script (right click and choose save target as)

Filed under: Mathematics,Programming — Tags: , , , , , , — admin @ 9:32 pm

After reading an article by Howard Yeend (Pure Mango) I decided I would try to write a version of the basic learn algorithm.

Below is what I came up with.

function kmeans( arrayToProcess, Clusters )
{

  var Groups = new Array();
  var Centroids = new Array();
  var oldCentroids = new Array();
  var changed = false;

  // initialise group arrays
  for( initGroups=0; initGroups < Clusters; initGroups++ )
  {

    Groups[initGroups] = new Array();

  }  

  // pick initial centroids

  initialCentroids=Math.round( arrayToProcess.length/(Clusters+1) );  

  for( i=0; i < Clusters; i++ )
  {

    Centroids[i]=arrayToProcess[ (initialCentroids*(i+1)) ];

  }

  do
  {

    for( j=0; j < Clusters; j++ )
	{

	  Groups[j] = [];

	}

    changed=false;

	for( i=0; i < arrayToProcess.length; i++ )
	{

	  Distance=-1;
	  oldDistance=-1

 	  for( j=0; j < Clusters; j++ )
	  {

        distance = Math.abs( Centroids[j]-arrayToProcess[i] );	

		if ( oldDistance==-1 )
		{

		   oldDistance = distance;
		   newGroup = j;

		}
		else if ( distance <= oldDistance )
		{

		    newGroup=j;
			oldDistance = distance;

		}

	  }	

	  Groups[newGroup].push( arrayToProcess[i] );	  

	}

    oldCentroids=Centroids;

    for ( j=0; j < Clusters; j++ )
	{

      total=0;
	  newCentroid=0;

	  for( i=0; i < Groups[j].length; i++ )
	  {

	    total+=Groups[j][i];

	  } 

	  newCentroid=total/Groups[newGroup].length;  

	  Centroids[j]=newCentroid;

	}

    for( j=0; j < Clusters; j++ )
	{

	  if ( Centroids[j]!=oldCentroids[j] )
	  {

	    changed=true;

	  }

	}

  }
  while( changed==true );

  return Groups;

}

Download the script (right click and choose save target as)

I’ve expanded the script now to support multiple dimensions, you can see my script here.

Filed under: Mathematics,Programming — Tags: , , , , , — admin @ 8:35 pm

About me

Jonathan Spicer

My CV

My curriculum vitae and a wealth of other facts about me.

Warhammer Quest tools

Flickering flame effect Flickering flame effect Flickering flame effect

Powered by WordPress