最近阅读<<我的第一本算法书>>(【日】石田保辉;宫崎修一)
本系列笔记拟采用golang练习之
聚类就是在输入为多个数据时, 将“相似”的数据分为一组的操作。 k-means算法是聚类算法中的一种。 首先随机选择k个点作为簇的中心点, 然后重复执行“将数据分到相应的簇中”和 “将中心点移到重心的位置”这两个操作, 直到中心点不再发生变化为止。 k-means算法中,随着操作的不断重复, 中心点的位置必定会在某处收敛, 这一点已经在数学层面上得到证明。 摘自 <<我的第一本算法书
【日】石田保辉;宫崎修一循环每个样本
计算每个簇的中心点, 作为新的中心点
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
样本点接口, 其实是一个空接口
- package km
- import "fmt"
- type IPoint interface {
- fmt.Stringer
- }
距离计算器接口
- package km
- type IDistanceCalculator interface {
- Calc(a, b IPoint) int
- }
分类器接口, 将samples聚类成k个, 并返回k个中心点
- package km
- type IClassifier interface {
- // 将samples聚类成k个, 并返回k个中心点
- Classify(samples []IPoint, calc IDistanceCalculator, k int) []IPoint
- }
病例样本点, 实现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)
- }
病例距离计算器, 计算两点间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()
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()
【51CTO.com快译】边缘计算对于更广泛的云计算和基础设施服务市场意味着什么?很...
本文转载自微信公众号「Serverless」,作者王科怀(行松)。转载本文请联系Serve...
描述 给出一个小数数组A,一个非负整数target。对A中的每个小数进行向上取整或者...
云服务器实例更换公网 IP 地址有什么限制? 更换云服务器实例的公网 IP 地址有以...
专属主机搭载了华为云虚拟化系统,购买之后可以直接使用ECS的公共镜像发放虚拟机...
Windows云服务器卡顿怎么办? Linux云服务器卡顿怎么办?...
1. 背景 随着越来越多的金融行业基于mPaas搭建并上线新的App,App的上线质量也成...
本文汇总了基于对象存储服务(OBS,Object Storage Service)常见应用场景的操作...
想要理解Spring,必须要掌握的两个知识点就是IoC和AOP,在这里我首先带大家了解...
虚拟环境是安全地使用不同版本的 Python 和软件包组合的关键。 Python 对管理虚...