共计 4806 个字符，预计需要花费 13 分钟才能阅读完成。
缘起
最近浏览 << 我的第一本算法书 >>(【日】石田保辉；宫崎修一)
本系列笔记拟采纳 golang 练习之
k-means 聚类算法
聚类就是在输出为多个数据时，将“类似”的数据分为一组的操作。k-means 算法是聚类算法中的一种。首先随机抉择 k 个点作为簇的中心点,
而后反复执行“将数据分到相应的簇中”和“将中心点移到重心的地位”这两个操作，直到中心点不再发生变化为止。k-means 算法中，随着操作的一直反复，中心点的地位必定会在某处收敛，这一点曾经在数学层面上失去证实。摘自 << 我的第一本算法书 >>【日】石田保辉；宫崎修一 场景
- 某地忽然暴发新冠疫情, 现防疫急需依据病例散布, 查找可能的病源地
- 首先将病例散布的坐标, 录入零碎
- 而后依据 k -means 算法, 按 k 从 1 到 3, 别离进行聚类
- 聚类的中心点, 可能就是病源地
流程
- 给定若干样本, 和样本间隔计算器, 须要求解 k 个样本中心点
- 首先从样本中随机抽取 k 个点, 作为中心点
-
循环每个样本
- 别离计算样本点到 k 个中心点的间隔
- 判断间隔样本点最小的中心点
- 将样本划分到该最小中心点的簇
-
计算每个簇的中心点, 作为新的中心点
- 循环簇中的每个样本
- 计算该样本, 到本簇其余样本的间隔之和
- 与其余样本的间隔和最小的点, 就是新的中心点
- 反复 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.002sIPoint.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()(end)
正文完