K-means Clustering

One of the biggest advantages of being an engineer is that we can apply concepts that we have learnt in our syllabus to virtually any problem in the world, and try to come up with new and innovative ideas to deal with these problems. We see a number of examples of engineers coming up with bizarre applications. Why refer to other engineers. Me and Anant Devi have already come up with Datar-Devi Approximations for Exams. A cousin of mine, by profession a computer geek, by passion a world class singer came up with another of such fantastic research of the relation between the frequency of your arm swing while walking and your velocity. Amazing stuff. Really, there are no boundaries for us engineers. All we need to do is think a little bit out of the box. Today, I shall be discussing one of the more important algorithms that we have in signal processing (esp speech processing)-the K-means algorithm and its application to one of the major headache for all college guys- the right girl.

Now, engineers, or for that matter most of the guys are hopeless when it comes to selecting the right girl for them. They just fall in love without thinking! (I know Ill be called a hypocrite- I too have been down this path on multiple occasions. MadB will be the one who will accuse me first, but yeah, who takes her seriously when she accuses!) And then they end up fighting with the girl over petty issues, and then act like crybabies.  What guys need is patience. This post is dedicated to all guys who are eternally confused as to what they will do with their love life and provide with insight of finding the best possible partners.

Let me introduce you to our quirky and extremely challenging to implement in matlab friend of ours, The K-means algorithm, which I will use to address your woes. To the unwary and uneducated, K-Means is a clustering algorithm that we commonly use for vector quantization. A given n dimensional ( n corresponding to various parameters) vectors when quantized into a data of say n bits is mapped to its nearest encoded bitstream which gives minimum mean squared error ( the message to which it is encoded is called the centroid) . One problem is- how do you assign the centroid. Well, it is simple. Its nothing but a mean of all the vectors in that cluster. So, dynamically, the centroid will keep on changing until all entities converge to a single point.
Mathematically, the K-means algorithm will be given by


Given a set of observations (x₁, x₂, …, x_n), where each observation is a d-dimensional real vector, k-means clustering aims to partition the n observations into k sets (k ≤ n) S = {S₁, S₂, …, S_k} so as to minimize the within-cluster sum of squares (WCSS):

where μ_i is the mean of points in S_i.

[wikipedia.]

Pictorally, this can be represented as:

• 

  1) k initial "means" (in this casek=3) are randomly selected from the data set (shown in color).
 
• 

  2) k clusters are created by associating every observation with the nearest mean. The partitions here represent theVoronoi diagram generated by the means.
 
• 

  3) The centroid of each of the kclusters becomes the new means.
 
• 

  4) Steps 2 and 3 are repeated until convergence has been reached.

Now, coming back to the notion of the application of K-means for the problem to be addressed. Here, in k-means we have a n dimensional vector. Let these n dimensions be all the points you will look for in the girl. (My vector, is 20 dimensional.) as shown in the figure above, make three categories- Girls who you like.
Girls who you do not like. and Girls who you think are OK. Each girl will have her own unique n dimensional vector. Assign a self defined centroid for all three of them.

As you grow older through your engineering years you come across a number of girls, not necessarily in your college, who you may have considered as your potential ideal match, or as your worst possible match. This will give you quite a bit of database for statistical analysis. When you see a girl in either category, observe them for a few days, and adjust their vectors, and keep them updating. after a sufficient amount of time, the vectors will have reached a saturation point and will not alter. this is when you apply the k-means.

now, it is highly unlikely that we will get a girl who coincides with our self defined centroids. If that happens to be your case, you are one hell of a lucky ba***d. But for people like me, who have some impossible conditional vector entries, this is almost impossible. Also, it is highly improbable that you will have a girl with some qualities from girl B who has some desirable qualities and girl C who has other desirable qualities. Lets face it- its unlikely. So, the best solution is to find the "vector" which will give you the least mean squared error at the output of the K-means. The girl corresponding to that vector is the one you go for!

Just to conclude:

If you like a girl, you have to wait for some time to be absolutely sure that she is the one that is perfect for you. Observe. Make mental notes of all the small things she does. (ofcourse this advise is only for those who are looking long term.. those interested in short term can jump ships whenever they want!). Make a mental note of what you want your ideal girl to be like beforehand. Ive received a lot of flack for my ideal girl, who can be found here, but nevertheless, do it.  Jot down all the points you want in all of them, and get ready to run the K-means algorithm.It works!!

(Personally, I dont recommend this approach- I havent done it for myself, and probably will not do it. Im more of a hopeless old school- fall in love arbitrarily kind of person to try this out. I am not suffering that much, and I am happy with the things as of now. No need for me then! This analogy was made purely to showcase the versatility that an engineer can adopt to make even the simplest of the things mathematical and complex. )

The Fridge Key

I dont know how much impact this will have on my grades, but i hope it does not, for we did this misdeed last year! 

Third year, for many reasons, was one of the most memorable years in college. Especially the 6th semester. Probably, it was the first time we didnt have that much load on our shoulders, or maybe the subjects were easy, or even maybe for the fact the I managed to score an 8 point grade after two wretched semesters made it all the more special. It was the time that the bonding in class was at its best. I had made some incredible like minded friends by that time. So its not surprizing that we ended up doing what I am going to narrate. 

It was a typical March afternoon, probably the last week-sometime between 3:30-5:30, EM practical, with Babya conducting the practical session. March in Pune is bad, and in a closed 20x20 room filled with an assortment of CROs and other measuring instruments,  with just a single ceiling fan operating, and a ban to switch on the AC, it gets even worse. Heat, sweat and practicals had drawn us to madness. To make the matters worse we had run out of supplies for water, and if we needed to get them, we had to climb down two flights of stairs and back up again. Who has the energy to do all that at the end of a tiring day! Nevertheless we did go down to get two waterbottles filled up, but to our sheer disappointment, the water was as hot as the weather outside. Something Cool was the need of the hour.

Fortune, was on our side. The EM lab has a refrigerator.  So, we decided to cool our water bottles and have something cool to drink later. When we opened the fridge door, to our delight, there were 5-6 bottles of cold water, which we immediately set about consuming, and were promptly told off for doing so. Angered at the fact that we were told off for drinking cool water, and were prevented from cooling our own bottles, we plotted a revenge.

As it happened, we conducted an extra practical for ourselves to get the lab assignments out of the way a couple of days later. Now, that day, me and my partner in crime from my lab sessions- Krishna, observed that our friend Babya had left the key on the refrigerator lock. A devilish scheme tool place, and we came up with the conclusion that if we cannot drink cold water, nobody can. So, when nobody was observing, me and Krishna quickly locked the fridge and hid the key, initially in Krishnas pocket. When we did finish performing the practical, we left silently, taking the key with us.

Now, the summer heat got to Babya, and he wanted to have a drink, but could not open the fridge as we had locked it! He was livid. He told off the remaining people from our batch and demanded where was the key. He knew that we had left. So he called us back to the lab, and told that he is checking all bags and pockets for his fridge keys. we needed a place to hide the key somewhere. So Krishna came up with a solution. the key was put on his sandal underneath his foot, and off we went to the lab. We got searched, and still the key could not be found. So we acted to show that we didnt have it by helping search for it. We literally lifted the fridge to check if it was underneath the fridge, checked under all desks, tables, chairs everywhere- but no sign of the key. Babya who was flustered by his thirst by now, told that this was a serious issue and would be reported to the HOD. (who is scared of action taken on a prank!)

We were told off, and then let go. Next day I think it was RDJ who came and told off the entire class for stealing the keys. Here, playing mafia came in rather handy. I was totally able to pull off the fact that it wasnt with me, and I was not associated with this crime! The same applied for Krishna, although he doesnt need mafia practice. 

We kept the key with us for atleast 3 days. the 4th day was the April fools day. So, on that day, we decided to return our key anonymously. We put a sign saying april fool on it, and put the key in the lock of the Lab door. Somebody saw us putting the key there, but fortunately, did not report it. The next time we went for the practical, Babya was gleeful that he had found the key. He told that it was just misplaced probably, and he found it(as if..), and no action will be taken. So, the key was back, everyone was happy, me and krishna were let off for what can only be described as the most vadheev prank that Ive pulled off. 

It was fun! More fun than hiding Gandhalis Dio. More fun than we have had on the Boat club at times. Probably not that much fun as I had this semester doing vadheev pana with MadB,Ketki,Teja and Alok. Still, it was one of the best pranks that can be played in college. Juniors, it is your time to fill in my shoes now that I am graduating soon!

Krishna- Half the gang.

Chinmay- The other half of the gang.

Key- the one we kidnapped.