ALGORITMA DATA MINING A. DECISION TREE 1. Konsep Decision Tree Mengubah data menjadi pohon keputusan (decision tree) dan aturan-aturan keputusan (rule). Sebagai contoh misalnya ingin membuat aturan yang dapat digunakan untuk menentukan apakah seseorang mempunyai potensi untuk menderita hipertensi atau tidak berdasarkan data usia, berat badan dan jenis kelamin.
2. Penggunaan Decision Tree Beberapa contoh pemakaian decision tree antara lain:
Diagnosa penyakit tertentu seperti hipertensi, kanker, stroke dan lain-lain. Pemilihan produk seperti rumah, kendaraan, komputer dan lain-lain Pemilihan pegawai teladan sesuai dengan kriteria tertentu. Deteksi ganguan pada komputer atau jaringan komputer seperti Deteksi Entrusi, deteksi Virus (trojan dan varians) Masih banyak lainnya.
3. Algoritma Decision Tree a. Konsep Data Data dinyatakan dalam bentuk tabel dengan atribut dan record. Atribut menyatakan suatu parameter yang dibuat sebagai kriteria dalam pembentukan tree. Misalkan untuk menentukan main tenis, kriteria yang diperhatikan adalah cuaca, angin dan temperatur. Salah satu atribut merupakan atribut yang menyatakan data solusi per-item data yang disebut dengan target atribut. Sebagai gambaran perhatikan tabel berikut :
b. Proses Dalam Decision Tree Mengubah bentuk data (tabel) menjadi model tree Mengubah model tree menjadi rule Menyederhanakan rule (pruning) c. Perhitungan Entropi Entropi merupakan suatu besaran yang digunakan untuk menentukan nilai root awal yang akan dijadikan pembentukan tree. 1
Entroy (S) adalah jumlah bit yang diperkirakan dibuuthkan untuk dapat mengekstrak suatu kelas ( + atau - ) dari sejumlah data acak pada ruang sampel S. Entropy bisa dikatakan sebagai kebutuhan bit untuk menyatakan suatu kelas. Semakin kecil nilai entropy , maka semakin baik untuk digunakan dalam mengekstrak suatu kelas. Panjang kode untuk menyatakan informasi secara optimal adalah –log2 p bits untuk data yang mempunyai probabilitas p. Sehingga jumlah bit yang diperkirakan untuk mengekstraksi S ke dalam kelas adalah -p log2 p – q log2 q. Rumus
Entropi (S) = -p loq2 p – q log2q atau
Entropi (S) = -p 2loq p – q 2log q
Dimana : o S adalah ruang(data) sample yang digunakan untuk training o p adalah jumlah data yang bersolusi positif (mendukung) pada data sampel untuk kriteria tertentu. o q adalah jumlah yang bersolusi negatif (tidak mendukung) pada data sampel untuk kriteria tertentu.
4. Contoh Misalnya dicari aturan yang dapat digunakan untuk menentukan apakah seseorang menderita hipertensi atau tidak. Data yang diambil sebanyak 8 sampel dengan perkiraan bahwa yang mempengaruhi seseorang menderita hipertensi atau tidak adalah usia, berat badan dan jenis kelamin. Dimana masing-masing atribut yang diduga berpengaruhi tersebut memiliki nilai (intance): Usia mempunyai instance Muda dan Tua Berat Badan mempunyai instance Underweight, Average dan Overweight Jenis Kelamin mempunyai instance Pria dan Wanita
Langkah-langkah untuk menyelesaikan kasus diatas dengan algoritma Decision Tree adalah: a. Menentukan Node Terpilih Untuk menentukan node terpilih, gunakan nilai Entropy dari setiap kriteria dengan data sampel yang ditentukan. 2
Node terpilih adalah kriteria dengan entropy terkecil.
Memilih node awal
Entropy untuk Usia :
Lakukan perhitungan untuk semua kriteria, hasil perhitungannya misalnya seperti dibawah ini:
Berdasarkan perhitungan entropy diatas, maka diperoleh atribut BERAT BADAN sebagai node awal karena memiliki entropy terkecil.
b. Menyusun Tree Dari hasil perhitungan entropy, maka dapat disusun tree awal seperti gambar berikut :
Node berikutnya dapat dipilih dengan cara mencari bagian yang mempunyai nilai + dan - . Pada contoh diatas hanya berat=overweight yang mempunyai nilai + dan -, maka semuanya pasti memiliki leaf node. Untuk menyusun leaf node dilakukan satu persatu. Penentuan leaf node untuk cabang berat = overweight
3
Dari perhitungan diatas, terlihat bahwa hasil perhitungan Entropy Usia dan Kenis Kelamin menunjukkan nilai yang sama. Jika terdapat kasus seperti ini, maka cara lain adalah dengan menggunakan bantuan pakar untuk menentukan mana yang lebih penting atau percaya dengan hasil acak. Selanjutnya menyusun tree untuk leaf node, misalnya secara acak dipilih kriteria Jenis Kelamin.
Pada usia=tua ternyata ada 1 data yang menyatakan ya dan 1 data yang menyatakan tidak, keadaan ini perlu dicermati . Pilihan hanya dapat ditentukan dengan campur tangan seorang pakar. Menyusun node tree lanjutan
4
c. Mengubah Tree menjadi Rule Dari rule yang sudah dihasilkan, maka diperoleh rule sebagai berikut : Rule 1: IF berat=average OR berat=underweight THEN hipertensi=tidak Rule 2: IF berat=overweight AND kelamin=wanita THEN hipertensi=ya Rule 3: IF berat=overweight AND kelamin=pria AND usia=muda THEN hipertensi=ya Rule 4: IF berat=overweight AND kelamin=pria AND usia=tua THEN hipertensi=tidak d. Menyederhanakan dan Menguji Rule (Pruning) Menguji Rule untuk Prediksi
Kesalahan (error) : 1/8 x 100% = 12,5 % Akurasi Prediksi : 7/8 x 100% = 87,5%
Menyederhanakan Rule 1) Membuat tabel distribusi terpadu dengan menyatakan semua nilai kejadian pada setiap rule.
5
2) Menghitung tingkat independensi antara kriteria pada suatu rule, yaitu antara atribut dan target atribut dengan Uji Statistik Chi-Square Kriteria Berat Badan H0 : Berat Badan tidak dependent terhadap Hipertensi H1 : Berat Badan dependensi terhadap Hipertensi Selanjutnya dihitung tingkat dependensi antara kriteria Berat Badan terhadap Hipertensi :
Derajat Kebebasan adalah (jumlah baris-1)(jumlah kolom -1) =(2-1)(3-1) dan nilai tingkat keercayaan α =5%. Didapatkan nilai
χ2 α
yang didapat dari tabel distribusi Chi-Square adalah
6.27.
Karena nilai
χ2hitung > χ2tabel
yaitu 19,2 > 6,27 maka Tolak H0 artinya kriteria berat ini
dependent sehingga tidak dapat dihilangkan Kriteria Jenis Kelamin H0 : Jenis Kelamin tidak dependent terhadap Hipertensi H1 : Jenis Kelamin dependensi terhadap Hipertensi Dengan cara yang sama dengan cara perhitungan untuk kriteria Berat Badan, maka didapatkan nilai
χ2hitung
sebesar 0,71 dan
χ2tabel
yaitu 3,89 dengan demikian
χ2hitung < χ2tabel artinya
Terima H0 sehingga kriteria jenis kelamin ini independent terhadap hipertensi dan dapat dihilangkan. Kriteria Usia H0 : Usia tidak dependent terhadap Hipertensi H1 : Usia dependensi terhadap Hipertensi Dengan cara yang sama dengan cara perhitungan untuk kriteria Berat Badan, maka didapatkan nilai
χ2hitung
sebesar 2,13 dan
χ2tabel
yaitu 3,89 dengan demikian
χ2hitung < χ2tabel artinya
Terima H0 sehingga kriteria usia ini independent terhadap hipertensi dan dapat dihilangkan. 6
3) Mengeliminasi kriteria yang tidak perlu, yaitu yang tingkat independensinya tinggi. Dengan melihat hasil perhitungan nilai dependensi setiap kriteria terhadap hipertensi didapatkan bahwa : Kriteria Berat Badan dependent terhadap Hpertensi Tidak dapat dihilangkan Kriteria Jenis Kelamin tidak dependent terhadap Hipertensi Dapat dihilangkan Kriteria Usia tidak dependent terhadap Hipertensi Dapat dihilangkan Rule Awal : Rule 1: Rule 2: Rule 3: Rule 4:
IF berat=average OR berat=underweight THEN hipertensi=tidak IF berat=overweight AND kelamin=wanita THEN hipertensi=ya IF berat=overweight AND kelamin=pria AND usia=muda THEN hipertensi=ya IF berat=overweight AND kelamin=pria AND usia=tua THEN hipertensi=tidak
Rule Hasil Penyederhanaan 1: Rule 1: Rule 2: Rule 3: Rule 4:
IF berat=average OR IF berat=overweight IF berat=overweight IF berat=overweight
berat=underweight THEN hipertensi=tidak THEN hipertensi=ya THEN hipertensi=ya THEN hipertensi=tidak
Rule Hasil Penyederhanaan 2: Rule 1: Rule 2:
IF berat=average v berat=underweight THEN hipertensi=tidak IF berat=overweight THEN hipertensi=ya
Menguji Rule Hasil Pruning
Kesalahan (error) : 1/8 x 100% = 12,5 % Akurasi Prediksi : 7/8 x 100% = 87,5%
7
B. NAIVE BAYES 1. Konsep Naive Bayes Simple naive Bayesian classifiermerupakan salah satu metode pengklasifikasi berpeluang sederhana yang berdasarkan pada penerapan Teorema Bayes dengan asumsi antar variabel penjelas saling bebas (independen).Algoritma ini memanfaatkan metode probabilitas dan statistik yang dikemukakan oleh ilmuwan Inggris Thomas Bayes, yaitu memprediksi probabilitas di masa depan berdasarkan pengalaman di masa sebelumnya. Dua kelompok peneliti, satu oleh Pantel dan Lin, dan yang lain oleh Microsoft Research memperkenalkan metode statistik Bayesian ini pada teknologi anti spam filter. Tetapi yang membuat algoritma Bayesian filtering ini popular adalah pendekatan yang dilakukan oleh Paul Graham. Dasar dari teorema naive digunakan dalam pemrograman adalah rumus Bayes berikut ini:
P (A|B) = (P(B|A) * P(A))/P(B) Artinya Peluang kejadian A sebagai B ditentukan dari peluang B saat A, peluang A, dan peluang B.
2. Penggunaan Naive Bayes Contoh penggunaan Algoritma Naive Bayes antara lain: Untuk klasifikasi Dokumen Untuk deteksi SPAM atau fitering SPAM Dan masalah klasifikasi lainnya
3. Algoritma Naive Bayes Teorema Bayes: P(C|X) = P(X|C)·P(C) / P(X) Dimana :
P(X) bernilai konstan utk semua klas P(C) merupakan frek relatif sample klas C Dicari P(C|X) bernilai maksimum, sama halnya dengan P(X|C)·P(C) juga bernilai maksimum
Masalah menghitung P(X|C) tidak mungkin Apabila diberikan k atribut yang saling bebas (independence), nilai probabilitas dapat diberikan sebagai berikut. P(x1,…,xk|C) = P(x1|C) x … x P(xk|C) Jika atribut ke-i bersifat diskret, maka P(xi|C) diestimasi sebagai frekwensi relatif dari sampel yang memiliki nilai xi sebagai atribut ke i dalam kelas C. Namun jika atribut ke-i bersifat kontinu, maka P(xi|C) diestimasi dengan fungsi densitas Gauss.
1 f ( x) e 2
x 2 2 2
dengan = mean, dan = deviasi standar.
8
4. Contoh Misalnya terdapat ingin diketahui apakah suatu objek masuk dalam ketegori dipilih untuk perumahan atau tidak dengan algoritma Naive Bayes Classifier. Untuk menetapkan suatu daerah akan dipilih sebagai lokasi untuk mendirikan perumahan, telah dihimpun 10 aturan. Ada 4 atribut yang digunakan, yaitu: harga tanah per meter persegi (C1), jarak daerah tersebut dari pusat kota (C2), ada atau tidaknya angkutan umum di daerah tersebut (C3), dan keputusan untuk memilih daerah tersebut sebagai lokasi perumahan (C4).
a. Probabilitas kemunculan setiap nilai untuk atribut Harga Tanah (C1)
b. Probabilitas kemunculan setiap nilai untuk atribut Jarak dari Pusat Kota (C2)
c. Probabilitas kemunculan setiap nilai untuk atribut Ada Angkutan Umum (C3)
9
d. Probabilitas kemunculan setiap nilai untuk atribut Dipilih untuk perumahan (C4)
e. Menghitung probabilitas setiap kejadian : Berdasarkan data tersebut, apabila diketahui suatu daerah dengan harga tanah MAHAL, jarak dari pusat kota SEDANG, dan ADA angkutan umum, maka dapat dihitung: YA TIDAK
=P(Ya| Tanah=MAHAL).P(Ya|Jarak=SEDANG).P(Ya|Angkutan=ADA).P(Ya) = 1/5 x 2/5 x 1/5 x 5/10 = 2/125 = 0,008 = P(Tidak| Tanah=MAHAL).P(Tidak|Jarak=SEDANG).P(Tidak|Angkutan=ADA).P(Ya) = 3/5 x 1/5 x 3/5 x 5/10 = 2/125 = 0,036
Nilai probabilitas dapat dihitung dengan melakukan normalisasi terhadap likelihood tersebut sehingga jumlah nilai yang diperoleh = 1 Probabilitas Ya =
0,008 0,182. 0,008 0,036
Klasifikasi : TIDAK Probabilitas Tidak =
0,036 0,818. 0,008 0,036
Untuk jenis data harga tanah dan jarak pusat kota yang kontinue, misalnya :
Probabilitas kemunculan setiap nilai untuk atribut Harga Tanah (C1)
10
Probabilitas kemunculan setiap nilai untuk atribut Jarak dari Pusat Kota (C2)
Probabilitas kemunculan setiap nilai untuk atribut Angkutan Umum (C3)
Probabilitas kemunculan setiap nilai untuk atribut Dipilih untuk Perumahan (C4)
Apabila diberikan C1 = 300, C2 = 17, C3 = Tidak, maka: 300 212 2
f (C1 300 | ya )
2 1 e 2(168,8787) 0,0021. 2 (168,8787)
300 435 2
2 1 f (C1 300 | tidak ) e 2( 261.9637) 0,0013. 2 (261.9637)
17 4 ,8 2
2 1 f (C 2 17 | ya ) e 2(3.9623) 0,0009. 2 (3.9623)
17 17 , 2 2
2 1 f (C 2 17 | tidak ) e 2( 6,3008) 0,0633. 2 (6,3008)
Sehingga : Likelihood Ya
= = Likelihood Tidak
(0,0021) x (0,0009) x 4/5 x 5/10 0,000000756. = (0,0013) x (0,0633) x 2/5 x 5/10 = 0,000016458.
Nilai probabilitas dapat dihitung dengan melakukan normalisasi terhadap likelihood tersebut sehingga jumlah nilai yang diperoleh = 1 Probabilitas Ya = 0,000000756 0,000000756 0,000016458
0,0439.
Klasifikasi : TIDAK
Probabilitas Tidak =
0,000016458 0,9561. 0,000000756 0,00001645 8
11
C. TIME SERIES ANALYSIS 1. Konsep Analisis Deret Waktu (Time Series Analysis) Dalam statistika dan pemrosesan sinyal, deret waktu adalah rangkaian data yang berupa nilai pengamatan (observasi) yang diukur selama kurun waktu tertentu, berdasarkan waktu dengan interval yang uniform (sama).Beberapa Contoh data deret waktu adalah produksi total tahunan produk pertanian indonesia, harga penutupan harian sebuah saham di pasar modal untuk kurun waktu satu bulan, suhu udara per jam, dan penjualan total bulanan sebuah pasar swalayan dalam waktu satu tahun.Analisis deret waktu (Bahasa Inggris: time series analysis) merupakan metode yang mepelajari deret waktu, baik dari segi teori yang menaunginya maupun untuk membuat peramalan (prediksi). Prediksi / Peramalan deret waktu adalah penggunaan model untuk memprediksi nilai di waktu mendatang berdasar peristiwa yang telah terjadi. Di dunia bisnis, data deret waktu digunakan sebagai bahan acuan pembuatan keputusan sekarang, untuk proyeksi, maupun untuk perencanaan di masa depan. Analisis data deret waktu pada dasarnya digunakan untuk melakukan analisis data yang mempertimbangkan pengaruh waktu. Data-data yang dikumpulkan secara periodik berdasarkan urutan waktu, bisa dalam jam, hari, minggu, bulan, kuartal dan tahun, bisa dilakukan analisis menggunakan metode analisis data deret waktu. Analisis data deret waktu tidak hanya bisa dilakukan untuk satu variabel (Univariate) tetapi juga bisa untuk banyak variabel (Multivariate). Selain itu pada analisis data deret waktu bisa dilakukan peramalan data beberapa periode ke depan yang sangat membantu dalam menyusun perencanaan ke depan. Beberapa bentuk analisis data deret waktu dapat dikelompokkan ke dalam beberapa katagori : a. Metode Pemulusan (Smoothing) Metode pemulusan dapat dilakukan dengan dua pendekatan yakni Metode Perataan (Average) dan Metode Pemulusan Eksponensial (Exponential Smoothing). Pada metode rataan bergerak dapat digunakan untuk memuluskan data deret waktu dengan berbagai metode perataan, diantaranya : (1) rata-rata bergerak sederhana (simple moving average), (2) rata-rata bergerak ganda dan (3) rata-rata bergerak dengan ordo lebih tinggi. Untuk semua kasus dari metode tersebut, tujuannya adalah memanfaatkan data masa lalu untuk mengembangkan sistem peramalan pada periode mendatang. Pada metode pemulusuan eksponensial, pada dasarnya data masa lalu dimuluskan dengan cara melakukan pembotan menurun secara eksponensial terhadap nilai pengamatan yang lebih tua. Atau nilai yang lebih baru diberikan bobot yang relatif lebih besar dibanding nilai pengamatan yang lebih lama. Beberapa jenis analisis data deret waktu yang masuk pada katagori pemulusan eksponensial, diantaranya : (1) pemulusan eksponensial tunggal, (2) pemulusan eksponensia tunggal: pendekatan adaptif, (3) pemulusan eksponensial ganda : metode Brown, (4) metode pemulusan eksponensial ganda : metode Holt, (5) pemulusan eksponensial tripel : metode Winter. Pada metode pemulusan eksponensial ini, sudah mempertimbangkan pengaruh acak, trend dan musiman pada data masa lalu yang akan dimuluskan. Seperti halnya pada metode rataan bergerak, metode pemulusan eksponensial juga dapat digunakan untuk meramal data beberapa periode ke depan. b. Model ARIMA (Autoregressive Integrated Moving Average) Seperti halnya pada metode analisis sebelumnya, model ARIMA dapat digunakan untuk analisis data deret waktu dan peramalan data. Pada model ARIMA diperlukan penetapan karakteristik data deret berkala seperti stasioner, musiman dan sebagainya, yang memerlukan suatu pendekatan sistematis, dan akhirnya akan menolong untuk mendapatkan gambaran yang jelas mengenai model-model dasar yang akan ditangani. Hal utama yang mencirikan dari model ARIMA dalam rangkan analisis data deret waktu dibandingkan metode pemulusan adalah perlunya pemeriksaan keacakan data dengan melihat koefisien autokorelasinya. Model ARIMA juga bisa digunakan untuk mengatasi masalah sifat keacakan, trend, musiman bahkan sifat siklis data data deret waktu yang dianalisis. 12
c. Analisis Deret Berkala Multivariate Model ARIMA digunakan untuk analisis data deret waktu pada katagori data berkala (tunggal), atau sering dikatagorikan model-model univariate. Untuk data-data dengan katagori deret berkala berganda (multiple), tidak bisa dilakukan analisis menggunakan model ARIMA, oleh karena itu diperlukan model-model multivariate. Model-model yang masuk kelompok multivariate analisisnya lebih rumit dibandingkan dengan model-model univariate. Pada model multivariate sendiri bisa dalam bentuk analisis data bivariat (yaitu, hanya data dua deret berkala) dan dalam bentuk data multivariate (yaitu, data terdiri lebih dari dua deret berkala). Model-model multivariate diantaranya: (1) model fungsi transfer, (3) model analisis intervensi (intevention analysis), (4) Fourier Analysis, (5) analisis Spectral dan (6) Vector Time Series Models.
2. Penggunaan Analisis Deret Waktu (Time Series Analysis) Banyak persoalan dalam ilmu terapan yang datanya merupakan data deret waktu, misalnya dalam bidang ilmu: Ekonomi : banyak barang terjual dalam setiap hari, keuntungan perusahaan dalam setiap tahun, total nilai ekspor dalam setiap bulan, pergerakan saham, dan lain-lain. Fisika : curah hujan bulanan, temperatur udara harian, gerak partikel, dan lain-lain. Demografi : pertumbuhan penduduk, mortalitas dan natalitas, dan lain-lain Pengontrolan kualitas : proses pengontrolan kualitas produk, pengontrolan proses produksi, dan lainlain. Biomedis : denyut nadi, proses penyembuhan, pertumbuhan mikroba, dan lain-lain
3. Algoritma Analisis Deret Waktu (Time Series Analysis) Dalam analisis data deret waktu, proses baku yang harus dilakukan adalah a. Definisikan Tujuan Peramalan Misalnya peramalan dapat digunakan selama masa pra-produksi untuk mengukur tingkat dari suatu permintaan. b. Buatlah diagram pencar (Plot Data) Misalnya memplot demand versus waktu, dimana demand sebagai ordinat (Y) dan waktu sebagai axis (X). Misalnya seperti gambar dibawah ini :
Model Stasioner
Model Trend
Model Seasonal (Musiman)
Model Seasonal dan Trend 13
c. Memilih model peramalan yang tepat Melihat dari kecenderungan data pada diagram pencar, maka dapat dipilih beberapa model peramalan yang diperkirakan dapat mewakili pola tersebut. Model-model didalam peramalan data time series antara lain : 1) Model Konstan (Constant Forecasting) Persamaan garis yang menggambarkan pola konstan adalah: Y’(t) = a , dimana a = konstanta Untuk mendapatkan nilai (a) maka dapat didekati melalui turunan kuadrat terkecilnya (least square) terhadap (a) sebagai berikut: n
E [Y (t ) a ]2 i 1
Dimana : n
dE 0 da
n
2 [Y (t ) a ] 0 , karena
diperoleh
i 1
n
Y (t ) a 0 ; i 1
i 1
n
maka
Y (t ) na 0 i 1
n
Y (t ) Sehingga:
i 1
a ; dimana n = jumlah periode peramalan.
n
Jadi, apabila pola data berbentuk konstan, maka peramalannya dapat didekati dengan harga ratarata dari data tersebut.
2) Model Siklis (Musiman) Untuk pola data yang bersifat siklis atau musiman, persamaan garis yang mewakili dapat didekati dengan fungsi trigonometri, yaitu:
Y ' (t ) a u cos
2 2 t v sin t n n
Dimana n adalah jumlah periode peramalan Jumlah Kuadrat Kesalahan Terkecil didefinisikan sebagai: n
E [Y (t ) a u cos i 1
2 2 2 t v sin t )] N N
Bentuk diskriminannya adalah sebagai berikut:
k’ '
1
k
n
k cos
k sin
2 N 2 N
t
0
t
0
cos
2 N 0 n 2 0
t
sin
2 N 0 0
t 0
n 2
14
Maka:
n k' 0
0 n 2
0
0
0
k
0 n 2
2 0 1 k cos t N n 2 k sin t 2 N
0
k 2 2 0 cos t k cos t N N n 2 k sin t 2 N 0
n 0 0
k 2 2 0 sin t k cos t N N n 2 k sin t 2 N 0
3) Model Regresi Liner Persamaan garis yang mendekati bentuk data linier adalah
n 0 0
0 n 0 2 0
Y’(t) = a + b(t)
Konstanta a dan b ditentukan dari data mentah berdasarkan Kriteria Kuadrat Terkecil (least square criterion). Perhitungannya sebagai berikut: Anggaplah data mentah diwakili dengan (Yi,ti), dimana Yi adalah permintaan aktual di saat ti, dimana i = 1,2, .....,n. n Definisikan: E [Y (t ) a b(t )]2
i 1
Turunkan persamaan tersebut terhadap a dan b: n dE 0 yaitu 2 [Y (t ) a bt ] 0 diperoleh da i 1
n
i 1
n
dE 0 yaitu 2 t[Y (t ) a bt ] 0 diperoleh db i 1
n
Y (t ) na b t 0 ...........(1) i 1
n
n
n
tY (t ) a t b t 2 0 ....(2) i 1
i 1
i 1
Dengan mengeliminasi persamaan (1) dan (2) diperoleh nilai a dan b: n
n
n
n
b
i 1
i 1 n
i 1 n
n t 2 t i 1 i 1
n
Y (t ) b t
n tY (t ) Y (t ) t a
2
i 1
i 1
n
Confidence Interval dan Prediction Interval Berdasarkan sebaran t dengan (n – 2) derajat bebas, maka pada persamaan linier [Y’(t) = a + b(t)] dapat dibuat Selang Kepercayaan (confidence intervals) dengan (1-)100% bagi nilai tengah dari Y dan Selang Taksiran (prediction intervals) untuk setiap nilai Y, yaitu:
Confidence Interval = Y’(t) ± t/2 SEE
1 n
(t o t ) 2 ( t ) 2 2 t n
Prediction Interval untuk setiap nilai Y yaitu (1-)100% bila t = to.
15
Prediction Interval = Y’(t) ± t/2SEE 1
1 n
(t o t ) 2 ( t ) 2 2 t n
4) Model Rata-Rata Bergerak (Moving Average) Metode rata-rata bergerak banyak digunakan untuk menentukan trend dari suatu deret waktu. Dengan menggunakan metode rata-rata bergerak ini, deret berkala dari data asli diubah menjadi deret rata-rata bergerak yang lebih mulus. Metode ini digunakan untuk data yang perubahannya tidak cepat, dan tidak mempunyai karakteristik musiman atau seasonal. Model rata-rata bergerak mengestimasi permintaan periode berikutnya sebagai rata-rata data permintaan aktual dari n periode terakhir. Terdapat tiga macam model rata-rata bergerak, yaitu: a) Simple Moving Average Simple Moving Average (SMAt) =
Yt Yt 1 Yt 2 .... Yt n1 n
b) Centered Moving Average Perbedaan utama antara Simple Moving Average dan Centered Moving Average terletak pada pemilihan observasi yang digunakan. Simple Moving Average menggunakan data yang sedang diobservasi tambah data sebelum observasi. Misalnya, menggunakan 5 periode moving average, maka untuk SMA menggunakan data periode ke-5 dan 4 data periode sebelumnya. Sebaliknya untuk CMA, “Center” berarti rataan antara data sekarang dengan menggunakan data sebelumnya dan data sesudahnya. Misalnya untuk 3 periode moving average, maka SMA menggunakan data periode 3 ditambah data sebelumnya dan data sesudahnya. Didefinisikan sebagai berikut:
CMAt
Yt (( L 1 / 2 ) ........Yt ........ Yt (( L 1) / 2 L
Dimana Yt adalah nilai tengah dari interval L data observasi. (L-1)/2 observasi merupakan data sebelum dan sesudahnya. Misalnya CMA 5 periode, maka Yt = Y5 maka intervalnya dimulai dari Y3 sampai Y7 . c) Weighted Moving Average Formula untuk Weighted Moving Average (WMAt):
Ft w1 At 1 w2 At 2 ....... wn At n dan n
w
i
1
i 1
5) Model Pelicinan/Pemulusan Eksponensia ( Exponential Smoothing) Dalam model rata-rata bergerak (Moving Average) dapat dilihat bahwa untuk semua data obesrvasi memiliki bobot yang sama yang membentuk rata-ratanya. Padahal, data observasi terbaru seharusnya memiliki bobot yang lebih besar dibandingkan dengan data observasi di masa yang lalu. Hal ini dipandang sebagai kelemahan model peramalan Moving Average. Untuk itu, digunakanlah 16
metode Exponential Smoothing agar kelemahan tersebut dapat diatasi didasarkan pada alasan sebagai berikut: Metode exponential smoothing mempertimbangkan bobot data-data sebelumnya dengan estimasi untuk Y’(t+1) dengan periode (t+1) dihitung sebagai:
Y '(t 1) Y1 (1 )Y(t 1) (1 ) 2 Y(t 2) ...... Dimana disebut konstanta pelicinan dalam interval 0 < < 1. Rumus ini memperlihatkan bahwa data yang lalu memiliki bobot lebih kecil dibandingkan dengan data yang terbaru. Rumus tersebut dapat disederhanakan sebagai berikut:
Dengan nilai Y’(1) untuk inisial ramalan didekati dengan nilai rata-ratanya ( Y ) Atau
Y '(t ) Y '( t 1) (Y(t 1) Y '(t 1) ) Perlu diperhatikan bahwa penetapan nilai konstanta memiliki andil yang penting dalam menghasilkan hasil ramalan yang “andal”. Model Exponential Smoothing digunakan untuk peramalan jangka pendek.
Selain model-model diatas masih banyak model lain yang sedang dikembangkan dalam rangka mencari model terbaik untuk peramalan. d. Lakukan Peramalan e. Hitung kesalahan ramalan (forecast error) Keakuratan suatu model peramalan bergantung pada seberapa dekat nilai hasil peramalan terhadap nilai data yang sebenarnya. Perbedaan atau selisih antara nilai aktual dan nilai ramalan disebut sebagai “kesalahan ramalan (forecast error)” atau deviasi yang dinyatakan dalam:
et = Y(t) – Y’(t) Dimana : Y(t) = Nilai data aktual pada periode t Y’(t) = Nilai hasil peramalan pada periode t t = Periode peramalan Maka diperoleh Jumlah Kuadrat Kesalahan Peramalan yang disingkat SSE (Sum of Squared Errors) dan Estimasi Standar Error (SEE – Standard Error Estimated)
SSE = e(t)2 = [Y(t)-Y’(t)]2
n 2
[Y (t ) Y ' (t )] SEE
f.
i 1
n2
Pilih Metode Peramalan dengan kesalahan yang terkecil. Apabila nilai kesalahan tersebut tidak berbeda secara signifikan pada tingkat ketelitian tertentu (Uji statistik F), maka pilihlah secara sembarang metode-metode tersebut. 17
g. Lakukan Verifikasi Untuk mengevaluasi apakah pola data menggunakan metode peramalan tersebut sesuai dengan pola data sebenarnya.
4. Contoh 1) Model Konstan (Constant Forecasting) Diberikan data permintaan pabrik konveksi PT Garmen Mandiri dari bulan Januari sampai Juni tahun 2006. Tentukan jumlah permintaan untuk lima bulan selanjutnya dengan menggunakan model konstan. Bulan (t) Jan Feb Mar Apr Mei Jun
Permintaan dalam unit (Y) 46 56 54 43 57 56
Menghitung Konstanta a :
a=
(46 56 54 43 57 56) 52 6
Jadi permintaan untuk bulan Juli sampai dengan November 2006 dapat didekati dengan harga rataratanya (a) yaitu 52 unit. 2) Model Siklis (Musiman) Diketahui data permintaan produksi chip pada tahun 2005 sebagai berikut: Bulan (t) Jan Feb Mar Apr Mei Jun Jul Aug Spt Oct Nov Des
Permintaan dalam unit (Y) 73 83 92 107 114 129 91 108 116 79 92 93
1) Tentukan demand di tahun berikutnya dengan metode peramalan pola data siklis. k= h= t Y hk sin (2t/12) cos (2t/12) kcos(t/6) ksin(t/6) d -98 t - 6 Jan 1 72 -26 -5 130 0.500 0.866 -22.52 -13.00 Feb 2 83 -15 -4 60 0.866 0.500 -7.50 -12.99 Mar 3 92 -6 -3 18 1.000 0.000 0.00 -6.00 Apr 4 107 9 -2 -18 0.866 -0.500 -4.50 7.79 18
May Jun Jul Aug Sept Oct Nov Dec Total
5 114 6 129 7 91 8 108 9 116 10 79 11 92 12 93 78 1176
k'
16 31 -7 10 18 -19 -6 -5 0
1
cos
0 12 98.01 0
0 6
19.90
0
0
t 6
-1 -16 0 0 1 -7 2 20 3 54 4 -76 5 -30 6 -30 6 105
0.500 0.000 -0.500 -0.866 -1.000 -0.866 -0.500 0.000 0.000
-0.866 -1.000 -0.866 -0.500 0.000 0.500 0.866 1.000 0.000
-13.86 -31.00 6.06 -5.00 0.00 -9.50 -5.20 -5.00 -98.01
t 6 0 0 0 6
sin
Maka:
12 0 0 0 0 0 0 12 0 0 12 0 t t k ' 0 6 0 1 98.01 6 0 cos 98.01 0 0 sin 98.01 0 6 0 6 6 0 0 6 19.90 0 6 19.90 0 6 19.90 0 0
t t (7056.72) sin 1432.80 0 6 6 t t k ' 16.33 cos 3.32 sin 6 6 k ' (432) cos
sehingga persamaan garisnya :
Y ' (t ) d k ' = Y ' (t ) 98 16.33 cos t 3.32 sin t 6
Month January February March April May June July August September October November December Totals
t 1 2 3 4 5 6 7 8 9 10 11 12 78
Demand (Y) 72 83 92 107 114 129 91 108 116 79 92 93 1176
6
82.20 86.96 94.68 103.29 110.48
Error (e) -10.20 -3.96 -2.68 3.71 3.52
114.33 113.80 109.04 101.32 92.71 85.52 81.67 1176
14.67 -22.80 -1.04 14.68 -13.71 6.48 11.33 0
Forecast (Y’)
19
(Y - Y')^2 104.00 15.68 7.18 13.76 12.38 215.21 519.92 1.08 215.50 187.97 42.01 128.37 1463.07
8.00 0.00 3.50 -8.66 -18.00 16.45 3.00 0.00 -19.90
2) Hitunglah standard error estimate-nya! Standar Error Estimatenya (SEE) : N
[Y (t ) Y ' (t )] SEE
2
i 1
n2
1463.07 12.09 10
3) Model Regresi Liner Diketahui data pada tahun 2005 pada tabel berikut ini. Bulan (t) Jan Feb Mar Apr Mei Jun Jul Aug Spt Oct Nov Des
Permintaan dalam unit (Y) 199 202 199 208 212 194 214 220 219 234 219 233
1) Tentukan demand tahun 2007 Month
Bulan Ke-
Demand
t^2
t*Y(t)
Jan
1
199
1
199
Feb
2
202
4
404
Mar
3
199
9
597
Apr
4
208
16
832
May
5
212
25
1060
Jun
6
194
36
1164
Jul
7
214
49
1498
Aug
8
220
64
1760
Sep
9
219
81
1971
Oct
10
234
100
2340
Nov
11
219
121
2409
Des
12
233
144
2796
t=
Y(t) =
t^2 =
t*Y(t) =
78
2553
650
17030
b
12(17030) (78)( 2553) 3,05 12(650) (78) 2
a
(2553) (3,05)(78) 192,95 12 20
Diperoleh Persamaannya : Y’(t) = 193 + 3(t) sehingga permintaan pada tahun 2007 adalah sebagai berikut: Bulan (t) Jan (25) Feb (26) Mar (27) Apr (28) Mei (29) Jun (30) Jul (31) Aug (32) Spt (33) Oct (34) Nov (35) Des (36)
Permintaan dalam unit (Y) 268 271 274 277 280 283 286 289 292 295 298 301
2) Hitunglah SSE (Sum of Squared Errors) dan SEE-nya (Standard Error Estimated) Untuk menghitung SSE dan Standard Error Estimatenya (SEE) terlebih dahulu dihitung demand aktual dengan menggunakan persamaan (Y’(t)) yang telah diketahui. Month Jan Feb Mar Apr May Jun Jul Aug Sep Oct Nov Dec
Bulan Ke1 2 3 4 5 6 7 8 9 10 11 12 Total 78
Demand 199 202 199 208 212 194 214 220 219 234 219 233 2553
Ramalan 196 199 202 205 208 211 214 217 220 223 226 230 2553
[Y(t)-Y'(t)]^2 9 9 9 9 16 289 0 9 1 121 49 9 530
Maka diperoleh Jumlah Kuadrat Kesalahan (SSE) = e(t)2 = [Y(t)-Y’(t)]2 = 530 Dan Estimasi Standard Errornya (SEE): t
[Y (t ) Y ' (t )] SEE
i 1
t 2
2
530 7,28 12 2
3) Tentukan Confidence Interval dan Prediction Interval dengan t = 18 serta derajat = 0,01 Dari Persamaan : Y’(t) = 193 + 3(t), maka untuk satu harga t = 18 diperoleh Y’=247 dengan Standar Error Estimatenya (SEE)= 7.28 dan t/2 = t 0,005 = 3,169 untuk (n – 2 = 12 – 2 =10) derajat bebas.
21
1 n
Confidence Interval = Y’(t) ± t/2 SEE
(t o t ) 2 ( t ) 2 2 t n
= 247 ± (3,169)(7,28)
1 (18 6,5) 2 12 (78) 2 650 12
= 247 ± 23,16
Prediction Interval = Y’(t) ± t/2SEE 1
1 n
= 247 ± (3,169)(7,28)
(t o t ) 2 ( t ) 2 2 t n
1
1 (18 6,5) 2 12 78 2 650 12
= 247 ± 46,32
4) Model Rata-Rata Bergerak (Moving Average) a) Simple MA Diberikan data harga penutupan akhir minggu surat-surat berharga perusahaan “Mandala” yang bergerak dalam bidang maskapai penerbangan.
Maka Moving Average 3 mingguan (SMA3) terhadap harga penutupan akhir minggu saham diperoleh dari perhitungan berikut:
Contoh perhitungan:
SMAMinggu3
22
46 56 54 52 3
SMAmin ggu 4
56 54 43 51 3
Berdasarkan data di atas, maka ramalan untuk minggu-minggu mendatang (13)
Y '(12 t )
56 47 56 53 unit 3
dengan t = 1,2,3
b) Centered MA
Contoh perhitungan:
CMAMei
54 43 57 56 67 55,4 5
c) Weighted MA Diketahui data penjualan suatu departement store 4 bulan periode. Kemudian ingin meramalkan penjualan bulan ke-5 dengan moving average dimana menggunakan bobot 40% actual sales untuk bulan saat ini (4), 30% untuk 2 bulan sebelumnya, 20% untuk 3 bulan sebelumnya, dan 10% untuk 4 bulan sebelumnya. Data penjualannya sebagai berikut:
Peramalan weighted moving average dengan N = 4 adalah:
F4 0.4(95) 0.3(105) 0.2(90) 0.1(100) 97.50 Maka ramalan bulan ke (5 + t) dengan t =1,2,3 adalah:
F5 0.4(95) 0.3(105) 0.2(90) 0.1(100) 97.50
23
5) Model Pelicinan/Pemulusan Eksponensia ( Exponential Smoothing) Tabulasi data berikut ini merupakan actual sales dalam unit untuk 6 bulan dan peramalan dimulai dari bulan januari. Month Actual Sales
Jan 100
Feb 94
Marc 108
Apr 80
May 68
June 94
1) Hitunglah estimasi nilai ramalannya menggunakan simple exponensial smoothing dengan = 0.2 jika inisial estimasi periode Januari = 80. Bulan
Actual Sales
January February March April May June July Total
100 94 106 80 68 94 542
Forecast (1) 80 84 86 90 88 84 86 598
Forecast(II) 80 84 86 90 88 84 86 598
Error
(Y-Y')^2 20 10 20 -10 -20 10 90
atau
Y '(t ) Y '(t 1) (Y(t 1) Y '(t 1) ) Y ' 2 0.2(100) 0.8(80) 84
atau
Y ' 2 80 0.2(100 80) 84
2) Hitunglah Mean Absolute Deviation (MAD) Mean Absolute Deviation (MAD)
n
Y (t ) Y ' (t ) MAD
MAD
t 1
n
90 15 ; 6
dimana 1 MAD = 0.8 standard deviation diperoleh standar deviation = 12
24
400 100 400 100 400 100 0 1500
D. CLUSTERING ANALYSIS 1. Konsep Analisis Cluster Analisis Cluster adalah suatu analisis statistik yang bertujuan memisahkan kasus/obyek ke dalam beberapa kelompok yang mempunyai sifat berbeda antar kelompok yang satu dengan yang lain. Dalam analisis ini tiap-tiap kelompok bersifat homogen antara anggota dalam kelompoknya atau dapat dikatakan variasi obyek/individu dalam satu kelompok yang terbentuk sekecil mungkin. Analisis Cluster merupakan metode pengelompokan, di mana data yang akan dikelompokan belum membentuk kelompok sehingga pengelompokkan yang akan dilakukan bertujuan agar data yang terdapat di dalam kelompok yang sama relatif lebih homogen daripada data yang berada pada kelompok yang berbeda. Diharapkan dengan terbentuknya kelompok tersebut akan lebih mudah menganalisa dan lebih tepat pengambilan keputusan sehubungan dengan masalah tersebut. Analisis Cluster dilakukan untuk tujuan: (1) menggali data/eksplorasi data, (2) mereduksi data menjadi kelompok data baru dengan jumlah lebih kecil atau dinyatakan dengan pengkelasan (klasifikasi) data, (3) menggeneralisasi suatu populasi untuk memperoleh suatu hipotesis, (4) menduga karakteristik data-data. Pengelompokkan untuk mereduksi obyek-obyek dalam satu kelompok yang mempunyai sifat yang relatif sama (homogen) dapat dilakukan dengan dua cara, yaitu; Pengelompokkan Herarkhi. Pengelompokkan tak Herarkhi (non herarchi). Pengelompokkan Herarkhi digunakan apabila tidak ada informasi tentang jumlah kelompok yang akan diperoleh. Sedangkan pengelompokkan tak Herarkhi digunakan apabila seluruh obyek (n obyek) akan dikelompokkan dalam k kelompok yang telah ditentukan terlebih dulu, dimana k < n. Metode yang digunakan dalam Cluster non herarchi adalah: - Metode K-Rataan (K-Mean method) - Metode MANOVA (Manova method) Klasifikasi prosedur pengelompokan dapat dilihat pada tabel dibawah ini :
Keunggulan Analisis Cluster : Dapat mengelompokan data observasi dalam jumlah besar dan variabel yang relatif banyak. Data yang direduksi dengan kelompok akan mudah dianalisis. Dapat dipakai dalam skala data ordinal, interval dan rasio Kelemahan Analisis Cluster Pengelompokan bersifat subyektifitas peneliti karena hanya melihat dari gambar dendrogram Untuk data yang terlalu heterogen antara objek penelitian yang satu dengan yang lain akan sulit bagi peneliti untuk menentukan jumlah kelompok yang dibentuk. Metode-metode dipakai memberikan perbedaan yang signifikan, sehingga dalam perhitungan biasanya masing-masing metode dibandingkan. Semakin besar observasi, biasanya tingkat kesalahan pengelompokan akan semakin besar (hasil penelitian)
2. Penggunaan Analisis Cluster Contoh aplikasi dengan analisis Cluster antara lain : Segmentasi Pasar Konsumen Memahami Perilaku Pembeli. Mengidentifikasi peluang produk baru 25
Memilih pasar mana yang akan dituju (targeting). Meringkas data atau Mereduksi data.
3. Algoritma Analisis Cluster a. Merumuskan permasalahan b. Memilih ukuran jarak atau kesamaan Ada berbagai metode dan kriteria untuk melakukan pengelompokan. Salah satunya adalah secara matematis. Untuk mengelompokkan data atau permasalahan dibutuhkan suatu ukuran yang dapat menerangkan keserupaan atau kedekatan antara data. Jika data tersebut dapat dinyatakan dalam bentuk matrik X yang anggota-anggotanya Xij, i = 1..n dan k=1..p maka beberapa ukuran kedekatan antara data ke i dan ke j ( dij ) adalah sebagai berikut :
c. Memilih prosedur pengklusteran Secara umum terdapat dua metode pengelompokan data yaitu metode pengelompokan hirarki dan non hirarki. Metode pengelompokan hirarki adalah metode pengelompokan data yang mengelompokan n buah data ke dalam n, n-1, 1 kelompok sedangkan metode pengelompokan non hirarki adalah metode pengelompokan yang mengelompokkan n data ke dalam k kelompok yang sudah ditentukan terlebih dahulu. Di dalam metode pengelompokan data hirarki terdapat beberapa metode yang dibedakan penentuan jarak antar kelompok yaitu : 1) Metode pautan tunggal (Single Lingkage) Jarak antar kelompok untuk metode ini didefinisikan sebagai jarak terdekat antar pasangan data yang terdapat pada dua kelompok tersebut. 2) Metode pautan lengkap (Complete Lingkage) Jarak antar kelompok untuk metode ini didefinisikan sebagai jarak terjauh antar pasangan data yang terdapat pada dua kelompok tersebut. 3) Metode pautan pusat (Centroid Lingkage) Jarak antar kelompok untuk metode ini didefinisikan sebagai jarak terdekat antar pusat kelompok. 4) Metode pautan rerata (Average Lingkage) Jarak antar kelompok untuk metode ini didefinisikan sebagai rerata jarak antar pasangan data yang terdapat pada dua kelompok tersebut. Sedangkan didalam metode pengelompokan no hirarki terdapat Masalah utama dalam metoda non hirarkhi adalah bagaimana memilih bakal cluster. Harus disadari pengaruh pemilihan bakal cluster terhadap hasil akhir analisis cluster. Bakal cluster pertama adalah observasi pertama dalam set data tanpa missing value. Bakal kedua adalah observasi lengkap berikutnya (tanpa missing data) yang dipisahkan dari bakal pertama oleh jarak minimum khusus. Ada tiga prosedur dalam metode non hirarkhi, yaitu : 1) Sequential threshold Metode ini dimulai dengan memilih bakal cluster dan menyertakan seluruh objek dalam jarak tertentu. Jika seluruh objek dalam jarak tersebut disertakan, bakal cluster kedua terpilih, kemudian proses terus berlangsung seperti sebelumnya. 26
2) Parallel Threshold Metode ini memilih beberapa bakal cluster secara simultan pada permulaannya dan menandai objek-objek dengan jarak permulaan ke bakal terdekat. 3) Optimalisasi Metode ketiga ini mirip dengan kedua metode sebelumnya kecuali pada penandaan ulang terhadap objek-objek. Hal penting lain adalah menentukan jumlah cluster yang akan dibentuk. Sebenarnya tidak ada standar,prosedur pemilihan tujuan eksis. Karena tidak ada kriteria statistik internal digunakan untuk inferensia, seperti tes signifikansipada teknik multivariat lainnya, para peneliti telah mengembangkan beberapa kriteria dan petunjuk sebagai pendekatan terhadap permasalahan ini dengan memperhatikan substansi dan aspek konseptual. d. Menetapkan jumlah cluster Algoritma untuk metode pengelompokan hirarki adalah : 1) Tentukan matrik jarak antar data atau kelompok 2) Gabungkan dua data atau kelompok terdekat ke dalam kelompok yang baru 3) Tentukan kembali matrik jarak tersebut. 4) Lakukan langkah 2 dan 3 sampai semua data masuk dalam satu kelompok Algoritma untuk metode pengelompokan Non Hirarki adalah : 1) Tentukan jumlah cluster (K), tetapkan pusat cluster sembarang. 2) Hitung jarak setiap data ke pusat cluster. 3) Kelompokkan data ke dalam cluster yang dengan jarak yang paling pendek. 4) Hitung pusat cluster. 5) Ulangi langkah 2 - 4 hingga sudah tidak ada lagi data yang berpindah ke cluster yang lain.
e. interpretasi dan profil dari cluster Hasil pengelompokan tersebut dapat digambarkan dengan diagram pohon dendrogram atau vicicle plot. Jumlah kelompok yang terjadi ditentukan dari dendrogram yang terjadi dan tergantung subyektivitas peneliti. Dibawah ini contoh dendrogram hasil output SPSS untuk 10 observasi dengan 3 variabel. Terlihat bahwa ada 2 kelompok yang dibentuk yaitu kelompok pertama terdiri dari observasi ke 8, 9 10, 7 dan kelompok kedua yang terdiri dari observasi 1, 2, 4, 5, 6, dan 3.
f.
Menaksir reliabilitas dan validitas Yaitu melakukan pengujian terhadap kesalahan dan akurasi hasil pengelompokan dengan membandingkan antara data prediksi pengelompokan dan data sebenarnya. Proses validasi bertujuan menjamin bahwa solusi yang dihasilkan dari analisis cluster dapat mewakili populasi dan dapat 27
digeneralisasi untuk objek lain. Pendekatan ini membandingkan solusi cluster dan menilai korespondensi hasil. Terkadang tidak dapat dipraktekkan karena adanya kendala waktu dan biaya atau ketidaktersediaan ibjek untuk analisis cluster ganda. Tahap ini menggambarkan karakteristik tiap cluster untuk menjelaskan cluster-cluster tersebut dapat dapat berbeda pada dimensi yang relevan. Titik beratnta pada karakteristik yang secara signifikan berbeda antar clustre dan memprediksi anggota dalam suatu cluster khusus. Secara keseluruhan proses analisis cluster berakhir setelah keenam tahap ini dilalui. Hasil analisis cluster dapat digunakan untuk berbagai kepentingan sesuai dengan materi yang dianalisis.
4. Contoh a. Metode Hirarki
Proximity Matrix Contoh menghitung jarak antar titik : 1) Metode MIN (SINGLE LINKAGE) Nearest Neighbour Dist({3,6},{2,5}) = min(dist(3,2),dist(3,5),dist(6,2),dist(6,5)) = min(0.15,0.25,0.28,0.39) = 0.15
28
2) Metode MAX (COMPLETE LINKAGE) Dist({3,6},{4}) = max(dist(3,4),dist(6,4)) = max (0.15,0.22) = 0.22 Dist({3,6},{2,5}) = max(dist(3,2),dist(3,5),dist(6,2),dist(6,5)) = max(0.15,0.25,0.28,0.39) = 0.39 Dist({3,6},{1}) = max(dist(3,1),dist(6,1)) = max(0.22,0.23) = 0.23
3) Metode AVERAGE
Proximity dari 2 klaster adalah rata-rata jarak tiap 2 titik pada 2 klaster yang berbeda
dist({3,6,4},{1}) = (0.22+0.37+0.23)/(3*1)= 0.28 dist({2,5},{1}) = (0.24+0.34)/(2*1) = 0.29 dist({3,6,4},{2,5}) = (0.15+0.28+0.25+0.39+0.20+0.29)/(3*2) = 0.26
29
4) Penerapan
X1 6 5 3 7 2 2 2 5 7 1 4 10 6 4 9 7 8 7 10 6 9 6 8 6 8
X2 2 7 5 1 2 1 4 4 6 4 9 8 7 10 5 9 5 7 4 9 7 5 10 4 5
Jarak (8,5) terhadap (X1,X2) 13 13 25 17 45 52 37 10 2 50 32 13 8 41 1 17 0 5 5 20 5 4 25 5
Y + + + + + + + + + + ?
Jadi titik (8,5) termasuk dalam kelompok (-) 12
10
8 Positive 6
Negative ?
4
2
0 0
2
4
6
8
30
10
12
b. Metode Non Hirarki (K-Means)
Instance
X
Y
1 2 3 4 5 6 7
2 2 5 6,5 7 3,5 4
5 5,5 3,5 2,2 3,3 4,8 4,5
Pilih K=2 Pilih titik pusat klaster misalnya C1(3,4) dan C2(6,4) Iterasi 1 Hitung jarak masing-masing titik terhadap tiitk pusat C1 (3,4)
Instance 1 2 3 4 5 6 7
X 2 2 5 6,5 7 3,5 4
Y 5 5,5 3,5 2,2 3,3 4,8 4,5
Jarak ke C1
Di
(2 − 3) + (5 − 4) (2 − 3) + (5,5 − 4) (5 − 3) + (3,5 − 4) (6,5 − 3) + (2,2 − 4) (7 − 3) + (3,3 − 4) (3,5 − 3) + (4,8 − 4) (4 − 3) + (4,5 − 4)
1,41 1,80 2,06 3,94 4,06 0,94 1,12
Hitung jarak masing-masing titik terhadap tiitk pusat C2 (6,4)
Instance 1 2 3 4 5 6 7
X 2 2 5 6,5 7 3,5 4
Y 5 5,5 3,5 2,2 3,3 4,8 4,5
Jarak ke C2
Di
(2 − 6) + (5 − 4) (2 − 6) + (5,5 − 4) (5 − 6) + (3,5 − 4) (6,5 − 6) + (2,2 − 4) (7 − 6) + (3,3 − 4) (3,5 − 6) + (4,8 − 4)
4,12 4,27 1,18 1,86 1,22
(4 − 6) + (4,5 − 4)
Bandingkan nilai jarak terhadap C1 dan C2
Instance
Di,c1
Di,c2
1 2 3 4 5 6 7
1,41 1,80 2,06 3,94 4,06 0,94 1,12
4,12 4,27 1,18 1,86 1,22 2,62 2,06
Jadi klaster 1 berisi instance 1,2,6,7 dan klaster 2 berisi instance 3,4,5
31
2,62 2,06
Hitung tiitk pusat baru
Iterasi 2 Dengan cara yang sama seperti pada iterasi 1 , diperoleh :
Instance
Di,c1
Di,c2
1 2 3 4 5 6 7
0,76 0,96 2,65 4,62 4,54 0,76 1,31
4,62 4,86 1,27 0,86 0,88 3,22 2,63
Dari perbandingan ini diketahui bahwa anggota klaster 1 adalah instance 1,2, 6 dan 7 sedangkan anggota klaster 2 adalah instance 3,4 dan 5. Karena anggota klaster tidak berubah, maka titik pusat yang baru pu tidak berubah sehingga iterasi dapat dihentikan
Jadi iterai berhenti hingga nilai C1 dan C2 tidak berubah (atau memenuhi treshold yang diinginkan) Hitung SSE = Sum Squared Error, digunakan untuk menentukan hasil klasterisasi yang lebih baik,jika inisialisasi centroidnya berbeda-beda K
SSE dist (ci , x ) 2 i 1 xCi
ci
1 mi
x
xCi
Makin kecil nilai SSE, makin baik Salah satu teknik untuk memperkecil nilai SSE adalah dengan memperbesar nilai K
32