Data Mining - Klasifikasi

Klasifikasi

Konsep Dasar

  • Klasifikasi vs. Prediksi
    • Klasifikasi: Memprediksi label kelas kategori.
      • Mengklasifikasikan data berdasarkan himpunan data pelatihan dan atribut klasifikasi nilai (label kelas).
      • Menggunakan model yang dihasilkan untuk mengklasifikasikan data baru.
    • Prediksi: Memodelkan fungsi bernilai kontinyu.
      • Contoh: Memprediksi nilai yang tidak diketahui atau hilang.

Apa itu Klasifikasi?

  • Diberikan sebuah kumpulan record (training set).
  • Setiap record dikarakterisasi oleh tuple (x, y), di mana x adalah himpunan atribut dan y adalah label kelas.
    • x: attribute, prediktor, variabel bebas, input.
    • y: class, response, variabel tak bebas, output.
  • Tugas: Mempelajari sebuah model yang memetakan setiap set atribut x ke salah satu label kelas yang telah ditetapkan y.

Model Klasifikasi

  • Model Induction: Proses pembelajaran model dari training data.
  • Model Deduction: Proses menggunakan model yang telah dipelajari untuk mengklasifikasi data baru (test set).
  • Contoh:
    • Training Set: Tabel dengan atribut dan class yang sudah diketahui.
    • Learning Algorithm: Algoritma yang digunakan untuk mempelajari model (misalnya, decision tree).
    • Model: Representasi dari pola yang ditemukan dalam data training.
    • Test Set: Data baru dengan atribut yang diketahui, tetapi class belum diketahui.

Contoh Kasus Klasifikasi

  • Mengategorikan pesan email:
    • Himpunan attribute (x): Fitur diekstrak dari header pesan email dan konten.
    • Class label (y): spam atau non-spam.
  • Identifikasi sel tumor:
    • Himpunan attribute (x): Fitur diekstraksi dari pemindaian MRI.
    • Class label (y): ganas atau jinak.
  • Cataloging galaxies:
    • Himpunan attribute (x): Fitur diekstraksi dari citra teleskop.
    • Class label (y): Galaksi berbentuk elips, spiral, atau tidak beraturan.

Teknik Klasifikasi

  • Base Classifiers
    • Metode berbasis Decision Tree
    • Rule-based Methods
    • Nearest-neighbor
    • Jaringan Syaraf Tiruan
    • Deep Learning
    • Naïve Bayes dan Bayesian Belief Networks
    • Support Vector Machines
  • Ensemble Classifiers
    • Boosting, Bagging, Random Forests

Evaluasi dari Sistem Klasifikasi

  • Training Set: Contoh dengan nilai kelas untuk pembelajaran.
  • Test Set: Contoh dengan nilai kelas untuk mengevaluasi.
  • Accuracy: Persentase contoh dalam himpunan data tes yang diklasifikasikan dengan benar.
  • Confusion Matrix:
    • Actual vs Predicted.
    • True Positives.
    • False Positives.
    • False Negatives.

Algoritma k-Nearest Neighbors (kNN)

  • Metode klasifikasi terhadap sekumpulan data berdasarkan pembelajaran data yang sudah terklasifikasikan sebelumnya.
  • Metode supervised learning, dimana hasil query instance yang baru diklasifikasikan berdasarkan mayoritas kedekatan jarak dari kategori yang ada dalam KNN.
  • Data direpresentasikan dalam ruang vektor.

Ruang Feature

  • Data direpresentasikan sebagai vektor dalam ruang berdimensi-d, di mana setiap dimensi mewakili sebuah fitur.
  • Contoh: \langle x^{(1)}, f(x^{(1)}) \rangle, \langle x^{(2)}, f(x^{(2)}) \rangle, …, \langle x^{(n)}, f(x^{(n)}) \rangle
    • x = \begin{bmatrix} x1 \ x2 \ … \ x_d \end{bmatrix} \in \Re^d
  • Jarak antara dua titik x dan y dihitung menggunakan Euclidean distance:
    • x - y = \sqrt{\sum{i=1}^{d} (xi - y_i)^2}

Algoritma KKN

  • Pada pembelajaran nearest-neighbor fungsi target dapat berupa fungsi bernilai diskrit atau real
  • Pembelajaran sebuah fungsi bernilai diskrit
    • f : \Re^d \rightarrow V, V adalah himpunan berhingga \lbrace v1, …, vn \rbrace
  • Untuk bernilai diskrit, k-NN mengembalikan nilai paling umum di antara sampel pelatihan k terdekat ke x_q.

Algoritma Pembelajaran dan Klasifikasi

  • Algoritma Pembelajaran
    • Untuk setiap contoh training
  • Algoritma Klasifikasi
    • Diberikan sebuah query instance xq yang akan di klasifikasikan
    • Misal x1,..,xk k instances yang paling dekat ke xq
    • \hat{f}(xq) \leftarrow \underset{v \in V}{\operatorname{argmax}} \sum{i=1}^{k} \delta(v, f(x_i))
      • dimana \delta(a,b) = 1 jika a=b, \delta(a,b) = 0 untuk yang lainnya (fungsi Kronecker)

Cara kerja kNN?

  • Diberikan query instance, akan ditemukan sejumlah k obyek atau (titik training) yang paling dekat dengan query instance.
  • Klasifikasi menggunakan voting terbanyak diantara klasifikasi dari k obyek
  • Algoritma k-nearest neighbor (KNN) menggunakan klasifikasi ketetanggaan sebagai nilai prediksi dari query instance yang baru.

Contoh Ilustrasi k-NN

  • 1-Nearest Neighbor: Titik query diklasifikasikan berdasarkan kelas dari tetangga terdekatnya.
  • 3-Nearest Neighbors: Titik query diklasifikasikan berdasarkan mayoritas kelas dari 3 tetangga terdekat.
  • 7-Nearest Neighbors: Titik query diklasifikasikan berdasarkan mayoritas kelas dari 7 tetangga terdekat.

Menentukan Nilai k yang Baik

  • Ditentukan secara eksperimental
  • Mulai dengan k = 1 dan gunakan set tes untuk memvalidasi tingkat kesalahan pengklasifikasi
  • Ulangi dengan k = k + 2
  • Pilih nilai k yang tingkat kesalahannya minimum
  • Catatan: k harus berupa angka ganjil untuk menghindari ikatan

Algoritma kNN

  1. Menentukan parameter k (jumlah tetangga paling dekat).
  2. Menghitung kuadrat jarak euclidean objek terhadap data training yang diberikan.
  3. Mengurutkan hasil no 2 secara ascending
  4. Mengumpulkan kategori Y (Klasifikasi nearest neighbor berdasarkan nilai k)
  5. Dengan menggunakan kategori nearest neighbor yang paling mayoritas maka dapat dipredisikan kategori objek .

Kelebihan kNN

  • Simpel
  • Efektif jika data besar
  • Intuitif
  • Peforma cukup baik
  • Tahan terhadap data latih yang noisy

Kekurangan kNN

  • Waktu komputasi tinggi jika data latih besar. Disebabkan oleh semua data diukur jaraknya untuk setiap data uji.
  • Sangat sensitive dengan ciri yang redundan atau tidak relevan. Ditanggulangi dengan seleksi ciri atau pembobotan ciri.
  • Tidak diketahui perhitungan jarak apa yang paling sesuai untuk dataset tertentu.

Contoh 1

  • Terdapat beberapa data yang berasal dari survey questioner tentang klasifikasi kualitas kertas tissue apakah baik atau jelek, dengan objek training menggunakan dua attribute yaitu daya tahan terhadap asam dan kekuatan.
  • Attribute X1 = 7 dan X2 = 4, klasifikasikan apakah kertas tisu tersebut termasuk yang baik atau jelek.
    • x1 =daya tahan asam (detik)
    • x2 = kekuatan (kg/m2)
    • Y=Klasifiikasi
      • 8 4 baik
      • 4 5 jelek
      • 4 6 jelek
      • 7 7 baik
      • 5 6 jelek
      • 6 5 baik
  • Jarak kuadrat ke Query (7,4)
    • 8 4 (8-7)2+(4-4)2=1
    • 4 5 (4-7)2+(5-4)2=10
    • 4 6 (4-7)2+(6-4)2=13
    • 7 7 (4-7)2+(7-4)2=9
    • 5 6 (5-7)2+(6-4)2=8
    • 6 5 (6-7)2+(5-4)2=2
  • k=3

Latihan Soal

  • Tentukan class dari test data dengan nilai atribut (50,3,40)
    • X1 =Takaran Saji (gr)
    • X2= Jumlah Saji Perkemasan
    • X3 = Energi Total
  • Y=Klasifikasi
    • 40 5 60 Jelek
    • 50 8 40 Bagus
    • 50 7 30 Jelek
    • 70 4 60 Bagus
    • 80 4 80 Bagus
    • 60 6 60 Bagus

Contoh Implementasi dengan Bahasa Pemrograman Python

  • Customer Churn Prediction with KNN Classifier
  • Setiap baris mewakili seorang pelanggan, setiap kolom berisi atribut pelanggan yang dijelaskan pada Metadata kolom.
  • Kumpulan data mencakup informasi tentang:
    • Pelanggan yang keluar dalam bulan terakhir – kolom tersebut bernama Churn
    • Layanan yang telah didaftarkan oleh setiap pelanggan – telepon, banyak saluran, internet, keamanan online, cadangan online, perlindungan perangkat, dukungan teknologi, dan streaming TV dan film
    • Informasi akun pelanggan – berapa lama mereka menjadi pelanggan, kontrak, metode pembayaran, penagihan tanpa kertas, biaya bulanan, dan total biaya
    • Info demografis tentang pelanggan – jenis kelamin, rentang usia, dan apakah mereka memiliki pasangan dan tanggungan

Mengimport Package /Modul

import numpy as np
import pandas as pd
import matplotlib.pyplot as plt
import seaborn as sns
import warnings
warnings.filterwarnings('ignore')
from sklearn._config import set_config
set_config(print_changed_only=False)
from sklearn.preprocessing import StandardScaler
from sklearn.model_selection import train_test_split
from sklearn.neighbors import KNeighborsClassifier
from sklearn.model_selection import StratifiedKFold
from sklearn.model_selection import GridSearchCV
from sklearn.metrics import accuracy_score

Membaca Data Set

df= pd.read_csv('WA_Fn-UseC_-Telco-Customer-Churn.csv')
# View all columns
pd.set_option("display.max_columns", None)
df.head()

Menampilkan info dari data

df.info()

Melihat distribusi data

df.describe().T

Memeriksa missing value

df.isnull().sum()

EDA

plt.figure(figsize= (10, 7), dpi= 80)
ax= sns.countplot(x='Churn' , data= df)
for p in ax.patches:
 ax.annotate('{:.1f}'.format(p.get_height()), (p.get_x()+0.3, p.get_height()+50))

Korelasi Churn dengan Fitur

corr_df = pd.get_dummies(df[['gender', 'SeniorCitizen',
 'Partner', 'Dependents','PhoneService', 'MultipleLines',
 'OnlineSecurity', 'OnlineBackup', 'DeviceProtection',
 'TechSupport', 'InternetService',
 'StreamingTV', 'StreamingMovies', 'Contract',
 'PaperlessBilling', 'PaymentMethod', 'Churn']]).corr()
corr_df['Churn_Yes'].sort_values().iloc[1:-1]

Korelasi Churn dengan Fitur (lanjutan)

  • Menampilkan visualisasi korelasi
    python plt.figure(figsize=(10, 4), dpi= 150) sns.barplot(x= corr_df['Churn_Yes'].sort_values().iloc[1:- 1].index, y= corr_df['Churn_Yes'].sort_values().iloc[1:- 1].values, palette= 'Blues_d') plt.title("Feature Correlation w.r.t. Churn_Yes") plt.xticks(rotation= 90);

Hubungan Tenur dan Churn

Churn_yes= df.groupby(['Churn', 'tenure']).count().T['Yes']
Churn_no= df.groupby(['Churn', 'tenure']).count().T['No']
Churn_rate= (Churn_yes/ (Churn_yes+Churn_no))*100
Churn_rate= Churn_rate.drop(0, axis=1)
Churn_rate= Churn_rate.T
Churn_rate

Cohort-Analysis (Tenure)

def cohort(tenure):
 if tenure< 13:
 return '0-12 months'
 elif tenure< 25:
 return '12-24 months'
 elif tenure < 37:
 return '24-36 months'
 elif tenure < 49:
 return '36-48 months'
 else:
 return 'Over 48 months'
  • Aplikasi fungsi cohort
    ```python
    df['Tenure Cohort']= df['tenure'].apply(cohort)
    df[['tenure', 'Tenure Cohort']].head (10)
*   Visualisasi
    ```python
plt.figure(figsize = (10,4), dpi =150)
sns.countplot(data = df, x = 'Tenure Cohort', hue = 'Churn', palette= 'viridis')

Model-Prediction

  • Memastikan tipe data
    ```python
    df['TotalCharges'].dtype
## Model-Prediction (Lanjutan)

python
df.dropna(inplace= True)
df.isnull().sum()

## Model-Prediction (Lanjutan)

python
X= df.drop(['customerID', 'Tenure Cohort', 'Churn'], axis= 1)
y=df['Churn']
X.head()

## Model-Prediction (Lanjutan)

python
Xnum= X.selectdtypes(include= ['int64', 'float64'])
Xcat= X.selectdtypes(exclude= ['int64', 'float64'])
Xcatnew= pd.getdummies(Xcat, dropfirst= True) Xcat_new.head()

## Model-Prediction (Lanjutan)

python
X= pd.concat([Xnum, Xcat_new], axis=1)
X.head()

## Model-Prediction (Lanjutan)

python
from sklearn.modelselection import traintestsplit Xtrain, Xtest, ytrain, ytest= traintestsplit(X, y, testsize= 0.25, randomstate= 2022) Xtrain.shape, X_test.shape

## Model-Prediction (Lanjutan)
*   Standardisasi fitur input untuk meningkatkan kinerja pembelajaran.
*   Mean dan standard deviation dari setiap fitur dihitung.
*   Mean dikurangi dari setiap sampel fitur dan hasilnya dibagi dengan standard deviation.
*   Tujuannya adalah untuk mengubah fitur agar memiliki mean 0 dan standard deviation 1.
*   StandardScaler dari scikit-learn digunakan.
*   StandardScaler dipasang ke fitur di train_X, lalu scaler ini mengubah fitur yang sama di train_X dan test_X. Proses ini diulangi untuk semua fitur.

## Model-Prediction (Lanjutan)

python
for column in range(trainX.shape[1]): scaler = StandardScaler() scaler.fit(trainX[:,column].reshape(-1,1))
trainX[:,column] = scaler.transform(trainX[:,column]. reshape(-1,1)).ravel()
testX[:,column] = scaler.transform(testX[:,column]. reshape(-1,1)).ravel()

## Model-Prediction (Lanjutan)

python
knncls = KNeighborsClassifier() parameters = { "nneighbors": range(3, 10, 1),
"metric": ["minkowski"],
"p": [1.0, 2.0],
"algorithm": ["brute"]
}
skfcv = StratifiedKFold(nsplits=5, randomstate=None, shuffle=False) gscv = GridSearchCV( estimator=knncls,
paramgrid=parameters, scoring="accuracy", njobs=2,
cv=skfcv, verbose=True ) gscv.fit(trainX, trainY.ravel()) print("Best parameters {}".format(gscv.bestparams_))

## Akurasi

python
knncls = KNeighborsClassifier(**gscv.bestparams) knncls.fit(trainX, trainY.ravel())
starttime = time.time() ypred = knncls.predict(testX)
stoptime = time.time() elapsedbrute = stoptime - starttime
print("Test time with brute search: {:.4f} seconds".format(elapsedbrute)) bruteacc = accuracyscore(testY, ypred) print("Accuracy with brute search: {:.4f}".format(bruteacc))
```

Decision Tree Training Dataset

  • Contoh dataset untuk pelatihan decision tree.
  • Atribut: age, income, student, credit_rating.
  • Class: buys_computer (yes/no).

Keluaran: Decision Tree untuk “buys_computer”

  • Visualisasi decision tree yang dihasilkan dari dataset pelatihan.
  • Menunjukkan bagaimana atribut digunakan untuk membuat keputusan.
  • Algoritma ID3 dan C4.5 digunakan untuk menghasilkan decision tree.

Algoritma untuk Induksi Decision Tree

  • Algoritma Dasar
    • Tree dibangun dengan cara membagi secara rekursif top-down
    • Pada awalnya, semua contoh pelatihan adalah akar
    • Atribut bersifat kategoris (jika nilai kontinyu, mereka didiskualifikasi sebelumnya)
    • Contoh dipartisi secara rekursif berdasarkan atribut yang dipilih
    • Atribut uji dipilih berdasarkan ukuran heuristik atau statistik(e.g., information gain)
  • Kondisi untuk memberhentikan partisi
    • Semua sampel untuk node yang diberikan milik kelas yang sama
    • Tidak ada atribut yang tersisa untuk dipartisi lebih lanjut - pemungutan suara mayoritas digunakan untuk mengklasifikasikan daun
    • Tidak ada sampel yang tersisa

Ukuran Seleksi Atribut: Information Gain (ID3/C4.5)

  • Pilih atribut dengan informasi Gain tertinggi
  • S berisi si tuples dari kelas Ci untuk i = {1, …, m}
  • Ukuran informasi yang diperlukan untuk mengklasifikasikan sembarang tuple
  • Entropi dari attribute A dengan nilai {a1,a2,…,av}
  • Informasi gain dari cabang pada atribut A
    • I(s1, s2, …, sm) = - \sum{i=1}^{m} \frac{si}{s} \log2 \frac{s_i}{s}
    • E(A) = \sum{j=1}^{v} \frac{mj}{s} I(s{1j}, s{2j}, …, s_{mj})
    • Gain(A) = I(s1, s2, …, s_m) - E(A)

Contoh Perhitungan

  • Contoh dataset yang digunakan untuk perhitungan information gain.
  • Sama seperti dataset pada slide sebelumnya.

Seleksi Attribute oleh Perhitungan Information Gain / Decision Tree Algorithm: ID3

  • Class P: buys_computer = “yes”
  • Class N: buys_computer = “no”
  • I(p, n) = I(9, 5) =0.940
  • I(9,5)=-(9/14LOG(9/14,2)+5/14LOG(5/14,2))

Decision Tree Algorithm: ID3 (Lanjutan)

  • Menghitung gain untuk atribut age.
  • Memilih atribut dengan gain tertinggi sebagai node.

Decision Tree Generation Algorithm: ID3

  • Misalkan S adalah himpunan yang berisi dari s data samples. Andaikan attribut label kelas mempunyai m nilai yang berbeda yang mendefinisikan m kelas yang berbeda., Ci,i=1,2,…m. Misalkan si adalah jumlah sampel dari S dalam kelas Ci . Informasi yang diperlukan untuk diharapkan untuk mengklasifikasikan sebuah sample yang diharapkan adalah adalah:
  • Pi adalah peluang sebrang sampel berada pada kelas ke Ci dan diestimasi dengan Si/S. Catatan sebuah fungsi log berbasis 2 karena informasi dikodekan dalam bits.
    • I(s1, s2, …, sm) = - \sum{i=1}^{m} pi \log2 pi, dengan pi = \frac{si}{s} dan \sum pi = 1

Algoritma C4.5

  • Merupakan pengembangan dari algoritma ID3, dimana kekurangan yang dimiliki algoritma ID3 dapat ditutupi oleh algoritma C4.5.

Beberapa hal yang membedakan algoritma C4.5 dengan ID3

  • Tahan (robust) terhadap data noise, sehingga mencegah adanya
  • Mampu menangani variabel dengan tipe diskrit maupun kontinu.
  • Mampu menangani variable yang memiliki missing value
  • Dapat memangkas cabang dari pohon keputusan.

Secara umum algoritma C4.5 untuk membangun pohon keputusan adalah sebagai berikut:

  • Pilih variabel sebagai akar
  • Buat cabang untuk masing-masing nilai
  • Bagi kasus dalam cabang
  • Ulangi proses untuk masing-masing cabang sampai semua kasus pada cabang memiliki kelas yang sama.