如何使用Golang基本数据结构与算法k-means聚类算法

本篇内容介绍了"如何使用Golang基本数据结构与算法k-means聚类算法"的有关知识，在实际案例的操作过程中，不少人都会遇到这样的困境，接下来就让小编带领大家学习一下如何处理这些情况吧！希望大家仔细阅读，能够学有所成！

k-means聚类算法

聚类就是在输入为多个数据时， 将"相似"的数据分为一组的操作。 k-means算法是聚类算法中的一种。 首先随机选择k个点作为簇的中心点, 然后重复执行"将数据分到相应的簇中"和 "将中心点移到重心的位置"这两个操作， 直到中心点不再发生变化为止。 k-means算法中，随着操作的不断重复， 中心点的位置必定会在某处收敛， 这一点已经在数学层面上得到证明。 摘自 <<我的第一本算法书>> 【日】石田保辉；宫崎修一

场景

• 某地突然爆发新冠疫情, 现防疫急需根据病例分布, 查找可能的病源地

• 首先将病例分布的坐标, 录入系统

• 然后根据k-means算法, 按k从1到3, 分别进行聚类

• 聚类的中心点, 可能就是病源地

流程

1. 鸿蒙官方战略合作共建--HarmonyOS技术社区

2. 给定若干样本, 和样本距离计算器, 需要求解k个样本中心点

3. 首先从样本中随机抽取k个点, 作为中心点

4. 循环每个样本

1. 鸿蒙官方战略合作共建--HarmonyOS技术社区

2. 分别计算样本点到k个中心点的距离

3. 判断距离样本点最小的中心点

4. 将样本划分到该最小中心点的簇

5. 计算每个簇的中心点, 作为新的中心点

1. 鸿蒙官方战略合作共建--HarmonyOS技术社区

2. 循环簇中的每个样本

3. 计算该样本, 到本簇其他样本的距离之和

4. 与其他样本的距离和最小的点, 就是新的中心点

6. 重复3-4, 直到中心点不再变化, 计算完毕

设计

• IPoint: 样本点接口, 其实是一个空接口

• IDistanceCalculator: 距离计算器接口

• IClassifier: 分类器接口, 将samples聚类成k个, 并返回k个中心点

• tPerson: 病例样本点, 实现IPoint接口, 含x,y坐标

• tPersonDistanceCalculator: 病例距离计算器, 计算两点间x,y坐标的直线距离

• tKMeansClassifier: k-means聚类器, 实现IClassifier接口.

单元测试

k_means_test.go

package others  import (     km "learning/gooop/others/k_means"     "strings"     "testing" )  func Test_KMeans(t *testing.T) {     // 创建样本点     samples := []km.IPoint {         km.NewPerson(2, 11),         km.NewPerson(2, 8),         km.NewPerson(2, 6),          km.NewPerson(3, 12),         km.NewPerson(3, 10),          km.NewPerson(4, 7),         km.NewPerson(4, 3),          km.NewPerson(5, 11),         km.NewPerson(5, 9),         km.NewPerson(5, 2),          km.NewPerson(7, 9),         km.NewPerson(7, 6),         km.NewPerson(7, 3),          km.NewPerson(8, 12),          km.NewPerson(9, 3),         km.NewPerson(9, 5),         km.NewPerson(9, 10),          km.NewPerson(10, 3),         km.NewPerson(10, 6),         km.NewPerson(10, 12),          km.NewPerson(11, 9),     }      fnPoints2String := func(points []km.IPoint) string {         items := make([]string, len(points))         for i,it := range points {             items[i] = it.String()         }         return strings.Join(items, " ")     }      for k:=1;k<=3;k++ {         centers := km.KMeansClassifier.Classify(samples, km.PersonDistanceCalculator, k)         t.Log(fnPoints2String(centers))     } }

测试输出

$ go test -v k_means_test.go  === RUN   Test_KMeans     k_means_test.go:53: p(7,6)     k_means_test.go:53: p(5,9) p(7,3)     k_means_test.go:53: p(9,10) p(3,10) p(7,3) --- PASS: Test_KMeans (0.00s) PASS ok      command-line-arguments  0.002s

IPoint.go

样本点接口, 其实是一个空接口

package km  import "fmt"  type IPoint interface {     fmt.Stringer }

IDistanceCalculator.go

距离计算器接口

package km  type IDistanceCalculator interface {     Calc(a, b IPoint) int }

IClassifier.go

分类器接口, 将samples聚类成k个, 并返回k个中心点

package km  type IClassifier interface {     // 将samples聚类成k个, 并返回k个中心点     Classify(samples []IPoint, calc IDistanceCalculator, k int) []IPoint }

tPerson.go

病例样本点, 实现IPoint接口, 含x,y坐标

package km  import "fmt"  type tPerson struct {     x int     y int }  func NewPerson(x, y int) IPoint {     return &tPerson{x, y, } }  func (me *tPerson) String() string {     return fmt.Sprintf("p(%v,%v)", me.x, me.y) }

tPersonDistanceCalculator.go

病例距离计算器, 计算两点间x,y坐标的直线距离

package km   type tPersonDistanceCalculator struct { }  var gMaxInt = 0x7fffffff_ffffffff  func newPersonDistanceCalculator() IDistanceCalculator {     return &tPersonDistanceCalculator{} }  func (me *tPersonDistanceCalculator) Calc(a, b IPoint) int {     if a == b {         return 0     }      p1, ok := a.(*tPerson)     if !ok {         return gMaxInt     }      p2, ok := b.(*tPerson)     if !ok {         return gMaxInt     }      dx := p1.x - p2.x     dy := p1.y - p2.y      d := dx*dx + dy*dy     if d < 0 {         panic(d)     }     return d }  var PersonDistanceCalculator = newPersonDistanceCalculator()

tKMeansClassifier.go

k-means聚类器, 实现IClassifier接口.

package km  import (     "math/rand"     "time" )  type tKMeansClassifier struct { }  type tPointEntry struct {     point IPoint     distance int     index int }  func newPointEntry(p IPoint, d int, i int) *tPointEntry {     return &tPointEntry{         p, d, i,     } }  func newKMeansClassifier() IClassifier {     return &tKMeansClassifier{} }  // 将samples聚类成k个, 并返回k个中心点 func (me *tKMeansClassifier) Classify(samples []IPoint, calc IDistanceCalculator, k int) []IPoint {     sampleCount := len(samples)     if sampleCount <= k {         return samples     }      // 初始化, 随机选择k个中心点     rnd := rand.New(rand.NewSource(time.Now().UnixNano()))     centers := make([]IPoint, k)     for selected, i:= make(map[int]bool, 0), 0;i < k; {         n := rnd.Intn(sampleCount)         _,ok := selected[n]          if !ok {             selected[n] = true             centers[i] = samples[n]             i++         }     }       // 根据到中心点的距离, 划分samples     for {         groups := me.split(samples, centers, calc)          newCenters := make([]IPoint, k)         for i,g := range groups {             newCenters[i] = me.centerOf(g, calc)         }          if me.groupEquals(centers, newCenters) {             return centers         }         centers = newCenters     } }  // 将样本点距离中心点的距离进行分簇 func (me *tKMeansClassifier) split(samples []IPoint, centers []IPoint, calc IDistanceCalculator) [][]IPoint {     k := len(centers)     result := make([][]IPoint, k)     for i := 0;i
"如何使用Golang基本数据结构与算法k-means聚类算法"的内容就介绍到这里了，感谢大家的阅读。如果想了解更多行业相关的知识可以关注网站，小编将为大家输出更多高质量的实用文章！