knnClassification.cpp 5.2 KB
Newer Older
1
2
3
4
5
6
7
8
//
//  knnClassification.cpp
//  RapidLib
//
//  Created by mzed on 05/09/2016.
//  Copyright © 2016 Goldsmiths. All rights reserved.
//

James Frink's avatar
James Frink committed
9
#include <math.h>
10
#include <utility>
mzed's avatar
mzed committed
11
12
#include <map>
#include <vector>
mzed's avatar
mzed committed
13
#include <algorithm>
14
#include "knnClassification.h"
mzed's avatar
mzed committed
15
#ifdef EMSCRIPTEN
16
#include "emscripten/knnEmbindings.h"
mzed's avatar
mzed committed
17
#endif
18

19
template<typename T>
20
knnClassification<T>::knnClassification(const int &num_inputs, const std::vector<int> &which_inputs, const std::vector<trainingExampleTemplate<T> > &_neighbours, const int k)
21
22
23
: numInputs(num_inputs),
whichInputs(which_inputs),
neighbours(_neighbours),
mzed's avatar
mzed committed
24
25
desiredK(k),
currentK(k)
mzed's avatar
mzed committed
26
{
mzed's avatar
mzed committed
27
    nearestNeighbours = new std::pair<int, T>[currentK];
28
29
}

30
31
template<typename T>
knnClassification<T>::~knnClassification() {
32
    delete[] nearestNeighbours;
33
34
}

35
36
template<typename T>
void knnClassification<T>::reset() {
mzed's avatar
mzed committed
37
38
39
    //TODO: implement this
}

40
41
template<typename T>
int knnClassification<T>::getNumInputs() const {
mzed's avatar
mzed committed
42
43
44
    return numInputs;
}

45
46
template<typename T>
std::vector<int> knnClassification<T>::getWhichInputs() const {
mzed's avatar
mzed committed
47
48
49
    return whichInputs;
}

50
51
template<typename T>
int knnClassification<T>::getK() const {
mzed's avatar
mzed committed
52
53
54
    return currentK;
}

55
56
template<typename T>
inline void knnClassification<T>::updateK() {
mzed's avatar
mzed committed
57
58
59
    if (currentK != desiredK) {
        currentK = std::min(desiredK, (int) neighbours.size());
    }
mzed's avatar
mzed committed
60
61
}

62
63
template<typename T>
void knnClassification<T>::setK(int newK) {
mzed's avatar
mzed committed
64
65
    desiredK = newK;
    updateK();
mzed's avatar
mzed committed
66
67
}

68
69
70
71
template<typename T>
void knnClassification<T>::addNeighbour(const int &classNum, const std::vector<T> &features) {
    std::vector<T> classVec;
    classVec.push_back(T(classNum));
72
    trainingExampleTemplate<T>  newNeighbour = {features, classVec};
73
    neighbours.push_back(newNeighbour);
mzed's avatar
mzed committed
74
    updateK();
75
76
};

77
template<typename T>
78
void knnClassification<T>::train(const std::vector<trainingExampleTemplate<T> > &trainingSet) { //FIXME: Does numInputs need to be reset here? -MZ
79
80
    neighbours.clear();
    neighbours = trainingSet;
mzed's avatar
mzed committed
81
    updateK();
mzed's avatar
mzed committed
82
83
};

84
template<typename T>
mzed's avatar
mzed committed
85
T knnClassification<T>::run(const std::vector<T> &inputVector) {
mzed's avatar
mzed committed
86
    for (int i = 0; i < currentK; ++i) {
87
88
        nearestNeighbours[i] = {0, 0.};
    };
mzed's avatar
mzed committed
89
    std::pair<int, T> farthestNN = {0, 0.};
90
    
91
    std::vector<T> pattern;
92
93
94
95
96
97
    for (int h = 0; h < numInputs; h++) {
        pattern.push_back(inputVector[whichInputs[h]]);
    }
    
    //Find k nearest neighbours
    int index = 0;
98
    for (typename std::vector<trainingExampleTemplate<T> >::iterator it = neighbours.begin(); it != neighbours.end(); ++it) {
99
        //find Euclidian distance for this neighbor
mzed's avatar
mzed committed
100
        T euclidianDistance = 0;
101
        for(int j = 0; j < numInputs ; ++j){
102
            euclidianDistance += pow((pattern[j] - it->input[j]), 2);
103
104
        }
        euclidianDistance = sqrt(euclidianDistance);
mzed's avatar
mzed committed
105
        if (index < currentK) {
106
107
108
109
110
111
112
113
114
            //save the first k neighbours
            nearestNeighbours[index] = {index, euclidianDistance};
            if (euclidianDistance > farthestNN.second) {
                farthestNN = {index, euclidianDistance};
            }
        } else if (euclidianDistance < farthestNN.second) {
            //replace farthest, if new neighbour is closer
            nearestNeighbours[farthestNN.first] = {index, euclidianDistance};
            int currentFarthest = 0;
mzed's avatar
mzed committed
115
            T currentFarthestDistance = 0.;
mzed's avatar
mzed committed
116
            for (int n = 0; n < currentK; n++) {
117
118
119
120
121
122
123
124
125
126
127
128
129
                if (nearestNeighbours[n].second > currentFarthestDistance) {
                    currentFarthest = n;
                    currentFarthestDistance = nearestNeighbours[n].second;
                }
            }
            farthestNN = {currentFarthest, currentFarthestDistance};
        }
        ++index;
    }
    
    //majority vote on nearest neighbours
    std::map<int, int> classVoteMap;
    typedef std::pair<int, int> classVotePair;
mzed's avatar
mzed committed
130
    for (int i = 0; i < currentK; ++i){
James Frink's avatar
James Frink committed
131
        int classNum = (int) round(neighbours[nearestNeighbours[i].first].output[0]);
132
133
134
135
136
137
        if ( classVoteMap.find(classNum) == classVoteMap.end() ) {
            classVoteMap.insert(classVotePair(classNum, 1));
        } else {
            classVoteMap[classNum]++;
        }
    }
mzed's avatar
mzed committed
138
    T foundClass = 0;
139
140
141
142
143
144
145
146
147
148
149
    int mostVotes = 0;
    std::map<int, int>::iterator p;
    for(p = classVoteMap.begin(); p != classVoteMap.end(); ++p)
    {
        if (p->second > mostVotes) {
            mostVotes = p->second;
            foundClass = p->first;
        }
    }
    return foundClass;
}
150

151
#ifndef EMSCRIPTEN
152
153
template<typename T>
void knnClassification<T>::getJSONDescription(Json::Value &jsonModelDescription) {
mzed's avatar
mzed committed
154
    jsonModelDescription["modelType"] = "kNN Classificiation";
mzed's avatar
mzed committed
155
    jsonModelDescription["numInputs"] = numInputs;
mzed's avatar
mzed committed
156
    jsonModelDescription["whichInputs"] = this->vector2json(whichInputs);
mzed's avatar
mzed committed
157
    jsonModelDescription["k"] = desiredK;
mzed's avatar
mzed committed
158
    Json::Value examples;
159
    for (typename std::vector<trainingExampleTemplate<T> >::iterator it = neighbours.begin(); it != neighbours.end(); ++it) {
mzed's avatar
mzed committed
160
161
        Json::Value oneExample;
        oneExample["class"] = it->output[0];
mzed's avatar
mzed committed
162
        oneExample["features"] = this->vector2json(it->input);
mzed's avatar
mzed committed
163
164
165
        examples.append(oneExample);
    }
    jsonModelDescription["examples"] = examples;
166
167
}
#endif
168
169
170
171

//explicit instantiation
template class knnClassification<double>;
template class knnClassification<float>;