深度学习常用代码总结(k-means, NMS)

一、k-means 算法

二、NMS

一、k-means 算法

k-means 是一种无监督聚类算法，常用的聚类算法还有 DBSCAN。k-means 由于其原理简单，可解释强，实现方便，收敛速度快，在数据挖掘、数据分析、异常检测、模式识别、金融风控、数据科学、智能营销和数据运营等领域有着广泛的应用。具体实现步骤为：

设定 K 个类别的中心的初值；
计算每个样本到 K个中心的距离，按最近距离进行分类；
以每个类别中样本的均值，更新该类别的中心；
重复迭代以上步骤，直到达到终止条件（迭代次数、最小平方误差、簇中心点变化率）。

k-means 算法可以通过纯原生 python 语法实现，也可以通过 numpy 科学数据包实现。

纯原生 python 语法实现：

# 定义 List 求距离的函数
def getDistance(point1, point2, dim):sum = 0for i in range(dim):sum += (point1[i]-point2[i])**2return 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])# 初始化旧的聚类中心，默认前kcenter_old = []for i in range(k):center_old.append(dets[i][:])  # [:]是浅拷贝 == copy()# 初始化新的聚类中心center_new = []for i in range(k):center_new.append([0]*dim)# 初始化一个记录的 Listcenter_num = [0]*dim# 迭代 n 次for _ in range(n):for i in range(nums):min_dis = 1e10min_idx = 0for j in range(k):  # 基于最新距离找到第 i 数据的新的类别归属dis = getDistance(dets[i], center_old[j], dim)if min_dis > dis:min_dis = dismin_idx = jgetSum(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] = 0center_num[i] = 0return center_oldif __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 = kself.tol = toleranceself.max_iter = max_iterself.features_count = -1self.classifications = Noneself.centroids = Nonedef 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:returndef 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 npdef 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_areadef 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 keepif __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 npdef 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设为0w = 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 NMSif 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] = 0scores[b] = weight*scores[b]# 更新pos, pos_scores, keep, keep_scoresb_scores = scores[b]if np.any(b_scores) == 0: # 如果全为0则不再继续循环breakpos = 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 indxif __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]])    # 4nms_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 npdef 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# 计算IOUious[i, :] = inter/(areas[i] + areas - inter)# 遍历循环N次，调整每个box的坐标(在IOU大于阈值的box中依照坐标方差加权求平均)，以及按照优先级调整排序i = 0while 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 + 1while 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 -= 1pos += 1i += 1return 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]])    # 4b = 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]])     # 4nms_result = softer_nms(a, b)print(nms_result)