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

发布时间:2021-10-18 11:54:23 作者:iii
来源:亿速云 阅读:125

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

k-means聚类算法

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

场景

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

流程

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

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

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

  4. 循环每个样本

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

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

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

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

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

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

    2. 循环簇中的每个样本

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

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

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

设计

单元测试

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,src := range samples {         distance := 0         for _,it := range samples {             distance += calc.Calc(src, it)         }         entries[i] = newPointEntry(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聚类算法”的内容就介绍到这里了,感谢大家的阅读。如果想了解更多行业相关的知识可以关注亿速云网站,小编将为大家输出更多高质量的实用文章!

推荐阅读:
  1. 网格聚类算法综述
  2. 怎么在python中利用K-means聚类算法对图像进行分割

免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。

golang k-means

上一篇:如何使用python-nmap模块扫描端口脚本

下一篇:ES6中let怎么用

相关阅读

您好,登录后才能下订单哦!

密码登录
登录注册
其他方式登录
点击 登录注册 即表示同意《亿速云用户服务条款》