LoginSignup
5
5

More than 5 years have passed since last update.

@shu_marubo(Shuhei Kishi)

【機械学習】GoでKNN(K近傍法)実装

Last updated at Posted at 2017-08-11

Goで機械学習フルスクラッチシリーズ

この記事は、自身のブログ、Data Science Struggleでも掲載予定。許可なき掲載とかではない。

概略

機械学習アルゴリズムの一つkNN法(k最近傍法)をGoで書く。
Goでも機械学習用のパッケージはあるが、それぞれの機械学習アルゴリズムの書き方に焦点を当てた情報はなかったので少しづつ公開していく。
アルゴリズム理解のための書き下しなので、導入することで見通しの悪くなるような精度向上要素はいれず、多少の問題が生じることは気にせずにシンプルに書いていく。

kNNとは

kNNは教師あり機械学習アルゴリズムの一つで、データ間の距離と多数決を利用して予測対象のラベルを予測する。

アルゴリズム

kNNのアルゴリズムは、予測対象のデータと最も距離の近いk個のラベルと取ってくる。そのk個のラベルで多数決を行い、最も数の多いラベルを予測対象のラベルとする。
このアルゴリズムは別の教師ありアルゴリズムにあるような重みの更新のような概念はない。説明変数とラベルからなるデータを保持し、予測対象のラベルを予測する段階でそのデータとの距離を計算する。
そのため、保持させて置いたデータの量に応じて、予測にかかる時間も長くなるという特徴がある。
その一方で、単純な距離計算と多数決の組み合わせで成り立っているため、別の機械学習アルゴリズムとの組み合わせをしやすく、様々な面で使い勝手が良い。

コード

実際に使用したコードは以下の通り。

package main

import (
    "math"
    "sort"
    "os"
    "encoding/csv"
    "io"
    "strconv"
    "fmt"
)

func main() {
    //データ読み込み
    irisMatrix := [][]string{}
    iris, err := os.Open("iris.csv")
    if err != nil {
        panic(err)
    }
    defer iris.Close()

    reader := csv.NewReader(iris)
    reader.Comma = ','
    reader.LazyQuotes = true
    for {
        record, err := reader.Read()
        if err == io.EOF {
            break
        } else if err != nil {
            panic(err)
        }
        irisMatrix = append(irisMatrix, record)
    }

    //説明変数と被説明変数にデータを分割
    X := [][]float64{}
    Y := []string{}
    for _, data := range irisMatrix {

        //strスライスデータをfloatスライスデータに変換
        temp := []float64{}
        for _, i := range data[:4] {
            parsedValue, err := strconv.ParseFloat(i, 64)
            if err != nil {
                panic(err)
            }
            temp = append(temp, parsedValue)
        }
        //説明変数へ
        X = append(X, temp)

        //被説明変数
        Y = append(Y, data[4])

    }

    //データを訓練データとテストデータに分割
    var (
        trainX [][]float64
        trainY []string
        testX  [][]float64
        testY  []string
    )
    for i, _ := range X {
        if i%2 == 0 {
            trainX = append(trainX, X[i])
            trainY = append(trainY, Y[i])
        } else {
            testX = append(testX, X[i])
            testY = append(testY, Y[i])
        }
    }

    //学習
    knn := KNN{}
    knn.k = 8
    knn.fit(trainX, trainY)
    predicted := knn.predict(testX)

    //正答率確認
    correct := 0
    for i, _ := range predicted {
        if predicted[i] == testY[i] {
            correct += 1
        }
    }
    fmt.Println(correct)
    fmt.Println(len(predicted))
    fmt.Println(float64(correct) / float64(len(predicted)))

}

//二つのスライス間のユークリッド距離を計算
func Dist(source, dest []float64) float64 {
    val := 0.0
    for i, _ := range source {
        val += math.Pow(source[i]-dest[i], 2)
    }
    return math.Sqrt(val)
}

//argument sort作成
type Slice struct {
    sort.Interface
    idx []int
}

func (s Slice) Swap(i, j int) {
    s.Interface.Swap(i, j)
    s.idx[i], s.idx[j] = s.idx[j], s.idx[i]
}

func NewSlice(n sort.Interface) *Slice {
    s := &Slice{Interface: n, idx: make([]int, n.Len())}
    for i := range s.idx {
        s.idx[i] = i
    }
    return s
}

func NewFloat64Slice(n []float64) *Slice { return NewSlice(sort.Float64Slice(n)) }

//mapのソート
type Entry struct {
    name  string
    value int
}
type List []Entry

func (l List) Len() int {
    return len(l)
}

func (l List) Swap(i, j int) {
    l[i], l[j] = l[j], l[i]
}

func (l List) Less(i, j int) bool {
    if l[i].value == l[j].value {
        return l[i].name < l[j].name
    } else {
        return l[i].value > l[j].value
    }
}

//スライス中のアイテムの出現頻度をカウント
func Counter(target []string) map[string]int {
    counter := map[string]int{}
    for _, elem := range target {
        counter[elem] += 1
    }
    return counter
}

type KNN struct {
    k      int
    data   [][]float64
    labels []string
}

func (knn *KNN) fit(X [][]float64, Y []string) {
    //データを読み込む
    knn.data = X
    knn.labels = Y
}

func (knn *KNN) predict(X [][]float64) []string {

    predictedLabel := []string{}
    for _, source := range X {
        var (
            distList   []float64
            nearLabels []string
        )
        //予測対象データと教師データとの距離を計算
        for _, dest := range knn.data {
            distList = append(distList, Dist(source, dest))
        }
        //距離の近い上位k個のインデックスを獲得
        s := NewFloat64Slice(distList)
        sort.Sort(s)
        targetIndex := s.idx[:knn.k]

        //獲得したインデックスのラベルを獲得
        for _, ind := range targetIndex {
            nearLabels = append(nearLabels, knn.labels[ind])
        }

        //ラベルの出現頻度を獲得
        labelFreq := Counter(nearLabels)

        //最も出現回数の多いラベルが予測対象データの予測ラベル
        a := List{}
        for k, v := range labelFreq {
            e := Entry{k, v}
            a = append(a, e)
        }
        sort.Sort(a)
        predictedLabel = append(predictedLabel, a[0].name)
    }
    return predictedLabel

}

順を追って見ていく

実行部で行なっているのはデータの読み込み、訓練、テストデータへの分割などなので後に回し、kNNのコード部分から見ていく。 

type KNN struct {
    k      int
    data   [][]float64
    labels []string
}

KNN構造体に持たせるのは、予測を行うときに幾つの近傍点でラベルを判断するかを指すのがk。dataは説明変数、labelはデータに対応するラベルを格納する。 

func (knn *KNN) fit(X [][]float64, Y []string) {
    //データを読み込む
    knn.data = X
    knn.labels = Y
}

データの読み込みを行う。他の教師ありアルゴリズムではこのfitメソッドで重みの更新などを行うわけだが、KNNは予測フェーズで読み込んでおいたデータとの距離計算を行うので、ここでは読み込みだけを行う。 

func (knn *KNN) predict(X [][]float64) []string {

    predictedLabel := []string{}
    for _, source := range X {
        var (
            distList   []float64
            nearLabels []string
        )
        //予測対象データと教師データとの距離を計算
        for _, dest := range knn.data {
            distList = append(distList, Dist(source, dest))
        }
        //距離の近い上位k個のインデックスを獲得
        s := NewFloat64Slice(distList)
        sort.Sort(s)
        targetIndex := s.idx[:knn.k]

        //獲得したインデックスのラベルを獲得
        for _, ind := range targetIndex {
            nearLabels = append(nearLabels, knn.labels[ind])
        }

        //ラベルの出現頻度を獲得
        labelFreq := Counter(nearLabels)

        //最も出現回数の多いラベルが予測対象データの予測ラベル
        a := List{}
        for k, v := range labelFreq {
            e := Entry{k, v}
            a = append(a, e)
        }
        sort.Sort(a)
        predictedLabel = append(predictedLabel, a[0].name)
    }
    return predictedLabel

}

予測部分。KNNではここが計算のメイン部分になる。
少し長いのでバラして見ていく。 

        //予測対象データと教師データとの距離を計算
        for _, dest := range knn.data {
            distList = append(distList, Dist(source, dest))
        }

予測対象であるデータと読み込んでおいた各データ点との距離を計算してdistListに格納しておく。ここで使用している関数Distは以下の通りのコード。

//二つのスライス間のユークリッド距離を計算
func Dist(source, dest []float64) float64 {
    val := 0.0
    for i, _ := range source {
        val += math.Pow(source[i]-dest[i], 2)
    }
    return math.Sqrt(val)
}

二つのスライスを引数として取り、その距離を返す。今回はユークリッド距離を使用している。 

        //距離の近い上位k個のインデックスを獲得
        s := NewFloat64Slice(distList)
        sort.Sort(s)
        targetIndex := s.idx[:knn.k]

距離の値を昇順にソートして、そのインデックスの上位k個を取ってくる。 

        //獲得したインデックスのラベルを獲得
        for _, ind := range targetIndex {
            nearLabels = append(nearLabels, knn.labels[ind])
        }

先ほど獲得したインデックスのラベルを獲得してくる。
ここまでのことをまとめると、予測対象データと距離の近いk個の教師ありデータのラベルを取ってきたことになる。 

        //ラベルの出現頻度を獲得
        labelFreq := Counter(nearLabels)

        //最も出現回数の多いラベルが予測対象データの予測ラベル
        a := List{}
        for k, v := range labelFreq {
            e := Entry{k, v}
            a = append(a, e)
        }
        sort.Sort(a)
        predictedLabel = append(predictedLabel, a[0].name)

Counter関数では、スライスに含まれている要素の頻度をマップに格納する。それをソートして出現頻度が最も多い要素を返している。
正直、Goでのソートのことがよくわかってないので、もっとうまい書き方があるのかもしれない。 

func main() {
    //データ読み込み
    irisMatrix := [][]string{}
    iris, err := os.Open("iris.csv")
    if err != nil {
        panic(err)
    }
    defer iris.Close()

    reader := csv.NewReader(iris)
    reader.Comma = ','
    reader.LazyQuotes = true
    for {
        record, err := reader.Read()
        if err == io.EOF {
            break
        } else if err != nil {
            panic(err)
        }
        irisMatrix = append(irisMatrix, record)
    }

    //説明変数と被説明変数にデータを分割
    X := [][]float64{}
    Y := []string{}
    for _, data := range irisMatrix {

        //strスライスデータをfloatスライスデータに変換
        temp := []float64{}
        for _, i := range data[:4] {
            parsedValue, err := strconv.ParseFloat(i, 64)
            if err != nil {
                panic(err)
            }
            temp = append(temp, parsedValue)
        }
        //説明変数へ
        X = append(X, temp)

        //被説明変数
        Y = append(Y, data[4])

    }

    //データを訓練データとテストデータに分割
    var (
        trainX [][]float64
        trainY []string
        testX  [][]float64
        testY  []string
    )
    for i, _ := range X {
        if i%2 == 0 {
            trainX = append(trainX, X[i])
            trainY = append(trainY, Y[i])
        } else {
            testX = append(testX, X[i])
            testY = append(testY, Y[i])
        }
    }

    //学習
    knn := KNN{}
    knn.k = 8
    knn.fit(trainX, trainY)
    predicted := knn.predict(testX)

    //正答率確認
    correct := 0
    for i, _ := range predicted {
        if predicted[i] == testY[i] {
            correct += 1
        }
    }
    fmt.Println(correct)
    fmt.Println(len(predicted))
    fmt.Println(float64(correct) / float64(len(predicted)))

}

メイン部。行なっていることはデータの読み込み、説明変数と被説明変数への分割、訓練データとテストデータの分割、予測、正答率の確認である。
少し冗長になるが、ここも分割して追っていく。 

    //データ読み込み
    irisMatrix := [][]string{}
    iris, err := os.Open("iris.csv")
    if err != nil {
        panic(err)
    }
    defer iris.Close()

    reader := csv.NewReader(iris)
    reader.Comma = ','
    reader.LazyQuotes = true
    for {
        record, err := reader.Read()
        if err == io.EOF {
            break
        } else if err != nil {
            panic(err)
        }
        irisMatrix = append(irisMatrix, record)
    }

irisデータを読み込んでいる。行単位で読み込んで行って、irisMatrixにデータを格納していく。 

    //説明変数と被説明変数にデータを分割
    X := [][]float64{}
    Y := []string{}
    for _, data := range irisMatrix {

        //strスライスデータをfloatスライスデータに変換
        temp := []float64{}
        for _, i := range data[:4] {
            parsedValue, err := strconv.ParseFloat(i, 64)
            if err != nil {
                panic(err)
            }
            temp = append(temp, parsedValue)
        }
        //説明変数へ
        X = append(X, temp)

        //被説明変数
        Y = append(Y, data[4])

    }

説明変数はfloatに変換してXに、被説明変数はYに格納する。 

    //データを訓練データとテストデータに分割
    var (
        trainX [][]float64
        trainY []string
        testX  [][]float64
        testY  []string
    )
    for i, _ := range X {
        if i%2 == 0 {
            trainX = append(trainX, X[i])
            trainY = append(trainY, Y[i])
        } else {
            testX = append(testX, X[i])
            testY = append(testY, Y[i])
        }
    }

データを訓練データとテストデータに分割する。irisデータは偶数奇数で分けてもそれぞれのラベルの数がブレないので偶数奇数で分ける。 

    //学習
    knn := KNN{}
    knn.k = 8
    knn.fit(trainX, trainY)
    predicted := knn.predict(testX)

今回は近傍8個の点のラベルで多数決を行うように指定して予測を行なっている。 

    //正答率確認
    correct := 0
    for i, _ := range predicted {
        if predicted[i] == testY[i] {
            correct += 1
        }
    }
    fmt.Println(correct)
    fmt.Println(len(predicted))
    fmt.Println(float64(correct) / float64(len(predicted)))

正答率の確認を行う。今回の正答率は0.9733333333333334となる。

5
5
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
5
5