资源描述：
《基于密度的局部离群点检测算法》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。
1、总第252期计算机与数字工程Vo.l38No.102010年第10期Computer&DigitalEngineering11*基于密度的局部离群点检测算法张卫旭尉宇(武汉科技大学信息科学与工程学院武汉430081)摘要基于统计学和基于距离的离群点检测都依赖与给定数据点集的全局分布,然而数据通常并非都是均匀分布的。当分析分布密度相差很大的数据时,基于密度的局部离群点检测方法有着很好的识别局部离群点的能力。但存在时间复杂度较大,文章提出了一种改进的算法,能降低时间复杂度,实现有效的局部离群点的检测。关键词数据挖掘;离群点检测;局部离群
2、点中图分类号TP301.6DetectionAlgorithmforLocalOutliersBasedonDensityZhangWeixuWeiYu(CollegeofInformationScienceandEngineering,WuhanUniversityofScienceandTechnology,Wuhan430081)AbstractBecausebasedonstatisticsanddistanceoutliersdetectionreliesonagivensetofdatapointsglobaldistribu
3、tion.However,thedataareusuallynotevenlydistributed.Whenanalyzingthedatadensityvarygreatly,basedonthedensityoflocaloutlierdetectionmethodhasagoodabilitytoidentifylocaloutliers.Butthereisagreatercomplexity,inthispaperproposedanimprovedalgorithmcanreducethetimecomplexity,canach
4、ieveeffectivelocaloutlierdetection.KeyWordsdatamining,outlierdetection,localoutlierClassNumberTP301.6音或发现潜在的、有意义的知识。实际在一些应用1引言中,如电信和信用卡欺骗、药物研究、气象预报、电[1]数据挖掘,在人工智能领域,习惯上又称为子商务、贷款审批、客户分类、金融领域、网络入侵数据库中知识发现(KnowledgeDiscoveryinData检测等领域有关例外情况的信息比常规模式更有base,KDD),也有人把数据挖掘视为数据库中
5、知识价值。目前在数据挖掘中,对偏离常规模式的数据发现过程的一个基本步骤。知识发现过程由以下即离群数据的研究正得到越来越多的重视。三个阶段组成:1)数据准备;2)数据挖掘;3)结2局部离群点的定义及LOF挖掘算法果表达和解释。数据挖掘可以与用户或知识库交[2]互。近年来,数据挖掘引起了信息产业界的极大关关于离群点的定义,D.Hawkins给出了一个注,其主要原因是存在大量数据,可以广泛使用,并笼统而直观的定义:离群点是偏离其他观察对象且迫切需要将这些数据转换成有用的信息和知识。的、由不同一般的机制原理生成的观察对象。通常获取的信息和知识可以广泛用于
6、各种应用,包括商离群点也被称为异常点、孤立点、歧异值、有时也称务管理、生产控制、市场分析、工程设计和科学探索其为野值。等。概括地说,离群点是由于系统受外部干扰而造离群点检测(outlierdetection)是数据挖掘的基成的。但是,形成离群点的系统外部干扰是多种多本任务之一,故称为离群点挖掘,其目的是消除噪样的。首先可能是采样中的误差,如记录的偏误,*收稿日期:2010年3月30日,修回日期:2010年4月27日作者简介:张卫旭,男,硕士研究生,研究方向:数据挖掘及软件开发。尉宇,男,副教授,研究方向:信号处理及其应用。12张卫旭等:基于密度的
7、局部离群点检测算法第38卷工作人员出现笔误,计算错误等,都有可能产生极假设Xi-Yj是m维空间的两个点,它们之间端大值或者极端小值。其次可能是被研究现象本的距离通常有以下几种定义:欧几里德距离、曼哈身由于受各种偶然非正常的因素影响而引起的,例顿距离和明考斯距离等,具体计算定义分别如下:如,在人口死亡序列中,由于某年发生了地震,使该欧几里德距离:年度死亡人数剧增,形成离群点;在股票价格序列d222ij=(Vi1-Vj1)+(Vi2-Vj2)++(Vim-Vjm)中,由于受某项政策出台或某种谣传的刺激,都会m2出现极增、极减现象,变现为序列中的离群点
8、。=(Vik-Vjk)(3)k=1[1]局部离群点的描述如下例子:如果数据对象为区间标度变量类型,则绝对距图1中给出了包
