Why Are You Doing This in Excel? A Primer on K-means Clustering


Introduction

A few years back, when Data Science was still Big Data (but after it was called Artificial Intelligence), I was tasked with helping to prepare a primer on different techniques that could be useful for cost analysis. One of the techniques, K-means clustering, seemed simple enough to tackle and I was soon distracted enough by it to implement it. Recently, I came across the topic again and was inspired to see if I'd learned enough in the interim to do a better version. Ignoring common sense, I once more set out to solve a non-existent problem using a 30-year-old language that hasn't been supported in a decade.

This is the result.

Generating the Data

This is a solution in search of a problem, so generating that problem is the first step. I like problems that I already know the answer to, so I generated three groups of 2 data type (x,y) sets. I used a simple random distribution on the x's and y's with a set 'deviation' to get a nice spread. 

The result looks like this: 


I picked clusters that would intentionally be a little confusing to keep myself honest - hence, closely packed. Shaping the sets as circles would have been more optimal for this implementation, but since I'm not arguing for this particular technique I kept the generated problem simple. 

The Approach

K-Means clustering is an extraordinarily simple algorithm that has 2 real steps:

Initilization: Make k guesses for each potential central point (mean). I used a random set of points for fun graphics, but something like min, max, average, and regular intervals would be more scalable.
  1. Group the data according to the closest mean
  2. Calculate the means of the new groups, and use these as the next guess
Rinse and repeat until your data achieves the desired sheen. 

Here's what the data looks like after the first iteration:


Nice and messy.

If you use this for an actual problem, a tolerance should probably be defined, but in the spirit of this blog, I just stopped at 15 steps since the data is known to be well behaved in the assumed structure (3 means). At that point, it already looks like this: 


As you can see, this is more or less the original grouping. The actual means themselves are totally different than the original, but the fun thing about this sort of analysis is that it doesn't really matter.

I hope you enjoyed this overcomplicated solution to a problem that doesn't exist. If you'd like to view the source code, the link to the Excel sheet (VBA script included) is here.

Bonus Useless Solution - Refreshing charts in the middle of a VBA loop

You shouldn't use Excel to animate things, but I wanted to watch my groups evolve to the solution through each iteration. Here's the code I inserted at the end of the loop to get it to repopulate graphs without re-drawing every single point individually:

'Refresh graph display

        DoEvents
        ActiveSheet.ChartObjects("Chart 3").Chart.Refresh
        Application.Calculate
        DoEvents

I don't know why charts don't refresh automatically, I don't know why Chart.Refresh doesn't work without DoEvents, I don't know why DoEvents needs to be in there twice, but I'm pretty sure no one else does either. 

Fortunately, I don't have to, so if you run the macro you can watch the Solved graph evolve into the solution. Enjoy the show.










Comments

Post a Comment

Popular posts from this blog

What does it take to win at Kaggle? An Introduction to Data Strategy

Image
For our latest project, we were set to work on a completed  Kaggle competition  and tasked with analyzing the appearance of West Nile Virus (WNV) in Chicago to see if we could identify where the virus would start. Having learned my lesson from my experience with Ames housing prices , and being given a completed Kaggle leaderboard to start with, I wanted to know what constituted a 'good' score, and how hard it would be to get there. Hoping for a nice clean graph, I took a look at the score submissions over time: This is obviously a mess. If you look closely, there are some red, yellow, and green data points in there. These are respectively scores from groups with: The lowest 10 scores on the board Scores closest to the average Scores in the top 10 overall These are isolated here: Rolling over will isolate the groups. There seems to be a general elbow curve up and to the right, with groups slowly getting closer to a max score ...
Read more

Cutting Logs Part 1: Catching Ideas and Z's

Image
Trouble Sleeping Along with many other Americans, I often have a little trouble sleeping after a long day of staring at computer screens. My favorite solution at the moment is to take melatonin supplements. Like a lot of vitamins, it's a very iffy method with no regulation on dosage size or measure of effectiveness. Thus, while the limited scientific material I could find suggests between .5-1.5 mg for consumption, the smallest size I can find in the store comes in 3 mg. My solution for this has been to cut the pills in half, and throw the unused half back in the bottle. This went well until the other week, when I began to be bothered by the sensation that I only seemed to ever pull full pills from the bottle, despite having them around for months. So, I did what any normal person does with a vague but quantifiable suspicion and built a model to study the concentration of whole and half pills in the bottle over time, and the subsequent likelihood of pulling one or the other. ...
Read more

Creating a Dynamic Calendar

Image
Overview This is a sample Excel workbook which takes dates and events in a list, color codes them, and exports them into a natural and printable calendar format. It is designed to take events with durations and dependencies (as in a Gant Chart), and to update them quickly. The downloadable link is here . Sample Project The example in this workbook is a project with 5 sub-projects. Each project is about 1 week long, with a review scheduled for one day after completion and associated documentation due within 3 days of completion. Sample Input Results for Month of May Background and Discussion Some time ago, I was tasked with helping to manage an Agile development. In addition to the Sprints, I was tasked with keeping track of developing internal documentation, filing approvals for release, and developing detailed updates to management, including long-term and financial planning. I had about 150 sub-tasks associated with this project, and they...
Read more