DETEKSI OUTLIER BERBASIS KLASTER PADA DATA SET DENGAN ATRIBUT CAMPURAN NUMERIK DAN KATEGORIKAL
TESIS DWI MARYONO 5107201006
LATAR BELAKANG MASALAH Data Set Numerik : distance-based, density-based, clustering-based, subspace-based, dan lain-lain
Deteksi Outlier Data Set Kategorikal :CBLOF, FPOF dan LSA Bagaimana jika data set terdiri dari aribut campuran numerik dan kategorikal? Alternatif way : Transformasi dari satu tipe data menjadi tipe data lain. Contoh : He et al (2005b) melakukan diskritisasi tipe data numerik menjadi kategorikal untuk kemudian diterapkan algoritma FPOF.
LATAR BELAKANG MASALAH He et al (2005a): Klasterisasi data set campuran dengan membagi data set menjadi numerik dan kategorikal Assent et al (2007), Agrawal dan Yu (2005): deteksi outlier pada sub data set
IDE : • Partisi data set menjadi numerik dan kategorikal, • deteksi outlier pada sub data set • pemanfaatan klasterisasi untuk untuk deteksi outlier
Hong et al (2008) : Menerapkan cluster ensemble untuk deteksi outlier
Definisi Outlier seperti apa yang memungkinkan?
LATAR BELAKANG MASALAH Outlier berbasis klaster: sebarang obyek yang tidak berada pada klaster yang ”cukup besar” Outlier bisa berupa obyek data tunggal atau dapat juga keseluruhan obyek dari klaster yang kecil. Penghitungan derajat outlier: Jika ia berada pada ”klaster besar”, maka dilihat seberapa jauh ia menyimpang dari obyek lain dalam klaster tersebut. Jika obyek tersebut terdapat dalam ”klaster kecil” maka dihitung kedudukannya terhadap ”klaster besar”
LATAR BELAKANG MASALAH Ide : penggabungan partisi data set, klastering sub dataset dan deteksi outlier berbasis klaster Partisi data set Numerik dan kategorikal
Klasterisasi dan deteksi outlier secara bersilang pada kedua sub data set
Penggabungan derajat outlier dengan multi-atribut decision making (MADM)
PERUMUSAN MASALAH Rumusan masalah Bagaimana menerapkan teknik gabungan klasterisasi dan deteksi outlier lokal berbasis klaster untuk menemukan outlier pada data set campuran numerik dan kategorikal Bagaimana performa algoritma yang dihasilkan
TUJUAN DAN MANFAAT Tujuan : menyelesaikan masalah deteksi outlier pada data set campuran numerik dan kategorikal dengan menggunakan teknik gabungan klasterisasi dan deteksi outlier secara bersilang pada sub data set numerik dan kategorikal Manfaat : memberikan penyelesaian masalah deteksi outlier pada data set campuran numerik dan kategorikan sehingga dapat diaplikasikan pada masalah nyata
CLUSTER BASED LOCAL OUTLIER (CBLOF)
Outlier: observasi menyimpang dari sebagian besar observasi lain, hingga muncul dugaan bahwa ia dibangkitkan oleh mekanisme yang salah. Macam-macam deteksi outlier: statistic-based, distance-based, density-based, cluster-based, dsb. Dari sudut pandang klaster, pada C1 dan C3 dapat dianggap sebagai outlier karena tidak terdapat pada klaster yang besar yaitu C2 dan C4 CBLOF diukur berdasar ukuran klaster di mana ia berada dan kemiripannya terhadap klaster terdekat
Metode CBLOF untuk deteksi outlier data kategorikal Konsep klaster besar dan klaster Kecil: Misalkan C= {C1, C2, …, Ck} dengan |C1|≥ |C2|≥ …≥|Ck|. Untuk parameter α dan β, didefinsikan b sebagai batas antara klaster besar dan kecil jika memenuhi formula (|C1|+|C2|+...+|Cb|)≥|D|*α |Cb|/|Cb+1| ≥ β Klaster besar didefinsikan LC = {Ci, / i ≤ b} Klaster kecil didefinisikan SC = {Ci, / i >b}. Penghitungan derajat outlier dari obyek t: | Ci | * max(sim (C j , t ) CBLOF (t ) = | Ci | *(sim(Ci , t ))
untuk t ∈ C i , C i ∈ SC dan C j ∈ LC untuk t ∈ C i , C i ∈ LC
Deteksi outlier berbasis klaster pada data numerik Pendekatan: Menganggap klaster-klaster kecil yang jauh dari klaster yang lain sebagai outlier menentukan derajat di mana sebuah obyek berada pada sebarang klaster Penentuan derajat outlier Mengukur jarak obyek terhadap centroid klaster terdekat Mengukur jarak relatif obyek terhadap klaster terdekat
Numerical CBLOF Penentuan derajat outlier berdasarkan konsep CBLOF Menggunakan konsep klaster besar dan klaster kecil Derajat outlier dihitung berdasarkan ukuran klaster terdekat dan jaraknya terhadap klaster terdekat 1 | | C j relatif distance(t , C ) untuk t ∈ C i , C i ∈ SC dan C j ∈ LC , j C j = arg min(t , centroid (C j )) NCBLOF (t ) = 1 untuk t ∈ C i , C i ∈ LC | Ci | relatif distance ( , )) t C i
MCDM (Multicriteria Decision Making) Berkaitan dengan pengambilan keputusan di bawah keberadaan sejumah criteria keputusan Dibagi menjadi Multi-objective Decision making (MODM) dan Multi-attribute decision making (MADM). Dalam masalah penggabungan derajat outlier digunakan MADM MADM menggunakan MAVT dengan operator agregat Operator product ∏ (a1w1, a2w2, ..., amwm) = a1w1 a2w2 ... amwm = ∏ ai wi Operator tambah + (a1w1, a2w2, ..., amwm) = a1w1 + a2w2 +...+ amwm = Σai wi Operator S∞. S∞ (w1 a1, w2 a2, ..., wm am) = max { wi ai}
Penentuan Bobot dalam MADM Penentuan bobot :Subyektif, Default (bobot sama), otomatis (Konsep Entropy) Misalkan diberikan matriks keputusan a11 a A = 21 M a n1
a12 L a1m x11 x a 22 L a 2 m Normalisasi X = 21 M M M M a n 2 L a nm x n1
x12 x 22 M x 2m
L x1m L x 2 m M M L x nm
Hitung Nilai entropi ej dan derajat divergensi fj n e j = −k ∑ (xij ln xij ) fj = 1- ej i =1
Hitung bobot tiap kolom/atribut
wj =
fj
m
∑f k =1
k
ALGORITMA MIXCBLOF
Gambar Diagram Alir ALgoritma MixCBLOF
Uji Coba dan Analisis Hasil Data Set Uji Coba: UCI Machine Learning Real dataset
Data set Cleveland (Heart Disease) Dataset Hypothyroid Dataset Hepatitis Dataset Annealing
Karakteristik data : data set terdiri dari beberapa klaster di mana di antaranya terdapat klaster dengan ukuran ralatif kecil Pengukuran kinerja berdasarkan top ratio dan coverage
Skenario Menentukan parameter yang tepat utuk algoritma MixCBLOF, meliputi penentuan α, β, operator agregat dan pembobotan yang tepat untuk masing-masing dataset Membandingkan MixCBLOF dibandingkan dengan algoritma lain, dalam hal ini adalah algoritma CBLOF yang diterapkan pada dataset yang sudah didiskritisasi
HASIL UJI COBA Sub Dataset Cleveland I
Tabel 4.3 Hasil MixCBLOF pada subdata Cleveland I dengan parameter s=2.3, k=4, wi=1, α=80%, dan β=10
Sub Dataset Cleveland II (wi=1 dan entropy)
Hasil Uji Coba Dataset Hypothyroid (entropy weight)
Hasil Uji Coba Dataset Hepatitis (equal weigth)
Hasil Uji Coba Dataset Annealing (equal weigth)
EVALUASI Operator dan Pembobotan terbaik Tabel 4.29 Pencapaian coverage untuk n=jumlah outlier eksak pada keseluruhan dataset berdasarkan operator dan pembobotan
EVALUASI Penetapan α dan β: terpenuhinya konsep klaster besar dan kecil Tabel 4.28 Pengaruh pemenuhan konsep klaster besar dan kecil terhadap kinerja algoritma MixCBLOF
DAFTAR PUSTAKA
Aggarwal, C., Yu, P. (2005) “An effective and efficient algorithm for high-dimensional outlier detection”. VLDB Journal 14(2), hal 211-221 Assent, I., Krieger,R., Muller,E., Seidl, T. (2007) "Subspace outlier mining in large multimedia databases", Dagstuhl Seminar Proceedings 07181 :Parallel Universes and Local Patterns Breunig, M. M.., Kriegel, H. P., Ng, R. T., Sander, J. (2000). “LOF: identifying density-based local outliers”. Proceedings of the 2000 ACM SIGMOD International Conference on Management of Data, hal 93-104. Climaco, J. (1997), ”Multicriteria analysis”, Springer-Verlag, New York. Karpys, G., Han, H, Kumar, V. (1999), “CHAMELEON: A Hierarchical Clustering Algorithm Using Dynamic Modelling”. IEEE Computer, Vol 32, No. 8 68-75 He, Z., Xu, X., Deng, S. (2002), “Squeezer: An Efficient Algorithm for Clustering Categorical Data”. Journal of Computer Science and Technology, 17(5):611-624. He, Z., Deng, X., Xu, X. (2005a), “Clustering Mixed Numeric and Categorical Data: A Cluster Ensemble Approach”, eprint arXiv:cs/0509011 He, Z, X. Xu, J. Huang, S. Deng (2005b). ”FP-Outlier: Frequent Pattern Based Outlier Detection”. Computer Science and Information Systems, 2(1), 103-118. Hong, Y, Kwong, S., Chang, Y., Ren, Q. (2008), “Unsupervised Data Pruning for Clustering of Noisy Data”, Elvesier : Knowledge-Based System 21 hal 612-616 Huang, Z (1998),” Extension to the k-Means Algorithm for Clustering Large dataset with Categorical Values”, Data Mining and Knowledge Discovery, 2, hal. 283-304. Knorr, E. . Ng, R., Tucakov, T.(2000).”Distance-based outliers: algorithms and applications”. VLDB Journal 8(3-4), hal 237-253. Sedl, T., Miller, E., Assent, I., Sfenhausen, U. (2009). "Outlier Detection and Ranking Based on Subspace Clustering". Daghtul Seminar Procedings 08421 Tan, Pan. N, Steinbach, M., Kumar, V. (2006), ”Introduction to Data mining”. Perason, Addison Weisley. Boston.
