00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011 #ifdef USE_SVMLIGHT
00012 #include <shogun/classifier/svm/SVMLightOneClass.h>
00013 #endif //USE_SVMLIGHT
00014
00015 #include <shogun/kernel/Kernel.h>
00016 #include <shogun/classifier/svm/ScatterSVM.h>
00017 #include <shogun/kernel/ScatterKernelNormalizer.h>
00018 #include <shogun/io/SGIO.h>
00019
00020 using namespace shogun;
00021
00022 CScatterSVM::CScatterSVM(void)
00023 : CMultiClassSVM(ONE_VS_REST), scatter_type(NO_BIAS_LIBSVM),
00024 model(NULL), norm_wc(NULL), norm_wcw(NULL), rho(0), m_num_classes(0)
00025 {
00026 SG_UNSTABLE("CScatterSVM::CScatterSVM(void)", "\n");
00027 }
00028
00029 CScatterSVM::CScatterSVM(SCATTER_TYPE type)
00030 : CMultiClassSVM(ONE_VS_REST), scatter_type(type), model(NULL),
00031 norm_wc(NULL), norm_wcw(NULL), rho(0), m_num_classes(0)
00032 {
00033 }
00034
00035 CScatterSVM::CScatterSVM(float64_t C, CKernel* k, CLabels* lab)
00036 : CMultiClassSVM(ONE_VS_REST, C, k, lab), scatter_type(NO_BIAS_LIBSVM), model(NULL),
00037 norm_wc(NULL), norm_wcw(NULL), rho(0), m_num_classes(0)
00038 {
00039 }
00040
00041 CScatterSVM::~CScatterSVM()
00042 {
00043 SG_FREE(norm_wc);
00044 SG_FREE(norm_wcw);
00045 }
00046
00047 bool CScatterSVM::train_machine(CFeatures* data)
00048 {
00049 ASSERT(labels && labels->get_num_labels());
00050 m_num_classes = labels->get_num_classes();
00051 int32_t num_vectors = labels->get_num_labels();
00052
00053 if (data)
00054 {
00055 if (labels->get_num_labels() != data->get_num_vectors())
00056 SG_ERROR("Number of training vectors does not match number of labels\n");
00057 kernel->init(data, data);
00058 }
00059
00060 int32_t* numc=SG_MALLOC(int32_t, m_num_classes);
00061 CMath::fill_vector(numc, m_num_classes, 0);
00062
00063 for (int32_t i=0; i<num_vectors; i++)
00064 numc[(int32_t) labels->get_int_label(i)]++;
00065
00066 int32_t Nc=0;
00067 int32_t Nmin=num_vectors;
00068 for (int32_t i=0; i<m_num_classes; i++)
00069 {
00070 if (numc[i]>0)
00071 {
00072 Nc++;
00073 Nmin=CMath::min(Nmin, numc[i]);
00074 }
00075
00076 }
00077 SG_FREE(numc);
00078 m_num_classes=m_num_classes;
00079
00080 bool result=false;
00081
00082 if (scatter_type==NO_BIAS_LIBSVM)
00083 {
00084 result=train_no_bias_libsvm();
00085 }
00086 #ifdef USE_SVMLIGHT
00087 else if (scatter_type==NO_BIAS_SVMLIGHT)
00088 {
00089 result=train_no_bias_svmlight();
00090 }
00091 #endif //USE_SVMLIGHT
00092 else if (scatter_type==TEST_RULE1 || scatter_type==TEST_RULE2)
00093 {
00094 float64_t nu_min=((float64_t) Nc)/num_vectors;
00095 float64_t nu_max=((float64_t) Nc)*Nmin/num_vectors;
00096
00097 SG_INFO("valid nu interval [%f ... %f]\n", nu_min, nu_max);
00098
00099 if (get_nu()<nu_min || get_nu()>nu_max)
00100 SG_ERROR("nu out of valid range [%f ... %f]\n", nu_min, nu_max);
00101
00102 result=train_testrule12();
00103 }
00104 else
00105 SG_ERROR("Unknown Scatter type\n");
00106
00107 return result;
00108 }
00109
00110 bool CScatterSVM::train_no_bias_libsvm()
00111 {
00112 struct svm_node* x_space;
00113
00114 problem.l=labels->get_num_labels();
00115 SG_INFO( "%d trainlabels\n", problem.l);
00116
00117 problem.y=SG_MALLOC(float64_t, problem.l);
00118 problem.x=SG_MALLOC(struct svm_node*, problem.l);
00119 x_space=SG_MALLOC(struct svm_node, 2*problem.l);
00120
00121 for (int32_t i=0; i<problem.l; i++)
00122 {
00123 problem.y[i]=+1;
00124 problem.x[i]=&x_space[2*i];
00125 x_space[2*i].index=i;
00126 x_space[2*i+1].index=-1;
00127 }
00128
00129 int32_t weights_label[2]={-1,+1};
00130 float64_t weights[2]={1.0,get_C2()/get_C1()};
00131
00132 ASSERT(kernel && kernel->has_features());
00133 ASSERT(kernel->get_num_vec_lhs()==problem.l);
00134
00135 param.svm_type=C_SVC;
00136 param.kernel_type = LINEAR;
00137 param.degree = 3;
00138 param.gamma = 0;
00139 param.coef0 = 0;
00140 param.nu = get_nu();
00141 CKernelNormalizer* prev_normalizer=kernel->get_normalizer();
00142 kernel->set_normalizer(new CScatterKernelNormalizer(
00143 m_num_classes-1, -1, labels, prev_normalizer));
00144 param.kernel=kernel;
00145 param.cache_size = kernel->get_cache_size();
00146 param.C = 0;
00147 param.eps = epsilon;
00148 param.p = 0.1;
00149 param.shrinking = 0;
00150 param.nr_weight = 2;
00151 param.weight_label = weights_label;
00152 param.weight = weights;
00153 param.nr_class=m_num_classes;
00154 param.use_bias = get_bias_enabled();
00155
00156 const char* error_msg = svm_check_parameter(&problem,¶m);
00157
00158 if(error_msg)
00159 SG_ERROR("Error: %s\n",error_msg);
00160
00161 model = svm_train(&problem, ¶m);
00162 kernel->set_normalizer(prev_normalizer);
00163 SG_UNREF(prev_normalizer);
00164
00165 if (model)
00166 {
00167 ASSERT((model->l==0) || (model->l>0 && model->SV && model->sv_coef && model->sv_coef));
00168
00169 ASSERT(model->nr_class==m_num_classes);
00170 create_multiclass_svm(m_num_classes);
00171
00172 rho=model->rho[0];
00173
00174 SG_FREE(norm_wcw);
00175 norm_wcw = SG_MALLOC(float64_t, m_num_svms);
00176
00177 for (int32_t i=0; i<m_num_classes; i++)
00178 {
00179 int32_t num_sv=model->nSV[i];
00180
00181 CSVM* svm=new CSVM(num_sv);
00182 svm->set_bias(model->rho[i+1]);
00183 norm_wcw[i]=model->normwcw[i];
00184
00185
00186 for (int32_t j=0; j<num_sv; j++)
00187 {
00188 svm->set_alpha(j, model->sv_coef[i][j]);
00189 svm->set_support_vector(j, model->SV[i][j].index);
00190 }
00191
00192 set_svm(i, svm);
00193 }
00194
00195 SG_FREE(problem.x);
00196 SG_FREE(problem.y);
00197 SG_FREE(x_space);
00198 for (int32_t i=0; i<m_num_classes; i++)
00199 {
00200 SG_FREE(model->SV[i]);
00201 model->SV[i]=NULL;
00202 }
00203 svm_destroy_model(model);
00204
00205 if (scatter_type==TEST_RULE2)
00206 compute_norm_wc();
00207
00208 model=NULL;
00209 return true;
00210 }
00211 else
00212 return false;
00213 }
00214
00215 #ifdef USE_SVMLIGHT
00216 bool CScatterSVM::train_no_bias_svmlight()
00217 {
00218 CKernelNormalizer* prev_normalizer=kernel->get_normalizer();
00219 CScatterKernelNormalizer* n=new CScatterKernelNormalizer(
00220 m_num_classes-1, -1, labels, prev_normalizer);
00221 kernel->set_normalizer(n);
00222 kernel->init_normalizer();
00223
00224 CSVMLightOneClass* light=new CSVMLightOneClass(C1, kernel);
00225 light->set_linadd_enabled(false);
00226 light->train();
00227
00228 SG_FREE(norm_wcw);
00229 norm_wcw = SG_MALLOC(float64_t, m_num_classes);
00230
00231 int32_t num_sv=light->get_num_support_vectors();
00232 create_new_model(num_sv);
00233
00234 for (int32_t i=0; i<num_sv; i++)
00235 {
00236 set_alpha(i, light->get_alpha(i));
00237 set_support_vector(i, light->get_support_vector(i));
00238 }
00239
00240 kernel->set_normalizer(prev_normalizer);
00241 return true;
00242 }
00243 #endif //USE_SVMLIGHT
00244
00245 bool CScatterSVM::train_testrule12()
00246 {
00247 struct svm_node* x_space;
00248 problem.l=labels->get_num_labels();
00249 SG_INFO( "%d trainlabels\n", problem.l);
00250
00251 problem.y=SG_MALLOC(float64_t, problem.l);
00252 problem.x=SG_MALLOC(struct svm_node*, problem.l);
00253 x_space=SG_MALLOC(struct svm_node, 2*problem.l);
00254
00255 for (int32_t i=0; i<problem.l; i++)
00256 {
00257 problem.y[i]=labels->get_label(i);
00258 problem.x[i]=&x_space[2*i];
00259 x_space[2*i].index=i;
00260 x_space[2*i+1].index=-1;
00261 }
00262
00263 int32_t weights_label[2]={-1,+1};
00264 float64_t weights[2]={1.0,get_C2()/get_C1()};
00265
00266 ASSERT(kernel && kernel->has_features());
00267 ASSERT(kernel->get_num_vec_lhs()==problem.l);
00268
00269 param.svm_type=NU_MULTICLASS_SVC;
00270 param.kernel_type = LINEAR;
00271 param.degree = 3;
00272 param.gamma = 0;
00273 param.coef0 = 0;
00274 param.nu = get_nu();
00275 param.kernel=kernel;
00276 param.cache_size = kernel->get_cache_size();
00277 param.C = 0;
00278 param.eps = epsilon;
00279 param.p = 0.1;
00280 param.shrinking = 0;
00281 param.nr_weight = 2;
00282 param.weight_label = weights_label;
00283 param.weight = weights;
00284 param.nr_class=m_num_classes;
00285 param.use_bias = get_bias_enabled();
00286
00287 const char* error_msg = svm_check_parameter(&problem,¶m);
00288
00289 if(error_msg)
00290 SG_ERROR("Error: %s\n",error_msg);
00291
00292 model = svm_train(&problem, ¶m);
00293
00294 if (model)
00295 {
00296 ASSERT((model->l==0) || (model->l>0 && model->SV && model->sv_coef && model->sv_coef));
00297
00298 ASSERT(model->nr_class==m_num_classes);
00299 create_multiclass_svm(m_num_classes);
00300
00301 rho=model->rho[0];
00302
00303 SG_FREE(norm_wcw);
00304 norm_wcw = SG_MALLOC(float64_t, m_num_svms);
00305
00306 for (int32_t i=0; i<m_num_classes; i++)
00307 {
00308 int32_t num_sv=model->nSV[i];
00309
00310 CSVM* svm=new CSVM(num_sv);
00311 svm->set_bias(model->rho[i+1]);
00312 norm_wcw[i]=model->normwcw[i];
00313
00314
00315 for (int32_t j=0; j<num_sv; j++)
00316 {
00317 svm->set_alpha(j, model->sv_coef[i][j]);
00318 svm->set_support_vector(j, model->SV[i][j].index);
00319 }
00320
00321 set_svm(i, svm);
00322 }
00323
00324 SG_FREE(problem.x);
00325 SG_FREE(problem.y);
00326 SG_FREE(x_space);
00327 for (int32_t i=0; i<m_num_classes; i++)
00328 {
00329 SG_FREE(model->SV[i]);
00330 model->SV[i]=NULL;
00331 }
00332 svm_destroy_model(model);
00333
00334 if (scatter_type==TEST_RULE2)
00335 compute_norm_wc();
00336
00337 model=NULL;
00338 return true;
00339 }
00340 else
00341 return false;
00342 }
00343
00344 void CScatterSVM::compute_norm_wc()
00345 {
00346 SG_FREE(norm_wc);
00347 norm_wc = SG_MALLOC(float64_t, m_num_svms);
00348 for (int32_t i=0; i<m_num_svms; i++)
00349 norm_wc[i]=0;
00350
00351
00352 for (int c=0; c<m_num_svms; c++)
00353 {
00354 CSVM* svm=m_svms[c];
00355 int32_t num_sv = svm->get_num_support_vectors();
00356
00357 for (int32_t i=0; i<num_sv; i++)
00358 {
00359 int32_t ii=svm->get_support_vector(i);
00360 for (int32_t j=0; j<num_sv; j++)
00361 {
00362 int32_t jj=svm->get_support_vector(j);
00363 norm_wc[c]+=svm->get_alpha(i)*kernel->kernel(ii,jj)*svm->get_alpha(j);
00364 }
00365 }
00366 }
00367
00368 for (int32_t i=0; i<m_num_svms; i++)
00369 norm_wc[i]=CMath::sqrt(norm_wc[i]);
00370
00371 CMath::display_vector(norm_wc, m_num_svms, "norm_wc");
00372 }
00373
00374 CLabels* CScatterSVM::classify_one_vs_rest()
00375 {
00376 CLabels* output=NULL;
00377 if (!kernel)
00378 {
00379 SG_ERROR( "SVM can not proceed without kernel!\n");
00380 return false ;
00381 }
00382
00383 if ( kernel && kernel->get_num_vec_lhs() && kernel->get_num_vec_rhs())
00384 {
00385 int32_t num_vectors=kernel->get_num_vec_rhs();
00386
00387 output=new CLabels(num_vectors);
00388 SG_REF(output);
00389
00390 if (scatter_type == TEST_RULE1)
00391 {
00392 ASSERT(m_num_svms>0);
00393 for (int32_t i=0; i<num_vectors; i++)
00394 output->set_label(i, apply(i));
00395 }
00396 #ifdef USE_SVMLIGHT
00397 else if (scatter_type == NO_BIAS_SVMLIGHT)
00398 {
00399 float64_t* outputs=SG_MALLOC(float64_t, num_vectors*m_num_classes);
00400 CMath::fill_vector(outputs,num_vectors*m_num_classes,0.0);
00401
00402 for (int32_t i=0; i<num_vectors; i++)
00403 {
00404 for (int32_t j=0; j<get_num_support_vectors(); j++)
00405 {
00406 float64_t score=kernel->kernel(get_support_vector(j), i)*get_alpha(j);
00407 int32_t label=labels->get_int_label(get_support_vector(j));
00408 for (int32_t c=0; c<m_num_classes; c++)
00409 {
00410 float64_t s= (label==c) ? (m_num_classes-1) : (-1);
00411 outputs[c+i*m_num_classes]+=s*score;
00412 }
00413 }
00414 }
00415
00416 for (int32_t i=0; i<num_vectors; i++)
00417 {
00418 int32_t winner=0;
00419 float64_t max_out=outputs[i*m_num_classes+0];
00420
00421 for (int32_t j=1; j<m_num_classes; j++)
00422 {
00423 float64_t out=outputs[i*m_num_classes+j];
00424
00425 if (out>max_out)
00426 {
00427 winner=j;
00428 max_out=out;
00429 }
00430 }
00431
00432 output->set_label(i, winner);
00433 }
00434
00435 SG_FREE(outputs);
00436 }
00437 #endif //USE_SVMLIGHT
00438 else
00439 {
00440 ASSERT(m_num_svms>0);
00441 ASSERT(num_vectors==output->get_num_labels());
00442 CLabels** outputs=SG_MALLOC(CLabels*, m_num_svms);
00443
00444 for (int32_t i=0; i<m_num_svms; i++)
00445 {
00446
00447 ASSERT(m_svms[i]);
00448 m_svms[i]->set_kernel(kernel);
00449 m_svms[i]->set_labels(labels);
00450 outputs[i]=m_svms[i]->apply();
00451 }
00452
00453 for (int32_t i=0; i<num_vectors; i++)
00454 {
00455 int32_t winner=0;
00456 float64_t max_out=outputs[0]->get_label(i)/norm_wc[0];
00457
00458 for (int32_t j=1; j<m_num_svms; j++)
00459 {
00460 float64_t out=outputs[j]->get_label(i)/norm_wc[j];
00461
00462 if (out>max_out)
00463 {
00464 winner=j;
00465 max_out=out;
00466 }
00467 }
00468
00469 output->set_label(i, winner);
00470 }
00471
00472 for (int32_t i=0; i<m_num_svms; i++)
00473 SG_UNREF(outputs[i]);
00474
00475 SG_FREE(outputs);
00476 }
00477 }
00478
00479 return output;
00480 }
00481
00482 float64_t CScatterSVM::apply(int32_t num)
00483 {
00484 ASSERT(m_num_svms>0);
00485 float64_t* outputs=SG_MALLOC(float64_t, m_num_svms);
00486 int32_t winner=0;
00487
00488 if (scatter_type == TEST_RULE1)
00489 {
00490 for (int32_t c=0; c<m_num_svms; c++)
00491 outputs[c]=m_svms[c]->get_bias()-rho;
00492
00493 for (int32_t c=0; c<m_num_svms; c++)
00494 {
00495 float64_t v=0;
00496
00497 for (int32_t i=0; i<m_svms[c]->get_num_support_vectors(); i++)
00498 {
00499 float64_t alpha=m_svms[c]->get_alpha(i);
00500 int32_t svidx=m_svms[c]->get_support_vector(i);
00501 v += alpha*kernel->kernel(svidx, num);
00502 }
00503
00504 outputs[c] += v;
00505 for (int32_t j=0; j<m_num_svms; j++)
00506 outputs[j] -= v/m_num_svms;
00507 }
00508
00509 for (int32_t j=0; j<m_num_svms; j++)
00510 outputs[j]/=norm_wcw[j];
00511
00512 float64_t max_out=outputs[0];
00513 for (int32_t j=0; j<m_num_svms; j++)
00514 {
00515 if (outputs[j]>max_out)
00516 {
00517 max_out=outputs[j];
00518 winner=j;
00519 }
00520 }
00521 }
00522 #ifdef USE_SVMLIGHT
00523 else if (scatter_type == NO_BIAS_SVMLIGHT)
00524 {
00525 SG_ERROR("Use classify...\n");
00526 }
00527 #endif //USE_SVMLIGHT
00528 else
00529 {
00530 float64_t max_out=m_svms[0]->apply(num)/norm_wc[0];
00531
00532 for (int32_t i=1; i<m_num_svms; i++)
00533 {
00534 outputs[i]=m_svms[i]->apply(num)/norm_wc[i];
00535 if (outputs[i]>max_out)
00536 {
00537 winner=i;
00538 max_out=outputs[i];
00539 }
00540 }
00541 }
00542
00543 SG_FREE(outputs);
00544 return winner;
00545 }