即日起在codingBlog上分享您的技术经验即可获得积分,积分可兑换现金哦。

K-Means算法

编程语言 nextstepfans 11℃ 0评论
本文目录
[隐藏]

K-Means算法的基本思想是初始随机给定K个簇中心,按照最邻近原则把待分类样本点分到各个簇。然后按平均法重新计算各个簇的质心(这个点可以不是样本点),从而确定新的簇心。一直迭代,直到簇心的移动距离小于某个给定的值。


下面给出Python下面的算法

1.!usr/bin/python

2.! –– coding:utf-8 –

from numpy import *


import matplotlib.pyplot as plt

3.首先把数据给加载进来,定义一个函数,加载原始数据

def load_data(file_dir):


fstr = open(file_dir,’r’)


data_mat = []


#创建一个空的列表,用来加载需要处理的数据


for line in fstr :


row = line.split()


#此函数的方法是对原始数据进行加工,打碎重组


#每一行原始数据为列表的一行,每一行遇到空格则处理成每行的一个数据


row = map(float,row)


#map函数的参数为2个 map(A,B)


#A 为函数,B为序列,map将传入的函数依次作用到序列的每个元素,并且把结果


#把结果作为新的list返回


#以此处为例,是把row的数据处理成float的类型便于后期数据的处理


data_mat.append(row)


#把处理好的每行数据加入到开始创建的空数组data_mat中


return mat(data_mat)


#mat函数。把数组处理成对应的矩阵

4.计算欧几里得距离

def dist_enclid(vec1,vec2):


return sqrt(sum(power((vec1 – vec2),2)))


#公式 v1-v2 的平方的总和加起来,开根号

5.第一步,通过随机数首先找出k个随机簇点

def rand_centroids(data_mat,k):


ndim = shape(data_mat)[1]


#shape()[0],shape()[1],此函数的返回值是一个int


#如果[]为0,则计数该矩阵的行数,为1则计数该矩阵的列数


centroids = mat(zeros([k,ndim]))


#zeros([n,m]),zeros函数为生成n行m列的一个0数组


#此处的目的是生成一个放簇点的矩阵


for j in range(ndim):


#此循环的目的是为了找出原始数据中每一列的最大值和最小值


min_j = min(data_mat[:,j])


max_j = max(data_mat[:,j])


range_j = float(max_j – min_j)


centroids[:,j] = min_j +range_j *random.rand(k,1)


#random.rand(n,m),此函数的用法是生成一个n行m列的一个随机数从0~1的矩阵


#此处生成的是k行1列的矩阵


#在centroids的[:j]的切片中,把每一列生成的随机数加到centroids矩阵中


return centroids

6.kmeans算法核心

def kmeans(data_mat,k,gen_centrtoid = rand_centroids,dist_measure = dist_enclid):


#此处特别之处在于,它把前面我们定义的函数,当做参数


nrow = shape(data_mat)[0]


#shape函数取出原始数据矩阵的行数


cluster_assign = mat(zeros([nrow,2]))


#生成一个nrow行,2列的矩阵,目的后面装簇


centroids = gen_centrtoid(data_mat,k)


#此函数调用,目的是第一步生成的随机簇


cluster_changed = True


#设置一个标签,用来判断簇什么时候稳定


while cluster_changed:


cluster_changed = False


for i in range(k):


dist_min = inf #先设定一个最小值


index_min = -1


for j in range(k):


#双重循环,目的是为了找出每组数据和簇之间的距离


dist_ij = dist_measure(data_mat[i,:],centroids[i,:])


if dist_ij < dist_min:


dist_min = dist_ij


index_min = j


#此处找出每次的最小距离和最小距离


if cluster_assign[i,0] != index_min:


cluster_changed = True


cluster_assign[i,0] = index_min


#在装簇的矩阵中装入最小距离的下标,装在二维矩阵的第一列


cluster_assign[i,1] = dist_min ** 2


#在装簇的矩阵中装入最小距离,装在二维矩阵的第二列


#这样生成的装簇的矩阵的中,每行的第一个元素表示小标,第二个元素表示距离


for cent in range(k):


pts_in_cluster_cent = data_mat[nonzero(cluster_assign[:, 0]==cent)[0], :]


#nonzero函数生成的是代表真值的下标,


centroids[cent, :] = mean(pts_in_cluster_cent, axis=0)


return centroids,cluster_assign

7.可视化

def visual_clustering(data_mat, centroids, cluster_assign):


x_cord = data_mat[:, 0].T


y_cord = data_mat[:, 1].T


x_cen = transpose(centroids[:, 0])


y_cen = transpose(centroids[:, 1])


# plt.plot(x_cord, y_cord, ‘ro’)

k = len(centroids)

style_set = ['o', '^', 'yh', '>']

for i in range(k):
    # print nonzero(cluster_assign[:, 0] == i)
    pts_in_cluster_i = data_mat[nonzero(cluster_assign[:, 0] == i)[0], :]
    marker_style = style_set[i]
    plt.plot(pts_in_cluster_i[:,0], pts_in_cluster_i[:,1], marker_style)
plt.plot(x_cen, y_cen, 'b+', markersize=12)
plt.show()

def main():


file_dir = “C:/testSet.txt”


data_mat = load_data(file_dir)


k = 4


centroids = rand_centroids(data_mat,k)


centroids,cluster_assign = kmeans(data_mat,k)


visual_clustering(data_mat, centroids, cluster_assign)

if name == ‘main‘:


main()

  • 列表内容

转载请注明:CodingBlog » K-Means算法

喜欢 (0)or分享 (0)
发表我的评论
取消评论

*

表情