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