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 )
{
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: clustering, javascript, k means, learning machine, mathematics, maths, multi-dimentional — admin @ 9:32 pm8 Comments »
RSS feed for comments on this post. TrackBack URL
Leave a comment
Warhammer Quest tools
Handy tools for creating the various cards the game uses, dungeon, magic, event and treasure
Create your own unexpected event cards
Create your own monster event cards
Powered by WordPress
Most cool, my friend!
Comment by Jim — December 24, 2011 @ 2:37 pm
can you post a complete example to show us how it works, or comment about what the input data you expected
Comment by horsley — June 4, 2013 @ 7:43 am
Hiya,
I’ve just been looking at the code and I was going to upload a method however I’ve found a bug and I want to fix it first.
Comment by admin — June 5, 2013 @ 9:32 pm
Yeah, I found a bug too.
I found that the amount of iterations always was one.
On the line 05, you want to save centroids to oldcentroids
but you simply use the assign statement.
In javascript, array won’t be copied by assign statement,
but they share the same address.
It’s means that when you calc the new centroids, you also overwrite the old_centroids
(You can trace that bro), so when you determine if centroids changed, it always be true.
The solution is copy the old centroids with other methods like Array.slice()
Sorry for my poor English
Comment by horsley — June 18, 2013 @ 4:14 am
Both slice, concat were not working to copy the value correctly.
Because that the multi dimention array in javascript is a one dimention array which items was a reference to the second dimention.
I found a solution.
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];
}
}
}
use deepCopy to save old_centroids
Comment by horsley — June 18, 2013 @ 5:34 am
I also found some problem with the distance calculate on line 33 and below
you are doing sqrt(abs(a^2 – b^2))
It should be sqrt((abs(a – b))^2)
Comment by horsley — June 18, 2013 @ 6:06 am
Is there a fully debugged version?
Comment by Jm — July 27, 2013 @ 1:45 am
Hello,
Alas I’ve been a little busy just recently and haven’t had a chance to fix it. Hopefully I’ll have to sometime tomorrow.
Comment by admin — July 28, 2013 @ 11:58 am