基于层次的孤立点检测算法设计及实现

南华大学计算机科学与技术学院毕业设计（论文）毕业设计(论文)题目基于层次的孤立点检测算法设计及实现学院名称计算机科学与技术学院指导教师肖基毅职称教授班级本05计算04班学号20054440428学生姓名李敬康2009年5月29南华大学计算机科学与技术学院毕业设计（论文）i目录摘要...................................................iiiAbstract................................................iv第一章绪论..............................................11.1研究背景及研究意义......................................................................................11.3论文组织结构..................................................................................................2第二章相关知识..........................................32.1数据挖掘概述..................................................................................................32.1.1数据挖掘概念.......................................................................................32.1.2数据挖掘过程.......................................................................................42.1.2数据挖掘算法组成...............................................................................52.2聚类分析..........................................................................................................52.2.1聚类算法简介.......................................................................................62.2.2基于层次的聚类方法...........................................................................82.2.3距离、相似系数及聚类分析中的数据类型.....................................142.3孤立点分析....................................................................................................172.3.1基于统计的方法.................................................................................182.3.2基于距离的孤立点检测算法.............................................................182.3.3基于偏离的孤立点探测.....................................................................202.4本章小结........................................................................................................20第三章算法设计与实现...................................213.1算法相关定义................................................................................................213.2算法描述........................................................................................................223.3算法实现........................................................................................................243.3.1数据结构定义.....................................................................................24南华大学计算机科学与技术学院毕业设计（论文）ii3.3.2算法函数说明.....................................................................................253.4算法分析........................................................................................................303.4.1算法复杂度.........................................................................................303.4.2算法的局限性.....................................................................................303.5本章小结........................................................................................................30第四章结论.............................................31参考文献................................................32谢辞....................................................33南华大学计算机科学与技术学院毕业设计（论文）iii摘要摘要：孤立点检测是数据挖掘的一个重要方面，因其独特的知识发现功能而得到较为深入的研究。孤立点检测算法己经在金融欺诈检测、网络入侵检测、生态系统失调天气预报等风险控制领域得到了广泛的应用。聚类分析和孤立点检测技术己经广泛应用于模式识别、数据分析、图像处理、市场研究等许多领域。聚类及孤立点检测算法研究已经成为数据挖掘研究领域中非常活跃的一个研究课题。本文介绍了数据挖掘理论，在深入研究聚类分析和孤立点检测算法的基础上提出了基于层次的孤立点检测算法。给出了算法较为详细的描述，阐述了算法中各个函数的功能。该算法基于层次方法，采用欧几里得距离进行凝聚的层次聚类。根据聚类中含有单一数据元素的类数来确定初始孤立点个数，然后根据距离阀值判断是否为孤立点。通过对算法的性能进行分析，该算法的时间复杂度为)(2NO，空间复杂度为)(NO，其中N是数据规模。试验结果表明，基于层次的孤立点检测算法能基本实现孤立点的检测，并对孤立点进行精确性分析。关键字：数据挖掘；层次聚类；凝聚；孤立点检测；距离南华大学计算机科学与技术学院毕业设计（论文）ivAbstractAbstract:OutlierdetectionisanimportantaspectofDataMining，whichhasgetmoredepthresearchbecauseofitsuniqueknowledgediscoveryfunctions.Today，therearelotsofefficientoutlierdetectionalgorithmswhicharewidelyusedinfinancialfrauddetection，networkinstructiondetection，ecosystemimbalance，Weatherforecastandotherriskcontrolareas.Clusteringanalysisandoutlierdetection,asimportantpartsofdatamining,arewidelyappliedtothefieldssuchaspatternrecognition,dataanalysis,imageprocessing,andmarketresearch.Researchonclusteringanalysisandoutlierdetectionalgorithmshasbecomeahighlyactivetopicinthedataminingresearch.Inthisthesis,theauthorpresentsthetheoryofdatamining,andbasedondeeplyanalysisthealgorithmsofclusteringandoutlierdetection,theauthoradvanceshierarchical-basedoutlier-detectionalgorithm.Elaboratestheideaofthealgorithm,expoundsthefunctionsofalgorithm.ThealgorithmbasedonhierarchicalclusteringandusedEucliddistancetoagglomeratedclustering.Accordingtoasingleclustercontainsseveraltypesofdataelementstodeterminetheinitialnumberofoutliers,thendeterminewhethertheoutlierwiththethresholddistance.Throughananalysisoftheperformanceofalgorithm,thecomputationalcomplexityofthealgorithmis)(2NO,andthespatialcomplexityofthealgorithmis)(NO,whereNisthenumberdatasetobjects.Keywords:DataMing;HierarchicalClustering;agglomeration;outlierdetection;distance南华大学计算机科学与技术学院毕业设计（论文）第1页，共38页第一章绪论1.1研究背景及研究意义由于计算技术和存储技术的飞速发展，使人们在短时间里就可以从各种信息源搜集和存储大量的人工难以管理的资料。虽然现代数据库技术可以对这些资料进行经济地存储，但还是需要一种技术来帮助人们分析、理解甚至可视化这些资料。因此就产生了KDD(KnowledgeDiscover