K-means 分类
引例
每一个×点都有一个权力范围,如下图所示:
如果一个权力中心,去管理这两个市区的人口,光是车费,就是个很大的支出,因此为了节约支出,需要重新确定权力中心的位置,如下图:
同时秉承着谁离我近我管谁的原则,然后重新划分能管理到谁,如下图:
然后权力中心就开始扯皮子,我们之间那六个我不想管,你来管,扯来扯去,最终他们决定移动到当前范围最中心的地方,哪个权力中心离得近就谁管,因此他们又移动了一下,如下图:
接着权力中心他们之间再对势力范围划分,如下图:
最终蓝色的权力中心接受了其中的一个,剩下的全部丢给红色权力中心,如下图最终结果:
初级实现
而现在我们来实现这个功能,其步骤思路:
1、随机生成权力点与治理点 2、哪些治理点距离哪个权力中心近,就归哪个权力中心管 3、权力中心向治理点中心移动 4、重新执行步骤2 5、再次执行步骤3,直到权力中心不在移动
我们先不使用密集的治理点,而是平均分散的随机点(一步一步来嘛)
定义相关的变量,并初始化相关变量
# 导入使用到的包
import numpy as np
import matplotlib.pyplot as plt
import math
# 职员
class People:
def __init__(self):
# 记录职员的位置
self.people = []
# 打上标签,表示被哪个上司管
self.label = []
# 管理人员
class Boss:
def __init__(self):
# 记录管理员的位置
self.boss = []
# 图像显示:被管理的职员的颜色应该与管理员一致
# 被管理职员与管理员的颜色一致,显示的形状不一致
self.people_style = ["r*","go","bs","yv","c<","m>","k*"]
self.boss_style = ["rx","gx","bx","yx","cx","mx","kx"]
# 所有人员的地点位置
class Map:
def __init__(self,boss,people):
# 管理员与职员的人数
self.boss = boss
self.people = people
# 存放管理员与职员的位置
self.bossaddr = Boss()
self.peopleaddr = People()
# 每个职员与不同管理员的距离,用于计算最小值
self.dis = []
# 管理员移动前的位置
self.oldbossaddr = []
# 初始化地图
self.init_map()
def init_map(self):
# 假设地图的大小是0到100
# 生成管理员的位置,并添加到管理员位置列表当中
for i in range (self.boss):
x = np.random.randint(0,100)
y = np.random.randint(0,100)
# 将随机生成的boss的位置放到self.bossaddr.boss 中
self.bossaddr.boss.append([x,y])
# 生成职员位置,并添加到职员位置列表中
for i in range(self.people):
x = np.random.randint(0,100)
y = np.random.randint(0,100)
self.peopleaddr.people.append([x,y])
# 同时先默认所有员工不属于任何管理员
self.peopleaddr.label.append(9)
# 打印当前的地图
self.show_init_map()
def show_init_map(self):
# 打印职员的位置
people = np.array(self.peopleaddr.people)
plt.plot(people[:,0],people[:,1],"b*")
# 打印管理员的位置
boss = np.array(self.bossaddr.boss)
plt.plot(boss[:,0],boss[:,1],"r^")
# 设置标签
plt.legend(["people-addr","boss-addr"],loc = 1)
plt.show()
这样,我们随机生成位置的码就写好了
接下来就是给所有管理员分配职员
给管理员分配职员
我们依照的原则是,职员离哪个管理员近就被哪个管理员支配.
续上代码!!
def sort_people(self):
# 处理: 以职员为原点,计算职员距离哪个管理员近
for peo in range(self.people):
# 清空数组,第一次是空数组,但是后面再次分类的时候,不清空会有影响
self.dis.clear()
for bos in range(self.boss):
# 计算距离,使用的是根号下x0-x1差的平方加上y0-y1差的平方
bos_peo_dis = math.sqrt((self.peopleaddr.people[peo][0]-self.bossaddr.boss[bos][0])**2+(self.peopleaddr.people[peo][1]-self.bossaddr.boss[bos][1])**2)
# 计算结果放入到self.dis的列表中
self.dis.append(bos_peo_dis)
# 通过比较大小,并寻找出最小值下标,那么self.dis 下标对应的就是第一个管理员的下标
# 修改peo员工的标签,表示为,输入第一个管理员
self.peopleaddr.label[peo] = self.dis.index(min(self.dis))
# self.dis.index(min(self.dis))
# min(self.dis) 是找出一个职员离最管理员最近的距离,返回的值是距离值,不是下标值
# 通过index(min(self.dis))找到最小值的下标,通过下标看这个职员属于哪个管理员
分完类,那么就打印出来看看分完之后,哪些职员被哪些管理员支配吧
打印分类后,管理员支配的职员
续上续上~~
def show_after_sort(self):
# 这里用for 循环是为了与分类后的职员作为区分
for bos in range(self.boss):
# 显示管理员的位置
plt.plot(self.bossaddr.boss[bos][0],self.bossaddr.boss[bos][1],self.bossaddr.boss_style[bos])
# 显示职员的位置
# 通过下标分类
people =np.array( [self.peopleaddr.people[peo] for peo in range(self.people) if self.peopleaddr.label[peo] == bos])
plt.plot(people[:,0],people[:,1],self.bossaddr.people_style[bos])
plt.show()
为了更有效的管理职员,管理员的位置最好要位于分配后员工的中心。
管理员的有效管理位置(坐标)
def move(self):
# 还是一样,先清空旧数组,第一次为空,多次移动不清除,会影响结果
self.oldbossaddr.clear()
# 将当前的放到旧的位置里面去
for addr in self.bossaddr.boss: self.oldbossaddr.append(addr)
# 清空当前管理员的位置,为移动到新位置的坐标做准备
self.bossaddr.boss.clear()
# 通过所管理的职员范围的中心确定管理员的位置
for bos in range(self.boss):
addr = [self.peopleaddr.people[peo] for peo in range(self.people) if self.peopleaddr.label[peo] == bos]
# 如果管理员出现在奇怪的位置,那么他就没有可管理的职员
if len(addr) != 0:
new_x = sum(np.array(addr)[:,0])/len(addr)*1.0
new_y = sum(np.array(addr)[:,1])/len(addr)*1.0
self.bossaddr.boss.append([new_x,new_y])
else:
# 如果管理员没有职员可以管理,那么他的位置不变
self.bossaddr.boss.append(self.oldbossaddr[bos])
移动之后,那么有些职员与管理员的距离就会改变,需要重新划分,直到管理员不再移动
计算管理员从旧得驻点到新的驻点得距离(移动的距离)
def move_dis(self):
dis_move = []
for bos in range(self.boss):
dis_move.append( math.sqrt((self.oldbossaddr[bos][0]-self.bossaddr.boss[bos][0])**2+(self.oldbossaddr[bos][1]-self.bossaddr.boss[bos][1])**2))
return sum(dis_move)
这就是管理员驻点移动结束的条件,所有管理员不移动时,完成最终的管理范围
调用上述的函数
# 调用函数
def main():
map = Map(boss = 2, people = 100)
while(True):
map.sort_people()
map.show_after_sort()
map.move()
map.move_dis()
if (map.move_dis() == 0 ):
break
if __name__ == "__main__":
main()
调用的结果如下:
最初始的一张分布图
分类后的图:注意打叉(x)的位置,为boss的位置
移动后的图
在分类且为最终的权力范围图
小结:
或许循环有很多次,其实到最后都是可以结束的。 而小编只是恰巧循环了4次就结束了。
我所使用的方法是通过打标签,每一个的职员都打上标签,哪个职员属于哪一个管理员通过排序的下标进行相关联。 另外一种方法就是利用矩阵的方式去划分,可能会比小编的这种方式的代码量小很多,大家可以多多尝试。
篇外拓展:
(1)从https://www.kaggle.com/akram24/mall-customers下载Mall_Customers.csv数据,利用python读取数据并转换为numpy数组;
(2)不考虑性别,保留年龄、年收入、消费率数据,分别计算中心点数量为2,3,4,5或6个时,使用Kmeans聚类;
(3)使用matplotlib或seaborn工具包对聚类结果进行可视化。