k-means聚类:讲解与实现
2016-03-01 16:08:59
终于可以开始更新我的机器学习系列的博文了,因为刚刚开始,所以涉及的东西不深,先写写最简单的k-means聚类吧
话说最近终于找到了机器学习相关的科研,而且最近遇到几个靠谱的程序员,能帮忙参考意见,还有的已经有了发paper的精力,真是抱大腿啊,加上这学期课少,想想就让人想奋进!!!!这学期必须炼成金刚不坏身,好到了朝阳区继续战斗啊
还记得一个开发前辈这么评价程序员:
即使是一个人,也要像一支军队一样战斗
頑張ってる、!!!!!
以上都是唠叨,请忽视
k-means介绍
首先,作为一个 data science的从业人员,最经常遇到的情况就是,一大堆的表,所谓的表,就是一个对象,基于的坐标量的数值(比如x,y轴)的一个集合
那么,所有的data science人员都想一件事,就是如何让这些数据说话,这样才能从这些人类活动产生的抽象意义的信息产生二次价值
那么把它归类就是一个很好的选择
那么,他们只是数据,我们要怎么把他们归类呢?或者说他们的抽象意义太大,如何归类。
所以就有人提出了k-means聚类方法,它是基于欧式距离聚类,核心公式为:
而他的基本步骤是这样的:
也就是这样:
- 首先,你先有一堆堆的数据集,他们可以表达成一个
list
:data[1]=[2,5,7,...]
,其中,list里面的每一个值都有实际价值,例如,小明的各科成绩就可以表达成:xiaoming_score=[98,99,100...],这样,我们就可以针对这些数据,把好学生类,和坏学生类分出来了,但这里有一点需要说明,就好比高考时物理是120分,而生物只有72分一样,不同的数据类的标准不一样,而对于这种加权怎么加就看情况而定,不过一般我们要做归一化
处理,这往往能提高数据处理结果的准确性 - 接着,如果是
k-means
的话,一般使用欧式距离(euclidean metric)
- 我们会先随机k个值(randintNum),每个值在一定的区间内
- 接着我们遍历所有数据点,用欧式距离,算出来这个点和每个随机点(randintNum)的距离,并把它归入距离最小的那个随机点(randintNum)的类,这样我们便得到了大概的几个类
- 然后,我们把这几个类里面的每一个点,去算他和其他的在这个类的点的距离,找到这个类的几何坐标中心
- 得到的每一个类的几何坐标中心后,再吧这几个中心当成随机点(randintNum)重复聚类操作,
- 这样重复的次数越多,类的精确性就越大
下图为上面操作的图示,可以看到,重复多次之后,我们得到了较为满意的聚类结果:
最后的结果,比较明显的话,会变成类似这样:
下面是这个聚类算法的python
实现,因为python类似伪代码,好做表达:
#-*- coding: UTF-8 -*-
'''
auther:Aljun
project:k-means聚类
'''
from random import randint
import math
import matplotlib.pylab as mlp
import seaborn as sns
import numpy
'''
我们简单定义一个x,y的类
'''
class point():
def __init__(self,x,y):
self.x=x
self.y=y
'''
计算欧式距离
'''
def get_distance(vec1,vec2):
return math.sqrt((vec1.x-vec2.x)**2+(vec1.y-vec2.y)**2)
'''
聚类开始程序,data_set为输入数据,k为要几个类,depth为做几次欧式距离聚类
'''
def cluster_start(data_set,k=5,depth=5):
rand_num=[]
for i in range(k):
rand_num.append(point(x=randint(1,100),y=randint(1,100)))
parse_list=cluster(rand_num,data_set)
for i in range(depth-1):
new_center=find_center(parse_list)
parse_list=cluster(new_center,data_set)
draw_pic(parse_list)
'''
画散点图
'''
def draw_pic(data_list_set):
for i in range(len(data_list_set)):
parse_x=[]
parse_y=[]
for j in range(len(data_list_set[i])):
parse_x.append(data_list_set[i][j].x)
parse_y.append(data_list_set[i][j].y)
mlp.scatter(parse_x,parse_y,c=numpy.random.rand(3,1),alpha=0.65,label="Team:"+str(i),s=40)
mlp.legend()
mlp.title("The Result From The Cluster")
mlp.show()
'''
得到一堆测试用的随机数
'''
def get_random_num(num=100):
data_set=[]
for i in range(num):
data_set.append(point(x=randint(1,100),y=randint(1,100)))
return data_set
'''
在第一次聚类后,寻找几个类的中心点,即是这个点到这个类的各个点的距离最短
'''
def find_center(data_set):
res=[]
for i in range(len(data_set)):
minn=100000000000000
min_p=None
for j in range(len(data_set[i])):
sumn=0
for h in range(len(data_set[i])):
sumn=sumn+get_distance(data_set[i][j],data_set[i][h])
if sumn<minn:
min_p=j
minn=sumn
if min_p!=None:
res.append(data_set[i][min_p])
return res
'''
遍历所有的点,得到输入的k个类
'''
def cluster(center_num,data_set):
the_clusted_list={}
for i in range(len(center_num)):
the_clusted_list[i]=[]
for i in range(len(data_set)):
maxn=0
p_to_center=None
for j in range(len(center_num)):
if get_distance(data_set[i],center_num[j])>maxn:
maxn=get_distance(data_set[i],center_num[j])
p_to_center=j
the_clusted_list[p_to_center].append(data_set[i])
return the_clusted_list
'''
这里的data_set为输入数据
'''
if __name__=="__main__":
data_set=get_random_num(num=300)
cluster_start(data_set=data_set)
我们将其输出,画成图就会得到,类似这样的结果:
其代码在这里:
k-means算法的劣处:
首先,先说清楚k-means算法的好处,他对于分类明显的数据集非常快速的能够操作
而且k-means便于理解,容易上手
- 但同时,他的计算量很大,运行比较慢
- 如果遇到,分类不明显的数据集,k-means就失效了,类似于:
或者,类似于:
这些就很难用了
不过,k-means有很多改良方案,可以对起精确度进行不断的优化
而且他容易上手,是data science从业人员非常好的工具帮手