-
Notifications
You must be signed in to change notification settings - Fork 0
/
knn.go
134 lines (120 loc) · 3.77 KB
/
knn.go
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
package knn
import (
"errors"
"math"
"sort"
)
// Classifier : kNN を使った分類器
type Classifier struct {
k int `json:"k"` // 調べる近傍点の個数
numLabels int `json:"num_labels"` // ラベルの個数(0<=ラベル番号<numLabels)
data [][]float32 `json:"data"` // データ
labels []int `json:"labels"` // データごとのラベル
numDataElm int `json:"num_data_elm"` // データの要素の個数 (!=データの個数)
distances []distance
}
type distance struct {
idx int
distance float32
}
func (cls *Classifier) Len() int {
return len(cls.distances)
}
func (cls *Classifier) Less(i, j int) bool {
return cls.distances[i].distance < cls.distances[j].distance
}
func (cls *Classifier) Swap(i, j int) {
cls.distances[i], cls.distances[j] = cls.distances[j], cls.distances[i]
}
// New : 分類器の作成。
// Params:
// k --- 調べる近傍点の個数
// numDataElm --- データの要素の個数 (!=データの個数)
// numLabels --- ラベルの個数(0<=ラベル番号<numLabels)
func New(k, numDataElm, numLabels int) (r *Classifier) {
return &Classifier{
k: k,
numLabels: numLabels,
data: [][]float32{},
labels: []int{},
numDataElm: numDataElm,
}
}
// Add : データとラベルの追加
func (cls *Classifier) Add(data [][]float32, labels []int) (err error) {
// num : 処理する個数。data と labels のそれぞれの個数が異なる時はエラー。
num := len(data)
if num != len(labels) {
err = errors.New("knn.Classifier.Add: size of data and labels are different")
return
}
for i := 0; i < num; i++ {
if len(data[i]) != cls.numDataElm {
// データの要素の個数と合わないものはエラー
err = errors.New("knn.Classifier.Add: len(data[i]) != cls.numDataElem")
break
}
if labels[i] >= cls.numLabels {
// ラベル番号の上限を超えるものはエラー
err = errors.New("knn.Classifier.Add: labels[i] >= cls.numLabels")
break
}
cls.data = append(cls.data, data[i])
cls.labels = append(cls.labels, labels[i])
}
// fmt.Println(cls.data)
// fmt.Println(cls.labels)
return
}
// Predict : ラベルの予測
func (cls *Classifier) Predict(data []float32) (label int) {
// 全データとの距離を計算
cls.calcDistances(data)
// 距離を昇順でソート
sort.Sort(cls)
//fmt.Println("cls.distances =", cls.distances)
// 最近傍点との距離が 0 なら最近傍点のラベルを回答とする。
if cls.distances[0].distance == float32(0) {
idx := cls.distances[0].idx
label = cls.labels[idx]
return
}
// k 個の近傍点のラベルの個数を集計
labelCounts := make([]int, cls.numLabels)
for i := 0; i < cls.k; i++ {
idx := cls.distances[i].idx
lbl := cls.labels[idx]
labelCounts[lbl] = labelCounts[lbl] + 1
}
//fmt.Println("labelCounts =", labelCounts)
// 最も多かったラベルを決定
maxCount := 0
for i, count := range labelCounts {
if count > maxCount {
label = i
maxCount = count
}
}
return
}
func (cls *Classifier) calcDistances(xx []float32) (err error) {
if len(xx) != cls.numDataElm {
err = errors.New("knn.Classifier.calcDistances: len(xx) != cls.numDataElm")
return
}
cls.distances = make([]distance, len(cls.data))
for i, xx2 := range cls.data {
cls.distances[i] = distance{idx: i, distance: calcDistance(xx, xx2)}
}
return
}
// calcDistance : calculate L2
func calcDistance(xx, xx2 []float32) (r float32) {
s := float64(0)
for i := 0; i < len(xx); i++ {
delta := float64(xx[i] - xx2[i])
s += delta * delta
}
r = float32(math.Sqrt(s))
return
}