April 6, 2010

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 pmRSS feed for comments on this post. TrackBack URL

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**

Nice. Very similar to the JS code I wrote. Maybe tomorrow I’ll get it working with multiple dimensions. I think it’s pretty much just the distance measure that needs updating to make that change.

Comment by Howard Yeend — April 6, 2010 @ 11:27 pm