Javascript Multi-Dimentional K-Means Algorithm

June 10, 2010

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)