基于中心移动的轨迹离群点检测.pdf

基于中心移动的轨迹离群点检测杨洪宁,徐文进,杜珍珍,姚佳禹(青岛科技大学信息科学技术学院,青岛266061)通信作者:徐文进,E-mail:摘要:AIS 数据是指通过 AIS 系统获取的船舶运动轨迹信息,对其进行挖掘可以获得船舶的运动模式、航行路线、停靠地点等信息.但其在采集过程中产生的离群点会对聚类等任务造成负面影响,因此对 AIS 数据挖掘之前需要进行离群点检测.然而,当 AIS 轨迹数据中存在大量离群点时,会导致大多数离群点检测算法的准确率显著下降.为了解决这个问题,本文提出了一种基于中心移动的轨迹离群点检测算法(centershiftoutlierdetection,CSOD).通过迫使数据点向其 K 近邻集合的中心移动,使每个数据点更加接近典型数据,从而有效地消除了离群点对聚类的影响.为了验证本文算法的有效性,使用浙江海域 AIS 渔船轨迹数据集,将本文提出的 CSOD 算法与一些经典的离群点检测算法进行了对比实验.实验结果表明,CSOD 算法整体上性能更加优越.关键词:AIS 数据;离群点检测;聚类;K 近邻;异常值得分引用格式:杨洪宁,徐文进,杜珍珍,姚佳禹.基于中心移动的轨迹离群点检测.计算机系统应用,2023,32(12):189196.http:/www.c-s- Outlier Detection Based on Center ShiftYANGHong-Ning,XUWen-Jin,DUZhen-Zhen,YAOJia-Yu(SchoolofInformationScienceandTechnology,QingdaoUniversityofScienceandTechnology,Qingdao266061,China)Abstract:AISdatareferstothevesselsmotiontrajectoryinformationobtainedthroughtheAISsystem.MiningAISdatacanprovideinsightsintothevesselsmotionpatterns,navigationroutes,dockinglocations,etc.However,outliersgeneratedduringtheAISdatacollectioncanhaveanegativeeffectonclusteringandothertasks.Therefore,outlierdetectiononAISdatabeforeminingisnecessary.However,whentherearealargenumberofoutliersinAIStrajectorydata,asignificantdecreaseoccursintheaccuracyofmostoutlierdetectionalgorithms.Toaddressthisissue,thisstudyproposesatrajectoryoutlierdetectionbasedoncentershift(CSOD).TheCSODalgorithmencouragesdatapointstomovetowardsthecenteroftheirK-nearestneighbor(KNN)set,makingeachdatapointclosertotypicaldataandeffectivelyeliminatingtheinfluenceofoutliersonclustering.Tovalidatetheeffectivenessoftheproposedalgorithm,thestudyconductscomparativeexperimentsbetweentheCSODalgorithmandseveralclassicaloutlierdetectionalgorithmsusingtheAISfishingvesseltrajectorydatasetintheZhejiangseaarea.TheexperimentalresultsdemonstratethattheCSODalgorithmoutperformstheotheralgorithmsintermsofoverallperformance.Key words:AISdata;outlierdetection;clustering;K-nearestneighbor(KNN);outlierscore在数据挖掘过程中,通常会存在一些偏离正常数据的对象,这些对象被称为离群点.根据偏离程度,可将其分为强离群点和弱离群点.强离群点1通常被视为异常点,但不一定是错误的数据,它们往往包含重要信计算机系统应用ISSN1003-3254,CODENCSAOBNE-mail:ComputerSystems&Applications,2023,32(12):189196doi:10.15888/ki.csa.009329http:/www.c-s-中国科学院软件研究所版权所有.Tel:[phone]收稿时间:2023-06-07;修改时间:2023-07-12;采用时间:2023-07-19;csa 在线出版时间:2023-09-15CNKI 网络首发时间:2023-09-18SoftwareTechniqueAlgorithm软件技术算法189息.通过分析强离群点可以实现欺诈行为检测2、异常设备检测3以及网络安全检测4.弱离群点1则被认为是噪声点,噪声点会导致模型准确性降低、泛化能力不足等问题,进而对数据分析的结果产生负面影响.因此,离群点的检测和处理是非常重要的.离群点检测在机器学习和数据挖掘中具有广泛的应用,它可以帮助发现异常行为、提高数据质量.通常,离群点检测根据参考集的大小可以分为全局离群点检测和局部离群点检测.参考集是用来建模和计算离群点得分的一组基准样本集合.在全局离群点检测方法中,参考集通常包含数据集中的所有对象,因此可以全面地考虑整个数据集的特征和分布.全局离群点检测方法主要指基于统计模型5的方法.而在局部离群点检测方法中,参考集则是某个数据点邻近区域内的对象.局部离群点检测方法包括基于密度的方法6、基于距离的方法7以及基于聚类的方法8.在众多离群点检测方法中,基于聚类的方法因其较高的可扩展性和适用性而被广泛应用.基于聚类的方法可以将数据点划分为相似的簇,但对于离群点来说,它们与其他数据点的差异较大,往往无法被归类到任何一个簇中,而是被单独作为一组.在聚类任务中,如果存在大量的离群点,将会导致聚类效果显著下降,从而影响后续的数据挖掘工作.因此,离群点的检测和剔除可以被视为聚类任务的预处理步骤.然而,将剔除离群点作为聚类分析的前提与使用聚类方法进行离群点检测的初衷背道而驰.如何在不影响聚类任务和离群点检测效果的情况下正确处理离群点,仍然是当前亟待解决的问题.除此之外,包括基于聚类方法在内的大多数传统离群点检测方法,在选择阈值参数或确定离群点数量方面需要手动操作.而这些参数需要根据先验知识或领域经验进行选择,随意选择很容易导致结果不准确或不一致.因此,实现自动化选择阈值或确定离群点数量能够提高离群点检测的准确性和可靠性,对于离群点检测具有重要意义.针对上述问题,本文提出了一种基于中心移动的轨迹离群点检测算法.关键思想是使数据点向其 K 近邻(K-nearestneighbor,KNN)集合的中心移动,促使每个数据点靠近更密集的区域.这意味着每个数据点会更接近典型的数据点,从而有效地抵消离群点对聚类的影响.此外,该方法计算所有数据点的异常值分数,并将异常值分数的标准差作为全局阈值,用于判定数据点是否为离群点,从而避免了手动选择阈值参数.本文算法在实现离群点检测的同时,还可以完成对数据的聚类工作,并进一步应用于后续的热点挖掘工作.本文的主要贡献有以下 3 点.(1)提出了一种基于中心移动的轨迹离群点检测算法,将每个数据点移动到其 KNN 集合 Ni的中心,从而使其更加接近典型数据点,以此来抵消离群点对聚类的影响.(2)与传统离群点检测算法不同,本文算法不需要手动选择阈值参数或确定离群点数量,而是将所有数据点异常值分数的标准差作为全局阈值,用于离群点的判定.(3)不同于传统离群点检测算法的验证数据集,本文采用渔船 AIS 轨迹数据集对所提算法进行验证.相对于其他数据集,轨迹数据集的离群点检测具有数据存在时序性、数据分布不均、数据维度高等难点.尽管如此,本文算法相较于其他算法的 F1-score 仍能平均提高 0.18,离群点检测时间也能平均减少 5.3s.本文第 1 节介绍对轨迹数据进行异常检测的不同方法及各自研究现状.第 2 节给出本文算法涉及的相关概念.第 3 节详细介绍本文算法的流程.第 4 节实验与结果分析.第 5 节是结论与展望.1研究现状轨迹数据挖掘的目标是从大量移动对象中提取共同的特征,为了实现这一目标,需要对轨迹数据进行离群值的检测和处理.由于轨迹数据具有时序性和连续性等特点,使得单个真实轨迹数据点的分析价值有限,这就导致了轨迹数据集中的离群点多为弱离群点,即噪声数据.在不同的研究领域中,噪声数据所代表的含义和性质都有所不同.Zhu 等人9认为轨迹领域中的噪声数据是指在某些相似性度量方面与大多数轨迹点存在显著差异的轨迹点.由于轨迹数据的采集设备通常存在测量误差、信号干扰等问题,导致噪声数据在实际应用中是难以避免的.因此,在对轨迹数据进行挖掘之前必须进行去噪处理,避免噪声数据引起的偏差对后续数据分析产生负面影响.由于轨迹数据具有数据量大、数据稀疏以及数据更新频率快等特点,使得噪声数据的检测仍存在挑战性10,11.现有的噪声数据检测方法主要分为 3 类:基于历史轨迹数据的噪声检测、基于网格化的噪声检测、基计 算 机 系 统 应 用http:/www.c-s-2023年第32卷第12期190软件技术算法SoftwareTechniqueAlgorithm于距离的噪声检测.Li 等人12提出了一种基于历史轨迹相似性的度量方式,称为时序噪声值检测框架(TOD).该框架利用数据集的时序信息来检测噪声值.它通过比较每个路段与其他路段在相同时间步长内的运动轨迹,计算它们之间的相似性值,并将历史相似性值记录在每个路段的时间邻域向量中.当某个路段的相似性值与之前的历史值发生急剧变化时,该路段被认为是噪声值.Chawla 等人13将道路交通建模为一个基于时间依赖流的网络,将城市划分为以主要道路为界的区域,并通过识别各链路与历史流量配置文件的偏差来检测异常链路.Pang 等人14对 iForest 算法与懒惰学习方法进行创新,提出了一种异常检测方法.该方法将每个轨迹划分到随机选定的不同单元格中,并提出假设:异常轨迹所涵盖的单元格数量应小于正常轨迹所涵盖的单元格数量,从而实现异常数据的检测.Chen 等人15提出了一种实时的异常轨迹检测方法 iBOAT.在该方法中,使用固定窗口的方式来代替网格进行数据处理,并通过计算阈值大小来检测异常轨迹.Knorr 等人16以数据的速度和方向为切入点,提出了一种基于距离的异常值检测方法.计算轨迹对象之间的平均加权距离并作为判定指标,来判断该轨迹是否异常.Lei 等人17提出了一种基于聚类距离度量的轨迹异常检测方法,用来检测 AIS 轨迹数据中的距离异常、航向异常和速度异常.尽管以上方法在轨迹数据的噪声检测方面取得了一定效果,但仍存在局限性.在基于历史轨迹数据的噪声检测中,由于轨迹数据在采集过程中可能存在定位误差、数据缺失等问题,因此很难获取完全准确的历史轨迹,这就导致了噪声数据的检测结果通常不够准确.在基于网格化的噪声检测中,需要手动设置一些参数,如网格的划分单位、窗口的大小等.因此,噪声数据的检测结果与参数之间具有较强的关联性,很容易受到参数的影响.而基于距离的噪声检测方法对于噪声和异常值非常敏感,即使是微小的距离变化,都可能对检测结果产生较大的影响.2相关概念致力于抵消离群点对轨迹数据聚类的影响,本文提出了一种基于中心移动的轨迹离群点检测算法.该算法以最近邻思想和距离判定为基础,以轨迹数据的特征空间为输入.涉及的相关概念如下.x1,xn)y1,yn)(1)最近邻:是一种基于距离度量的概念,通过计算数据点之间的距离来确定它们之间的相似性或接近程度.常见的最近邻算法是 KNN 算法18.KNN 算法的思想:在数据集特征空间中,计算某个数据点与数据集中所有数据点之间的距离,选取距离最近的 k 个数据点作为其最近邻,并根据最近邻的类别或属性值进行分类.由于欧氏距离计算方法简单直观,因此被视为一种常用的距离度量方法.当特征空间的数据样本为N 维时,数据点 x(与数据点 y(的欧氏距离公式为:d(x,y)=vtni=1(xiyi)2(1)(2)距离判定:是一种用来确定数据点是否为离群点的方法,该方法基于设定的距离阈值来确定离群点.如果一个数据点与其他数据点之间的距离超过了阈值,就被认为是离群点.T=(p1,p2,pi,pn),0 i npi=(loni,lati,ti,fi)lonilatitifiti(3)特征空间:是指由多个特征组成的空间,每个特征在空间中对应一个维度.本文中的轨迹点特征空间可以表示为,其中轨迹点,和分别表示 时刻轨迹点所在位置的经纬度,表示 时刻轨迹点的运动特征,如速度、角度、加速度等.3本文算法本节讨论了基于中心移动的轨迹离群点检测算法CSOD 的具体流程,主要分为 3 个部分:确定 KNN 集合、确定 KNN 集合的中心点以及判别离群点.算法流程如图 1 所示.3.1 基于特征距离确定 KNN 集合pjlonj,latjpklonk,latk计算轨迹特征空间中不同数据点之间的距离,为每个数据点找到 k 个最近邻居点.由于轨迹数据包含经纬度特征,因此使用欧氏距离公式计算球体表面上的轨迹距离的方法不再适用,通常使用半正矢公式19来进行距离计算.因此,本文采用半正矢距离公式来计算两个轨迹点之间的地理位置距离.当两个轨迹点的经纬度坐标为()和()时,地理位置距离计算公式表示为:d1(pj,pk)=2rarcsin(sin2A+cos(latj)cos(latk)sin2B)(2)2023年第32卷第12期http:/www.c-s-计 算 机 系 统 应 用SoftwareTechniqueAlgorithm软件技术算法191(latjlatk)/2(lonjlonk)/2 d1(pj,pk)pjpkpjpkfj=(fj1,fj2,fjn)fk=(fk1,fk2,fkn)其中,A=,B=,表示轨迹点、之间的地理位置特征距离,r 表示地球半径.除经纬度特征外,轨迹数据中通常还存在速度、角度等运动特征,我们使用欧氏距离公式计算两个轨迹点之间的运动特征距离.当两个轨迹点和的运动特征分别为和时,运动特征距离计算公式表示为:d2(pj,pk)=vtni=1(fji fki)2(3)d2(pj,pk)pjpk其中,表示轨迹点、之间的运动特征距离.基于上述计算出的地理位置特征距离和运动特征距离,可以得到两个轨迹点之间的特征距离.特征距离计算公式表示为:dist(pj,pk)=d1(pj,pk)+d2(pj,pk)(4)dist(pj,pk)pjpkpiNi T,0 i n其中,表示轨迹点、之间的特征距离.基于此,我们可以计算出特征空间中不同数据点之间的距离,并为每个数据点找到 KNN 集合.轨迹点对应的 KNN 集合为.经纬度坐标运动特征地理位置特征距离运动特征距离特征距离稀疏度得分边缘度得分集合中心点异常值得分判别离群点确定 KNN 集合确定 KNN 图 1算法流程图 3.2 基于边缘度得分确定 KNN 集合Ni的中心Ni为了消除离群点造成的负面影响,我们让每个数据点向其 KNN 集合的中心移动,促使数据点向更密集的区域聚集,从而使每个数据点都更加接近典型数据点.移动过程如图 2 所示.我们通过计算数据点的稀疏度得分和边缘度得分来确定每个 KNN 集合的中心点.原始数据点中心数据点图 2轨迹点移动示意图piNipipiNi=p1,p2,pk,pi Ni首先根据特征距离公式计算每个数据点的稀疏度得分:将数据点到其 KNN 集合中所有数据点的特征距离之和作为的稀疏度得分,进而得到所有数据点的稀疏度得分.数据点的稀疏度得分越高,意味着该数据点的近邻区域越稀疏.假设数据点的 KNN 集合,则稀疏度计算公式表示为:spari=kj=1dist(pi,pj),pj Ni(5)sparipiNiNi其中,表示数据点的稀疏度得分.然后在已知数据点稀疏度得分的情况下,计算集合内每个数据点与其他数据点的稀疏度乘积之和,并将结果作为该数据点在集合内的边缘度得分.边缘度计算公式表示为:margm=kn=1,n,msparmsparn(6)margmpmNiNi其中,表示数据点的边缘度得分.边缘度得分越低,表明数据点越靠近集合的中心区域.因此,我们选取边缘度得分最低的数据点作为该 KNN 集合的中心点.3.3 基于异常值得分判定离群点NipiNipi确定 KNN 集合的中心后,计算每个数据点的异常值得分并判定离群点.首先将数据点移动到 KNN集合中心点位置,然后计算两者的边缘度得分之差,该差值被定义为数据点的异常值得分.异常值得分计算公式表示为:scorei=margimarg(7)scoreipi其中,表示数据点的异常值得分,marg 表示集计 算 机 系 统 应 用http:/www.c-s-2023年第32卷第12期192软件技术算法SoftwareTechniqueAlgorithmNi合中心点的边缘度得分.该过程迭代 3 次后,对数据点的异常值得分进行统计,并将全部数据点异常值得分的标准差作为阈值,超过阈值的数据点即为离群点.离群点判定示意图如图 3 所示.离群点正常点阈值图 3离群点判定示意图基于以上描述,本文设计的离群点检测算法流程如算法 1 所示.算法 1.CSOD 算法T=(p1,p2,pi,pn),0in输入:训练数据集.输出:离群点集合.pipi1)根据半正矢公式和欧氏距离公式分别计算数据点与其他数据点之间的地理位置特征距离和运动特征距离,并将二者之和作为数据点的特征距离;pipi2)对步骤 1)中得到的数据点的所有特征距离排序,选择距离最近的 k 个数据点作为的 KNN 集合;pipi3)计算数据点到 KNN 集合中所有数据点的特征距离之和,并将其作为数据点的稀疏度得分;4)计算 KNN 集合中每个数据点的边缘度得分,将边缘度得分最小的点记作 KNN 集合的中心点;pi5)将数据点移动到 KNN 集合的中心点位置,将二者边缘度得分之差记为异常值得分;6)迭代移动过程 3 次,得到不同的簇和簇中心;7)选择全体数据点异常值得分的标准差作为阈值,超过阈值的点记作离群点并纳入到离群点集合.上述算法使用全局阈值参数来标准化离群点检测.与其他方法不同的是,该方法不需要先验知识来设定噪声量,从而使得该方法易于理解和实现.我们将异常值得分超过阈值的点定义为离群点,并进行剔除,以便在后续的数据挖掘工作中继续使用该数据集.此外,聚类后的数据可以用来显示数据密集区域,并结合网格区域等技术来挖掘轨迹数据的热点信息.4实验分析 4.1 实验数据本文实验中使用的轨迹数据来自浙江省海洋与渔业局,该数据为东经 118,128,北纬 26,36海域2015 年 4 月(10000 数据量)、2015 年 5 月(5000 数据量)、2016 年 4 月(5000 数据量)的渔船轨迹数据.由于 AIS 轨迹数据的采集容易受到设备故障、天气、海浪等因素的影响,会导致采集到的定位数据出现缺失、漂移.因此使用该数据之前需要进行预处理,包括剔除缺失数据、保留有效字段等步骤.具体的数据格式如表 1 所示.表 1渔船AIS数据格式表字段名称 字段类型数据样例字段描述渔船IDINT259560船舶ID,唯一性时间戳INT1454710544unix时间戳,单位为s纬度INT18945334单位为1/600000经度INT73824632单位为1/600000角度INT2580单位为0.1,默认正北方向为0速度INT30速度,单位为0.1节图 4 以热力图的方式展示了 2015 年 4 月轨迹数据的分布情况,可以直观地看到不同区域的轨迹点密集程度.图 4渔船轨迹数据热力图Xmeanrange,Xmean+rangeXmean此外,在原数据集的维度内增加了随机噪声点.其中,为所有数据点的平均值,range 为所有数据点到平均值的最大绝对距离,噪声量为原数据集大小的 8%.4.2 评估指标现有的离群点检测研究所采用的评估标准通常为二分类任务中的常用评价指标,即精确率(Precision)和召回率(Recall).精确率是指被算法标记为离群点的数据点中,有多少是真正的离群点.召回率是指在所有真正的离群点中,有多少被算法正确地标记为离群点.渔船 AIS 时空轨迹数据的分布具有随机性,不同的分布情况会影响精确率和召回率的表现.如果数据集中离群点的数量较多,精确率可能会下降,召回率可能会2023年第32卷第12期http:/www.c-s-计 算 机 系 统 应 用SoftwareTechniqueAlgorithm软件技术算法193提高;相反,如果离群点数量较少,精确率可能会提高,召回率可能会下降.因此,为了避免这种影响,我们采用 F1-score 作为实验评价指标.F1-score 是基于精确率(Precision)与召回率(Recall)的调和平均数,综合考虑了精确率和召回率两方面的因素,对两者进行了调和,从而能够保证离群点检测结果的准确性和完整性.计算公式表示为:F1-score=2PrecisionRecallPrecision+Recall(8)Precision=TPTP+FP(9)Recall=TPTP+FN(10)其中,TP(truepositive)表示被正确标记为离群点的数量,即真正的离群点数量;而 FP(falsepositive)则表示被错误标记为离群点的正常点数量,即误判为离群点的数量.为了更好地评估本文算法性能,除了将 F1-score作为评价指标外,我们还将离群点检测时间作为该实验的一个重要评价指标,并与近年来的其他4种异常检测算法进行了对比实验.4.3 实验结果与分析首先,本文使用上述提到的 AIS 轨迹数据集对CSOD 算法的聚类效果进行了验证,实验效果如图 5所示.其中,图 5(a)表示原始轨迹数据的分布,图 5(b)表示经过 CSOD 算法聚类后的轨迹数据分布.从图 5(a)、(b)的对比可以看到,原始轨迹数据点经过 CSOD 算法聚类后形成了不同的簇,并剔除了分布在边缘的轨迹离群点.为了评估 CSOD 算法的性能表现,我们在数据集上运行了其他 4 种不同离群点检测算法,分别是 MO-GAAL20、NC21、iForest22、QUE23,并对它们的 F1-score 进行了分析.5 种离群点检测算法的 F1-score 结果如表 2 所示.通过表 2 中 5 种算法的 F1-score 可以看出,本文CSOD 算法的 F1-score 指标在不同数据集上的表现均优于其他算法.比如,2015.04 数据集中,相较于表现最好的 QUE 算法高出 0.06;2015.05 数据集中,相较于表现最好的 iForest 算法高出 0.07;2016.04 数据集中,相较于表现最好的 iForest 算法高出 0.06.这表明 CSOD算法能够更有效地消除离群点造成的负面影响,并且能够更准确地识别数据集中的轨迹离群点.1281271261251241231221211202628303234原始轨迹点(a)原始数据纬度经度纬度经度1281271261251241231221211202628303234Cluster1Cluster2Cluster3Cluster4Cluster5(b)聚类数据图 5轨迹数据分布示意图表 2不同算法的最佳 F1-score(k 在 227之间)算法2015.04数据集2015.05数据集2016.04数据集MO-GAAL0.690.530.57NC0.730.750.74iForest0.890.890.90QUE0.910.880.87CSOD0.970.960.96另外,比较了 5 种离群点检测算法在处理不同规模数据集时的时间消耗,单位为 s.我们选择了 2015 年4 月(10000 数据量)与 2015 年 5 月(5000 数据量)的AIS 渔船轨迹数据进行实验.具体运行时间如表 3 所示.通过表 3 可以看出,CSOD 算法在不同规模数据集上的时间消耗均优于其他算法.比如,在 10000 数据量的 2015.04 数据集中,相较于耗时最短的 NC 算法减少了 4.8s;而在 5000 数据量的 2015.05 数据集中,相较于耗时最短的 NC 算法减少了 3.1s.这表明 CSOD算法具有更为精简的算法结构,能够更高效地处理数据.计 算 机 系 统 应 用http:/www.c-s-2023年第32卷第12期194软件技术算法SoftwareTechniqueAlgorithm 4.4 实验验证Xmeanrange,Xmean+range为了进一步验证本文算法的性能,我们在 2015 年4 月数据集的维度内分别增加了规模大小为原数据集 18%、28%、38%的随机噪声量,并在这些数据集上运行了 5 种离群点检测算法,以获得离群点检测效果.5 种离群点检测算法在不同噪声量的数据集上的 F1-score 对比结果如图 6 所示.通过图 6 的对比可以看出,随着数据集中噪声量的增加,5 种离群点检测算法的 F1-score 在逐渐降低.然而,在噪声量相同的情况下,CSOD 算法性能明显优于其他 4 种算法,进而证明了本文算法具有更强的鲁棒性.表 3离群点检测时间(k=10)(s)算法2015.04数据集2015.05数据集MO-GAAL8.36.2NC6.54.3iForest9.06.7QUE7.25.8CSOD1.71.21.00.90.80.70.60.50.40.3MO-GAALNC(a)18%noise amountiForest QUE CSOD算法F1-score1.00.90.80.70.60.50.40.3MO-GAALNC(b)28%noise amountiForest QUE CSOD算法F1-score1.00.90.80.70.60.50.40.3MO-GAALNC(c)38%noise amountiForest QUE CSOD算法F1-score图 6不同噪声量情况下的算法 F1-score 对比5结论与展望本文提出了一种基于中心移动的轨迹离群点检测算法.通过计算特征距离来确定每个数据点的 KNN 集合,然后根据稀疏度计算边缘度得分来确定近邻集合的中心,最后基于异常值得分的标准差来判定离群点.我们在浙江海域 AIS 数据集上对该算法进行了评估,并与 4 种经典的离群点检测算法进行了对比实验,实验使用 F1-score 和算法运行时间作为评估标准.结果表明,本文算法的离群点检测效果明显优于其他算法,并且在噪声量较高的数据集上也能表现出良好的性能.未来,本文算法可以在聚类基础上开展热点挖掘等工作,以进一步提升算法的应用价值.参考文献Knorr EM,Ng RT.Finding intensional knowledge ofdistance-basedoutliers.Proceedingsofthe25thInternationalConferenceonVeryLargeDataBases.NewYork:MorganKaufmannPublishersInc.,1999.211222.1Domingues R,Filippone M,Michiardi P,et al.Acomparative evaluation of outlier detection algorithms:Experiments and analyses.Pattern Recognition,2018,74:2406421.doi:10.1016/j.patcog.2017.09.037Boukerche A,Zheng LN,Alfandi O.Outlier detection:Methods,models,and classification.ACM ComputingSurveys,2021,53(3):137.doi:10.1145/33810283MoustafaN,HuJK,SlayJ.Aholisticreviewofnetworkanomalydetectionsystems:Acomprehensivesurvey.JournalofNetworkandComputerApplications,2019,128:3355.doi:10.1016/j.jnca.2018.12.0064Andrysiak T,Saganowski L.Network anomaly detectionbasedonstatisticalmodelswithlong-memorydependence.Proceedings of the 10th International Conference onDependability and Complex Systems.Brunw:Springer.2015.110.doi:10.1007/978-3-319-19216-1_15BreunigMM,KriegelHP,NgRT,et al.LOF:Identifyingdensity-basedlocaloutliers.ACMSIGMODRecord,2000,29(2):93104.doi:10.1145/335191.3353886Angiulli F,Basta S,Lodi S,et al.Reducing distancecomputations for distance-based outliers.Expert Systemswith Applications,2020,147:113215.doi:10.1016/j.eswa.2020.1132157Pu G,Wang LJ,Shen J,et al.A hybrid unsupervisedclustering-based anomaly detection method.TsinghuaScienceandTechnology,2021,26(2):146153.doi:10.26582023年第32卷第12期http:/www.c-s-计 算 机 系 统 应 用SoftwareTechniqueAlgorithm软件技术算法19599/TST.2019.9010051ZhuXD,ZhangJ,LiHZ,et al.FRIOD:Adeeplyintegratedfeature-rich interactive system for effective and efficientoutlierdetection.IEEEAccess,2017,5:2568225695.doi:10.1109/ACCESS.2017.27712379MengFR,YuanG,LvSQ,et al.Anoverviewontrajectoryoutlierdetection.ArtificialIntelligenceReview,2019,52(4):24372456.doi:10.1007/s10462-018-9619-110BhowmickK,NarvekarM.Trajectoryoutlierdetectionfortrafficevents:Asurvey.In:BhallaS,BhatejaV,ChandavaleA,et al.,eds.Intelligent Computing and Information andCommunication.Singapore:Springer,2018.3746.doi:10.1007/978-981-10-7245-1_511LiXL,LiZH,HanJW,et al.Temporaloutlierdetectioninvehicle traffic data.Proceedings of the 25th IEEEInternational Conference on Data Engineering.Shanghai:IEEE,2009.13191322.doi:10.1109/ICDE.2009.23012ChawlaS,ZhengY,HuJF.Inferringtherootcauseinroadtrafficanomalies.Proceedingsofthe12thIEEEInternationalConferenceonDataMining.Brussels:IEEE,2012.141150.doi:10.1109/ICDM.2012.10413Pang LX,Chawla S,Liu W,et al.On mining anomalouspatternsinroadtrafficstreams.In:TangJ,KingI,Chen,L,et al.,eds.AdvancedDataMiningandApplications.Berlin:Springer,2011.237251.doi:10.1007/978-3-642-25856-5_1814Chen C,Zhang D,Samuel Castro P,et al.Real-timedetectionofanomaloustaxitrajectoriesfromGPStraces.In:Puiatti A,Gu T,eds.Mobile and Ubiquitous Systems:Computing,Networking,and Services.Berlin:Springer,2011.6374.doi:10.1007/978-3-642-30973-1_615Knorr EM,Ng RT.Algorithms for mining distance-basedoutliers in large datasets.Proceedings of the 24th16International Conference on Very Large Data Bases.NewYork:MorganKaufmannPublishersInc.,1998.392403.Lei B,Mingchao D.A distance-based trajectory outlierdetectionmethodonmaritimetrafficdata.Proceedingsofthe4th International Conference on Control,Automation andRobotics(ICCAR).Auckland:IEEE,2018.340343.doi:10.1109/ICCAR.2018.838469717Liu GY,Zhao HQ,Fan F,et al.An enhanced intrusiondetectionmodelbasedonimprovedKNNinWSNs.Sensors,2022,22(4):1407.doi:10.3390/s2204140718AlamCN,ManafK,AtmadjaAR,et al.Implementationofhaversine formula for counting event visitor in the radiusbased on Android application.Proceedings