在go語言中實(shí)現(xiàn)K-NN算法代碼示例

Go  /  管理員 發(fā)布于 9個(gè)月前   507

KNN算法，即K最近鄰算法，是一種基于實(shí)例的學(xué)習(xí)方法，

通過測量不同數(shù)據(jù)點(diǎn)之間的距離進(jìn)行分類或回歸。

這種算法的主要優(yōu)點(diǎn)是簡單直觀，但缺點(diǎn)是計(jì)算復(fù)雜度高，特別是在處理大規(guī)模數(shù)據(jù)集時(shí)。

knn算法應(yīng)用場景:

KNN算法的應(yīng)用場景包括圖像識(shí)別、語音識(shí)別、文本分類、

推薦系統(tǒng)、數(shù)據(jù)挖掘、生物信息學(xué)、財(cái)務(wù)分析等。

knn算法原理：

如果一個(gè)樣本在特征空間中的k個(gè)最相鄰的樣本中的大多數(shù)屬于某一個(gè)類別，

則該樣本也屬于這個(gè)類別，并具有這個(gè)類別上樣本的特性。

該方法在確定分類決策上只依據(jù)最鄰近的一個(gè)或者幾個(gè)樣本的類別來決定待分樣本所屬的類別。

示例代碼:

package main
import (
    "container/heap"
    "fmt"
    "math"
)
// 特征數(shù)據(jù)點(diǎn)
type Point struct {
    X float64
    Y float64
    Label string
}
// 點(diǎn)之間距離的計(jì)算
func Distance(p1, p2 Point) float64 {
    return math.Sqrt(math.Pow(p1.X-p2.X, 2) + math.Pow(p1.Y-p2.Y, 2))
}
// 元素的索引
type Element struct {
    Point
    Index int
}
// 元素集合，按距離排序
type PriorityQueue []Element
func (pq PriorityQueue) Len() int { return len(pq) }
func (pq PriorityQueue) Less(i, j int) bool {
    return pq[i].Distance < pq[j].Distance
}
func (pq PriorityQueue) Swap(i, j int) {
    pq[i], pq[j] = pq[j], pq[i]
}
func (pq *PriorityQueue) Push(x interface{}) {
    *pq = append(*pq, x.(Element))
}
func (pq *PriorityQueue) Pop() interface{} {
    old := *pq
    n := len(old)
    x := old[n-1]
    *pq = old[0 : n-1]
    return x
}
// KNN 分類器
type KNNClassifier struct {
    K        int
    Distance func(Point, Point) float64
    Points   map[string][]Point
}
// 根據(jù)KNN規(guī)則進(jìn)行分類
func (knn *KNNClassifier) Classify(point Point) string {
    pq := make(PriorityQueue, knn.K)
    i := 0
    for label, points := range knn.Points {
        for _, p := range points {
            d := knn.Distance(point, p)
            heap.Push(&pq, Element{Point: p, Index: i, Distance: d})
            i++
        }
    }
    labels := make(map[string]int)
    for pq.Len() > 0 {
        item := heap.Pop(&pq).(Element)
        labels[knn.Points[item.Label][item.Index].Label]++
    }
    var maxLabel string
    var maxCount int
    for label, count := range labels {
        if count > maxCount {
            maxLabel = label
            maxCount = count
        }
    }
    return maxLabel
}
func main() {
    // 示例數(shù)據(jù)
    trainingData := map[string][]Point{
        "circle": {
            {X: 1, Y: 1, Label: "circle"},
            {X: 2, Y: 2, Label: "circle"},
            {X: -1, Y: -1, Label: "circle"},
            {X: -2, Y: -2, Label: "circle"},
        },
        "triangle": {
            {X: 3, Y: 3, Label: "triangle"},
            {X: 4, Y: 4, Label: "triangle"},
            {X: -3, Y: -3, Label: "triangle"},
            {X: -4, Y: -4, Label: "triangle"},
        },
    }
    // 創(chuàng)建KNN分類器
    knn := &KNNClassifier{
        K:        3,
        Distance: Distance,
        Points:   trainingData,
    }
    // 測試點(diǎn)
    testPoint := Point{X: 0, Y: 0}
    // 分類
    result := knn.Classify(testPoint)
    fmt.Printf("The test point is classified as: %s\n", result)
}