Linear Regression Series - Part 2/5: Implementasi Algoritma Linear Regression

Bagaimana cara komputer dapat merumuskan model dan membuat garis seperti yang kita buat pada postingan sebelumnya? Secara garis besar sama. Mulailah dengan garis acak. Pilih titik acak dalam himpunan data dan pindahkan garis sedikit lebih dekat ke satu titik itu. Ulangi proses ini berkali-kali, selalu pilih titik acak dalam himpunan data. Pseudocode dan ilustrasinya adalah sebagai berikut.

Input: Himpunan titik data pada bidang

Output: Garis yang melewati titik-titk sedekat mungkin

Procedure: 

• Pilih garis secara acak
• Ulangi berkali-kali:
• Pilih titik data secara acak
• Pindahkan garis sedikit lebih dekat ke titik itu
• Return garis yang telah diperoleh.

Ilustrasi

Itu adalah gambaran umumnya. Untuk mempelajari prosesnya dengan lebih detail, kita perlu menggunakan matematika. Tenang, bukan matematika yang rumit. Mari mulai dengan mendefinisikan beberapa variabel

• p: harga sebuah rumah dalam dataset
• p̂: prediksi harga rumah
• k: jumlah kamar
• m: harga per kamar (bobot)
• b: harga dasar rumah (bias)

Dengan demikian, model yang akan memprediksi harga rumah dapat dirumuskan ke dalam persamaan berikut:

Jika teman-teman ingat, awal mula rumus di atas juga telah kita pelajari pada bagian pertama dan dapat kita artikan sebagai berikut

Supaya lebih jelas, katakanlah kita memiliki model yang mana harga per kamar adalah 80 juta dan harga dasar rumah adalah 500 juta. Dengan demikian model prediktif dapat kita rumuskan sebagai berikut.

Untuk mengilustrasikan algoritma ini, bayangkan di dalam dataset kita terdapat rumah dengan  2 kamar yang dijual dengan harga 680 juta. Sedangkan jika kita hitung menggunakan formula model di atas, harga rumah yang diprediksi adalah (80 x 2) + 500 = 660. Bukan prediksi yang buruk, namun terdapat selisih 20 juta antara prediksi dan harga sesungguhnya. Bagaimana kita dapat meningkatkan model? Tampaknya model yang kita miliki memprediksi harga rumah terlalu murah. Mungkin model memiliki harga dasar yang terlalu rendah, mungkin juga harga per kamar terlalu murah, atau mungkin keduanya. Jika kita menambahkan sejumlah angka pada keduanya (harga dasar dan harga per kamar), mungkin saja kita dapat menghasilkan estimasi yang lebih baik. Mari kita tambahkan harga per kamar sebanyak 2 juta dan harga dasar rumah kita tambahkan sebanyak 10 juta (angka dipilih secara acak). Dengan demikian, persamaan model baru kita menjadi seperti berikut:

Dengan model baru ini, prediksi yang kita dapatkan adalah (82 x 2) + 510 = 674. Karena 674 juta lebih dekat dengan 680 juta, maka model baru ini lebih baik untuk titik data tersebut. Namun kita tidak tau apakah ini model yang lebih baik untuk titik data lainnya. Saat ini, tidak perlu khawatir dengan hal tersebut. Ide dari algoritma Linear Regression adalah mengulangi proses sebelumnya berkali-kali. Pseudocode dari algoritma Linear Regression berikut:

Input: Himpunan titik data

Output: Model Linear Regression yang sesuai dengan himpunan data

Procedure: 

• Pilih model dengan bobot acak dan bias acak.
• Ulangi berkali-kali:
• Pilih titik data acak.
• Sedikit sesuaikan bobot dan bias untuk meningkatkan prediksi pada titik data tertentu.
• Return model yang telah diperoleh.

Memindahkan garis menggunakan slope dan y-intercept

Pada postingan sebelumnya, kita sempat menyinggung persamaan baris. Sekarang, kita akan belajar bagaimana cara memanipulasi persamaan ini untuk memindahkan garis. Coba kita ingat kembali, pada persamaan baris, kita memiliki 2 komponen, yaitu:

• Slope (bobot)
• y-intercept (bias)

Slope atau kemiringan memberitahu kita seberapa curam garis tersebut. Slope diperoleh dengan membagi besar unit kenaikan dengan besar unit ke kanan. Sedangkan y-intercept memberitahu kita di mana garis berada saat melintasi sumbu y (sumbu vertikal). Kita akan melihat contoh keduanya pada gambar di bawah. Katakanlah terdapat garis dengan persamaan sebagai berikut:

y = 0.5x + 2

Sumber gambar: Grokking Machine Learning

Apa arti dari persamaan garis di atas? Itu berarti garis tersebut memiliki slope 0.5 dan y-intercept nya adalah 2.

Ketika kita mengatakan slope-nya adalah 0.5, ini artinya setiap kali kita berpindah ke kanan sebanyak 1 unit, maka kita akan naik sebanyak 0.5 unit. Slope dapat bernilai 0 jika kita tidak berpindah ke atas sama sekali, dan menjadi negatif saat kita berpindah ke bawah. Banyak garis yang dapat memiliki slope yang sama. Jika kita menggambar garis apa pun yang sejajar dengan garis pada gambar di atas, maka garis-garis ini juga akan memiliki slope 0.5 setiap kali kita bergerak ke kanan. Di sinilah peran y-intercept. Y-intercept memberitahu kita di mana garis memotong sumbu y. Pada gambar di bawah ini, kita dapat melihat garis yang berbeda dengan y-intercept yang sama dan garis yang berbeda dengan kemiringan yang sama.

Sumber gambar: Grokking Machine Learning

Dengan kata lain, slope memberitahu arah di mana garis itu menunjuk. Sedangkan y-intercept memberitahu kita lokasi garis itu.

Dalam contoh kasus kita, slope merepresentasikan harga per kamar, dan y-intercept merepresentasikan harga dasar rumah. Dari penjabaran di atas, kita dapat menarik kesimpulan seperti berikut:

Mengubah Slope:

• Jika kita menambahkan slope pada garis, maka garis akan berputar berlawanan arah jarum jam.
• Jika kita mengurangi slope pada garis, maka garis akan berputar searah jarum jam.

Mengubah y-intercept:

• Jika kita menambahkan y-intercept pada garis, maka garis tersebut akan beralih ke atas.
• Jika kita mengurangi y-intercept pada garis, maka garis tersebut akan beralih ke bawah.

Gambar di bawah mengilustrasikan perputaran dan peralihan garis.

Sebagaimana dijelaskan sebelumnya, secara umum, persamaan garis dinyatakan dengan

y = mx + b

di mana x dan y adalah sumbu horizontal dan vertikal pada koordinat, m adalah slope, dan b adalah y-intercept. Selanjutnya, pada postingan ini, persamaan garis akan kita tuliskan dengan formula berikut:

p̂ = mk + b

di mana p̂ adalah prediksi harga rumah, k adalah jumlah kamar, m (slope) adalah harga per kamar, dan b (y-intercept) adalah harga dasar rumah.

Memindahkan garis mendekati titik

Ada beberapa metode yang dapat digunakan untuk memindahkan garis mendekati titik.

Metode 1: Simple Trick

Ini merupakan metode yang paling sederhana. Kita cukup melihat posisi titik terhadap garis. Metode ini dapat diringkas ke dalam 4 kasus berikut:

• Kasus 1: Jika titiknya berada di atas garis dan di kanan sumbu y, maka garis berputar berlawanan arah jarum jam dan beralih ke atas.
• Kasus 2: Jika titiknya berada di atas garis dan di kiri sumbu y, maka garis berputar searah jarum jam dan beralih ke atas.
• Kasus 3: Jika titiknya berada di bawah garis dan di kanan sumbu y, maka garis berputar searah jarum jam dan beralih ke bawah.
• Kasus 4: Jika titiknya berada di bawah garis dan di kiri sumbu y, maka garis berputar berlawanan arah jarum jam dan beralih ke bawah.

Untuk metode ini, cukup mudah dibayangkan ya, teman-teman. Dengan menggunakan 4 kasus di atas, kita dapat membuat pseudocode seperti di bawah ini.

Input:

• Sebuah garis dengan slope m, y-intercept b, dan persamaan p̂ = mk + b
• Sebuah titik dengan koordinat (k, h); k = jumlah kamar, h= harga rumah

Output:

• Bobot model (harga per kamar dan harga dasar) baru untuk persamaan p̂ = m'k + b' yang telah mendekati titik.

Procedure: 

    Pilih 2 angka yang sangat kecil secara acak, yaitu  η1 dan η2

    Jika titiknya berada di atas garis dan di kanan sumbu y (Kasus 1):

• Tambahkan η1 dengan slope m. Diperoleh m' = m + η1
• Tambahkan η2 dengan y-intercept b. Diperoleh b' = b + η2

    Jika titiknya berada di atas garis dan di kiri sumbu y (Kasus 2):

• Kurangkan η1 dari slope m. Diperoleh m' = m - η1
• Tambahkan η2 dengan y-intercept b. Diperoleh b' = b + η2

    Jika titiknya berada di bawah garis dan di kanan sumbu y (Kasus 3):

• Kurangkan η1 dari slope m. Diperoleh m' = m - η1
• Kurangkan η2 dari y-intercept b. Diperoleh b' = b - η2

    Jika titiknya berada di bawah garis dan di kiri sumbu y (Kasus 4):

• Tambahkan η1 dengan slope m. Diperoleh m' = m + η1
• Kurangkan η2 dari y-intercept b. Diperoleh b' = b - η2

    Return Bobot model baru untuk persamaan p̂ = m'k + b'

Jika diterjemahkan ke dalam bahasa python, maka akan menjadi seperti snippet kode di bawah ini.

def simple_trick(base_price, price_per_room, num_rooms, price):
    small_random_1 = random.random()*0.1
    small_random_2 = random.random()*0.1
    predicted_price = base_price + price_per_room*num_rooms
    if price > predicted_price and num_rooms > 0:
        price_per_room += small_random_1
        base_price += small_random_2
    if price > predicted_price and num_rooms < 0:
        price_per_room -= small_random_1
        base_price += small_random_2
    if price < predicted_price and num_rooms > 0:
        price_per_room -= small_random_1
        base_price -= small_random_2
    if price < predicted_price and num_rooms < 0:
        price_per_room -= small_random_1
        base_price += small_random_2
    return price_per_room, base_price

Metode ini dapat dilakukan, namun ini bukan metode yang terbaik. Bukankah langkahnya terlalu panjang? Dapatkan kita menggunakan langkah-langkah yang lebih singkat? Tentu! Kita beralih ke metode berikutnya.

Metode 2: Square Trick

Memanipulasi y-intercept

Pada metode 1, ketika titik berada di atas garis, maka kita menambahkan angka kecil ke y-intercept dan ketika titik berada di bawah garis, maka kita mengurangkannya dengan sebuah angka kecil.

Pada metode 2, harap perhatikan dengan seksama, jika titik berada di atas garis, maka nilai dari p - p̂ (selisih antara harga aktual dengan harga prediksi) adalah positif. Dan jika titik di bawah garis, maka nilainya akan negatif. Mohon diresapi betul, dan jangan dilanjutkan jika masih bingung.

Berdasarkan penjabaran di atas, kita dapat menyimpulkan bahwa jika nilai dari p - p̂ kita tambahkan dengan y-intercept, maka garis akan selalu berpindah mendekati titik. Sepakat? Sepakat ya. Misalnya saja, y-interceptnya 2, dan p - p̂ = 3 (selisihnya positif, berarti titiknya di atas). Sekarang tambahkan y-intercept dan p - p̂ tadi, 2+3 = 5. Nah, berarti y-intercept yang sekarang kan 5, garisnya naik, titiknya di atas, berarti garis akan mendekati titik. Begitu pula jika p - p̂ negatif, berarti titiknya berada di bawah garis. Jika y-intercept ditambahkan nilai  dari p - p̂ yang negatif tadi, berarti nilai y-intercept yang baru akan berkurang dari sebelumnya, dengan demikian garisnya akan turun mendekati titik.

Pada machine learning, kita selalu mengambil langkah-langkah kecil, baby steps. Untuk itu, kita akan berkenalan dengan konsep baru yang sangat penting, yaitu Learning Rate.

Learning Rate adalah angka yang sangat kecil yang kita pilih sebelum melatih model. Angka ini membantu kita memastikan model kita berubah dalam jumlah yang sangat kecil melalui pelatihan. Dengan kata lain, garis akan berpindah posisi dengan sangat perlahan.

Notasi yang akan digunakan untuk learning rate pada pembahasan kali ini adalah η.

Karena nilai learning rate ini sangat kecil, begitu pula dengan nilai η(p - p̂). Nilai ini akan ditambahkan dengan y-intercept untuk memindahkan garis mendekati titik.

Memanipulasi slope

Pada metode 1, di kasus 1 atau 4 (titik di atas dan di kanan sumbu y atau titik di bawah dan di kiri sumbu y), kita memutar garis berlawanan arah jarum jam. Sebaliknya di kasus 2 atau 3, kita memutar garis searah jarum jam. 

Pada metode 2, jika titik (k, h) berada di kanan sumbu y, maka nilai k adalah positif. Jika titik berada di kiri sumbu y, maka k bernilai negatif. Hal ini diilustrasikan pada gambar di bawah. Dalam kasus kita, nilai k tidak mungkin negatif, karena k adalah jumlah kamar. Namun, untuk kasus-kasus lainnya, fitur bisa juga bernilai negatif.

Sekarang lihatlah nilai k(p - p̂). Hasilnya akan positif jika k maupun (p - p̂), keduanya bernilai positif atau keduanya bernilai negatif (perkalian negatif dan negatif hasilnya positif). Inilah tepatnya yang terjadi pada kasus 1 dan kasus 4 pada metode 1. Begitu pula, k(p - p̂) bernilai negatif pada kasus 2 dan kasus 3 di metode 1. Oleh sebab itu, inilah kuantitas yang akan ditambahkan ke slope. Namun kita ingat, machine learning selalu menginginkan langkah kecil. Untuk itu, sekali lagi, kita akan mengalikannya dengan learning rate sehingga menjadi ηk(p - p̂). Nilai ini akan ditambahkan dengan slope untuk memindahkan garis mendekati titik.

Sekarang kita dapat membuat pseudocode untuk metode 2 seperti di bawah ini.

Input:

• Sebuah garis dengan slope m, y-intercept b, dan persamaan p̂ = mk + b
• Sebuah titik dengan koordinat (k, h); k = jumlah kamar, h= harga rumah
• Sebuah angka positif kecil η (learning rate)

Output:

• Bobot model (harga per kamar dan harga dasar) baru untuk persamaan p̂ = m'k + b' yang telah mendekati titik.

Procedure: 

• Tambahkan ηk(p - p̂) dengan slope m. Diperoleh m' = m + ηk(p - p̂) (Operasi ini akan memutar garis searah atau berlawanan arah jarum jam)
• Tambahkan η(p - p̂) dengan y-intercept b. Diperoleh b' = b + η(p - p̂) (Operasi ini akan memindahkan garis ke atas dan ke bawah)

    Return Bobot model baru untuk persamaan p̂ = m'k + b'

Jika pseudocode di atas diterjemahkan ke dalam bahasa python, maka akan menjadi seperti ini.

def square_trick(base_price, price_per_room, num_rooms, price, learning_rate):
    #perbarui model
    predicted_price = base_price + price_per_room*num_rooms
    
    #perbarui slope (harga per kamar)
    price_per_room += learning_rate*num_rooms*(price-predicted_price)
    
    #perbarui y-intercept (harga dasar rumah)
    base_price += learning_rate*(price-predicted_price)
    
    return price_per_room, base_price

Baiklah, teman-teman. Karena metode kedua ini cukup efektif, maka untuk selanjutnya kita akan menggunakan metode ini.

Algoritma Linear Regression: Menjalankan Square Trick berulang kali untuk memindahkan garis mendekati titik

Setelah penjelasan panjang lebar di atas, sekarang kita dapat mengembangkan algoritma linear regression. Algoritma ini memiliki input sekelompok titik dan mengembalikan garis yang cocok untuk titik-titik itu. Dimulai dengan memilih nilai acak untuk slope dan y-intercept, kemudian mengulangi prosedur, dan memperbarui nilainya berulang kali menggunakan square trick. Ringkasnya, lihat pseudocode di bawah.

Input:

• Dataset rumah dengan jumlah kamar dan harganya

Output:

• Bobot Model: harga per kamar dan harga dasar rumah

Procedure: 

• Mulai dengan nilai acak untuk slope dan y-intercept
• Ulangi beberapa kali:
• Ambil titik data secara acak.
• Perbarui nilai slope dan y-intercept menggunakan square trick.
• Return bobot model

Setiap iterasi pada perulangan akan kita sebut sebagai epoch, yang mana nilainya akan kita tentukan di awal. Di bawah ini adalah snippet kode untuk algoritma linear regression. Kita menggunakan package random pada python untuk menghasilkan angka acak yang akan digunakan sebagai nilai awal (slope dan y-intercept) serta untuk memilih titik data kita secara acak pada saat perulangan. Kita menggunakan random.seed() supaya angka acak yang dihasilkan selalu tetap meskipun kita jalankan berulang-ulang, jika tidak, maka setiap kali kita menjalankannya, hasilnya akan sedikit berbeda karena angka yang dipilih berbeda.

import random
random.seed(1)
def linear_regression(features, labels, learning_rate=0.01, epochs = 1000):
    #ambil nilai slope secara acak
    price_per_room = random.random()
    
    #ambil nilai y-intercept secara acak
    base_price = random.random()
    
    for epoch in range(epochs):
        #pilih titik data secara acak
        i = random.randint(0, len(features)-1)
        
        num_rooms = features[i]
        price = labels[i]
        
        #Perbarui nilai slope dan y-intercept menggunakan square trick.
        price_per_room, base_price = square_trick(base_price,
                                                  price_per_room,
                                                  num_rooms,
                                                  price,
                                                  learning_rate=learning_rate)
    return price_per_room, base_price

Langkah selanjutnya adalah menjalankan algoritma ini untuk membangun model yang sesuai dengan dataset kita.

Pada pembahasan ini, kita akan menggunakan package NumPy dan Matplotlib pada python. NumPy digunakan untuk menyimpan data array dan menjalankan operasi matematika, dan Matplotlib akan kita gunakan untuk membuat plot.

Hal pertama yang kita lakukan adalah membuat dataset (sampel). Nanti kita akan menggunakan dataset sungguhan di part lain, namun untuk saat ini kita mulai dengan contoh sederhana.

import random
import numpy as np
features = np.array([1,2,3,5,6,7]) #jumlah kamar
labels = np.array([1.55, 1.97, 2.44, 3.56, 4.07, 4.48]) #harga rumah dalam milyar

Selanjutnya, kita akan membuat plot menggunakan kode di bawah ini.

import random
import matplotlib
from matplotlib import pyplot

def draw_line(slope, y_intercept, color='grey', linewidth=0.7, starting=0, ending=8):
    x = np.linspace(starting, ending, 1000)
    pyplot.plot(x, y_intercept + slope*x, linestyle='-', color=color, linewidth=linewidth)

def plot_points(features, labels):
    X = np.array(features)
    y = np.array(labels)
    pyplot.scatter(X, y)
    pyplot.xlabel('jumlah kamar')
    pyplot.ylabel('harga')

Ketika dijalankan, kita akan mendapatkan plot seperti di bawah.

Sekarang, mari kita terapkan algoritma linear regression untuk dataset kita dengan memanggil fungsi linear_regression yang telah kita buat sebelumnya.

linear_regression(features, labels, learning_rate = 0.01, epochs = 1000)

Kita memilih learning rate 0.01 dan epoch 1.000, itu berarti, perulangan akan dilakukan sebanyak 1.000 kali. Ketika dijalankan, kita akan mendapatkan balikan harga per kamar dan harga dasar rumah seperti berikut.

Jika kita bulatkan, harga per kamar yang didapatkan adalah 0.51 Milyar dan harga dasar rumah adalah 0.99 Milyar. Hasil ini tidak jauh berbeda dengan 0.5 Milyar dan 1 Milyar seperti yang kita lihat pada postingan sebelumnya (Baca bagian pertama). Sampel dataset yang kita gunakan sama dengan yang di postingan sebelumnya.

Untuk memvisualisasikan prosesnya, mari kita lihat perkembangannya sedikit lebih detail. Pada gambar di bawah, kita dapat melihat beberapa garis perantara. Perhatikan bahwa garis dimulai jauh dari titik. Seiring perkembangan algoritma, ia bergerak perlahan agar lebih pas dan lebih baik setiap saat. Perhatikan bahwa pada awalnya (dalam 10 epoch pertama), garis bergerak cepat menuju solusi yang baik. Setelah epoch 50, garisnya bagus, tetapi masih belum terlalu sempurna dan tampak dilema. Jika kita membiarkannya berjalan selama 1.000 epoch, garisnya menjadi sangat cocok.

Hasil akhir:

Menggunakan Model untuk membuat Prediksi

Sekarang kita memiliki model regresi linier yang cukup baik untuk membuat prediksi! Ingatlah dari awal blog series ini bahwa tujuan kita adalah untuk memprediksi harga rumah dengan 4 kamar. Pada hasil di atas, kita memperoleh slope (harga per kamar) 0.51 M dan y-intercept (harga dasar rumah) 0.99 M. Dengan demikian, persamaannya menjadi seperti di bawah ini.

p̂ = 0.51 ⋅ k + 0.99

Prediksi model untuk rumah dengan 4 kamar adalah

p̂ = 0.51 ⋅ 4 + 0.99 = 3.03 Milyar

3.03 Milyar tidak terlalu jauh dengan estimasi awal kita pada postingan sebelumnya.

Selanjutnya, bagaimana kita mengukur seberapa baik model yang kita buat? Kita akan mempelajarinya di bagian berikutnya.

Full Code: Linear Regression Introduction Code

See you~

Referensi

• Grokking Machine Learning (Luis G. Serrano)
• Linear Regression (Serrano Academy)
• Polynomial Regression (Ahmad Bazzi)