如何使用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<k;i++ {         result[i] = make([]IPoint, 0)     }      entries := make([]*tPointEntry, k)     for i,c := range centers {         entries[i] = newPointEntry(c, 0, i)     }      for _,p := range samples {         for _,e := range entries {             e.distance = calc.Calc(p, e.point)         }          center := me.min(entries)         result[center.index] = append(result[center.index], p)     }      return result }  // 计算一簇样本的重心. 重心就是距离各点的总和最小的点 func (me *tKMeansClassifier) centerOf(samples []IPoint, calc IDistanceCalculator) IPoint {     entries := make([]*tPointEntry, len(samples))     for i,class="lazy" data-src := range samples {         distance := 0         for _,it := range samples {             distance += calc.Calc(class="lazy" data-src, it)         }         entries[i] = newPointEntry(class="lazy" data-src, distance, i)     }      return me.min(entries).point }  // 判断两组点是否相同 func (me *tKMeansClassifier) groupEquals(g1, g2 []IPoint) bool {     if len(g1) != len(g2) {         return false     }      for i,v := range g1 {         if g2[i] != v {             return false         }     }      return true }  // 查找距离最小的点 func (me *tKMeansClassifier) min(entries []*tPointEntry) *tPointEntry {     minI := 0     minD := gMaxInt     for i,it := range entries {         if it.distance < minD {             minI = i             minD = it.distance         }     }      return entries[minI] }   var KMeansClassifier = newKMeansClassifier()

“如何使用Golang基本数据结构与算法k-means聚类算法”的内容就介绍到这里了，感谢大家的阅读。如果想了解更多行业相关的知识可以关注编程网网站，小编将为大家输出更多高质量的实用文章！