{"id":668,"date":"2009-01-29T11:38:56","date_gmt":"2009-01-29T10:38:56","guid":{"rendered":"http:\/\/www.navision-blog.de\/2009\/01\/29\/kmeans-clustering-with-f\/"},"modified":"2023-01-01T13:18:02","modified_gmt":"2023-01-01T13:18:02","slug":"n-dimensional-k-means-clustering-with-f","status":"publish","type":"post","link":"http:\/\/www.navision-blog.de\/blog\/2009\/01\/29\/n-dimensional-k-means-clustering-with-f\/","title":{"rendered":"n-dimensional k-means clustering with F#"},"content":{"rendered":"

The K-means-Algorithm<\/a> is one of the simplest unsupervised learning algorithms that solve the well known clustering problem. In this article I will show how we can implement this in F#.<\/p>\n

First of all we define an interface for \u201cclusterable\u201d objects:<\/p>\n

\n

type<\/span> IClusterable =<\/p>\n

  abstract<\/span> DimValues: float array with<\/span> get <\/p>\n

  abstract<\/span> Dimensions: int<\/p>\n<\/p>\n<\/div>\n

The next step is to define a distance function. We will use n-dimensional Euclidean distance<\/a> here.<\/p>\n

\"Euclidean<\/p>\n

\n

let<\/span> calcDist (p1:IClusterable) (p2:IClusterable) =<\/p>\n

  let<\/span> sq x = x * x<\/p>\n

  if<\/span> p1.Dimensions <> p2.Dimensions then<\/span><\/p>\n

    failwith "Cluster dimensions aren’t equal."<\/span><\/p>\n

 <\/p>\n

  p2.DimValues<\/p>\n

    |> Array.fold2<\/p>\n

        (fun<\/span> acc x y -><\/span> x – y |> sq |> (+) acc) <\/p>\n

        0. p1.DimValues <\/p>\n

   |> sqrt  <\/p>\n<\/p>\n<\/div>\n

Now we define a n-dimensional Centroid<\/a> type. Our kMeans-Algorithm will minimize the squared distances to k centroids (or \u201cmeans\u201d).<\/p>\n

\n

type<\/span> Centroid =<\/p>\n

  {Values: float array;<\/p>\n

   dimensions: int}<\/p>\n

  member<\/span> x.Print = printfn "%A"<\/span> x.Values <\/p>\n

  interface<\/span> IClusterable with<\/span><\/p>\n

    member<\/span> x.DimValues = x.Values    <\/p>\n

    member<\/span> x.Dimensions = x.dimensions    <\/p>\n<\/p>\n<\/div>\n

The centroid of a finite set of n-dimensional points x1<\/sub>, x2<\/sub>, \u2026, xn<\/sub> is calculated as<\/p>\n

\"image\"<\/p>\n

\n

let<\/span> calcCentroid (items:’a list when<\/span> ‘a :> IClusterable)<\/p>\n

     (oldCentroid:Centroid) =<\/p>\n

  let<\/span> count = items.Length<\/p>\n

  if<\/span> count = 0 then<\/span> oldCentroid else<\/span><\/p>\n

  let<\/span> mValues =     <\/p>\n

    [|for<\/span> d in<\/span> 0..oldCentroid.dimensions-1 do<\/span><\/p>\n

        let<\/span> sum =<\/p>\n

          items <\/p>\n

            |> List.sumBy (fun<\/span> item -><\/span> item.DimValues.[d])<\/p>\n

 <\/p>\n

        yield<\/span> sum \/ (count |> float)|]<\/p>\n

 <\/p>\n

  { Values = mValues;<\/p>\n

    dimensions = oldCentroid.dimensions} <\/p>\n<\/p>\n<\/div>\n

We made a small modification – if we don\u2019t have any items assigned to a cluster the centroid won\u2019t change. This is important for the robustness of the algorithm.<\/p>\n

Now we can calculate the squared errors to a centroid:<\/p>\n

\n

let<\/span> calcError centroid (items:’a list when<\/span> ‘a :> IClusterable) = <\/p>\n

  let<\/span> calcDiffToCentroid (item:’a) =<\/p>\n

    centroid.Values<\/p>\n

      |> Array.fold2 <\/p>\n

          (fun<\/span> acc c i -><\/span> acc + (c-i)*(c-i)) <\/p>\n

          0. item.DimValues<\/p>\n

 <\/p>\n

  items<\/p>\n

    |> List.sumBy calcDiffToCentroid  <\/p>\n<\/p>\n<\/div>\n

For storing cluster information we create a cluster type:<\/p>\n

\n

type<\/span> Cluster<‘a> when<\/span> ‘a :> IClusterable =<\/p>\n

  {Items: ‘a list;<\/p>\n

   Count: int;<\/p>\n

   Centroid: Centroid;<\/p>\n

   Error: float}<\/p>\n

 <\/p>\n

  member<\/span> x.Print = <\/p>\n

     printfn "(Items: %d, Centroid: %A, Error: %.2f)"<\/span> <\/p>\n

       x.Count x.Centroid x.Error<\/p>\n

 <\/p>\n

  static<\/span> member<\/span> CreateCluster dimensions (item:’a) =<\/p>\n

    let<\/span> items = [item]<\/p>\n

    let<\/span> empty = <\/p>\n

      { Values = [||];<\/p>\n

        dimensions = dimensions}<\/p>\n

 <\/p>\n

    let<\/span> centroid = calcCentroid items empty<\/p>\n

    { Items = items;<\/p>\n

      Count = 1;<\/p>\n

      Centroid = centroid;<\/p>\n

      Error = calcError centroid items}<\/p>\n

 <\/p>\n

  member<\/span> x.EvolveCluster (items:’a list) = <\/p>\n

    let<\/span> l = items.Length<\/p>\n

    let<\/span> centroid = calcCentroid items x.Centroid<\/p>\n

    {x with<\/span> <\/p>\n

      Items = items;<\/p>\n

      Count = l;<\/p>\n

      Centroid = centroid;<\/p>\n

      Error = calcError centroid items}  <\/p>\n<\/p>\n<\/div>\n

Now we need a function to initialize the clusters and a function to assign a items to the nearest cluster: <\/p>\n

\n

open<\/span> System<\/p>\n

 <\/p>\n

let<\/span> rand = new<\/span> Random()  <\/p>\n

 <\/p>\n

let<\/span> InitClusters (k:int) dimensions <\/p>\n

      (items:’a array when<\/span> ‘a :> IClusterable)  =<\/p>\n

  let<\/span> length = items.Length<\/p>\n

  let<\/span> getInitItem() = items.[rand.Next length]<\/p>\n

  Array.init k (fun<\/span> _ -><\/span> <\/p>\n

                  getInitItem() <\/p>\n

                    |> Cluster<‘a>.CreateCluster dimensions)  <\/p>\n

 <\/p>\n

let<\/span> AssignItemsToClusters k dimensions (clusters:Cluster<‘a> array)<\/p>\n

      (items:’a seq when<\/span> ‘a :> IClusterable) = <\/p>\n

  if<\/span> k <= 0 then<\/span> failwith "KMeans needs k > 0"<\/span>   <\/p>\n

  let<\/span> findNearestCluster item =<\/p>\n

    let<\/span> minDist,nearest,lastPos =<\/p>\n

      clusters<\/p>\n

        |> Array.fold<\/p>\n

            (fun<\/span> (minDist,nearest,pos) cluster -><\/span><\/p>\n

               let<\/span> distance = calcDist item (cluster.Centroid)<\/p>\n

               if<\/span> distance < minDist then<\/span> <\/p>\n

                 (distance,pos,pos+1) <\/p>\n

               else<\/span> <\/p>\n

                 (minDist,nearest,pos+1))<\/p>\n

            (Double.PositiveInfinity,0,0)  <\/p>\n

    nearest<\/p>\n

 <\/p>\n

  let<\/span> assigned =<\/p>\n

    items <\/p>\n

      |> Seq.map (fun<\/span> item -><\/span> item,findNearestCluster item) <\/p>\n

 <\/p>\n

  let<\/span> newClusters = Array.create k []   <\/p>\n

  for<\/span> item,nearest in<\/span> assigned do<\/span>         <\/p>\n

    newClusters.[nearest] <- item::(newClusters.[nearest])<\/p>\n

 <\/p>\n

  clusters<\/p>\n

    |> Array.mapi (fun<\/span> i c -><\/span> c.EvolveCluster newClusters.[i])    <\/p>\n<\/p>\n<\/div>\n

The last step is a function which calculates the squared error over all clusters:<\/p>\n

\n

let<\/span> calcClusterError (clusters:Cluster<‘a> array) =<\/p>\n

  clusters<\/p>\n

    |> Array.sumBy (fun<\/span> cluster -><\/span> cluster.Error)<\/p>\n<\/p>\n<\/div>\n

Now it is an easy task to write the kMeans algorithm:<\/p>\n

\n

let<\/span> kMeansClustering K dimensions epsilon <\/p>\n

       (items:’a array when<\/span> ‘a :> IClusterable) =<\/p>\n

  let<\/span> k = if<\/span> K <= 0 then<\/span> 1 else<\/span> K<\/p>\n

  let<\/span> rec<\/span> clustering lastError (clusters:Cluster<‘a> array) =<\/p>\n

    let<\/span> newClusters = <\/p>\n

      AssignItemsToClusters k dimensions clusters items<\/p>\n

    let<\/span> newError = calcClusterError newClusters<\/p>\n

 <\/p>\n

    if<\/span> abs(lastError – newError) > epsilon then<\/span>        <\/p>\n

      clustering newError newClusters<\/p>\n

    else<\/span><\/p>\n

      newClusters,newError    <\/p>\n

 <\/p>\n

  InitClusters k dimensions items<\/p>\n

    |> clustering Double.PositiveInfinity  <\/p>\n<\/p>\n<\/div>\n

We can test this algorithm with random 2-dimensional points:<\/p>\n

\n

type<\/span> Point =<\/p>\n

  {X:float; Y: float}  <\/p>\n

  member<\/span> x.Print = printfn "(%.2f,%.2f)"<\/span> x.X x.Y<\/p>\n

  interface<\/span> IClusterable with<\/span><\/p>\n

    member<\/span> x.DimValues = [| x.X; x.Y |]<\/p>\n

    member<\/span> x.Dimensions = 2   <\/p>\n

 <\/p>\n

let<\/span> point x y = {X = x; Y = y}<\/p>\n

let<\/span> getRandomCoordinate() = rand.NextDouble() – 0.5 |> (*) 10.  <\/p>\n

let<\/span> randPoint _ = point (getRandomCoordinate()) (getRandomCoordinate())     <\/p>\n

let<\/span> points n = Array.init n randPoint<\/p>\n

let<\/span> items = points 1000<\/p>\n

 <\/p>\n

printfn "Items:"<\/span><\/p>\n

items |> Seq.iter (fun<\/span> i -><\/span> i.Print)<\/p>\n

 <\/p>\n

let<\/span> clusters,error = kMeansClustering 3 2 0.0001 items<\/p>\n

printfn "\\n"<\/span><\/p>\n

clusters |> Seq.iter (fun<\/span> c -><\/span> c.Print)    <\/p>\n

printfn "Error: %A"<\/span> error    <\/p>\n<\/p>\n<\/div>\n

Next time<\/a> I will show how we can simplify the code by using F#’s built-in type vector instead of array.<\/p>\n

https:\/\/edpillsbelgium.com<\/a><\/div>\n","protected":false},"excerpt":{"rendered":"

The K-means-Algorithm is one of the simplest unsupervised learning algorithms that solve the well known clustering problem. In this article I will show how we can implement this in F#. First of all we define an interface for \u201cclusterable\u201d objects: type IClusterable =   abstract DimValues: float array with get   abstract Dimensions: int The […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":[],"categories":[9,23,448,8],"tags":[515,514,664,516,513],"_links":{"self":[{"href":"http:\/\/www.navision-blog.de\/blog\/wp-json\/wp\/v2\/posts\/668"}],"collection":[{"href":"http:\/\/www.navision-blog.de\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/www.navision-blog.de\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/www.navision-blog.de\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"http:\/\/www.navision-blog.de\/blog\/wp-json\/wp\/v2\/comments?post=668"}],"version-history":[{"count":13,"href":"http:\/\/www.navision-blog.de\/blog\/wp-json\/wp\/v2\/posts\/668\/revisions"}],"predecessor-version":[{"id":2047,"href":"http:\/\/www.navision-blog.de\/blog\/wp-json\/wp\/v2\/posts\/668\/revisions\/2047"}],"wp:attachment":[{"href":"http:\/\/www.navision-blog.de\/blog\/wp-json\/wp\/v2\/media?parent=668"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/www.navision-blog.de\/blog\/wp-json\/wp\/v2\/categories?post=668"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/www.navision-blog.de\/blog\/wp-json\/wp\/v2\/tags?post=668"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}