Clustering

Bismillahirrahmanirrahiim. Dengan nama Allah yang Maha Pemurah lagi Maha Penyayang.

...

Prolog.

"Akhirnya, saya dah jumpa satu circle yang saya rasa sangat selesa bersama - sama", katanya.

Aku terdiam.

Sebenarnya aku jeleous. Ya. Sebab aku takde pon satu circle yang aku boleh katakan, yang aku sangat selesa to be with...

...

Beberapa ketika lepas. Officemate aku tanya, "Fairuz, you boleh tolong suggest tak?"

"Ha apa dia"

So dia terangkanlah ada beberapa use case yang tengah sangkut sekarang. Kesahnya, sekarang ni ada data geolocation (yang ada latitude dengan longitude) di mana berlakunya tangkapan di laut. So sekarang dia nak suggest tempat rondaan atau berapa kapal yang dicadangkan untuk membuat rondaan di kawasan tersebut.

Aku cakaplah kat dia, "Kalau kat laut, senang. Sebab takde restriction untuk lalu laluan macam jalan raya"

"Meaning?" tanyanya lagi.

"Ok kalau kat laut, data yang melibatkan (x, y) iaitu location, nak paling mudah sekali analisis kita boleh buat, kita boleh gunakan teknik clustering".

Ok sebenarnya clustering ni tak de la strict sangat nak location x,y. Anything with 2 demensional data pon boleh juga. 

...

Anyway, basically untuk clustering ni, dia akan associatekan setiap data point tu ke cluster yang berdekatan.

So let say kita ada 300 sets of data yang quite random macam kat bawah ni.

^ Figure 100: Random points generated

(abaikan kaler - kaler tu) So contohnya aku ada 5 kapal dan point - point tu merujuk kepada lokasi tangkapan berdasarkan jenis - jenis tangkapan (colour coded).

Now, macam mana aku nak maximizekan, i.e. gerakkan kesemua (lima) kapal tersebut meronda di kawasan yang pernah terjadinya tangkapan tersebut, tetapi, memastikan setiap kapal dekat dengan historically/sejarah tangkapan.

So where to put those 5 ships? Using math of course.

We start with simplest type of clustering. K-Means.

Objective Function for K-Means basically can be defined it as below. 

\[ J = \sum_{i=1}^{k} \sum_{j=1}^{n} \left\| \mathbf{x}_j^{(i)} - \boldsymbol{\mu}_i \right\|^2 \label{kmeans}\tag{1} \]

with,

• \( \boldsymbol{k} \) tu jumlah cluster yang kita define.
• \( \mathbf{x}_j^{(i)} \) adalah \( j \) data point in cluster \( i \)
• \( \mu_i \) is the centroid of cluster \( i \)
• \( \left\| . \right\| \) pulak adalah distance (biasa kita gunakan Euclidean Distance.

Now see here. Yang paling penting adalah untuk nak minimizekan \( \boldsymbol{J} \), which means to get the minimum distance for each point to cluster centroid.

Ok cenggini. Contoh kalau kita gunakan equation $\ref{kmeans}$ kat data yang kita ada sebelum ni, kita akan dapat camni ha.

^ Figure 101: K-Means Clustering

Idea dia, setiap point tu, akan pergi ke centroid yang terdekat. So jadinya macam ni.

^ Figure 102: K-Means Clustering with line connected to centroid

Also notice that yang dekat2 antara dua cluster tu, dia akan pilih the nearest cluster. So basically dia macam ni dari hasil kiraan dia.

^ Table 100: Distance Point to Cluster Center.

So all the distance ni yang paling kecik yang dia dapat untuk minimizekan objective function $\ref{kmeans}$ tu. And of course, ianya dikuasa duakan untuk kasi penalti kepada yang makin jauh (remember the equation for Mean Square Error? Ya. Sama konsep).

Ok yang ni biasanya kita cakap dia sebagai hard clustering. Means that setiap satu points hanya akan sambung ke satu cluster centroid sahaja. So all points ni kita panggil as a cluster member.

Contohnya la kan, kita ada data lokasi kedudukan orang ramai - ramai kat dalam dewan. So nak letak budak sales, kita boleh gunakan ni untuk carik lokasi terbaik (centroid) yang berdekatan dengan setiap orang. So kalau ada 3 budak sales, kita buat 3 cluster. Ok ni theoritically lah.

Tapi, kadang - kadang, tak semestinya setiap point tu boleh connect ke satu cluster centroid sahaja. Boleh jadi satu point tu akan connect ke beberapa centroid. Dia agak fuzzy - fuzzy sikit (sebab bayangkan satu point boleh pergi ke dua tiga cluster).

And that is why nama untuk teknik ni adalah Fuzzy C-Means (FCM). And yes. This is Artificial Intelligence method (kategori fuzzy logic).

So the idea for FCM, dia akan associatekan satu point ni ke semua cluster centroid dan dia akan kira jarak dia.

Macam biasa, objektive function dia adalah untuk minimizekan this \( J \).

\[ J_m = \sum_{i=1}^{k} \sum_{j=1}^{n} u_{ij}^m \left\| \mathbf{x}_j - \boldsymbol{\mu}_i \right\|^2  \label{fcm}\tag{2}\]

dimana,

• \( \boldsymbol{\mu}_i = \frac{\sum_{j=1}^{n} u_{ij}^m \mathbf{x}_j}{\sum_{j=1}^{n} u_{ij}^m} \) is the centroid at \( i \).
  
• \( u_{ij} = \frac{1}{\sum_{l=1}^{k} \left( \frac{\left\| \mathbf{x}_j - \boldsymbol{\mu}_i \right\|}{\left\| \mathbf{x}_j - \boldsymbol{\mu}_l \right\|} \right)^{\frac{2}{m-1}}} \) is the membership.
  
• \( m \) is fuzziness parameter (\( m > 1 \). Lagi tinggi \( m \), lagi kabur mata.
  

Ok nampak bukan. Dia lebih kurang sama je dengan K-Means clustering, cuma tambah fuzziness parameter dengan cara dia update membership cluster dia. Ok there's a lot story behind the "membership". But the idea is that, kita akan connect semua points tu ke cluster and kira jarak, dan anggap je jarak tu sebagai dia punya weightage. 

Boleh refer kat figure bawah ni.

^ Figure 103: Fuzzy C-Means Clustering

The story is like this..

Aku, seorang manusia biasa, boleh belong to all cluster - cluster member aku (kalau aku ni jenis yang ok lah dengan semua orang). Korang pon boleh nampak kan. Yang sorang ni ada geng - geng dia. Yang sorang lagi tu pon ada geng - geng dia jugak. Ada jugak yang dia boleh overlap beberapa geng.

But the most important, diorang ada geng diorang sendiri. In psychology, we (they) call it as "Social Identity Theory". You belonging to one close group. Atau satu komuniti. Yang ada benifit atau some target or positive thing they feel kalau dia ada dalam group/komuniti tu.

...

So apabila kawan aku cakap dia dah jumpa close circle dia, means dia dah betul - betul berada di area dalam satu cluster dengan jarak ke centroid cluster dia sangat rendah (remember, in clustering we are trying to find the minimum distance?).

And why aku jelous.

Basically macam graph bawah ni.

So I try to figure out. Why like this. Aku ni takde ke Social Identity?

Several explaination that I found out actually. One, maybe sebab dah ada family. Kawan - kawan aku pon ada macam ni gak. But later I found out, it is not. Sebab diorang duduk sekali dengan family dia. Aku pulak, well.. aku malas pulak nak citer ni. But the main point, this is not the reason.

Secondly, maybe sebab ada social media, to fill in the gap of the closeness by fitting oneself to social media. Remember Social Identity Theory tu? And also korang tau kan macam mana algorithm social media ni berfungsi? Lagi banyak korang tengok feed/video pasal satu topic tu, algo akan define ko kat dalam some sort of category. 

But I don't think because of that. Aku takde pon main social media sangat. Ada tengok. But not feeling to be a part of it.

Or maybe.

Maybe..

Disebabkan alasan nombor tiga ni:

The kind of guy yang tak boleh rapat dengan mana - mana group.

...

Several weeks ago, Pika ada citer kat aku. Dia kata aku ni jenis kalau orang rapat je dengan aku, nanti aku akan ghostingkan dia. Aku mula menjarakkan diri.

To be honest. Ya. Aku memang macam ni. Makin lama, makin rapat. Makin rapat tu, aku mula lah menjarakkan diri. Tak kesah. Lelaki atau perempuan. Same!

I don't have valid reason kenapa aku macam ni..

Maybe..

I was build like this.

Enough. That's all reasoning that I need.

Bukan aku tak ada kawan rapat. Ada. In fact, aku buat blog ni pon sebab dialah yang 'force' aku buat blog (tengok balik my first post in 2006: here). Ya kawan rapat aku tu is actually my "Social Identity". Aku pergi mana - mana jumpa kawan mutual kitorang, mesti diorang akan tanya, "Raje, kucai mana?".. But unfortunately, dia dah pergi meninggalkan kita semua. Including me.

So I was left with a big hole in my life. Right.. That's is where the jelousy comes in (I force to think that, that is the main reason).

And makin tak lah aku nak rapat dengan orang...

In the end, actually I know the reason.

If I left this world, I wanted to be the furthest from all cluster that is associated with me. So at least diorang ni takde la rasa terluka sangat kan, kalau aku takda?