Feature Selection for Linear Regression Using Spiral Dynamic Optimization Algorithm

Study Case Crime Level Database

Spiral Dynamic Optimization Algorithm

Melanjutkan beberapa tulisan terkait SDOA, kali ini saya akan menunjukkan penggunaannya untuk membantu kita melakukan feature selection model machine learning.

Sebagai contoh, saya akan gunakan kasus regresi linear dari data crime.

Saya akan bertujuan membuat model regresi linear yang memprediksi inequality dari semua variabel lain yang ada pada data tersebut.

Model Regresi Linear

Data yang Digunakan

Berikut adalah data yang digunakan dalam contoh ini:

Data Crime
id	percent_m	is_south	mean_education	police_exp60	police_exp59	labour_participation	m_per1000f	state_pop	nonwhites_per1000	unemploy_m24	unemploy_m39	gdp	inequality	prob_prison	time_prison	crime_rate
1	151	1	91	58	56	510	950	33	301	108	41	394	261	0.084602	26.2011	791
2	143	0	113	103	95	583	1012	13	102	96	36	557	194	0.029599	25.2999	1635
3	142	1	89	45	44	533	969	18	219	94	33	318	250	0.083401	24.3006	578
4	136	0	121	149	141	577	994	157	80	102	39	673	167	0.015801	29.9012	1969
5	141	0	121	109	101	591	985	18	30	91	20	578	174	0.041399	21.2998	1234
6	121	0	110	118	115	547	964	25	44	84	29	689	126	0.034201	20.9995	682
7	127	1	111	82	79	519	982	4	139	97	38	620	168	0.042100	20.6993	963
8	131	1	109	115	109	542	969	50	179	79	35	472	206	0.040099	24.5988	1555
9	157	1	90	65	62	553	955	39	286	81	28	421	239	0.071697	29.4001	856
10	140	0	118	71	68	632	1029	7	15	100	24	526	174	0.044498	19.5994	705
11	124	0	105	121	116	580	966	101	106	77	35	657	170	0.016201	41.6000	1674
12	134	0	108	75	71	595	972	47	59	83	31	580	172	0.031201	34.2984	849
13	128	0	113	67	60	624	972	28	10	77	25	507	206	0.045302	36.2993	511
14	135	0	117	62	61	595	986	22	46	77	27	529	190	0.053200	21.5010	664
15	152	1	87	57	53	530	986	30	72	92	43	405	264	0.069100	22.7008	798
16	142	1	88	81	77	497	956	33	321	116	47	427	247	0.052099	26.0991	946
17	143	0	110	66	63	537	977	10	6	114	35	487	166	0.076299	19.1002	539
18	135	1	104	123	115	537	978	31	170	89	34	631	165	0.119804	18.1996	929
19	130	0	116	128	128	536	934	51	24	78	34	627	135	0.019099	24.9008	750
20	125	0	108	113	105	567	985	78	94	130	58	626	166	0.034801	26.4010	1225
21	126	0	108	74	67	602	984	34	12	102	33	557	195	0.022800	37.5998	742
22	157	1	89	47	44	512	962	22	423	97	34	288	276	0.089502	37.0994	439
23	132	0	96	87	83	564	953	43	92	83	32	513	227	0.030700	25.1989	1216
24	131	0	116	78	73	574	1038	7	36	142	42	540	176	0.041598	17.6000	968
25	130	0	116	63	57	641	984	14	26	70	21	486	196	0.069197	21.9003	523
26	131	0	121	160	143	631	1071	3	77	102	41	674	152	0.041698	22.1005	1993
27	135	0	109	69	71	540	965	6	4	80	22	564	139	0.036099	28.4999	342
28	152	0	112	82	76	571	1018	10	79	103	28	537	215	0.038201	25.8006	1216
29	119	0	107	166	157	521	938	168	89	92	36	637	154	0.023400	36.7009	1043
30	166	1	89	58	54	521	973	46	254	72	26	396	237	0.075298	28.3011	696
31	140	0	93	55	54	535	1045	6	20	135	40	453	200	0.041999	21.7998	373
32	125	0	109	90	81	586	964	97	82	105	43	617	163	0.042698	30.9014	754
33	147	1	104	63	64	560	972	23	95	76	24	462	233	0.049499	25.5005	1072
34	126	0	118	97	97	542	990	18	21	102	35	589	166	0.040799	21.6997	923
35	123	0	102	97	87	526	948	113	76	124	50	572	158	0.020700	37.4011	653
36	150	0	100	109	98	531	964	9	24	87	38	559	153	0.006900	44.0004	1272
37	177	1	87	58	56	638	974	24	349	76	28	382	254	0.045198	31.6995	831
38	133	0	104	51	47	599	1024	7	40	99	27	425	225	0.053998	16.6999	566
39	149	1	88	61	54	515	953	36	165	86	35	395	251	0.047099	27.3004	826
40	145	1	104	82	74	560	981	96	126	88	31	488	228	0.038801	29.3004	1151
41	148	0	122	72	66	601	998	9	19	84	20	590	144	0.025100	30.0001	880
42	141	0	109	56	54	523	968	4	2	107	37	489	170	0.088904	12.1996	542
43	162	1	99	75	70	522	996	40	208	73	27	496	224	0.054902	31.9989	823
44	136	0	121	95	96	574	1012	29	36	111	37	622	162	0.028100	30.0001	1030
45	139	1	88	46	41	480	968	19	49	135	53	457	249	0.056202	32.5996	455
46	126	0	104	106	97	599	989	40	24	78	25	593	171	0.046598	16.6999	508
47	130	0	121	90	91	623	1049	3	22	113	40	588	160	0.052802	16.0997	849

Tujuan

Saya akan membuat model regresi linear terbaik yang bisa memprediksi nilai inequality dari prediktor-prediktor yang ada di data crime. Untuk itu, saya akan menjadikan nilai \(R^2\) sebagai parameter goodness of fit yang akan saya maksimalkan.

Bagaimana saya bisa mendapatkan nilai \(R^2\) tertinggi?

Saya perlu memilih dan memilah prediktor mana saja yang terbaik.

Oleh karena itu saya menggunakan SDOA untuk melakukannya.

Catatan Penting

Metode eksak yang bisa digunakan untuk melakukan feature selection pada metode regresi linear adalah backward atau forward stepwise. Metode eksak menjadi solusi yang diberikan adalah yang terbaik.

Namun pendekatan meta heuristic seperti SDOA tidak menjamin solusi yang diberikan adalah yang terbaik tapi dari segi pengerjaannya relatif mudah diaplikasikan ke berbagai model machine learning termasuk klasifikasi. Agar solusi yang diberikan optimal, kita cukup memperluas area jelajah meta heuristic atau memperbanyak percobaan saja.

Flowchart Pengerjaan

Berikut ini adalah flowchart pengerjaan ini:

Pengerjaan

Tahap I

Pertama-tama saya akan lakukan beberapa pre-processing seperti berikut:

target = data$inequality                  # save variabel target
data = data %>% select(-id,-inequality)   # menghapus variabel target agar semua data berisi murni predictors
nama_var = colnames(data)                 # save variabel dulu untuk kepentingan SDOA

Tahap II

Membuat dua functions, yakni objective function dan matriks rotasi.

# set obj function
obj_funct = function(list){
  bound = round(list,0)
  predictor = nama_var[bound == 1]
  df_reg = data[predictor]
  df_reg$target = target
  
  model = lm(target ~ .,df_reg)
  hasil = summary(model)
  r_sq = hasil$adj.r.squared
  return(r_sq)
}

# set constraint 1
batas1 = function(list){
  bound = round(list,0)
  sqrt(sum(bound^2)) - sqrt(15)
}

# set constraint 2
batas2 = function(list){
  bound = round(list,0)
  1 - sqrt(sum(bound^2))
}

beta = 9999999

# obj function keseluruhan
f_tot = function(list){
  - obj_funct(list) + max((beta * batas1(list)),0) + max((beta * batas2(list)),0)
}

# function matriks rotasi
buat_rot_mat = function(theta,n){
  # buat template sebuah matriks identitas
  temp_mat = matrix(0,ncol = n,nrow = n)
  diag(temp_mat) = 1
  
  # buat matriks identitas terlebih dahulu
  mat_rot = temp_mat
  
  for(i in 1:(n-1)){
    for(j in 1:i){
      temp = temp_mat
      idx = n-i
      idy = n+1-j
      # print(paste0("Matriks rotasi untuk ",idx," - ",idy,": DONE"))
      temp[idx,idx] = cos(theta)
      temp[idx,idy] = -sin(theta)
      temp[idy,idx] = sin(theta)
      temp[idy,idy] = cos(theta)
      # assign(paste0("M",idx,idy),temp)
      mat_rot = mat_rot %*% temp
      mat_rot = mat_rot 
    }
  }
  return(mat_rot)
}

Tahap III

Set semua initial conditions:

# random calon solusi
N = 450                      # berapa banyak calon yang akan digenerate
star = vector("list",N)     # template utk calon
f_hit = c()                 # template utk nilai obj function

# looping utk menghitung generate sekaligus menghitung obj function
for(i in 1:N){
  calon = runif(15,0,1)
  star[[i]] = calon
  f_hit[i] = f_tot(calon)
}

# set matriks rotasi
mat_rotasi = buat_rot_mat(2*pi / 10,15)

Tahap IV

Mulai melakukan SDOA:

for(ikanx in 1:60){              # melakukan SDOA sebanyak 80 kali rotasi dan konstraksi
  # penentuan calon dengan nilai paling minimum
  n_bhole = which.min(f_hit)
  bhole = star[[n_bhole]]
  
  # melakukan rotasi dan konstraksi
  for(i in 1:N){
    Xt = star[[i]]
    X = mat_rotasi %*% (Xt - bhole)
    X = bhole + (.8 * X)
    star[[i]] = X
  }
  
  # perhitungan obj function kembali
  for (i in 1:N){
    temp = f_tot(star[[i]])
    f_hit[i] = temp
  }
}

Tahap V

Mengeluarkan hasil akhir:

hasil = which.min(f_hit)
pilihan = star[[hasil]] %>% round()

# nilai R squared terbaik
obj_funct(pilihan)

## [1] 0.8893899

# prediktor yang dipilih
nama_var[pilihan == 1]

## [1] "percent_m"            "is_south"             "mean_education"      
## [4] "police_exp60"         "labour_participation" "state_pop"           
## [7] "gdp"                  "crime_rate"

Kesimpulan

Bisa dilihat bahwa SDOA bisa dijadikan salah satu algoritma untuk melakukan feature selection.

Keuntungan yang bisa kita dapatkan dari pendekatan ini adalah kita bisa membatasi berapa banyak predictor yang diperlukan.