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 )
{	

	tempdistance=0;
	oldcentoids=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.abs( Math.pow( arrayToProcess[i][j], 2 ) - Math.pow( 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; i < Groups[clustersloop].length; i++ )
		  {

			for( j=0; j < Groups[clustersloop][i].length; 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=centroids;

			}

		  }

		}

	}
	while(changed==true);

  return Groups;

}

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

Filed under: Mathematics,Programming — Tags: clustering, javascript, k means, learning machine, mathematics, maths, multi-dimentional — 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: algorithm, javascript, k means, learning, mathematics, maths — admin @ 8:35 pm