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

目录

一、k-means 算法

二、NMS

1. NMS

2. soft-NMS

3. softer-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 的坐标方差的倒数，需要注意的是修改 score 所用的 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)