1 // The contents of this file are in the public domain. See LICENSE_FOR_EXAMPLE_PROGRAMS.txt
2 /*
3 This is an example illustrating the use of the kkmeans object
4 and spectral_cluster() routine from the dlib C++ Library.
5
6 The kkmeans object is an implementation of a kernelized k-means clustering
7 algorithm. It is implemented by using the kcentroid object to represent
8 each center found by the usual k-means clustering algorithm.
9
10 So this object allows you to perform non-linear clustering in the same way
11 a svm classifier finds non-linear decision surfaces.
12
13 This example will make points from 3 classes and perform kernelized k-means
14 clustering on those points. It will also do the same thing using spectral
15 clustering.
16
17 The classes are as follows:
18 - points very close to the origin
19 - points on the circle of radius 10 around the origin
20 - points that are on a circle of radius 4 but not around the origin at all
21 */
22
23 #include <iostream>
24 #include <vector>
25
26 #include <dlib/clustering.h>
27 #include <dlib/rand.h>
28
29 using namespace std;
30 using namespace dlib;
31
main()32 int main()
33 {
34 // Here we declare that our samples will be 2 dimensional column vectors.
35 // (Note that if you don't know the dimensionality of your vectors at compile time
36 // you can change the 2 to a 0 and then set the size at runtime)
37 typedef matrix<double,2,1> sample_type;
38
39 // Now we are making a typedef for the kind of kernel we want to use. I picked the
40 // radial basis kernel because it only has one parameter and generally gives good
41 // results without much fiddling.
42 typedef radial_basis_kernel<sample_type> kernel_type;
43
44
45 // Here we declare an instance of the kcentroid object. It is the object used to
46 // represent each of the centers used for clustering. The kcentroid has 3 parameters
47 // you need to set. The first argument to the constructor is the kernel we wish to
48 // use. The second is a parameter that determines the numerical accuracy with which
49 // the object will perform part of the learning algorithm. Generally, smaller values
50 // give better results but cause the algorithm to attempt to use more dictionary vectors
51 // (and thus run slower and use more memory). The third argument, however, is the
52 // maximum number of dictionary vectors a kcentroid is allowed to use. So you can use
53 // it to control the runtime complexity.
54 kcentroid<kernel_type> kc(kernel_type(0.1),0.01, 8);
55
56 // Now we make an instance of the kkmeans object and tell it to use kcentroid objects
57 // that are configured with the parameters from the kc object we defined above.
58 kkmeans<kernel_type> test(kc);
59
60 std::vector<sample_type> samples;
61 std::vector<sample_type> initial_centers;
62
63 sample_type m;
64
65 dlib::rand rnd;
66
67 // we will make 50 points from each class
68 const long num = 50;
69
70 // make some samples near the origin
71 double radius = 0.5;
72 for (long i = 0; i < num; ++i)
73 {
74 double sign = 1;
75 if (rnd.get_random_double() < 0.5)
76 sign = -1;
77 m(0) = 2*radius*rnd.get_random_double()-radius;
78 m(1) = sign*sqrt(radius*radius - m(0)*m(0));
79
80 // add this sample to our set of samples we will run k-means
81 samples.push_back(m);
82 }
83
84 // make some samples in a circle around the origin but far away
85 radius = 10.0;
86 for (long i = 0; i < num; ++i)
87 {
88 double sign = 1;
89 if (rnd.get_random_double() < 0.5)
90 sign = -1;
91 m(0) = 2*radius*rnd.get_random_double()-radius;
92 m(1) = sign*sqrt(radius*radius - m(0)*m(0));
93
94 // add this sample to our set of samples we will run k-means
95 samples.push_back(m);
96 }
97
98 // make some samples in a circle around the point (25,25)
99 radius = 4.0;
100 for (long i = 0; i < num; ++i)
101 {
102 double sign = 1;
103 if (rnd.get_random_double() < 0.5)
104 sign = -1;
105 m(0) = 2*radius*rnd.get_random_double()-radius;
106 m(1) = sign*sqrt(radius*radius - m(0)*m(0));
107
108 // translate this point away from the origin
109 m(0) += 25;
110 m(1) += 25;
111
112 // add this sample to our set of samples we will run k-means
113 samples.push_back(m);
114 }
115
116 // tell the kkmeans object we made that we want to run k-means with k set to 3.
117 // (i.e. we want 3 clusters)
118 test.set_number_of_centers(3);
119
120 // You need to pick some initial centers for the k-means algorithm. So here
121 // we will use the dlib::pick_initial_centers() function which tries to find
122 // n points that are far apart (basically).
123 pick_initial_centers(3, initial_centers, samples, test.get_kernel());
124
125 // now run the k-means algorithm on our set of samples.
126 test.train(samples,initial_centers);
127
128 // now loop over all our samples and print out their predicted class. In this example
129 // all points are correctly identified.
130 for (unsigned long i = 0; i < samples.size()/3; ++i)
131 {
132 cout << test(samples[i]) << " ";
133 cout << test(samples[i+num]) << " ";
134 cout << test(samples[i+2*num]) << "\n";
135 }
136
137 // Now print out how many dictionary vectors each center used. Note that
138 // the maximum number of 8 was reached. If you went back to the kcentroid
139 // constructor and changed the 8 to some bigger number you would see that these
140 // numbers would go up. However, 8 is all we need to correctly cluster this dataset.
141 cout << "num dictionary vectors for center 0: " << test.get_kcentroid(0).dictionary_size() << endl;
142 cout << "num dictionary vectors for center 1: " << test.get_kcentroid(1).dictionary_size() << endl;
143 cout << "num dictionary vectors for center 2: " << test.get_kcentroid(2).dictionary_size() << endl;
144
145
146 // Finally, we can also solve the same kind of non-linear clustering problem with
147 // spectral_cluster(). The output is a vector that indicates which cluster each sample
148 // belongs to. Just like with kkmeans, it assigns each point to the correct cluster.
149 std::vector<unsigned long> assignments = spectral_cluster(kernel_type(0.1), samples, 3);
150 cout << mat(assignments) << endl;
151
152 }
153
154
155