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从业人员非常好的工具帮手