Ann_perceptron.docx

DATA MINING ALGORITMA PERCEPTRON

Oleh: Kadek Alit Sudiyana

1605551044

Imelda Alvionita Tarigan

1605551046

I Made Jaladhi Kori

1605551051

MD. Wira Putra Dananjaya

1605551056

Evan Himawan Saragih

1605551060

I Made Ari Saputra

1605551064

Anak Agung Ketut Krishna Dwipayana

1605551072

I Putu Yoga Pertama Yasa

1605551081

I Kadek Supadma

1605552031

PROGRAM STUDI TEKNOLOGI INFORMASI FAKULTAS TEKNIK UNIVERSITAS UDAYANA 2019

Algoritma Perceptron Perceptron adalah salah satu metode Jaringan Syaraf Tiruan (JST) sederhana yang menggunakan algoritma training untuk melakukan klasifikasi secara linier. Perceptron digunakan untuk melakukan klasifikasi sederhana dan membagi data untuk menentukan data mana yang masuk dalam klasifikasi dan data mana yang missclasifikasi (diluar klasifikasi). Model perceptron terdiri dari beberapa unit input x1, x2, ..., xn (ditambah sebuah bias yang bernilai 1) dan memiliki sebuah unit output Y. Setiap unit input dihubungkan ke unit output dengan bobot masing-masing (b, w1, w2, ..., wn). Selama proses pembelajaran, bobot-bobot tersebut akan dimodifikasi untuk meningkatkan keakuratan hasil.

Gambar 1 Model Perceptron

Model perceptron tersebut dapat digunakan untuk mengklasifikasikan setiap pola input, apakah pola input tersebut berada pada suatu kelas atau tidak. Jika suatu pola input berada pada kelas tertentu maka unit output akan memberikan respon bernilai +1. Sedangkan, jika pola input tidak berada pada kelas tertentu maka nilai respon yang diberikan oleh unit output adalah -1.

Untuk melakukan klasifikasi terhadap suatu pola input, model perceptron menggunakan pembelajaran dengan teknik iterasi. Vektor input yang digunakan dapat bernilai biner (0, 1) atau bipolar (-1, 0, 1). Sedangkan output yang dihasilkan bernilai bipolar. Algoritma pembelajaran perceptron dengan s sebagai vektor input dan t sebagai vektor output adalah sebagai berikut:

1.

Inisialisasi nilai semua bobot dan bias (biasanya b = wi = 0 ) Tentukan laju pemahaman 𝛼(0 < 𝛼 ≤ 1) (biasanya 𝛼 = 1)

2.

Selama ada elemen vektor input yang memiliki nilai respon output yang berbeda dengan target, lakukan langkah 3 – 5

3.

Tetapkan aktivasi dari unit input: 𝑥𝑖 = 𝑠𝑖

4.

Hitung respon dari unit output 𝑦_𝑖𝑛 = 𝑏 + ∑ 𝑥𝑖 𝑤𝑖 𝑖

𝑗𝑖𝑘𝑎 𝑦_𝑖𝑛 1 𝑗𝑖𝑘𝑎 𝜃 ≤ 𝑦_𝑖𝑛 ≤ 𝜃 (𝑦_𝑖𝑛) 𝑦=𝑓 = {0 −1 𝑗𝑖𝑘𝑎 𝑦_𝑖𝑛 < 𝜃 5.

Perbarui nilai bobot dan bias pada pola yang mengandung kesalahan 𝐼𝑓 𝑦 ≠ 𝑡, 𝑤𝑖 (𝑏𝑎𝑟𝑢) = 𝑤𝑖 (𝑙𝑎𝑚𝑎) + 𝛼𝑡𝑥𝑖 𝑏(𝑏𝑎𝑟𝑢) = 𝑏(𝑙𝑎𝑚𝑎) + 𝛼𝑡 𝑒𝑙𝑠𝑒 𝑤𝑖 (𝑏𝑎𝑟𝑢) = 𝑤𝑖 (𝑙𝑎𝑚𝑎) 𝑏(𝑏𝑎𝑟𝑢) = 𝑏(𝑙𝑎𝑚𝑎)

6.

Tes kondisi berhenti: jika tidak terjadi perubahan bobot pada (i) maka kondisi berhenti TRUE, namun jika masih terjadi perubahan maka kondisi berhenti FALSE

Untuk lebih memahami mengenai klasifikasi berbasis ANN dengan menggunakan model perceptron, berikut ini akan diberikan dua buah contoh klasifikasi untuk masalah pengenalan pola. Contoh pertama menggunakan model perceptron dengan output tunggal. Sedangkan contoh kedua menggunakan model perceptron dengan output majemuk.

Contoh 1: Klasifikasi dengan Model Perceptron Output Tunggal Model perceptron berikut akan dilatih untuk mengenali apakah pola input yang diberikan adalah pola karakter “-”.

Gambar 2 Pola 1 Dan Pola 2

Unit input dan unit output yang digunakan bernilai bipolar sehingga kotak yang berwarna hijau akan bernilai +1. Sedangkan kotak berwarna biru bernilai -1. Bobot (w) dan bias (b) awal diinisialisasi dengan 0. Learning rate (α) diinisialisasi dengan 1 dan threshold (θ) diinisialisasi dengan 0. Bentuk pola input dan target yang digunakan untuk mengenali pola “-” diberi nilai, untuk target bernilai 1 berarti pola input dikenali sebagai pola “-”. Sedangkan target bernilai -1 berarti pola input tidak dikenali sebagai pola “-”.

Pola Input

Target (t)

Pola 1

1

Pola 2

-1

Iterasi yang dilakukan pada proses pelatihan untuk mengenali pola “-” adalah sebagai berikut. Penyelesaian: 1.

Inialisasi:

b=wi = 0, dengan i=1,2,3,..,9. α=1; θ=0

Epoch 1 2.

Hitung respon dari unit output untuk pola input 1: [-1,-1,-1,1,1,1,-1,-1,-1] y_in = 0 + (-1*0)+ (-1*0) + (-1*0) + 1*0 + 1*0 + 1*0 + (-1*0) + (-1*0) + (-1*0) =0 Karena syarat θ ≤ y_in ≤ θ, maka y=0

3.

Karena y ≠ t maka menghitung perubahan bobot. If y ≠ t, wi(baru) = wi(lama) + α*t*xi b(baru) = b(lama) + a*t else wi(baru) = wi(lama) b(baru) = b(lama) b(baru) = 0 + 1*1 = 1 w1(baru) = 0 + 1*1*-1 = -1 w2(baru) = 0 + 1*1*-1 = -1 w3(baru) = 0 + 1*1*-1 = -1 w4(baru) = 0 + 1*1*1 = 1 w5(baru) = 0 + 1*1*1 = 1 w6(baru) = 0 + 1*1*1 = 1 w7(baru) = 0 + 1*1*-1 = -1 w8(baru) = 0 + 1*1*-1 = -1 w9(baru) = 0 + 1*1*-1 = -1

4.

Hitung respon dari unit output untuk pola input 2 dengan b(baru) dan w(baru): [1,1,1,-1,-1,-1,1,1,1] y_in = 1 + (-1*1) + (-1*1) + (-1*1) + 1*-1 + 1*-1 + 1*-1 + (-1*1) + (-1*1) + (-1*1) = -8 Karena syarat y_in ˂θ, maka y= -1 Karena y = t maka tidak perlu dilakukan perubahan bobot. b(baru) = b(lama) w1(baru) = w1(lama) w2(baru) = w2(lama) w3(baru) = w3(lama) w4(baru) = w4(lama) w5(baru) = w5(lama)

w6(baru) = w6(lama) w7(baru) = w7(lama) w8(baru) = w8(lama) w9(baru) = w9(lama) Epoch 2 1.

Hitung respon dari unit output untuk pola input 1: [-1,-1,-1,1,1,1,-1,-1,-1] y_in = 1 + (-1*-1) + (-1*-1) + (-1*-1) + 1*1 + 1*1 + 1*1 + (-1*-1) + (-1*-1) + (-1*1) = 10 Karena syarat y_in ˃ θ, maka y=1

2.

Karena y = t maka tidak perlu dilakukan perubahan bobot. b(baru) = b(lama) w1(baru) = w1(lama) w2(baru) = w2(lama) w3(baru) = w3(lama) w4(baru) = w4(lama) w5(baru) = w5(lama) w6(baru) = w6(lama) w7(baru) = w7(lama) w8(baru) = w8(lama) w9(baru) = w9(lama)

3.

Hitung respon dari unit output untuk pola input 2 dengan b(baru) dan w(baru): [1,1,1,-1,-1,-1,1,1,1] y_in = 1 + (-1*1) + (-1*1) + (-1*1) + 1*-1 + 1*-1 + 1*-1 + (-1*1) + (-1*1) + (-1*1) = -8 Karena syarat y_in ˂θ, maka y= -1 Karena y = t maka tidak perlu dilakukan perubahan bobot. b(baru) = b(lama) w1(baru) = w1(lama) w2(baru) = w2(lama) w3(baru) = w3(lama) w4(baru) = w4(lama) w5(baru) = w5(lama) w6(baru) = w6(lama) w7(baru) = w7(lama) w8(baru) = w8(lama) w9(baru) = w9(lama)

Pada epoch ke-2, ternyata setiap vektor input telah mampu menghasilkan nilai respon output yang sesuai dengan target yang diharapkan dan tidak terjadi lagi perubahan bobot. Sehingga proses pelatihan tidak perlu dilanjutkan ke epoch ke-3. Hal ini menandakan bahwa perceptron telah mampu mengklasifikasikan mana pola yang berada di kelas “-” dan yang bukan di kelas “-”.

Bias akhir yang dihasilkan = 1 Bobot akhir yang dihasilkan adalah sebagai berikut. [-1,-1,-1,1,1,1,-1,-1,-1]

Langkah-langkah bawah ini merupakan pelatihan pada contoh perceptron diatas tetapi ditampilkan dalam bentuk tabel. Penyelesaian: 1. Inialisasi:

b=wi = 0, dengan i=1,2,3,..,9. α=1; θ=0 Epoch 1 Table 1 Pola 1 Epoch 1

Input Target

y_in

Output

(t) xi

α

t

𝑏

y

+ ∑ 𝑥𝑖 𝑤𝑖 𝑖

1

0

0

Perubahan

Perubahan

Bias

Bobot

Bias

Bobot

Baru

Baru

b(baru) =

wi(baru) =

b(lama) +

wi(lama) +

α*t

α*t* xi

1

-1

b(baru) wi(baru)

-1

1

1

-1

-1

1

-1

-1

-1

1

-1

-1

1

1

1

1

1

1

1

1

1

1

1

1

-1

1

-1

-1

-1

1

-1

-1

-1

1

-1

-1

Pada tabel 1 terlihat bahwa y ≠ target sehingga perlu dilakukan perubahan bobot.

Table 2 Pola 2 Epoch 1

Input Target

y_in

Output

(t) xi

α

t

𝑏

y

+ ∑ 𝑥𝑖 𝑤𝑖 𝑖

-1

-8

-1

Perubahan

Perubahan

Bias

Bobot

Bias

Bobot

Baru

Baru

b(baru) =

wi(baru) =

b(lama) +

wi(lama) +

α*t

α*t* xi

b(baru) wi(baru)

1

1

1

-1

1

1

-1

1

1

-1

-1

1

1

-1

1

1

-1

1

1

1

1

-1

1

1

-1

1

1

-1 Pada tabel 2 terlihat bahwa y = target. Sehingga perubahan bobot tidak perlu

dilakukan.

Epoch 2 Table 3. Pola 1 Epoch 2

Input Target

y_in

Output

(t) xi

α

t

𝑏

y

+ ∑ 𝑥𝑖 𝑤𝑖 𝑖

1

10

Perubahan

Perubahan

Bias

Bobot

Bias

Bobot

Baru

Baru

b(baru) =

wi(baru) =

b(lama) +

wi(lama) +

α*t

α*t* xi

1

b(baru) wi(baru)

-1

1

1

-1

-1

1

-1

-1

1

-1

1

1

1

1

1

1

1

1

1

-1

1

-1

-1

1

-1

-1

1

-1

Pada tabel 3 terlihat bahwa y = target. Sehingga perubahan bobot tidak perlu dilakukan.

Table 4. Pola 2 Epoch 2

Input Target

y_in

Output

(t) xi

α

t

𝑏

y

+ ∑ 𝑥𝑖 𝑤𝑖 𝑖

-1

-8

-1

Perubahan

Perubahan

Bias

Bobot

Bias

Bobot

Baru

Baru

b(baru) =

wi(baru) =

b(lama) +

wi(lama) +

α*t

α*t* xi

b(baru) wi(baru)

1

1

1

-1

1

1

-1

1

1

-1

-1

1

1

-1

1

1

-1

1

1

1

1

-1

1

1

-1

1

1

-1

Pada tabel 4 terlihat bahwa y = target. Sehingga perubahan bobot tidak perlu dilakukan. Contoh ini berhenti pada epoch ke-2 karena pada kedua pola input tidak terdapat perubahan lagi. Sehingga proses pelatihan tidak perlu dilanjutkan ke epoch ke-3. Hal ini menandakan bahwa perceptron telah mampu mengklasifikasikan mana pola yang berada di kelas “-“. Bias akhir yang dihasilkan adalah 1. Bobot akhir yang dihasilkan adalah [-1,-1,1,1,1,1,-1,-1,-1].

Contoh 2: Klasifikasi dengan Model Perceptron Output Majemuk Model perceptron berikut akan dilatih untuk mengenali apakah pola input yang diberikan adalah pola karakter “-” atau “=”..

Gambar 3. Pola 1 Dan Pola 2

Unit input dan unit output yang digunakan bernilai bipolar sehingga kotak yang berwarna hijau akan bernilai +1. Sedangkan kotak berwarna biru bernilai -1. Bobot (w) dan bias (b) awal diinisialisasi dengan 0. Learning rate (α) diinisialisasidengan 1 dan threshold (θ) diinisialisasi dengan 0.

Bentuk pola input dan target yang digunakan untuk mengenali pola “-” diberi nilai, untuk target bernilai 1 berarti pola input dikenali sebagai pola “-”. Sedangkan target bernilai -1 berarti pola input tidak dikenali sebagai pola “-”.

Pola Input

Target (t) “-“

Target (t) ”=”

Pola 1

1

-1

Pola 2

-1

1

Iterasi yang dilakukan pada proses pelatihan untuk mengenali pola “-” adalah sebagai berikut. Perbedaan arsitektur perceptron yang digunakan dengan arsitektur perceptron pada contoh sebelumnya hanya berbeda pada jumlah unit output (jumlah kelas yang dihasilkan).

Gambar 4 Arsitektur Perceptron Majemuk

Langkah-langkah yang dilakukan pada pelatihan sama dengan di Contoh 1. Namun pada contoh berikut iterasi ditampilkan dalam bentuk tabel karena prosesnya tidak jauh berbeda dengan iterasi pada Contoh 1:

Penyelesaian: 1.

Inialisasi:

b=wi = 0, dengan i=1,2,3,4..,25. α=1; θ=0 Epoch 1 Table 5 Pola 1 Epoch 1 Input

Target

y_in

Output

Perubahan Bias

Perubahan Bobot

Bias Baru

Bobot Baru

y1

b(bar

b(baru)

W1(bar

W2(bar

b1(ba

b2(ba

W1(ba

W2(

ru)

ru)

ru)

bar

(t) X1

α

t1

t2

y_

y_

y2

in

in

u) =

=

u) =

u) =

1

2

b(lam

b(lama)

wi(lama

wi(lama

a) +

+ α*t

) + α*t*

) + α*t*

xi

xi

-1

1

α*t -1

1

1

-1

0

0

0

0

1

-1

-1

1

-1

-1

1

1

u)

1

-1

-1

1

1

-1

1

-1

1

-1

1

1

1

-1

1

-1

1

1

1

-1

1

-1

1

1

1

-1

1

-1

-1

1

-1

1

-1

1

-1

1

-1

1

-1

1

-1

1

-1

1

-1

1

Pada tabel 5 terlihat bahwa y1 ≠ target 1 dan y2 ≠ target 2 sehingga perlu dilakukan perubahan bobot. Bobot baru terletak pada kolom w1 (baru), w2(baru), b1(baru), dan b2(baru).

Table 6 Pola 2 Epoch 1 Input

Target

y_in

Output

Perubahan Bias

Perubahan Bobot

Bias Baru

Bobot Baru

y1

b(bar

b(baru)

W1(bar

W2(bar

b1(ba

b2(ba

W1(ba

W2(

ru)

ru)

ru)

bar

(t) X1

α

t1

t2

y_

y_

y2

in

in

u) =

=

u) =

u) =

1

2

b(lam

b(lama)

wi(lama

wi(lama

+ α*t

u)

1

1

1

-1

1

-8

8

-1

a) +

) + α*t*

) + α*t*

α*t

xi

xi

1

1

-1

-1

1

1

-1

1

1

1

-1

1

-1

1

1

-1

-1

1

1

-1

-1

1

1

-1

1

1

-1

1

1

1

-1

1

1

1

-1

1

Pada tabel 6 terlihat bahwa y1 = target 1 dan y2 = target 2. Sehingga perubahan bobot tidak perlu dilakukan.

Epoch 2 Table 7 Pola 1 Epoch 2 Input

Target

y_in

Output

Perubahan

α

t1

Bias Baru

Bobot Baru

Bias

(t) X1

Perubahan Bobot

t2

y_

y_in

in

2

y1

y2

1

b(b

b(baru)

W1(bar

W2(bar

b1(ba

b2(ba

W1(ba

W2(

aru)

=

u) =

u) =

ru)

ru)

ru)

bar

=

b(lama)

wi(lama

wi(lama

b(la

+ α*t

) + α*t*

) + α*t*

xi

xi

ma)

u)

+ α*t -1

1

-1

1

-1

10

-10

1

-1

1

-1

-1

1

1

-1

1

-1

1

-1

1

1

1

1

-1

1

1

1

-1

1

1

1

-1

-1

1

-1

1

-1

1

-1

1

-1

1

-1

1

Pada tabel 7 terlihat bahwa y1 = target 1 dan y2 = target 2. Sehingga perubahan bobot tidak perlu dilakukan.

Table 8 Pola 2 Epoch 2 Input

Target

y_in

Output

Perubahan Bias

Perubahan Bobot

Bias Baru

Bobot Baru

y1

b(bar

b(baru)

W1(bar

W2(bar

b1(ba

b2(ba

W1(ba

W2(

ru)

ru)

ru)

bar

(t) X1

α

t1

t2

y_

y_

y2

in

in

u) =

=

u) =

u) =

1

2

b(lam

b(lama)

wi(lama

wi(lama

a) +

+ α*t

) + α*t*

) + α*t*

xi

xi

α*t 1

1

1 1

1

-1

-8

8

-1

1

u)

1

-1

-1

1

1

-1

1

1

-1

1

-1

1

1

-1

-1

1

1

-1

-1

1

1

-1

1

1

-1

1

1

1

-1

1

1

1

-1

1

Pada tabel 8 terlihat bahwa y1 = target 1 dan y2 = target 2. Sehingga perubahan bobot tidak perlu dilakukan.

Contoh ini berhenti pada epoch ke-2 karena pada kedua pola input tidak terdapat perubahan lagi. Sehingga proses pelatihan tidak perlu dilanjutkan ke epoch ke-3. Hal ini menandakan bahwa perceptron telah mampu mengklasifikasikan mana pola yang berada di kelas “-“ dan yang berada di kelas “=”.

Kelas Bias akhir yang dihasilkan = 1 Bobot akhir yang dihasilkan adalah sebagai berikut. [-1,-1,-1,1,1,1,-1,-1,-1]

Kelas = Bias akhir yang dihasilkan = -1 Bobot akhir yang dihasilkan adalah sebagai berikut. [1,1,1,-1,-1,-1,1,1,1] Soal:

Buatlah jaringan perceptron untuk mengenali apakah pola input yang diberikan adalah pola karakter “/”. Dengan Kotak Hitam akan bernilai +1. kotak Putih bernilai -1. (w) dan (b) = 0. (α) = 1 dan (θ) = 0. Dengan target pola input di bawah ini Pola Input

Target (t)

Pola 1

1

Pola 2

-1