论文部分内容阅读
摘 要 离群数据检测是数据挖掘的一个重要分支，也成为当前研究的热点。本文对离群数据检测技术进行了介绍，探讨了基于无监督的离群数据检测技术。对基于统计、基于距离和基于密度的离群检测方法进行了研究。
关键词 离群数据 数据分析 监督式检测
基于无监督的离群数据检测的通常存在一个假设，即离群数据的样本容量远远小于数据集中正常数据或主流数据的样本容量。实施无监督式的离群数据检测不需要任何先验知识，也不需要对标签数据进行预处理，当发现某个观察值与正常数据的特征差异较大时，则判断该数据是离群数据的理由极为充分。基于无监督的离群检测技术主要分为基于统计的方法和基于最近邻的方法等。
一、基于统计的离群数据检测
统计的方法主要是基于对小概率事件的判别来实现对数据样本异常的鉴别，是目前发展最为成熟的离群数据检测技术。其主要原理是假定已知的数据集服从某种概率分布，通过不一致检验确把那些严重偏离分布曲线的记录标记为离群点。使用基于统计的离群检测方法的前提是事先获得数据集的数据分布、分布参数（均值、方差等）和预期的离群数据规模，而这些参数一般获取比较困难。
基于统计学的离群检测方法可分为基于分布的检测方法和基于深度的检测方法两类。
基于分布的方法其原理是假设一个标准分布来对数据集进行拟合，在拟合的基础上观察数据集的概率分布情况来逐步离群检测。此类方法的主要缺陷在于难以准确估计多维数据的分布模型。于是Merz（1996）提出了一个以计算机几何为基础的基于深度的方法，他通过计算不同层的k-d凸包将外层的对象标记为离群数据。
在一元数据集的离群检测中，给定数据集为P=（pij）m€譶，pi=（pi1，pi2，…，pin）为第i个数据对象，m为数据对象个数，n为属性的维数，对于任意j∈{1，2，…，n}，分别就一维子空间L1（j）上的投影数据子集进行分析，对能够反映其属性的概括性指标如位置、不对称、可变性以及峰度等进行观察，判断其是否落入离群范畴。
多维离群数据的定义与一元数据集类似，本质上是指具有较低概率的数据。设多维数据集Q=（qij）m€譶，qi=（qi1，qi2，…，qin）为第i个数据对象，m为数据对象个数，n为属性的维数。可以利用马氏距离来度量两个对象间的距离，设Q=（q1，q2，…，qn，）为数据均值，则数据点qi与均值之间的马氏距离为dists（qi，Q）=（qi，Q）=（qi-Q）S-1（qi-Q）T。其中S为Q的协方差矩阵。该距离与点qi的概率有关，可设一个阈值，当dists（qi，Q）>€%Z时，将qi标记为离群数据进行下一步检测。
二、基于最近邻的离群数据检测
在利用该方法进行离群检测时，需要计算两个记录之间的距离或相似度，可分为两类：第一类是基于距离，将数据记录视为多维空间的点，计算记录与正常数据之间的距离并和某个阈值进行比较来判断是否为离群数据；第二类是基于密度，对每个记录估计其相邻区域的密度，当记录落入低密度区域则被标记为离群数据。
1、基于距离的离群数据检测
基于距离的离群数据最早由Knorr和Ng（1998）提出，S.Ramaswamy（2000）和S.D.Bay（2003）等人对此进行了改进。其原理可用以下定义描述：
定义2.1.1 已知数据集X，X={x1，x2，…，xn}，o为数据对象，如果数据集i中有pct部分数据Y，Y€H裍，y∈Y远离于对象o及与之距离为的邻域，称o为基于距离的离群数据，表示为DB（pct，1）。
基于距离的离群数据检测技术包含并改进了基于统计的思想，其优势在于当数据集难以估计出概率分布模型时，依然能检测出离群数据，而且在高维空间中算法效率较高。在实施检测时，事先给出数据对象间距离的测度，一旦给定参数pct和1即可实施离群检测。一般采用欧氏距离、曼哈顿距离和兰氏距离作为距离测度。基于距离的离群数据检测技术的最大缺陷在于确定参数pct和1比较困难，致使输出结果不稳定，需要多次输入pct和1测试，增加了算法的复杂度。为克服该缺陷，引入距离和（distance sum-based）的概念。其与DB（pct，1）不同的是，该方法的原理是测量数据集中n个数据记录两两之间的距离1ij，形成距离矩阵R，令pi=1ij，值越大，pi则对象i与其他对象的距离越远，若设预期的离群点个数为X，则距离和最大的X个对象即可被判定为离群数据。
2、基于密度的离群数据检测
在基于无监督的离群数据检测中，当只有一类样本可以学习时，最简单也是最直接的方式就是基于密度估计的方法。其主要原理是通过参数或非参数化的方法设定训练样本的密度分布模型，根据经验和实际环境设定密度阈值，通过与阈值的比较来判断离群数据。
在一元单模数据的离群检测中，文献[2]假设样本服从一元高斯分布：
三、结语
总体来说，无监督式离群检测方法的优点是不需要先验知识，操作简单便于实施。不足是出现误报的概率较大，时间复杂度高，其性能易受某一密度或距离测度标准影响。在未来的研究中，应更加注重提高检测的质量和效率。
参考文献：
[1] S Ramaswamy，R Rastogi，K Shim.Efficient Algorithms for Mining Outliers from Large Data Sets[C].In：Proceedings of the ACM SIGMOD Conference，2000：473-438.
[2]DUAD R，HART P，STORK D.Pattern classification[M].2nd ed.New York：John Wiley &Sons，2001.
（作者单位：中南财经政法大学信息与安全工程学院）
关键词 离群数据 数据分析 监督式检测
基于无监督的离群数据检测的通常存在一个假设，即离群数据的样本容量远远小于数据集中正常数据或主流数据的样本容量。实施无监督式的离群数据检测不需要任何先验知识，也不需要对标签数据进行预处理，当发现某个观察值与正常数据的特征差异较大时，则判断该数据是离群数据的理由极为充分。基于无监督的离群检测技术主要分为基于统计的方法和基于最近邻的方法等。
一、基于统计的离群数据检测
统计的方法主要是基于对小概率事件的判别来实现对数据样本异常的鉴别，是目前发展最为成熟的离群数据检测技术。其主要原理是假定已知的数据集服从某种概率分布，通过不一致检验确把那些严重偏离分布曲线的记录标记为离群点。使用基于统计的离群检测方法的前提是事先获得数据集的数据分布、分布参数（均值、方差等）和预期的离群数据规模，而这些参数一般获取比较困难。
基于统计学的离群检测方法可分为基于分布的检测方法和基于深度的检测方法两类。
基于分布的方法其原理是假设一个标准分布来对数据集进行拟合，在拟合的基础上观察数据集的概率分布情况来逐步离群检测。此类方法的主要缺陷在于难以准确估计多维数据的分布模型。于是Merz（1996）提出了一个以计算机几何为基础的基于深度的方法，他通过计算不同层的k-d凸包将外层的对象标记为离群数据。
在一元数据集的离群检测中，给定数据集为P=（pij）m€譶，pi=（pi1，pi2，…，pin）为第i个数据对象，m为数据对象个数，n为属性的维数，对于任意j∈{1，2，…，n}，分别就一维子空间L1（j）上的投影数据子集进行分析，对能够反映其属性的概括性指标如位置、不对称、可变性以及峰度等进行观察，判断其是否落入离群范畴。
多维离群数据的定义与一元数据集类似，本质上是指具有较低概率的数据。设多维数据集Q=（qij）m€譶，qi=（qi1，qi2，…，qin）为第i个数据对象，m为数据对象个数，n为属性的维数。可以利用马氏距离来度量两个对象间的距离，设Q=（q1，q2，…，qn，）为数据均值，则数据点qi与均值之间的马氏距离为dists（qi，Q）=（qi，Q）=（qi-Q）S-1（qi-Q）T。其中S为Q的协方差矩阵。该距离与点qi的概率有关，可设一个阈值，当dists（qi，Q）>€%Z时，将qi标记为离群数据进行下一步检测。
二、基于最近邻的离群数据检测
在利用该方法进行离群检测时，需要计算两个记录之间的距离或相似度，可分为两类：第一类是基于距离，将数据记录视为多维空间的点，计算记录与正常数据之间的距离并和某个阈值进行比较来判断是否为离群数据；第二类是基于密度，对每个记录估计其相邻区域的密度，当记录落入低密度区域则被标记为离群数据。
1、基于距离的离群数据检测
基于距离的离群数据最早由Knorr和Ng（1998）提出，S.Ramaswamy（2000）和S.D.Bay（2003）等人对此进行了改进。其原理可用以下定义描述：
定义2.1.1 已知数据集X，X={x1，x2，…，xn}，o为数据对象，如果数据集i中有pct部分数据Y，Y€H裍，y∈Y远离于对象o及与之距离为的邻域，称o为基于距离的离群数据，表示为DB（pct，1）。
基于距离的离群数据检测技术包含并改进了基于统计的思想，其优势在于当数据集难以估计出概率分布模型时，依然能检测出离群数据，而且在高维空间中算法效率较高。在实施检测时，事先给出数据对象间距离的测度，一旦给定参数pct和1即可实施离群检测。一般采用欧氏距离、曼哈顿距离和兰氏距离作为距离测度。基于距离的离群数据检测技术的最大缺陷在于确定参数pct和1比较困难，致使输出结果不稳定，需要多次输入pct和1测试，增加了算法的复杂度。为克服该缺陷，引入距离和（distance sum-based）的概念。其与DB（pct，1）不同的是，该方法的原理是测量数据集中n个数据记录两两之间的距离1ij，形成距离矩阵R，令pi=1ij，值越大，pi则对象i与其他对象的距离越远，若设预期的离群点个数为X，则距离和最大的X个对象即可被判定为离群数据。
2、基于密度的离群数据检测
在基于无监督的离群数据检测中，当只有一类样本可以学习时，最简单也是最直接的方式就是基于密度估计的方法。其主要原理是通过参数或非参数化的方法设定训练样本的密度分布模型，根据经验和实际环境设定密度阈值，通过与阈值的比较来判断离群数据。
在一元单模数据的离群检测中，文献[2]假设样本服从一元高斯分布：
三、结语
总体来说，无监督式离群检测方法的优点是不需要先验知识，操作简单便于实施。不足是出现误报的概率较大，时间复杂度高，其性能易受某一密度或距离测度标准影响。在未来的研究中，应更加注重提高检测的质量和效率。
参考文献：
[1] S Ramaswamy，R Rastogi，K Shim.Efficient Algorithms for Mining Outliers from Large Data Sets[C].In：Proceedings of the ACM SIGMOD Conference，2000：473-438.
[2]DUAD R，HART P，STORK D.Pattern classification[M].2nd ed.New York：John Wiley &Sons，2001.
（作者单位：中南财经政法大学信息与安全工程学院）