🎯 Orthogonal Matching Pursuit (OMP) for Sparse Feature Selection

Proyek ini mengimplementasikan pipeline Orthogonal Matching Pursuit (OMP), sebuah model regresi linier yang dirancang untuk menghasilkan solusi sparse (memilih hanya sejumlah kecil fitur yang paling relevan) pada data berdimensi tinggi.

⚙️ Dependencies

Pastikan Anda memiliki pustaka berikut terinstal:

pip install pandas numpy matplotlib scikit-learn

📁 Struktur Proyek

.
├── data/
│   └── train.csv        # Dataset input (diasumsikan)
└── omp_pipeline.py      # Skrip utama (kode yang Anda jalankan)
└── README.md            # File ini

---

🚀 Langkah-Langkah dan Metode Utama

1. Persiapan Data & Scaling

• Data dimuat dari data/train.csv.
• Fitur (X) dan Target (y) dipisahkan.
• Data di-split 80% (Train) dan 20% (Test).
• Fitur di-scale menggunakan StandardScaler. (Penting untuk OMP karena OMP sensitif terhadap skala fitur.)

2. Penentuan Jumlah Fitur Optimal (Sparsity)

Tujuan utama OMP adalah menentukan n_nonzero_coefs (jumlah fitur asli yang akan digunakan model). Dua pendekatan digunakan untuk membandingkan hasilnya:

Pendekatan A: OMP-CV (Otomatis)

Menggunakan OrthogonalMatchingPursuitCV untuk secara otomatis mencari n_nonzero_coefs yang optimal berdasarkan Cross-Validation internal.

Pendekatan B: GridSearchCV (Eksplisit)

Menggunakan GridSearchCV untuk menguji rentang n_nonzero_coefs secara eksplisit (misalnya, dari 1 hingga 60 dengan langkah 2) dan memilih parameter yang memberikan skor neg_mean_squared_error terbaik.

3. Pemilihan Model Akhir

Model yang dipilih (antara OMP-CV dan OMP-GridSearch) adalah yang menghasilkan RMSE (Root Mean Squared Error) terendah pada test set yang belum pernah dilihat model.

4. Interpretasi Fitur Terpilih

Model yang dipilih diinterpretasikan untuk melihat fitur mana yang dipertahankan (koefisien $\ne 0$) dan fitur mana yang dibuang (koefisien $= 0$).

---

🛡️ Analisis Kestabilan (Critical Step)

Karena OMP adalah model yang greedy (memilih fitur terbaik secara iteratif), pilihan fiturnya sangat sensitif terhadap split data.

• Metode: Dilakukan 50 kali iterasi bootstrap. Pada setiap iterasi, data di-split dan OMP dilatih ulang untuk melihat fitur mana yang dipilih.
• Tujuan: Menghitung frekuensi (persentase) fitur terpilih.

Fitur Kunci	Hasil Stabilitas (Contoh)	Implikasi Analisis
Feature 56	Frekuensi: 0.30 (Terpilih 15 dari 50 kali)	Model Tidak Stabil! Karena frekuensi jauh di bawah 1.0, fitur yang dipilih pada single run (Langkah 4) kemungkinan besar adalah hasil kebetulan. Ini menunjukkan model rentan terhadap data baru.
Fitur Lain	Frekuensi: Sangat rendah (< 0.10)	Sinyal prediktif didistribusikan secara tipis, membuat OMP bingung memilih fitur tunggal terbaik.

---

📈 Hasil Evaluasi

# Hasil Pemilihan Parameter
OMP-CV memilih n_nonzero_coefs = 1
GridSearchCV memilih n_nonzero_coefs = 1

# Hasil Ujian Akhir (OMP-CV)
OMP-Grid Test RMSE: 4.4907, MAE: 1.5567, R2: 0.0355

# Daftar Fitur Terpilih (OMP-CV)
Jumlah fitur terpilih: 1
Daftar fitur terpilih (index: 56): feature_135  coef=0.431002

# Hasil Kestabilan (CHECK STABILITY OMP 50x)
=== TOP 20 FITUR PADA STABILITY CHECK ===
   feature  count_selected_in_bootstrap  frequency
56 feature_56           15                    0.30
5  feature_5            12                    0.24
# ...

---

🚀 Cara Menjalankan

1. Clone Repository

git clone https://github.com/rifaldomalau/Orthogonal-Matching-Pursuit-OMP-Regression-on-High-Dimensional-Space.git

2. Masuk Directory

cd Orthogonal-Matching-Pursuit-OMP-Regression-on-High-Dimensional-Space

3. Install Library

pip install -r requirements.txt

4. Jalankan Notebook

jupyter notebook NotebookV1.ipynb