缘起

最近阅读<<我的第一本算法书>>(【日】石田保辉；宫崎修一)
本系列笔记拟采用golang练习之

k-means聚类算法

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

场景

  • 某地突然爆发新冠疫情, 现防疫急需根据病例分布, 查找可能的病源地
  • 首先将病例分布的坐标, 录入系统
  • 然后根据k-means算法, 按k从1到3, 分别进行聚类
  • 聚类的中心点, 可能就是病源地

image.png

流程

  1. 给定若干样本, 和样本距离计算器, 需要求解k个样本中心点
  2. 首先从样本中随机抽取k个点, 作为中心点
  3. 循环每个样本
    1. 分别计算样本点到k个中心点的距离
    2. 判断距离样本点最小的中心点
    3. 将样本划分到该最小中心点的簇
  4. 计算每个簇的中心点, 作为新的中心点
    1. 循环簇中的每个样本
    2. 计算该样本, 到本簇其他样本的距离之和
    3. 与其他样本的距离和最小的点, 就是新的中心点
  5. 重复3-4, 直到中心点不再变化, 计算完毕

设计

  • IPoint: 样本点接口, 其实是一个空接口
  • IDistanceCalculator: 距离计算器接口
  • IClassifier: 分类器接口, 将samples聚类成k个, 并返回k个中心点
  • tPerson: 病例样本点, 实现IPoint接口, 含x,y坐标
  • tPersonDistanceCalculator: 病例距离计算器, 计算两点间x,y坐标的直线距离
  • tKMeansClassifier: k-means聚类器, 实现IClassifier接口.

单元测试

k_means_test.go

  1. package others
  3. import (
  4.     km "learning/gooop/others/k_means"
  5.     "strings"
  6.     "testing"
  7. )
  9. func Test_KMeans(t *testing.T) {
  10.     // 创建样本点
  11.     samples := []km.IPoint {
  12.         km.NewPerson(2, 11),
  13.         km.NewPerson(2, 8),
  14.         km.NewPerson(2, 6),
  16.         km.NewPerson(3, 12),
  17.         km.NewPerson(3, 10),
  19.         km.NewPerson(4, 7),
  20.         km.NewPerson(4, 3),
  22.         km.NewPerson(5, 11),
  23.         km.NewPerson(5, 9),
  24.         km.NewPerson(5, 2),
  26.         km.NewPerson(7, 9),
  27.         km.NewPerson(7, 6),
  28.         km.NewPerson(7, 3),
  30.         km.NewPerson(8, 12),
  32.         km.NewPerson(9, 3),
  33.         km.NewPerson(9, 5),
  34.         km.NewPerson(9, 10),
  36.         km.NewPerson(10, 3),
  37.         km.NewPerson(10, 6),
  38.         km.NewPerson(10, 12),
  40.         km.NewPerson(11, 9),
  41.     }
  43.     fnPoints2String := func(points []km.IPoint) string {
  44.         items := make([]string, len(points))
  45.         for i,it := range points {
  46.             items[i] = it.String()
  47.         }
  48.         return strings.Join(items, " ")
  49.     }
  51.     for k:=1;k<=3;k++ {
  52.         centers := km.KMeansClassifier.Classify(samples, km.PersonDistanceCalculator, k)
  53.         t.Log(fnPoints2String(centers))
  54.     }
  55. }

测试输出

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

IPoint.go

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

  1. package km
  3. import "fmt"
  5. type IPoint interface {
  6.     fmt.Stringer
  7. }

IDistanceCalculator.go

距离计算器接口

  1. package km
  3. type IDistanceCalculator interface {
  4.     Calc(a, b IPoint) int
  5. }

IClassifier.go

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

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

tPerson.go

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

  1. package km
  3. import "fmt"
  5. type tPerson struct {
  6.     x int
  7.     y int
  8. }
  10. func NewPerson(x, y int) IPoint {
  11.     return &tPerson{x, y, }
  12. }
  14. func (me *tPerson) String() string {
  15.     return fmt.Sprintf("p(%v,%v)", me.x, me.y)
  16. }

tPersonDistanceCalculator.go

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

  1. package km
  4. type tPersonDistanceCalculator struct {
  5. }
  7. var gMaxInt = 0x7fffffff_ffffffff
  9. func newPersonDistanceCalculator() IDistanceCalculator {
  10.     return &tPersonDistanceCalculator{}
  11. }
  13. func (me *tPersonDistanceCalculator) Calc(a, b IPoint) int {
  14.     if a == b {
  15.         return 0
  16.     }
  18.     p1, ok := a.(*tPerson)
  19.     if !ok {
  20.         return gMaxInt
  21.     }
  23.     p2, ok := b.(*tPerson)
  24.     if !ok {
  25.         return gMaxInt
  26.     }
  28.     dx := p1.x - p2.x
  29.     dy := p1.y - p2.y
  31.     d := dx*dx + dy*dy
  32.     if d < 0 {
  33.         panic(d)
  34.     }
  35.     return d
  36. }
  38. var PersonDistanceCalculator = newPersonDistanceCalculator()

tKMeansClassifier.go

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

  1. package km
  3. import (
  4.     "math/rand"
  5.     "time"
  6. )
  8. type tKMeansClassifier struct {
  9. }
  11. type tPointEntry struct {
  12.     point IPoint
  13.     distance int
  14.     index int
  15. }
  17. func newPointEntry(p IPoint, d int, i int) *tPointEntry {
  18.     return &tPointEntry{
  19.         p, d, i,
  20.     }
  21. }
  23. func newKMeansClassifier() IClassifier {
  24.     return &tKMeansClassifier{}
  25. }
  27. // 将samples聚类成k个, 并返回k个中心点
  28. func (me *tKMeansClassifier) Classify(samples []IPoint, calc IDistanceCalculator, k int) []IPoint {
  29.     sampleCount := len(samples)
  30.     if sampleCount <= k {
  31.         return samples
  32.     }
  34.     // 初始化, 随机选择k个中心点
  35.     rnd := rand.New(rand.NewSource(time.Now().UnixNano()))
  36.     centers := make([]IPoint, k)
  37.     for selected, i:= make(map[int]bool, 0), 0;i < k; {
  38.         n := rnd.Intn(sampleCount)
  39.         _,ok := selected[n]
  41.         if !ok {
  42.             selected[n] = true
  43.             centers[i] = samples[n]
  44.             i++
  45.         }
  46.     }
  49.     // 根据到中心点的距离, 划分samples
  50.     for {
  51.         groups := me.split(samples, centers, calc)
  53.         newCenters := make([]IPoint, k)
  54.         for i,g := range groups {
  55.             newCenters[i] = me.centerOf(g, calc)
  56.         }
  58.         if me.groupEquals(centers, newCenters) {
  59.             return centers
  60.         }
  61.         centers = newCenters
  62.     }
  63. }
  65. // 将样本点距离中心点的距离进行分簇
  66. func (me *tKMeansClassifier) split(samples []IPoint, centers []IPoint, calc IDistanceCalculator) [][]IPoint {
  67.     k := len(centers)
  68.     result := make([][]IPoint, k)
  69.     for i := 0;i<k;i++ {
  70.         result[i] = make([]IPoint, 0)
  71.     }
  73.     entries := make([]*tPointEntry, k)
  74.     for i,c := range centers {
  75.         entries[i] = newPointEntry(c, 0, i)
  76.     }
  78.     for _,p := range samples {
  79.         for _,e := range entries {
  80.             e.distance = calc.Calc(p, e.point)
  81.         }
  83.         center := me.min(entries)
  84.         result[center.index] = append(result[center.index], p)
  85.     }
  87.     return result
  88. }
  90. // 计算一簇样本的重心. 重心就是距离各点的总和最小的点
  91. func (me *tKMeansClassifier) centerOf(samples []IPoint, calc IDistanceCalculator) IPoint {
  92.     entries := make([]*tPointEntry, len(samples))
  93.     for i,src := range samples {
  94.         distance := 0
  95.         for _,it := range samples {
  96.             distance += calc.Calc(src, it)
  97.         }
  98.         entries[i] = newPointEntry(src, distance, i)
  99.     }
  101.     return me.min(entries).point
  102. }
  104. // 判断两组点是否相同
  105. func (me *tKMeansClassifier) groupEquals(g1, g2 []IPoint) bool {
  106.     if len(g1) != len(g2) {
  107.         return false
  108.     }
  110.     for i,v := range g1 {
  111.         if g2[i] != v {
  112.             return false
  113.         }
  114.     }
  116.     return true
  117. }
  119. // 查找距离最小的点
  120. func (me *tKMeansClassifier) min(entries []*tPointEntry) *tPointEntry {
  121.     minI := 0
  122.     minD := gMaxInt
  123.     for i,it := range entries {
  124.         if it.distance < minD {
  125.             minI = i
  126.             minD = it.distance
  127.         }
  128.     }
  130.     return entries[minI]
  131. }
  134. var KMeansClassifier = newKMeansClassifier()

(end)