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 pmApril 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 pmHandy 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