-->

Jendela Statistika

Melihat Dunia Dengan Data Sebagai Sebuah Investasi

» » » MEMEMAHAMI K-MEAN

MEMEMAHAMI K-MEAN

Selamat sore kawan blogger, 
apa kabar semua?? 

Ok, lagi malas basa basi.. jadi langsung ke topik.
kita sore ini akan membahas secara singkat mengenai K-Means.

apa itu K-Means?
sebelum menjawab inti perrtanyaan, mari kita urutkan:

Pertama:  Definisi Clustering 
Metode untuk menemukan kelompok pada data berdasarkan kriteria tertentu.

Kedua: K-Means 
K‐Means clustering adalah metode untuk mengelompokkan item ke dalam k kelompok (dimana k adalah jumlah kelompok yang diinginkan).

Kelompok/cluster dibentuk dengan meminimalkan jumlah dari Euclidean distances diantara data dengan titik pusat (centroid) yang berkorespondensi.

Centroid adalah titik pusat data, dalam hal ini kita mengasumsikan rata‐rata vector sebagai centroid.

Titik (biru, merah, hijau) menyatakan data. Bintang (biru, merah, hijau) merepresentasikan titik pusat (centroid) yang mendefinisikan suatu kelompok.

Inisialisasi titik pusat (centroid)

Inisialisasi centroid dapat dilakukan dengan beberapa cara, contohnya 3 cara berikut: 

Dipilih secara dinamik: Metode ini tepat digunakan jika data baru ditambahkan secara cepat dan banyak. Untuk menyederhanakan persoalan, inisial cluster dipilih dari beberapa data baru, misal jika data dikelompokkan menjadi 3 clusters, maka inisial cluster berarti 3 item pertama dari data. 

Dipilih secara random: Paling banyak digunakan, dimana inisial cluster dipilih secara random dengan range data antara nilai terendah sampai nilai tertinggi.

Memilih dari batasan nilai tinggi dan rendah: tergantung pada tipe datanya, nilai data tertinggi dan terendah dipilih sebagai inisial cluster. 


Kelemahan K‐Means 

Jumlah cluster (k) harus ditentukan terlebih dahulu. 

Jika sampel data terlalu sedikit, hasilnya menjadi tidak akurat.

Kita tidak pernah tahu independent variable yang berkontribusi lebih terhadap proses clustering karena setiap variable diasumsikan memiliki bobot yang sama. 

Jika terdapat outlier, maka hasilnya akan berpengaruh secara signifikan sehingga tidak lagi akurat. 

Solusi yang bisa dilakukan: 

Melibatkan data sebanyak mungkin (semakin banyak data, maka hasilnya akan semakin akurat) Untuk menghindari distorsi yang disebabkan oleh outlier, maka digunakan nilai median, bukan nilai rata‐rata.


Mari mencoba membangun K-mean selangkah demi selangkah dengan bantuan library python:

*Perhatian
Buat mahasiswa atau alumni UII masih ingat Pak Prof. Fauzy, beliau dulu pernah mengajarkan cara untuk membangun data sampel secara random. Pada saat ini mari kita terapkan bersama ilmu yang dihibah ke kita.

Pertama, Kita akan membuat $n$ pasang data dua dimensi $(x,y)$ atau $\{(x_1,y_1),(x_2,y_2), (x_3,y_3), ..., (x_i,y_i), ..., (x_n,y_n)\}$, dengan domain $x$ dan $y$ sama yakni $[0,100]$ secara acak (random) namun ada struktur kelompoknya, dengan $n=100$ dan $k=3$ dengan Numpy untuk nantinya kita gunakan untuk ujicoba algoritma K-means yang akan buat.

# Import library Numpy
import numpy as np
# Pembuatan data secara random
ax = np.random.randint(0,40,20)
ay = np.random.randint(0,40,20)
bx = np.random.randint(70,100,20)
by = np.random.randint(33,66,20)
cx = np.random.randint(33,59,20)
cy = np.random.randint(70,100,20)
# keterangan:
# list(np.random.randint(minimum,maksimum,jumlah bilangan(data)
# yang dibuat))
# Mengelompokan data-data yang telah dibuat di atas menjadi x dan y.
x = []
y = []
for i in range(len(ax)):
x.append(ax[i])
x.append(bx[i])
x.append(cx[i])
y.append(ay[i])
y.append(by[i])
y.append(cy[i])
# Untuk melihat data sebagai berikut:
print('data x: ',x)
print('panjang x:',len(x))
print('data y: ',y)
print('panjang y:', len(y))


agar lebih mudah memahami data yang dibentuk, mari bawa data tersebut kedalam bentuk data frame.
# Import library Pandas
import pandas as pd
# Pembuatan dataframe kosong
df = pd.DataFrame()
# Memasukan data x dan y ke dalam dataframe
df['x'] = x
df ['y'] = y
# Dataframe 5 data pertama yang telah dibuat akan terlihat
# sebagai berikut:
print(df.head())
Kemudian, agar lebih bisa memahami pola dari data kita maka mari kita bentuk sebuah plot.
# Import library Matplotlib
import matplotlib.pyplot as plt
# Gambar dibuat dengan ukuran 5 x 5
plt.figure(figsize=(5,5))
plt.scatter(df['x'],df['y'],color = 'k')
plt.show() 

Dari data berikut kita bisa melihat 3 bentukan pola. 
Setelah itu, kita akan membuat inisiasi titik-titik pusat dari 3 pola tersebut.

Kita menggunakan Numpy kembali untuk membuat titik-titik pusat inisiasi secara acak sebanyak tiga pasang karena data menunjukan 3 kelompok dengan domain acak sama seperti domain data, yakni $[0,100]$.
pusat_x = np.random.randint(0,100,3)
pusat_y = np.random.randint(0,100,3)
pusat = []
for i in range(len(pusat_x)):
    pusat.append([pusat_x[i],pusat_y[i]])
print(pusat)


Ketika sudah mendapat nilai untuk setiap titik, maka kita akan menginisiasikkan titik ke dalam pola data.
# Tahap Inisiasi
import pandas as pd
import numpy as np
import matplotlib.pyplot as plt
#%matplotlib inline
#np.random.seed(200)
plt.figure(figsize=(5,5))
plt.scatter(x,y,color = 'k')
plt.scatter(pusat[0][0],pusat[0][1],color = 'r',marker= '*')
plt.scatter(pusat[1][0],pusat[1][1],color = 'b',marker= '*')
plt.scatter(pusat[2][0],pusat[2][1],color = 'g',marker= '*')
plt.show()
Setiap titik data disemati dengan titik pusat terdekatnya. Untuk melakukan hal tersebut kita gunakan konsep jarak antara dua vektor $d(c,p)$. 
Jadi jarak titik data $c=(x_c,y_c)$ ke pusat $p=(x_p,y_p)$ adalah
$$d(c,p)=\sqrt{(x_c-y_p)^2+(y_c-y_p)^2)}$$
karena ada tiga titik pusat, maka kita akan hitung jarak antara setiap data dan ketiga titik pusat, kemudian kita pilih titik pusat dengan jarak terpendek. Titik pusat dengan jarak terpendek inilah yang menjadi label bagi titik data yang bersangkutan. Untuk kebutuhan tersebut, karena akan digunakan berkali-kali di perhitungan ini, kita membuatnya dalam bentuk fungsi dalam Python sebagai berikut:
def penyematan(df,pusat):
      # Data x dan data y dipisahkan untuk diproses.
      x = df['x'] # Cara menggambil data kolom x dari dataframe df.
      y = df['y']
     # wadah untuk menampung hasil perihitungan jarak antara
     # setiap data dengan pusat.
     d1 = []
     d2 = []
     d3 = []
     for i in range(len(x)):
     # Perhintungan jarak antara setiap titik data dan setiap pusat
          d1.append(np.sqrt((x[i]-pusat[0][0])**2+(y[i]-pusat[0][1])**2))
          d2.append(np.sqrt((x[i]-pusat[1][0])**2+(y[i]-pusat[1][1])**2))
          d3.append(np.sqrt((x[i]-pusat[2][0])**2+(y[i]-pusat[2][1])**2))
    # Penentuan titik pusat terdekat
          d_min = []
          for i in range(len(x)):
                m = min([d1[i],d2[i],d3[i]])
                if m == d1[i]:
                      d_min.append(1)
                elif m == d2[i]:
                      d_min.append(2)
                elif m == d3[i]:
                      d_min.append(3)
                      # Pembuatan tabel untuk hasil perhingungan jarak dan pusat terdekat.
                      jarak = pd.DataFrame()
                      jarak['d_pusat 1']=d1
                      jarak['d_pusat 2']=d2
                      jarak['d_pusat 3']=d3
                      jarak['pusat terdekat']=d_min
                      # Pengelompokan data-data dengan group yang sama.
                      k1x = []
                      k2x = []
                      k3x = []
                      k1y = []
                      k2y = []
                      k3y = []
                      for i in range(len(x)):
                            if jarak['pusat terdekat'][i] == 1:
                                k1x.append(df['x'][i])
                                k1y.append(df['y'][i])
                            elif jarak['pusat terdekat'][i] == 2:
                                k2x.append(df['x'][i])
                                k2y.append(df['y'][i])
                            elif jarak['pusat terdekat'][i] == 3:
                                k3x.append(df['x'][i])
                                k3y.append(df['y'][i])
                                group = [[k1x,k1y],[k2x,k2y],[k3x,k3y]]
                        return jarak, group
# Menggunakan fungsi penyematan untuk mendapatkan pusat terdekat:
# jarak adalah tabel jarak antara titik data dan pusat serta pusat terdekatnya
# group adalah list himpunan kelompok-kelompok yang terbentuk (untuk pengrafikan).
jarak,group = penyematan(df,pusat)
print("Jarak")
print(jarak.head())
print("Group 1")
print(group[0])
print("Group 2")
print(group[1])
print("Group 3")
print(group[2])
def grafik(group,pusat):
    plt.figure(figsize=(5,5))
    plt.scatter(group[0][0],group[0][1],color = 'r')
    plt.scatter(group[1][0],group[1][1],color = 'b')
    plt.scatter(group[2][0],group[2][1],color = 'g')
    print('catatan',len(group[1][0]),len(group[1][1]))
    x = plt.scatter(pusat[0][0],pusat[0][1],color = 'r',marker= '*',label = 'K1')
    y = plt.scatter(pusat[1][0],pusat[1][1],color = 'b',marker= '*',label = 'K2')
    z = plt.scatter(pusat[2][0],pusat[2][1],color = 'g',marker= '*',label = 'K3')
    print('pusat',pusat,len(pusat))
    print('group',len(group[0]),len(group[1]),len(group[2])) 
    plt.legend(handles = [x,y,z])
    plt.show()
    return
grafik(group,pusat)












Dapat terlihat pada grafik di atas, setiap data telah disemati dengan group sesuai dengan titik pusatnya yang terdekat. Dan terlihat juga bahwa group yang terbentuk belum mempresentasikan struktur kelompok data, oleh karena itu kita perlu memperbaharui titik pusat sedemikian sehingga memperesentasikan struktur data.







Pembaharuan Titik Pusat







Titik pusat yang baru $(x_{p_{baru}},y_{p_{baru}})$ adalah nilai rerata data-data yang termasuk dalam group tersebut. Jadi komponen $x_{p_{baru}}$ dari pusat baru adalah nilai rerata dari semua komponen $x$ data dalam group tersebut, begitu juga komponen $y_{p_{baru}}$.







$$x_{p_{baru}}={\frac{1}{n}}{\sum_{j=1}^{n}x_j}$$



dan







$$y_{p_{baru}}={\frac{1}{n}}{\sum_{j=1}^{n}y_j}$$



dengan $n$ jumlah data dalam group tersebut. Untuk melakukannya kita buat fungsi update pusat sebagai berikut:



def updatePusat(df,jarak,pusat):

      p1x = []

      p2x = []

      p3x = []

      p1y = []

      p2y = []

      p3y = []

      for i in range(len(jarak['pusat terdekat'])):

            if jarak['pusat terdekat'][i] == 1:

               p1x.append(df['x'][i])

               p1y.append(df['y'][i])

            elif jarak['pusat terdekat'][i] == 2:

               p2x.append(df['x'][i])

               p2y.append(df['y'][i])

            elif jarak['pusat terdekat'][i] == 3:

               p3x.append(df['x'][i])

               p3y.append(df['y'][i])

               px = [p1x,p2x,p3x]

               py = [p1y,p2y,p3y]

               for i in range(len(px)):

                     if len(px[i])==0:

                        px[i].append(pusat[i][0])

                        py[i].append(pusat[i][1])

                     #            print('###############################')

                     #            print('#ini dia yang tetap')

                     #            print('###############################')

                        pusat_baru = [[np.mean(px[0]),np.mean(py[0])],                  [np.mean(px[1]),np.mean(py[1])],[np.mean(px[2]),np.mean(py[2])]]

                return pusat_baru

                print('Pusat lama')

                print(pusat)

                pusat_baru = updatePusat(df,jarak,pusat)

                print('Pusat baru: ')

                print(pusat_baru)

















untuk melihatnya hasil agar lebih jelas, mari kita grafikan dengan fungsi grafik yang sudah dibuat:



grafik(group,pusat)











grafik(group,pusat_baru)







Kemudian kita sematkan lagi data-data dengan pusat yang baru.



jarak_baru,group_baru = penyematan(df,pusat_baru)



seperti terlihat pada grafik berikut, grup yang terbentuk sudah semakin baik, namun pusat belum tentu mempresentasikan pusat sesungguhnya.



grafik(group_baru,pusat_baru)







Supaya memastikan titik pusat adalah representasi dari kelompok-kelompok yang terbentuk, maka kita perlu mengulang-ulang pembaruan pusat sampai pada batas yang diinginkan. Untuk melakukannya kita membuat fungsi lagi untuk melakukan pengulangan dan penyematan berulang-ulang hingga pusat yang terbentuk konvergen (perubahan yang terjadi tidak berarti).



def iterasi(jarak,df,pusat):

      while True:

            pusat_terdekat = jarak['pusat terdekat'].copy(deep=True)

            pusat = updatePusat(df,jarak, pusat)

            jarak,group = penyematan(df,pusat)

            grafik(group,pusat)

            if pusat_terdekat.equals(jarak['pusat terdekat']):

                  break

                       return pusat, jarak, group

                       pusat, jarak, group = iterasi(jarak,df,pusat)











Model

Di awal kita sudah menyebutkan salah satu kelemahan k-means adalah sensitif terhadap pemilihan pusat awal. Jadi pemilihan pusat awal bisa menghasilkan struktur yang tidak mempresentasikan struktur kelompok-kelompok data, untuk mengatasinya, salah satunya adaah dengn cara mengulang proses di atas dari awal sampai akhir berkali-kali dan kita ambil titik pusat yang mayoritas membentuk kelompok yang sama.



from collections import Counter

def pembelajaran(df):

      x = df['x']

      y = df['y']

      it = 100

      pusat_g = []

      jarak_g = []

      group_g = []

      index_g = []

      for i in range(it):

           #=========================# Inisiasi #========================

           print('Inisiasi----------------------------------------------')

           #        k = 3

           #np.random.seed(200)

           c1 = [np.random.randint(0,80),np.random.randint(0,80)]

           c2 = [np.random.randint(0,80),np.random.randint(0,80)]

           c3 = [np.random.randint(0,80),np.random.randint(0,80)]

           pusat = [c1,c2,c3]

           plt.figure(figsize=(5,5))

           plt.scatter(x,y,color = 'k')

           plt.scatter(c1[0],c1[1],color = 'r',marker= '*')

           plt.scatter(c2[0],c2[1],color = 'b',marker= '*')

           plt.scatter(c3[0],c3[1],color = 'g',marker= '*')

           plt.show()

           # ================ # Penyematan #============================

           print('Penyematan--------------------------------------------')

           jarak, group = penyematan(df,pusat)

           grafik(group,pusat)

           pusat,jarak,group = iterasi(jarak,df,pusat)

           pusat_g.append(pusat)

           group_g.append(group)

           jarak_g.append(jarak)

           pus = list(jarak['pusat terdekat'])

           #        print(pus)

           satu = []

           dua = []

           tiga = []

           for j in range(len(pus)):

                 if pus[j] == 1:

                     satu.append(j)

                 elif pus[j] == 2:

                     dua.append(j)

                 else:

                     tiga.append(j)

                     index_g.append([sorted(satu),sorted(dua),sorted(tiga)])

            index_g2 = []

            for i in index_g:

                  index_g2.append(sorted(i))

                  counter = Counter(str(e) for e in index_g2)

                  counter_keys = list(counter.keys())

                  counter_values = list(counter.values())

                  max_conter_values = max(counter_values)

                  ind_max = counter_values.index(max_conter_values)

                  index_max = counter_keys[ind_max]

            index_g2_string = []

            for i in index_g2:

                  index_g2_string.append(str(i))

            group_model = []

            pusat_model = []

            for i in range(len(index_g2_string)):

                  if index_g2_string[i] == index_max:

                       group_model.append(index_g2[i])

                       pusat_model.append(pusat_g[i])

             pusat_model_set = []

             for i in pusat_model:

                   pusat_model_set.append(sorted(i))

              pusat_model_unik = []

              for i in pusat_model_set:

                    if i not in pusat_model_unik:

                         pusat_model_unik.append(i)

                    if len(pusat_model_unik) == 1:

                        print("Model telah sukses dibuat.")

              pusat_model_unik = pusat_model_unik[0]

              print(pusat_model_unik,'pusat unik')

              print('Group mayoritas yang terbentuk')

              print(counter_keys)

              print('Jumlah populasi group yang konvergen pada kelompok yang sama dengan iterasi', it)

              print('sebanyak',max_conter_values,'populasi')

              print('-----------------------------------------------------')

              print('Gambaran model yang terbentuk')

              jarak, group_terakhir = penyematan(df,pusat_model_unik)

              grafik(group_terakhir,pusat_model_unik)

              print('-----------------------------------------------------')

              return pusat_model_unik

              model_kmeans = pembelajaran(df)



coba running code diatas wkwkwkwkwkwk











model_kmeans







diatas adalah gambaran model k-mean yang terbentuk, jika kita punya sebuah inputan data baru, maka model tersebutkan akan menempatkan data tersebut kedalam kelompok yang merepresentasi nilai dari model.







misalkan:







bikin data baru



data_baru = pd.DataFrame()

xi = [80]

yi = [60]

data_baru['x'] = xi

data_baru['y'] = yi



prediksikan data baru berdasarkan model yang terbentuk



def predict(data_baru,model_kmeans):

    jarak,group = penyematan(data_baru,model_kmeans)

    kelompok = jarak['pusat terdekat'][0]

    return kelompok











sampai tahapan diatas kita telah mempelajari mengenai langkah-langkah k-mean.



pada saat ini sangat banyak library yang memberikan kemudahan untuk melakukan komputasi k-mean, salah satu contoh:







library sklearn pada python.



from sklearn.cluster import KMeans

kmeans = KMeans(n_clusters =3)

kmeans.fit(df)

labels = kmeans.predict(df)

centroids = kmeans.cluster_centers_

fig = plt.figure(figsize=(5, 5))

colmap = {1: 'r', 2: 'g', 3: 'b'}

colors = list(map(lambda x: colmap[x+1], labels))

plt.scatter(df['x'], df['y'], color=colors, alpha=0.5, edgecolor='k')

for idx, centroid in enumerate(centroids):

    plt.scatter(*centroid, color=colmap[idx+1])

plt.xlim(0, 100)

plt.ylim(0, 100)

plt.show()







silahkan mencoba mempelajari nya.







note:

kmeans sangat sensitif terhadap skala karena menggunakan jarak euclid oleh karena itu diperlukan normalisasi data.



Jika ada simetri pada data, beberapa data mungkin akan kelewatan dilabeli.



Direkomendasikan menggunakan k-means yang sama dengan titik pusat awal yang berbeda-beda, dan dipilih yang paling umum.







semoga bisa bermanfaat.







Baca juga:





















0
komentar



























 Emoticon