目录
一、k-means 算法
二、NMS
一、k-means 算法
k-means 是一种无监督聚类算法，常用的聚类算法还有 DBSCAN。k-means 由于其原理简单，可解释强，实现方便，收敛速度快，在数据挖掘、数据分析、异常检测、模式识别、金融风控、数据科学、智能营销和数据运营等领域有着广泛的应用。具体实现步骤为：
- 设定 K 个类别的中心的初值；
- 计算每个样本到 K个中心的距离，按最近距离进行分类；
- 以每个类别中样本的均值，更新该类别的中心；
- 重复迭代以上步骤，直到达到终止条件（迭代次数、最小平方误差、簇中心点变化率）。
k-means 算法可以通过纯原生 python 语法实现，也可以通过 numpy 科学数据包实现。
纯原生 python 语法实现：
# 定义 List 求距离的函数
def getDistance(point1, point2, dim):
sum = 0
for i in range(dim):
sum += (point1[i]-point2[i])**2
return pow(sum, 0.5)
# 定义 List 求和的函数，引用调用
def getSum(point1, point2, dim):
for i in range(dim):
point1[i] += point2[i]
# 定义 List 求除法的函数，引用调用
def getDiv(point1, v, dim):
for i in range(dim):
point1[i] /= v
# 定义 List 深拷贝的函数
def deepCopy(det1, det2):
m, n = len(det1), len(det1[0])
for i in range(m):
for j in range(n):
det1[i][j] = det2[i][j]
# 定义主函数
def kmeans(dets, k, n):
nums, dim = len(dets), len(dets[0])
# 初始化旧的聚类中心，默认前k
center_old = []
for i in range(k):
center_old.append(dets[i][:]) # [:]是浅拷贝 == copy()
# 初始化新的聚类中心
center_new = []
for i in range(k):
center_new.append([0]*dim)
# 初始化一个记录的 List
center_num = [0]*dim
# 迭代 n 次
for _ in range(n):
for i in range(nums):
min_dis = 1e10
min_idx = 0
for j in range(k): # 基于最新距离找到第 i 数据的新的类别归属
dis = getDistance(dets[i], center_old[j], dim)
if min_dis > dis:
min_dis = dis
min_idx = j
getSum(center_new[min_idx], dets[i], dim) # 在新的类别归属上累计求和
center_num[min_idx] += 1 # 记录数量，以求均值
for i in range(k): # 求取均值，获得新的聚类中心
getDiv(center_new[i], center_num[i], dim)
deepCopy(center_old, center_new) # 将新的聚类中心赋值给旧的聚类中心
for i in range(k): # 清空新的聚类中心
for j in range(dim):
center_new[i][j] = 0
center_num[i] = 0
return center_old
if __name__ == "__main__":
x = [[1, 2], [1.5, 1.8], [5, 8], [8, 8], [1, 0.6], [9, 11]]
y = kmeans(x, 2, 50)
print(y) # 结果为：[[1.1667, 1.4666], [7.3333, 9.0]]numpy 科学数据包实现：参考
class Kmeans:
def __init__(self, k=2, tolerance=0.01, max_iter=300):
self.k = k
self.tol = tolerance
self.max_iter = max_iter
self.features_count = -1
self.classifications = None
self.centroids = None
def fit(self, data):
"""
:param data: numpy数组，约定shape为：(数据数量，数据维度)
:type data: numpy.ndarray
"""
self.features_count = data.shape[1]
# 初始化聚类中心（维度：k个 * features种数）
self.centroids = np.zeros([self.k, data.shape[1]])
for i in range(self.k):
self.centroids[i] = data[i]
for i in range(self.max_iter):
# 清空聚类列表
self.classifications = [[] for i in range(self.k)]
# 对每个点与聚类中心进行距离计算
for feature_set in data:
# 预测分类
classification = self.predict(feature_set)
# 加入类别
self.classifications[classification].append(feature_set)
# 记录前一次的结果
prev_centroids = np.ndarray.copy(self.centroids)
# 更新中心
for classification in range(self.k):
self.centroids[classification] = np.average(self.classifications[classification], axis=0)
# 检测相邻两次中心的变化情况
for c in range(self.k):
if np.linalg.norm(prev_centroids[c] - self.centroids[c]) > self.tol:
break
# 如果都满足条件（上面循环没break），则返回
else:
return
def predict(self, data):
# 距离
distances = np.linalg.norm(data - self.centroids, axis=1)
# 最小距离索引
return distances.argmin()二、NMS
1. NMS
非极大值抑制 (Non-maximum supression) 简称 NMS，其作用是去除冗余的检测框，去冗余手段是剔除与极大值重叠较多的检测框结果。 通常我们所说的 NMS 指的是标准 NMS，非标准的 NMS 还有 soft NMS 和 softer NMS 参考 参考。那么为什么一定要去冗余呢？因为图像中的目标是多种多样的形状、大小和长宽比，目标检测算法中为了更好的保障目标的召回率，通常会使用 SelectiveSearch、RPN (例如：Faster-RCNN)、Anchor (例如：YOLO) 等方式生成长宽不同、数量较多的候选边界框 (BBOX)。因此在算法预测生成这些边界框后，紧接着需要跟着一个 NMS 后处理算法，进行去冗余操作，为每一个目标输出相对最佳的边界框，依次作为该目标最终检测结果。默认的两个框相似度的评判工具是 IOU，其它常用的还有 GIOU、DIOU、CIOU、EIOU 参考参考。
一般NMS后处理算法需要经历以下步骤（不含背景类，背景类无需NMS）：
step1：先将所有的边界框按照类别进行区分；
step2：把每个类别中的边界框，按照置信度从高到低进行降序排列；
step3：选择某类别所有边界框中置信度最高的边界框bbox1，然后从该类别的所有边界框列表中将该置信度最高的边界框bbox1移除并同时添加到输出列表中；
step4：依次计算该bbox1和该类别边界框列表中剩余的bbox计算IOU；
step5：将IOU与NMS预设阈值Thre进行比较，若某bbox与bbox1的IOU大于Thre，即视为bbox1的“邻域”，则在该类别边界框列表中移除该bbox，即去除冗余边界框；
step6：重复step3~step5，直至该类别的所有边界框列表为空，此时即为完成了一个物体类别的遍历；
step7：重复step2~step6，依次完成所有物体类别的NMS后处理过程；
step8：输出列表即为想要输出的检测框，NMS流程结束。
import numpy as np
def IOU(point, points):
# 计算交集面积
lu = np.maximum(point[0:2], points[:, 0:2])
rd = np.minimum(point[2:4], points[:, 2:4])
intersection = np.maximum(0, rd-lu)
inter_area = intersection[:,0]*intersection[:,1]
# 计算每个框的单独面积
area1 = (point[2]-point[0])*(point[3]-point[1])
area2 = (points[:,2]-points[:,0])*(points[:,3]-points[:,1])
union_area = np.maximum(area1+area2-inter_area, 1e-10)
# 计算交并比
return inter_area/union_area
def nms(dets, thresh):
points = dets[:,:4]
score = dets[:,4]
order = score.argsort()[::-1]
keep = []
while order.size > 0:
i = order[0]
keep.append(i)
ious = IOU(points[i,:], points[order[1:]]) # 当order.size==1时，order[1]会报错，但order[1:]不会报错
inds = np.where(ious<=thresh)[0] # 对于IOU函数，order[1:]不会报错，但np.array([])则会报错
order = order[inds+1] # 定义函数时，不需要特殊处理，numpy会自动帮忙处理这种情况
return keep
if __name__ == "__main__":
dets = np.array([
[30, 10, 200, 200, 0.95],
[25, 15, 180, 220, 0.98],
[35, 40, 190, 170, 0.96],
[60, 60, 90, 90, 0.3],
[20, 30, 40, 50, 0.1],
])
print(nms(dets, 0.5))2. soft-NMS
由于 NMS 直接删除所有 IOU 大于阈值的框，这种做法是粗暴的，有可能会漏检目标。因此，softe-nms 吸取了 NMS 的教训，在算法执行过程中不是简单的对 IOU 大于阈值的检测框删除，而是降低得分。soft-NMS 算法流程同 NMS 相同，但是对原置信度得分使用函数运算，目标是降低置信度得分。相比原 NMS 算法，只是将删除 IOU 过大框的操作修改为将 IOU 过大框的置信度降低。具体降低置信度的方法一般有两种，如下，分别是线性加权和高斯加权法。当所有 Box 都运算一遍后，将最终得分小于阈值的 Box 删除。
线性加权：
高斯加权：
import numpy as np
def soft_nms(boxes, thresh=0.3, sigma2=0.5, score_thresh=0.5, method=1):
"""
:param boxes: 检测结果 n*5 前4列是x1y1x2y2, 第5列是置信度
:param thresh: IOU阈值
:param sigma2: 高斯函数中用到的sigma
:param score_thresh: 置信概率分数阈值
:param method: soft-nms对应1或者2, 传统nms对应0
:return: 最终保留的boxes的索引号
"""
# 初始化参数
N = boxes.shape[0]
indexs = [i for i in range(N)]
# 得到每个box的左上角和右下角坐标并得到每个box的面积
x1 = boxes[:, 0]
y1 = boxes[:, 1]
x2 = boxes[:, 2]
y2 = boxes[:, 3]
areas = (y2-y1+1)*(x2-x1+1)
# 得到每个box的得分
scores = boxes[:, 4]
# 用keep存放保留的数据的索引并完成初始化，用keep_scores存放保留的数据的得分，该得分是乘以系数降低后的分数
# 其实keep保存了所有得分非0的数据和得分，所有得分非0数据调整了数据的优先级进行排序，优先级逐步降低，最后再通过阈值去除一部分数据
keep = []
keep_scores = []
pos = np.argmax(scores, axis=0)
pos_scores = np.max(scores, axis=0)
keep.append(pos)
keep_scores.append(pos_scores)
# 处理N-1次
for _ in range(N):
# 通过index-keep找到所有未检查的数据
b = list(set(indexs).difference(set(keep)))
# 计算当前pos数据与所有未检查数据的IOU
# 计算交集的左上角和右下角
x11 = np.maximum(x1[pos], x1[b])
y11 = np.maximum(y1[pos], y1[b])
x22 = np.minimum(x2[pos], x2[b])
y22 = np.minimum(y2[pos], y2[b])
# 如果两个方框相交, x22-x11, y22-y11是正的, 如果两个方框不相交，x22-x11, y22-y11是负的，将不相交的w和h设为0
w = np.maximum(0, x22-x11)
h = np.maximum(0, y22-y11)
# 计算重叠交集的面积
overlaps = w*h
# 计算IOU, IOU公式（交集/并集）
ious = overlaps / (areas[pos] + areas[b] - overlaps)
# IOU大于阈值的重新赋值分数，大于阈值被认为是重叠度过高
weight = np.ones(ious.shape)
# Three methods: 1.linear 2.gaussian 3.original NMS
if method == 1:
weight[ious>thresh] = weight[ious>thresh] - ious[ious>thresh]
elif method == 2:
weight[ious>thresh] = np.exp(-(ious[ious>thresh])**2/sigma2)
else:
weight[ious>thresh] = 0
scores[b] = weight*scores[b]
# 更新pos, pos_scores, keep, keep_scores
b_scores = scores[b]
if np.any(b_scores) == 0: # 如果全为0则不再继续循环
break
pos = b[np.argmax(b_scores, axis=0)]
pos_scores = np.max(b_scores, axis=0)
keep.append(pos)
keep_scores.append(pos_scores)
# score约束
keep = np.array(keep)
keep_scores = np.array(keep_scores)
indx = keep[keep_scores>=score_thresh]
return indx
if __name__ == "__main__":
a = np.array([[191, 89, 413, 420, 0.80], # 0
[281, 152, 573, 510, 0.99], # 1
[446, 294, 614, 471, 0.65], # 2
[50, 453, 183, 621, 0.98], # 3
[109, 474, 209, 635, 0.78]]) # 4
nms_result = soft_nms(a)
print(a[nms_result])3. softer-NMS
以上两种 NMS 算法都忽略了一个问题，就是 NMS 时用到的 score 仅仅是分类置信度得分，不能反映 Bounding Box 的定位精准度，既分类置信度和定位置信非正相关的。因此， softer-NMS 改进了预测模型，原本预测模型输出为 4+1+nClass，其中 4 为 xywh，修改后的模型输出为 8+1+nClass，其中 8 为 x1_u、x1_std、y1_u、y1_std、x2_u、x2_std、y2_u、y2_std，这里用一个预测的高斯分布描述预测坐标的准确度。softer-NMS 的算法流程同 soft-NMS 相同。唯一的区别是在每次循环中，当排在首位的 Box 找到与其重叠度很高 (IOU 大于 thresh) 的一组 Box 后，除了基于 IOU 对这一组 Box 的 score 进行降低外，还需要基于这一组 Box 对排在首位的 Box 的坐标进行加权求平均，权重因子就是每个 Box 的坐标方差的倒数。在训练过程中，可以认为预测输出的 u 和 std 构成一个高斯分布，而真值 x 构成一个脉冲分布 (狄拉克 delta 分布)，采用 KL 散度作为损失函数用于评价预测分布与真值分布之间的误差。
import numpy as np
def softer_nms(dets, confidence, thresh=0.6, score_thresh=0.7, sigma=0.5):
"""
:param boxes: 检测结果 n*5 前4列是x1_u,y1_u,x2_u,y2_u, 第5列是置信度
:param confidence: 检测结果 n*4 是x1_std,y1_std,x2_std,y2_std
:param thresh: IOU阈值
:param score_thresh: 置信概率分数阈值
:param sigma: 高斯函数中用到的sigma
:return: 最终保留的boxes
"""
# 初始化参数
N = dets.shape[0]
# 构建一个N*N的矩阵，第i-j表示第i个box与第j个box之间的IOU
# 获取每个box的左上角和右下角坐标，直接=号是引用，后面会对dets做改变，所以这里需要浅拷贝
x1 = dets[:, 0].copy()
y1 = dets[:, 1].copy()
x2 = dets[:, 2].copy()
y2 = dets[:, 3].copy()
# 计算每个box的面积，用于IOU的计算
areas = (x2-x1)*(y2-y1)
# 预定义IOU矩阵
ious = np.zeros((N,N))
# 循环计算IOU，这里存在重复计算，其实可以优化一下！！！
for i in range(N):
# 计算交集坐标
xx1 = np.maximum(x1[i], x1)
yy1 = np.maximum(y1[i], y1)
xx2 = np.minimum(x2[i], x2)
yy2 = np.minimum(y2[i], y2)
# 计算交集宽高
w = np.maximum(0.0, xx2-xx1)
h = np.maximum(0.0, yy2-yy1)
# 计算交集面积
inter = w*h
# 计算IOU
ious[i, :] = inter/(areas[i] + areas - inter)
# 遍历循环N次，调整每个box的坐标(在IOU大于阈值的box中依照坐标方差加权求平均)，以及按照优先级调整排序
i = 0
while i < N:
# 找到i到n-1索引中的极大值索引，作为该轮循环中的待调整box，这里可以优化，如果最大值过小，就跳出循环！！！
maxpos = dets[i:N, 4].argmax()
maxpos += i
# 对调第i和第maxpos的位置，让maxpos成为本轮循环的待调整box和最高优先级box，排位在最靠前位置，如此操作会比较耗时，可以优化为只对索引操作！！！
dets[[maxpos, i]] = dets[[i, maxpos]]
confidence[[maxpos, i]] = confidence[[i, maxpos]]
areas[[maxpos, i]] = areas[[i, maxpos]]
ious[[maxpos, i]] = ious[[i, maxpos]]
ious[:,[maxpos, i]] = ious[:,[i, maxpos]]
# 找到与待调整box的IOU大于阈值的box，利用这些box的坐标调整待调整box的坐标，1/confidence是加权参数
ovr_bbox = np.where(ious[i,:N]>thresh)[0]
avg_std_bbox = ((dets[ovr_bbox,:4] / confidence[ovr_bbox]).sum(0)) / ((1/confidence[ovr_bbox]).sum(0))
dets[i, :4] = avg_std_bbox
# 利用待调整box调整从i+1到N-1中与其重叠度过高的box的得分，与soft-nms一模一行，这里也可以优化为矩阵运算！！！
pos = i + 1
while pos < N:
if ious[i , pos] > 0:
# 得到IOU并利用高斯函数调整得分
ovr = ious[i, pos]
dets[pos, 4] *= np.exp(-(ovr*ovr)/sigma)
# 如果得分过低，可以将其移到最后，这里其实有点浪费，即使没有这部分代码，经过N-1个循环后，最小得分的也都是在最后，可以优化！！！
if dets[pos, 4] < score_thresh:
dets[[pos, N-1]] = dets[[N-1, pos]]
confidence[[pos, N-1]] = confidence[[N-1, pos]]
areas[[pos, N-1]] = areas[[N-1, pos]]
ious[[pos, N-1]] = ious[[N-1, pos]]
ious[:,[pos, N-1]] = ious[:,[N-1, pos]]
N -= 1 # 减少循环的次数
pos -= 1
pos += 1
i += 1
return dets[:N, :]
if __name__ == "__main__":
a = np.array([[191, 89, 413, 420, 0.80], # 0
[281, 152, 573, 510, 0.99], # 1
[446, 294, 614, 471, 0.65], # 2
[50, 453, 183, 621, 0.98], # 3
[109, 474, 209, 635, 0.78]]) # 4
b = np.array([[1, 1, 1, 1], # 0
[1, 1, 1, 1], # 1
[1, 1, 1, 1], # 2
[1, 1, 1, 1], # 3
[1, 1, 1, 1]]) # 4
nms_result = softer_nms(a, b)
print(nms_result)
