如何使用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,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聚類算法”的內容就介紹到這里了，感謝大家的閱讀。如果想了解更多行業相關的知識可以關注億速云網站，小編將為大家輸出更多高質量的實用文章！