[TKI] Text Classification

Pada kesempatan kali ini saya akan mencoba menjelaskan bagaimana suatu dokument dapat di klasifikasikan? contohnya jika ada portal berita yang memiliki beberapa kategori, dan kita ingin mengkategorikan berita baru yang ada. jikalau kita menggunakan cara konvensiional, makas kita akan mengklasifikasikanya manual, tapi bagaimana kalau misalkan kita memiliki 1000 dokumen baru? apakah itu baik kita kategorikan secara manual? saya rasa tidak. maka dari itu sya akan mencoba untuk sedikit menjelaskan bagaimana untuk mengklaskan dokumen secara otomatis.

langsung saja, untuk dapat melakukan pengkelasaanterhadap dokumen berikut beberapa langkah yang harus dilakukan.

kita akan membahasa masing masing dari tahapan yang ada diatas.

#Langkah pertama:

pada langkah ini kita di fukuskan untuk mengumpulkan dokumen, yang dimaksudkan untuk membuat suatu kelas untuk fungsi klasifikasi,

# Langakah kedua 

pada langkah ini kita akan melakukan seleksi fitur yang berguna untuk kira-kira pada kelas tertentu punya identitas apa sih yang berbeda. 

nah pada langakah ini terdapat 3 metode (yang saya tau)

1. metode petama yaitu metode Luhn dimana dalam metode ini saya tidak akan bercerita banyak. tapi initinya kita melakukan langkah-langkah yang biasa digunakan dalan pemprosesan text.

    - Buang stopwoard => IDF = 0 

    - Buang daerah kurva sebelah kanan => IDF = log N

2. metode kedua yaitu namanya Mutual Information (MI) -> peluang similarity

sebelumnya kita harus mengetahui tabel berikut:

|	Ct = 1	| Ct = 0
Cc = 1 |	N11	| N10
Cc = 0 |	N01	| N00

jika kita ketahui c = class dan t = term

jadi misalkan kita ingin tau (c = spam, t = jual), maksudnya yaitu seberapa banyak kata jual kita kelaskan di kelas spam (N11)

Formula dari MI

langsung saja kita ke contoh soal

misalkan ada data: 

seberapa besar kata-kata (brazil, council, producers, roasted) masuk kedalam class coffee??

term	N00	N10	N01	N11
brazil	98012	102	1835	51
council	96322	133	3525	20
producers	98524	119	1118	34
roasted	99824	143	23	10

berapa besaranya kata Brazil masuk ke kelas coffee -> I(Brazil, Coffee)

berapa besaranya kata Council masuk ke kelas coffee -> I(Council, Coffee)

berapa besaranya kata Producers masuk ke kelas coffee -> I(Producers, Coffee)

berapa besaranya kata Roasted masuk ke kelas coffee -> I(Roasted, Coffee)

dari hasil tersebut kita mengetahui bahwa producers > brazil > roasted > council,
maka jikka hanya ingin mengambil 2 terbesar saja, maka kita akan memilih producers danbrazil

3. metode ketiga yaitu chi-square (x^2)
langsung saja, dengan data yang sama
rumus chi-square yaiut


atau dengan menggunakan rumus yang lebih ringkas











dari hasil tersebut roasted>brazil>producers>council

nah, jika kita perhatikan, terdapat perbedaan hasil antara dua metode yang kita gunakan yaitu MI dan chi-square

#Langkah ketiga
lanjut pada langkah ketiga kita akan melakukan dan membuat kelas dengan fungsi klasifikasi menggunakan dokumen latih.

untuk dapat membuaat fungsi klasifikasi, harus kita ketahui ada beberapa cara
cara pertama berdasarkan vektor { KNN, SVM}
cara kedua berdasarkan peluang {Decision tree, Naive Bayes}

pada artikel ini saya hanya akan membahas tentang cara pengerjaan menggunakan naive bayes.
ada beberapa istilah sebelumnya:
P(c) = berapa peluang kelas c
P(c) = berapa peluang kelas bukan c
P(c|d) = berapa peluang dokumen d berada dalam kelas c
P(~c|d) = berapa peluang dokumen d berada dalam kelas bukan d


langsung saja ke contoh soal:

	Doc ID	Word in Document	in C = Chinese
training set	1	Chinese Beijing Chinese	yes
	2	Chinese Chinese sanghai	yes
	3	Chinese Macau	yes
	4	Tokyo Japan Chinese	no
test set	1	Chinese Chinese Chinese Tokyo Japan	?

dari hasil tersebut nilai peluang P(c|ds) menjadi nol karena ada data yang tidak ada dalam kelas chinese, maka dari itu kita harus memikirkan cara bagaimana perluang tersebut tidah harus Nol. tenang saja kita tidak harus memikirkannya begitu serius soalnya sudah ada metode dimana nal tersebut dapat tertangani. yaitu menggunakan smoothing. ada dua cara untuk smoothing, yaitu:

1. Laplace Smoothing
menggunakan metode Laplace Smoothing = add one smoothing
metode ini hanya tinggal menambahkan 1 pada masing-masing nilai pembilang, dan menampahkan angkan sebanyak kata unit yang ada dalam kelas tersebut

dari hasil tersebut kita dapat menentukan bahwa dokumen tersebut masuk kedalam kelas chinese

2. Bernaulli
sebenarnya hampir sama dengan Laplace Smoothing, hanya saja bernauli menambahkan beberapa perhirungan kedalamnya.
pembilang -> +1
penyebut   -> +(jumlah kelas)

[PPCD] Image Compresion

seperti yang kita tahu image / citra merupakan kumpulan dari ribuan bahkan jutaan pixel yang tersusun rapi sehingga membentuk suatu gambar yang bagus. kebayang ga sih bagaimana citra itu disimpan jika 1 pixel itu memakan memori sebanyak 3 byte (RGB)? sekarang misalkan saya memiliki kamera dengan resolusi 18Mp, jika kita kalkulasikan:

18 Mp = 18.000.000 px x 3 byte 

           = 54 = 10^6 byte

           = 54 MB

dengan begitu artinya, sekali saya melakukan pengambilan gambar, saya membutuh kan memori sebanyak 54MB. nah loh kebayang ga sih gimana membuka file sebesar itu? yang ada juga komputer atau device kita (kalau kuat) akam mengalami loading dulu kan ya? syukur2 ga error. jika kalian punya camera SLR (dengan resolusi yang sama) pernah ga mengambil gambar dan satu gambarnya memiliki ukuran file yang sangat besar, misal 54 MB? saya rasa tidak. lalu bagaimanakah gambar-gambar tersebut memiliki ukuran gambar yang relatif kecil? pada artikel ini saya akan membahas bagaimanakan gambar / citra dilakukan kompresi.

langsung saja, 

ide dasar dilakukannya compresi yaitu menghilangkan redudansi. nah dalam redudansi sendiri ada beberapa macam:

1. coding

2. psicovisual

3. interpixel

---------------------------------------

sedangkan kompresi sendiri memiliki 2 macam, yaitu:

1. Lossless  -> tidak ada pengurangan informasi

                   -> ukuran setelah kompresi > lossy

                   -> BMP, PNG, GIF

                   -> digunakan ketika kita lebih mementingkan keakuratan gambar

                   -> melakukan percetakan gambar

2. Lossy     -> terdapat pengurangan informasi

                   -> ukuran setelah komppresi < Lossles

                   -> untuk menghitung kebaikan algoritama kompresi -> harus ada ukuran banyaknya data yg hilang 

                   -> JPEG

                   -> digunakan ketiaka gambar di peruntukan dalan dah yang berhubungan dengan pengiriman data, misal aktivitas treaming, uplaod ke media social.

karena lossless data / informasi tidak ada yang hilang berarti sedikit masalh dengan teknik ini. berbeda dengan lossy, hal ini harus dilakukan pendalam sendiri terhadap teknik lossy. lanjut saja, bagaimana kita melakukan pengukuran terhadap lossy? berapa banyak data yagn hilang? dsb.

pengukuran terhadap hasil kompresi lossy, terdapat w macam:

1. Subjektif -> secara subjektif, kita dapat mengukur dengan cara membandingkan 2 gambar (gambar asli, hasil kompresi) dan kita tanyakan kepada beberapa orang untuk melakukan penilaian, gambar manakah yang lebih baik? seberapa baik gambar hasil kompresi? dll

2. objektif -> sedangkan secara objektif, kita dapat melakukan pengukuran dengan beberapa metode:

    a. RMSE (Root Mean Square Error) -> jika hasil mendekati 0, maka jarak antara 2 gambar kecil.

    b. SNR (Signal to Noise Ratio) -> semakin besar hasil SNR, maka kompresi semakin baik  

|  |  |  |

|  |  |  |

|  |  |  |

contoh perhitungan:

citra asli:

| 1 | 3 | 1 |

| 2 | 1 | 4 |

| 5 | 1 | 2 |

citra hasil kompresi:

| 1 | 2 | 1 |

| 0 | 3 | 4 |

| 1 | 2 | 2 |

~oke kita skip dulu perhitungannya~

------------------------------------------------

lanjut, setelah kita mengetahui banyaknya data yang hilang dari suatu gambar hasil kompresi, lalu bagaimanakan kita mengukur nilai kebaikannya? 

Ukuran kebaikan kompresi:

CR (copretion ratio) = n1/n2

-> n1 = citra ukuran asli

-> n2 = citra ukuran setelah kompresi

RD (redudansi ...) = 1 - (1/CR)    ----> menghitung banyaknya redudansi pada citra asli

# n1 = n2 (CR = 1 & RD = 0)

tidak ada redudansi pada citra asli

 

# n1 >>  n2 (CR=~ & RD=1)

gambar asli sangat redundant

# n1 << n2 (CR=0 & RD = -~)

kasus yang tidak diinginkan 

--------------------------------------------------

kembali lagi ke perhitungan pengukuran secara subjektif. perhitungan secara subjektif dapat dilakukan dengan menggunakan kuesioner dengan melakukan penilaian secara langsung oleh pengamat (baik, sanggat baik, tidak baik, dsb) dengan masing masing pilihan memiliki kriteria masing-masing.

contohnya yaitu psycovisual

----------------------------------------------------

encoding

dalam teknik ini, bagaimana cara kita memetakan setiap katakter ke bit yang sesuai dan sesuai dengan kesepakatan bersama.

contohnya dalam ASCII bit 65 merupakan representaasi dari karakter A, 97 -> a dan lain sebagainya. lalu bagaimanakah dengan gambar?

#skema encoding I

-----------------------

no   bit    frekuensi

-----------------------

1   0000       50        -> 4 bit x 50 = 200

2   0001       40        -> 4 bit x 40 = 160

3   0010        5         -> 4 bit x   5 =   20

4   0011        5         -> 4 bit x   5 =   20    +

-----------------------                      ----------- 

                                                         400 bit

#skema encoding II

 -----------------------

no   bit    frekuensi

-----------------------

1         1       50        -> 1 bit x 50 =   50

2       01       40        -> 2 bit x 40 =   80

3     000        5         -> 3 bit x   5 =   15

4   0011        5         -> 4 bit x   5 =   20    +

-----------------------                      ----------- 

                                                         165 bit

artinya dengan menggunakan skema encoding II kita dapat menghemat penyimpanan lebih baik. namun  masalahnya bagai mana kita dapat memetakan masing2 bit dengan representasi yang sesuai???

jawabannya akan dijelaskan menggunakan metode "Huffman"

misalkan kita memiliki beberapa macam warna (A, B, C, D, E, F, G, H) dengan frekuensi masing masing

 -----------------------

warna    frekuensi(%)

-----------------------

     A             0.50 

     B             0.05

     C             0.05   

     D             0.03   

     E             0.02

     F             0.01

     G             0.13

     H             0.12

-----------------------

                     1.0

lalu buat dendogram, hubungkan warna2 yang memiliki frekuensi dari kecil -> besar

A(0.05)---------------------------------------------------|---1.00

H(0.12)--|--0.22-------------------------------|--0.50---|

F(0.10)---|                                                  |

G(0.13)--------------------------------|--0.28-|

B(0.05)-----------------------|--0.15--|

C(0.05)-------------|---0.1---|

D(0.03) ---|-0.05--|

E(0.02)  ---|

lalu buat kesepakatan bahwa kalau kebawah 1 dan keatas 0, telusuri dari nila1 1

A(0.05)--------------------------(0)----------------------|--

H(0.12)-(0)-|-----------------------(0)---------|--(1)----|

F(0.10)--(1)-|                                                  |

G(0.13)-----------------(0)-------------|--(1)--|

B(0.05)-------------(0)-------|--(1)----|

C(0.05)------(0)----|---(1)---|

D(0.03) -(0)-|-(1)--|

E(0.02)  -(1)-|

 ----------------------------------------------------

warna    frekuensi(%)  code-lama code-baru

-----------------------------------------------------

     A             0.50              000          0

     B             0.05              001         1110

     C             0.05              010         11110 

     D             0.03              011         111110

     E             0.02              100          111111

     F             0.01              101          101

     G             0.13             110          110

     H             0.12             111          100

------------------------------------------------------

jika kita hitung:

1 pixel (code-lama) membutuhkan memori 3 satuan, sedangkan

1 pixel (code-baru) membutuhkan memori 2.24 satuan (hiting sendiri ya)

[PPCD] Segmentasi

nah pada kesempatan ini kita kan coba bahas tentang segmentasi. nah terus apa sih gunanya dilakukannya segmentasi? sebagai contoh jika kita akan menghitung jumlah mobil dijalannan secara realtime (car counting) kita harus mengetahui bahwa ada objek mobil disana, kita harus dapat memisahkkan mobil dari jalannya agar bisa dilakukan counting. nah dari masalah itu memisahkan objek dari latarnya merupakan masalah segmentasi, tp sekarang bagaimana melakukan segmentasi terhadap gambar???

ayo kita bahas.
terdapat dua tahap yang harus dilakukan untuk melakukan segmentasi:
1. Discountinuity -> deteksi tepi (edge detection)
2. Similarity -> mencari intensitas yang seragam


1. Similarity
pertama saya coba bahas bagaimana cara melakukan similarity / mencari pixel-pixel saling similar. nah cara mencari pixel yang similar, kita dapat melakukan point detection, caranya? lakukan dengan meng-konvolusikan filter tertentu dengan image yang akan kita olah

sebagai contoh kita memiliki kernel filter
| -1 -1  -1 |
| -1  8   -1|
| -1 -1  -1 |

sekarang kita akan mencari pixel yang seragam/similar dengan pixel-pixel di sekelilingnya. bgaimana caranya? sekarang kita memiliki (contoh) image yang similar antara
| 10 10 10 |
| 10 10 10 |   <------ image (pixel) yang similar
| 10 10 10 |

misal kita akan mencari point/pixel yang berada di tengah (apakah dia similar dengan nilai disekelilingnya?)
kita lakukan konvolusi antara image kernel filternya. maka:

| -1 -1  -1 |      | 10 10 10 |          | 10 10 10 |
| -1  8   -1|   x | 10 10 10 |    =    | 10   0 10 |
| -1 -1  -1 |      | 10 10 10 |          | 10 10 10 |

artinya jika pixel-pixel tersebut memiliki nilai yang sama(similar) maka nilai hhasil konvolusinya akan seragam semua.


berbeda jika nilai pixelnya tidak seragam, (misal) ->
| 10 10 10 |
| 10   0 10 |   <------ image (pixel) yang tidak similar
| 10 10 10 |

kita lakukan konvolusi antara image kernel filternya. maka:

| -1 -1  -1 |      | 10 10 10 |          | 10 10   10 |
| -1  8   -1|   x | 10 10 10 |    =    | 10  -80 10 |
| -1 -1  -1 |      | 10 10 10 |          | 10 10   10 |

artinya, jika pixelnya berbeda-beda maka nilai akhirnya juga akan berbeda-beda (tidak seragam)

apakah udah selesai? beloman. tahap terakhir kita lakukan tresholding hasil dari convolusi image dengan kernelnya itu.

f(x) = | 1 , f(x,y) >= treshold
          | 0 , f(x,y) <   treshold

2. Discountinuity (edge detection)
sebenarnya tahap ini merupakan tahap awal proses segmentasi, sebelum dilakukannya similarity. tetappi jadi kita bahas jadi bahasan kedua, ya gpp kan ya? kayanya sih bahasin ini akan sedikit banyak. langsung saja kita ke materinya.

sebelum kita melakukan edge detection ada baiknya kita laklukna smooting (langkah ini tergantung dari gambar asli yang digunakan). smoothing ini dilakukan karena pada proses deteksi tepi hanya memerlukan memilih objeknya saja, tidak perlu detail dari objeknya.

salah satu edge detection itu adalah line detection. misalkan terdapat 4 kernel, satu kernel mendeteksi line berdasarkan garis horizontal, kernel yang lain digunakan untuk mendeteksi secara vertikal, garis 45 derajat dan garis -45 derajat. bagaimana sih kernelnya?

| -1 -1 -1 |
|  2   2  2 |   <------ iHorizontal
| -1 -1 -1 |

| -1  2  -1 |
| -1  2  -1 |   <------ Verikal
| -1  2  -1 |

|   2 -1 -1 |
| -1   2 -1 |   <------ 45 derajat
| -1 -1   2 |

| -1 -1   2 |
| -1   2 -1 |   <------ -45 derajat
|   2 -1 -1 |

dibawah ini meruakan perbedaan menggunakan masing-masing kernel untuk line detection (45, -45, vertikal, horizontal)

 ------------------------------------

selanjutnya akan kita bahas teknik lain untuk melakukan deteksi tepi, yaitu menggunakan "gradient". langsung saja saya coba jelaskan bagaimanakah step-stepnya:

1. lakukan smoothing pada gambar -> kalikan citra dengan kernel untuk smoothing

2. cari gradient x                              -> kalikan citra dengan kernel x

3. cari gradient y                              -> kalikan citra dengan kernel y

4. cari magnitude(x,y)                      -> tambahkan hasil dari gradient x dan y

5. cari dir(x,y)                                  

6. tentukan treshold(T), jika mag(x,y)>T maka possible edge point

nah sekarang, apa aja sih kernel yang bisa digunakan dalam edge detection menggunakan gradient. beberapa kernel yang terkenal untuk mendeteksi edge ada 3, yaitu Robert, Prewitt, Sobel:

Robert:

|  1  0  |
|  0  -1 |   <------ Mx

|  0  1  |
| -1  0 |   <------ My

Prewitt
| -1 0 1 |
| -1 0 1 |   <------ Mx
| -1 0 1 |

| -1 -1 -1 |
|  0  0   0 |   <------ My
|  1  1   1 |

Sobel
| -1 0 1 |
| -2 0 2 |   <------ Mx
| -1 0 1 |

| -1 -2 -1 |
|  0  0   0 |   <------ My
|  1  2   1 |

sebagai contoh, saya akan menjabarkan perhitungan menggunakan kernel prewitt:
misalkan ada citra sebagai berikut->
| 38 66 65 |
| 14 35 64 |
| 12 15 42 |

fx = (12 + 15 + 42) - (38 + 66 + 65)
    = 69 - 169
    = -100
fy = (65 + 64 + 42) - (38 + 14 + 12)
    = 171 -64
    = 107
|df| = |-100| + |107| = 207

jika T = 190 maka f(1.1) merupakan edge

Sinkronasi pada openmp [parallel computing]

sinkronasi merupakan hal yang perlu diperhatikan. bagaimana tidak? jika kita telah membagi-bagi pekerjaan kebeberapa thread /  processor, hal terakhir yang harus kita lakukan yaitu menyatukan data-data hasil proses yang telah dikerjakan masing-masing processor.

ada tiga jenis sinkronasi pada openmp:
critical
Direktif untuk membuat wilayah kritis dalam wilayah paralel, hanya satu thread dalam satu waktu yang bisa masuk ke wilayah kritis ini. Wilayah kritis perlu dibuat untuk melindungi shared variable dari race condition yang mengakibatkan inkonsistensi data.

atomic
Direktif yang fungsinya sama seperti critical, tetapi hanya berlaku untuk satu statement aritmatika saja.

barrier
Direktif untuk membuat batas, thread akan menunggu sampai semua thread sampai pada batas ini.

bagaimana menggunakan nya? berikut contoh program yang akan saya sampaikan. kode saa sadur dari sini

############################
atomic
############################

1. tulis program misalkan dengan nama <task2.c>

#include <stdio.h>
#include <omp.h>
#define N 1200
#define T 4

int main() {
    int sum = 0;
    #pragma omp parallel num_threads(T)
    {
        int i;
        for (i = 0; i < N/T; i++)
            sum++;                  // critical section
    }
    printf("%d\n", sum);

    return 0;
}

2. lakukan kompilasi

$ gcc task2.c -o task2 -fopenmp

$ ./task2

coba lakukan running program berkali-kali, maka akan didapatkan hasil yang tidak konsisten. bagaimana cara agar hasil yang didapatkan sama seperti yang diharapkan (1200) dan hasilnya konsisten?

caranya yaitu lindungi daerah "critical section" dengan sintax sinkronasi dari openmp. kode dimodifikasi sebagai berikut:

#include <stdio.h>
#include <omp.h>
#define N 1200
#define T 4

int main() {
    int sum = 0;
    #pragma omp parallel num_threads(T)
    {
        int i;
        for (i = 0; i < N/T; i++)
            #pragma omp atomic
            sum++;                  // critical section
    }
    printf("%d\n", sum);

    return 0;
}

maka hasil yang didapatkan akan konsisten,, yaitu 1200.


############################
Critical
############################
yang kedua, kita akan melakukan proses sinkronasi menggunakan critical. apakah perbedaan dengan yang atomic? dan pada kasus apa critical digunakan.

berikut kode yang digunakan untuk melakukan pencarian nilai maksimal

<task3.c>

#include <stdio.h>
#include <omp.h>

#define N 16 
#define T 4

int main() {
    int max = 0;
    int A[N] = {1,2,3,4,57,6,7,8,9,10,11,12,13,14,15,16};
    #pragma omp parallel num_threads(T)
    {
        int i;
 int max_loc = 0;
        int id = omp_get_thread_num();
 int start = id*N/T;
 int stop = (id+1)*N/T;
        for (i = start; i < stop; i++)
  if (A[i] > max_loc) 
   max_loc = A[i];

 #pragma omp critical
  if (max_loc > max)
   max = max_loc;
    }
    printf("%d\n", max);

    return 0;

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ sekian ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~


referensi: http://cs.ipb.ac.id/~auriza/parallel/pp.html