欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

python手动实现K_means聚类(指定K值)

程序员文章站 2022-07-14 19:22:36
...

前言

这几天作业,用到了k_means聚类,作为一名deeper,怎么能不手动实现一下呢?然后,我就错过了作业的提交时间。。。。

实现

  • 原理
    简单来说,可以分为以下几步:
  1. 指定有几个簇
  2. 每个簇任选一个点作为初值(数据中的点),中心点(几个簇就几个中心点),会有很多种情况
  3. 通过指定的距离函数,计算数据中每个点与中心点的距离
  4. 将计算的点加入到与其最近的簇中
  5. 所有点都进行一遍之后,重新计算中心点(簇中的每个点加起来,求平均值)
  6. 重复以上步骤,直至簇不会变化
  7. 将所有的情况进行计算,找出最小的(也可以通过设置阈值),就是最合适的聚类(当然也有很多评判方式,这里实现一个最简单的,通过求出簇中的所有点到中心点的平方均值,补充:除了计算簇内部的值要求最小之外,也可以计算簇与簇之间的值越大。因为最理想的情况就是簇内部越近越好,簇与簇之间越远越好。)
    python手动实现K_means聚类(指定K值)
#Author:龙文汉
#Data:2020.11.18
#Discription:聚类算法
import numpy as np
import copy
import itertools

class K_means():
    def __init__(self,data,cu_num):
        self.arry_first = data
        self.cu_num = cu_num
        self.cu = []
        self.arry = []

#初始化每个簇,根据设定的簇数量,随机添加簇
    def Cu_initial(self,x):
        #x = random.sample(range(0,len(self.arry)-self.cu_num),self.cu_num)
        #print(x)
        # x = np.random.randint(1,6,self.cu_num,"int32")#会重复
        self.arry = copy.deepcopy(self.arry_first)
        #print("^^^^^^^",self.arry)
        self.cu = []
        for i in x:
            self.cu.append([])
            self.cu[-1].append(data[i])
            self.arry.remove(data[i])
            #print(self.arry)
#计算欧氏距离
    def Ou_in(self,data1,data2):
        #print(data1,data2)
        ans = ((data1[0]-data2[0])**2+(data1[1]-data2[1])**2)**0.5
        #print(ans)
        return ans
#计算每个簇的平方和均差
    def Pinfang(self,tem):
        # cu_center = 0
        # for i in cu:
        #     cu_center+=i
        # cu_center /= len(cu)
        # pinfang = 0
        # for i in cu:
        #     pinfang += (cu-cu_center)**2
        pingfang = 0
        for cu in tem:
            cu_center = np.mean(cu,axis=0)
            pingfang += np.sum(list(map(lambda x:self.Ou_in(x,cu_center)**2,cu)))
        return pingfang
#开始进行没一簇的聚类
    def Evualution(self):
        first = 1
        while(True):#一直循环,直到簇不再变化
            center_list = []
            tem = copy.deepcopy(self.cu)  # 暂时簇的形式,便于对后面进行对比,注意复制形式,地址的问题
            if first==0:
                self.cu = []
                self.arry = copy.deepcopy(self.arry_first)
            for i in range(self.cu_num):#计算每一个簇的中心点
                center_list.append(np.mean(tem[i], axis=0))
                if first==0:
                    self.cu.append([])
            if first == 1:
                first = 0
            print("每个簇的中心点",center_list)
            for i in self.arry:#依次对每个点进行迭代计算(根据欧式距离决定归属)
                print("开始对该点的聚类",i)
                ans_list = []  # 一个点对于每一个簇的欧式距离集合
                for x in center_list:#依次迭代每个中心簇
                    ans_list.append(self.Ou_in(i, x))#增加一个点对每个簇的欧式距离
                print("该点和所有簇的欧式距离集合",ans_list)
                print("最小的欧式距离为",min(ans_list),"index是",ans_list.index(min(ans_list)))
                self.cu[ans_list.index(min(ans_list))].append(i)#更新簇,将该点添加到欧式距离最小的簇中
                print("添加该节点之后的簇",self.cu)
            print("原来的簇", tem)
            print("更新之后的簇",self.cu)
            if (self.cu == tem):#如果簇已经不变,则说明此时完成了聚类
                return tem
            print("所有的点本轮聚类结束(在这之前的中心点不改变)")
#开始找出最优解
    def Best(self):
        min_list = []
        min_pin = 100000000
        x = list(itertools.permutations(range(len(self.arry_first)),self.cu_num))
        for w in x:
            self.Cu_initial(w)
            tem = self.Evualution()
            pin = self.Pinfang(tem)
            print("本次的平方差值为",pin)
            if pin < min_pin:
                min_pin=pin
                min_list = self.cu
        return min_list,min_pin

if __name__ == "__main__":
    data = [[4.0, 2.5], [1.5, 1.0], [3.0, 1.5], [4.5, 3.5], [4.0, 2.5], [2.5, 5.0]]
    # data.remove([4.0, 2.5])
    # print(data)
    k_means = K_means(data,2)
    answer = k_means.Best()
    print(answer)



参考:K-means原理、优化及应用

相关标签: 算法 聚类