做网站都需要什么东西,各种网站开发语言的优缺点,成都网站建设是什么意思,django和wordpress目录 一、k-means 算法
二、NMS 一、k-means 算法
k-means 是一种无监督聚类算法#xff0c;常用的聚类算法还有 DBSCAN。k-means 由于其原理简单#xff0c;可解释强#xff0c;实现方便#xff0c;收敛速度快#xff0c;在数据挖掘、数据分析、异常检测、模式识别、金…目录 一、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, k2, tolerance0.01, max_iter300):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.ndarrayself.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], axis0)# 检测相邻两次中心的变化情况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, axis1)# 最小距离索引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(area1area2-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.size1时order[1]会报错但order[1:]不会报错inds np.where(iousthresh)[0] # 对于IOU函数order[1:]不会报错但np.array([])则会报错order order[inds1] # 定义函数时不需要特殊处理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, thresh0.3, sigma20.5, score_thresh0.5, method1)::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-y11)*(x2-x11)# 得到每个box的得分scores boxes[:, 4]# 用keep存放保留的数据的索引并完成初始化用keep_scores存放保留的数据的得分该得分是乘以系数降低后的分数# 其实keep保存了所有得分非0的数据和得分所有得分非0数据调整了数据的优先级进行排序优先级逐步降低最后再通过阈值去除一部分数据keep []keep_scores []pos np.argmax(scores, axis0)pos_scores np.max(scores, axis0)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[iousthresh] weight[iousthresh] - ious[iousthresh]elif method 2:weight[iousthresh] np.exp(-(ious[iousthresh])**2/sigma2)else:weight[iousthresh] 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, axis0)]pos_scores np.max(b_scores, axis0)keep.append(pos)keep_scores.append(pos_scores)# score约束keep np.array(keep)keep_scores np.array(keep_scores)indx keep[keep_scoresscore_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 改进了预测模型原本预测模型输出为 41nClass其中 4 为 xywh修改后的模型输出为 81nClass其中 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, thresh0.6, score_thresh0.7, sigma0.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调整从i1到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)
