### **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**.
Sign in with Wallet
Connect another wallet