上篇的K-means算法得事先确定聚类簇的个数，而本篇将要介绍的Mean-Shift聚类法就可以自动确定k的个数，下面简要介绍一下其算法流程：
1.随机确定样本空间内一个半径确定的高维球及其球心；
2.求该高维球内质心，并将高维球的球心移动至该质心处；
3.重复2，直到高维球内的密度随着继续的球心滑动变化低于设定的阈值，算法结束。
如果当前簇C的center与其它已经存在的簇C2中心的距离小于阈值，那么把C2和C合并，数据点出现次数也对应合并。否则，把C作为新的聚类。
重复1、2、3、4、5直到所有的点都被标记为已访问。
分类：根据每个类，对每个点的访问频率，取访问频率最大的那个类，作为当前点集的所属类。
代码实现如下：
import numpy as np
import random
STOP_THRESHOLD = 1e-4
CLUSTER_THRESHOLD = 1e-1
def distance(a, b):
return np.linalg.norm(np.array(a) - np.array(b))
def gaussian_kernel(distance, bandwidth):
return (1 / (bandwidth * np.sqrt(2 * np.pi))) * np.exp(-0.5 * ((distance / bandwidth)) ** 2)
class MeanShift(object):
def __init__(self, kernel=gaussian_kernel):
self.kernel = kernel
def fit(self, points, kernel_bandwidth):
shift_points = np.array(points)
shifting = [True] * points.shape[0]
while True:
max_dist = 0
for i in range(0, len(shift_points)):
if not shifting[i]:
continue
p_shift_init = shift_points[i].copy()
shift_points[i] = self._shift_point(shift_points[i], points, kernel_bandwidth)#对样本进行漂移计算
dist = distance(shift_points[i], p_shift_init)#计算该点和漂移之后的点之间的距离
max_dist = max(max_dist, dist)
shifting[i] = dist > STOP_THRESHOLD
if(max_dist < STOP_THRESHOLD):
break
cluster_ids = self._cluster_points(shift_points.tolist())
return shift_points, cluster_ids
def _shift_point(self, point, points, kernel_bandwidth):
shift_x = 0.0
shift_y = 0.0
scale = 0.0
for p in points:
dist = distance(point, p)
weight = self.kernel(dist, kernel_bandwidth)
shift_x += p[0] * weight
shift_y += p[1] * weight
scale += weight
shift_x = shift_x / scale
shift_y = shift_y / scale
return [shift_x, shift_y]
def _cluster_points(self, points):
cluster_ids = []
cluster_idx = 0
cluster_centers = []
for i, point in enumerate(points):
if(len(cluster_ids) == 0):
cluster_ids.append(cluster_idx)
cluster_centers.append(point)
cluster_idx += 1
else:
for center in cluster_centers:
dist = distance(point, center)
if(dist < CLUSTER_THRESHOLD):
cluster_ids.append(cluster_centers.index(center))
if(len(cluster_ids) < i + 1):
cluster_ids.append(cluster_idx)
cluster_centers.append(point)
cluster_idx += 1
return cluster_ids
###from sklearn.datasets.samples_generator import make_blobs
from sklearn.datasets import make_blobs
import matplotlib.pyplot as plt
def colors(n):
ret = []
for i in range(n):
ret.append((random.uniform(0, 1), random.uniform(0, 1), random.uniform(0, 1)))
return ret
#import random
def main():
centers = [[-1, -1], [-1, 1], [1, -1], [1, 1]]
X, _ = make_blobs(n_samples=300, centers=centers, cluster_std=0.4,random_state=2)
#for i in range(300):
# Any number can be used in place of '11'.
# random.seed(11)
# Generated random number will be between 1 to 1000.
#X=(random.randint(1, 1000))
mean_shifter = MeanShift()
_, mean_shift_result = mean_shifter.fit(X, kernel_bandwidth=0.4)
np.set_printoptions(precision=3)
print('input: {}'.format(X))
print('assined clusters: {}'.format(mean_shift_result))
color = colors(np.unique(mean_shift_result).size)
for i in range(len(mean_shift_result)):
plt.scatter(X[i, 0], X[i, 1], color = color[mean_shift_result[i]])
plt.show()
if __name__ == '__main__':
main()
结果如下：
但在实际工作中的复杂数据用Mean-Shift来聚类因为无法控制k个值，可能会产生过多的类而导致聚类失去意义，但Mean-Shift在图像分割上用处很大 。
mean-shift算法的优缺点：
优点：
不需要设置簇类的个数；
可以处理任意形状的簇类；
算法只需设置带宽这一个参数，带宽影响数据集的核密度估计
算法结果稳定，不需要进行类似K均值的样本初始化
缺点：
聚类结果取决于带宽的设置，带宽设置的太小，收敛太慢，簇类个数过多；带宽设置的太大，一些簇类可能会丢失。
对于较大的特征空间，计算量非常大。
上便是本篇对Mean-Shift简单的介绍，如有错误望指出。
