K-Means Clustering from Scratch

k_means_from_scratch.kt

import org.apache.commons.math3.distribution.NormalDistribution
import kotlin.math.pow

// Desmos graph: https://www.desmos.com/calculator/pb4ewmqdvy

val points = sequenceOf(
		1.4,1.3,
		3.1,2.3,
		3.6,2.4,
		1.7,1.5,
		4.5,3.1,
		2.0,3.3,
		3.1,1.2,
		8.4,8.2,
		10.1,9.7,
		7.6,9.1,
		11.1,8.7,
		9.6,8.9,
		11.4,7.6,
		10.3,10.9,
		8.1,6.3,
		9.4,5.3,
		8.6,4.3,
		7.2,5.5,
		6.9,4.1,
		6.1,6.3,
		6.2,5.0,
		14.1,2.1,
		16.5,3.2,
		12.5,2.8,
		15.3,4.5,
		12.1,1.8,
		15.2,1.1,
		14.9,3.2
).windowed(2,2)
.map { (x,y) -> ObservedPoint(x,y) }
.toList()

sealed class Point {
	abstract val x: Double
	abstract val y: Double
}

data class ObservedPoint(override val x: Double, override val y: Double): Point()

class Centroid(val index: Int): Point() {
	override var x = 0.0
	override var y = 0.0
}

fun distanceBetween(point1: Point, point2: Point) =
		((point2.x - point1.x).pow(2) + (point2.y - point1.y).pow(2)).pow(.5)

fun main() {

	val k = 4
	val centroids = (0 until k).map { Centroid(it) }

	var bestLoss = Double.MAX_VALUE

	val normalDistribution = NormalDistribution(0.0, 1.0)

	repeat(100_000) {

		val randomCentroid = centroids.random()

		val xAdjust = normalDistribution.sample()
		val yAdjust = normalDistribution.sample()

		randomCentroid.x += xAdjust
		randomCentroid.y += yAdjust

		val newLoss = points.asSequence()
				.map { pt ->
					centroids.asSequence().map { distanceBetween(it, pt) }.min()!!.pow(2)
				}.sum()

		if (newLoss < bestLoss) {
			bestLoss = newLoss
		} else {
			randomCentroid.x -= xAdjust
			randomCentroid.y -= yAdjust
		}
	}

	centroids.forEach { println("${it.x},${it.y}") }
}