如何使用Golang基本數(shù)據(jù)結(jié)構(gòu)與算法k-means聚類算法

本篇內(nèi)容介紹了“如何使用Golang基本數(shù)據(jù)結(jié)構(gòu)與算法k-means聚類算法”的有關(guān)知識，在實際案例的操作過程中，不少人都會遇到這樣的困境，接下來就讓小編帶領(lǐng)大家學(xué)習(xí)一下如何處理這些情況吧！希望大家仔細(xì)閱讀，能夠?qū)W有所成！

k-means聚類算法

聚類就是在輸入為多個數(shù)據(jù)時， 將“相似”的數(shù)據(jù)分為一組的操作。 k-means算法是聚類算法中的一種。 首先隨機選擇k個點作為簇的中心點, 然后重復(fù)執(zhí)行“將數(shù)據(jù)分到相應(yīng)的簇中”和 “將中心點移到重心的位置”這兩個操作， 直到中心點不再發(fā)生變化為止。 k-means算法中，隨著操作的不斷重復(fù)， 中心點的位置必定會在某處收斂， 這一點已經(jīng)在數(shù)學(xué)層面上得到證明。 摘自 <<我的第一本算法書>> 【日】石田保輝；宮崎修一

場景

• 某地突然爆發(fā)新冠疫情, 現(xiàn)防疫急需根據(jù)病例分布, 查找可能的病源地

• 首先將病例分布的坐標(biāo), 錄入系統(tǒng)

• 然后根據(jù)k-means算法, 按k從1到3, 分別進行聚類

• 聚類的中心點, 可能就是病源地

流程

1. 鴻蒙官方戰(zhàn)略合作共建——HarmonyOS技術(shù)社區(qū)

2. 給定若干樣本, 和樣本距離計算器, 需要求解k個樣本中心點

3. 首先從樣本中隨機抽取k個點, 作為中心點

4. 循環(huán)每個樣本

1. 鴻蒙官方戰(zhàn)略合作共建——HarmonyOS技術(shù)社區(qū)

2. 分別計算樣本點到k個中心點的距離

3. 判斷距離樣本點最小的中心點

4. 將樣本劃分到該最小中心點的簇

5. 計算每個簇的中心點, 作為新的中心點

1. 鴻蒙官方戰(zhàn)略合作共建——HarmonyOS技術(shù)社區(qū)

2. 循環(huán)簇中的每個樣本

3. 計算該樣本, 到本簇其他樣本的距離之和

4. 與其他樣本的距離和最小的點, 就是新的中心點

6. 重復(fù)3-4, 直到中心點不再變化, 計算完畢

設(shè)計

• IPoint: 樣本點接口, 其實是一個空接口

• IDistanceCalculator: 距離計算器接口

• IClassifier: 分類器接口, 將samples聚類成k個, 并返回k個中心點

• tPerson: 病例樣本點, 實現(xiàn)IPoint接口, 含x,y坐標(biāo)

• tPersonDistanceCalculator: 病例距離計算器, 計算兩點間x,y坐標(biāo)的直線距離

• tKMeansClassifier: k-means聚類器, 實現(xiàn)IClassifier接口.

單元測試

k_means_test.go

package others  import (     km "learning/gooop/others/k_means"     "strings"     "testing" )  func Test_KMeans(t *testing.T) {     // 創(chuàng)建樣本點     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

病例樣本點, 實現(xiàn)IPoint接口, 含x,y坐標(biāo)

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坐標(biāo)的直線距離

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聚類器, 實現(xiàn)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++         }     }       // 根據(jù)到中心點的距離, 劃分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基本數(shù)據(jù)結(jié)構(gòu)與算法k-means聚類算法”的內(nèi)容就介紹到這里了，感謝大家的閱讀。如果想了解更多行業(yè)相關(guān)的知識可以關(guān)注億速云網(wǎng)站，小編將為大家輸出更多高質(zhì)量的實用文章！