下载文档原格式
离群分析报告摘要离群分析是数据挖掘领域的一种重要技术，用于发现异常或离群的数据点。
本报告将介绍离群分析的概念、常用算法和实际应用，并通过一个示例说明离群分析在现实生活中的作用。
引言随着数据的爆炸式增长，如何从海量数据中发现有价值的信息成为一项挑战。
离群分析作为一种数据挖掘技术，能够识别出与大多数数据点不同的异常或离群数据点，对于异常检测、欺诈检测、网络安全等领域具有重要意义。
概念离群分析的目标是识别那些与大多数数据点有很大不同的观测值。
这些观测值可能是真正的异常，也可能是数据收集或处理中的错误。
离群点通常具有以下特征：•离群值与其他数据点的距离较远；•离群值违反了数据分布的统计规律；•离群值对于整体数据的影响较大。
离群分析的核心任务是将离群点与正常点分开，以便进一步分析。
离群分析算法常见的离群分析算法包括：1. Z-ScoreZ-Score是一种常用的统计方法，利用数据的标准差和均值将数据点标准化为Z分数。
Z分数表示一个数据点与平均值之间的差异，通过设定阈值，我们可以将超出阈值的数据视为离群点。
2. 基于距离的方法基于距离的方法通过计算数据点与其他数据点之间的距离来判断离群程度。
常见的方法包括KNN（k近邻）、LOF（局部离群因子）等。
3. 箱线图法箱线图是一种可视化方法，通过绘制数据分布的箱线图来判断是否存在离群点。
箱线图通常包括上下四分位数、中位数和异常值，通过设定阈值，我们可以将超出阈值的数据点视为离群点。
4. 异常点检测算法异常点检测算法利用机器学习和统计方法来发现异常点。
常见的算法包括孤立森林、One-Class SVM等。
实际应用离群分析在许多领域都有广泛的应用：1. 欺诈检测银行、网络支付等领域常常遭受欺诈行为的威胁。
通过离群分析算法，我们可以识别出异常的交易行为，及时发现欺诈行为。
2. 网络安全离群分析可以用于检测网络异常，及时发现恶意攻击或异常行为。
通过监控网络流量、用户行为等数据，我们可以识别出异常的网络流量，并采取相应的安全措施。
大规模数据中的离群点检测方法研究一、绪论在大规模数据中，信息的数量很大，而且数据的结构比较复杂。
因此，离群点检测是大规模数据挖掘中常见的问题，而且对于很多领域都有着极其重要的实际应用，例如金融风险管理、健康监测、木材病虫害分析等。
离群点检测是数据挖掘中的一项基本任务，其目的是识别出与大多数数据点不同的数据样本。
离群点通常被称为异常值或噪声点，而离群点检测的目标是识别和排除这些点，以便进一步分析数据。
本文将介绍几种大规模数据中的离群点检测方法。
二、离群点检测方法1. 基于统计方法的离群点检测方法统计方法是最早也是最基本的离群点检测方法之一。
这些方法通常涉及到基本的假设检验、最小二乘法以及高斯混合模型等。
其中，基于高斯混合模型的离群点检测方法是常用的统计学方法之一，其思想是将数据集分解为多个高斯分布，使得每个高斯分布含有一个或多个类似的数据集。
采用 EM 算法对高斯分布进行参数估计，最后根据估计的结果确定离群点。
2. 基于距离的离群点检测方法基于距离的离群点检测方法是一种常用的基于相似性的技术。
本质上，该技术通过将点与它们的相邻点进行比较来评估它们是否为离群点。
最常用的基于距离的离群点检测方法是基于 k 邻居算法的检测方法。
该算法基于距离度量，利用查询点周围 k 个邻居的距离计算离群得分。
具体而言，它利用距离计算，将于邻居间存在较大距离的数据点标识为离群点。
3. 基于密度的离群点检测方法基于密度的离群点检测方法是另一种常见的方法。
该方法通过计算一个点周围的点的密度来确定该点是否为离群点。
最常用的基于密度的离群点检测方法是LOF算法。
该算法基于距离和密度的概念，因此它结合了基于距离和基于密度的技术。
具体而言，LOF算法会计算每个点相对于周围邻居的局部密度，并将其用于计算该点的离群得分。
4. 基于子空间的离群点检测方法随着高维数据的产生，传统的距离和密度的离群点检测方法已经不能很好地应对高维数据的需求。
基于离群点检测的K-means算法冷泳林;张清辰;赵亮;鲁富宇【摘要】K-means算法以其简单、快速的特点在现实生活中得到广泛应用。
然而传统K-means算法容易受到噪声的影响，导致聚类结果不稳定，聚类精度不高。
针对这个问题，提出一种基于离群点检测的K-means算法，首先检测出数据集中的离群点，在选择初始种子的时候，避免选择离群点作为初始种子。
然后在对非离群点进行聚类完成后，根据离群点到各个聚类的距离，将离群点划分到相应的聚类中。
算法有效降低离群点对K-means算法的影响，提高聚类结果的准确率。
实验表明，在聚类类别数给定的前提下，在标准数据集UCI上该算法有效降低离群点对K-means算法的影响，提高了聚类的精确率和稳定性。
%K-means algorithm is widely used in real life for its simple and rapid characteristics .However , traditional K-means algorithm is affected by outliers , leading to the instability of the clustering results and low accuracy of the clustering .For this problem , the paper proposes a novel K -means algorithm based on outliers detection .The presented algorithm firstly detects outliers from the given dataset , which can avoid selecting outli-ers as the initial seed .After clustering all the objects which are not outliers , the algorithm allocates every outlier to the corresponding cluster according to distance between the outlier and different clusters .The presented algo-rithm reduces the impact of outliers on traditional K -means algorithm and improves the clustering accuracy .For the given number of categories of the clusters and in the standard UCI data sets ,the experimental results indicate that thealgorithm is effective , reduces the influence of outlier on the K -means algorithm , improving the accura-cy and stability of the cluster .【期刊名称】《渤海大学学报（自然科学版）》【年(卷),期】2014(000)001【总页数】6页(P34-38,48)【关键词】聚类;K-means算法;离群点;UCI数据集【作者】冷泳林;张清辰;赵亮;鲁富宇【作者单位】渤海大学高职学院，辽宁锦州 121001; 大连理工大学软件学院，辽宁大连 116621;大连理工大学软件学院，辽宁大连 116621;大连理工大学软件学院，辽宁大连 116621;渤海大学高职学院，辽宁锦州 121001【正文语种】中文【中图分类】TP3110 引言聚类是将物理或抽象对象的集合分成由类似的对象组成多个类的过程，即“物以类聚，人以群分”.聚类是数据挖掘中的一类重要技术，是分析数据并从中发现有用信息的一种有效手段.它将数据对象分组成为多个类或簇，使得同一簇中的对象之间具有较高的相似度，而不同簇中的对象差别很大〔1〕.聚类已经广泛应用于模式识别、空间数据分析、经济学等领域.聚类分析既可以作为单独的工具发现数据集中隐含的相关知识，又可以作为其他数据挖掘分析方法的预处理过程，其已经成为数据挖掘领域的一个重要的研究方向.目前常用的聚类算法包括划分法、层次法、基于密度的方法、基于网格的方法和基于模型的方法等.其中，基于划分方法思想的K-means算法以其简单、快速并有效处理大规模数据等诸多特点，成为现实应用最为广泛的聚类算法.K-means算法〔2，3〕适合聚类大型数据集,特别是当样本分布呈现类内团聚状时，可以达到很好的聚类结果.但是，在有噪声数据影响时，K-means聚类算法结果易受初始聚类中心影响，导致聚类结果不稳定.K-means算法过度依赖初始条件的缺点影响了该算法的聚类效果并制约了其应用范围.当前许多学者致力于改进K-means算法的聚类中心选取方法，如基于均值-标准差选取方法〔4〕，基于近邻密度选取方法〔5〕, 基于密度参数的选取方法〔6〕等，然而这些算法没有充分考虑离群点对聚类的影响，导致最后聚类精度提高不明显.针对这个问题，本文提出一种基于离群点检测的K-means算法，算法将离群点检测引入传统K-means算法，首先检测出数据集中的离群点，在选择初始种子的时候，避免选择离群点作为初始种子.在对非离群点进行聚类完成后，根据离群点到各个聚类的距离，将离群点划分到相应的聚类中.算法有效降低离群点对K-means算法的影响，提高聚类结果的准确率.实验表明，在聚类类别数给定的前提下，通过标准UCI数据库进行实验比较，在保留噪声数据的同时，该算法有效提高聚类精度.1 相关理论和技术1.1 基于距离的离群点检测离群点是指明显偏离数据集中其他数据对象的数据点，人们怀疑这些点是由不同机制产生的〔7〕.离群点检测是数据挖掘领域中的一项重要挖掘技术.它可以发现数据集中小部分偏离了大多数数据行为或数据模型的异常数据.目前常用的离群点检测方法包括基于统计分布、基于距离、基于密度和基于偏差等方法〔8〕.其中，基于距离的离群点检测方法无需了解数据集的分布模型，适用于任何可以计算对象间距离的数据集，而且计算简单，因此本文采用该算法检测离群点.如果对象o在数据集S〔9〕中有大于p部分的对象与它的距离都大于d，那么就将对象o称为数据集S上的DB(p,d)离群点.基于距离的离群点的定义适用于任意维度的数据集，其中参数p表明与离群点的距离大于d的对象所占数据集的最小比例〔10〕.基于距离的离群点检测方法可以简便的定制对象间的距离函数，欧氏距离计算函数就是其中的一种.欧氏距离的定义如下：其中m为数据对象的维(属性)数，xij表示第i个对象的第j属性的值.基于距离的离群点检测算法主要步骤如下：1.随机选取一个数据对象.2.计算其他数据对象与选取的数据对象间的欧氏距离，如果与之距离大于d的数据对象的比例大于p，则判定该数据对象为离群点.3.选取下一个不重复数据对象.4.重复2，直到所有数据对象都被选到.1.2 传统K-means算法传统K-means算法的基本思想是〔11〕：随机地选择k个对象，每个对象初始代表了一个聚类中心；对剩余的每个对象根据其与各个聚类中心的距离，将它赋给最近的聚类；然后重新计算每个聚类的平均值，作为新的聚类中心.不断重复这个过程，直到准则函数收敛.收敛函数E定义为：其中：E是数据集所有对象与它所在的聚类中心的平方误差的总和，E越大说明对象与聚类中心的距离越大，聚类内的相似度越低，反之E越小说明聚类内的相似性越高. 为聚类内的一个数据对象；是聚类Ci的聚类中心，k是聚类个数，Ci是第i个聚类.K-means算法步骤如下：1.随机选择k个数据对象，每个对象作为初始聚类中心.2.计算每个数据对象与聚类中心的距离，根据距离将对象划分到距离最近的聚类.3.重复计算每个聚类中对象的平均值，更新聚类中心.4.重复2和3，直到准则函数E收敛.2 基于离群点检测的K-means算法基于离群点检测的K-means算法的基本思想是：首先利用基于距离的离群点检测方法检测数据集的离群点，然后在非离群点中随机选择k个数据点作为聚类的初始种子，利用传统K-means算法对非离群点进行聚类，最后将离群点划分到相应到聚类中.算法的思想如图1所示.图1 基于离群点检测的K-means算法算法具体步骤如下：1.随机选取一个数据对象.2.计算其他数据对象与选取的数据对象间的欧氏距离，如果与之距离大于d的数据对象的比例大于p，则判定该数据对象为离群点.3.选取下一个不重复数据对象.重复2，直到将所有离群点检测出为止.4.在非离群点中随机选取k个数据对象作为初始聚类种子.5.计算每个非离群点数据对象与聚类中心的距离，根据距离将对象划分到距离最近的聚类.6.重复计算每个聚类中对象的平均值，更新聚类中心.7.重复5和6，直到准则函数E收敛.8.计算每个离群点数据对象与聚类中心的距离，根据距离将其划分到最近的聚类. 算法描述如下：输入：n个数据对象集S 和聚类数k;输出：k个聚类中心Zj及k个聚类数据对象集合Cj;Beginfor r=1 to n //取数据集S中的各个数据对象begincount=0;for any q!=r //数据集中除了当前对象的其他对象beginend//离群点集A={a1,a2,...,ai}；M=S-A; //在S中去除数据集A中的数据对象，生成数据集M；k_means( M , k ); //执行传统的K_means算法；for r=1 to i dobeginfor q=1 to jEnd.3 结果与分析本文将传统的K-means算法和基于离群点检测的K-means算法进行实验对比.为了测试本文算法的有效性，实验选择专用于测试聚类算法性能的UCI数据库中的Iris数据集，Diabetes数据集和Wine数据集作为实验数据集.分别用传统聚类算法与本文提出的算法对3组数据集进行测试.本文实验环境为：CPU为E4500(2.20 GHz)、内存为1.99 GB、操作系统为Windows XP，编程语言为Java.实验结果一：随机选择一批数据分别利用传统K-means聚类算法与本文改进的K-means算法对其进行聚类，结果示意图如图2所示.图2 聚类结果示意图由图2可知，传统K-means算法没有充分考虑离群点的影响，导致最后聚类结果不精确.本文在选择初始聚类中心时，避免选择离群点作为初始聚类中心，首先对非离群点进行聚类，最后根据离群点到与各个聚类的距离将其分配到相应的聚类中.本文有效避免离群点对聚类结果的影响，聚类精度高于传统K-means算法.实验结果二：利用传统K-means算法与本文改进的K-means算法分别对3组数据进行6次实验，对实验结果进行统计，平均准确率如表1所示.表1 传统K-means算法与本文算法聚类平均精度比较IrisDiabetesWine传统k-means算法0.79530.61880.9563本文算法0.83090.64840.96716次实验准确率统计曲线如图3所示.Iris聚类结果曲线 Diabetes聚类结果曲线Wine聚类结果曲线图3 实验结果统计曲线从表1与图3可以看出，传统K-means算法的最高准确率与本文算法的平均准确率接近，但平均准确率明显低于本文改进的K-means算法.另外，传统K-means算法容易受到噪声影响，导致聚类结果不稳定，当不选择离群点作为初始种子时，聚类结果较好，否则聚类效果很差.本文避免选择离群点作为初始种子，因此聚类效果稳定，聚类精度高于传统K-means聚类算法.4 结论聚类分析是数据挖掘领域中常用的数据分析方法，目前聚类分析的主流方法有很多，其中基于划分的K- means算法以其简单、快速并有效处理大规模数据等诸多优点，成为最经典并应用最广泛的聚类方法之一.然而传统K-means算法容易受到离群点的影响，导致聚类结果不稳定、聚类精度低，影响了该算法的聚类效果并制约了其应用范围.本文针对这个问题提出基于离群点检测的K-means算法，将离群点检测引入传统K-means算法，避免选择离群点作为初始聚类中心.在对非离群点进行聚类之后，根据离群点到各个聚类的距离，将其分配到相应的聚类之中.实验结果表明，算法在聚类精度上明显高于传统K-means算法.参考文献:【相关文献】〔1〕Stalling W. Operating systems: internals and design principles(4th Edition)〔M〕.New Jersey, Prentice-Hall, 2001.〔2〕MacQueen J. Some methods for classification and analysis of multivariate observations〔C〕. Proceedings of the 5th Berkeley Symposium on Mathematical Statistics and Probability. Berkeley: University of California Press, 1967.〔3〕张玉芳，毛嘉莉，熊忠阳. 一种改进的K-means算法〔J〕. 计算机应用, 2003,8(23)：31-34. 〔4〕张文君，顾行发，陈良富，等. 基于均值-标准差的K均值初始聚类中心选取方法〔J〕. 遥感学报,2006,10(5)：715-721.〔5〕Shehroz S Khan, Amir Ahmad. Cluster center initialization algorithm for K-Means clustering〔J〕. Pattern Recogintion Letters(S0167-8655),2004,25(11):1293-1320.〔6〕韩凌波，王强，蒋正锋，等. 一种基于改进的K-means初始聚类中心选取算法〔J〕. 计算机工程与应用,2010,46(17)：150-153.〔7〕Elio L, Edgar A. Parallel algorithms for distance-based and density-based outliers 〔C〕.Proc of International Conference on IEEE. 2005: 767-776.〔8〕Kriegel H P, Schubert M, Zimek A. Angle-based outlier detection in high-dimensional data〔C〕. Proceedings of the 14th ACM SIGKDD international conference on knowledge discovery and data mining. ACM,2008:444-452.〔9〕张秀梅，王涛.模糊聚类分析方法在学生成绩评价中的应用〔J〕. 渤海大学学报：自然科学版,2007,28(2)：169-172.。
编号南京航空航天大学毕业设计题目基于无线传感网络的离群点检测的研究及实现学生姓名学号学院计算机科学与技术学院专业计算机科学与技术专业班级指导教师二〇一三年六月南京航空航天大学本科毕业设计（论文）诚信承诺书本人郑重声明：所呈交的毕业设计（论文）（题目：基于无线传感网络的离群点检测的研究及实现）是本人在导师的指导下独立进行研究所取得的成果。
尽本人所知，除了毕业设计（论文）中特别加以标注引用的内容外，本毕业设计（论文）不包含任何其他个人或集体已经发表或撰写的成果作品。
作者签名：年月日（学号）：基于无线传感网络的离群点检测的研究及实现摘要无线传感器网络（Wireless Sensor Network，WSN）的迅猛发展推动了人类生活和社会发展的进步，在家庭、商业、医学、工业以及军事领域等都有广泛的应用。
然而，无线传感器网络自身条件的局限性以及分布环境等条件因素的影响，导致传感器网络的感知数据样本存在丢失、错误等问题，这些问题的存在影响了无线传感器网络的应用，至今如何很好地解决这一问题仍是人们亟待解决的问题。
无线传感器网络中的数据异常检测问题严重影响了数据质量和数据的整体分析。
本文针对这个问题给出了解决方法，并通过实验进行了验证。
主要工作如下：支持向量机（Support Vector Machine, SVM）技术解决无线传感器网络中的数据异常问题，虽然可以避免维数灾难的问题，但是对于大规模感知数据时，SVM技术的映射过程开销很大。
针对这个问题，本文提出KNN-SVM算法，该算法先利用KNN算法对感知数据样本进行裁剪，去掉大部分的正常数据，然后对剩下的小部分数据样本进行异常检测，从而可以减少开销；关键词：无线传感器网络，异常点检测，支持向量机，KNN-VSMResearch and implementation of outlier detection based on wireless sensor networksAbstractRapid development of wireless sensor network (WSN) impelled the human life and social progress.WSN has a wide range of applications in family, business, medical, industrial, military fields and so on. However, the limitations of WSN and the distribution of environment result in missing, error and other problems of data samples in WSN, which affect the application of WSN. So how to solve this problem is still the key problem.The problem of outlier detection affects data quality and data integrity analysis.This paper gives a solution to this problem and validated by experiment.The main work is as follows: Support Vector Machine (SVM) technology can solve abnormal data in WSN and can avoid the dimension disaster problem, but for large scale data, SVM technology mapping process is costly. Aiming at this problem, this thesis puts forward KNN-SVM method which uses KNN method to cut data samples and get rid of most of the normal data, and then detect anomaly in the remaining data samples. KNN-SVM can reduce the overhead effectively.Key Words：WSN; data anomaly detection; SVM;KNN-SVM目录摘要 (i)Abstract (ii)第一章引言............................................................ - 1 -1.1 研究背景.......................................................... - 1 -1.1.1 无线传感器网络基本概念....................................... - 1 -1.1.2 无线传感器网络特点........................................... - 2 -1.2 数据挖掘的研究现状................................................. - 4 -1.2.1 国外的研究现状............................................... - 4 -1.2.2 国内的研究现状............................................... - 4 -1.3 本文主要工作....................................................... - 5 -1.4 论文组织结构....................................................... - 5 - 第二章相关理论及技术介绍................................................. - 7 -2.1 离群点检测技术..................................................... - 7 -2.1.1 离群点检测的定义............................................. - 7 -2.1.2 离群点的检测方法............................................. - 7 -2.1.3 离群点检测技术的应用和存在的问题............................. - 9 -2.2. 支持向量机技术................................................... - 10 -2.2.1 支持向量机的背景知识........................................ - 10 -2.2.2 支持向量机技术介绍.......................................... - 11 - 第三章基于无线传感网络的离群点检测的KNN-SVM算法........................ - 14 -3.1 KNN算法.......................................................... - 14 -3.1.1 KNN算法介绍................................................. - 14 -3.1.2 KNN算法描述................................................. - 15 -3.2 KNN-SVM异常检测算法介绍.......................................... - 17 -3.2.1 KNN-SVM算法原理............................................. - 17 -3.2.2 KNN-SVM算法优化问题......................................... - 20 -3.2.3 KNN-SVM算法描述............................................. - 22 - 第四章基于无线传感网络的离群点检测的KNN-SVM算法实现.................... - 25 -4.1 概要设计和需求分析................................................ - 25 -4.2 KNN-SVM算法的实现................................................ - 26 -4.3 数据分析和实验测试................................................ - 35 -4.3.1实验数据来源................................................. - 35 -4.3.2 实验结果和分析.............................................. - 37 - 第五章总结.............................................................. - 39 - 参考文献.............................................................. - 40 - 致谢................................................................ - 42 -第一章引言1.1 研究背景随着时代的进步，人们对科技的认知能力不断提升，对科技的永无止境的探索，在当今人们对科学的探索水平也在快速增长。
基于边界和距离的离群点检测江 峰1,杜军威1,眭跃飞2,曹存根2(1.青岛科技大学信息与科学技术学院,山东青岛266061;2.中国科学院计算技术研究所,北京100080)摘 要: 近年来,离群点检测已经引起人们的广泛关注.离群点检测在网络入侵检测、信用卡欺诈、电子商务犯罪、医疗诊断以及反恐等诸多领域都具有十分重要的作用.离群点检测的目的是为了发现数据集中的一小部分对象,与数据集中其余的大部分对象相比,这一小部分对象有着特殊的行为或者具有反常的属性.针对现有的离群点检测方法不能有效处理不确定与不完整数据的问题,本文将粗糙集中边界的概念与Knorr 等所提出的基于距离的离群点检测方法结合在一起,在粗糙集的框架中提出一种新的离群点定义与检测方法.针对于该方法,我们设计出相应的离群点检测算法BDOD,并且通过在临床诊断数据集上所进行的实验,验证了算法BDOD 的有效性.实验结果表明本文的方法为处理离群点检测中的不确定与不完整数据问题提供了一条新的途径.关键词: 数据挖掘;离群点检测;粗糙集;不确定与不完整数据中图分类号: TP274 文献标识码: A 文章编号: 0372-2112(2010)03-0700-06Outlier Detection Based on Bounda ry and D istanceJI ANG Feng 1,DU Jun -wei 1,SUI Yue -fei 2,CAO Cun -gen 2(1.Colle ge o f Information and Science Technology,Qingdao U niversity o f Sc ienc e and Technology,Qingdao,Shandong 266061,China;2.Institute o f Computing Technology ,Chinese Acade my o f Sciences,Bei jing 100080,China )Abstract: In recent years,outlier detection has gained considerable interest.T he identification of outliers is important for many applications such as intrusion detection,credit card fraud,criminal activities in electronic commerce,medical diagno sis and an -t-i terrorism,etc.The ai m of outlier detection is to find small groups of objects who behave in an unexpected w ay or have abnormal properties when compared with the rest large amo u nt of data.Since the existing methods for outlier detection cannot deal with uncer -tain and incomplete data.In this paper,we propose a new method for outlier definition and detection,which exploits the basic notion )boundary of rough sets and Knorr .s method abou t distance -based o u tliers.We also give an algorithm BDOD to find such outliers w ithin the framework of rough set theory.The effectiveness of our algorithm is demonstrated on publicly clinical diagno sis data sets.O u r method gives a new approach to the treatment of u ncertain and incomplete data in outlier detection.Key words: data mining;outlier detection;rough sets;uncertain and incomplete data1 引言离群数据是数据集中偏离大部分数据的数据,它们的表现与大多数常规对象有着明显的差异,以至于让人怀疑它们可能是由另外一种完全不同的机制所产生的[1].离群数据并不等同于错误数据,离群数据中可能蕴含着极为重要的信息,例如在信用卡欺诈检测、网络入侵检测、疾病诊断、通信欺诈分析、故障检测、灾害预测、恐怖活动防范等诸多领域中,离群点都是数据分析的主要对象[2,3].在所有的科学研究领域中,离群数据都可能给予我们新的视角,从而导致新的理论和新的应用的不断出现.因此,对离群数据进行分析与研究具有十分重要的理论意义和实际应用价值.目前,对离群点的检测和分析已经发展成为数据挖掘中一项重要而又有趣的研究任务[3].离群点检测最早出现在统计学领域[5].后来,Knorr 等将其引入到数据挖掘领域[2,18,19,21].现有的离群点检测方法主要有五类[4]:(1)基于统计的方法[5];(2)基于深度的方法[6];(3)基于聚类的方法[7];(4)基于密度的方法[8];(5)基于距离的方法[2,18,19,21].经过分析,我们发现这些方法基本上都是采用确定性的方式来表示和处理数据的,并没有考虑数据的不确定与不完整性问题.而我们的现实生活中又存在着大量不确定与不完整数据.对于这种类型的数据,现有的离群点检测方法还无法处理.因此,我们迫切需要一种能够处理不确定与不完整数据的离群点检测方法.收稿日期:2008-12-22;修回日期:2009-03-23基金项目:国家自然科学基金(No.60802042,60674004,60641010,60573063,60573064);国家863高技术研究发展计划(No.2007A A01Z325);青岛科技大学引进人才启动基金(No.200702583)第3期2010年3月电 子 学 报ACTA ELECTRONICA SINICA Vol.38 No.3Mar. 2010针对上述问题,在前期研究工作中,本文作者深入研究了如何利用粗糙集来进行离群点检测的问题,并提出了若干基于粗糙集的离群点检测方法[9~11].在文献[9]中,基于粗糙集边界的概念,我们提出了一种基于边界的离群点检测方法.另外,在论文[11]中,我们将基于距离的离群点检测方法引入到粗糙集中,并提出了两种针对分类型属性的距离度量,用于计算对象之间的距离.本文将在前期工作基础上,进一步把基于边界的与基于距离的离群点检测方法结合在一起,在粗糙集的框架中提出一种基于边界和距离的离群点检测方法.自1982年Pawla k提出粗糙集理论以来[16],粗糙集作为处理不确定与不完整数据的重要工具,受到广泛关注.经过二十余年的发展,粗糙集已成为数据挖掘、机器学习等领域的重要方法,其中数据约简是其最主要的贡献之一[22].但是,目前在粗糙集理论中对于离群点检测的研究还没有引起足够的重视,类似的研究还很少见.因此,本文利用粗糙集理论来研究离群点检测,选题具有较强的创新性.由于我们的现实世界中存在着大量不确定与不完整数据,离群点检测不可避免地会遇到不确定与不完整数据的处理问题,因此,本文的研究不仅可以为离群点检测中的不确定与不完整数据的处理提供一种新的解决办法,而且还可以拓宽粗糙集理论在数据挖掘等领域的应用范围,为粗糙集理论开辟一个新的应用空间.2粗糙集理论的基本知识粗糙集理论采用基于信息表的知识表示形式,信息表是粗糙集理论表示和处理知识的基本工具.信息表通常被定义成一个四元组IS=(U,A,V,f),其中U 和A分别代表对象集合与属性集合;V是所有属性论域的并集;f是一个信息函数,使得对任意a I A和x I U, f(x,a)I V[16].给定一个信息表IS=(U,A,V,f),对任意的属性子集B A A,我们都可以确定论域U上的一个不可区分关系IND(B)={(x,y)I U@U:P a I B(f(x,a)=f (y,a))}[16].关系IND(B)将论域U划分成多个等价类,所有这些等价类就构成U的一个划分,记为U/ I ND(B).对任意对象x I U,本文将使用[x]B来表示在关系IND(B)下包含对象x的等价类[16,20].定义1给定一个信息表IS=(U,A,V,f),对于任意B A A和X A U,X的B-上近似和B-下近似分别被定义为:X B=G{[x]B I U/IND(B):[x]B H X Xª};X B=G{[x]B I U/IND(B):[x]B A X}.另外,BNB(X)=X B-X B被称为集合X的B-边界.我们可以将X的边界看成是在现有的知识条件下,无法对其进行确定分类的那些元素所组成的集合.边界是某种意义上论域U中的不确定域.因此,相对于U中的其它对象而言,边界中的元素是一类特殊的对象,这些元素既不能确定地属于X,也不能确定地不属于X[16,20].既然相对于U中其它对象而言,边界中的元素是一类特殊的对象,而我们在进行离群点检测时,正好需要在给定数据集中寻找一小部分行为比较特殊或者具有反常属性的对象.因此,本文在讨论离群点检测时,将考虑使用集合边界所蕴含的信息来进行离群点检测[9].3基于边界和距离的离群点本文将针对信息表来设计基于边界和距离的离群点检测方法,该方法的主要思想可以描述如下:给定一个信息表IS=(U,A,V,f)和任意X A U(X Xª).对于任意B A A,首先,根据关系I ND(B)将集合X分成三个部分:异常边界EB(X)、B-主边界PB B(X)和B-下近似XB.然后,针对任意x I X,分别计算x与EB(X)、PB B(X)以及X B中每个对象之间的距离.最后,根据所求得的距离值,就可以判断x是否是一个离群点.虽然上述方法也是通过计算对象x与X中所有对象的距离来判定x是否为离群点.但是,与基于距离的离群点检测不同的是[2,18,19],我们在寻找X中的离群点时,首先将X分成三个部分,然后对来自这三个不同部分的对象采取不同的方式进行处理.具体来说,对于异常边界中的对象,我们认为这些对象是离群点的可能性最大.因此,如果异常边界中存在越多的对象与x 的距离较近,则x越有可能是离群点.而对于下近似中的对象,我们认为这些对象是离群点的可能性最小.因此,如果下近似中存在越多的对象与x的距离较远,则x越有可能是离群点.另外,对于主边界中的对象,我们认为这些对象是离群点的可能性居中.因此,如果主边界中存在越多的对象与x保持适当的距离,则x越有可能是离群点.总之,在给定的知识条件下,如果对象x 总是与异常边界中的对象靠得很近,而与下近似中的对象离得很远,并且与主边界中的对象保持适当的距离,则我们认为x是X中的一个基于边界和距离的离群点.在传统的基于距离的离群点检测方法中,给定数据集X和x I X,只要X中的大部分(超过一定比例)的对象与x的距离较远(大于给定的阈值),就认为x是一个离群点[2,18,19].虽然这种方法比较简单,但它却忽略了X中对象之间的差异.如果我们在检测离群点时,采用同一种方式来处理X中的所有对象,不加以区分,701第3期江峰:基于边界和距离的离群点检测明显这是不合理的,并且最终将导致检测结果存在着偏差.因此,本文所提出的基于边界和距离的离群点检测方法是对传统的基于距离方法的一种改进.定义2(内边界) 给定一个信息表IS =(U,A ,V,f )和任意的X A U(X X ª).对于任意B A A ,我们将集合X 的B -内边界定义为:IB B (X )=G {x I X:[x ]B ¾X }命题1 给定一个信息表IS =(U,A ,V,f )和任意的X A U(X X ª).对于任意B A A ,令IB B (X )和X B 分别为X 的B -内边界和B -下近似,则IB B (X)=X -X B .证明 由于X B =G {x I X :[x ]B A X},IB B (X )=G {x I X :[x ]B ¾X},并且对于任意x I X,[x ]B A X 或者[x]B ¾X.因此,x I X B 或者x I IB B (X ),即x I IB B (X )G X B ,所以X A IB B (X )G X B .另外,由内边界和下近似的定义可知,X B A X 且IB B (X)A X ,因此IB B (X )G X B A X.这样,我们就有得到IB B (X )G X B =X.另外,不存在一个对象x I X ,使得[x ]B A X 且[x ]B ¾X ,即不存在一个对象x I X 使得x I X B 且x I IB B (X).因此,IB B (X)H X B =ª.由IB B (X )G X B =X 和IB B (X )H X B =ª,我们可以得到IB B (X )=X -X B .根据上述命题,对于任意的X A U 和B A A ,我们都可以把X 分成两个部分:B -内边界和B -下近似.此外,我们还可以进一步把X 的B -内边界分成两个部分:异常边界和主边界.定义3(异常边界) 给定一个信息表IS =(U,A,V,f ),其中A ={a 1,a 2,,,a m }.对于任意X A U(X X ª)和任意a i I A,令IB {a i }(X )为X 的{a i }-内边界,1[i [m.我们将集合X 在信息表IS 中的异常边界定义为:EB(X )=H mi =1IB {a i }(X )定义4(主边界) 给定一个信息表IS =(U,A ,V,f )和任意的X A U(X X ª).对于任意B A A ,令IB B (X)和EB(X)分别为X 的B -内边界和异常边界.我们将集合X 的B -主边界定义为:PB B (X )=IB B (X)-EB(X )定义5(偏离因子) 给定一个信息表IS =(U,A ,V,f )和任意的X A U (X X ª).对于任意B A A 和x I X ,我们将对象x相对于集合X 的B -偏离因子定义为:DF BX (x )={y I EB(X):d(x ,y )[d 1}+{y I PB B (X):d(x ,y )\d 2}+{y I X B :d(x ,y )\d 3}X其中d(x ,y)为在某个给定的距离度量下对象x 与y 间的距离[2,3].另外,d 1、d 2和d 3是三个给定的距离阈值.对象x 的偏离因子DF BX (x )体现了x 在现有知识条件下,是一个离群点的可能性.为了刻画数据集中每个对象的离群程度,本文将在偏离因子的基础上引入一个多重离群因子(Multiple Outlier Factor,MOF )的概念,用来表征信息表中每个对象的离群程度[8,10,11].定义6(多重离群因子) 给定一个信息表IS =(U,A ,V,f ),其中A ={a 1,a 2,,,a m }.对于任意X A U (X X ª)和任意x I X ,我们将对象x 相对于集合X 的多重离群因子MO F X (x)定义为:MOF X (x )=E mj =1DF {a j}X (x )@W {a j }X (x )|A |其中,DF {a j }X (x )为对象x 相对于X 的{a j }-偏离因子;W {a j }X :X y [0,1)是一个权重函数,使得对任意x I X ,W {a j }X (x )=1-[x ]a j H XX为x 的权重,1[j [m.|M |表示集合M 的势.定义7(基于边界和距离的离群点)给定一个信息表IS =(U,A ,V,f )和任意的X A U(X X ª).令L 为一个给定的阈值,对于任意x I X,如果MOF X (x )>L ,则x 被称为X 中的一个基于边界和距离的离群点,其中MOF X (x )为对象x 相对于集合X 的多重离群因子.4 基于边界和距离的离群点检测算法BDOD算法1 BDOD输入 信息表IS =(U,A ,V,f )和X A U,其中|U |=n,A ={a 1,a 2,,,a m },|X |=n X .阈值L 、d 1、d 2和d 3输出 X 中所有离群点的集合O(1)对于A 中的每一个属性a i ,1[i [m,循环执行如下操作:( ) 根据U 中对象在属性a i 上的取值,按照值域上的一个给定次序(例如字典序),对U 中的所有对象进行排序[17];( )求出划分U/I ND({a i });( )计算X 的{a i }-内边界和{a i }-下近似.(2)计算X 的异常边界.(3)对于任意1[i [m,计算X 的{a i }-主边界.(4)对于X 中的每个对象x ,循环执行如下操作:( )对于任意y I X ,计算对象x 与y 之间的距离d(x ,y );( )对于任意1[i [m,计算x 相对于X 的{a i }-偏离因子和{a i }-权重;( )计算对象x 相对于X 的多重离群因子MOF X (x);( )如果MOF X (x )>L ,则令O =O G {x }.(5)算法结束,返回离群点集合O.在算法1中,我们采用了一种预先对U 中对象进702电 子 学 报2010年行排序,然后再计算划分U/IND(B)的方法[17],这样可以有效降低计算划分的复杂度.在最坏的情况下,算法1的时间复杂度为O((m@n2X)+(m@n log n)),空间复杂度为O(m@n),其中m,n和n X分别为集合A, U与X的势.5实验结果为了验证BDOD算法的有效性,我们将通过实验来比较BDOD算法、基于边界的离群点检测方法[9]和基于距离的离群点检测方法[11]各自的性能.在实验中,对于BDOD算法,我们将采用/基于粗糙集的覆盖度量0作为距离度量[11].另外,我们将d1、d2和d3这三个距离阈值分别设置为:d1=|A|/3,d2=|A|/2,d3=0.9@|A|,其中|A|代表属性集A的势.对于基于边界的离群点检测方法和基于距离的离群点检测方法,具体的实验细节请参考文献[10].实验中所采用的数据集有2个:Lymphography(淋巴系统造影术)数据集和Wisc onsin Breast Cancer(威斯康星乳腺癌)数据集[15].在这两个数据集上,我们将采用Ag-garwal等所提出的评价指标体系来评测每类离群点检测方法的性能,该评价体系是目前最常用的一类离群点检测方法评价体系[12,14].给定一个数据集以及数据集中每个对象所属的类,Aggarwal认为要评价一个离群点检测方法的好坏,可以通过在给定的数据集上来运行该方法,并且计算在由该方法所找出的离群点中,真正的离群点所占据的比例.比例越高,则表明该方法的性能越好[12].5.1Lymphography数据集Lymphography数据集中包含148个对象和19个属性[15].所有的对象被分成四个类:/nor mal find0、/me tas-tases0、/malign ly mph0和/fibrosis0.我们将/normal find0和/malign lymph0看作稀有类(注:属于稀有类的对象都是离群点).在实验中,Lymphography数据集中的所有数据都被导入到信息表ISL=(U,A,V,f)中.我们分别在U的两个子集X1和X2中检测离群点,其中:(1)X1={x I U:f (x,dislocation)=1};(2)X2={x I U:f(x,early-up-take)=1D f(x,bl-a ff ere)=1}.具体的实验结果如下面的表1所示.表1信息表ISL 中关于X1和X2的实验结果X1:|X1|=50,|R X1|=4X2:|X2|=90,|R X2|=5离群程度值前k%的对象(对象个数)属于稀有类的对象个数(覆盖率)BDOD DIS BOU离群程度值前k%的对象(对象个数)属于稀有类的对象个数(覆盖率)BDOD D IS BOU2%(1)1(25%)1(25%)1(25%)2%(2)2(40%)2(40%)2(40%) 4%(2)2(50%)2(50%)2(50%)4%(4)4(80%)3(60%)3(60%) 6%(3)3(75%)3(75%)2(50%)5%(5)4(80%)4(80%)3(60%) 8%(4)4(100%)3(75%)2(50%)8%(7)5(100%)4(80%)3(60%) 10%(5)4(100%)3(75%)2(50%)14%(13)5(100%)5(100%)3(60%) 12%(6)4(100%)4(100%)2(50%)66%(59)5(100%)5(100%)4(80%) 32%(16)4(100%)4(100%)3(75%)70%(63)5(100%)5(100%)5(100%) 40%(20)4(100%)4(100%)4(100%)在表1中,/BDOD0、/DIS0和/BOU0分别代表BDOD算法、基于距离的和基于边界的离群点检测方法.|Xj|和|RXj|分别表示集合X j中的元素个数以及X j中的离群点个数,1[j[2.对于Xj中的每个对象x,我们分别利用这三种离群点检测方法来计算x的离群程度值.然后根据每种方法所计算出的Xj中对象的离群程度值,由高到低对Xj中对象进行排序.因此,在表1中/离群程度值前k%的对象(对象个数)0是指在采用某种离群点检测方法来计算X j中对象的离群程度值之后,离群程度值排在前k%的对象以及这些对象的个数.而/属于稀有类的对象个数0则是指在由该方法所检测出的离群程度值排在前k%的对象中,属于稀有类的对象个数./覆盖率0是指这些属于稀有类的对象占Xj中所有离群点的比例,1[j[2[10,11,14].从表1中我们可以看出,对于Lymphography数据集,BDOD算法的性能明显要好于基于距离的方法和基于边界的方法,其中基于边界的方法的性能最差.5.2Breast C ancer数据集Breast Cancer数据集中包含699个对象和9个连续型属性.所有对象被分成两类:/malignant0和/be-nign0[15].为了形成一个极不均匀的分布,我们从该数据集中移去一些属于/malignant0类的对象[13].最终的数据集包括483个对象,其中39个对象属于/malignant0类, 444个属于/benign0类.另外,数据集中的9个连续型属性被分别转换成分类型属性X[13-14].703第3期江峰:基于边界和距离的离群点检测X最终的数据集可以从如下网站获取:http://researc h.c mis.csiro.au/rohanb/outliers/breas-t cancer/在最终所获得的Breast Cancer数据集中,我们将/malignant0类看作稀有类.另外,我们将数据集中的数据都导入到信息表ISW=(U c,A c,V c,f c)中[10,11].我们分别在U c的两个子集X c1和X c2中检测离群点,其中: (1)X c1={x I U c:f c(x,Clump-thickness)=5};(2)X c2={x I U c:f c(x,Mitoses)=1}.具体的实验结果如表2所示.从表2中我们可以看出,对于Breast Cancer数据集中,BDOD算法的性能也明显要好于基于距离的方法和基于边界的方法.因此,这同样证明了我们的方法的有效性.表2信息表IS W中关于X c1和X c2的实验结果X c1:|X c1|=87,|R X c1|=4X c2:|X c2|=454,|R X c2|=23离群程度值前k%的对象(对象个数)属于稀有类的对象个数(覆盖率)BDOD DIS BOU离群程度值前k%的对象(对象个数)属于稀有类的对象个数(覆盖率)BDOD D IS BOU2%(2)2(50%)2(50%)2(50%)1%(5)4(17%)4(17%)4(17%) 3%(3)3(75%)2(50%)3(75%)2%(9)8(35%)6(26%)7(30%) 5%(4)3(75%)3(75%)3(75%)3%(14)11(48%)10(43%)11(48%) 6%(5)4(100%)3(75%)3(75%)4%(18)14(61%)12(52%)13(56%) 7%(6)4(100%)4(100%)3(75%)5%(23)18(78%)15(65%)18(78%) 8%(7)4(100%)4(100%)4(100%)6%(27)20(87%)18(78%)20(87%)7%(32)23(100%)23(100%)21(91%)10%(45)23(100%)23(100%)22(96%)12%(54)23(100%)23(100%)23(100%)6结论针对当前的离群点检测方法无法处理不确定与不完整数据的问题,本文将基于粗糙集边界的离群点检测方法与传统的基于距离的离群点检测方法结合在一起,充分发挥这两类方法各自的特点,提出了一种基于边界和距离的离群点检测方法.该方法利用粗糙集在处理不确定与不完整数据方面的优势,可以从不确定与不完整的数据中高效地检测出离群点.针对该方法,我们在粗糙集的信息表中设计出相应的离群点检测算法BDOD,并且通过实验表明,基于边界和距离的方法比基于边界的方法以及基于距离的方法具有更好的性能.由于利用粗糙集的方法进行离群点检测的研究还很少见,本文的工作不仅使得离群点检测可以处理不确定与不完整的数据,而且还扩展了粗糙集在数据挖掘等领域的应用范围,为粗糙集理论开辟了一个新的应用空间.在下一步的工作中,我们打算将本文所提出的离群点检测方法应用于网络入侵检测,用来解决现有的入侵检测系统中所普遍存在的检测准确率低、误警率高的问题[23].参考文献:[1]D Hawkins,Identifications of Outliers[M].London:Chapmanand Hall,1980.[2]E Knorr,R Ng.Algori thms for mining dis tance-based outliers inlarge datasets[A].In Proc of the24th VLD B Conf[C].New Y ork:Morgan Kaufmann,1998.392-403.[3]J W Han,M D amber.Data M ining:Concepts and Techno logies[M].San Francisco:Morgan Kaufmann,2001.[4]L Kovacs,D Vass,A Vidacs.Improving quality of service pa-rameter prediction with preliminary outlier detection and elim-i nation[A].Proc of the2nd Int Workshop on Inter-Domain Per-formance and Si mulation[C].Budapest,2004.194-199. [5]P J Rouss eeuw,A M L eroy.Robus t Regression and O u tlier De-tection[M].New York:John Wiley&Sons,1987.[6]T Johnson,I Kwok,R T Ng.Fast compu tation of2-dimensionaldepth conto u r s[A].In Proc of the4th Int Conf on Knowledge Discovery and Data M ining[C].New Y ork:AAAI Press, 1998.224-228.[7]A K Jain,M N Murty,P J Flynn.Data clustering:a review[J].ACM Computing Su rveys,1999,31(3):264-323.[8]M M Breunig,H-P Kriegel,R T Ng,J Sander.LOF:identifyingdensity-based local o u tliers[A].In Proc of the2000ACM SIG-MOD Int Conf on M anagement of Data[C].Dallas:ACM Press,2000.93-104.[9]F Jiang,Y F Sui,C G Cao.Outlier detection using rough settheory[A].In Proc of the10th Int Conf on Ro ugh Sets,Fuzzy Sets,Data Mining,and Granular Computing[C].Canada: Springer-V erlag,2005.79-87.[10]F Jiang,Y F Sui,C G Cao.A rough set approach to o u tlierdetection[J].International Jo u rnal of General Sy s tems,2008, 37(5):519-536.[11]F Jiang,Y F Sui,C G Cao.Some issues about outlier detectionin rough set theory[J].Expert Systems with Applications, 2009,36(3):4680-4687.[12]C C A ggarwal,P S Y u.Outlier detection for high dimensionaldata[A].In Proc of the2001ACM SIGMOD Int Conf on M anagement of Data[C].California:ACM Press,2001.37-704电子学报2010年46.[13]S Harkins,HXHe,G J Williams,R A Baxter.Outlier detectionusing replicator neural networks[A].In Proc of the4th Int Conf on Data Warehousing and Knowledge Discovery[C].France:Springer-Verlag,2002.170-180.[14]Z Y He,S C Deng,XF Xu.An optimization model for outlierdetection in categorical data[A].In Int Conf on Intelligent Compu ting[C].China:Springer-V erlag,2005.400-409. [15]S D Bay.The UCI KDD repository[D B].http://kdd.ics.,1999.[16]Z Pawlak,Rough Sets.Theoretical Aspects of Reas oning aboutData[M].Dordrecht:Klu wer,1991.[17]S H Nguyen,H S Nguyen.Some efficient algorithms for roughset methods[A].In Proc of the6th Int Conf on Information Processi ng and Management of U ncertainty[C].Spain: Springer-V erlag,1996.1451-1456.[18]L Z Wang,L K Z ou.Research on algorithms for mining dis-tance-based outliers[J].Chinese Jo u rnal of Electronics,Be-ijing,14(3),2005.485-490.[19]E Knorr,R Ng,V T ucakov.D istance-based outliers:algo-ri thms and applications[J].VL DB Journal,2000,8(3-4):237-253.[20]刘清.Rough集及Rough推理[M].北京:科学出版社,2001.Q Liu.Rough Sets and Rough Reasoning[M].Beijing:Sc-ience Press,2001.(in Chinese)[21]黄毅群,卢正鼎,胡和平,李瑞轩.分布式异常检测中隐私保持问题研究[J].电子学报,2006,34(5):796-799.Y Q Huang,Z D Lu,H P Hu,RXLi.Privacy preserving outl-ier detection[J].Acta Electronica Sinica,2006,34(5):796-799.(i n Chinese)[22]邓大勇,黄厚宽,李向军.不一致决策系统中约简之间的比较[J].电子学报,2007,35(2):252-255.D Y Deng,H K Huang,X J parison of various typesof reductions in i nconsistent systems[J].Acta Electronica Sinica,2007,35(2):252-255.(in Chinese)[23]陶新民,陈万海,郭黎利.一种新的基于模糊聚类和免疫原理的入侵检测模型[J].电子学报,2006,34(7):1329-1332.X M T ao,W H Chen,L L G uo.A novel model of IDS based on fuzzy cluster and immune principle[J].Acta Electronica Sinica2006,34(7):1329-1332.(in Chinese)作者简介:江峰男,1978年生,博士、副教授.2007年毕业于中科院计算所.主要研究方向有粗糙集理论、人工智能.现主持国家自然科学基金项目1项.近年来,发表论文10多篇,其中SCI收录6篇.E-mail:jiangkong@眭跃飞男,1963年生,中科院计算所研究员,博士生导师,中国计算机学会高级会员.主要研究方向为人工智能、数理逻辑、大规模知识处理的理论基础.曹存根男,1964年出生,中科院计算所研究员,博士生导师,入选中科院百人计划.主要研究方向为人工智能、知识工程、大规模知识获取与知识处理、情感计算等.705第3期江峰:基于边界和距离的离群点检测。
基于距离的离群点检测算法08计算机二班侯宇铭张国勇易小倩一、概述：这个算法是一个基于距离的异常点检测算法，算法以欧式距离为衡量标准，整个算法分三个部分。
第四部分的改进是用了类似密度检测的思想，比较了之前步骤选出的怀疑离群点的三近邻，经过C++语言的实现，效果还不错。
但是程序稍有漏洞，因此没有在这里体现。
但是第四阶段算法的思想已经附在算法描述后面。
本文档附上测试的数据集的arff格式，excel格式，以及txt供程序使用的格式。
三种格式的数据都是一样的。
数据分布如下：附上算法涉及的变量名称对应表：二、算法描述：（这里以数据集为两个相对集中的数据簇和若干离群点为例进行说明）第一部分：找出两个质心Step1: 遍历数据，将数据存入数组dot中该数据设为二维数据，有x,y两个属性。
Step2:设定遍历时的第一个和第二个数据为初始质心。
设定两个变量longest_distance分别记录两个初始簇的最长的距离，设置dotcore1变量记录第一个簇的质心，dotcore2变量记录第二个簇的质心。
Step3:循环：当一个新的点p进入程序时，首先比较点p分别到点dotcore1的距离和到dotcore2的距离，选择距离较小的质心（这里假设选择了dotcore1），记该距离为distancep。
比较distancep和第一个簇（因为选择了dotcore1）的longest_distance。
若distancep<longest_distance，开始下一次循环。
若distancep>longest_distance，则使点p成为新的质心coredot1。
这样循环下去，就可以找到两个簇的最终质心。
算法流程图：进入阶段2图.1 阶段1第二部分：将所有的点归簇，并筛选一部分点Step4: 开始第二次点的扫描：当一个新的点p进入程序时，首先比较点p分别到点dotcore1的距离和到dotcore2的距离，选择距离较小的质心。
基于映射距离比离群因子的离群点检测算法张忠平;姚春辰;孙光旭;刘硕;张睿博;魏永辉【期刊名称】《计算机集成制造系统》【年(卷),期】2024(30)5【摘要】针对基于邻近性的离群点检测方法需要花费大量时间过滤正常点,并且在检测全局离群点时难以检测出局部离群点的问题,提出一种基于映射距离比离群因子离群点检测(MDROF)算法。
首先,为了减少正常点在检测过程中的时间消耗,给出了差异相似度的概念,通过定义差异相似度剪枝因子过滤掉数据集中的大部分正常点。
其次,定义映射k距离,通过映射距离与可达距离的比值刻画数据对象的局部离群程度,通过可达密度刻画数据对象的全局离群程度。
最后,结合数据对象相互近邻点的平均排位定义映射距离比离群因子来检测离群点。
在人工数据集以及真实数据集上分别对该算法与其他经典的离群点检测算法在精确率、AUC值和离群点发现曲线上进行实验对比分析。
实验结果证明MDROF算法在离群点检测的准确性和稳定性上明显优于对比算法。
【总页数】14页(P1719-1732)【作者】张忠平;姚春辰;孙光旭;刘硕;张睿博;魏永辉【作者单位】燕山大学信息科学与工程学院;河北省计算机虚拟技术与系统集成重点实验室;武汉理工大学国际教育学院;燕山大学里仁学院;蒙古科技大学信息与通信技术学院【正文语种】中文【中图分类】TP311【相关文献】1.基于聚类离群因子和相互密度的离群点检测算法2.ERDOF:基于相对熵权密度离群因子的离群点检测算法3.基于快速密度峰值聚类离群因子的离群点检测算法4.数据流环境下基于距离的离群点检测算法5.基于期望核密度离群因子的离群点检测算法因版权原因，仅展示原文概要，查看原文内容请购买。
