PARTISI HIMPUNAN ATRIBUT UNTUK SISTEM PENALARAN PROBABILISTIK
TESIS
Oleh
SABAR 0770210072/MT
SEKOLAH PASCASARJANA UNIVERSITAS SUMATERA UTARA MEDAN 2009
Sabar : Partisi Himpunan Atribut Untuk Sistem Penalaran Probabilistik, 2009.
PARTISI HIMPUNAN ATRIBUT UNTUK SISTEM PENALARAN PROBABILISTIK
TESIS
Diajukan Sebagai Salah Satu Syarat untuk Memperoleh Gelar Magister Sains dalam Program Studi Magister Matematika pada Sekolah Pascasarjana Universitas Sumatera Utara
Oleh
SABAR 077021072/MT
SEKOLAH PASCASARJANA UNIVERSITAS SUMATERA UTARA MEDAN 2009
Sabar : Partisi Himpunan Atribut Untuk Sistem Penalaran Probabilistik, 2009.
Judul Tesis
: PARTISI HIMPUNAN ATRIBUT UNTUK SISTEM PENALARAN PROBABILISTIK Nama Mahasiswa : Sabar Nomor Pokok : 077021072 Program Studi : Matematika
Menyetujui, Komisi Pembimbing
(Dr. Sutarman, M.Sc) Ketua
(Prof. Dr. Iryanto, M.Si) Anggota
Ketua Program Studi,
Direktur,
(Prof. Dr. Herman Mawengkang)
(Prof. Dr. Ir. T.Chairun Nisa. B, M.Sc)
Tanggal lulus: 27 Mei 2009
Sabar : Partisi Himpunan Atribut Untuk Sistem Penalaran Probabilistik, 2009.
Telah diuji pada Tanggal: 27 Mei 2009
PANITIA PENGUJI TESIS Ketua Anggota
: Dr. Sutarman, M.Sc : 1. Prof. Dr. Drs. Iryanto, M.Si 2. Dr. Saib Suwilo, M.Sc 3. Dra. Mardiningsih, M.Si
Sabar : Partisi Himpunan Atribut Untuk Sistem Penalaran Probabilistik, 2009.
ABSTRAK Kemampuan sistem komputasi untuk memodelkan proses penalaran manusia adalah sesuatu yang penting dalam peninjauan suatu permasalahan. Peninjauan ini membutuhkan suatu sistem penalaran probabilistik dalam berbagai aplikasi yang dibutuhkan untuk membuat suatu keputusan pada kondisi yang tak pasti. Sistem penalaran yang mengandung ketidakpastian diasosiasikan dengan kemungkinan hasil yang berbeda-beda dan didasarkan pada data historikal, memberikan para pengguna suatu penaksiran pada ketidakpastian tersebut. Untuk membuat suatu penaksiran yang akurat skema partisi membutuhkan variabel prediksi yang bebas secara kondisional satu sama lainya yang ada sehingga memberikan hasil yang dapat dikelompokan ke atribut gabungan dengan tujuan estimasi probabilitas.Artibut gabungan tersebut mempartisi seluruh himpunan artibut prediksi ke himpunan gabungan. Suatu hal penting, selanjutnya adalah membuat skema partisi diperbolehkan sebelum skema penalaran digunakan. Dirumuskan permasalahan untuk menemukan penyekatan yang optimal dan menunjukan lima teknik heuristik berbeda (meskipun ada hubunganya satu dan yang lainya)untuk menghasilkan partisi dari kasus historika. Dengan menggunakan data yang tersimulasi, kelima teknik tersebut ditunjukan untuk mendapatkan kebebasan artibut untuk suatu jumlah pelalaran pada data gabungan yang tersedia untuk dianalisis. Dalam situasi dimana terdapat beberapa kasus historikal,penggunaan stuktur gabungan kurang akurat. Dalam situasi ini,penggunaan stuktur gabungan yntuk membuat prediksi probabilitas pada akhirnya didapat penyelesaian yang sesuai dengan hasil yang didapat saat menggunakan stuktur kebenaran. Kata kunci : Probabilistik, skema, partisi, heuristik.
i Sabar : Partisi Himpunan Atribut Untuk Sistem Penalaran Probabilistik, 2009.
ABSTRACT The ability of a computerized system to model the reasoning process of humans has become an important area of research. This research considers a probabilistic reasoning system for applications that require decision making under uncertain conditions. The reasoning system captures the uncertainty associated with different feasible outcomes, and based on historical data, provides users with a measure of this uncertainty. To make accurate prediction, the scheme requires that predictive variables that are not conditionally independent of each other given the outcome be grouped into compound attributes for the purpose of estimating probabilistic. These compound attributes partition the entire set of predictive attributes into disjoint sets. An important design issue, then, is that the appropriate partitioning scheme be obtained before the reasoning scheme is used in practice. Formulated[by] a problems to find the optimal partitioning plan , and present five different(although related) heuristic techniques to induce partitioning from historical cases. Using simulated data, all five techniques are shown to capture accurately underlying dependencies across attributes when a reasonable amount of historical data is available for analysis. In situations where few historical cases are available, the induced structures are less accurate. In such situations, the performance of induced structures for making probability predictions is nevertheless found to be as good as that when using the true structure. Keywords : Probabilistic, scheme, partition, heuristic.
ii Sabar : Partisi Himpunan Atribut Untuk Sistem Penalaran Probabilistik, 2009.
KATA PENGANTAR
Alhamdulillah puji syukur kehadirat Allah SWT atas berkat Rahmat dan RidhoNya penulis dapat menyelesaikan penulisan tesis ini yang berjudul ”Partisi Himpunan Atribut Untuk Sistem Penalaran Probabilistik”. Tesis ini merupakan tugas akhir pada Sekolah Pascasarjana Program Studi Magister Matematika Universitas Sumatera Utara. Pada kesempatan ini penulis juga menyampaikan ucapan terimakasih kepada: Kepala Bappeda Propinsi Sumatera Utara beserta stafnya yang telah memberikan beasiswa kepada penulis, Kepala Dinas Pendidikan Kota Medan yang telah memberikan ijin mengikuti perkuliahan program pascasarjana di Universitas Sumatera Utara. Prof. dr. Chairuddin P. Lubis, DTM&H,Sp.A(K) selaku Rektor Universitas Sumatera Utara dan Prof. Dr. Ir. T. Chairun Nisa B, MSc selaku Direktur Sekolah Pascasarjana Universitas Sumatera utara beserta stafnya yang telah memberikan kesempatan kepada penulis untuk mengikuti perkuliahan pada Angkatan ke III Program Educator tahun 2007. Prof.Dr. Herman Mawengkang, selaku Ketua Program Studi Matematika SPs USU yang telah banyak membantu penulis dalam merampungkan penulisan tesis ini. Dr. Saib Suwilo, MSc selaku sekretaris Program Studi Matematika SPs USU dan juga sebagai pembanding pada penulisan tesis ini yang berkat bimbingannya penulisan tesis ini dapat selesai.
iii Sabar : Partisi Himpunan Atribut Untuk Sistem Penalaran Probabilistik, 2009.
Dr.Sutarman,MSc selaku ketua komisi pembimbing pada penulisan tesis ini berkat bimbingan, saran dan dorongan semangat sehingga penulisan tesis ini dapat terselesaikan. Prof. Dr. Drs. Iryanto, MSi sebagai anggota komisi pembimbing untuk kesempurnaan penulisan tesis ini serta bimbingan selama perkuliahan. Dra. Mardiningsih, MSi Selaku pembanding yang telah memberikan saran dan bantuannya untuk kesempurnaan tesis ini. Serta bimbingan selama pekuliahan berlangsung. Dr. Sutarman, MSc, Dr. Tulus, MSi, Drs. Marwan Harahap M.Eng, Drs. Open Darinus Sembiring, MSc, Dra. Mardiningsih, MSi, Drs. Sawaluddin, M.IT sebagai staf pengajar pada Sekolah Pascasarjana Program Studi Matematika atas semua bimbingan dan ilmu yang telah diberikan selama perkuliahan terutama bagi penulis. Seluruh staf administrasi Sekolah Pascasarjana Matematika USU dan Misiani, SSi yang telah banyak memberikan bantuan dan pelayanan administrasi yang baik pada penulis. Dra.Hj.Rebekka Girsang selaku Kepala Sekolah SMAN 1 Medan yang telah memberikan kesempatan dan ijin untuk mengikuti perkuliahan. Drs. Hardo Pamuko, Parlaungan, SPd. MSi , Ibnu Rusdi, SPd. MSi dan rekan rekan seperjuangan di SMAN 1 Medan yang telah banyak membantu penulis dalam segala hal. Kepada istri tercinta Dra. Lin Rismawati, ibu Senen dan anak anak tercinta Andi Setiawan, Lili Hariningrum, Aldi Nurcahyo dan Alwi Dahlan iv Sabar : Partisi Himpunan Atribut Untuk Sistem Penalaran Probabilistik, 2009.
dan seluruh keluarga besar penulis yang telah memberikan doa dan semangat kepada penulis untuk menyelesaikan perkuliahan dan penyusunan tesis ini. Dan rekan rekan seperjuangan angkatan ke III (2007) program Edukator, atas kebersamaan dan bantuan dalam mengentaskan perkuliahan dan tesis ini. Semoga Tesis ini bermamfaat dan Tuhan bersama kita, Amin.
Medan, Penulis,
Sabar
v Sabar : Partisi Himpunan Atribut Untuk Sistem Penalaran Probabilistik, 2009.
Mei 2009
RIWAYAT HIDUP
Sabar di lahirkan di Medan pada tanggal 3 Maret 1967 Kecamatan Medan Denai yang saat ini menjadi Kecamatan Medan Tembung. Dan merupakan anak ke 9 dari 9 bersaudara dari pasangan Alm. Muchtar Ahmad dan Alm Arbaiyah. Menamatkan Sekolah Dasar (SD) bersubsidi At Taufiq tahun 1981, Sekolah Menengah Pertama (SMP) 1 Negeri Labuhan Deli tahun 1984 dan Sekolah Menengah Atas (SMA) Swasta Abdi Karya jurusan Ilmu-ilmu Fisika (IPA) tahun 1987. Pada tahun 1987 melanjutkan pendidikan ke Institut Keguruan dan Ilmu Pendidikan (IKIP) Swasta Al Washliyah Medan yang sekarang menjadi Universitas Muslim Nusantara (UMN) Medan jurusan Matematika Program Studi Strata-1 ( S-1 ) Pada Tahun 1988 mengajar di Madrasah Tsanawiyah Swasta Al Ittihadiyah laut dendang Medan, Tahun 1990 mengajar di SMP Swasta Muhammadiyah 5 Medan dan tahun 1990 mengajar di SMEA Tugama (Tunas Gajah Mada) Medan serta tahun 1990 juga mengajar di SMA Swasta Darussalam Medan. Menikah Tahun 1991 dan di karunia 4 orang anak ( putra dan putri ), memperoleh ijazah S-1 Negara Tahun 1993 dan diangkat sebagai guru Pegawai Negeri Sipil Tahun 1997 di tempatkan di SMP Negeri 2 Bahorok Kabupaten Langkat, dan pada Tahun 2000 mutasi ke SMA Negeri 2 Medan hingga Sekarang. Pada tahun 2007 mengikuti pendidikan Program Studi Magister Matematika di Sekolah Pascasarjana Universitas Sumatera Utara.
vi Sabar : Partisi Himpunan Atribut Untuk Sistem Penalaran Probabilistik, 2009.
DAFTAR ISI Halaman ABSTRAK . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
i
ABSTRACT
. . . . . . . . . . . . . . . . . . . . . . . . . . . . .
ii
KATA PENGANTAR . . . . . . . . . . . . . . . . . . . . . . . . .
iii
RIWAYAT HIDUP . . . . . . . . . . . . . . . . . . . . . . . . . .
vi
DAFTAR ISI . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
vii
DAFTAR GAMBAR . . . . . . . . . . . . . . . . . . . . . . . . .
ix
BAB 1 PENDAHULUAN . . . . . . . . . . . . . . . . . . . . . . .
1
1.1 Latar Belakang . . . . . . . . . . . . . . . . . . . . . .
1
1.2 Rumusan Masalah
. . . . . . . . . . . . . . . . . . . .
4
1.3 Tujuan Penelitian . . . . . . . . . . . . . . . . . . . . .
5
1.4 Manfaat Penelitian . . . . . . . . . . . . . . . . . . . .
5
1.5 Metode Penelitian . . . . . . . . . . . . . . . . . . . . .
5
BAB 2 TINJAUAN PUSTAKA . . . . . . . . . . . . . . . . . . . .
6
BAB 3 LANDASAN TEORI . . . . . . . . . . . . . . . . . . . . .
8
3.1 Peluang dan penalaran probabilitas . . . . . . . . . . . .
8
3.2 Asumsi pada kebebasan kondisional . . . . . . . . . . . .
9
3.3 Menggunakan Atribut Gabungan untuk Estimasi Probabilitas Akurat . . . . . . . . . . . . . . . . . . . . . . . . . .
12
BAB 4 PARTISI HIMPUNAN ATRIBUT UNTUK SISTEM PENALARAN PROBABILITAS . . . . . . . . . . . . . . . . . . . . . . . 4.1 Evaluasi skema penalaran alternatif . . . . . . . . . . . . vii Sabar : Partisi Himpunan Atribut Untuk Sistem Penalaran Probabilistik, 2009.
16 16
4.2 Induksi Partisi dari Data
. . . . . . . . . . . . . . . . .
24
4.3 Teknik Pengelompokan Heuristik untuk Partisi Induksi . . .
26
4.4 Percobaan Numerical . . . . . . . . . . . . . . . . . . .
32
BAB 5 KESIMPULAN . . . . . . . . . . . . . . . . . . . . . . . .
37
DAFTAR PUSTAKA . . . . . . . . . . . . . . . . . . . . . . . . .
38
viii Sabar : Partisi Himpunan Atribut Untuk Sistem Penalaran Probabilistik, 2009.
DAFTAR GAMBAR
Nomor 4.1
Judul
Halaman
Skema Partisi . . . . . . . . . . . . . . . . . . . . . . . .
ix Sabar : Partisi Himpunan Atribut Untuk Sistem Penalaran Probabilistik, 2009.
17
BAB 1 PENDAHULUAN
1.1 Latar Belakang Kebanyakan permasalahan memerlukan penaksiran yang dibuat dengan kondisi tak pasti. Untuk memberikan penaksiran dari suatu permasalahan diperlukan pemodelan, sehingga mendapatkan proses penalaran probabilistik. Penalaran probabilistik adalah penaksiran suatu pemikiran dari proses probabilistik pada permasalahan. Permasalahan yang ada terdapat unsur atau obyek yang diamati di gunakan sebagai atribut. Dalam tesis ini atribut didefenisikan sebagai unsur yang di amati yang mengandung sifst-sifst tertentu. Untuk mengamati dari seluruh atribut yang ada diperlukan pemodelan. Dari proses pemodelan digunakan atribut sebagai gambaran karakteristik dari suatu permasalahan. Atribut-atribut yang digunakan sebagai gambaran karakteristik dari suatu permasalahan akan dikelompokan menjadi himpunan, yang disebut himpunan atribut. Himpunan atribut ini akan dibuat himpunan bagian yang disebut dengan partisi himpunan atribut. Atribut tersebut mempartisi seluruh himpunan atribut prediksi ke himpunan bagian. Selanjutnya akan dibuat skema partisi untuk mendapatkan data yang optimal. Dari permasalahan pada pencarian skema partisi optimal akan ditunjukkan lima teknik heuristik berbeda (meskipun ada hubungannya satu dan yang lainnya) untuk menghasilkan partisi dari kasus historikal. Dari kelima teknik itu adalah pembagian rantai sederhana (SLC), pembagian rantai utuh (CLC), metode rata-rata pasangan grup tak berbobot (UPGMA). Untuk teknik ke empat dan ke lima adalah teknik agglomeratif yang disebut Delta MI 1 Sabar : Partisi Himpunan Atribut Untuk Sistem Penalaran Probabilistik, 2009.
2 dan Marg MI. Dengan menggunakan data yang tersimulasi, kelima teknik tersebut ditunjukkan untuk mendapatkan kebebasan atribut pada data gabungan yang tersedia untuk dianalisis. Dalam situasi dimana terdapat kasus historikal, penggunaan struktur gabungan kurang akurat. Sehingga penggunaan struktur gabungan untuk membuat prediksi proba.bilitas pada akhirnya didapat dengan menggunakan struktur kebenaran. Akhirnya, diuji untuk validitas eksternal dengan mengaplikasi teknik pada kehidupan sehari-hari misalnya pada aplikasi kredit untuk suatu Bank. Akan ditunjukkan, dengan menggunakan himpunan data, bahwa (i) penggambaran klasifikasi pada sistem penalaran menggunakan struktur tergenerasi dengan teknik heuristik adalah sebaik penggambaran secara luas menggunakan algoritma induksi pohon keputusan dan (ii) struktur gabungan digunakan untuk menunjukkan adanya estimasi probabilitas untuk membuat keputusan dalam permasalahan dengan nilai kekeliruan gabungan yang asimetrik. Pada model probabilitas yang ada untuk skema penalaran didapat pada contoh dari jaringan Bayes. Model tersebut dianggap terdapat satu hipotesis node dan seluruh variabel lainya sebagai bukti node. Sebuah jaringan Bayes, pada umumnya mempunyai multi variabel hipotesis, seperti pada beberapa node lanjutan. Node lanjutan biasanya sesuai disaat terdapat variabel tersembunyi yang dapat mengkontribusi kebebasan variabel hipotesis pada variabel yang tidak tersembunyi. Meskipun model Bayes dengan node lanjutan dapat lebih menyatakan penyelesaian pada umumnya, ini cukup sulit untuk membuatnya dalam sebuah cara dimana data ditinjau, karena sulit untuk menunjukkan estimasi probabilitas termasuk variabel tersembunyi dari data yang diteliti. Distribusi esti-
Sabar : Partisi Himpunan Atribut Untuk Sistem Penalaran Probabilistik, 2009.
3 masi probabilitas untuk variabel tersembunyi merupakan sesuatu yang kompleks secara ekstrim bahkan untuk struktur jaringan yang kecil dan relatif sederhana seperti pohon dan banyak pohon. Banyak permasalahan memerlukan keputusan yang timbul dalam kehidupan bermasyarakat. Misalnya saat evaluasi aplikasi pinjaman pada Bank, seorang penyedia pinjaman menguji atribut relevan dan seorang peminjam untuk mengevaluasi kemungkinan memperoleh pinjaman dari Bank itu.Karena adanya biaya yang cukup besar dan terkadang tidak mungkin untuk mendapatkan semua informasi yang mungkin tentang seorang peminjam, keputusan sering diperoleh setelah adanya pertimbangan antara resiko dan pinjaman yang diberikan ke peminjam dalam suatu cara konsisten yang teoritis, Ini dapat dinyatakan bahwa manusia (bahkan para ahli) sering tidak mampu untuk menunjukkan estimasi akurat pada distribusi probabilitas. Database-database historikal merupakan suatu sumber informasi tentang suatu permasalahan utama, dan dapat digunakan untuk memperoleh ketidakpastian dengan pembuat keputusan dalam permasalahan utama. Solusi pada permasalahan yang ada dapat digunakan untk menunjukkan solusi pada situasi yang ada. Sistem penalaran menghasilkan ketidakpastian yang berasosiasi dengan hasil kemungkinan yang berbeda, dan didasarkan pada data historikal, dapat memberikan atau menetapkan dengan suatu penaksiran pada ketidakpastian. Himpunan atribut digunakan untuk mendeskripsikan suatu kasus yang ditentukan sebagai atribut prediksi, variabel prediksi, atau daftar indeks. Untuk merekomendasikan suatu solusi pada sejumlah permasalahan, dan karenanya identifikasi pada suatu cara alternatif dapat menjadi suatu cara yang baik. Estimasi probabili-
Sabar : Partisi Himpunan Atribut Untuk Sistem Penalaran Probabilistik, 2009.
4 tas dibutuhkan untuk proses penalaran yang diperoleh dari penganalisaan nilai atribut prediksi pada kasus tersebut. Kedepannya, pemodelan yang dapat membatasi atribut ke nilai diskrit. Pada model penalaran ketidakpastian dihubungkan dengan nilai keluaran terestimasi dalam suatu cara yang didasarkan pada teknik klasifikasi Bayes. Himpunan pada variabel dianggap sebagai bagian dari grup yang sama yang disebut atribut gabungan. Atribut gabungan tersebut mempartisi seluruh himpunan pada atribut prediksi ke beberapa himpunan. Analisis utama menunjukkan bahwa penggunaan atribut gabungan dalam model ini untuk estimasi probabilitas dalam suatu cara yang akurat. Dalam ruang lingkup medis, pakar memeriksa seperti yang diperlihatkan pasien untuk merevisi keyakinan para pakar tentang keyakinan penyebab (Shutlife dan Buchanan, 1975). Beberapa penalaran lainya yang menghendaki penalaran dengan adanya kondusi ketidakpastian mencakup deteksi kegagalan dalam sirkuit elektronik (Breinan et al , 1984). Dalam aplikasi demikian ini, meknisme penalaran dan sistim berbasis komputer harus mengikutsertakan ketidakpastian yang ada dalam ruang lingkup persoalan.
1.2 Rumusan Masalah Pemilihan pada atribut individual yang tepat yang akan menjadi suatu atribut gabungan mempengaruhi estimasi probabilitas untuk keluaran kemungkinan yang ada, dan karenanya ada gambaran pada sistem penalaran probabilistik. Bagaimanapun, struktur kebebasan utuh sekitar variabel prediksi selalu tidak
Sabar : Partisi Himpunan Atribut Untuk Sistem Penalaran Probabilistik, 2009.
5 diketahui. Satu cara untuk menunjukkan partisi tersebut adalah memperoleh skema partisi secara langsung dari kasus historikal.
1.3 Tujuan Penelitian Tujuan dari penulisan tesis ini adalah untuk menguji permasalahan tentang perolehan skema partisi dari data historikal ke estimasi yang akurat pada parameter probabilitas yang mendasari model Bayes.
1.4 Manfaat Penelitian Dengan partisi himpunan dan digunakannya pada sistem penalaran E. Manfaat Penelitian probabilistik diharapkan dapat memberi manfaat dalam kehidupan nyata sehari-hari saat mengambil keputusan dalam penalaran suatu permasalahan. Dan dengan memaparkan suatu bentuk partisi himpunan atribut pada suatu distribusi yang mengandung ketidakpastian, maka didapatkan bentuk penyelesaian yang mudah.
1.5 Metode Penelitian Dalam penelitian ini akan dibahas tentang: 1. Sistem penalaran probabilistik 2. Penalaran probabilistik kasus historikal 3. Skema partisi alternatif
Sabar : Partisi Himpunan Atribut Untuk Sistem Penalaran Probabilistik, 2009.
BAB 2 TINJAUAN PUSTAKA
Wason dan Johnson-Laird (1972) menjelaskan bahwa penggunaan penalaran probabilistik memudahkan pencarian penyelesaian representasi psikologis yang berbeda. Ini diasumsikan pada permasalahan yang melibatkan sebuah bentuk partisi sederhana pada ruang sampel yang menggunakan parameter dasar yang didasarkan pada deskripsi suatu permasalahan. Coole (1986) menyebutkan suatu bentuk diagram elegan untuk penjelasan tentang langkah sederhana Bayesian yang disebut dengan pemetaan probabilitas. Adapun Cooled dan Davidson (1989) membandingkan keefektifan pada pemetaan probabilitas subjek yang bertambah dengan metode yang cukup sering digunakan, seperti tabel kotingensi dan fungsi deteksi sinyal. Dabholkar (1996) dengan pemodelan atribut mendasari tiori pada pengambilan keputusan. Ma et al (2001) menggunakan pendekatan pengambilan keputusan atribut ganda berdasarkan pada pemilihan impormasi dan alternatif. Shafer (1976) teori telah menghasilkan dan digunakan untuk mengatasi masalah ketidakpastian Et Ghobadian al , (1994 ) konseptual pemodelan untuk menunjukan hubungan antar variabel. HaywoodFarmer, (1988) penggunaan atribut ke dalam berbagai kelompok menjadi langkah yang pertama ke arah pengembangan untuk memberi bantuan mutu pemodelan. Parasursman et al, (1988) pemodelan yang konseptual, teoritis didalam permasalahan pengukuran Sumit Sarkar (1998) probabilitas merupakan merupakan solusi yang tepat untuk setiap kemungkinan dugaan pengeluaran dari permasalahan nilai atribut. 6 Sabar : Partisi Himpunan Atribut Untuk Sistem Penalaran Probabilistik, 2009.
7 Breinan et al penalaran dengan adanya kondusi ketidakpastian mencakup deteksi ke gagalan dalam sirkuit elektronika. Buntine, Clark dan Niblett (1998) membandingkan tehnik Bayesin sebagai suatu alat mengklasifikasi dengan beberpa tehnik pohon induksi. De Mantaras (1998) menyebutkan baphwa suatu informasi taksiran yang berhubungan menggunakan sebuah faktor normalisasi yang berbeda untuk mengurangi kemampuan atribut yang meragukan. Ng dan Lloyd (2007) mengajukan penalaran probabilitas untuk dipakai dalam logika berordo tinggi. Bentuk penalaran probabilitas dalam persoalan logika juga disampaikan oleh Baral et al (2006).
Sabar : Partisi Himpunan Atribut Untuk Sistem Penalaran Probabilistik, 2009.
BAB 3 LANDASAN TEORI
3.1 Peluang dan penalaran probabilitas Pada bagian ini, akan dilakukan model probabilitas yang layak dengan bantuan kasus historikal. Seluruh atribut merupakan variabel kontinu ke data diskrit, dan akan dibahas dalam tesis ini. Dalam bagian keluaran digunakan untuk menghubungkan ke solusi yang tepat pada permasalahan. Ini didapat untuk membedakan antara dugaan solusi yang didapat untuk suatu kasus historikal dan hasil yang tepat pada kasus. Lebih jelasnya, dalam aplikasi peminjaman, seseorang peminjam telah diberikan sebuah peminjaman, namun mungkin tak sanggup untuk pembayaran. Saat kasus ini termasuk ke dalam data historikal, yang tepat bahwa kegagalan peminjaman adalah keadaan pengeluaran harus diperhatikan (dan bukan dugaan pada pembayaran kembali yang merujuk ke persetujuan pada peminjaman). Ini memperbolehkan sistem untuk menelaah dari kesalahan yang lalu. Ini diasumsikan bahwa pada setiap kebanyakan aplikasi, terdapat suatu himpunan terbatas pada dugaan pengeluaran. Lebih jauhnya, setiap kasus digabungkan dengan suatu dugaan pengeluaran . Dalam model probabilistik, kasus historikal digambarkan sebagai suatu kelompok pada atribut yang bebas secara probabilistik pada dugaan pengeluaran. Untuk kasus yang baru, didasarkan pada nilai atribut yang diteliti untuk permasalahan ini, dalam sistem penalaran dilakukan mengevaluasi, untuk setiap kemungkinan dugaan pengeluaran, probabilitas merupakan solusi yang tepat. Anggap himpunan atribut digunakan untuk prediksi sebagai X1 , . . . , Xn dan ke8 Sabar : Partisi Himpunan Atribut Untuk Sistem Penalaran Probabilistik, 2009.
9 luaran sebagai A. Jika suatu permasalahan baru dengan asumsi mempunyai nilai atribut X = x (dimana mempresentasikan realisasi X1 = x1 , . . . , Xn = xn ), fungsi evaluasi pada tiap kemungkinan nilai pengeluaran ai adalah estimasi pada ekspresi probabilitas P (A = ai|X = x). Sehingga, jika ada sepuluh kasus historikal dengan nilai atribut yang sama, dan delapan diantaranya dihasilkan dalam pengeluaran ai , maka estimasi probabilitas untuk P (A = ai|X = x) menjadi 0,8. Estimasi probabilitas untuk pengeluaran tepat lainnya dapat diperoleh dengan cara yang sama.
3.2 Asumsi pada kebebasan kondisional Meskipun skema diatas sangat baik, ini sulit untuk mengimplementasikan pada penalaran berikut. Pada saat jumlah besar pada atribut yang diasumsikan, kemungkinan perolehan kasus historikal yang mempunyai himpunan sama pada nilai atribut sangat rendah. Lebih jelasnya, jika terdapat sepuluh atribut biner, kemungkinan jumlah pada realisasi yang nyata lebih dari seribu. Jika sekarang dibutuhkan contoh yang lebih banyak pada himpunan yang sama dari nilai atribut untuk estimasi probabilitas yang dibutuhkan dengan tepat, contohnya dibutuhkan sepuluh ribu kasus untuk menunjukan estimasi realitis. Saat terdapat himpunan besar pada atribut atau atribut mempunyai nilai ganda, ukuran pada dugaan bertambah pada suatu tingkat eksponensial. Untuk menghindari data yang sangat besar, suatu asumsi yang selalu dibuat adalah bahwa kebebasan kondisional pada nilai atribut, diberikan dugaan pengeluaran. Dua atribut X1 dan X2 secara kondisional bebas satu dengan yang lainnya berdasarkan dugaan pengeluaran A jika P (X1 = x1|A = a1, X2 = x2) =
Sabar : Partisi Himpunan Atribut Untuk Sistem Penalaran Probabilistik, 2009.
10 P (X1 = x1 |A = a1) untuk seluruh kemungkinan realisasi pada X1 , X2 dan A. Basis yang mendasari untuk membuat asumsi dalah sebagai berikut. Nilai atribut yang membantu untuk memprediksikan dugaan pengeluaran yang digambarkan sebagai realisasi yang refleks. Karenanya, jika dugaan pengeluaran yang telah diketahui, maka dugaan pada nilai untuk setiap atribut harus didasarkan hanya pada pengeluaran saja, dan tidak pada nilai atribut lainnya. Menggunkan interpretasi ini, mungkin untuk estimasi dengan tepat pada probabilitas yang ada P (A = ai |X = x) tanpa membutuhkan sebanyak data sebelumnya. Dengan menggunakan aturan Bayes dan asumsi kebebasan kondisional, didapatkan P (A = ai |X = x) P (A = ai |X = xP (A = ai ) P (A = ai |X = x P (A = ai )Πj P (X = xj |A = ai ) = P (X = x P Persamaan P (A = ai|X = x sama dengan i (P (A = ai )Πj P (X = xj |A = =
ai )). Saat menggunakan ekspresi diatas, probabilitas digabungkan dengan dugaan perbedaan pengeluaran yang dapat diuji dengan mudah. Seluruh komponen probabilitas dalam pernyataan diatas dapat diestimasi dari beberapa kasus yang relatif, karena ini mudah untuk mendapatkan nilai yang cocok dengan atribut individual. Produser ini mudah diperluas ke permasalahan dimana suatu jumlah besar pada atribut prediksi yang digunakan, dan atribut yang bernilai ganda. Dengan ilustrasi tersebut, angap permasalahan pada komersial peminjaman bank. Seacra objektif adalah untuk mengevaluasi kualitas pada aplikasi peminjaman antara ”baik” dan ”kurang baik” (hasil LQ dengan nilai baik atau kurang baik). Dua atribut penting digunakan untuk mengevaluasi peminjaman adalah (i) jumlah peminjaman sebagai suatu persentase pada seluruh total debit pada
Sabar : Partisi Himpunan Atribut Untuk Sistem Penalaran Probabilistik, 2009.
11 peminjaman (variabel RLTDdengan kelas diatas 10% dan dibawah 10%), dan (ii) indikator kemungkinan keuntungan pengembalian (variabel RNW dengan kelas diatas 15% dan dibawah 15%). Diasumsikan bahwa dua atribut prediksi RLTD dan RNW adalah bebas secara kondisional satu dan lainnya dengan berdasarkan pada LQ. Maka, prbabilitas pada LQ baik atau kurang baik saat diberikan RLTD = diatas 10% dan RNW = diatas 15% oleh P (LQ = Baik|RLT D) = diatas 10% dan RNW = diatas 15%) = (1/K) ∗ P (RLT D = diatas 10%|LQ = Baik ) ∗ P (RNW = diatas 15%|LQ = Baik) ∗ P (LQ = Baik ) &P (LQ = kurang baik |RLT D = diatas 10% &RNW = diatas 15%) = (1/K) ∗ P (RLT D = diatas 10% |LQ = kurang baik ) ∗ P (RNW = diatas 15% |LQ = kurang baik ) ∗ P (LQ = kurang baik ) Dimana K = P (RLT D = diatas 10% |LQ = baik ) ∗ P (RNW = diatas 15% |LQ = baik ) ∗ P (LQ = Baik ) + P (RLT D = diatas 10% |LQ = kurang baik ) ∗ P (RNW = diatas 15% |LQ = kurang baik ) ∗ P (LQ = kurang baik ) Seluruh komponen probabilitas pada pernyataan diatas dapat diestimasi secara tepat dari jumlah kecil pada data historikal.
Sabar : Partisi Himpunan Atribut Untuk Sistem Penalaran Probabilistik, 2009.
12 Dikemukakan bahwa teknik ini bekerja dengan baik sebagai alat pengklasifikasi dalam kebanyakan permasalahan yang berbeda. Cheeman mengemukakan pada teknik ini, yang disebut teknik klasifikasi Bayesian, bekerja dengan baik pada Fisher’s Iris Database dan the Soybean Disease database. Buntine, Clark dan Niblett, Langley dan Sage telah membandingkan gambaran pada teknik ini sebagai suatu alat pengklasifikasi dengan beberapa teknik pohon induksi. Dari seluruhnya, hasil yang didapat bercampur aduk. Setelah mengadakan penelitian pada database ganda, mereka menjelaskan bahwa teknik ini menghasilkan teknik pohon induksi pada beberapa kebanyakan permasalahan, saat teknik pohon induksi memberikan hasil yang lebih baik. Buntine menemukan bahwa teknik klasifikasi Bayesian secara particular sesuai dengan permasalahan yang merupakan stokastik yang tak dapat dipisahkan secara alami (akibatnya, dimana tidak tepat untuk melengkapi penyelesaian ketidakpastian yang digabungkan dengan dugaan yang tepat sebelummembuat keputusan). Pada kebanyakan jenis ini, teknik ini sering menunjukkan ke hasil signifikan pada teknik pohon induksi. Sehingga, ini sangat cocok untuk jenis pada aplikasi yang ada.
3.3
Menggunakan Atribut Gabungan untuk Estimasi Probabilitas Akurat Dalam praktiknya, terdapat kemungkinan bahwa tidak semua atribut predik-
sibebas secara kondisional satu dan lainnya yang menghasilkan keluaran dugaan. Lebih jelasnya, kedua atribut RNW dan Return Assets (variabel ROA diklasifikasikan diatas 8% dan dibawah kedua keuntungan pada seorang peminjam). Pada lain pihak, mungkin tidaklah bebas secara kondisional yang memberikan suatu realisasi pada LQ. Pada situasi ini cara yang benar untuk mengetimasi pro-
Sabar : Partisi Himpunan Atribut Untuk Sistem Penalaran Probabilistik, 2009.
13 babilitas digabungkan dengan dugaan pengeluaran yang berbeda yang dianggap sebagai himpunan pada gabungan atribut. Peninjauan kembali pada probabilitas untuk hasil LQ baik, diberikan nilai atribut RLTD = diatas 10%, RNW = diatas 15% dan ROA = diatas 8% P (LQ = Baik |RLT D = diatas 10% &RNW = diatas 15% &ROA = diatas 8% ) = (1/K) ∗ P (RLT D = diatas 10% |LQ = Baik ) ∗ P (RNW = diatas 15% &ROA = diatas 8% |LQ = Baik ) ∗ P (LQ = Baik ) Dimana K adalah faktor pengembalian yang sesuai untuk fungsi evaluasi. Pada pernyataan ini, atribut RNW dan ROA dianggap sebagai suatu atribut gabungan saat digunakan untuk mengatifkan probabilitas. Pernyataan untuk P(LQ = kurang Baik—RLTD = diatas 10% & RNW = diatas 15% & ROA = diatas 8%) diperoleh dengan cara yang sama, dan hasil yang dinormalisasikan digunakan seperti sebelumnya. Penggunaan atribut bangunan menunjukkan banyak estimasi probabilitas yang akurat. Atribut gabungan tersebut mempartisi seluruh himpunan pada atribut sederhana, dimana setiap atribut sederhana merupakan bagian dari satu gabungan atribut.
Anggap Y2 , . . . , T sebagai himpunan yang dispesifikasikan
maka terbentuk himpunan atribut. Maka, perolehan probabilitas yang utama untuk dugaan pengeluaran A = ai diberikan realisasi Y 1 = y 1 , Y 2 = y2 , . . . , Y r = y r sehingga diperoleh sebagai P (A = ai )|Y 1 = y1 , Y 2 = y 2 , . . . , Y r = yr P (A = ai ) Y = P (Y j = y j | A = ai ) K j=1,r
Sabar : Partisi Himpunan Atribut Untuk Sistem Penalaran Probabilistik, 2009.
14
Dimana K =
P i
"
P (A = ai )
Q
#
P (Y j = y j | A = ai )
j=1,r
Secara operasional, seluruh atrubut sederhana didapatkan sebelum dijadikan sebagai suatu atribuit gabungan hanya saat digunakan menaksir probabilitas yang penting. Jumlah realisasi untuk suatu atribut gabungan adalah produksi Cartesius, pada jumlah realisasi untuk suatu realisasi tiap komponen artibut sederhana. Penaksiran probabilitas digabungkan dengan suatu dugaan pengeluaran yang diuji dengan estimasi pertama probabilitas pada tiap komponen pada bagian yang benar (dievaluasi dari kasus yang ada) dan kemudian memperoleh hasilnya. Satu dari hasilnya untuk srmua kemungkinan pengeluaran yang telah dievaluasikan, dinormalisasikan untuk menghitung kondisi probabilitas penting. Probabilitas tersebut, pada kebalikanya ,digunakan untuk menujukan proses pembuatan keputusan. Ini harus dikemukakan bahwa penggunaan pada atribut gabungan menujukan persyaratan yang dibutuhkan data tinggi dibandingkan situasi dimana seluruh atribut dianggap bebas secara kondisional. Sebagai jumlah pada realisasi yang tepat pada sutu atribut gabungan yang bertambah, jumlah pada data dibutuhkan untuk memmbuat estimasi probabilitas tepat yang bertambah. Skema penalaran probabilistik menyediakan beberapa fungsi penting pada suatu sitem terautomatisasi dalam aplikasi yang membutuhkan pembuatan keputusan dengan kondisi tak pasti. Dalam kebanyakan aplikasi, proses penalaran memerlukan inpormasi yang terbukti untuk menghasilkan dan penganalisaan pada permsalahan. Lebih jelasnya, dalam contoh evaluasi peminjaman yang dijelaskan, seorang penyedia pinjaman mungkin memilih untuk memperoleh suatu kredit yang detail untuk suatu aplikasi saat informasi yang tersedia tidak menghasilkan suatu keputusan yang tepat. Dalam situasi seperti ini, informasi terbaru yang
Sabar : Partisi Himpunan Atribut Untuk Sistem Penalaran Probabilistik, 2009.
15 diperoleh harus dimengerti dengan informasi yang telah tersedia dan dapat digunakan untuk menganalisis hasil altetrnatif. Hasil informasi dan proses asimilasi dapat diteruskan hingga inpormasi yang tersedia menuju ke sebuah prediksi yang akurat, atau semua sumber kemungkinan inpormasi dapat dicapai. Skema penalaran probabilistik dapat mengandung berbagai persyaratan atau keperluan dengan mudah. Saat mengevaluasi suatu permasalahan baru, seluruh nilai atribut yang ada digunakan untuk memperoleh estimasi probabilitas mendapatkan setiap pengeluaran. Saat sebuah pembuktian baru diteliti sehinga dapat digunakan dengan mudah untuk meninjau kembali nilai kepercayaan didasarkan pada pengeluaran yang berbeda. Ditunjukan bagaimana revisi pada nilai kepercayaan yang pasti oleh proses estimasi hanya pada beberapa tambahan parameter probabilitas dari kasus. Prosedur revisi nilai kepercayaan menggambarkan beberapa sifat yang sangat dibutuhkan. Saat pembuktian ganda telah diteliti dan diasimilasikan oleh sistem, ini akan menuju pada distribusi utama yang sama untuk pengeluaran tanpa bergantung pada urutan dimana pembuktian telah ditelaah.
Sabar : Partisi Himpunan Atribut Untuk Sistem Penalaran Probabilistik, 2009.
BAB 4 PARTISI HIMPUNAN ATRIBUT UNTUK SISTEM PENALARAN PROBABILITAS
4.1 Evaluasi skema penalaran alternatif Dengan menggunakan seluruh atribut secara sederhana, beberapa atribut bergantung pada atribut lainya, yang dapat menunjukan keputusan yang salah. Ini muncul dikrenakan oleh penggunaan atribut yang berhubungan dengan atribut bebas secara kondisional untuk penghitungan ganda pada efek dari variabelvariabel tersebut pada estimasi probabilitas terakhir. Sebagai hasilnya, dengan tambahan untuk mengidentifikasi seluruh atribut yang relevan, ini juga penting untuk mengidentifikasi dimana atribut tersebut juga harus dibandingkan bersama dengan atribut yang lanya sebagai atribut gabungan. Atribut gabungan tersebut mempartisi seluruh himpunan pada atribut prediksi ke beberapa himpunan. Dalam kebanyakan aplikasi kompleks, mengidentifikasikan himpunan yang benar pada atribut gabungan dapat menjadi sesutu yang sulit. Satu cara untuk mendapatkanya adalah dari anggapan pada sitem yang dibentuk. Bersama dengan mengidentifikasikan, atribut yang relevan dan kategori penyelesaian permasalahan, banyak anggapan bahwa himpunan atribut relevan dianggap sebagai atribut gabungan. Saat banyak anggapan tidak dapat menunjukan suatu partisi pada atribut prediksi, suatu cara alternatif untuk mendapatkan partisinya adalah dengan mengiduksikanya dari kasus itu sendiri. Pada bagian ini, akan dibicarakan tentang metrik 1-Divergence untuk membandingkan skema partisi alternatif, dan menghasilkan beberapa karaketristik yang berguna pada solusi optimal. 16 Sabar : Partisi Himpunan Atribut Untuk Sistem Penalaran Probabilistik, 2009.
17
Gambar 4.1 Skema Partisi Permasalahannya adalah untuk mengidentifikasi suatu skema partisi yang tepat yang akan memberikan atribut prediksi (kadang-kadang dalam bentuk yang sederhana)ke tepat satu atribut gabungan. Idealnya, atribut sederhana yang ada untuk membedakan atribut-atribut gabungan yang harus bebas secara kondisional satu dan yang lainnya dimana diberikan suatu keluaran. Atribut sederhana yang termasuk ke atribut gabungan yang sama dapat saja tidak bebas secara kondisional satu dan yang lainnya pada nilai keluaran yang diberikan. Misalkan suatu permasalahan utama dengan empat atribut prediksi, X1 , . . . , X4 . Anggap terdapat dua partisi alternatif, S1 dan S2, sebagai partisi yang tepat untuk permasalahan ini. Anggap S1 sebagai partisi {(X1 , X2 ) , (X3 ) , (X4 )} dan S2 sebagai partisi {(X1 ), (X2 ), (X3 , X4 )}. Lebih jelasnya, misalnya Pt (X, A) sebagai daerah asal sekitar atribut dan variabel-variabel keluaran, dimana X menunjukkan keempat tribut, dan A menunjukkan keluaran. Fungsi evaluasi menggunakan distribusi yang tepat untuk setiap himpunan sembarang pada nilai atribut X = x adalah Pt (A = a| X = x)∞Pt (X = x| A = a) ∗ Pt (A = a) Jika partisi S1 digunakan
Sabar : Partisi Himpunan Atribut Untuk Sistem Penalaran Probabilistik, 2009.
18 untuk mencari penyelesaian, maka PS1 (A = a| X = x)∞PS1 (X = x| A = a) ∗ PS1 (A = a) = PS1 (X1 = x1, X2 = x2| A = a) ∗ PS1 (X3 = x3 | A = a) ∗ PS1 (X4 = x 4 | A = a) ∗ PS1 (A = a) Hampir sama, menggunakan partisi S2 akan di dapatkan PS2 (A = a| X = x)∞PS2 (X 1 = x1| A = a) ∗ PS1 (X2 = x 2| A = a) ∗ PS1 (X3 = x3, X4 = x4| A = a) ∗ PS2 (A = a) Pada bagian persamaan 1 adalah probabilitas gabungan untuk realisasi yang terindikasi, dengan asumsi kebebasan kondisional secara mutlak dalam partisi S1. Ddengan cara yang sama, pernyataan pada persamaan 2 adalah hasil probabilitas gabungan dengan asumsi kebebasan kondisional pada partisi S2. Jika dari kedua probabilitas gabungan sangat cocok dengan hasil probabilitas yang digabungkan dengan distribusi yang tepat Pt (X, A), maka ada satu yang harus dipilih. Pada umumnya, tak ada satupun yang dapat menjadi penyelesaian sempurna yang dapat diselesaikan dengan kasus historikal. Maka untuk gambaran prediksi sempurna, solusi yang dipilih harus satu yang hasilnya ada dalam suatu probabilitas gabungan yang mendekati pada distribusi probabilitas. Pada bagian persamaan 1 adalah probabilitas gabungan untuk realisasi yang terindikasi, dengan asumsi kebebasan kondisional secara mutlak dalam partisi S1. Ddengan cara yang sama, pernyataan pada persamaan 2 adalah hasil probabilitas gabungan dengan asumsi kebebasan kondisional pada partisi S2. Jika dari kedua probabilitas gabungan sangat cocok dengan hasil probabilitas yang digabungkan dengan distribusi yang
Sabar : Partisi Himpunan Atribut Untuk Sistem Penalaran Probabilistik, 2009.
19 tepat Pt (X, A), maka ada satu yang harus dipilih. Pada umumnya, tak ada satupun yang dapat menjadi penyelesaian sempurna yang dapat diselesaikan dengan kasus historikal. Maka untuk gambaran prediksi sempurna, solusi yang dipilih harus satu yang hasilnya ada dalam suatu probabilitas gabungan yang mendekati pada distribusi probabilitas. Probabilitas gabungan yang ditunjukan pada persamaan 1 dan 2 menunjukan pada suatu himpunan yang spesifik pada penelitian untuk atribut prediksi, dan sebuah keluaran yang dispesifikasi. Sehingga dievaluasi seperi probabilitas untuk semua kemungkinan keluaran. Lebih jauhnya, setiap kombinasi pada realisasi dari atribut yang berbeda adalah tepat dalam menentukan penyelesaianya. Karenanya akan dipilih partisi yang menuju suatu probabilitas gabungan yang mendekati pada distribusi yang tepat pada seluruh himpunan padarealisasi untuk himpunan dan variabel-variabel keluaran Ini diimplikasikan bahwa pemilihan diantara skema partisi alternatif akan bergantung pada yang mana cara yang akan menghasilkan sebuah distribusi gabungan yang mendekati distribusi yang tepat. Penaksiran 1-Dipergence telah digunakan secara luas pada distribusi penaksiran dengan satu nilai yang tepat . Ini didefinisikan sebagai perbedaan dalam informasi yang terdapat pada distribusi yang sebenarnya p dan informasi yang terdapat pada distribusi penaksiran Pa (·) = r pada distribusi sebenarnya Pt (·) = P . Ini telah ditunjukan bahwa terdapat sifst-sifat yang diperlukan dalam mengidentifikasi gambaran probabilitas yang lebih mendekati distribusi yang dari distribusi lainnya. Untuk suatu distribusi penaksiran Pa (·) taksiran D(p, r) ditunjukan sebagai D(p, r) =
X
pi log
i
pi ri
Jika distribusi Pa (·) identik kePt(·) maka taksiran 1-Divergence menaksir ke nol
Sabar : Partisi Himpunan Atribut Untuk Sistem Penalaran Probabilistik, 2009.
20 atau lebih dari nol. Suatu sifat penting pada taksiran ini adalah bahwa ini merupakan trasformasi linier pada aturan logaritma, dan karenanya menunjukan pada suatu kelompok pada aturan penilaian yang tepat. Suatu aturan penilaian dianggap benar jika nilai yang ditunjukan deangan suatu distribusi digunakan untuk menaksir distribusi lainya (distribusi yang tepat) yang tidak dapat lebih besar dibandingkan dengan nilainyadidasarkan pada distribusi yang tepat itu sendiri (saat nilai paling besar digunakan ). Sehingga satu diantara kedua partisi S1 dan S2 dapat digunakan dengan membandingkan I(Pt (·), PS1 (·)) dan I(Pt (·), PS2 (·)), dan memilih satun dengan suatu 1-Divergence yang rendah . Perbandingan ini mungkin merupakan gambaran yang lebih sederhana karena pernyataan untuk taksiran 1-Divergence dapat dihilangkan ke komponen yang lebih sederhana. Akan dilihatkan konsep pada informasi yang berhubungan sekitar himpunan variabel, dan menunjukan bahwa ini dapat digunakan untuk membandingkan skema partisi alternatif dalam cara yang mudah. Jika variabel X1 , . . . , Xr terdapat sebuah atribut gabungan, dan A adalah variabel keluaran, maka informasi yang berhubungan sekitar variabel X1 . . . . , Xr dan A dapat didefinisikan sebagai I(A; X1; . . . ; Xr ) =
X
P (A, X1, ..., Xr ) log
A,X1 ,...,X2
P (A, X1 , ..., Xr ) P (A)P (X1 )...P (Xr )
Pernyataan informasi yang berhubungan menggambarkan daerah yang berhubungan sekitar himpunan variabel X1 , . . . , Xr dan A. Semakin tinggi ketergantungan variabel pada satu dan lainnya, semakin tinggi informasi yang berhubungan sekitar variabel tersebut. Anggap I-Divergence digabungkan dengan par-
Sabar : Partisi Himpunan Atribut Untuk Sistem Penalaran Probabilistik, 2009.
21 tisi S1. Maka, I(Pt (·), PS1 (·)) =
X
Pt (·) log
A,X
=
X
Pt (·) log Pt (·) −
A,X
X
Pt (·) PS1 (·)
Pt (·) log PS1 (·)
A,X
Pada bagian pertama tidaklah bergantung pada partisi pengasumsian, dan karenanya dapat diabaikan saat membandingkan skema partisi alternatif. Kita dapatkan PS1 (.) = PS1 (X1 , X 2 | A) ∗ PS1 (X 3 | A) ∗ PS1 (X 4 | A) ∗ PS1 (A). Untuk semua realisasi pada atribut dan variabel keluaran. Sehingga, X
Pt (·) log PS1 (·) =
X
Pt (·) log PS1 (X1 , X 2 | A)
A,X
+
X
Pt (·) logPS1 (X 3| A)
+
X
Pt (·) logPS1 (X 4| A)
+
X
Pt (·) logPS1 (A)
Dimana penjumlahan pada semua kemungkinan realisasi pada variabel. Distribusi probabilitas PS1 (X1 , X 2 | A), PS1 (X 3 | A), PS1 (X 4 | A) dan PS1 (A) diestimasi dari kasus yang berkaita, dan karenanya sama dengan hasil estimasi untuk distribusi yang tepat. Akibatnya, PS1 (A) = Pt (A) untuk seluruh realisasi. Maka, ini berlaku bahwa X
Pt (·) log PS1 (·) =
X
Pt (X1 , X2 , A) log PS1 (X1 , X 2 | A)
A,X
+
X
Pt (X3 , A) logPt (X 3 | A)
+
X
Pt (X4 , A) logPt (X 4 | A)
+
X
Pt (A) logPt (A)
Sabar : Partisi Himpunan Atribut Untuk Sistem Penalaran Probabilistik, 2009.
22 Dengan penghitungan aljabar daerah Pt (X1 , X2 |A) kita dapatkan X
Pt (X1 , X2 |A) log Pt (X1 , X2 |A) X = Pt (X1 , X 2 | A) log
Pt (X1 , X 2 | A) Pt (X1 )P1 (X2 )Pt (A) X X + Pt (X1 ) log +Pt (X1 ) + Pt (X1 ) + Pt (X2 ) + Pt (X2 )
Daerah pertama diatas menyatakan hasil pada informasi yang berhubungan sekitar variabel X1 , X2 dan A. Kedua daerah lainnya hasilnya hasilnya merupakan negative pada entropies untuk variabel X1 dan X2 . Karenanya, kita dapatkan X
Pt (X1 , X2 , A) logPt (X 1 , X2 | A)
= MI(X1 ; X2 ; A) − H(X1 ) − H(X2 ) Dimana MI(., ., .) dan H(·) hasil dari informasi yang berhiubungan dan pernyataan entropy, berturut-turut. Dengan cara yang sama, kita dapat tunjukkan bahwa X
Pt (X3 , A) logPt (X 3 | A) = MI(X3 ; A) − H(X3 )
X
Pt (X4 , A) logPt (X 4 | A) = MI(X4 ; A) − H(X4 )
Sebagai suatu hasilnya, kita didapatkan X
Pt (·) log PS1 (·) =MI(X1 ; X2 ; A) + MI(X3 ; A)
A,X
+ MI(X3 ; A) − H(X1 ) − H(X2 ) − H(X3 ) − H(X4 ) − H(XA ) Dengan cara yang sama, kita dapat tunjukkan bahwa, untuk partisi S2, X
Pt (·) log PS2 (·) =MI(X1 ; A) + MI(X2 ; A) + MI(X3 , ; X4 ; A)
A,X
− H(X1 ) − H(X2 ) − H(X3 ) − H(X4 ) − H(XA )
Sabar : Partisi Himpunan Atribut Untuk Sistem Penalaran Probabilistik, 2009.
23 Saat membandingkan pernyataan 3 dan 4 yang digabungkan, secara berturut, dengan partisi S1 dan S2, daerah entropy dapat diabaikan. Daerah informasi yang berhubungan dan dibutuhkan untuk setiap partisi merupakan hasil ke atribut gabungan pada partisi tersebut. Karenanya, partisi yang menuju ke suatu IDivergence terendah merupakan satu daerah informasi yang berhubungan dengan nilai jumlah terbesar. Sebagai hasilnya, partisi S1 digunakan jika MI(X1 ; X2 ; A) + MI(X3 ; A) + MI(X4 ; A) > MI(X1 ; A) + MI(X2 ; A) + MI(X3 ; X4 ; A) Lainnya, partisi S2 digunakan. Karenanya, perbandingan pada skema partisi alternatif ditemukan oleh daerah informasi yang berhubungan dan digabungkan dengan setiap skema. Kerena informasi mutu sekitar suatu himpunan pada variabel tersebut, pemilihan penggunaan partisi yang cendrung merupakan atribut tergantung yang digabungkan ke atribut gabungan.Ini mencegah adanya penghitungan ganda pada tingkat kepercayaan yang bertambah ke nilai keluaran terakhir didasarkan pada atribut individu yang parsial satu sama lainya. Ini dapat ditunjukan bahwa permasalahan tersebut ditunjukan dalam pencarian yang berbeda dari evaluasi pada partisi dalam konteks padainduksi pohon keputusan. Perbedaan yang paling penting adalah bahwa kecendrungan pada pembentukan partisi pada atribut prediksi yang berbeda, bagaimanapun, dalam pembagian pencarian,kasus historikal itu sendiri dipartisi ke kategori berbeda dengan tujuan mengidentifikasi suatu informasi strategi tambahan. Bagaimanapun, ini penting untuk menapsirkan bahwa informasi yang berhubungan dengan metrik digunakan untuk permasalahan ini, sehingga berhubungan lebih dekat ke beber-
Sabar : Partisi Himpunan Atribut Untuk Sistem Penalaran Probabilistik, 2009.
24 apa metrik yang biasa digunakan dalam pencarian .Kriteria yang menguntungkan ini digunakan oleh Qinlan sebagai suatu taksiran informasi yang berhubungan terevaluasi sekitar variabel keluaran dan setiap atribut yang dianggap untuk kasus partisi variabel, saat rasio keuntungan mrupakan taksiran keuntungan yang dinormalisasikan untuk mengurangi atribut yang meragukan dengan himpunan besar pada realisai yang tepat. De Mantaras menyebutkan bahwa suatu informasi taksiran yang berhubungan menggunakan sebuah faktor normalisasi yang berbeda untuk mengurangi kemampuan atribut yang mergukan. Fisher menggunakan sebuah kategori penaksiran yang dipaparkan oleh Gluck dan Corter . Kategori penaksiran tersebut didasarkan pada dugaan dari suatu nilai yang diduga dapat ditunjukan dan digunakan untuk memperkirkan nilai dari sebuah atribut dengan suatu probabilitas yang sama dengan kemungkinan pada perkiraan bahwa nilai (seperti yang diduga lebih cepat, taksiran 1-Divergence dan informasi yang berhubungan metrik adalah ekuivalen untuk menggunakan aturan penilaian logaritma).
4.2 Induksi Partisi dari Data Saat akan menggunakan skema partisi, sering kali suatu kebutuhan pada percobaan bahwa atribut gabungan dibatasi dalam jumlah, pada atribut sederhana yang ada didalamnya. Untuk lebih jelasnya, anggap suatu situasi ekstrim dimana tidak ada atribut prediksi yang bebas secar kondisional pada atribut lainya. Solusi optimal secara teori dapat digunakan untuk semua atribut yang digabungkan saat estimasi probabilitas. Bagaimanapun, ini dapat manjadi sesuatu yang sulit untuk mendapatkan estimasi probabilitas yang tepat karena terdapat bayak kasus his-
Sabar : Partisi Himpunan Atribut Untuk Sistem Penalaran Probabilistik, 2009.
25 torikal, jika ada, akan mecocokan dengan permasalahan baru pada pada seluruh himpunan dari nilai atribut yang diteliti. Dengan kata lain, jika setiap atribut bebas secara kondisional pada seluruh nilai keluaran lainya yang diberikan, estimasi probabilitas terakhir dapat ditunjukan dengan estimasi dari kasus komponen, dari setiap komponen tersebut melibatkan variabel keluaran dan hanya satu atribut prediksi . Dalm situasi ini relatif mudah untuk mendapatkan kecocokan ganda pada nilai atribut untuk estimasi probabilitas yang tepat. Pada umumnya, sebagai ukuran pada atribut gabungan yang bertambah, ini sulit untuk mementukan kecocokan yang cukup untuk esmasi probabilitas yang tepat. Pertama diformulasikan permasalahanya pada penunjukan solusi optimal yang membatasi ukuran, dan menunjukan bahwa ini menuju ke kelas permasalahan NP. Selanjutnya, dibahas suatu prosedur solusi heuristik untuk permasalahan ini yang efisien secara komputasi. Permasalahan dalam menentukan skema partisi optimal yang membatasi ukuran adalah satu dari partisi yang dihasilkan nilai terbesar pada penjumlahan dari informasi yang berhubungan, digabungkan dengan setiap atribut gabungan sehingga seluruh atribut gabungan membatasi jumlah pada komponen atribut sederhana. Anggap m sebagai nilai maksimum pada komponen dimana didapat suatu atribut gabungan. Untuk menghasilka skema partisi optimal ,dibutuhkan suatu masukan atau input seluruh informasi yang berhubungan untuk menunjukan ke atribut gabungan termasuk pada m atribut. Tentu saja , untuk mnunjukan daerah informasi yang berhubungan pertma kali harus mengestimasi hasil distribusi gabungan sekitar atribut prediksi dan variabel keluaran. Contoh permasalahan Misalnya: Suatu himpunan variabel prediksi Xi , i = 1, . . . , n dan variabel ke-
Sabar : Partisi Himpunan Atribut Untuk Sistem Penalaran Probabilistik, 2009.
26 luaran C. Daerah informasi yang berhubungan MI (C; Xi ; . . . ; Xk ) digabungkan dengan seluruh kombinasi pada k variabel prediksi, dimana k = 1, . . . , m. Permasalahanya, bagaimana menentukan himpunan pada atribut gabungan yang menghasilkan penjumlahan terbesar pada daerah informasi yang berhubungan dan memenuhi ukuran. Permasalan partisi batasan ukuran enuju ke kelas pada permasalahan NP. Teorema 1 dalam Apendiks A menunjukan sebuah pembuktian formal untuk pernyataan ini.
4.3 Teknik Pengelompokan Heuristik untuk Partisi Induksi Pada bagian sebelumnya, telah ditunjukan bahwa permasalahan pada pengidentifikasian skema partisi batasan ukuran adalah sulit pada dasarnya. Karenanya, untuk menetapkan suatu solusi secara optimal, yang mungkin diperlukan untuk menghitung dan membandingkan jumlah pada skema partisi yang muncul secara eksponen dengan ukuran pada permasalahan. Ini dapat menjadi batasan utama terhadap penggunaan teknik penalaran probabilitas.
Sehingga teknik
efisien secara komputasi dibutuhkan untuk penyelesaian yang baik. Akan uji dengan lima teknik heuristik yang saling berkaitan tersebut dengan maksud untuk memperoleh skema partisi optimal. Tiga teknik pengelompokan agglomerative , SLC , CLC ,dan UPGMA. Untuk dua teknik lainya menggunakan teknik agglomerative disebut sebagai Delta MI, dan Marg MI. Pertama akan dibahas bagaimana teknik SLC digunakan, dan kemudian membahas bagaimana CLC, UPGMA, Delta MI, dan Marg MI dibedakan dengan yang lainya Teknik SLC menggunakan suatu pendekatan metrik sekitar pasangan pada atribut untuk mengidentifikasi artibut prediksi yang mana yang harus dikelom-
Sabar : Partisi Himpunan Atribut Untuk Sistem Penalaran Probabilistik, 2009.
27 pokan secara bersmaan pertama kali.
Ini dapat dilihat sebagai suatu solusi
inisial dimana atribut gabungan mengandung suatu atribut tunggal. Pada iterasi pertama, algoritma menganggap solusi-solusi tersebut ditunjukan dengan mengkombinasikan dua dari atribut gabungan dalam solusi ke penggabungan satu atribut gabungan . Sehingga, jika terdapat sepuluh atribut prediksi pada suatu permasalahan, sehingga terdapat
10 C2
sebagai solusi yang tepat. Karena
obyeknya adalah untuk memaksimalkan penjumlahan pada daerah informasi yang berhubungan yang digabungkan dengan himpunan pada pengelompokan, sehingga didefinisikan pendekatan metrik sekitar pasangan pada atribut dalam penambahan M1 dimana dua atribut diasumsikan sbagai suatu atribut gabungan seperi pada pengasumsian saat diasumsikan sebagai pengelompokan individual. Karenanya, Untuk dua atribut Xi dan Xj , taksiran pendekatan adalah D(Xi ; Xj ) = MI(Xi ; Xj ; C) − MI(Xi ; C) − MI(Xi ; C). Semakin tinggi nilai D(Xi ; Xj ) semakin sempurna hasil dari solusi yang didapat. Anggap bahwa jika dua atribut bebas secara kondisional, maka D(Xi ; Xj ) = 0. Prosedur tersebut mengelompokan pasangan pada atribut-atribut dengan nilai taksiran pendekatan terbesar yang digabungkan. Solusi yang direvisi ini mempuyai sembilan atibut gabungan, satu dariny terdapat dua atribut prediksi. Untuk mendaparkanya dibutuhkan pendekatan antara pengelompokan yang baru dan tiap-tiap atribut lainya yang akan digunaka. Anggap (Xi ; Xj ) sebagai kelompok yang ditunjukan pada iterasi pertama, dan Xk sebagai atribut lainya dalam bembahasan. Dalam metode SLC, pendekatan taksiran antara (Xi ; Xj ) dan Xk , D((Xi ; Xj ); Xk ) diambil sebagai nilai maksimum pada D((Xi ; Xj ) dan D((Xi ; Xk ). Kelompok berikutnya ditunjukan dengan mengidentifikasi pendekatatan taksiran terbesar sekitar kelompok yang tersisa. Proses ini berlanjut sampai seluruh pendekatan taksiran yang ter-
Sabar : Partisi Himpunan Atribut Untuk Sistem Penalaran Probabilistik, 2009.
28 sisa adalah nol, atau lebih jauhnya pengelompokan tersebut mengganggu ukuran batasan. Dalam penambahan ukuran ke ukuran batasan, dibedakan aturan penghentian lainya diadasarkan pada suatu tes statistical untuk kebebasan kondisional. Dalam teori, taksiran informasi yang berhubungan dapat digunakan untuk mengidentifikasi secara pasti saat dua himpunan pada variabel prediksi bebas secara kondisional, keluaran yang diberikan satu dan lainya.Bagaimanapun, saat estimasi probabilitas dari contoh data digunakan untuk mengevaluasi daerah informasi yang berhubungan, ini sering tidak mungkin untuk mengidentifikasi kebebasan kondisional dalam suatu cara eksak. Karena kesalahan pada pemisalan, D((Xi ; Xj ) selalu lebih besar dari nol bahkan saat Xi dan X bebas secara kondisional satu sama lain. Karenanya, tanpa tes penambahan, algoritma dapat mengkombinasikan atribut gabungan tersebut yang berhubungan bebas secara kondisional pada kenyataanya, namun saat ukuran dikombinasikan lebih rendah dibandingkan ukuran batasan yang ditentukan. Untuk mencegah penggabungan atribut suatu cara yang salah, sebuah uji signifikasi ditunjukan pada penambahan dalam informasi yang berhubungan dimana dua atribut dikombinasikan. Uji rasio kemungkinan digunakan untuk menguji untuk signifikasi ini. Berdasarkan pada uji ini, untuk mengkobinasikan dua atribut, penambahan dalam informasi yang berhubungan harus sebelum suatu nilai awal yang hampir spesifik. Permulaan tersebut ditunjukkan dari tabel chi kuadrat, dan bergantung pada derajat tambahan pada kebebasan yang digabungkan dengan mengkombinasikan atribut-atribut yang dianggap untuk membiarkan atribut terpisah. Uji signifikasi dapat disimpulkan sebagai berikut.
Sabar : Partisi Himpunan Atribut Untuk Sistem Penalaran Probabilistik, 2009.
29 Anggap D(X1 ; X1 ) > 0 jika 2n.D(X1 ; X1 ) > x2(α, df ) Dimana n jumlah dari sampel yangdigunakan untuk estimasi daerah informasi yang berhubungan, α sebagai tingkat kebutuhan pada signifikasi, dan df sebagai tambahan dalam derajat kebebasan saat mengkobinasikan X1 dan X1 . Uji estimasi diatas dari pengasusian pada pasangan atribut yang tidak bebas secara signifikasi satu dan yang lainnya. Suatu uji yang sama dibutuhkan untuk mendeteksikan saat dua keompok, satu atau keuanya dimana terdapat atribut ganda, merupakan bebas secara kondisional. Karenanya, jika dua gabungan pada atribut, Y 1 = [X1, X2 ] dan Y 2 = [X3 , X4 ] yang telah ditunjukkan lebih jauh, dan atribut gabungan tersebut bebas secara kondisional, dan tidak mempunyai tujuan untuk mengelompokkan seluruhnya bersamaan. Bagaimanapun, saat menggunakan algoritma SLC, D(Y 1 , Y 2) dapat lebih besar dari nol karena taksiran pendekatan pertama dievaluasi dalam suatu cara yang saling berpasangan sekitar atribut individual. Sebagai subsekuen, jika Y 1 dan Y 2 dipilih sebagai kandidat berikutnya untuk pengelompokkan, di tunjukkan suatu uji signifikan untuk menguji jika atribut gabungan bebas secara kondisional sebelum dikelompokkan. Jika ada, gabungan taksiran pendekatan ditetapkan ke nol sehingga tidak dapat diasumsikan sebagai kandidat untuk mengelompokkan lebih jauh. Metode CLC adalah sebuah jenis sederhana pada SLC, dan berbeda dalam cara taksiran pendekatan yang dihitung kembali untuk kelompok baru yang dibentuk. Dalam CLC, taksiran pendekatan antara suatu kelompok baru yang di bentuk (Xi , Xj ) dan atribut lainnya Xk diambil sebagai minimum pada D(Xi ; Xj ) dan D(Xi Xk ) (jelas bahwa maksimum digunakan pada SLC). Dasar untuk peng-
Sabar : Partisi Himpunan Atribut Untuk Sistem Penalaran Probabilistik, 2009.
30 gunaan minimum adalah bahwa ini menunjukkan suatu estimasi bebas yang lebih banyak pada pendekatan antara (Xi , Xj ) dan Xk , dan mungkin lebih banyak kemungkinan dalam beberapa situasi. Metode UPGMA adalah suatu gabungan antara teknik SLC dan CLC, dimana teksiran pendekatan untuk kelompok baru yang di bentuk yang di hitung kembali dengan mengambil suatu rata-rata pada taksiran untuk anggota bagian pada kelompok. Saat anggota bagian merupakan ukuran berbeda, rata-rata secara eksplisit yang tidak digabungkan dengan kenyataan dengan menormalisasikan kontribusi pada tiap anggota bagian pada dasarnya. Sehingga, jika (Xi , Xj ) dikelompokkan dengan (Xk ), maka taksiran pendekatan antara kelompok baru yang dibentuk ((Xi ; Xj ; Xk ) dan atribut lainnya X adalah 1 2 xD((Xi ; Xj ); Xr ) + xD(Xk ; Xr ) 3 3 Satu dari batasan pada teknik SLC, CLC dan UPGMA adalah bahwa keseluruhan pada taksiran pendekatan yang digunakan, termasuk penghitungan kembali antara atribut gabungan. Ini dikarenakan kebanyakan fungsi jarak biasa tidak didefenisikan untuk tiga atau lebih variabel. Bagaimanapun, taksiran informasi yang berhubungan yang di gunakan didefinisikan untuk jumlah atribut sembarang. Sebagai hasilnya, kita asumsikan algoritma keempat, yang disebut Delta MI, yang menghitung kembali taksiran pendekatan sekitar atribut gabungan dalam daerah pada informasi yang berhubungan yang digabungkan secara langsung. Pada Delta MI, taksiran pendekatan antara suatu kelompok baru yang dibentuk Y i dan kelompok lainnya Y j adalah ∆MI(Y 1 , Yj = (Y 1 ; Yj ; C) − MI(Y i ; C) − MI(Y j ; C)
Sabar : Partisi Himpunan Atribut Untuk Sistem Penalaran Probabilistik, 2009.
31 . Akhirnya digunakan algoritma kelima,yang disebut Marg MI, yang menggunakan, suatu taksiran pendekatan, penambahan kecil dalam MI per unit tambahan dalam derajat kebebasan yang digabungkan dengan pengelompokkan dua (gabungan) atribut. Sehingga jika ∆df (Y 1 , Yj ) = df (Y 1 ; Yj ; C) − df (Y 1 ; C) − df (Y j ; C), maka taksiran pendekatan yang digunakan adalah ∆MI(Y 1 , Yj )/∆df (Y 1 , Yj ) Penggunaan Marg MI didasarkan pada fakta bahwa saat atribut yang dikelompokkan mempunyai suatu jumlah besar pada realisasi, terdapat suatu informasi yang berhubungan terbesar yang saling berhubungan digabungkan dengan mengkombinasikannya. Sebagai contoh, jika dua atribut biner digunakan, dan nilai keluaran juga adalah biner, maka penambahan pada derajat kebebasan pada hasil model probabilitas seperti sebuah hasil pada pengelompokkan pada dua atribut adalah 6-2-2 = 2 (jumlah pada parameter penambahan probabilitas yang dibutuhkan untuk menspesifikasi distribusi yang baru). Dengan kata lain, jika dua atribut dikelompokkan mempunyai tiga nilai kemungkinan masing-masing, penambahan pada derajat kebebasan akan menjadi 16-4-4 = 8. Penambahan jumlah pada parameter probabilitas ini menuju ke hasil tertinggi. Bagaimanapun, hanya jika, dalam kenyataannya, atribut tersebut tidak lebih informative dibandingkan dengan salah satu biner, kesalahan estimasi dapat menuju ke nilai MI tertinggi yang di estimasi. Sebagai hasilnya, ini dapat menjadi kerancuan pada algoritma Delta MI ke pengelompokkan pertama bersama atribut-atribut tersebut dengan jumlah besar pada realisasi.
Sabar : Partisi Himpunan Atribut Untuk Sistem Penalaran Probabilistik, 2009.
32 Kita implementasikan kelima teknik untuk menginduksi partisi dari contoh data. Uji signifikan dicocokkan dengan seluruhnya. Dalam tiap prosedur, pengelompokkan ditunjukkan sampai pengkombinasian pasangan atribut gabungan (dengan batasan ukuran) yang tidak menuju ke penambahan signifikan dalam informasi yang berhubungan. Suatu prosedur untuk algoritma Marg MI ditunjukkan dlam Apendiks B (keempat lainnya hampir sama).
4.4 Percobaan Numerical Berikut ini diberikan contoh: Gambaran pada teknik induksi telah ditunjukkan pada data yang dihasilkan menggunakan teknik simulasi Monte Carlo. Dengan tujuan penelitian, data dihasilkan dalam dua area. Pada area pertama, menghasilkan secara acak suatu model probabilitas dasar untuk variabel keluaran dan atribut prediksinya. Keterkaitan ini mengidentifiksi faktor mana yang menghasilkan atribut gabungan yang sama, dan kemudian menghasilkan distrusi gabungan sekitar variabel keluaran dan atribut gabungan. Anggap suatu kondisi dengan sepuluh atribut prediksi berbeda. Maka, suatu himpunan yang tepat pada atribut gabungan dapat dihasilkan sebagai berikut Y 1 = {X1 , X2 , X3 }; Y 2 = {X4 } Y 3 = {X5 , X6 }; dan Y 4 = {X7 , X8 , X9 , X10 } Suatu atribut gabungan yang dihasilkan, ketergantungan probabilitas dasar antara setiap atribut gabungan dan variabel keluaran yang tersimulasi. Ini diperlukan untuk menspesifikasi sebuah distribusi probabilitas gabungan sekitar tiaptiap atribut gabungan Y i dan keluaran A, dimana suatu distribusi gabungan un-
Sabar : Partisi Himpunan Atribut Untuk Sistem Penalaran Probabilistik, 2009.
33 tuk sebuah atribut gabungan dan keluaran A, dimana suatu distribusi gabungan untuk sebuah atribut gabungan Y i telah di spesifikasi dengan menetapkan massa probabilitas digabungkan dengan setiap realisasi yang tepat sekitar Y 1 dan A. sehingga, asumsikan seluruh atribut adalah biner, dibutuhkan 16 massa probabilitas untuk menspesifikasi distribusi gabungan sekitar Y i dan A, 4 massa probabilitas untuk distribusi gabungan sekitar Y 2 dan A, dan seterusnya. Untuk setiap atribut gabungan, didapatkan jumlah syarat pada bilangan acak antara 0 dan 1, dan kemudian dinormalisasikan untuk memperoleh distribusi probabilitas yang diperlukan. Pada area kedua, digunakan model probabilitas untuk menghasilkan kasus actual yang digunakan untuk menginduksi partisi. Setiap kasus yang telah dihasilkan seperti diatas. Sebuah realisasi untuk variabel keluaran, A, telah di gambarkan secara acak berdasarkan pada probabilitas yang digabungkan dengan keluaran. Untuk setiap atribut komponen, sebuah himpunan pada realisasi untuk komponennya pada keluaran, dan distribusi gabungan digabungkan dengan variabel gabungan dan keluaran. Contoh berikut mengilustrasikan sifat dasar pada atribut gabungan terinduksi dari kasus yang dihasilkan. Pada contoh ini, anggap terdapat 20 atribut prediksi untuk variabel keluaran. Seluruh atribut diasumsikan biner, dan setiap atribut atribut gabungan dalam skema partisi yang tepat yang diberikan terdiri pada paling banyak tiga atribut prediksi. Skema partisi yang tepat (dihasilkan secara acak) diberikan dalam 10 atribut gabungan berikut. Y 1 = {X1 , X2 , X3 }
Y 6 = {X10, X11 , X12 }
Y 2 = {X4 }
Y 7 = {X13 , X14 }
Sabar : Partisi Himpunan Atribut Untuk Sistem Penalaran Probabilistik, 2009.
34 Y 3 = {X5 , X6 , X7 }
Y 8 = {X15, X16 , X17 }
Y 4 = {X8 }
Y 9 = {X17 }
Y 5 = {X9 }
Y 10 = {X18, X19 , X20 }
Suatu distribusi probabilitas yang telah dihasilkan untuk atribut gabungan dan variabel keluaran. Didasarkan pada distribusi, seribu kasus pada contoh data telah tersimulasi. Prosedur Delta MI yang digunakan untuk menginduksi atribut gabungan dengan α = 0, 05 (suatu tingkat signifikan pada 5%), dan suatu batasan ukuran 5 untuk atribut gabungan yang terinduksi. Atribut gabungan diperoleh kembali dengan teknik induksi sebagai berikut. Z 1 = {X1 , X2 , X3 , x17}
Z 5 = {X9 }
Z 2 = {X4 }
Z 6 = {X10 , X10 , x12}
Z 3 = {X5 , X6 , X7 , x20}
Z 7 = {X13 , X14 }
Z 4 = {X8 , X15 , X16}
Z 8 = {X18 , X17}
Keempat dari atribut gabungan dalam solusi terinduksi, Z 2 , Z 5 , Z 6 dan Z 7 , adalah sama ke atribut gabungan dalam distribusi yang tepat. Pada atribut gabungan terinduksi yang tersisa, beberapa diantaranya adalah himpunan super pada atribut gabungan dalam distribusi gabungan, sebagai contoh, atribut gabungan Z 1 merupakan sebuah himpunan super pada atribut gabungan Z 1 . Dalam contoh, Z 1 merupakan sebuah himpunan super pada atribut gabungan Z 1 . Tujuan pada penggunaan atribut gabungan dalam proses penalaran adalah untuk mencegah pengasumsian pada kebebasan kondisional saat tidak bergantung pada sekitar variabel prediksi. Akibatnya, ini berlaku bahwa atribut gabungan Z 1 mendapatkan relasi ketergantungan penting sekitar atribut yang membentuk atribut gabungan y ang tepat. Sehingga, penggunaan pada atribut gabungan Z 1 tidak akan menentukan tambahan pengasumsian apapun pada ketergantungan
Sabar : Partisi Himpunan Atribut Untuk Sistem Penalaran Probabilistik, 2009.
35 kondisional dibandingkan dengan dalam distribusi yang tepat. Untuk alasan ini, saat menguji kemampuan pada teknik induksi untuk menginduksi distribusi probabilitas yang tepat, digunakan dua taksiran. Yang pertama adalah jumlah pada atribut gabungan yang tepat. Yang kedua adalah jumlah pada atribut gabungan dalam distribusi yang tepat yang terdapat dalam distribusi terinduksi (sehingga baik sebagai atribut gabungan yang sama atau sebagai subhimpunan pada atribut gabungan dalam distribusi terinduksi). Dalam contoh diatas, empat dari sepuluh atribut gabungan dalam struktur terinduksi adalah sama dengan atribut gabungan dalam struktur terinduksi, dimana sembilan dari sepuluh atribut gabungan terdapat dalam struktur terinduksi. Atribut gabungan yang tidak terdapat adalah Y 10 karena merupakan atribut gabungan itu sendiri yang didistribusikan sekitar dua atribut gabungan terpisah Z 3 dan Z 8 dalam solusi terinduksi. Pada contoh diatas, empat dari atribut gabungan yang tepat merupakan subhimpunan yang tepat pada dua atribut gabungan terinduksi (Y 1 dan Y 9 yang merupakan subhimpunan pada Z 1 dan Y 4 dan Y 8 yang merupakan subhimpunan pada Z 4 ), dimana tidak ada dari atribut gabungan yang tepat. Pengujian permulaan pada himpunan data yang lain dengan 1000 atau lebih kasus ditunjukkan dengan fenomena yang sama. Dengan kata lain, saat beberapa kasus (sebagai contoh 100) digunakan untuk menginduksi partisi, kebalikannya sering kali bernilai benar. Ini diindikasikan bahwa untuk ukuran contoh yang besar, saat suatu tingkat signifikan 5% digunakan untuk menguji perbaikan pada informasi yang berhubungan metrik, prosedurnya sering digunakan untuk mendeteksinya, jika tidak seluruhnya, pada ketergantungannya yang terdapat dalam distribusi yang mendasari. Bagaimanapun, ini kurang akurat dalam mengeliminasi ketergantungan tersebut
Sabar : Partisi Himpunan Atribut Untuk Sistem Penalaran Probabilistik, 2009.
36 yang ditunjukkan lebih lanjut karena pengandaian estimasi salah. Dengan ukuran contoh yang lebih kecil, tingkat signifikan 5% dihasilkan ketergantungan yang lebih kuat sekitar atribut prediksi saat kebanyakan dari ketergantungan hilang. Sebuah faktor yang mempengaruhi algoritma induksi untuk meneliti partisi yang tepat secara akurat merupakan tingkat signifikan yang digunakan untuk mengeliminasi atribut gabungan yang tepat. Karenanya, dikonduksikan penelitian dimana pengujian untuk signifikan dihasilkan pada tingkat 1%.
Sabar : Partisi Himpunan Atribut Untuk Sistem Penalaran Probabilistik, 2009.
BAB 5 KESIMPULAN
Pada penulisan tesis ini , diformulasikan permasalahan pada penentuan skema partisi yang tepat untuk atribut prediksi yang digunakan untuk membuat keputusan dengan menggunakan suatu model penalaran probabilitas. Permasalahan pada penentuan ukuran nilai batasan skema partisi telah ditunjukan sebagai NP-utuh. Ditunjukan kelima teknik heuristik untuk menginduksi partisi dari kasus historikal. Kelima teknik dapat digunakan untuk mendapatkan ketergantungan dasar secara akurat sekitar atribut pada saat nilai yang layak data historikal untuk dianalisis. Hasil penelitian menunjukan petunjuk yang berguna mengenai gambaran pada suatu teknik induksi. Dalam hal ini parisi sangat penting digunakan. Partisi tersebut menunjukan estimasi probabilitas yang tepat.
37 Sabar : Partisi Himpunan Atribut Untuk Sistem Penalaran Probabilistik, 2009.
DAFTAR PUSTAKA
Adams, Barclay, J, (2000). Probabilistic reasoning and certainty factors. In Buchanan and Shortliate [16], chapter 12, pages 263-271 Boole.G. (1964). An Investigation of The Laws and The Though on which are Founded The Mathematical Theories of Logic and and Probabilities. Watts &co. Baral et al (2006). Probabilistic reasoning with answer sets Markopits.H. (2008). Different developmental patterns of simple deductive and probabilistic inferential reasoning. Ng dan Lloyd (2007) . Probabilistic Reasoning in a Classical Logic Jonathan, L & R.F, Craig. (2004). Partition-Edit-Count: Nave Extensional Reasoning in Judgment of Conditional Probability. Columbia University. Richard T. Cox. (1976). Probability, Frequency and reasonable expectation. American Journal of Physics, 14(1):113. Wanson & Johnson-Laird. (1972). All of Statistics. USA William G. Cole. Medical cognitive graphics. In Marilyn Mantei and Peter Oberton, editors, Human Facrtors in Computing Sistems: CHI86 Conference Proceedings, pages 91 (95, Boston, MA, April 1986. ACM, New York. William G. Cole and Janet E. Davidson. Graphic representation can lead to fast And accurate Bayesian reasoning. Technical report, Carnegie Mellon University, Department of Psychology, Pittsburgh, PA, September 1989.
38 Sabar : Partisi Himpunan Atribut Untuk Sistem Penalaran Probabilistik, 2009.