1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
/*
This is an example illustrating the use of the kkmeans object
from the dlib C++ Library.
The kkmeans object is an implementation of a kernelized k-means clustering
algorithm. It is implemented by using the kcentroid object to represent
each center found by the usual k-means clustering algorithm.
So this object allows you to perform non-linear clustering in the same way
a svm classifier finds non-linear decision surfaces.
This example will make points from 3 classes and perform kernelized k-means
clustering on those points.
The classes are as follows:
- points very close to the origin
- points on the circle of radius 10 around the origin
- points that are on a circle of radius 4 but not around the origin at all
*/
#include <iostream>
#include <vector>
#include "dlib/svm.h"
#include "dlib/rand.h"
using namespace std;
using namespace dlib;
int main()
{
// Here we declare that our samples will be 2 dimensional column vectors.
typedef matrix<double,2,1> sample_type;
// Now we are making a typedef for the kind of kernel we want to use. I picked the
// radial basis kernel because it only has one parameter and generally gives good
// results without much fiddling.
typedef radial_basis_kernel<sample_type> kernel_type;
// Here we declare an instance of the kcentroid object. The first argument to the constructor
// is the kernel we wish to use. The second is a parameter that determines the numerical
// accuracy with which the object will perform part of the learning algorithm. Generally
// smaller values give better results but cause the algorithm to run slower. You just have
// to play with it to decide what balance of speed and accuracy is right for your problem.
// Here we have set it to 0.01.
//
// Also, since we are using the radial basis kernel we have to pick the RBF width parameter.
// Here we have it set to 0.1. But in general, a reasonable way of picking this value is
// to start with some initial guess and to just run all the data through the resulting
// kcentroid. Then print out kc.dictionary_size() to see how many support vectors the
// kcentroid object is using. A good rule of thumb is that you should have somewhere
// in the range of 10-100 support vectors (but this rule isn't carved in stone).
// So if you aren't in that range then you can change the RBF parameter. Making it
// smaller will decrease the dictionary size and making it bigger will increase the
// dictionary size.
//
// So what I often do is I set the kcentroid's second parameter to 0.01 or 0.001. Then
// I find an RBF kernel parameter that gives me the number of support vectors that I
// feel is appropriate for the problem I'm trying to solve. Again, this just comes down
// to playing with it and getting a feel for how things work.
kcentroid<kernel_type> kc(kernel_type(0.1),0.01);
// Now we make an instance of the kkmeans object and tell it to use kcentroid objects
// that are configured with the parameters from the kc object we defined above.
kkmeans<kernel_type> test(kc);
std::vector<sample_type> samples;
std::vector<sample_type> initial_centers;
sample_type m;
dlib::rand::float_1a rnd;
// we will make 50 points from each class
const long num = 50;
// make some samples near the origin
double radius = 0.5;
for (long i = 0; i < num; ++i)
{
double sign = 1;
if (rnd.get_random_double() < 0.5)
sign = -1;
m(0) = 2*radius*rnd.get_random_double()-radius;
m(1) = sign*sqrt(radius*radius - m(0)*m(0));
// add this sample to our set of samples we will run k-means
samples.push_back(m);
}
// make some samples in a circle around the origin but far away
radius = 10.0;
for (long i = 0; i < num; ++i)
{
double sign = 1;
if (rnd.get_random_double() < 0.5)
sign = -1;
m(0) = 2*radius*rnd.get_random_double()-radius;
m(1) = sign*sqrt(radius*radius - m(0)*m(0));
// add this sample to our set of samples we will run k-means
samples.push_back(m);
}
// make some samples in a circle around the point (25,25)
radius = 4.0;
for (long i = 0; i < num; ++i)
{
double sign = 1;
if (rnd.get_random_double() < 0.5)
sign = -1;
m(0) = 2*radius*rnd.get_random_double()-radius;
m(1) = sign*sqrt(radius*radius - m(0)*m(0));
// translate this point away from the origin
m(0) += 25;
m(1) += 25;
// add this sample to our set of samples we will run k-means
samples.push_back(m);
}
// tell the kkmeans object we made that we want to run k-means with k set to 3.
// (i.e. we want 3 clusters)
test.set_number_of_centers(3);
// You need to pick some initial centers for the k-means algorithm. So here
// we will use the dlib::pick_initial_centers() function which tries to find
// n points that are far apart (basically).
pick_initial_centers(3, initial_centers, samples, test.get_kernel());
// now run the k-means algorithm on our set of samples.
test.train(samples,initial_centers);
// now loop over all our samples and print out their predicted class. In this example
// all points are correctly identified.
for (unsigned long i = 0; i < samples.size()/3; ++i)
{
cout << test(samples[i]) << " ";
cout << test(samples[i+num]) << " ";
cout << test(samples[i+2*num]) << "\n";
}
}