4
BAB II Kajian Literatur
BAB II KAJIAN LITERATUR
2.1
Jarak Mahalanobis Mengutip artikel tentang jarak Mahalanobis dari http://en.wikipedia.org pada 28 Maret 2008, jarak Mahalanobis adalah ukuran jarak yang diperkenalkan oleh Prasanta Chandra Mahalanobis pada tahun 1936, seorang ilmuwan India. Jarak Mahalanobis didasarkan pada korelasi antar variabel-variabel, khususnya invers matriks kovariansi. Dengan demikian, jarak ini berbeda dengan jarak Euclides.
Jarak Euclides antara dua vektor x, y ∈ℜn dirumuskan sebagai berikut.
d Euc ( x, y ) = ( x1 − y1 )2 + ( x2 − y2 )2 + .. + ( xn − yn ) 2 Sedangkan kuadrat jarak Mahalanobis antara dua vektor acak x dan y, yang berdistribusi sama dengan matriks kovariansi ∑ , adalah d M ( x , y ) = ( x − y ) ∑ −1 ( x − y ) t
Jika matriks kovariansinya adalah matriks identitas, maka jarak Mahalanobisnya akan sama dengan jarak Euclid, berikut pembuktiannya : d M ( x , y ) = ( x − y ) ∑ −1 ( x − y ) t
= ( x − y ) I −1 ( x − y ) t = ( x − y ) I ( x − y )t
= ( x − y )( x − y )t
Abdullah - 10103076
5
BAB II Kajian Literatur = ( x1 − y1 ) 2 + ( x2 − y2 ) 2 + ... + ( x p − y p ) 2 = d Euc ( x, y )
Dan jika matriks kovariansinya adalah matriks diagonal maka jarak Mahalanobis akan berupa jarak Euclid yang ternormalisasikan. Misalkan, ⎡σ 12 0 ⎢ 2 ⎢ 0 σ2 ∑ = ⎢ 0 0 ⎢ 0 ⎢ 0 ⎢ 0 0 ⎣
0 0 . 0 0
0 0 ⎤ ⎥ 0 0 ⎥ 0 0 ⎥ ⎥ . 0 ⎥ 0 σ p 2 ⎥⎦
Maka, d M ( x , y ) = ( x − y ) ∑ −1 ( x − y ) t
⎡σ 12 0 ⎢ 2 ⎢ 0 σ2 = ( x − y) ⎢ 0 0 ⎢ 0 ⎢ 0 ⎢ 0 0 ⎣
⎡ 1 ⎢σ 2 ⎢ 1 ⎢ ⎢ 0 = ( x − y) ⎢ ⎢ 0 ⎢ ⎢ 0 ⎢ ⎢ 0 ⎢⎣
=
( x1 − y1 ) 2
Abdullah - 10103076
σ 12
+
0 1
σ 22 0 0 0
0 0 . 0 0
⎤ 0 ⎥ ⎥ ⎥ 0 0 0 ⎥ ⎥ ( x − y )t . 0 0 ⎥ ⎥ 0 . 0 ⎥ 1 ⎥ 0 0 ⎥ σ p 2 ⎥⎦ 0 0
( x2 − y2 ) 2
σ 22
−1
0 0 ⎤ ⎥ 0 0 ⎥ 0 0 ⎥ ( x − y )t ⎥ . 0 ⎥ 0 σ p 2 ⎥⎦
+ ... +
( x p − y p )2
σ p2
6
BAB II Kajian Literatur
=
p
∑ i =1
( xi − yi ) 2
σ i2
Jarak mahalanobis juga dapat diaplikasikan untuk masalah Qualitry control (lihat di buku “Introduction to Statistical Quality Control”) dan masalah regression diagnostic (lihat di buku “An Introduction to Computational Statistics”). Begitu luasnya penggunaan jarak Mahalanobis dapat dijumpai dalam literatur tentang statistik multivariat. Dalam skripsi ini jarak Mahalanobis akan digunakan untuk mendeteksi/memisahkan data yang merupakan outlier dari kelompok data yang bukan outlier. Dalam praktek, ∑ ditaksir berdasarkan sampel. Begitu pula dengan mean populasi
µ . Misalkan S dan X matriks kovariansi dan vekor rata-rata dari sampel yang berukuran n dan berditribusi p-variat. Jarak Mahalanobis antara dua anggota sampel x dan y adalah d S ( x , y ) = ( x − y ) t S −1 ( x − y )
Khususnya, jika y = X , maka d M ( x, X ) = ( x − X )t S −1 ( x − X ) . Jarak Mahalanobis ini tidak robust karena X dan S tidak robust. Mengutip dari buku karangan Rosseeuw dan Leroy, berjudul ”Detection outlier and robust regression”, penaksir parameter populasi dikatakan robust jika nilai penaksir tersebut tidak dipengaruhi oleh ada atau tidaknya gangguan/outlier. Jarak Mahalanobis yang robust, misalnya, adalah jarak Mahalanobis yang diberikan oleh FMCD atau MVV (lihat desertasi Diah Erni Herwindiati dan Maman A Djauhari tahun 2005 , “A New Criterion in Robust Estimator For Location And Covarianve Matrix, And Its Application For Outlier Labeling”). Rumusan (1) adalah rumusan jarak mahalanobis, apakah rumusan ini dapat dikatakan sebagai jarak? Untuk menjawabnya perlu dilakukan pengecekan dengan cara mengecek apakah sifat –sifat suatu jarak dipenuhi oleh formula jarak mahalanobis.
Abdullah - 10103076
BAB II Kajian Literatur
7
Suatu formula dikatakan jarak jika memenuhi: ∀x, y, k ∈ ℜ p , berlaku : 1. d ( x, y ) ≥ 0 dan d ( x, y ) = 0 ⇔ x = y 2. d ( x, y ) = d ( y , x) 3. d ( x, y ) ≤ d ( x, k ) + d ( k , y ) Akan ditunjukkan bahwa rumusan (1) merupakan jarak : 1. Sifat nomer 1 dari definisi jarak dipenuhi oleh rumusan (1) karena matriks kovariansi adalah matriks semi definit positif maka inversnya juga pasti semi definit positif sehingga jarak mahlanobis klasik pasti non negative. 2. Sifat nomer 2 dipenuhi oleh rumusan jarak mahalanobis berikut penjelasannya : d ( x, y ) = ( x − y )t * ∑ −1 *( x − y )
=
−( y − x)t * ∑ −1 *(−( y − x))
=
( y − x)t * ∑ −1 *( y − x )
= d ( y, x) 3. Sifat nomer 3 (ketaksamaan segitiga) dipenuhi oleh rumusan jarak mahalanobis. Tanda ketaksamaan bias menjadi sama dengan jika vector x, k dan y collinear (segaris) Jadi terbukti bahwa jarak mahalanobis adalah rumusan jarak.
Abdullah - 10103076
8
BAB II Kajian Literatur 2.2
Algoritma metode jarak Mahalanobis klasik Diketahui himpunan data A =
{ x1 , x2 ,.., xn }
dengan xi ∈ ℜ p berdistribusi normal
N (0, I p ) , berikut algoritma metode jarak Mahalanobis klasik jika diterapkan pada
data A. •
Hitung vector rata-rata dari data, x = (a1 , a2 ,..., a p ) dengan a j =
1 n ∑ aij untuk n i =1
aij adalah elemen matriks data A baris ke i dan kolom ke j •
Hitung vector xi − x dan transposnya yaitu ( xi − x)t untuk nilai i=1,2,…,n dengan xi ∈ ℜ p
•
Setelah itu hitung matriks kovariansi S dari himpunan data A. Ini bisa dihitung dengan menggunakan program Matlab 7 yaitu dengan cara mengetikkan sintaks “S=cov(A)” ke editor m-file.
•
Kemudian hitung nilai kuadrat jarak Mahalanobis untuk masing –masing vector data yaitu :
d S 2 ( xi , x) = ( xi − x)* S −1 *( xi − x)t untuk i = 1, 2, ..., n •
Selanjutnya plot nilai kuadrat jarak Mahalanobis untuk i dari 1 sampai n di atas terhadap indeksnya sendiri yaitu i = 1, 2, …, n
Dari plot kuadrat jarak Mahalanobis bisa terlihat data ke berapa yang patut dicurigai sebagai outlier. Dari kajian literatur dapat disimpulkan bahwa metode pendeteksian outlier berdasarkan jarak Mahalanobis hanya efektif untuk kehadiran 1 buah outlier dan distribusi kuadrat jarak Mahalanobis bersifat eksak.
Abdullah - 10103076
9
BAB II Kajian Literatur 2.3 Distribusi Kuadrat Jarak Mahalanobis
Pada metode ini yang diplot adalah nilai kuadrat jarak Mahalanobis untuk setiap data. Untuk menentukan data mana yang menjadi outlier, kita perlu menetukan terlebih dahulu titik kritis (cut-off) berdasarkan distribusi kuadrat jarak Mahalanobis. Johanna Hardin dan David M. Rocke dalam artikelnya yang terbit pada Journal of Computational and Graphical Statistics, volume 14 halaman 928 – 946 tahun 2005, mengatakan bahwa jika diberikan data
{ x1 , x2 ,.., xn }
untuk xi ∈ ℜ p
berdistribusi normal multivariat, maka n p (n − p − 1) d 2 ( xi , x) ~ Beta ( , ). 2 S (n − 1) 2 2 Dengan kata lain, kuadrat jarak Mahalanobis klasik mempunyai distribusi eksak
d S 2 ( xi , x) ~
(n − 1) 2 p (n − p − 1) Beta( , ) n 2 2
Dari sini kita peroleh mean dan variansinya, ⎡ nd 2 ( x , x) ⎤ ⎡ nd 2 ( x , x) ⎤ (n − p − 1) E ⎢ S i ⎥ = p dan var ⎢ S i ⎥ = 2 p (n + 1) ⎣ n −1 ⎦ ⎣ n −1 ⎦
Bukti. Jika diberikan X variabel acak berdistribusi Beta dengan parameter α dan β maka E[X ] =
α α +β
dan var [ X ] =
αβ (α + β + 1)(α + β ) 2
(lihat di buku ”Introduction to
Mathematical Statistics 6th edition” karangan Hogg and Craig) sehingga : •
⎡ nd 2 ( x , x) ⎤ p/2 E⎢ S i 2 ⎥= ⎣ (n − 1) ⎦ p / 2 + (n − p − 1) / 2
Abdullah - 10103076
10
BAB II Kajian Literatur =
p/2 (n − 1) / 2
=
p n −1
⎡ nd 2 ( x , x ) ⎤ ( n − 1) E ⎢ S i 2 ⎥ = p ⎣ ( n − 1) ⎦ ⎡ nd 2 ( x , x) ⎤ E⎢ S i ⎥= p ⎣ (n − 1) ⎦
•
⎡ nd 2 ( x , x ) ⎤ ( p / 2)( n − p − 1) / 2 var ⎢ S i 2 ⎥ = 2 ⎣ (n − 1) ⎦ ( p / 2 + (n − p − 1) / 2 + 1)( p / 2 + (n − p − 1) / 2)
=
p (n − p − 1) / 4 ((n + 1) / 2)((n − 1) / 2)2
=
2 p (n − p − 1) (n + 1)(n − 1) 2
⎡ nd S 2 ( xi , x ) ⎤ 2 p ( n − p − 1) ( n − 1) var ⎢ ⎥= 2 (n + 1) ⎣ ( n − 1) ⎦ 2
⎡ nd 2 ( x , x) ⎤ 2 p ( n − p − 1) var ⎢ ( n − 1) S i 2 ⎥ = ( n − 1) ⎦ ( n + 1) ⎣ ⎡ nd 2 ( x , x ) ⎤ 2 p ( n − p − 1) var ⎢ S i ⎥ = ( n + 1) ⎣ ( n − 1) ⎦
Kuadrat jarak Mahalanobis klasik juga dapat didekati oleh distribusi chisquare dengan parameter p.
Abdullah - 10103076
11
BAB II Kajian Literatur 2.4
Titik kritis (cut-off) Berdasarkan distribusi kuadrat jarak Mahalanobis di atas, maka titik kritis (cut-off) pada pengujian kehadiran outlier dapat ditentukan. Misalkan kesalahan tipe I yang diinginkan adalah α . Jadi, α adalah probabilitas bahwa data yang bukan outlier terdeteksi sebagai outlier. Maka titik kritisnya adalah, cut _ off =
(n − 1) 2 p (n − p − 1) ) * Beta(1 − α , , n 2 2
p ( n − p − 1) di mana Beta (1 − α , , ) adalah kuantil ke (1- α ) dari distribusi beta 2 2
dengan parameter
p (n − p − 1) dan , n adalah banyaknya data, dan p adalah 2 2
banyaknya variable. Untuk α = 5%, maka cut _ off =
Abdullah - 10103076
(n − 1) 2 p (n − p − 1) * Beta (0.95, , ). n 2 2