出处最近在看<<我的第一本算法书>>（[日本]石田康弘；宫崎修一）本系列笔记打算用golang练习k-意思是聚类算法聚类是当输入为多个数据时，将“相似”的数据归为一组的操作。k-means算法是聚类算法之一。先随机选取k个点作为聚类的中心点，然后重复“将数据划分到相应的聚类”和“将中心点移动到重心位置”这两个操作，直到中心点不再变化.在k-means算法中，随着运算的不断重复，中心点的位置一定会收敛到某处，这已经在数学层面得到了证明。摘自<<我的第一本算法书>>[日本]石田康弘；宫崎修一突然爆发新冠疫情的场景，现在防疫需要根据病例分布寻找可能的病源。首先，将病例分布的坐标输入，然后根据k-means算法，系统根据k从1到3进行聚类，聚类的中心点可能是疾病过程的原点。给定几个样本和一个样本距离计算器，需要先计算出k个样本的中心点，从样本中随机选择k个点，以它们为中心点循环每个样本，计算样本点到k的距离中心点。确定与样本点距离最小的中心点，将样本划分到中心点最小的簇中。计算每个簇的中心。点，作为新的中心点，为循环簇中的每个样本计算样本，与本簇中其他样本的距离和与其他样本的最小距离之和为新的中心点重复3-4直到中心点不变，计算完成后，设计IPoint：样本点接口，实际上是一个空接口IDistanceCalculator：距离计算器接口IClassifier：分类器接口，将样本聚类成k，返回k个中心点tPerson：案例样本点，实现IPoint接口，包括x，y坐标tPersonDistanceCalculator：案例距离计算器，计算两点之间x，y坐标的直线距离tKMeansClassifier：k-meansclusterer，实现IClassifier接口。单元测试k_means_test.gopackageothersimport(km"learning/gooop/others/k_means""strings""testing")funcTest_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,it:=rangepoints{items[i]=it.String()}returnstrings.Join(items,"")}fork:=1;k<=3;k++{centers:=km.KMeansClassifier.Classify(samples,km.PersonDistanceCalculator,k)t.Log(fnPoints2String(centers))}}Configuring$gotest-vk_means_test。go===RUNTest_KMean_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)PASSokcommand-line-arguments0.002s当IPoint.go为默认版本时，我们需要创建自定义包import"fmt"typeIPointinterface{fmt.Stringer}.IDigostanceCalculator默认配置类型包kmtypeIDistanceCalculatorinterface{Calc(a,bIPOint)int}IClassifier.go分类器接口，将样本聚类成k，并返回k个中心点packagekmtypeIClassifierinterface{//将样本聚类成k，并返回k个中心点.gocase样本点，实现IPoint接口，包括x,y坐标packagekmimport"fmt"typetPersonstruct{xintyint}funcNewPerson(x,yint)IPoint{return&tPerson{x,y,}}func(me*tPerson)String()string{returnfmt.Sprintf("p(%v,%v)",me.x,me.y)}tPersonDistanceCalculator.gocase距离计算器，计算两点之间的x和y坐标直线距离封装kmtypetPersonDistanceCalculatorstruct{}vargMaxInt=0x7fffffff_fffffffffuncnewPersonDistanceCalculator()IDistanceCalculator{return&tPersonDistanceCalculator{}}func(me*tPersonDistanceCalculator)Calc(a,bIPoint)int{ifa==b{return0}p1,okt:=a).ok{returngMaxInt}p2,ok:=b.(*tPerson)if!ok{returngMaxInt}dx:=p1.x-p2.xdy:=p1.y-p2.yd:=dx*dx+dy*dyifd<0{panic(d)}returnd}varPersonDistanceCalculator=newPersonDistanceCalculator()tKMeansClassifier.gok-meansclusterer,实现IClassifier接口.packagekmimport("math/rand""time")typetKMeansClassifierstruct{}typetPointEntrystruct{pointIPointdistanceintindexint}funcnewPointEntry(pIPoint,dint,iint)*tPointEntry{return&tPointEntry{p,d,i,}}funcnewKMeansClassifier()IClassifier{return&tKMeansClassifier{}}//聚合样本分类k，并返回k个中心点func(me*tKMeansClassifier)Classify(samples[]IPoint,calcIDistanceCalculator,kint)[]IPoint{sampleCount:=len(samples)ifsampleCount<=k{returnsamples}//初始化，随机选择k个中心点rnd:=rand.New(rand.NewSource(time.Now().UnixNano()))centers:=make([]IPoint,k)forselected,i:=make(map[int]bool,0),0;i
