---
# System prepended metadata

title: Deteksi Ouliter

---



###   **Angle-Based Outlier Detection (ABOD)**

**Angle-Based Outlier Detection (ABOD)** adalah pendekatan geometris untuk mengidentifikasi outlier dalam data berdimensi tinggi dengan menganalisis **varians sudut** yang dibentuk oleh vektor-vektor dari suatu titik ke tetangganya.


Dalam satu himpunan data, titik-titik normal cenderung memiliki sudut-sudut yang serupa antara pasangan vektor yang menghubungkannya ke titik lain. Sebaliknya, outlier sering kali terletak di tepi dan membentuk rentang sudut yang sangat luas terhadap tetangganya — artinya, varians sudut mereka **tinggi**.

> Titik outlier "melihat" tetangganya dari banyak arah berbeda → varians sudut besar → outlier.  
> Titik normal melihat tetangganya dari arah yang mirip → varians sudut kecil → inlier.

---

### Cara kerja ABOD:



---

1. Untuk setiap titik $p_i$ dalam dataset:  
   - Hitung semua vektor pasangan dari $p_i$ ke titik lainnya:  
     $\vec{v}_{ij} = p_j - p_i$  
   - Untuk setiap pasangan vektor seperti $(\vec{v}_{ij}, \vec{v}_{ik})$, hitung sudut di antara keduanya menggunakan rumus hasil kali titik:  
     $\cos(\theta_{ijk})=\frac{\vec{v}_{ij}\cdot\vec{v}_{ik}}{\|\vec{v}_{ij}\|\cdot\|\vec{v}_{ik}\|}$  
   - Hitung **varians** dari semua sudut tersebut untuk titik $p_i$.

2. **Skor outlier** untuk $p_i$ adalah **varians sudut**:  
   $\text{ABOD}(p_i)=\text{Var}(\theta_{ijk})\quad\text{untuk semua }j,k\neq i$




3. Titik-titik dengan **varians sudut tinggi** ditandai sebagai **outlier**.

---

### Kelebihan ABOD:
- **Berbasis geometri**: Memanfaatkan bentuk intrinsik distribusi data.  
- **Tanpa ambang jarak**: Berbeda dengan k-NN atau LOF, tidak perlu memilih nilai k atau radius.  
- **Efektif di dimensi tinggi**: Sering lebih baik daripada metode berbasis jarak ketika *curse of dimensionality* mempengaruhi jarak.

---

### Keterbatasan:
- **Komputasi mahal**: Kompleksitas \( O(n^3) \) karena adanya tiga loop bersarang yang melibatkan semua triple titik.  
- **Sensitif terhadap noise**: Dapat terganggu oleh data berisik atau jarang.  
- **Tidak invariant terhadap skala**: Memerlukan normalisasi jika fitur memiliki skala berbeda.




###  **Langkah-Langkah Menentukan Persentase Anomali dengan ABOD**

#### 1. **Hitung Skor ABOD untuk Setiap Titik**
Gunakan algoritma ABOD untuk menghitung skor outlier bagi semua titik dalam dataset:

$$
\text{ABOD}(p_i) = \text{Var}(\theta_{ijk}) \quad \text{untuk semua } j,k \neq i
$$

> Skor ABOD tinggi → kemungkinan besar outlier  
> Skor ABOD rendah → kemungkinan besar inlier

Hasilnya adalah vektor skor: `[0.12, 0.45, 1.89, 0.08, 3.21, ...]` — satu nilai per titik.

---

#### 2. **Urutkan Skor ABOD dari Tertinggi ke Terendah**
Setelah mendapatkan semua skor, urutkan secara **descending** (terbesar ke terkecil):

```python
abod_scores_sorted = sorted(abod_scores, reverse=True)
```

Contoh:
```
Skor ABOD (terurut): [3.21, 1.89, 0.45, 0.12, 0.08]
```

---

#### 3. **Tentukan Persentase Anomali yang Diinginkan**
Anda memilih **persentase anomali** berdasarkan kebutuhan bisnis atau eksperimen, misalnya:

| Tujuan | Persentase Anomali |
|--------|---------------------|
| Deteksi sangat ketat (high-security) | 1% |
| Deteksi umum (fraud detection) | 5% |
| Eksplorasi awal (data profiling) | 10% |
| Sensitivitas tinggi (penelitian) | 1–5% |

> **Rekomendasi umum**: Mulai dari **1% hingga 5%**, karena outlier biasanya jarang dalam data nyata.

---

#### 4. **Ambil Top N Titik sebagai Anomali**
Misalnya:

- Jumlah total titik: \( N = 1000 \)
- Ingin mendeteksi **5% anomali** → ambil top \( 5\% \times 1000 = 50 \) titik

Ambil 50 titik dengan **skor ABOD tertinggi**.

→ Ini adalah **5% anomali** menurut ABOD.

---

#### 5. **Tentukan Threshold Otomatis (Opsional)**
Jika ingin otomatis tanpa input manual, gunakan statistik:

##### a. Gunakan **kuartil** (contoh: atas 10%)
```python
threshold = np.percentile(abod_scores, 90)  # Ambil yang di atas 90th percentile
anomalies = abod_scores > threshold
```

##### b. Gunakan **mean + std** (asumsi distribusi normal)
```python
mean_score = np.mean(abod_scores)
std_score = np.std(abod_scores)
threshold = mean_score + 2 * std_score  # 2 standar deviasi
anomalies = abod_scores > threshold
```

> Catatan: Distribusi skor ABOD **tidak selalu normal**, jadi metode ini kurang andal dibanding kuartil.

##### c. Gunakan **Interquartile Range (IQR)** — lebih robust
```python
Q1 = np.percentile(abod_scores, 25)
Q3 = np.percentile(abod_scores, 75)
IQR = Q3 - Q1
threshold = Q3 + 1.5 * IQR
anomalies = abod_scores > threshold
```

> Metode IQR sering digunakan dalam deteksi outlier klasik (boxplot). Cocok jika ingin pendekatan non-parametrik.

---





### Referensi :
> **Kriegel, H.-P., Kröger, P., Zimek, A. (2008).** *"Angle-Based Outlier Detection in High-Dimensional Data."* Dalam *Proceedings of the 14th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD '08)*.

---




---

## Anomali deteksi berdasarkan KNN

Menentukan anomali berdasarkan K-Nearest Neighbors (KNN) adalah salah satu pendekatan distance-based yang populer dalam deteksi anomali. Ide dasarnya adalah: titik yang jauh dari tetangga terdekatnya kemungkinan besar merupakan anomali.

Berikut penjelasan langkah demi langkah cara menentukan anomali menggunakan KNN.

---

### Prinsip Dasar

Untuk setiap titik data, cari K tetangga terdekat berdasarkan jarak (misalnya Euclidean). Jika rata-rata jarak ke K tetangga terdekat sangat besar, maka titik tersebut dianggap anomali. Semakin jauh suatu titik dari tetangganya, semakin besar kemungkinannya menjadi outlier.

---

### Langkah-Langkah Menentukan Anomali dengan KNN

#### 1. Pilih nilai K

K adalah jumlah tetangga terdekat yang dipertimbangkan. Nilai K biasanya dipilih secara eksperimen (misalnya K = 3, 5, 10).  
- K kecil: lebih sensitif terhadap noise.  
- K besar: lebih stabil tetapi mungkin melewatkan anomali lokal.  

Pilih K yang sesuai dengan ukuran dataset dan distribusi data.

#### 2. Hitung jarak ke K tetangga terdekat untuk setiap titik

Untuk setiap titik data $x_i$, hitung jarak ke semua titik lain menggunakan Euclidean distance:  
$d(x_i,x_j)=\sqrt{\sum_{k=1}^{n}(x_{ik}-x_{jk})^2}$  

Urutkan semua jarak, ambil K jarak terkecil. Ini adalah jarak ke K-nearest neighbors.

#### 3. Hitung KNN Distance atau Local Outlier Factor (LOF)

Ada dua pendekatan umum.

---

#### Pendekatan 1: KNN Distance (Sederhana)

Untuk setiap titik $x_i$, hitung:  
$\text{KNN-Distance}(x_i)=\text{rata-rata jarak ke K tetangga terdekat}$  

Titik dengan KNN-Distance tertinggi dianggap anomali.  
Dapat mengurutkan semua titik berdasarkan KNN-Distance, lalu pilih top N sebagai anomali.  

Contoh: Jika ada 1000 titik dan ingin mendeteksi 5% anomali, ambil 50 titik dengan KNN-Distance tertinggi.

---

#### Pendekatan 2: Local Outlier Factor (LOF) — Lebih Canggih

LOF mempertimbangkan kerapatan relatif suatu titik dibandingkan tetangganya.

Langkah LOF:  
1. Hitung k-distance dari setiap titik: jarak ke K-th nearest neighbor.  
2. Hitung reachability distance dari titik A ke titik B:  
   $\text{reach-dist}_k(A,B)=\max(\text{k-distance}(B),d(A,B))$  
3. Hitung local reachability density (lrd) dari titik A:  
   $\text{lrd}_k(A)=\frac{1}{\frac{\sum_{B \in N_k(A)} \text{reach-dist}_k(A,B)}{|N_k(A)|}}$  
4. Hitung LOF score dari titik A:  
   $\text{LOF}_k(A)=\frac{\sum_{B \in N_k(A)} \frac{\text{lrd}_k(B)}{\text{lrd}_k(A)}}{|N_k(A)|}$  

Interpretasi LOF:  
- LOF ≈ 1: kerapatan mirip tetangga → normal  
- LOF >> 1: kerapatan jauh lebih rendah → anomali  
- LOF << 1: lebih padat daripada tetangga → kemungkinan cluster dalam  

LOF lebih robust karena membandingkan kerapatan lokal, bukan hanya jarak absolut.

---

### Contoh Sederhana (KNN Distance)

Misalkan ada 5 titik 2D:  
A(1,1), B(1,2), C(2,1), D(8,8), E(9,9)  

Pilih K=2.  

Untuk titik D(8,8):  
Jarak ke E(9,9) = $\sqrt{(8-9)^2+(8-9)^2}=\sqrt{2}\approx1.41$  
Jarak ke C(2,1) = $\sqrt{(8-2)^2+(8-1)^2}=\sqrt{36+49}=\sqrt{85}\approx9.22$  
Dua tetangga terdekat: E dan C  
Rata-rata jarak = $(1.41 + 9.22)/2 \approx 5.32$  

Untuk titik A(1,1):  
Jarak ke B(1,2) = 1.0  
Jarak ke C(2,1) = 1.0  
Rata-rata jarak = 1.0  

Maka D dan E memiliki KNN-Distance tinggi → anomali.

---

### Tips Praktis

| Aspek | Rekomendasi |
|-------|-------------|
| Jenis data | Cocok untuk data numerik, tidak cocok untuk kategorikal tanpa encoding |
| Skala fitur | Gunakan normalisasi (MinMax, Z-score) agar jarak tidak bias oleh skala besar |
| Nilai K | Mulai dari K=3–10, uji dengan cross-validation atau visualisasi |
| Deteksi anomali | Gunakan threshold: ambil top 1%, 5%, atau 10% titik dengan jarak tertinggi |
| Alternatif | Gunakan library seperti scikit-learn dengan LocalOutlierFactor |

---

### Implementasi Python (Contoh)

```python
from sklearn.neighbors import LocalOutlierFactor
import numpy as np

X = np.array([[1,1], [1,2], [2,1], [8,8], [9,9]])

lof = LocalOutlierFactor(n_neighbors=2, contamination=0.2)
y_pred = lof.fit_predict(X)

print("Prediksi:", y_pred)
# Output: [ 1  1  1 -1 -1] → D dan E adalah anomali

negative_outlier_factors = lof.negative_outlier_factor_
print("Skor LOF:", negative_outlier_factors)
```

---

## **Connectivity-Based Outlier Factor (COF)** adalah 
Connectivity-Based Outlier Factor metode deteksi outlier berbasis **keterhubungan lokal** (local connectivity) dalam ruang data. Metode ini diperkenalkan oleh **Ting et al. (2002)** sebagai perbaikan dari LOF (*Local Outlier Factor*) dengan fokus pada struktur jaringan keterhubungan antar titik, bukan hanya kepadatan.

---

### Definisi COF

**Connectivity-Based Outlier Factor (COF)** mengukur seberapa “terisolasi” suatu titik berdasarkan **rata-rata rasio jarak terpendek** antara titik tersebut dan tetangganya dalam *k-nearest neighbor graph*.

>  **Intuisi**:  
> Titik normal terhubung erat dengan tetangga-tetangganya melalui jalur pendek — seperti dalam kluster padat.  
> Titik outlier memiliki jalur keterhubungan yang panjang dan tidak alami ke tetangganya — artinya, ia "terputus" dari kelompoknya secara topologis.

---

### Cara Kerja COF

#### Langkah 1: Tentukan *k*-nearest neighbors
Untuk setiap titik $p_i$, cari $k$ titik terdekat (berdasarkan jarak Euclidean), disebut $\text{NN}_k(p_i)$.

#### Langkah 2: Hitung *Chain Distance* (Jarak Rantai)
Untuk setiap pasangan titik $(p_i, p_j)$, hitung **chain distance** $\text{CD}(p_i, p_j)$:

- Ini adalah panjang jalur terpendek dari $p_i$ ke $p_j$, di mana setiap langkah dalam jalur harus menghubungkan dua titik yang saling merupakan *k*-nearest neighbor.
- Jika $p_j \in \text{NN}_k(p_i)$, maka:
  $\text{CD}(p_i, p_j) = \text{dist}(p_i, p_j)$
- Jika tidak, cari jalur terpendek melalui titik-titik lain yang saling terhubung dalam graf $k$-NN:
  $\text{CD}(p_i, p_j) = \min_{\text{path } p_i \to p_{a_1} \to \dots \to p_{a_m} \to p_j} \sum \text{dist}(p_a, p_b)$

> Catatan : Chain distance hanya mempertimbangkan edge antar titik yang saling termasuk dalam *k*-NN masing-masing.

#### Langkah 3: Hitung *Average Chain Distance* (ACD)
Untuk setiap titik $p_i$, hitung rata-rata chain distance ke semua $k$ tetangganya:

$\text{ACD}(p_i) = \frac{1}{k} \sum_{p_j \in \text{NN}_k(p_i)} \text{CD}(p_i, p_j)$

#### Langkah 4: Hitung COF
COF dari titik $p_i$ adalah rata-rata rasio ACD dari tetangganya dibandingkan dengan ACD-nya sendiri:

$\text{COF}(p_i) = \frac{1}{k} \sum_{p_j \in \text{NN}_k(p_i)} \frac{\text{ACD}(p_j)}{\text{ACD}(p_i)}$

> Artinya:  
> Jika $p_i$ adalah titik normal → tetangganya juga memiliki ACD serupa → COF ≈ 1  
> Jika $p_i$ adalah outlier → tetangganya punya ACD jauh lebih besar (karena mereka terhubung lewat jalur panjang) → COF >> 1

---

### Interpretasi Skor COF

| Nilai COF | Interpretasi |
|----------|--------------|
| ≈ 1      | Titik normal (terhubung baik dengan tetangganya) |
| > 1      | Potensi outlier (lebih terisolasi secara topologis) |
| Semakin besar | Lebih kuat sebagai outlier |

Biasanya, titik dengan COF > threshold (misalnya 1.5–2.0) dianggap outlier.

---

### Kelebihan COF

- **Lebih sensitif terhadap bentuk kluster non-konveks** dibanding LOF.
- Tidak bergantung pada asumsi kepadatan global — cocok untuk data dengan variasi kepadatan.
- Menggunakan struktur graf keterhubungan, sehingga lebih robust terhadap noise lokal.

### Keterbatasan COF

- **Komputasi sangat mahal**: $O(n^2 \cdot k)$ atau lebih karena pencarian jalur terpendek (seperti Dijkstra) untuk setiap pasangan.
- Sensitif terhadap pilihan $k$ — nilai kecil bisa terlalu sensitif terhadap noise, nilai besar bisa mengaburkan outlier.
- Tidak efisien untuk dataset besar (>10K titik) tanpa optimasi.

---

### Perbandingan dengan LOF

| Aspek | LOF | COF |
|------|-----|-----|
| Dasar | Kepadatan lokal | Keterhubungan topologis |
| Ukuran | Jarak langsung ke tetangga | Jalur rantai terpendek antar tetangga |
| Kompleksitas | $O(n \cdot k^2)$ | $O(n^2 \cdot k)$ |
| Sensitivitas terhadap bentuk | Sedang | Tinggi (bisa deteksi outlier di kluster tak konveks) |
| Robust terhadap noise | Kurang | Lebih baik |




---

### Referensi Asli

> **Ting, K. M., Kang, Y., Zhao, Z., & Chawla, S. (2002).**  
> *"Connectivity-based Outlier Detection."*  
> In *Proceedings of the 2nd SIAM International Conference on Data Mining (SDM '02)*.  
> https://doi.org/10.1137/1.9781611972719.14

---

### Tips Implementasi

- Gunakan **k = 5–20** untuk dataset ukuran sedang.
- Gunakan **graph shortest path algorithm** (misalnya Floyd-Warshall atau Dijkstra) untuk menghitung `CD`.
- Untuk data besar, pertimbangkan **approximate COF** atau gunakan **sampling**.
