在go语言中实现K-NN算法代码示例

Go  /  管理员 发布于 1年前   692

KNN算法，即K最近邻算法，是一种基于实例的学习方法，

通过测量不同数据点之间的距离进行分类或回归。

这种算法的主要优点是简单直观，但缺点是计算复杂度高，特别是在处理大规模数据集时。

knn算法应用场景:

KNN算法的应用场景包括图像识别、语音识别、文本分类、

推荐系统、数据挖掘、生物信息学、财务分析等。

knn算法原理：

如果一个样本在特征空间中的k个最相邻的样本中的大多数属于某一个类别，

则该样本也属于这个类别，并具有这个类别上样本的特性。

该方法在确定分类决策上只依据最邻近的一个或者几个样本的类别来决定待分样本所属的类别。

示例代码:

package main
import (
    "container/heap"
    "fmt"
    "math"
)
// 特征数据点
type Point struct {
    X float64
    Y float64
    Label string
}
// 点之间距离的计算
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
}
// 根据KNN规则进行分类
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() {
    // 示例数据
    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"},
        },
    }
    // 创建KNN分类器
    knn := &KNNClassifier{
        K:        3,
        Distance: Distance,
        Points:   trainingData,
    }
    // 测试点
    testPoint := Point{X: 0, Y: 0}
    // 分类
    result := knn.Classify(testPoint)
    fmt.Printf("The test point is classified as: %s\n", result)
}