1. 均值漂移的基本概念
Mean Shift算法和k-means相似，都是⼀个迭代的过程，即先算出当前点的偏移均值，将该点移动到该偏移均值，以此为新的起始点，继续移动，直到满⾜最终的条件。 （1）设想在⼀个有N个样本点的特征空间，初始确定⼀个中⼼点center；
（2）计算在设置的半径为D的圆形空间内所有的点（xi）与中⼼点center的向量； （3）计算整个圆形空间内所有向量的平均值，得到⼀个偏移均值
（4）将中⼼点center移动到偏移均值位置；
（5）重复移动，直到满⾜⼀定条件结束。
2. 均值漂移计算
2.1 实施步骤
1、在未被分类的数据点中随机选择⼀个点作为中⼼点；
2、出离中⼼点距离在带宽之内的所有点，记做集合M，认为这些点属于簇c。
3、计算从中⼼点开始到集合M中每个元素的向量，将这些向量相加，得到偏移向量。
4、中⼼点沿着shift的⽅向移动，移动距离是偏移向量的模。
5、重复步骤2、3、4，直到偏移向量的⼤⼩满⾜设定的阈值要求，记住此时的中⼼点。
6、重复1、2、3、4、5直到所有的点都被归类。
7、分类：根据每个类，对每个点的访问频率，取访问频率最⼤的那个类，作为当前点集的所属类。
2.2 第⼀种⽅法：Mean Shift基础公式
偏移均值（中⼼点减去每个样本点，然后求和，除以点的个数得到）：
这⾥的S(h)是⼀个以x为中⼼点，半径为h的⾼维球区域，满⾜以下等式关系的y点的集合，
上⾯等式中的k值表⽰在这n个样本点x(i)中，有k个点落⼊S(h)区域，在上式中，我们可以看到(x(i) - x)是样本x(i)相对于点x的偏移向量，上⾯式⼦做的就是落⼊区域S(h)中的k个样本点相对于点x偏移向量求和然后再平均，那么如果样本点x(i)从⼀个概率密度函数f(x)中采样得到，由于⾮零的概率密度梯度指向概率密度增⼤的最⼤的⽅向， 因此从平均上来说，S(h)的样本点更多的是落在沿着概率密度梯度的⽅向，因此，对应的，
Mean Shift向量M(x)应该指向概率密度梯度的⽅向。
如上图所⽰，⼤圆圈所圈住的是S区域，⼩圆圈表⽰落⼊S区域的样本点x(i), ⿊⾊的点就是Mean Shift的基准点x，箭头表⽰样本点相对于基准点x的偏移向量，很明显我们可以看出，平均的偏移M(x)会指向样本分布最多的区域，也就是概率密度函数梯度的⽅向。
注：在上⾯式⼦中看到，只要是落⼊S区域的采样点，⽆论其离中⼼点x的远近，对最终M(x)的计算的贡献是⼀样的。然⽽在这个迭代的过程中，每个x(i)对于求解均值时的贡献是不同的，所以这⾥引⼊了其他类型的核函数。
中⼼点更新，将中⼼点移动到偏移均值位置：
Mt为t状态下求得的偏移均值; xt为t状态下的中⼼
下⾯讲引⼊⾼斯核函数的⽅式。
2.3 第⼆种⽅法：引⼊核函数改进Mean Shift算法
核函数的定义：
在Mean Shift算法中引⼊核函数的⽬的是使得随着样本与被偏移点的距离的不同，其偏移量对均值偏移向量的贡献也不同，下⾯看下核函数的定义：
核函数也叫窗⼝函数，在核估计中起到平滑的作⽤。
⾼斯核函数：
⾼斯核函数只是⽤来计算映射到⾼维空间之后的内积的⼀种简便⽅法，⽬的为让低维的不可分数据变成⾼维可分。利⽤核函数，可以忽略映射关系，直接在低维空间中完成计算。
引⼊⾼斯核函数的偏移均值
在均值漂移中引⼊核函数的概念，能够使计算中距离中⼼的点具有更⼤的权值，反映距离越短，权值越⼤的特性。改进的偏移均值如下：
把mh代⼊Mh则可以得到下列公式，正好印证了梯度上升的过程：
其中，x为中⼼点；xi为带宽范围内的点；n为带宽范围内的点的数量；g(x)为对核函数的导数求负。
孢子⾼斯核函数如下公式所⽰：
式⼦中的H如下⾯这个矩阵。
3. 均值漂移的应⽤
许鲜网Mean Shift算法在很多领域都有成功应⽤，例如图像平滑、图像分割、物体跟踪等，这些属于⼈⼯智能⾥⾯模式识别或计算机视觉的部分；另外也包括常规的聚类应⽤。 图像平滑：图像最⼤质量下的像素压缩；
图像分割：跟图像平滑类似的应⽤，但最终是将可以平滑的图像进⾏分离已达到前后景或固定物理分割的⽬的；
⽬标跟踪：例如针对监控视频中某个⼈物的动态跟踪；
常规聚类，如⽤户聚类等。聚类（K均值聚类）
对象轮廓检验（光线传播算法）
4. Python算法实现
import numpy as np
import matplotlib.pyplot as plt
# Input data set
X = np.array([
[-4, -3.5], [-3.5, -5], [-2.7, -4.5],
[-2, -4.5], [-2.9, -2.9], [-0.4, -4.5],
[-1.4, -2.5], [-1.6, -2], [-1.5, -1.3],
[-0.5, -2.1], [-0.6, -1], [0, -1.6],
[-2.8, -1], [-2.4, -0.6], [-3.5, 0],
[-0.2, 4], [0.9, 1.8], [1, 2.2],
[1.1, 2.8], [1.1, 3.4], [1, 4.5],
[1.8, 0.3], [2.2, 1.3], [2.9, 0],
[2.7, 1.2], [3, 3], [3.4, 2.8],
[3, 5], [5.4, 1.2], [6.3, 2]
])
校园记趣def mean_shift(data, radius=2.0):
clusters =[]
for i in range(len(data)):
cluster_centroid = data[i]
cluster_frequency = np.zeros(len(data))
# Search points in circle
while True:
temp_data =[]
for j in range(len(data)):
v= data[j]
# Handle points in the circles
if (v - cluster_centroid)<= radius:
if (v - cluster_centroid)<= radius:
temp_data.append(v)
cluster_frequency[i] += 1
# Update centroid
old_centroid = cluster_centroid
new_centroid = np.average(temp_data, axis=0)
cluster_centroid = new_centroid
# Find the mode
纪维时if np.array_equal(new_centroid, old_centroid):
break
# Combined 'same' clusters
has_same_cluster = False
for cluster in clusters:
if (cluster['centroid'] - cluster_centroid)<= radius:
has_same_cluster = True
cluster['frequency']= cluster['frequency'] + cluster_frequency
break
if not has_same_cluster:
clusters.append({
'centroid': cluster_centroid,
'frequency': cluster_frequency
})
print('clusters (', len(clusters), '): ', clusters)
clustering(data, clusters)
show_clusters(clusters, radius)
# Clustering data using frequency
def clustering(data, clusters):
t =[]
for cluster in clusters:
cluster['data']=[]
t.append(cluster['frequency'])
t = np.array(t)
# Clustering
for i in range(len(data)):
column_frequency = t[:, i]
cluster_index = np.where(column_frequency == np.max(column_frequency))[0][0] clusters[cluster_index]['data'].append(data[i])
# Plot clusters
def show_clusters(clusters, radius):
colors = 10 * ['r', 'g', 'b', 'k', 'y']
plt.figure(figsize=(5, 5))
plt.xlim((-8,8))
plt.ylim((-8,8))李民庆
plt.scatter(X[:, 0], X[:, 1], s=20)
theta = np.linspace(0, 2 * np.pi, 800)
for i in range(len(clusters)):
cluster = clusters[i]
data = np.array(cluster['data'])
plt.scatter(data[:, 0], data[:, 1], color=colors[i], s=20)
centroid = cluster['centroid']
plt.scatter(centroid[0], centroid[1], color=colors[i], marker='x', s=30)
x, y = np.cos(theta) * radius + centroid[0], np.sin(theta) * radius + centroid[1]
plt.plot(x, y, linewidth=1, color=colors[i])
三大改造plt.show()
mean_shift(X, 2.5)
import numpy as np
import math
MIN_DISTANCE = 0.00001 # 最⼩误差
def euclidean_dist(pointA, pointB):
# 计算pointA和pointB之间的欧式距离
豫公网安备41160202000603
站长QQ:729038198
关于我们
投诉建议