chabb/README.md

## README.md

      
    Raw
  

              README.md
            
          
    k-Nearest-Neighbors

Based on this tutorial
k is randomly choosen at every iteration.

  
## index.html
  <!DOCTYPE html>
  <meta charset="utf-8">
  <title>Quadtree</title>
  <style>
  p {
   font-family: "Helvetica Neue", Helvetica, sans-serif;
   font-size: 60px;
   margin:0px;
  }
  </style>
  <body>
  <p id="K"></p>
  <script src="http://d3js.org/d3.v3.min.js"></script>
  <script>
  var width = 800;
  var height = 400;
  var padding = 40;

  console.log('Start..');
  var svg = d3.select("body").append("svg")
    .attr("width", width)
    .attr("height", height);
  console.log('=');
  /*
   * Expected keys in object:
   * rooms, area, type
   */
  var KNode = function(object) {
      for (var key in object)
      {
          this[key] = object[key];
      }
  };
  KNode.prototype.measureDistances = function(area_range_obj, rooms_range_obj) {
      var rooms_range = rooms_range_obj.max - rooms_range_obj.min;
      var area_range  = area_range_obj.max  - area_range_obj.min;

      for (var i in this.neighbors)
      {
          /* Just shortcut syntax */
          var neighbor = this.neighbors[i];

          var delta_rooms = neighbor.rooms - this.rooms;
          delta_rooms = (delta_rooms ) / rooms_range;

          var delta_area  = neighbor.area  - this.area;
          delta_area = (delta_area ) / area_range;

          neighbor.distance = Math.sqrt( delta_rooms*delta_rooms + delta_area*delta_area );
      }
  };
  KNode.prototype.sortByDistance = function() {
      this.neighbors.sort(function (a, b) {
          return a.distance - b.distance;
      });
  };
  KNode.prototype.guessType = function(k) {
      var types = {};

      for (var i in this.neighbors.slice(0, k))
      {
          var neighbor = this.neighbors[i];

          if ( ! types[neighbor.type] )
          {
              types[neighbor.type] = 0;
          }

          types[neighbor.type] += 1;
      }

      var guess = {type: false, count: 0};
      for (var type in types)
      {
          if (types[type] > guess.count)
          {
              guess.type = type;
              guess.count = types[type];
          }
      }

      this.guess = guess;

      return types;
  };


  var KNodeList = function(k) {
      this.nodes = [];
      this.k = k;
  };
  KNodeList.prototype.add = function(node) {
      this.nodes.push(node);
  };
  KNodeList.prototype.determineUnknown = function() {

      this.calculateRanges();

      /*
       * Loop through our nodes and look for unknown types.
       */
      for (var i in this.nodes)
      {

          if ( ! this.nodes[i].type)
          {
              /*
               * If the node is an unknown type, clone the nodes list and then measure distances.
               */

              /* Clone nodes */
              this.nodes[i].neighbors = [];
              for (var j in this.nodes)
              {
                  if ( ! this.nodes[j].type)
                      continue;
                  this.nodes[i].neighbors.push( new KNode(this.nodes[j]) );
              }

              /* Measure distances */
              this.nodes[i].measureDistances(this.areas, this.rooms);

              /* Sort by distance */
              this.nodes[i].sortByDistance();

              /* Guess type */
              console.log(this.nodes[i].guessType(this.k));

          }
      }
  };
  KNodeList.prototype.calculateRanges = function() {
      this.areas = {min: 1000000, max: 0};
      this.rooms = {min: 1000000, max: 0};
      for (var i in this.nodes)
      {
          if (this.nodes[i].rooms < this.rooms.min)
          {
              this.rooms.min = this.nodes[i].rooms;
          }

          if (this.nodes[i].rooms > this.rooms.max)
          {
              this.rooms.max = this.nodes[i].rooms;
          }

          if (this.nodes[i].area < this.areas.min)
          {
              this.areas.min = this.nodes[i].area;
          }

          if (this.nodes[i].area > this.areas.max)
          {
              this.areas.max = this.nodes[i].area;
          }
      }

  };
  function nodeColor(type) {
         switch (type)
          {
              case 'apartment':
                  return 'red';
                  break;
              case 'house':
                  return 'green';
                  break;
              case 'flat':
                  return  'blue';
                  break;
              default:
                  return '#666666';
          }
  }


  KNodeList.prototype.draw = function(canvas_id) {
      var width = 800;
      var height = 400;
      var padding = 40;
      var rooms_range = this.rooms.max - this.rooms.min;
      var areas_range = this.areas.max - this.areas.min;

      var x_shift_pct = (width  - padding) / width;
      var y_shift_pct = (height - padding) / height;
      var dataJoin = svg.selectAll(".nodes").data(this.nodes);
      var minroom = this.rooms.min;
      var areasmin = this.areas.min;
      var self = this;
      //console.log(dataJoin.enter(),this.nodes.length);
      dataJoin.enter().append("circle");
      dataJoin.transition()
        .attr("class","nodes")
        .attr("cx", function(d) {
          //console.log(d.rooms,minroom,rooms_range,width,x_shift_pct,padding);
          return  (d.rooms-minroom)* (width  / rooms_range) * x_shift_pct + (padding / 2)})
        .attr("cy", function(d) { y=  (d.area-areasmin)* (height / areas_range) * y_shift_pct + (padding / 2);
          return Math.abs(y-height);
        })
        .attr("r",5)
        .attr("fill",function(d){
          return nodeColor(d.type)
        });
      dataJoin.exit().remove()
      var unknown = this.nodes.filter(function(d,i){ return !d.type });
      //console.log("UNK",unknown);
      datajoin = svg.selectAll(".nodesUnkown").data(unknown);
      datajoin.enter().append("circle")
      datajoin.transition().attr("cx", function(d) {
          //console.log(d.rooms,minroom,rooms_range,width,x_shift_pct,padding);
          return  (d.rooms-minroom)* (width  / rooms_range) * x_shift_pct + (padding / 2)})
        .attr("cy", function(d) { y=  (d.area-areasmin)* (height / areas_range) * y_shift_pct + (padding / 2);
          return Math.abs(y-height);
        })
        .attr("r",function(d){
          var radius = d.neighbors[self.k - 1].distance * width;
            radius *= x_shift_pct;
          return radius;
        })
        .attr("fill",function(d) {
          return nodeColor(d.guess.type)
        })
        .attr("class","nodesUnkown")
        .attr("opacity","0.1");
       datajoin.exit().transition().attr("r",0).remove();
       var neighbor = unknown[0].neighbors.slice(0,this.k);
       dataJoin = svg.selectAll(".nodesNext").data(neighbor);

       dataJoin.enter().append("circle").attr("r",0);
       dataJoin.exit().transition().attr("r",0).remove();
       dataJoin.transition()
        .attr("class","nodesNext")
        .attr("cx", function(d) {
          //console.log(d.rooms,minroom,rooms_range,width,x_shift_pct,padding);
          return  (d.rooms-minroom)* (width  / rooms_range) * x_shift_pct + (padding / 2)})
        .attr("cy", function(d) { y=  (d.area-areasmin)* (height / areas_range) * y_shift_pct + (padding / 2);
          return Math.abs(y-height);
        })
        .attr("r",10)
        .attr("stroke",function(d){
          return nodeColor(d.type)
        }).attr("fill","transparent");


      return;
      for (var i in this.nodes)
      {
          ctx.save();

          switch (this.nodes[i].type)
          {
              case 'apartment':
                  ctx.fillStyle = 'red';
                  break;
              case 'house':
                  ctx.fillStyle = 'green';
                  break;
              case 'flat':
                  ctx.fillStyle = 'blue';
                  break;
              default:
                  ctx.fillStyle = '#666666';
          }

          var padding = 40;
          var x_shift_pct = (width  - padding) / width;
          var y_shift_pct = (height - padding) / height;

          var x = (this.nodes[i].rooms - this.rooms.min) * (width  / rooms_range) * x_shift_pct + (padding / 2);
          var y = (this.nodes[i].area  - this.areas.min) * (height / areas_range) * y_shift_pct + (padding / 2);
          y = Math.abs(y - height);


          ctx.translate(x, y);
          ctx.beginPath();
          ctx.arc(0, 0, 5, 0, Math.PI*2, true);
          ctx.fill();
          ctx.closePath();


          /*
           * Is this an unknown node? If so, draw the radius of influence
           */

          if ( ! this.nodes[i].type )
          {
              switch (this.nodes[i].guess.type)
              {
                  case 'apartment':
                      ctx.strokeStyle = 'red';
                      break;
                  case 'house':
                      ctx.strokeStyle = 'green';
                      break;
                  case 'flat':
                      ctx.strokeStyle = 'blue';
                      break;
                  default:
                      ctx.strokeStyle = '#666666';
              }

              var radius = this.nodes[i].neighbors[this.k - 1].distance * width;
              radius *= x_shift_pct;
              ctx.beginPath();
              ctx.arc(0, 0, radius, 0, Math.PI*2, true);
              ctx.stroke();
              ctx.closePath();

          }

          ctx.restore();

      }

  };


  var nodes;

  var data = [
      {rooms: 1, area: 350, type: 'apartment'},
      {rooms: 2, area: 300, type: 'apartment'},
      {rooms: 3, area: 300, type: 'apartment'},
      {rooms: 4, area: 250, type: 'apartment'},
      {rooms: 4, area: 500, type: 'apartment'},
      {rooms: 4, area: 400, type: 'apartment'},
      {rooms: 5, area: 450, type: 'apartment'},

      {rooms: 7,  area: 850,  type: 'house'},
      {rooms: 7,  area: 900,  type: 'house'},
      {rooms: 7,  area: 1200, type: 'house'},
      {rooms: 8,  area: 1500, type: 'house'},
      {rooms: 9,  area: 1300, type: 'house'},
      {rooms: 8,  area: 1240, type: 'house'},
      {rooms: 10, area: 1700, type: 'house'},
      {rooms: 9,  area: 1000, type: 'house'},

      {rooms: 1, area: 800,  type: 'flat'},
      {rooms: 3, area: 900,  type: 'flat'},
      {rooms: 2, area: 700,  type: 'flat'},
      {rooms: 1, area: 900,  type: 'flat'},
      {rooms: 2, area: 1150, type: 'flat'},
      {rooms: 1, area: 1000, type: 'flat'},
      {rooms: 2, area: 1200, type: 'flat'},
      {rooms: 1, area: 1300, type: 'flat'},
  ];
  var run = function() {
      var k = Math.floor(1+Math.random()*5);
      d3.select("p").html( " K : " + k);
      nodes = new KNodeList(k);
      for (var i in data)
      {
          nodes.add( new KNode(data[i]) );
      }
      var random_rooms = Math.round( Math.random() * 10 );
      var random_area = Math.round( Math.random() * 2000 );
      nodes.add( new KNode({rooms: random_rooms, area: random_area, type: false}) );

      nodes.determineUnknown();
      nodes.draw("canvas");
  };
  var width = 400;
  var height = 400;
  var padding = 40;


  setInterval(run, 1000);
  run();
  </script>
	<!DOCTYPE html>
	<meta charset="utf-8">
	<title>Quadtree</title>
	<style>
	p {
	font-family: "Helvetica Neue", Helvetica, sans-serif;
	font-size: 60px;
	margin:0px;
	}
	</style>
	<body>
	<p id="K"></p>
	<script src="http://d3js.org/d3.v3.min.js"></script>
	<script>
	var width = 800;
	var height = 400;
	var padding = 40;

	console.log('Start..');
	var svg = d3.select("body").append("svg")
	.attr("width", width)
	.attr("height", height);
	console.log('=');
	/*
	* Expected keys in object:
	* rooms, area, type
	*/
	var KNode = function(object) {
	for (var key in object)
	{
	this[key] = object[key];
	}
	};
	KNode.prototype.measureDistances = function(area_range_obj, rooms_range_obj) {
	var rooms_range = rooms_range_obj.max - rooms_range_obj.min;
	var area_range = area_range_obj.max - area_range_obj.min;

	for (var i in this.neighbors)
	{
	/* Just shortcut syntax */
	var neighbor = this.neighbors[i];

	var delta_rooms = neighbor.rooms - this.rooms;
	delta_rooms = (delta_rooms ) / rooms_range;

	var delta_area = neighbor.area - this.area;
	delta_area = (delta_area ) / area_range;

	neighbor.distance = Math.sqrt( delta_roomsdelta_rooms + delta_areadelta_area );
	}
	};
	KNode.prototype.sortByDistance = function() {
	this.neighbors.sort(function (a, b) {
	return a.distance - b.distance;
	});
	};
	KNode.prototype.guessType = function(k) {
	var types = {};

	for (var i in this.neighbors.slice(0, k))
	{
	var neighbor = this.neighbors[i];

	if ( ! types[neighbor.type] )
	{
	types[neighbor.type] = 0;
	}

	types[neighbor.type] += 1;
	}

	var guess = {type: false, count: 0};
	for (var type in types)
	{
	if (types[type] > guess.count)
	{
	guess.type = type;
	guess.count = types[type];
	}
	}

	this.guess = guess;

	return types;
	};



	var KNodeList = function(k) {
	this.nodes = [];
	this.k = k;
	};
	KNodeList.prototype.add = function(node) {
	this.nodes.push(node);
	};
	KNodeList.prototype.determineUnknown = function() {

	this.calculateRanges();

	/*
	* Loop through our nodes and look for unknown types.
	*/
	for (var i in this.nodes)
	{

	if ( ! this.nodes[i].type)
	{
	/*
	* If the node is an unknown type, clone the nodes list and then measure distances.
	*/

	/* Clone nodes */
	this.nodes[i].neighbors = [];
	for (var j in this.nodes)
	{
	if ( ! this.nodes[j].type)
	continue;
	this.nodes[i].neighbors.push( new KNode(this.nodes[j]) );
	}

	/* Measure distances */
	this.nodes[i].measureDistances(this.areas, this.rooms);

	/* Sort by distance */
	this.nodes[i].sortByDistance();

	/* Guess type */
	console.log(this.nodes[i].guessType(this.k));

	}
	}
	};
	KNodeList.prototype.calculateRanges = function() {
	this.areas = {min: 1000000, max: 0};
	this.rooms = {min: 1000000, max: 0};
	for (var i in this.nodes)
	{
	if (this.nodes[i].rooms < this.rooms.min)
	{
	this.rooms.min = this.nodes[i].rooms;
	}

	if (this.nodes[i].rooms > this.rooms.max)
	{
	this.rooms.max = this.nodes[i].rooms;
	}

	if (this.nodes[i].area < this.areas.min)
	{
	this.areas.min = this.nodes[i].area;
	}

	if (this.nodes[i].area > this.areas.max)
	{
	this.areas.max = this.nodes[i].area;
	}
	}

	};
	function nodeColor(type) {
	switch (type)
	{
	case 'apartment':
	return 'red';
	break;
	case 'house':
	return 'green';
	break;
	case 'flat':
	return 'blue';
	break;
	default:
	return '#666666';
	}
	}


	KNodeList.prototype.draw = function(canvas_id) {
	var width = 800;
	var height = 400;
	var padding = 40;
	var rooms_range = this.rooms.max - this.rooms.min;
	var areas_range = this.areas.max - this.areas.min;

	var x_shift_pct = (width - padding) / width;
	var y_shift_pct = (height - padding) / height;
	var dataJoin = svg.selectAll(".nodes").data(this.nodes);
	var minroom = this.rooms.min;
	var areasmin = this.areas.min;
	var self = this;
	//console.log(dataJoin.enter(),this.nodes.length);
	dataJoin.enter().append("circle");
	dataJoin.transition()
	.attr("class","nodes")
	.attr("cx", function(d) {
	//console.log(d.rooms,minroom,rooms_range,width,x_shift_pct,padding);
	return (d.rooms-minroom)* (width / rooms_range) * x_shift_pct + (padding / 2)})
	.attr("cy", function(d) { y= (d.area-areasmin)* (height / areas_range) * y_shift_pct + (padding / 2);
	return Math.abs(y-height);
	})
	.attr("r",5)
	.attr("fill",function(d){
	return nodeColor(d.type)
	});
	dataJoin.exit().remove()
	var unknown = this.nodes.filter(function(d,i){ return !d.type });
	//console.log("UNK",unknown);
	datajoin = svg.selectAll(".nodesUnkown").data(unknown);
	datajoin.enter().append("circle")
	datajoin.transition().attr("cx", function(d) {
	//console.log(d.rooms,minroom,rooms_range,width,x_shift_pct,padding);
	return (d.rooms-minroom)* (width / rooms_range) * x_shift_pct + (padding / 2)})
	.attr("cy", function(d) { y= (d.area-areasmin)* (height / areas_range) * y_shift_pct + (padding / 2);
	return Math.abs(y-height);
	})
	.attr("r",function(d){
	var radius = d.neighbors[self.k - 1].distance * width;
	radius *= x_shift_pct;
	return radius;
	})
	.attr("fill",function(d) {
	return nodeColor(d.guess.type)
	})
	.attr("class","nodesUnkown")
	.attr("opacity","0.1");
	datajoin.exit().transition().attr("r",0).remove();
	var neighbor = unknown[0].neighbors.slice(0,this.k);
	dataJoin = svg.selectAll(".nodesNext").data(neighbor);

	dataJoin.enter().append("circle").attr("r",0);
	dataJoin.exit().transition().attr("r",0).remove();
	dataJoin.transition()
	.attr("class","nodesNext")
	.attr("cx", function(d) {
	//console.log(d.rooms,minroom,rooms_range,width,x_shift_pct,padding);
	return (d.rooms-minroom)* (width / rooms_range) * x_shift_pct + (padding / 2)})
	.attr("cy", function(d) { y= (d.area-areasmin)* (height / areas_range) * y_shift_pct + (padding / 2);
	return Math.abs(y-height);
	})
	.attr("r",10)
	.attr("stroke",function(d){
	return nodeColor(d.type)
	}).attr("fill","transparent");




	return;
	for (var i in this.nodes)
	{
	ctx.save();

	switch (this.nodes[i].type)
	{
	case 'apartment':
	ctx.fillStyle = 'red';
	break;
	case 'house':
	ctx.fillStyle = 'green';
	break;
	case 'flat':
	ctx.fillStyle = 'blue';
	break;
	default:
	ctx.fillStyle = '#666666';
	}

	var padding = 40;
	var x_shift_pct = (width - padding) / width;
	var y_shift_pct = (height - padding) / height;

	var x = (this.nodes[i].rooms - this.rooms.min) * (width / rooms_range) * x_shift_pct + (padding / 2);
	var y = (this.nodes[i].area - this.areas.min) * (height / areas_range) * y_shift_pct + (padding / 2);
	y = Math.abs(y - height);


	ctx.translate(x, y);
	ctx.beginPath();
	ctx.arc(0, 0, 5, 0, Math.PI*2, true);
	ctx.fill();
	ctx.closePath();


	/*
	* Is this an unknown node? If so, draw the radius of influence
	*/

	if ( ! this.nodes[i].type )
	{
	switch (this.nodes[i].guess.type)
	{
	case 'apartment':
	ctx.strokeStyle = 'red';
	break;
	case 'house':
	ctx.strokeStyle = 'green';
	break;
	case 'flat':
	ctx.strokeStyle = 'blue';
	break;
	default:
	ctx.strokeStyle = '#666666';
	}

	var radius = this.nodes[i].neighbors[this.k - 1].distance * width;
	radius *= x_shift_pct;
	ctx.beginPath();
	ctx.arc(0, 0, radius, 0, Math.PI*2, true);
	ctx.stroke();
	ctx.closePath();

	}

	ctx.restore();

	}

	};



	var nodes;

	var data = [
	{rooms: 1, area: 350, type: 'apartment'},
	{rooms: 2, area: 300, type: 'apartment'},
	{rooms: 3, area: 300, type: 'apartment'},
	{rooms: 4, area: 250, type: 'apartment'},
	{rooms: 4, area: 500, type: 'apartment'},
	{rooms: 4, area: 400, type: 'apartment'},
	{rooms: 5, area: 450, type: 'apartment'},

	{rooms: 7, area: 850, type: 'house'},
	{rooms: 7, area: 900, type: 'house'},
	{rooms: 7, area: 1200, type: 'house'},
	{rooms: 8, area: 1500, type: 'house'},
	{rooms: 9, area: 1300, type: 'house'},
	{rooms: 8, area: 1240, type: 'house'},
	{rooms: 10, area: 1700, type: 'house'},
	{rooms: 9, area: 1000, type: 'house'},

	{rooms: 1, area: 800, type: 'flat'},
	{rooms: 3, area: 900, type: 'flat'},
	{rooms: 2, area: 700, type: 'flat'},
	{rooms: 1, area: 900, type: 'flat'},
	{rooms: 2, area: 1150, type: 'flat'},
	{rooms: 1, area: 1000, type: 'flat'},
	{rooms: 2, area: 1200, type: 'flat'},
	{rooms: 1, area: 1300, type: 'flat'},
	];
	var run = function() {
	var k = Math.floor(1+Math.random()*5);
	d3.select("p").html( " K : " + k);
	nodes = new KNodeList(k);
	for (var i in data)
	{
	nodes.add( new KNode(data[i]) );
	}
	var random_rooms = Math.round( Math.random() * 10 );
	var random_area = Math.round( Math.random() * 2000 );
	nodes.add( new KNode({rooms: random_rooms, area: random_area, type: false}) );

	nodes.determineUnknown();
	nodes.draw("canvas");
	};
	var width = 400;
	var height = 400;
	var padding = 40;




	setInterval(run, 1000);
	run();
	</script>