svm_classifier.cpp
Go to the documentation of this file.
1 // Copyright (c) 2012, 2019 Scott Niekum, Joshua Whitley
2 // All rights reserved.
3 //
4 // Software License Agreement (BSD License 2.0)
5 //
6 // Redistribution and use in source and binary forms, with or without
7 // modification, are permitted provided that the following conditions
8 // are met:
9 //
10 // * Redistributions of source code must retain the above copyright
11 // notice, this list of conditions and the following disclaimer.
12 // * Redistributions in binary form must reproduce the above
13 // copyright notice, this list of conditions and the following
14 // disclaimer in the documentation and/or other materials provided
15 // with the distribution.
16 // * Neither the name of {copyright_holder} nor the names of its
17 // contributors may be used to endorse or promote products derived
18 // from this software without specific prior written permission.
19 //
20 // THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
21 // "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
22 // LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
23 // FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
24 // COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
25 // INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING,
26 // BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
27 // LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
28 // CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
29 // LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN
30 // ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
31 // POSSIBILITY OF SUCH DAMAGE.
32 
35 #include <cmath>
36 #include <string>
37 #include <vector>
38 #include <algorithm>
39 
41 
42 namespace ml_classifiers
43 {
44 
45 SVMClassifier::SVMClassifier() {}
46 
47 SVMClassifier::~SVMClassifier() {}
48 
49 void SVMClassifier::save(const std::string filename) {}
50 
51 bool SVMClassifier::load(const std::string filename)
52 {
53  return false;
54 }
55 
56 void SVMClassifier::addTrainingPoint(std::string target_class, const std::vector<double> point)
57 {
58  class_data[target_class].push_back(point);
59 }
60 
61 void SVMClassifier::train()
62 {
63  if (class_data.size() == 0) {
64  printf("SVMClassifier::train() -- No training data available! Doing nothing.\n");
65  return;
66  }
67 
68  int n_classes = class_data.size();
69 
70  // Count the training data
71  int n_data = 0;
72  int dims = class_data.begin()->second[0].size();
73 
74  for (ClassMap::iterator iter = class_data.begin(); iter != class_data.end(); iter++) {
75  CPointList cpl = iter->second;
76 
77  if (cpl.size() == 1) {
78  // There's a bug in libSVM for classes with only 1 data point,
79  // so we will duplicate them later
80  n_data += 2;
81  } else {
82  n_data += cpl.size();
83  }
84  }
85 
86  // Allocate space for data in an svm_problem structure
87  svm_data.l = n_data;
88  svm_data.y = new double[n_data];
89  svm_data.x = new svm_node *[n_data];
90 
91  for (int i = 0; i < n_data; i++) {
92  svm_data.x[i] = new svm_node[dims + 1];
93  }
94 
95  // Create maps between string labels and int labels
96  label_str_to_int.clear();
97  label_int_to_str.clear();
98  int label_n = 0;
99 
100  for (ClassMap::iterator iter = class_data.begin(); iter != class_data.end(); iter++) {
101  std::string cname = iter->first;
102  label_str_to_int[cname] = label_n;
103  label_int_to_str[label_n] = cname;
104  // cout << "MAP: " << label_n << " " << cname << " Size: " << iter->second.size() << endl;
105  ++label_n;
106  }
107 
108  // Find the range of the data in each dim and calc the scaling factors to scale from 0 to 1
109  scaling_factors = new double *[dims];
110 
111  for (int i = 0; i < dims; i++) {
112  scaling_factors[i] = new double[2];
113  }
114 
115  // Scale each dimension separately
116  for (int j = 0; j < dims; j++) {
117  // First find the min, max, and scaling factor
118  double minval = INFINITY;
119  double maxval = -INFINITY;
120 
121  for (ClassMap::iterator iter = class_data.begin(); iter != class_data.end(); iter++) {
122  CPointList cpl = iter->second;
123 
124  for (size_t i = 0; i < cpl.size(); i++) {
125  if (cpl[i][j] < minval) {
126  minval = cpl[i][j];
127  }
128  if (cpl[i][j] > maxval) {
129  maxval = cpl[i][j];
130  }
131  }
132  }
133 
134  double factor = maxval - minval;
135  double offset = minval;
136 
137  // Do the scaling and save the scaling factor and offset
138  for (ClassMap::iterator iter = class_data.begin(); iter != class_data.end(); iter++) {
139  for (size_t i = 0; i < iter->second.size(); i++) {
140  iter->second[i][j] = (iter->second[i][j] - offset) / factor;
141  }
142  }
143 
144  scaling_factors[j][0] = offset;
145  scaling_factors[j][1] = factor;
146  }
147 
148  // Put the training data into the svm_problem
149  int n = 0;
150  for (ClassMap::iterator iter = class_data.begin(); iter != class_data.end(); iter++) {
151  std::string cname = iter->first;
152  CPointList cpl = iter->second;
153 
154  // Account for bug in libSVM with classes with only 1 data point by duplicating it.
155  if (cpl.size() == 1) {
156  svm_data.y[n] = label_str_to_int[cname];
157  svm_data.y[n + 1] = label_str_to_int[cname];
158 
159  for (int j = 0; j < dims; j++) {
160  svm_data.x[n][j].index = j;
161  svm_data.x[n][j].value = cpl[0][j] + 0.001;
162  svm_data.x[n + 1][j].index = j;
163  svm_data.x[n + 1][j].value = cpl[0][j] + 0.001;
164  }
165 
166  svm_data.x[n][dims].index = -1;
167  svm_data.x[n + 1][dims].index = -1;
168  n = n + 2;
169  } else {
170  for (size_t i = 0; i < cpl.size(); i++) {
171  svm_data.y[n] = label_str_to_int[cname];
172 
173  for (int j = 0; j < dims; j++) {
174  svm_data.x[n][j].index = j;
175  svm_data.x[n][j].value = cpl[i][j];
176  }
177 
178  svm_data.x[n][dims].index = -1;
179  n = n + 1;
180  }
181  }
182  }
183 
184  // Set the training params
185  svm_parameter params;
186  params.svm_type = C_SVC;
187  params.kernel_type = RBF;
188  params.cache_size = 100.0;
189  params.gamma = 1.0;
190  params.C = 1.0;
191  params.eps = 0.001;
192  params.shrinking = 1;
193  params.probability = 0;
194  params.degree = 0;
195  params.nr_weight = 0;
196  // params.weight_label =
197  // params.weight =
198 
199  const char * err_str = svm_check_parameter(&svm_data, &params);
200  if (err_str) {
201  printf("SVMClassifier::train() -- Bad SVM parameters!\n");
202  printf("%s\n", err_str);
203  return;
204  }
205 
206  // Grid Search for best C and gamma params
207  int n_folds = std::min(10, n_data); // Make sure there at least as many points as folds
208  double * resp = new double[n_data];
209  double best_accy = 0.0;
210  double best_g = 0.0;
211  double best_c = 0.0;
212 
213  // First, do a coarse search
214  for (double c = -5.0; c <= 15.0; c += 2.0) {
215  for (double g = 3.0; g >= -15.0; g -= 2.0) {
216  params.gamma = pow(2, g);
217  params.C = pow(2, c);
218 
219  svm_cross_validation(&svm_data, &params, n_folds, resp);
220 
221  // Figure out the accuracy using these params
222  int correct = 0;
223 
224  for (int i = 0; i < n_data; i++) {
225  if (resp[i] == svm_data.y[i]) {
226  ++correct;
227  }
228 
229  double accy = static_cast<double>(correct) / static_cast<double>(n_data);
230 
231  if (accy > best_accy) {
232  best_accy = accy;
233  best_g = params.gamma;
234  best_c = params.C;
235  }
236  }
237  }
238  }
239 
240  // Now do a finer grid search based on coarse results
241  double start_c = best_c - 1.0;
242  double end_c = best_c + 1.0;
243  double start_g = best_g + 1.0;
244  double end_g = best_g - 1.0;
245 
246  for (double c = start_c; c <= end_c; c += 0.1) {
247  for (double g = start_g; g >= end_g; g -= 0.1) {
248  params.gamma = pow(2, g);
249  params.C = pow(2, c);
250  svm_cross_validation(&svm_data, &params, n_folds, resp);
251 
252  // Figure out the accuracy using these params
253  int correct = 0;
254 
255  for (int i = 0; i < n_data; i++) {
256  if (resp[i] == svm_data.y[i]) {
257  ++correct;
258  }
259 
260  double accy = static_cast<double>(correct) / static_cast<double>(n_data);
261 
262  if (accy > best_accy) {
263  best_accy = accy;
264  best_g = params.gamma;
265  best_c = params.C;
266  }
267  }
268  }
269  }
270 
271  // Set params to best found in grid search
272  params.gamma = best_g;
273  params.C = best_c;
274 
275  printf(
276  "BEST PARAMS ncl: %i c: %f g: %f accy: %f \n\n",
277  n_classes,
278  best_c,
279  best_g,
280  best_accy);
281 
282  // Train the SVM
283  trained_model = svm_train(&svm_data, &params);
284 }
285 
286 void SVMClassifier::clear()
287 {
288  class_data.clear();
289  label_str_to_int.clear();
290  label_int_to_str.clear();
291  trained_model = NULL; // Actually, this should get freed
292  scaling_factors = NULL;
293 }
294 
295 std::string SVMClassifier::classifyPoint(const std::vector<double> point)
296 {
297  // Copy the point to be classified into an svm_node
298  int dims = point.size();
299  svm_node * test_pt = new svm_node[dims + 1];
300 
301  for (int i = 0; i < dims; i++) {
302  test_pt[i].index = i;
303  // Scale the point using the training scaling values
304  test_pt[i].value = (point[i] - scaling_factors[i][0]) / scaling_factors[i][1];
305  }
306 
307  test_pt[dims].index = -1;
308 
309  // Classify the point using the currently trained SVM
310  int label_n = svm_predict(trained_model, test_pt);
311  return label_int_to_str[label_n];
312 }
313 } // namespace ml_classifiers
const char * svm_check_parameter(const svm_problem *prob, const svm_parameter *param)
Definition: svm.cpp:3029
def svm_train(arg1, arg2=None, arg3=None)
Definition: svmutil.py:77
double value
Definition: svm.h:15
int nr_weight
Definition: svm.h:40
void svm_cross_validation(const svm_problem *prob, const svm_parameter *param, int nr_fold, double *target)
Definition: svm.cpp:2352
def svm_predict(y, x, m, options="")
Definition: svmutil.py:164
double cache_size
Definition: svm.h:37
double eps
Definition: svm.h:38
int shrinking
Definition: svm.h:45
Definition: svm.h:26
int index
Definition: svm.h:14
int probability
Definition: svm.h:46
int degree
Definition: svm.h:32
Definition: svm.h:25
Definition: svm.h:12
c
Definition: easy.py:61
double gamma
Definition: svm.h:33
double C
Definition: svm.h:39
int svm_type
Definition: svm.h:30
#define PLUGINLIB_EXPORT_CLASS(class_type, base_class_type)
#define min(x, y)
Definition: libsvmread.c:18
g
Definition: easy.py:61
int kernel_type
Definition: svm.h:31
std::vector< CPoint > CPointList


ml_classifiers
Author(s): Scott Niekum , Joshua Whitley
autogenerated on Tue May 14 2019 02:28:35