精华内容
下载资源
问答
  • Apriori关联算法讲解以及利用Python实现算法软件设计
    2022-01-29 19:46:52

    一、Apriori关联算法原理概述

    1.1 关联分析

    关联分析是一种在大规模数据集中寻找有趣关系的任务。这些关系可以有两种形式:
    (1) 频繁项集(frequent item sets): 经常出现在一块的物品的集合。
    (2)关联规则(associational rules): 暗示两种物品之间可能存在很强的关系。
    在这里插入图片描述频繁项集指的就是那些经常一起出现的物品集合,比如{啤酒,尿布,饼干}就是频繁项集中的一个例子,而根据上表也可以找到尿布->啤酒这样的关联规则。而我们是要通过关联分析大规模数据从而发现数据之间存在的有趣关系,那么问题来了,什么样的关系是有趣的呢?而这个有趣又是怎么定义的呢?我们可以通过支持度(support)和可信度(置信度confidence)来定义。一个项集的支持度指的是数据集中包含该项集记录所占的比例,上例中{豆奶}的支持度是2/5,{啤酒,尿布}的支持度是3/5;可信度是针对于像{尿布}->{啤酒}这样的关联规则来定义的,定义为:支持度({尿布,葡萄酒})/支持度(尿布)。

    1.2 Apriori 原理

    1.2.1 Apriori 算法流程步骤

    收集数据:使用任意方法
    准备数据:任何数据类型都可以,因为我们只保存集合
    分析数据:使用任意方法
    训练数据:使用Apiori算法来找到频繁项集
    测试算法:不需要测试过程
    使用算法:用于发现频繁项集以及物品之间的关联规则

    1.2.2 使用Apriori算法来发现频繁集

    Apriori 算法的两个输入参数分别是最小支持度和数据集。该算法首先会生成所有单个物品的项集列表。接着扫描交易记录来查看哪些项集满足最小支持度要求,那些不满足最小支持度要求的集合会被去掉。燃尽后对生下来的集合进行组合以声场包含两个元素的项集。接下来再重新扫描交易记录,去掉不满足最小支持度的项集。该过程重复进行直到所有项集被去掉。生成候选项集。

    1.2.3 从频繁项集中挖掘关联规则

    频繁项集可以使用Apriori算法寻找,当然下来就是要找出关联规则了。我们知道,假设有一个频繁项集,它们之间就有可能有一条关联规则,即可以表示为:"…—>…",但反过来并不一定成立(其中箭头左边对应的集合为前件,箭头右边对应的集合为后件)。在上一节,我们使用最小支持度来量化频繁项集,对应的,采用可信度来量化关联规则。其中一条规则p—>H的可信度定义为:support(P|H)/support§,为找到其中的关联规则,我们可以先生成一个可能的规则列表,然后测试每条规则的可信度,结合可信度的最小要求,得到关联规则。同寻找频繁项集类似,我们可以为每个频繁项集产生许多关联规则,这样就会有很多的关联规则产生。结合Apriori原理,如果某条规则不满足最小可信度要求,那么该规则的所有子集也就不满足最小可信度要求,据此我们可以减少需要测试的规则数目,简化问题。

    详细的Apriori算法大家都已经讲的很详细了,给大家推荐一篇优秀的博文:
    Apriori算法详解

    二、Python实现(重点来了!!!)

    为了方便用户便捷的应用Apriori算法计算,我计划搭建一个便捷的可视化操作界面。一个Apriori算法计算器,先带大家看看效果,若需完整代码请看链接:Apriori算法代码链接(大家私信我可免费发给大家)
    1、实验数据
    在这里插入图片描述

    在这里插入图片描述

    注:(1)搭建的平台有两个数据输入端口,一种是用户导入csv文件数据进行计算另一种的用户手动输入订单。故导入csv文件端口使用数据集①进行计算,手动输入端口使用数据集②进行计算。
    (2)数据集①于打包文件中的“样例数据.csv”中。

    2、实验说明及过程截图
    按照实验要求,本次实验使用python中的tkinter模块搭建计算关联规则的平台可视化界面,平台名称为“5433关联规则计算平台”。平台主界面截图如下:
    在这里插入图片描述
    主界面主要介绍了平台使用计算关联规则的两个算法,分类是Apriori算法与FP-tree算法。Apriori算法简单且易于实现,是最具代表性的关联规则挖掘算法。但是Apriori算法需要频繁的对数据库进行扫描,这大大增长了计算时间。因此本次太在Apriori的基础上加入FP-tree算法计算通道,FP-tree算法秩序进行两次扫描便可以对所有可能的频繁项进行计数。
    点击“从本地文件读入数据”按钮,跳转到读入数据界面。从文件读入数据界面截图如下:
    在这里插入图片描述在这里插入图片描述可见用户只需选择文件路径平台即可自动将文件中的数据读入平台数据库。同时用户可根据数据集的需要设置最小支持度与最小置信度。点击“Apriori计算”或“FP-tree计算”即可进入计算界面。若数据集过大建议使用FP-tree计算。后即可进入结果展示界面查看计算结果。结果展示界面截图如下:
    在这里插入图片描述点击“返回主界面”后点击“用户手动输入数据集”按钮进入手动输入数据界面。手动输入数据界面截图如下:
    在这里插入图片描述在这里插入图片描述
    用户每输入一条数据点击“插入数据”按钮即可将数据插入数据库里。在设置最小支持度与最小置信度后,点击“Apriori计算”或“FP-tree计算”即可进入计算界面。
    3、实验结果
    本次计算于2021年10月21日星期四进行。
    首先进行数据集①的计算,利用数据导入功能将“样例数据.csv”中的数据导入平台数据库,并设置最小支持度为0.2,最小置信度为0.5。操作截图如下:

    在这里插入图片描述
    分别点击“Apriori计算”进行计算。计算结果截图如下:

    在这里插入图片描述

    更多相关内容
  • 雷达目标跟踪中的概率数据关联(PDA)算法,仿真场景采用何友的《雷达数据处理与应用》中的杂波场景,对于新手学习PDA算法很有帮助
  • 针对红外搜索跟踪系统(IRST)在单站情况下,对目标进行纯方位跟踪时存在的问题,提出一种数据关联算法.首先根据红外探测器的量测信息特点,从不同角度构造多组证据;然后采用证据组合规则对这些信息进行综合;最后通过极大...
  • 针对这一问题,引入全局搜索策略并采用动态规划和跟踪门技术,提出了一种新的全局最优航迹关联算法。在真实的海上目标航迹关联环境下对两种算法进行了实现,与最近邻域算法相比,新算法不仅获得了较高的关联正确率,同时...
  • 数据关联算法综述及其性能评估 论文关键词信息融合数据关联性 能评估 论文摘要随着传感器技术的不断发展 传感器在现代战争中得到广泛的应用 越来 越多的信息使得信息融合成为未来战场计 算机领域的研究重点文中首先...
  • 雷达目标跟踪中的概率数据关联(PDA)算法,仿真场景采用何友的《雷达数据处理与应用》中的杂波场景,对于新手学习PDA算法很有帮助雷达目标跟踪中的概率数据关联(PDA)算法,仿真场景采用何友的《雷达数据处理与...
  • 从分析联合概率数据关联(JPDA)算法的确认矩阵入手,建立了计算聚概率矩阵的近似公式,并根据聚概率矩阵中元素的大小,重新定义了新的确认矩阵,使可行联合事件的数目显著减少,有效地解决了联合概率数据关联算法可行...
  • 针对两传感器以上的分布式多传感器航迹关联问题,提出了一种基于极大似然估计的最优航迹关联算法,并且使用一种剪枝方法来快速求解该关联算法的最优解,最后,在不同的目标间隔距离条件下进行了仿真实验,仿真结果...
  • 基于光谱聚类的社交意识在线AP关联算法
  • 基于聚类和关联算法的学生成绩挖掘与分析.pdf
  • 多目标跟踪的数据关联算法研究,介绍了最近邻算法,概率数据互联算法,联合概率数据互联算法,交互式多模型概率数据关联算法等经典的数据关联算法
  • NNDA PDA JPDA IMM数据关联算法matlab代码 NNDA PDA JPDA IMM数据关联算法matlab代码
  • 改进的多传感器多目标量测数据关联算法
  • 最近邻航迹关联算法,用于目标跟踪,演示程序包括整个跟踪全过程。
  • 基于最近邻-自适应滤波AIS与HFSWR航迹关联算法
  • 本程序使用java实现灰色关联算法,计算灰色关联度,使用者可根据自身需要进行修改
  • jpda关联算法

    2018-01-07 22:32:23
    多传感器/多目标跟踪的JPDA数据关联算法,在密集杂波环境下
  • 联合相容分支定界算法(Joint Compatibility Branch and Bound,JCBB)充分考虑传感器量测之间的...引入机器学习领域的评价测度对改进后算法和JCBB算法进行比较,结果表明,改进后的关联算法能够保证更好的关联准确度。
  • 分析了点迹-航迹关联中常用的概率数据关联算法,针对此算法在密集目标环境下,尤其是当多个目标的关联波门相交且相交区域存在有效测量时易发生误跟和跟丢的问题,对算法进行了改进,引入了测量隶属度的概念,通过计算各个...
  • 该文提出一种基于中段目标群运动特性的角轨迹关联算法。首先,给出中段目标群的运动模型和角轨迹测量模型。其次,构建中段目标群的似然函数作为代价因子,采用基于二维指派的角轨迹关联算法。接下来进行Mont Carlo...
  • 使用一种将粗关联和精关联相结合的模糊关联方法,对现有的模糊关联算法进行改进,综合考虑了目标的位置信息(距离和角度量测)和属性信息(目标的身份信息等),使用多因素模糊综合决策方法进行关联,使用模糊判决规则进行...
  • 为了解决多传感器多目标跟踪问题,提出了一种新的基于数据压缩的多传感器广义概率数据关联算法(DCMS-GPDA)。 新算法首先对所有传感器的测量值进行组合,对每种可能的测量值进行粗关联测试以获得有效的测量多元组...
  • 概率数据关联算法和联合概率数据关联算法能很好地处理目标跟踪并在很多领域得到了广泛的应用。但是一旦出现某种干扰或是故障,通过概率数据关联算法得到的滤波值也会偏离真实值很多,造成滤波发散,严重影响性能。...
  • 针对该问题,提出一种基于二分法的改进关联规则算法:Dichotomy Apriori算法(D_Apriori算法)。D_Apriori算法利用逐步逼近的思想越级产生频繁K-项集,引入二分法获取每次需要产生频繁项集中集合的长度,结合排列...
  • 针对目前应用于分布式多传感器系统中航迹关联算法只能解决两局部节点航迹相关的问题,该文提出了一种基于多维分配的灰色航迹关联算法。该算法运用灰色理论获取各传感器航迹间的灰色关联度,以此关联度为多传感器系统的...
  • 针对基于线特征的单目SLAM(同时定位与地图构建)中的数据关联问题,提出了一种基于线段端点patch确认的迭代数据关联算法。算法依据近似共线和端点近似重合两个指标来获取线特征的最近邻关联对,使用基于线段端点...
  • 多目标数据关联算法

    千次阅读 2020-05-23 15:18:50
    多目标数据关联算法前言数据关联算法:匈牙利算法(DeepSort)问题2:重载、重定义、重写的区别问题3:构造函数和析构函数调用顺序问题4:宏定义中的#,##,#@问题5:利用memset对vector和string等容器初始化问题6:...

    前言

        我的研究方向主要是多传感器融合感知,应用在自动驾驶领域和无人机领域,实现多目标的识别和跟踪。多传感器间的数据采用特征提取的方法,需要针对性的采用合适的数据关联算法,并根据特征级融合进行优化。

    数据关联算法:

    级联匹配(DeepSort)

    谈到多目标跟踪算法,自然绕不开DeepSort这一个经典的方法。该方法作为经典的Tracking-by-Detection模式,可供优化和改进的方法较多。
    核心思路:寻找增广路径和最大匹配。换言之就是尽可能多的实现匹配。
    算法流程:
    1.状态估计 ( μ , ν , γ , h , x ^ , u ^ , γ ^ , h ^ ) , 其 中 μ , ν , γ , h , 代 表 检 测 框 中 心 的 横 纵 坐 标 , 横 纵 比 , 高 度 , u ^ , γ ^ , h ^ 为 图 像 中 的 对 应 速 度 。 (\mu,\nu,\gamma,h,\widehat{x},\widehat{u},\widehat{\gamma},\widehat{h}),其中\mu,\nu,\gamma,h,代表检测框中心的横纵坐标,横纵比,高度,\widehat{u},\widehat{\gamma},\widehat{h}为图像中的对应速度。 (μ,ν,γ,h,x ,u ,γ ,h ),μ,ν,γ,h,u ,γ ,h
    在这里插入图片描述
    2.目标管理:
    (1)帧间间隔时间 t t t,帧间实现成功匹配需要在阈值内;
    (2)目标三种状态:

    • tentative:当前帧中检测到目标新生成,待查看是否连续帧中均存在;
    • confirmed:连续帧中匹配成功;
    • deleted:连续帧中匹配失败。

    3.目标指派
    (1)运动信息关联:基于匀速直线运动模型,卡尔曼滤波器做状态预测,预测结果和检测结果间利用马氏距离完成数据关联:


    d 1 ( i , j ) = ( d j − y j ) T S j − 1 ( d j − y j ) d^1(i,j)=(d_j-y_j)^TS_j^{-1}(d_j-y_j) d1(i,j)=(djyj)TSj1(djyj)

    其中, d 1 ( i , j ) d^1(i,j) d1(i,j)表示第j个检测框和第i条轨迹之间的运动匹配度, S j S_j Sj表示当前时刻观测空间的协方差矩阵, y j y_j yj表示当前时刻观测量, d j d_j dj表示第j个检测框的状态 ( μ , ν , γ , h ) (\mu,\nu,\gamma,h) (μ,ν,γ,h)
    定义门限函数: b i , j 1 b^1_{i,j} bi,j1符合卡方分布,当 d 1 ( i , j ) < = t 1 d^1(i,j)<=t^{1} d1(i,j)<=t1时表示关联成功。
    运动信息向量 ( μ , ν , γ , h ) (\mu,\nu,\gamma,h) (μ,ν,γ,h)
    在这里插入图片描述
    在这里插入图片描述
    (2)表观特征关联:对于每一个检测框内的图像根据yolo_v3提取特征向量 r i r_i ri,限制条件 r i = 1 r_i=1 ri=1。作者对每一个追踪目标构建一个gallary,存储每一个追踪目标成功关联的最近100帧的特征向量。那么第二种度量方式就是计算第i个追踪器的最近100个成功关联的特征集与当前帧第j个检测结果的特征向量间的最小余弦距离。

    d 2 ( i , j ) = m i n { 1 − r j T r k ( i ) ∣ k ( i ) ∈ R i } d^2(i,j)=min\{{1-r_j^Tr_k^{(i)}|k^{(i)} \in R_i}\} d2(i,j)=min{1rjTrk(i)k(i)Ri}

    定义门限函数: b i , j 2 b^2_{i,j} bi,j2符合卡方分布,当 d 2 ( i , j ) < = t 2 d^2(i,j)<=t^{2} d2(i,j)<=t2时表示关联成功。
    特征向量 1 × 128 1 \times 128 1×128
    在这里插入图片描述
    在这里插入图片描述

    (3)相似度度量:线性加权进行相似度匹配。


    c i , j = λ d 1 ( i , j ) + ( 1 − λ ) d 2 ( i , j ) c_{i,j}= \lambda d^1(i,j) + (1-\lambda)d^2(i,j) ci,j=λd1(i,j)+(1λ)d2(i,j)

    其中,根据 λ \lambda λ的值更改权重,运动度量对运动较为明显的情况下效果较好,但对于长时间的遮挡的情况,使用外观特征的度量比较有效。
    定义门限函数: b i , j = b i , j 1 ⋅ b i , j 2 b_{i,j} = b^1_{i,j} \cdot b^2_{i,j} bi,j=bi,j1bi,j2
    detections数据结构:运动信息,表观特征和检测置信度构成一个数据结构
    在这里插入图片描述
    在这里插入图片描述
    相似度函数
    参数 metric : 选择欧式距离or余弦距离
    参数max_cosine_distance:匹配阈值;
    参数budget(可选):表示预测有n类目标,如果检测到超过n个目标,则删除最早检测到的目标。

    在这里插入图片描述4.匹配级联
    如果一个目标长时间被遮挡之后,kalman滤波预测的不确定性就会大大增加,状态空间内的可观察性就会大大降低,并且遮挡时间较长的那条轨迹因为长时间未更新位置信息,追踪预测位置的不确定性更大,即协方差会更大,因此马氏距离会更小,使得检测结果更可能和遮挡时间较长的那条轨迹相关联。
    考虑到上面的问题,Deepsort使用级联匹配来优化上述问题。级联匹配的核心思想就是由小到大对消失时间相同的轨迹进行匹配,这样首先保证了对最近出现的目标赋予最大的优先权,

    在这里插入图片描述
    级联匹配算法按流程:
    T T T表示跟踪目标集合, D D D表示检测目标集合,
    1: C C C表示跟踪目标和检测目标间的相似度;
    2: D D D表示跟踪目标和检测目标的是否关联(1/0);
    3: M M M表示匹配的目标集合,初始化为空;
    4: U U U表示未匹配的目标集合,初始化为当前帧的检测目标集合;
    5:循环遍历匹配:
    6: U U U表示未匹配的目标集合,初始化为当前帧的检测目标集合;
    7:根据最小损失匹配算法计算 T T T U U U之间关联成功的目标集合 x i , j x_{i,j} xi,j
    8: M M M更新匹配成功的目标;
    9: U U U去除匹配成功的目标;
    10:循环结束,返回 M M M U U U
    跟踪器类:
    在这里插入图片描述
    在这里插入图片描述

    • 参数max_age:判定已检测到的目标消失的最大相隔帧数;

    • 参数n_init:判断目标tentative->confirmedd或者tentative->deleted的最大连续帧数;

    • 参数max_iou_distance:最大重叠度的相隔距离;

    • 参数kf(图像卡尔曼滤波器类):
      在这里插入图片描述

      • 参数motion_mat:状态转移矩阵( 8 × 8 8 \times 8 8×8 [ m e s u r e m e n t ( 4 × 4 ) , p r e d i c t v e l o c i t y ( 4 × 4 ) ] [mesurement(4\times 4),predictvelocity(4\times 4)] [mesurement(4×4),predictvelocity(4×4)]
      • 参数update_mat:状态更新矩阵 ( 4 × 8 4\times 8 4×8
      • 参数std_weight_position:距离权重;
      • 参数std_weight_velocity:速度权重
      • 参数covariance:协方差矩阵( 8 × 8 8 \times 8 8×8
    • 参数tracks:跟踪轨迹集合;

    匹配级联类:
    在这里插入图片描述
    在这里插入图片描述

    • 参数distance_metric:检测目标集合和跟踪目标集合的相似度
    • 参数max_distance:目标关联的阈值;
    • 参数cascade_depth:判定已检测到的目标消失的最大相隔帧数;
    • 参数tracks:当前帧预测的跟踪目标集合;
    • 参数detections:当前帧的检测目标集合。
      在这里插入图片描述
      返回值:
    • 参数matchs:配对跟踪目标的索引;
    • 参数unmatched_tracks:未配对跟踪目标的索引;
    • 参数unmatched_detections:未配对检测目标的索引。

    总结:
    1、方法相对简单,也容易理解。
    2、Deepsort的性能主要取决于detections的质量很好;
    3、在运动匹配度主要考虑的是检测框的移动,即仅使用了位置信息。

    代码来源: https://github.com/Qidian213/deep_sort_yolov3

    展开全文

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 395,907
精华内容 158,362
关键字:

关联算法