![](\"https:\/\/contentlab.com\/wp-content\/uploads\/2021\/11\/image001-1.png\")
<\/p>\nLet\u2019s say we want to group some data. Each data element has some (numeric) attributes. Using these attributes, we want to split the data into different clusters. For us humans this often can be done just by looking at the data. For a computer, this is harder to determine.<\/p>\n
Of course, we (humans) can only “see” this if the data does not have too many dimensions, if the data set is not too big, and if the number of clusters is limited. If the data gets more complex, we\u2019ll require a computer.<\/p>\n
<\/p>\n
The code for this article can be found at https:\/\/github.com\/GVerelst\/ArtificialIntelligence<\/a>.<\/p>\n The sample code in this post is in F#, so some knowledge of this language is needed. There are good places on the web to learn this and I have put some of the better ones in the references section at the end. A good understanding of the |> operator will help.<\/p>\n We can have an e-commerce site with sales history per person. Maybe it would be nice to know whether a customer is a hobbyist so we can recommend some power tools. Or maybe they ordered a lot of DVDs before, so we can recommend them specific DVDs (or a DVD player).<\/p>\n For the DVDs, we might be able to find out the genres that this customer is interested in and propose some more interesting items to this customer.<\/p>\n Bitmaps are composed of RGB values. These values are sometimes just a little bit different, not visible to the human eye. But if we can cluster the millions of colors into a set of, say, 100 different colors, we may be able to compress the bitmap size. Or we may be able to discover shapes inside the image.<\/p>\n Let\u2019s start with clustering points on a line.<\/p>\n The inputs for the algorithm are:<\/p>\n Further inputs can be:<\/p>\n Using a functional language this can easily be done by passing the right functions into the algorithm.<\/p>\n Below we see a line with points at { 1, 2, 3, 7, 8, 10, 11, 15, 16, 18 } :<\/p>\n We want to divide this in 3 clusters (k = 3). Looking at the line we see that we\u2019ll probably end up with clusters { 1, 2, 3}, { 7, 8, 10, 11 } and { 15, 16, 18 }.<\/p>\n This is a typical flow for an optimization problem. First assign random values, then refine until a good solution is found.<\/p>\n The centroid is typically the “average” for each cluster. When we talk about single values, this means calculating the average of the values in each cluster. When we have more attributes in each item, we want to calculate the average value for each attribute. For example, in a cluster C, we have points {x, y}. The centroid will be the point with<\/p>\n The nearest point to another point is the point at the smallest distance from this point.<\/p>\n For each point, we are going to calculate the distance to each centroid, and then assign the point to the cluster with the nearest centroid.<\/p>\n A valid distance d(x, y) means:<\/p>\n There are a couple of different ways to calculate a distance between two points. We will create a separate function to calculate the distance.<\/p>\n In our case, we could suffice with (left | x-y right |)<\/span>. Alternatively, we could also use (sqrt{left ( x-y right )^{2}})<\/span>, which will always be possible as well. This brings us closer to the Euclidian distance.<\/p>\n When we want to calculate the distance between two points we get:<\/p>\n\\(d left( left( x_{1},y_{1} right ),left ( x_{2},y_{2} right ) right )=sqrt{left ( x_{1}-x_{2} right )^{2}+left ( y_{1}-y_{2} right )^{2}}\\)\n This is extensible to more attributes.<\/p>\n For the clustering algorithm, we are not interested in the exact distance, but we only want to know which centroid is nearer to a point. So there is no need to calculate the (expensive) square root.<\/p>\n On Wikipedia, this is explained in great detail: https:\/\/en.wikipedia.org\/wiki\/Distance<\/a><\/p>\n For our algorithm, we don\u2019t need to calculate the square root because we are not interested in the exact distance between two points. We only want to know which centroid is the nearest be a point.<\/p>\n This is the same data set as before, grouped randomly in three clusters: orange, yellow and green. For each cluster we now calculate the centroid:<\/p>\n I have added the centroids in the chart below. They are on the highest line.<\/p>\n The next thing to do is to find out for each point which centroid is closest. For each point, we now calculate the distance to all the centroids, and we assign the point to the nearest centroid\u2019s cluster. This gives us the following chart:<\/p>\n We can see that the situation is better and that the centroids are moving as well. The orange cluster currently only holds one item, but that will change.<\/p>\n This is the final solution. The algorithm has calculated new values, but they were equal to the previous ones. So, this is the best solution.<\/p>\n When in the code we see<\/p>\n this is the same as<\/p>\n We can look at this like: the values collection is sent into the With just one function in the pipeline this is not very useful (and mainly a matter of personal preference and code consistency) but looking at how we call the algorithm this starts to make sense:<\/p>\n We send the output from Structuring the code like this immediately makes all the steps that have been taken clear. It is more readable than<\/p>\n Typically, functional languages work with immutable lists. There are a lot of functions that can be used to handle elements in a list, often working on the whole list at once. This explains why we don\u2019t need loops.<\/p>\n Some of the functions are:<\/p>\n Example:<\/p>\n For each list item, the procedure for each list item, the function will be called. A new list with the results of the function will be returned.<\/p>\n This will return a list of lists, for each different value of I have used some more functions, but they are self-explanatory.<\/p>\n I used Visual Studio 2017 to create this project:<\/p>\n The code for this example is only 55 lines of F#. If you\u2019re going to check out the code from Github, you\u2019ll notice that there are actually 68 lines. This is because I also provided a condensed version of the This is the data row. In this case, it only contains a To make the code simple, I created a A second design choice I made was to keep the cluster with the data. Another possibility would be to create a new list for each cluster.<\/p>\n Let\u2019s start with the It runs over the collection and prints each element on a new line.<\/p>\n If you want to write this more concise, then you can make use of currying:<\/p>\n This will output the collection in the same way. Notice that the data type for The showClustered function outputs the same list of values but grouped per cluster.<\/p>\n I am using a This function returns the data. For the demo program, the data is a hard-coded list. The data can also be read from a file, which is more realistic.<\/p>\n Now that the plumbing is out of the way, we can move towards the actual implementation.<\/p>\n This function is used to calculate the distance between the centroids and the data points. I chose a very simple implementation, as you can see. This function will be passed as a parameter into the algorithm so that it can easily be replaced. This will be necessary when rows have more properties to take into account.<\/p>\n This function divides the original data set in k random clusters. Using F# helps to make this function a one-liner. All it does is mapping each element (x) to a new Row, together with a random number between 0 and k-1. If you want to make this more foolproof, you can verify that none of the clusters is empty. I have implemented this test in the k is passed as a parameter. This is the only place where we need to know the number of clusters.<\/p>\n You guessed it, this function will calculate the centroids for each cluster. The steps are<\/p>\n F# shines again in its conciseness!<\/p>\n Now that all the helpers are in place, not much is left for the actual calculation of the cluster.<\/p>\n Because this is a demo program, there is some output which you would leave out in a production program. The steps in the For the more concise version, profiting more from the |> operator:<\/p>\n Calling the In this pipeline we<\/p>\n The actual k-means algorithm is this: The algorithm is not perfect for a couple of reasons.<\/p>\n We made a simple example where rows only have one attribute, x. To extend this into clustering in a plane, you can add an attribute y. Besides the Both problems can be solved by making the type Clustering is an optimization problem. Often these problems are solved by first generating a random solution, and then refine this into an acceptable solution. It is never guaranteed that the solution will be perfect.<\/p>\n F# is a great language to use to implement such algorithms because of its conciseness, type inference, and immutability.<\/p>\n I implemented a more generic version of the algorithm that works with a list of floats in the data row, instead of just one x. This implies some changes in the code.<\/p>\n I have provided the code for this, but I will not discuss it further because only some details change. See https:\/\/github.com\/GVerelst\/ArtificialIntelligence\/blob\/master\/ArtificalIntelligence\/KmeansGeneric.fs<\/a>.<\/p>\n Introduction Let\u2019s say we want to group some data. Each data element has some (numeric) attributes. Using these attributes, we want to split the data into different clusters. For us humans this often can be done just by looking at the data. For a computer, this is harder to determine. Of course, we (humans) can […]<\/p>\n","protected":false},"author":3,"featured_media":5243,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"_jetpack_memberships_contains_paid_content":false,"footnotes":""},"categories":[241,18],"tags":[363,298,362],"hashtags":[],"yoast_head":"\nPrerequisites for this article<\/h2>\n
![\"\"](\"https:\/\/contentlab.com\/wp-content\/uploads\/2019\/04\/unnamed-1.png\")
<\/p>\nWhat are some examples of clustering?<\/h2>\n
E-commerce<\/h3>\n
Image compression<\/h3>\n
How does the algorithm work?<\/h2>\n
\n
\n
![](\"https:\/\/contentlab.com\/wp-content\/uploads\/2021\/11\/image003-1.png\")
<\/p>\nSteps for k-means clustering<\/h3>\n
![\"\"](\"https:\/\/contentlab.com\/wp-content\/uploads\/2019\/04\/unnamed2-1.png\")
<\/p>\n\n
\n
What is this “centroid”?<\/h4>\n
\n
What does “nearest” mean?<\/h4>\n
\n
Let\u2019s work out this example, with what we have learned so far<\/h3>\n
Iteration 0 (initialization)<\/h4>\n
![](\"https:\/\/contentlab.com\/wp-content\/uploads\/2021\/11\/image009.png\")
<\/p>\n![](\"https:\/\/contentlab.com\/wp-content\/uploads\/2021\/11\/image005-1.png\")
<\/p>\nIteration 1<\/h4>\n
![\"\"](\"https:\/\/contentlab.com\/wp-content\/uploads\/2019\/04\/unnamed3-2.png\")
<\/p>\nIteration 2<\/h4>\n
![\"\"](\"https:\/\/contentlab.com\/wp-content\/uploads\/2019\/04\/unnamed4-1.png\")
<\/p>\nIteration 3<\/h4>\n
![\"\"](\"https:\/\/contentlab.com\/wp-content\/uploads\/2019\/04\/unnamed5-1.png\")
<\/p>\nWhat you need to know about F# to follow the code<\/h2>\n
The pipeline operator |><\/h3>\n
let centroids = values |> calcCentroids<\/pre>\n
let centroids = calcCentroids values<\/pre>\n
calcCentroids<\/code> function.<\/p>\ngetValues |> assignRandomClusters k |> algo calcIntDistance |> showClustered<\/pre>\n
getValues<\/code> to the assignRandomClusters<\/code> function as a second (hidden) argument. The output from this function is then sent into the algo<\/code> function (hidden argument), and finally, the output from algo is sent into showClustered<\/code> (hidden argument).<\/p>\nshowClustered (algo calcIntDistance (assignRandomClusters k getValues))<\/pre>\n
Lists<\/h3>\n
List.iter<\/h4>\n
values |> List.iter (printfn \"%A\")<\/pre>\n
(printfn \"%A\")<\/code> will be called.<\/p>\nList.map<\/h4>\n
xs |> List.map (fun y -> {x = y; cluster = random.Next(k)} )<\/pre>\nList.groupBy<\/h4>\n
rows |> List.groupBy(fun r -> r.cluster)<\/pre>\n
r.cluster<\/code>.<\/p>\nCreating the project<\/h3>\n
\n
Show me the code!<\/h2>\n
algo<\/code> function. You can find the implementation of the algorithm here: https:\/\/github.com\/GVerelst\/ArtificialIntelligence\/blob\/master\/ArtificalIntelligence\/KmeansOneValue.fs<\/a>.<\/p>\nData structures<\/h3>\n
[<StructuredFormatDisplay(\"[x:{x}, c:{cluster}]\")>]\r\ntype Row =\r\n {\r\n x: float;\r\n cluster: int;\r\n }<\/pre>\nfloat<\/code> x as a data item, and as explained before, the cluster that it belongs to. The StructuredFormatDisplay<\/code> attribute makes the printfn<\/code> function output the Row<\/code> in a nice way.<\/p>\nRow<\/code> with 1 data point (x). To make things more generic we can change this into a float list. This would allow having multiple values per row.<\/p>\nPresentation functions<\/h3>\n
showData<\/h4>\n
showData<\/code> function, which is trivial:<\/p>\nlet showData values =\r\n values |> List.iter (fun r -> printfn \"%A\" r)<\/pre>\n
let showData values =\r\n values |> List.iter (printfn \"%A\")<\/pre>\n
showData<\/code> is not specified. This makes the function polymorphic. And this is where StructuredFormatDisplay<\/code> comes in.<\/p>\nshowClustered<\/h4>\n
let showClustered values =\r\n values |> List.groupBy(fun r -> r.cluster)\r\n |> List.iter(fun (c, r) -> \r\n printfn \"Cluster %d\" c \r\n r |> showData)<\/pre>\n
Initialize the randomizer<\/h4>\n
let random = new Random(5);<\/pre>\n
Random<\/code> with a seed of 5. This will always generate the same series of random numbers, so the output of the program will be the same. In real life, this is not necessary, and you can instantiate a Random<\/code> with no arguments.<\/p>\nlet getValues = [ 1.0; 2.0; 3.0; 7.0; 8.0; 10.0; 11.0; 15.0; 16.0; 18.0; ]<\/pre>\n
Helper functions<\/h3>\n
calcIntDistance<\/h4>\n
let calcIntDistance t u = Math.Abs(t.x - u.x)<\/pre>\n
assignRandomClusters<\/h4>\n
KmeansGeneric<\/code> module.<\/p>\nlet assignRandomClusters k xs =\r\n xs |> List.map (fun y ->= y; cluster = random.Next(k)} )<\/pre>\n
calcCentroids<\/h4>\n
let calcCentroids rows =\r\n rows |> List.groupBy(fun r -> r.cluster)\r\n |> List.map(fun (c, r) -> \r\n { \r\n x = r |> List.averageBy (fun x -> x.x);\r\n cluster = c\r\n })<\/pre>\n\n
rows |> List.groupBy<\/code> will split the collection of rows per cluster. The result is a list of lists.<\/li>\nList.map<\/code> will calculate the centroid for each cluster. This means taking the average from the cluster rows and adding the cluster number to it.<\/li>\n<\/ul>\nThe actual algorithm<\/h3>\n
let rec algo calcDistance values =\r\n printfn \"nLoop\"\r\n values |> showClustered\r\n printfn \"Centroids\"\r\n\r\n let centroids = values |> calcCentroids\r\n centroids |> showData\r\n\r\n let values' = values |> List.map (fun v -> \r\n let shortest = centroids |> List.minBy(fun c -> calcDistance c v)\r\n { v with cluster = shortest.cluster }\r\n )\r\n\r\n if values = values' then values'\r\n else algo calcDistance values'<\/pre>\nalgo<\/code> function are<\/p>\n\n
calcCentroids<\/code> function<\/li>\n\n
let rec algo calcDistance values =\r\n let values' = values |> List.map (fun v -> \r\n let shortest = values |> calcCentroids \r\n |> List.minBy(fun c -> calcDistance c v)\r\n { v with cluster = shortest.cluster }\r\n )\r\n\r\n if values = values' then values'\r\n else algo calcDistance values'<\/pre>\nUsing the algorithm<\/h4>\n
algo<\/code> function:<\/p>\ngetValues |> assignRandomClusters k |> algo calcIntDistance |> showClustered<\/pre>\n
\n
calcIntDistance<\/code> being the function that will calculate the distance between two points. This allows inserting different functions if desired.<\/li>\nassignRandomClusters k |> algo calcIntDistance<\/code><\/p>\nCaveats<\/h2>\n
\n
Extending this example<\/h2>\n
Row<\/code> type and the getValues<\/code> function, there are only two places where the code must be adapted:<\/p>\n\n
calcDistance<\/code> function, using x and y to calculate the distance.<\/li>\ncalcCentroids<\/code> function, you\u2019ll also need to assign the y value.<\/li>\n<\/ul>\nRow<\/code> more generic, but for the sake of simplicity, I left it as it is.<\/p>\nConclusion<\/h2>\n
\n
calcListDistance<\/code> is implemented as the sum of the squares<\/li>\ncalcCentroids<\/code> became a bit more complicated, but essentially it does the same<\/li>\nReferences<\/h2>\n
General<\/h3>\n
\n
k-means algorithm<\/h3>\n
\n
F#<\/h3>\n
\n
\n