Temporal Data Mining

https://komarudintasdik.wordpress.com

Terjemahan dari buku Temporal Data Mining

Bab 3

Temporal Data Classification and Clustering

Classification dan clustering adalah dua tools pembelajaran mesin utama dan merupakan dua bidang sangat penting dari data mining, karena keduanya memiliki banyak aplikasi praktis seperti diagnosis medis, deteksi penipuan, dan memprediksi trend finansial. Classification adalah aktivitas penentuan sampel baru terhadap sejumlah kelas yang diketahui sebelumnya, sementara clustering adalah aktivitas pengelompokkan sampel-sampel ke dalam cluster sampel-sampel yang serupa. Ini merupakan alasan bahwa classification dikenal supervised learning dan clustering dikenal sebagai unsupervised learning.

Bab ini diorganisir sebagai berikut: Dalam Bagian 3.1 dan 3.2, kami mengkaji teknik-teknik classification dan clustering umum, yakni, teknik-teknik yang dikembangkan untuk data non-temporal. Alasannya ada dua: pertama, untuk mengenalkan kepada pembaca dengan konsep classification dan clustering. Kedua, setelah satu atau lebih skema representasi temporal yang telah kita kaji dalam bab sebelumnya diaplikasikan ke data seri waktu, representasi output dapat secara langsung digunakan sebagai input untuk teknik classification dan clustering nontemporal. Sebagai contoh, seri waktu yang dapat direpresentasikan menggunakan feature vector yang terdiri dari Fourier transform coefcients dari seri waktu dan mean, skewness, dan kurtosis-nya. Feature vector inilah yang dapat menjadi input untuk algoritma classification dan clustering nontemporal. Contoh penggunaan feature vector untuk mengkarakterisasi time series dan kemudian menjadikan feature vector sebagai input untuk algoritma clustering dideskripsikan dalam [Wan05].

Pada bagian 3.3, kami mempresentasikan teknik analisis outlier dan ukuran validitas cluster. Pada bagian 3.4, teknik classification dan clustering yang dikembangkan secara khusus untuk time series data dideskripsikan. Pada bagian 3.5, bibliografi tambahan pada teknik classification dan clustering umum sebaik time series teknik classification dan clustering disajikan.

3.1    Teknik Classification

Dalam classification, kami berasumsi bahwa kami memiliki banyak domain knowledge tentang masalah yang sedang kita coba atasi. Domain knowledge ini bisa berasal dari domain experts atau data sampel dari domain itu, yang merupakan rangkaian data training. Pada bagian ini, kami akan menguji teknik classification yang dikembangkan untuk data nontemporal. Bagaimanapun, teknik itu dapat diperluas dengan mudah, sebagaimana akan didemontrasikan dengan contoh untuk data temporal.

3.1.1        Distance-Based Classifiers

Sebagamana namanya, ide utama dalam rumpun classifier ini adalah untuk mengklasifikasikan sampel baru terhadap kelas terdekat. Tiap contoh direpresentasikan oleh fitur N. Terdapat implementasi yang berbeda dari jenis classifier ini, berdasarkan pada (1) bagaimana tiap kelas direpresentasikan dan (2) bagaimana jarak itu dikomputasi dari tiap kelas. Terdapat dua variasi pada bagaimana merepresentasikan tiap kelas. Pertama, dalam pendekatan K-Nearest Neighbours, semua sampel kelas digunakan untuk merepresentasikan kelas. Kedua, dalam pendekatan berbasis exemplars, tiap kelas direpresentasikan dengan sampel representative, biasanya mengarah pada sebagai exemplar dari kelas ini. Mengenai jarak sampel yang tidak diketahui terhadap kelas-kelas yang berbeda, semua ukuran jarak yang ditentukan dalam bab sebelumnya dapat digunakan. Sangat banyak yang telah menggunakan metrik untuk mengkomputasi jarak sampel kelas yang tidak diketahui terhadap kelas-kelas yang ada adalah jarak Euclidian. Bagaimanapun, untuk beberapa teknik classification ukuran jarak lainnya lebih sesuai. Contohnya adalah 1-Nearest Neighbor classifier (dideskripsikan di bawah) untuk yang metrik zDynamic Time Warping adalah yang terbaik (Eru07). Sebagai contoh, kita berasumsi kita memiliki sampel baru x dari kelas yang tidak diketahui dengan fitur N, di mana masing-masing fitur ith dinotasikan sebagai Xi.

Kemudian jarak Euclidean dari sampel kelas, yang memiliki fiture ith dinotasikan sebagai yi, didefinisikan sebagai:

(3.1)

3.1.1.1  K-Nearest Neighbors

Dalam jenis classifier ini, domain knowledge tiap kelas direpresentasikan oleh semua sampelnya. Sampel baruu X, yang kelasnya kita tidak ketahui, diklasifikasikan ke kelas yang memiliki K nearest neighbors untuknya. K bisa berupa 1, 2, 3, dan seterusnya. Karena semua sampel training disimpan untuk tiap kelas, ini merupakan metode ekspensip secara komputasional. Mari kita lihat contoh temporal. Kita memiliki tanggal 22-6-2009, dan dua kelas hari, “Sunny Day” dan “Cloudy Day.” Kita akan mengetahui penggunaan classifier 1-nearest neighbor, apakah hari itu memiliki kelas “Sunny Day” atau “Cloudy Day”. Data training terdiri dari hari-hari yang dipilih secara random di tiap 12 bulan dan ditampilkan pada tabel 3.1.

Mari sekarang kita hitung jarak Euclidean dari sampel kita ke masing-masing salah satu dari dua kelas: Pertama, jarak Euclidean ke sampel sunny day adalah

TABLE 3.1 Data Training untuk Kelas Sunny-Cloudy

Bulan               Hari                 Kelas

1                      10                    Cloudy

2                      3                      Cloudy

3                      15                    Cloudy

4                      23                    Sunny

5                      18                    Cloudy

6                      12                    Sunny

7                      4                      Cloudy

8                      6                      Sunny

9                      12                    Sunny

10                    8                      Cloudy

11                    26                    Cloudy

12                    8                      Sunny

Kemudian jarak menuju kelas cloudy day dapat dikomputasi sebagai

Kami lihat bahwa sampel yang sangat tertutup terhadap incoming sample memiliki sunny class. Jadi 6/22 diklasifikasikan ke sunny class. Ini bisa juga dilihat pada Figure 3.1, yang menggambarkan sampled days tiap bulan berkaitan dengan hari-hari dari permulaan tahun.

S di atas bagian dari sampel yang menunjukkan bahwa sampel ini memiliki sunny class. Simbol X pada grafik (nilai 173) sesuai dengan 22 Juni, hari yang kita ingin klasifikasikan. Jika kita menggambarkan garis lurus dari X, kita akan melihat bahwa sampel yang sangat tertutup adalah hari dari bulan Juni yang memiliki sunny class.

Variasi teknik K-NN tidak memperlakukan sampel yang berbeda dalam sebuah kelas secara sama, tapi menetapkan weight untuk masing-masing sampel, berdasarkan baik peran pentingnya atau jaraknya dari sampel yang belum diketahui. Sebagai contoh, weight yang dapat digunakan adalah 1/(Eudis+1) di mana Eudis adalah jarak dari sampel tersebut ke sampel kelas yang belum diketahui.

FIGURE 3.1 Diagram yang Menggambarkan Kelas-Kelas Sunny dan Cloudy Day

Beberapa pertimbangan penting tentang algoritma neighborhood terdekat diuraikan dalam [Wu08]:

  • Kinerja algoritma dipengaruhi oleh pilihan K. Jika K kecil, maka algoritma tersebut dipengaruhi dengan poin noise. Jika K sangat besar, maka nearest neighbors dapat memiliki banyak kelas yang berbeda.
  • Pilihan ukuran jarak dapat juga mempengaruhi kinerja algoritma. Banyak ukuran jarak dipengaruhi dengan dimensionalitas data. Contohnya, kekuatan klasifikasi jarak Euclidean direduksi sebagai jumlah pertambahan atribut.
  • Error algoritma K-NN secara asimtotik mendekati Bayes error.
  • K-NN sangat aplikatif untuk masalah klasifikasi dengan kelas multimodal. Sebagai contoh, [Wu08] menyebutkan bahwa untuk untuk profil ekspresi gen K-NN melibatkan Support Vecotr Machines (yang akan diuraikan di bawah).

Pekerjaan tambahan yang telah dilakukan untuk memperbaiki kinerja K-NN. Contoh pekerjaan oleh Hart [Har68], yang menghapus banyak objek training tanpa mengurangi akurasi klasifikasi K-NN. Proses ini dikenal sebagai condensing [Wu08]. Perbaikan K-NN juga disajikan dalam [Tou02], menggunakan proximity graphs.

3.1.1.2   Exemplar-Based Nearest Neighbor

Dalam jenis classifier ini, tiap kelas direpresentasikan dengan sampel representative yang dikenal sebagai exemplar. Secara khusus, fitur exemplar itu dikomputasi sebagai nilai mean dari fitur sampel training di tiap kelas. Sehingga, kelas Y muncul dengan tiga fitur, exemplarnya akan digambarkan oleh:

 

di mana bar horizontal menunjukkan nilai mean dari sebuah fitur.

Sekarang mari kita kaji contoh sebelumnya dengan kelas sunny-cloudy day dan menggunakan pendekatan berbasis exemplar. Exemplar kelas sunny adalah August 1 dan exemplar kelas cloudy adalah May 24. Tanggal sampel kita adalah June 22 semakin dekat dengan exemplar kelas cloudy, sehingga, ia sekarang diklasifikasikan dalamkelas cloudy.

Figure 3.2 menampilkan dua kelas, sampel di dalamnya, dan sampel kelas yang belum diketahui. Dalam kasus ini, 1-NN dan algoritma exemplar akan mengklasifikasikan secara tepat sampel itu untuk kelas 2. Bagaimanapun, Figure 3.3 menampilkan kasus di mana dua algoritma akan menghasilkan hasil yang berbeda. Secara khusus, algoritma exemplar akan menetapkan sampel yang belum diketahui terhadap kelas 2, tapi algoritma 1-NN akan mengklasifikasikan sampel yang belum diketahui ke kelas 1.

3.1.1        Bayes Classifier

Bayes classifier adalah sebuah classifier statistic, karena classification berbasis komputasi probabilitas, dan domain knowledge juga diekspresikan dalam cara probabilistic. Dalam buku ini, kita akan mendiskusikan sangat banyak penggunaan jenis Bayes classifier, yang dikenal sebagai naïve Bayes classifier, di mana kita berasumsi bahwa fitur-fitur itu berbeda-beda secara independen dari yang lainnya; yakni, fitur itu “independen secara kondisional.” Bayesian classification dibahas pada [Dud73]. Pelanggaran dari independensi fitur dalam naïve Bayes classifier dan efeknya pada akurasi classifier dibahas pada [Dom96]. Pada bagian ini, kita akan membahas naïve Bayes classifier secara detil, karena kesederhanaan dan efektivitasnya yang membuatnya sangat popular di bidang seperti text classification dan spam filtering seperti ini [Wu08].

Sebelum kita mengkaji bagaimana classification yang menggunakan jenis classifier ini dilakukan, mari kita kaji beberapa konsep dasar:

  • Posteriori probability: Mari kita asumsikan bahwa kita memiliki domain dengan dua kelas, C dan D. Probabilitas bahwa sebuah sampel S dari kelas yang belum diketahui akan melibatkan C yang dikenal sebagai posteriori probability dan diekspresikan sebagai P(C/S). sebagaimana ia dapat dengan mudah diduga oleh pembacanya,

 

FIGURE 3.2 Sebuah Kasus di mana K-NN dan Exemplar-Based Clustering Menghasilkan Hasil yang Sama

Posteriori probability adalah kunci untuk menetapkan kelas mana yang menentukan sampel baru. Sehingga bagaimana probabilitas ini dikomputasi? Itu dilakukan menggunakan Baye’s theorem, yang dibahas di bawah.

  • Baye’s Theorem:

 

 

FIGURE 3.3 Sebuah Kasus di mana K-NN dan Exemplar-Based Clustering menghasilkan hasil yang berbeda

 

Di mana P(S|C) merupakan probabilitas bahwa kelas C akan memiliki sampel S, P(C) merupakan probabilitas bahwa sampel akan melibatkan kelas C, dan P(S) merupakan probabilitas sebelum S.

Sekarang mari kita berasumsi bahwa kita diberi N kelas C1, C2,…, CN. Sampel baru S dengan fitur K dan nilai S1,…Sk, ditetapkan terhadap kelas ith jika

 

Dengan kata lain, sampel baru S ditempatkan ke kelas dengan maximum posteriori probability. Posteriori probability dikomputasi menggunakan Baye’s theorem seperti tampak di atas. Karena denominator, P(S), sama untuk semua posteriori probability, ia dapat difaktorkan, sehingga sampel baru S itu ditempatkan ke kelas ith untuk:

P(S|Ci) P(Ci)>P(S|Cj)P(Cj) for j=1…, N dan i≠j         (3.17)

Probabilitas tiap kelas, P(Ci), dikomputasi dari sampel training seperti

 

di mana Ntotal merupakan total number dari sampel training dan N(Ci) merupakan jumlah sampel training yang melibatkan kelas Ci. Probabilitas P(S|Ci)dikomputasi sebagai

P(S|Ci) =

di mana P(Sm|Ci) merupakan probabilitas bahwa untuk sampel dari kelas C, fitur mth nya memiliki nilai Sm. Asumsi di sini bahwa fitur-fitur itu independen, yang merupakan alasan dari naïve Baye’s classifier.

The computation hal 74

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s