admin 管理员组

文章数量: 1086019

基于python的mean

一、Mean Shift算法概述

Mean Shift算法又称均值漂移算法，Mean Shift的概念最早是由Fukunage在1975年提出的，在后来又由Yzong Cheng对其进行扩充，主要提出了两点改进：

定义了核函数；

增加了权重系数。

核函数的定义使得偏移向量的贡献随着样本与被偏移点的距离的不同而不同。

权重系数使得不同样本的权重不同。Mean Shift算法在聚类，图像平滑，分割以及视频跟踪等方面有广泛的应用。

二、算法原理

2.1、核函数

 

常用的核函数有高斯核函数。高斯核函数如下所示：

其中，h称为带宽(bandwidth)，不同带宽的核函数如下图所示：

2.2、Mean Shift算法的核心思想

 

2.2.1、基本原理

对于Mean Shift算法，是一个迭代的过程，即先算出当前点的偏移均值，将该点移动到此偏移均值，然后以此为新的起始点，继续移动，直到满足最终的条件。

以上是官方的说法，即书上的定义，个人理解就是，在d维空间中，任选一个点，然后以这个点为圆心，h为半径做一个高维球，因为有d维，d可能大于2，所以是高维球。落在这个球内的所有点和圆心都会产生一个向量，向量是以圆心为起点落在球内的点位终点。然后把这些向量都相加。相加的结果就是Meanshift向量。

步骤1：在指定的区域内计算偏移均值(下图中黄色的圈)

步骤2：移动该点到偏移均值点处（如图，其中黄色箭头就是Mh（meanshift向量））

再以meanshift向量的终点为圆心，再做一个高维的球。如下图所以，重复以上步骤，就可得到一个meanshift向量。如此重复下去，meanshift算法可以收敛到概率密度最大得地方。也就是最稠密的地方。

步骤3： 重复上述的过程(计算新的偏移均值，移动)

步骤4： 满足最终的条件，即退出。下图便是最终的结果！

从上述过程可以看出，在Mean Shift算法中，最关键的就是计算每个点的偏移均值，然后根据新计算的偏移均值更新点的位置。

2.2.2、基本的Mean Shift向量形式

 

2.3、Mean Shift算法流程

 

复制代码
import matplotlib.pyplot as pltf = open("data")
x = []
y = []
for line in f.readlines():lines = line.strip().split("\t")if len(lines) == 2:x.append(float(lines[0]))y.append(float(lines[1]))
f.close()  plt.plot(x, y, 'b.', label="original data")
plt.title('Mean Shift')
plt.legend(loc="upper right")
plt.show()
复制代码
3.2 实验源码
复制代码
import math
import sys
import numpy as npMIN_DISTANCE = 0.000001#mini errordef load_data(path, feature_num=2):f = open(path)data = []for line in f.readlines():lines = line.strip().split("\t")data_tmp = []if len(lines) != feature_num:continuefor i in range(feature_num):data_tmp.append(float(lines[i]))data.append(data_tmp)f.close()return datadef gaussian_kernel(distance, bandwidth):m = np.shape(distance)[0]right = np.mat(np.zeros((m, 1)))for i in range(m):right[i, 0] = (-0.5 * distance[i] * distance[i].T) / (bandwidth * bandwidth)right[i, 0] = np.exp(right[i, 0])left = 1 / (bandwidth * math.sqrt(2 * math.pi))gaussian_val = left * rightreturn gaussian_valdef shift_point(point, points, kernel_bandwidth):points = np.mat(points)m,n = np.shape(points)#计算距离point_distances = np.mat(np.zeros((m,1)))for i in range(m):point_distances[i, 0] = np.sqrt((point - points[i]) * (point - points[i]).T)#计算高斯核      point_weights = gaussian_kernel(point_distances, kernel_bandwidth)#计算分母all = 0.0for i in range(m):all += point_weights[i, 0]#均值偏移point_shifted = point_weights.T * points / allreturn point_shifteddef euclidean_dist(pointA, pointB):#计算pointA和pointB之间的欧式距离total = (pointA - pointB) * (pointA - pointB).Treturn math.sqrt(total)def distance_to_group(point, group):min_distance = 10000.0for pt in group:dist = euclidean_dist(point, pt)if dist < min_distance:min_distance = distreturn min_distancedef group_points(mean_shift_points):group_assignment = []m,n = np.shape(mean_shift_points)index = 0index_dict = {}for i in range(m):item = []for j in range(n):item.append(str(("%5.2f" % mean_shift_points[i, j])))item_1 = "_".join(item)print(item_1)if item_1 not in index_dict:index_dict[item_1] = indexindex += 1for i in range(m):item = []for j in range(n):item.append(str(("%5.2f" % mean_shift_points[i, j])))item_1 = "_".join(item)group_assignment.append(index_dict[item_1])return group_assignmentdef train_mean_shift(points, kenel_bandwidth=2):#shift_points = np.array(points)mean_shift_points = np.mat(points)max_min_dist = 1iter = 0m, n = np.shape(mean_shift_points)need_shift = [True] * m#cal the mean shift vectorwhile max_min_dist > MIN_DISTANCE:max_min_dist = 0iter += 1print ("iter : " + str(iter))for i in range(0, m):#判断每一个样本点是否需要计算偏置均值if not need_shift[i]:continuep_new = mean_shift_points[i]p_new_start = p_newp_new = shift_point(p_new, points, kenel_bandwidth)dist = euclidean_dist(p_new, p_new_start)if dist > max_min_dist:#record the max in all pointsmax_min_dist = distif dist < MIN_DISTANCE:#no need to moveneed_shift[i] = Falsemean_shift_points[i] = p_new#计算最终的groupgroup = group_points(mean_shift_points)return np.mat(points), mean_shift_points, groupif __name__ == "__main__":#导入数据集path = "./data"data = load_data(path, 2)#训练，h=2points, shift_points, cluster = train_mean_shift(data, 2)for i in range(len(cluster)):print( "%5.2f,%5.2f\t%5.2f,%5.2f\t%i" % (points[i,0], points[i, 1], shift_points[i, 0], shift_points[i, 1], cluster[i]))

3，实验结果

经过Mean Shift算法聚类后的数据如下所示：

但在实际工作中的复杂数据用Mean-Shift来聚类因为无法控制k个值，可能会产生过多的类而导致聚类失去意义，但Mean-Shift在图像分割上用处很大 。

mean-shift算法的优缺点：

优点：

不需要设置簇类的个数；

可以处理任意形状的簇类；

算法只需设置带宽这一个参数，带宽影响数据集的核密度估计

算法结果稳定，不需要进行类似K均值的样本初始化

缺点：

聚类结果取决于带宽的设置，带宽设置的太小，收敛太慢，簇类个数过多；带宽设置的太大，一些簇类可能会丢失。

对于较大的特征空间，计算量非常大。

上便是本篇对Mean-Shift简单的介绍，如有错误望指出。

本文标签： 基于python的mean

版权声明：本文标题：基于python的mean 内容由网友自发贡献，该文观点仅代表作者本人， 转载请联系作者并注明出处：http://www.roclinux.cn/b/1693412408a220444.html， 本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容，一经查实，本站将立刻删除。