Calculating a Decision Boundary

This JavaScript program demonstrates how to calculate a decision boundary to minimize the entropy and maximize the information gain of a coordinate-wise linear boundary.

DecisionBoundary.html

<!DOCTYPE html>
<html>
  <head>
    <title>XoaX.net's Javascript</title>
    <script type="text/javascript" src="DecisionBoundary.js"></script>
  </head>
  <body onload="Initialize()">
    <canvas id="idCanvas" width="600" height ="600" style="background-color: #F0F0F0;"></canvas>
    <br />
    <label>Entropy: <span id="idEntropy"></span></label><br />
    <label>Split Entropy: <span id="idSplitEntropy"></span></label><br />
    <label>Information Gain: <span id="idInformationGain"></span></label>
  </body>
</html>

DecisionBoundary.js

// This is a collection of points in the region [0,1]x[0,1] representing two variable values.
// Additionally, each point has a classification as A or B with values 0 and 1, respectively.
class CDataPoint {
	#mdaValues = [0,0];
	#miClass;
	constructor() {
		// Create random Values
		this.#mdaValues[0] = Math.random();
		this.#mdaValues[1] = Math.random();
		this.#miClass = ((Math.random() < .5) ? 0 : 1);
	}
	get X() {
		return this.#mdaValues[0];
	}
	get Y() {
		return this.#mdaValues[1];
	}
	get Class() {
		return this.#miClass;
	}
}

class CDataSet {
	#mqaPoints;
	constructor(iSampleSize) {
		this.#mqaPoints = new Array(iSampleSize);
		for (let i = 0; i < iSampleSize; ++i) {
			this.#mqaPoints[i] = new CDataPoint();
		}
	}
	Graph(qContext) {
		let iWidth = qContext.canvas.width;
		let iHeight = qContext.canvas.height;
		for (let i = 0; i < this.#mqaPoints.length; ++i) {
			let qP = this.#mqaPoints[i];
			if (qP.Class == 0) {
				qContext.fillStyle = "red";
				qContext.beginPath();
				const kdRadius = 3;
				qContext.ellipse(qP.X*iWidth, qP.Y*iHeight, kdRadius, kdRadius, 0, 0, 2*Math.PI);
				qContext.fill();
			} else {
				qContext.fillStyle = "blue";
				qContext.beginPath();
				const kdSide = 6;
				qContext.rect(qP.X*iWidth - kdSide/2, qP.Y*iHeight - kdSide/2, kdSide, kdSide);
				qContext.fill();
			}
		}
	}
	Points() {
		return this.#mqaPoints;
	}
	P(i) {
		return this.#mqaPoints[i];
	}
	Entropy() {
		// Count the data points
		// Count number of each type
		let iClass0 = 0;
		let iClass1 = 0;
		for (let i = 0; i < this.#mqaPoints.length; ++i) {
			let qP = this.#mqaPoints[i];
			if (qP.Class == 0) {
				++iClass0;
			} else {
				++iClass1;
			}
		}
		return Entropy(iClass0, iClass1);
	} 
}

// A decision node contains a variable index (0 or 1) and boundary value in the interval [0, 1]
// It also has two child pointers to potential nodes.
class CDecisionBoundary {
	#miVariable;
	#mdDecision;
	constructor(qDataSet) {
		let qaP = qDataSet.Points();
		// Sort the points by a coordinate value
		let qaSort0 = new Array(qaP.length);
		let qaSort1 = new Array(qaP.length);
		for (let i = 0; i < qaP.length; ++i) {
			let qSwap = null;
			// Insert the point into each list
			qaSort0[i] = qaP[i];
			let j = i;
			while (j > 0 && qaSort0[j].X < qaSort0[j - 1].X) {
				qSwap = qaSort0[j - 1];
				qaSort0[j - 1] = qaSort0[j];
				qaSort0[j] = qSwap;
				--j;
			}
			qaSort1[i] = qaP[i];
			j = i;
			while (j > 0 && qaSort1[j].Y < qaSort1[j - 1].Y) {
				qSwap = qaSort1[j - 1];
				qaSort1[j - 1] = qaSort1[j];
				qaSort1[j] = qSwap;
				--j;
			}
		}
		// There are two groups: 0 and 1
		let iaInitialCount = [0,0];
		// Calculate the zero split first. This is the basis for generating the other counts. It also gives us the group entropy;
		for (let i = 0; i < qaP.length; ++i) {
			if (qaP[i].Class == 0) {
				iaInitialCount[0] += 1;
			} else {
				iaInitialCount[1] += 1;
			}
		}
		// We want to find the split value with the minimal entropy
		// Take the middle value between each successive point values
		let iMinEntropyCoord = 0;
		// Start with the entire group entropy
		let dGroupEntropy = Entropy(iaInitialCount[0], iaInitialCount[1]);
		let dMinEntropy = dGroupEntropy;
		// This designates the index that we split after. So, 0 is a split between 0 and 1.
		let dMinSplitIndex = -1;
		// The counts are [group#][class]
		let iaaCounts = [[0,0],[0,0]];
		// Put the sorts into arrays
		let qaaSorts = [qaSort0, qaSort1];
		for (let iCoord = 0; iCoord < 2; ++iCoord) {
			// Everything begins in the second group
			iaaCounts[0][0] = 0;
			iaaCounts[0][1] = 0;
			iaaCounts[1][0] = iaInitialCount[0];
			iaaCounts[1][1] = iaInitialCount[1];
			// The initial entropy is group entropy value
			for (let iSplit = 0; iSplit < qaP.length - 1; ++iSplit) {
				// Move the first point from group 1 to group 0
				if (qaaSorts[iCoord][iSplit].Class == 0) {
					iaaCounts[0][0] += 1;
					iaaCounts[1][0] -= 1;
				} else {
					iaaCounts[0][1] += 1;
					iaaCounts[1][1] -= 1;
				}
				let dCurrEntropy = TotalSplitEntropy(iaaCounts);
				if (dCurrEntropy < dMinEntropy) {
					iMinEntropyCoord = iCoord;
					dMinSplitIndex = iSplit;
					dMinEntropy = dCurrEntropy;
				}
			}
		}
		this.#miVariable = iMinEntropyCoord;
		// Use the average between value
		if (this.#miVariable == 0) {
			this.#mdDecision = (qaaSorts[this.#miVariable][dMinSplitIndex].X + qaaSorts[this.#miVariable][dMinSplitIndex + 1].X)/2
		} else {
			this.#mdDecision = (qaaSorts[this.#miVariable][dMinSplitIndex].Y + qaaSorts[this.#miVariable][dMinSplitIndex + 1].Y)/2
		}
		var qEntropy = document.getElementById("idSplitEntropy");
		qEntropy.innerHTML = dMinEntropy;
		var qInformationGain = document.getElementById("idInformationGain");
		qInformationGain.innerHTML = dGroupEntropy - dMinEntropy;
	}

	Graph(qContext) {
		let iWidth = qContext.canvas.width;
		let iHeight = qContext.canvas.height;
		qContext.strokeStyle = "black";
		qContext.lineWidth = 1;
		qContext.beginPath();
		// x = this.#mdDecision
		if (this.#miVariable == 0) {
			let dX = this.#mdDecision*iWidth;
			qContext.moveTo(dX, 0);
			qContext.lineTo(dX, iHeight);
		} else {
			let dY = this.#mdDecision*iHeight;
			qContext.moveTo(0, dY);
			qContext.lineTo(iWidth, dY);
		}
		qContext.stroke();
	}
}

function Entropy(iCount0, iCount1) {
	let dP0 = iCount0/(iCount0 + iCount1);
	let dP1 = iCount1/(iCount0 + iCount1);
	if (dP0 == 1 || dP1 == 1) {
		return 0;
	}
	// Use the log base 2
	let dEntropy = -(dP0*Math.log(dP0) + dP1*Math.log(dP1))/Math.log(2);
	return dEntropy;
}

function TotalSplitEntropy(iaaCounts) {
	let iTotal0 = iaaCounts[0][0] + iaaCounts[0][1];
	let iTotal1 = iaaCounts[1][0] + iaaCounts[1][1];
	let iTotal = iTotal0 + iTotal1;
	let dPG0 = iTotal0/iTotal;
	let dPG1 = iTotal1/iTotal;
	let dEntropy = dPG0*Entropy(iaaCounts[0][0], iaaCounts[0][1]) + dPG1*Entropy(iaaCounts[1][0], iaaCounts[1][1]);
	return dEntropy;
}

function Initialize() {
	var qCanvas = document.getElementById("idCanvas");
	var qContext2D = qCanvas.getContext("2d");
	qContext2D.transform(1, 0, 0, -1, 0, qContext2D.canvas.height);
	
	let qDataSet = new CDataSet(50);
	qDataSet.Graph(qContext2D);
	
	let qDecision = new CDecisionBoundary(qDataSet);
	qDecision.Graph(qContext2D);
	
	var qEntropy = document.getElementById("idEntropy");
	qEntropy.innerHTML = qDataSet.Entropy();
}

Canvas JavaScript

Calculating a Decision Boundary

DecisionBoundary.html

DecisionBoundary.js

Output