kmeans

README

kmeans

k-means clustering algorithm implementation written in Go

What It Does

k-means clustering partitions a multi-dimensional data set into k clusters, where each data point belongs to the cluster with the nearest mean, serving as a prototype of the cluster.

When Should I Use It?

• When you have numeric, multi-dimensional data sets
• You don't have labels for your data
• You know exactly how many clusters you want to partition your data into

Example

import (
	"github.com/DerikZhang/kmeans"
	"github.com/DerikZhang/clusters"
)

// set up a random two-dimensional data set (float64 values between 0.0 and 1.0)
var d clusters.Observations
for x := 0; x < 1024; x++ {
	d = append(d, clusters.Coordinates{
		rand.Float64(),
		rand.Float64(),
	})
}

// Partition the data points into 16 clusters
km := kmeans.New()
clusters, err := km.Partition(d, 16)

for _, c := range clusters {
	fmt.Printf("Centered at x: %.2f y: %.2f\n", c.Center[0], c.Center[1])
	fmt.Printf("Matching data points: %+v\n\n", c.Observations)
}

Complexity

If k (the amount of clusters) and d (the dimensions) are fixed, the problem can be exactly solved in time O(n^dk+1), where n is the number of entities to be clustered.

The running time of the algorithm is O(nkdi), where n is the number of d-dimensional vectors, k the number of clusters and i the number of iterations needed until convergence. On data that does have a clustering structure, the number of iterations until convergence is often small, and results only improve slightly after the first dozen iterations. The algorithm is therefore often considered to be of "linear" complexity in practice, although it is in the worst case superpolynomial when performed until convergence.

Options

You can greatly reduce the running time by adjusting the required delta threshold. With the following options the algorithm finishes when less than 5% of the data points shifted their cluster assignment in the last iteration:

km, err := kmeans.NewWithOptions(0.05, nil)

The default setting for the delta threshold is 0.01 (1%).

If you are working with two-dimensional data sets, kmeans can generate beautiful graphs (like the one above) for each iteration of the algorithm:

km, err := kmeans.NewWithOptions(0.01, plotter.SimplePlotter{})

Careful: this will generate PNGs in your current working directory.

You can write your own plotters by implementing the kmeans.Plotter interface.

Documentation

Overview

Package kmeans implements the k-means clustering algorithm See: https://en.wikipedia.org/wiki/K-means_clustering

Index

• type Kmeans
  • func New() Kmeans
  • func NewWithOptions(deltaThreshold float64, plotter Plotter) (Kmeans, error)
  • func (m Kmeans) Partition(dataset clusters.Observations, k int) (clusters.Clusters, error)
• type Plotter

Types

type Kmeans

type Kmeans struct {
	// contains filtered or unexported fields
}

Kmeans configuration/option struct

func New

func New() Kmeans

New returns a Kmeans configuration struct with default settings

func NewWithOptions

func NewWithOptions(deltaThreshold float64, plotter Plotter) (Kmeans, error)

NewWithOptions returns a Kmeans configuration struct with custom settings

func (Kmeans) Partition

func (m Kmeans) Partition(dataset clusters.Observations, k int) (clusters.Clusters, error)

Partition executes the k-means algorithm on the given dataset and partitions it into k clusters

type Plotter

type Plotter interface {
	Plot(cc clusters.Clusters, iteration int) error
}

The Plotter interface lets you implement your own plotters