k-means聚类:讲解与实现

2016-03-01 16:08:59

本博客采用创作共用版权协议, 要求署名、非商业用途和保持一致. 转载本博客文章必须也遵循署名-非商业用途-保持一致的创作共用协议

终于可以开始更新我的机器学习系列的博文了,因为刚刚开始,所以涉及的东西不深,先写写最简单的k-means聚类吧

话说最近终于找到了机器学习相关的科研,而且最近遇到几个靠谱的程序员,能帮忙参考意见,还有的已经有了发paper的精力,真是抱大腿啊,加上这学期课少,想想就让人想奋进!!!!这学期必须炼成金刚不坏身,好到了朝阳区继续战斗啊

还记得一个开发前辈这么评价程序员:

即使是一个人,也要像一支军队一样战斗

頑張ってる、!!!!!

以上都是唠叨,请忽视


k-means介绍


首先,作为一个 data science的从业人员,最经常遇到的情况就是,一大堆的表,所谓的表,就是一个对象,基于的坐标量的数值(比如x,y轴)的一个集合

那么,所有的data science人员都想一件事,就是如何让这些数据说话,这样才能从这些人类活动产生的抽象意义的信息产生二次价值

那么把它归类就是一个很好的选择

那么,他们只是数据,我们要怎么把他们归类呢?或者说他们的抽象意义太大,如何归类。

所以就有人提出了k-means聚类方法,它是基于欧式距离聚类,核心公式为:

pic

而他的基本步骤是这样的:

pic

也就是这样:

  • 首先,你先有一堆堆的数据集,他们可以表达成一个list:data[1]=[2,5,7,...],其中,list里面的每一个值都有实际价值,例如,小明的各科成绩就可以表达成:xiaoming_score=[98,99,100...],这样,我们就可以针对这些数据,把好学生类,和坏学生类分出来了,但这里有一点需要说明,就好比高考时物理是120分,而生物只有72分一样,不同的数据类的标准不一样,而对于这种加权怎么加就看情况而定,不过一般我们要做 归一化处理,这往往能提高数据处理结果的准确性
  • 接着,如果是k-means的话,一般使用欧式距离(euclidean metric)

pic

  • 我们会先随机k个值(randintNum),每个值在一定的区间内
  • 接着我们遍历所有数据点,用欧式距离,算出来这个点和每个随机点(randintNum)的距离,并把它归入距离最小的那个随机点(randintNum)的类,这样我们便得到了大概的几个类
  • 然后,我们把这几个类里面的每一个点,去算他和其他的在这个类的点的距离,找到这个类的几何坐标中心
  • 得到的每一个类的几何坐标中心后,再吧这几个中心当成随机点(randintNum)重复聚类操作,
  • 这样重复的次数越多,类的精确性就越大

下图为上面操作的图示,可以看到,重复多次之后,我们得到了较为满意的聚类结果: pic

最后的结果,比较明显的话,会变成类似这样:

pic

pic


下面是这个聚类算法的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)

我们将其输出,画成图就会得到,类似这样的结果: pic

其代码在这里:

代码实现

k-means算法的劣处:


首先,先说清楚k-means算法的好处,他对于分类明显的数据集非常快速的能够操作

而且k-means便于理解,容易上手

  • 但同时,他的计算量很大,运行比较慢
  • 如果遇到,分类不明显的数据集,k-means就失效了,类似于:

pic

或者,类似于:

pic

这些就很难用了

不过,k-means有很多改良方案,可以对起精确度进行不断的优化

而且他容易上手,是data science从业人员非常好的工具帮手

机器学习 返回首页

Designed and built with all the love in the world by the Mr.ALJUN.

@SERVER BY NGINX AND POWER BY DIGITALOCEAN.

© COPYRIGHT BY GAGASALAMER 2015