‘壹’ 聚类分析法
聚类分析，亦称群分析或点分析，是研究多要素事物分类问题的数量方法。其基本原理是，根据样本自身的属性，用数学方法按照某些相似性或差异性指标，定量地确定样本之间的亲疏关系，并按亲疏关系的程度对样本进行聚类（徐建华，1994）。
聚类分析方法，应用在地下水中，是在各种指标和质量级别标准约束条件下，通过样品的各项指标监测值综合聚类，以判别地下水质量的级别。常见的聚类分析方法有系统聚类法、模糊聚类法和灰色聚类法等。
（一）系统聚类法
系统聚类法的主要步骤有：数据标准化、相似性统计量计算和聚类。
1.数据标准化
在聚类分析中，聚类要素的选择是十分重要的，它直接影响分类结果的准确性和可靠性。在地下水质量研究中，被聚类的对象常常是多个要素构成的。不同要素的数据差异可能很大，这会对分类结果产生影响。因此当分类要素的对象确定之后，在进行聚类分析之前，首先对聚类要素进行数据标准化处理。
假设把所考虑的水质分析点（G）作为聚类对象（有m个），用i表示（i=1，2，…，m）；把影响水质的主要因素作为聚类指标（有n个），用j表示（j=1，2，…，n），它们所对应的要素数据可用表4-3给出。在聚类分析中，聚类要素的数据标准化的方法较多，一般采用标准差法和极差法。
表4-3 聚类对象与要素数据
对于第j个变量进行标准化，就是将xij变换为x′ij。
（1）总和标准化
区域地下水功能可持续性评价理论与方法研究
这种标准化方法所得的新数据x′ij满足
区域地下水功能可持续性评价理论与方法研究
（2）标准差标准化
区域地下水功能可持续性评价理论与方法研究
式中：
由这种标准化方法所得的新数据x′ij，各要素的平均值为0，标准差为1，即有
区域地下水功能可持续性评价理论与方法研究
（3）极差标准化
区域地下水功能可持续性评价理论与方法研究
经过这种标准化所得的新数据，各要素的极大值为1，极小值为0，其余的数值均在［0，1］闭区间内。
上述式中：xij为j变量实测值；xj为j变量的样本平均值；sj为样本标准差。
2.相似性统计量
系统聚类法要求给出一个能反映样品间相似程度的一个数字指标，需要找到能量度相似关系的统计量，这是系统聚类法的关键。
相似性统计量一般使用距离系数和相似系数进行计算。距离系数是把样品看成多维空间的点，用点间的距离来表示研究对象的紧密关系，距离越小，表明关系越密切。相似系数值表明样本和变量间的相似程度。
（1）距离系数
常采用欧几里得绝对距离，其中i样品与j样品距离dij为
区域地下水功能可持续性评价理论与方法研究
dij越小，表示i，j样品越相似。
（2）相似系数
常见的相似系数有夹角余弦和相关系数，计算公式为
1）夹角余弦
区域地下水功能可持续性评价理论与方法研究
在式（4-20）中：-1≤cosθij≤1。
2）相关系数
区域地下水功能可持续性评价理论与方法研究
式中：dij为i样品与j样品的欧几里得距离；cosθij为i样品与j样品的相似系数；rij为i样品与j样品的相关系数；xik为i样品第k个因子的实测值或标准化值；xjk为j样品第k个因子的实测值或标准化值；
3.聚类
在选定相似性统计量之后，根据计算结果构成距离或相似性系数矩阵（n×n），然后通过一定的方法把n个样品组合成不同等级的分类单位，对类进行并类，即将最相似的样品归为一组，然后，把次相似的样品归为分类级别较高的组。聚类主要有直接聚类法、距离聚类法（最短距离聚类法、最远距离聚类法）。
（1）直接聚类法
直接聚类法，是根据距离或相似系数矩阵的结构一次并类得到结果，是一种简便的聚类方法。它首先把各个分类对象单独视为一类，然后根据距离最小或相似系数最大的原则，依次选出一对分类对象，并成新类。如果一对分类对象正好属于已归的两类，则把这两类并为一类。每一次归并，都划去该对象所在的列与列序相同的行。经过n-1次把全部分类对象归为一类，最后根据归并的先后顺序作出聚类分析谱系图。
（2）距离聚类法
距离聚类法包括最短距离聚类法和最远距离聚类法。最短距离聚类法具有空间压缩性，而最远距离聚类法具有空间扩张性。这两种聚类方法关于类之间的距离计算可以用一个统一的公式表示：
区域地下水功能可持续性评价理论与方法研究
当γ=-0.5时，式（4-22）计算类之间的距离最短；当γ=0.5时，式（4-22）计算类之间的距离最远。
最短、最远距离法，是在原来的n×n距离矩阵的非对角元素中找出dpq=min（dij）或dpq=max（dij），把分类对象Gp和Gq归并为一新类Gr，然后按计算公式：
dpq=min（dpk，dqk）（k≠ p，q） （4-23）
dpq=max（dpk，dqk）（k≠ p，q） （4-24）
计算原来各类与新类之间的距离，这样就得到一个新的（n-1）阶的距离矩阵；再从新的距离矩阵中选出最小或最大的dij，把Gi和Gj归并成新类；再计算各类与新类的距离，直至各分类对象被归为一类为止。最后综合整个聚类过程，作出最短距离或最远距离聚类谱系图（图4-1）。
图4-1 地下水质量评价的聚类谱系图
（二）模糊聚类法
模糊聚类法是普通聚类方法的一种拓展，它是在聚类方法中引入模糊概念形成的。该方法评价地下水质量的主要步骤，包括数据标准化、标定和聚类3个方面（付雁鹏等，1987）。
1.数据标准化
在进行聚类过程中，由于所研究的各个变量绝对值不一样，所以直接使用原始数据进行计算就会突出绝对值大的变量，而降低绝对值小的变量作用，特别是在进行模糊聚类分析中，模糊运算要求必须将数据压缩在［0，1］之间。因此，模糊聚类计算的首要工作是解决数据标准化问题。数据标准化的方法见系统聚类分析法。
2.标定与聚类
所谓标定就是计算出被分类对象间的相似系数rij，从而确定论域集U上的模糊相似关系Rij。相似系数的求取，与系统聚类分析法相同。
聚类就是在已建立的模糊关系矩阵Rij上，给出不同的置信水平λ（λ∈［0，1］）进行截取，进而得到不同的分类。
聚类方法较多，主要有基于模糊等价关系基础上的聚类与基于最大树的聚类。
（1）模糊等价关系方法
所谓模糊等价关系，是指具有自反性（rii=1）、对称性（rij=rji）与传递性（R·R⊆R）的模糊关系。
基于模糊等价关系的模糊聚类分析方法的基本思想是：由于模糊等价关系R是论域集U与自己的直积U×U上的一个模糊子集，因此可以对R进行分解，当用λ-水平对R作截集时，截得的U×U的普通子集Rλ就是U上的一个普通等价关系，也就是得到了关于U中被分类对象元素的一种。当λ由1下降到0时，所得的分类由细变粗，逐渐归并，从而形成一个动态聚类谱系图（徐建华，1994）。此类分析方法的具体步骤如下。
第一步：模糊相似关系的建立，即计算各分类对象之间相似性统计量。
第二步：将模糊相似关系R改造为模糊等价关系R′。模糊等价关系要求满足自反性、对称性与传递性。一般而言，模糊相似关系满足自反性和对称性，但不满足传递性。因此，需要采用传递闭合的性质将模糊相似关系改造为模糊等价关系。改造的方法是将相似关系R自乘，即
R2=R·R
R4=R2·R2
︙
这样计算下去，直到：R2k=Rk·Rk=Rk，则R′=Rk便是一个模糊等价关系。
第三步：在不同的截集水平下进行聚类。
（2）最大树聚类方法
基于最大树的模糊聚类分析方法的基本思路是：最大树是一个不包含回路的连通图（图4-2）；选取λ水平对树枝进行截取，砍去权重低于λ 的枝，形成几个孤立的子树，每一棵子树就是一个类的集合。此类分析方法的具体步骤如下。
图4-2 最大聚类支撑树图
第一步：计算分类对象之间的模糊相似性统计量rij，构建最大树。
以所有被分类的对象为顶点，当两点间rij不等于0时，两点间可以用树干连接，这种连接是按rij从大到小的顺序依次进行的，从而构成最大树。
第二步：由最大树进行聚类分析。
选择某一λ值作截集，将树中小于λ值的树干砍断，使相连的结点构成一类，即子树，当λ由1到0时，所得到的分类由细变粗，各结点所代表的分类对象逐渐归并，从而形成一个动态聚类谱系图。
在聚类方法中，模糊聚类法比普通聚类法有较大的突破，简化了运算过程，使聚类法更易于掌握。
（三）灰色聚类法
灰色聚类是根据不同聚类指标所拥有的白化数，按几个灰类将聚类对象进行归纳，以判断该聚类对象属于哪一类。
灰色聚类应用于地下水水质评价中，是把所考虑的水质分析点作为聚类对象，用i表示（i=1，2，…，n）；把影响水质的主要因素作为聚类指标，用j表示（j=1，2，…，m），把水质级别作为聚类灰数（灰类），用k表示（k=1，2，3）即一级、二级、三级3个灰类（罗定贵等，1995）。
灰色聚类的主要步骤：确定聚类白化数、确定各灰色白化函数fjk、求标定聚类权重ηjk、求聚类系数和按最大原则确定聚类对象分类。
1.确定聚类白化数
当各灰类白化数在数量上相差悬殊时，为保证各指标间的可比性与等效性，必须进行白化数的无量纲化处理。即给出第i个聚类对象中第j个聚类指标所拥有的白化数，i=1，2，…，n；j=1，2，…，m。
2.确定各灰色白化函数
建立满足各指标、级别区间为最大白化函数值（等于1），偏离此区间愈远，白化函数愈小（趋于0）的功效函数fij（x）。根据监测值Cki，可在图上（图4-3）解析出相应的白化函数值fjk（Cik），j=1，2，…，m；k=1，2，3。
3.求标定聚类权重
根据式（4-25），计算得出聚类权重ηjk的矩阵（n×m）。
区域地下水功能可持续性评价理论与方法研究
式中：ηjk为第j个指标对第k个灰类的权重；λjk为白化函数的阈值（根据标准浓度而定）。
图4-3 白化函数图
注：图4-3白化函数f（x）∈［0，1］，具有下述特点：①平顶部分，表示该量的最佳程度。这部分的值为最佳值，即系数（权）为1，f（x）=max=1（峰值），x∈［x2，x3］。②白化函数是单调变化的，左边部分f（x）=L（x），单调增，x∈（x1，x2］，称为白化的左支函数；右边部分f（x）=R（x），单调减，x∈［x3，x4），称为白化的右支函数。③白化函数左右支函数对称。④白化函数，为了简便，一般是直线。⑤白化函数的起点和终点，一般来说是人为凭经验确定。
4.求聚类系数
σik=∑fjk（dij）ηjk （4-26）
式中：σik为第i个聚类对象属于第k个灰类的系数，i=1，2，…，n；k=1，2，3。
5.按最大原则确定聚类对象分类
由σik构造聚类向量矩阵，行向量最大者，确定k样品属于j级对应的级别。
用灰色聚类方法进行地下水水质评价，能最大限度地避免因人为因素而造成的“失真、失效”现象。
聚类方法计算相对复杂，但是计算结果与地下水质量标准级别对应性明显，能够较全面反映地下水质量状况，也是较高层次定量研究地下水质量的重要方法。
‘贰’ 异常检测方法 二
离群点是一个数据对象，它显着不同于其他数据对象，好像它是被不同的机制产生的一样。有时也称非离群点为“正常数据”，离群点为“异常数据”。
离群点不同于噪声数据。噪声是被观测变量的随机误差或方差。一般而言，噪声在数据分析（包括离群点分析）中不是令人感兴趣的。如在信用卡欺诈检测，顾客的购买行为可以用一个随机变量建模。一位顾客可能会产生某些看上去像“随机误差”或“方差”的噪声交易，如买一份较丰盛的午餐，或比通常多要了一杯咖啡。这种交易不应该视为离群点，否则信用卡公司将因验证太多的交易而付出沉重代价。因此，与许多其他数据分析和数据挖掘任务一样，应该在离群点检测前就删除噪声。
离群点检测是有趣的，因为怀疑产生它们的机制不同于产生其他数据的机制。因此，在离群点检测时，重要的是搞清楚为什么检测到的离群点被某种其他机制产生。通常，在其余数据上做各种假设，并且证明检测到的离群点显着违反了这些假设。
离群点可以分成三类：全局离群点、情境（或条件）离群点和集体离群点。
在给定的数据集中，一个数据对象是全局离群点，如果它显着的偏离数据集中的其他对象。全局离群点是最简单的一类离群点，大部分的离群点检测方法都旨在找出全局离群点。
在给定的数据集中，一个数据对象是情境离群点，如果关于对象的特定情境，它显着的偏离其他对象。情境离群点又称为条件离群点，因为它们条件的依赖于选定的情境。一般地，在情境离群点检测中，所考虑数据对象的属性划分成两组：
情境属性 ：数据对象的情境属性定义对象的情境。一般为静态属性变量，如信用卡欺诈检测中，不同年龄、不同地区的人消费情况是不同的，先按照静态属性将人群大致分类，再检测每一类的离群点，会得到更好的结果。
行为属性 ：定义对象的特征，并用来评估对象关于它所处的情境是否为离群点。在上述例子中，行为属性可以是消费金额，消费频率等
情境离群点分析为用户提供了灵活性，因为用户可以在不同情境下考察离群点，这在许多应用中都是非常期望的。
给定一个数据集，数据对象的一个子集形成集体离群点，如果这些对象作为整体显着的偏离整个数据集。如一家供应链公司，每天处理数以千计的订单和出货。如果一个订单的出货延误，则可能不是离群点，因为统计表明延误时常发生。然而，如果有一天有100个订单延误，则必须注意。这100个订单整体来看，形成一个离群点，尽管如果单个考虑，它们每个或许都不是离群点。你可能需要更详细地整个考察这些订单，搞清楚出货问题。
与全局和情境离群点检测不同，在集体离群点检测中，不仅必须考虑个体对象的行为，而且还要考虑对象组群的行为。因此，为了检测集体离群点，需要关于对象之间联系的背景知识，如对象之间的距离或相似性测量方法。
离群点检测的统计学方法对数据的正常性做假定。假定数据集中的正常对象由一个随机过程（生成模型）产生。因此，正常对象出现在该随机模型的高概率区域中，而低概率区域中的对象是离群点。
离群点检测的统计学方法的一般思想是：学习一个拟合给定数据集的生成模型，然后识别该模型低概率区域中的对象，把它们作为离群点。有许多不同方法来学习生成模型，一般而言，根据如何指定和如何学习模型，离群点检测的统计学方法可以划分成两个主要类型： 参数方法和非参数方法。
参数方法: 假定正常的数据对象被一个以为参数的参数分布产生。该参数分布的概率密度函数给出对象被该分布产生的概率。该值越小，越可能是离群点。
非参数方法: 并不假定先验统计模型，而是试图从输入数据确定模型。非参数方法的例子包括直方图和核密度估计。
假定数据集由一个正态分布产生，然后，可以由输入数据学习正态分布的参数，并把低概率的点识别为离群点。
在正态分布的假定下，区域包含99.7%的数据，包含95.4%的数据，包含68.3%的数据。视具体情况而定，将其区域外的数据视为离群点。
这种直截了当的统计学离群点检测方法也可以用于可视化。例如盒图方法使用五数概况绘制一元输入数据：最小的非离群点值（Min）、第一个四分位数（Q1）、中位数（Q2）、第三个四分位数（Q3）和最大的非离群点值（Max）。
四分位数极差（IQR）定义为Q3-Q1。比Q1小1.5倍的IQR或者比Q3大1.5倍的IQR的任何对象都视为离群点，因为Q1-1.5 IQR和Q3+1.5 IQR之间的区域包含了99.3%的对象。
（1）使用马哈拉诺比斯距离检测多元离群点。
对于一个多元数据集，设为均值向量。对于数据集中的对象，从到的马哈拉诺比斯（Mahalanobis）距离为其中S是协方差矩阵。是一元数据，可以对它进行离群点检测。如果被确定为离群点，则也被视为离群点。
（2）使用统计量的多元离群点检测。
在正态分布的假设下，统计量可以用来捕获多元离群点。对于对象，统计量是
其中，是在第维上的值，是所有对象在第维上的均值，而是维度。如果对象的统计量很大，则该对象是离群点。
（3）使用混合参数分布
在许多情况下，数据是由正态分布产生的假定很有效。然而，当实际数据很复杂时，这种假定过于简单。在这种情况下，假定数据是被混合参数分布产生的。
混合参数分布中用期望最大化（EM）算法来估计参数。具体情况比较复杂，可以参考韩家炜的《数据挖掘：概念与技术》一书。
在离群点检测的非参数方法中，“正常数据”的模型从输入数据学习，而不是假定一个先验。通常，非参数方法对数据做较少假定，因而在更多情况下都可以使用。
使用直方图检测离群点
包括如下两步：
步骤1： 构造直方图。尽管非参数方法并不假定任何先验统计模型，但是通常确实要求用户提供参数，以便由数据学习。如指定直方图的类型（等宽或等深的）和其他参数（如直方图中的箱数或每个箱的大小）。与参数方法不同，这些参数并不指定数据分布的类型（如高斯分布）。
步骤2： 检测离群点。为了确定一个对象是否是离群点，可以对照直方图检验它。在最简单的方法中，如果该对象落入直方图的一个箱中，则该对象被看做是正常的，否则被认为是离群点。
对于更复杂的方法，可以使用直方图赋予每个对象一个离群点得分。一般可以令对象的离群点得分为该对象落入的箱的容积的倒数。得分越高，表明是离群点的概率越大。
使用直方图作为离群点检测的非参数模型的一个缺点是，很难选择一个合适的箱尺寸。一方面，如箱尺寸太小，则由很多正常对象都会落入空的或稀疏箱，因而被误识别为离群点。这将导致很高的假正例率或低精度。相反，如果箱尺寸太大，则离群点对象可能渗入某些频繁的箱中，这将导致很高的假负例率或召回率。为了解决这些问题，使用核密度估计来估计数据的概率密度分布。具体参考韩家炜的《数据挖掘：概念与技术》。
给定特征空间中的对象集，可以使用距离度量来量化对象间的相似性。基于邻近性的方法假定：离群点对象与它最近邻的邻近性显着偏离数据集中其他对象与它们近邻之间的邻近性。
有两种类型的基于邻近性的离群点检测方法：基于距离的和基于密度的方法。基于距离的离群点检测方法考虑对象给定半径的邻域。一个对象被认为是离群点，如果它的邻域内没有足够多的其他点。基于密度的离群点检测方法考察对象和它近邻的密度。这里，一个对象被识别为离群点，如果它的密度相对于它的近邻低得多。
对于待分析的数据对象集D，用户可以指定一个距离阈值r来定义对象的合理邻域。对于每个对象o，可以考察o的r-邻域中的其他对象的个数。如果D中大多数对象都远离o，即都不在o的r-邻域中，则o可以被视为一个离群点。
令是距离阈值，是分数阈值。对象是一个离群点，如果
其中是距离度量。
如何计算-离群点？一是嵌套循环方法，时间复杂度为。当数据集很大时，该方法的开销很大。为了改进性能，可以用基于网格的方法来实现。具体见韩家炜《数据挖掘》一书。
基于距离的离群点检测从全局考虑数据集。由于以下两个原因，这种离群点被看成“全局离群点”：
l 例如，一个-离群点至少远离（用参数r定量）数据集中的对象。换言之，这种离群点远离数据的大多数。
l 为了检测基于距离的离群点，需要两个距离参数，它们用于每个离群点对象。
现实世界的许多数据集都呈现更复杂的结构，那里对象可能关于其局部邻域，而不是关于整个数据分布而被视为离群点。如下图，基于距离的离群点检测方法不能捕获像o1和o2这样的局部离群点。
那么，如何确切地定义如图所示的局部离群点？这里关键的思想是，需要把对象周围的密度与对象邻域周围的密度进行比较。基于密度的离群点检测方法的基本假定是：非离群点对象周围的密度与其邻域周围的密度类似，而离群点对象周围的密度显着不同于其邻域周围的密度。
基于聚类的方法通过考察对象与簇之间的关系检测离群点。直观地，离群点是一个对象，它属于小的偏远簇，或不属于任何簇。
这导致三种基于聚类的离群点检测的一般方法。考虑一个对象。
l 该对象属于某个簇吗？如果不，则它被识别为离群点。
l 该对象与最近的簇之间的距离很远吗？如果是，则它是离群点。
l 该对象是小簇或稀疏簇的一部分吗?如果是，则该簇中的所有对象都是离群点。
下面对每一种方法考察一个例子。
例1 把离群点检测为不属于任何簇的对象。如图1所示，使用基于密度的聚类方法，如DBSCAN,注意到黑色点都属于簇，白色点a不属于任何簇，因而被认为是离群点。
图1 对象a是离群点，因为 它不属于任何簇
图2 离群点（a,b,c）都（关于簇中心）远离距它们最近的簇
例2 使用到最近簇的距离的基于聚类的离群点检测。如图2所示，使用k-均值聚类方法，可以把图2中的数据点划分成3个簇，如图中不同符号所示，每个簇中心用“+”标记。对于每个对象o，都可以根据该对象与最近簇中心的距离，赋予该对象一个离群点得分。假设到o的最近中心为c,则o与c之间的距离为dist(o,c)，c与指派到c的对象之间的平均距离为L,比率度量与平均值的差异程度。在图2中，点a,b和c都相对远离它们的对应中心，因而被怀疑是离群点。
例3 检测小簇中的离群点
迄今为止我们看到的每种方法都只检测个体离群点，因为它们一次把一个对象与数据集中的簇进行比较。然而，在大型数据中，一些离群点可能是类似的，并且形成一个小簇。例如，在入侵检测中，使用相同手段攻击系统的黑客可能形成一个簇。迄今为止所讨论的方法可能被这种离群点所欺骗。
为了解决这一问题，第三种基于聚类的离群点检测方法识别小簇或稀疏簇，并宣告这些簇中的对象也是离群点。这种方法的一个例子是FindCBLOF算法，其方法如下。
（1） 找出数据集中的簇，并把它们按大小降序排列。该算法假定大部分数据点都不是离群点，它使用一个参数来区别大簇和小簇。任何至少包含数据集中百分之（如，=90%）数据点的簇都被视为大簇，而其余的簇被看成小簇。
（2） 对于每个数据点赋予基于簇的局部离群点因子（CBLOF），对于属于大簇的点，它的CBLOF是簇的大小和该点与簇的相似性的乘积。对于属于小簇的点，它的CBLOF用小簇的大小和该点与最近的大簇的相似性的乘积计算。
CBLOF用统计学方法定义点和簇之间的相似性，代表点属于簇的概率。该值越大，点与簇越相似。CBLOF值可以检测远离任何簇的离群点。
基于聚类的离群点检测方法具有如下优点。首先，它们可以检测离群点，而不要求数据是有标号的，即它们以无监督方式检测。它们对许多类型的数据都有效。簇可以看成是数据的概括，一旦得到簇，基于聚类的方法只需要把对象与簇进行比较，以确定该对象是否是离群点，这一过程通常很快，因为与对象总数相比，簇的个数通常很小。
基于聚类的方法的缺点是：它的有效性高度依赖于所使用的聚类方法。这些方法对于离群点检测而言可能不是最优的。对于大型数据集，聚类方法通常开销很大，这可能成为一个瓶颈。
如果训练数据具有类标号，则离群点检测可以看做分类问题。基于分类的离群点检测方法的一般思想是，训练一个可以区分“正常”数据和离群点的分类模型。
基于分类的离群点检测方法通常使用一类模型（单分类模型SVDD），即构造一个仅描述正常类的分类器，不属于正常类的任何样本都被视为离群点。
基于分类的方法和基于聚类的方法可以联合使用，以半监督的方式检测离群点。
例通过半监督学习检测离群点
如上图所示，其中对象被标记为“正常”或“离群点”，或者没有标号。使用基于聚类的方法，发现一个大簇C和一个小簇C1。因为C中的某些对象携带了标号“正常”，因此可以把该簇的所有对象（包括没有标号的对象）都看做正常对象。在离群点检测中，使用这个簇的一类模型来识别离群点。类似的，因为簇C1中的某些对象携带标号“离群点”，因此宣布C1中的所有对象都是离群点。未落入C模型中的任何对象（如a）也被视为离群点。
与一般的离群点检测相比，识别情境离群点需要分析对应的情境信息。情境离群点检测方法可以根据情境是否可以清楚地识别而分成两类。
这类方法适用于情境可以被清楚识别的情况，其基本思想是把情境离群点检测问题转换成典型的离群点检测问题。具体地说，对于给定的数据对象，用两步来评估该对象是否是离群点。第一步，使用对象的情境属性识别对象的情境。第二步，使用一种传统的离群点检测方法，估计该对象的离群点得分。
在某些应用中，清楚地把数据划分成情境是不方便的或不可行的。这时，可以关于情境对正常行为建模。使用一个训练数据集，这种方法训练一个模型，关于情境属性的值，预测期望的行为属性值。然后，为了确定一个数据对象是否是情境离群点，可以在该对象的情境属性上使用该模型。如果该对象的行为属性值显着地偏离该模型的预测值，则该对象被宣布为情境离群点。
通过使用连接情境和行为的预测模型，这些方法避免直接识别具体情境。许多分类和预测技术都可以用来构建这种模型，如回归、马尔科夫模型和有穷状态自动机等等。
与情境离群点检测一样，集体离群点检测方法也可以划分为两类。第一类方法把问题归结为传统的离群点检测。其策略是识别结构单元，把每个结构单元（例如，子序列、时间序列片段、局部区域或子图）看做是一个数据对象，并提取特征。这样，集体离群点检测问题就转换成在使用提取的特征构造的“结构化对象”集上的离群点检测。一个结构单元代表原数据集中的一组对象，如果该结构单元显着地偏离提取的特征空间中的期望趋势，则它是一个集体离群点。
为集体离群点检测预先定义结构单元可能是困难的，或者是不可能的。因此，第二类方法直接对结构单元的期望行为建模。例如，为了在时间序列中检测离群点，一种方法是从序列中学习马尔科夫模型。因此，一个子序列被宣布为集体离群点，如果它显着地偏离该模型。
一般地，高维数据的离群点检测方法应该应对以下挑战：
l 离群点的解释：不仅应该能够识别检测离群点，而且能够提供离群点的解释。离群点的解释可能是，例如，揭示离群点的特定子空间，或者关于对象的“离群点性”的评估。这种解释可以帮助用户理解离群点的含义和意义。
l 数据的稀疏性：这些方法应该能处理高维空间的稀疏性。随着维度的增加，对象之间的距离严重地被噪声所左右。因此，高维空间中的数据通常是稀疏的。
l 数据子空间：它们应该以合适的方式对离群点建模，例如，自适应现实离群点的子空间和捕获数据的局部变化。在所有的子空间上使用固定的距离阈值来检测离群点捕食一种好想法，因为两个对象之间的距离随着维度增加而单调增加。
l 关于维度的可伸缩性：随着维度的增加，子空间的数量指数增加。包含所有可能的子空间的穷举组合探索不是可伸缩的选择。
高维数据的离群点检测方法可以划分成三种主要方法，包括扩充的传统离群点检测、发现子空间中的离群点和对高维离群点建模。
一种高维数据离群点检测方法是扩充的传统离群点检测方法。它使用传统的基于邻近性的离群点模型。然而，为了克服高维空间中邻近性度量恶化问题，它使用其他度量，或构造子空间并在其中检测离群点。
HilOut算法就是这种方法的一个例子。HitOut找出基于距离的离群点，但在离群点检测中使用距离的秩，而不是绝对距离。具体地说，对于每个对象o，HitOut找出o的k个最近邻，记作nn1(o),nn2(o)……nnk(o),其中k是一个依赖于应用的参数。参数o的权重定义为
所有对象按权重递减序定秩。权重最高的top-p个对象作为离群点输出，其中p是另一个用户指定的参数。
HilOut算法计算每个对象的k-最近邻开销很大，当维度很高并且数据很大时不能伸缩。
另一种方法则是通过维归约，把高维离群点检测问题归结为较低维上的离群点检测。其基本思想是，把高维空间归约到低维空间，那里标准的距离度量仍然能够区分离群点。如果能够找到这样的较低维空间，则可以用传统的离群点检测方法。
为了降低维度，可以对离群点检测使用或扩充一般的特征特征选择和提取方法。例如，可以用主成分分析（PCA）来提取一个低维空间。
高维数据中离群点检测的另一种方法是搜索各种子空间中的离群点。其唯一的优点是，如果发现一个对象是很低维度的子空间的离群点，则该子空间提供了重要信息，解释该对象为什么和在何种程度上是离群点。
如何检测子空间中的离群点，一种方法是基于网格的子空间离群点检测。具体做法见韩家炜《数据挖掘》。
另一种方法是试图直接为高维离群点建立一个新模型。这种方法通常避免邻近性度量，而是采用新的启发式方法来检测离群点。具体做法见韩家炜《数据挖掘》。
‘叁’ 什么是基于聚类的离群点监测方法
本论文提出来一个聚类方法用以检测离群点。通过使用k均值聚类算法来从数据集中划分聚类。离聚类中心比较近的点不太可能是离群点，同时我们可以从聚类中去除掉这些点。接下来计算剩下的点和离群点的距离。需要计算的离群点度的降低可能是由于一些点的去除。我们声明离群度最高的点作为离群点。实验数据使用真实数据集，并论证得知，即使所计算的数据比较少，但所提出的方法比现存的方法优越。
‘肆’ 数据挖掘之离群点检测的方法
离群点检测是数据挖掘中重要的一部分，它的任务是发现与大部分其他对象显着不同的对象。大部分数据挖掘方法都将这种差异信息视为噪声而丢弃，然而在一些应用中，罕见的数据可能蕴含着更大的研究价值。
离群点的检测已经被广泛应用于电信和信用卡的诈骗检测、贷款审批、电子商务、网络入侵和天气预报等领域。
离群点的主要成因有：数据来源于不同的类、自然变异、数据测量和手机误差。
从数据范围来看，分为全局离群点和局部离群点，整体来看，某些对象没有离群特征，但是从局部来看，却显示了一定的离群性。
从数据类型来看，分为数值型离群点和分类型离群点，这是以数据集的属性类型进行划分的。
从属性的个数来看，分为一维离群点和多维离群点，一个对象可能有一个或多个属性。
大部分的基于统计的离群点检测方法是构建一个概率分布模型，并计算对象符合该模型的概率，把具有低概率的对象视为离群点。基于统计模型的离群点检测方法的前提是必须知道数据集服从什么分布；对于高维数据，检验效果可能很差。
通常可以在数据对象之间定义邻近性度量，把原理大部分点的对象视为离群点。二位或三维的数据可以做散点图观察；大数据集不适用；对参数选择敏感；具有全局阈值，不能处理具有不同密度区域的数据集
考虑数据集可能存在不同密度区域这一事实，从基于密度的观点分析，离群点是在低密度区域中的对象。一个对象的离群点得分是该对象周围密度的逆。给出了对象是离群点的定量度量，并且即使数据具有不同的区域也能够很好的处理；大数据集不适用；参数选择是困难的。
一种利用聚类检测离群点的方法是丢弃远离其他簇的小簇；另一种更系统的方法，首先聚类所有帝乡，然后评估对象属于簇的程度。基于聚类技术来发现离群点可能是高度有效的；聚类算法产生的簇的质量对该算法产生的离群点的质量影响非常大。
基于统计模型的离群点检测方法需要满足统计学原理，如果分布一直，则检验可能非常有效。基于邻近度的离群点检测方法比统计学方法更一般、更容易使用，因为确定数据集有意义的邻近度量比确定他的统计分布更容易。基于密度的离群点检测与基于邻近度的离群点检测密切相关，因为密度常用邻近度定义：一种是定义密度为到K个最邻近的平均距离的倒数，如果该距离小，则密度高；另一种是使用DBSCAN聚类算法，一个对象周围的密度等于该对象指定距离d内对象的个数。
‘伍’ 异常点检测方法
一、基本概念
异常对象被称作离群点。异常检测也称偏差检测和例外挖掘。
常见的异常成因：数据来源于不同的类（异常对象来自于一个与大多数数据对象源（类）不同的源（类）的思想），自然变异，以及数据测量或收集误差。
异常检测的方法：
（1）基于模型的技术：首先建立一个数据模型，异常是那些同模型不能完美拟合的对象；如果模型是簇的集合，则异常是不显着属于任何簇的对象；在使用回归模型时，异常是相对远离预测值的对象。
（2）基于邻近度的技术：通常可以在对象之间定义邻近性度量，异常对象是那些远离其他对象的对象。
（3）基于密度的技术：仅当一个点的局部密度显着低于它的大部分近邻时才将其分类为离群点。
二、异常点检测的方法
1、统计方法检测离群点
统计学方法是基于模型的方法，即为数据创建一个模型，并且根据对象拟合模型的情况来评估它们。大部分用于离群点检测的统计学方法都是构建一个概率分布模型，并考虑对象有多大可能符合该模型。离群点的概率定义：离群点是一个对象，关于数据的概率分布模型，它具有低概率。这种情况的前提是必须知道数据集服从什么分布，如果估计错误就造成了重尾分布。异常检测的混合模型方法：对于异常检测，数据用两个分布的混合模型建模，一个分布为普通数据，而另一个为离群点。
聚类和异常检测目标都是估计分布的参数，以最大化数据的总似然（概率）。聚类时，使用EM算法估计每个概率分布的参数。然而，这里提供的异常检测技术使用一种更简单的方法。初始时将所有对象放入普通对象集，而异常对象集为空。然后，用一个迭代过程将对象从普通集转移到异常集，只要该转移能提高数据的总似然（其实等价于把在正常对象的分布下具有低概率的对象分类为离群点）。（假设异常对象属于均匀分布）。异常对象由这样一些对象组成，这些对象在均匀分布下比在正常分布下具有显着较高的概率。
优缺点：（1）有坚实的统计学理论基础，当存在充分的数据和所用的检验类型的知识时，这些检验可能非常有效；（2）对于多元数据，可用的选择少一些，并且对于高维数据，这些检测可能性很差。
2、基于邻近度的离群点检测。
一个对象是异常的，如果它远离大部分点。这种方法比统计学方法更一般、更容易使用，因为确定数据集的有意义的邻近性度量比确定它的统计分布更容易。一个对象的离群点得分由到它的k-最近邻的距离给定。离群点得分对k的取值高度敏感。如果k太小（例如1），则少量的邻近离群点可能导致较低的离群点得分；如果k太大，则点数少于k的簇中所有的对象可能都成了离群点。为了使该方案对于k的选取更具有鲁棒性，可以使用k个最近邻的平均距离。
优缺点：（1）简单；（2）缺点：基于邻近度的方法需要O(m^2)时间，大数据集不适用；（3）该方法对参数的选择也是敏感的；（4）不能处理具有不同密度区域的数据集，因为它使用全局阈值，不能考虑这种密度的变化。
3、基于密度的离群点检测。
从基于密度的观点来说，离群点是在低密度区域中的对象。一个对象的离群点得分是该对象周围密度的逆。基于密度的离群点检测与基于邻近度的离群点检测密切相关，因为密度通常用邻近度定义。一种常用的定义密度的方法是，定义密度为到k个最近邻的平均距离的倒数。如果该距离小，则密度高，反之亦然。另一种密度定义是使用DBSCAN聚类算法使用的密度定义，即一个对象周围的密度等于该对象指定距离d内对象的个数。需要小心的选择d，如果d太小，则许多正常点可能具有低密度，从而具有高离群点得分。如果d太大，则许多离群点可能具有与正常点类似的密度（和离群点得分）。使用任何密度定义检测离群点具有与基于邻近度的离群点方案类似的特点和局限性。特殊地，当数据包含不同密度的区域时，它们不能正确的识别离群点。
为了正确的识别这种数据集中的离群点，我们需要与对象邻域相关的密度概念，也就是定义相对密度。常见的有两种方法：（1）使用基于SNN密度的聚类算法使用的方法；（2）用点x的密度与它的最近邻y的平均密度之比作为相对密度。
使用相对密度的离群点检测（局部离群点要素LOF技术）：首先，对于指定的近邻个数（k），基于对象的最近邻计算对象的密度density(x,k) ，由此计算每个对象的离群点得分；然后，计算点的邻近平均密度，并使用它们计算点的平均相对密度。这个量指示x是否在比它的近邻更稠密或更稀疏的邻域内，并取作x的离群点得分（这个是建立在上面的离群点得分基础上的）。
优缺点：
（1）给出了对象是离群点的定量度量，并且即使数据具有不同的区域也能够很好的处理；
（2）与基于距离的方法一样，这些方法必然具有O(m2)的时间复杂度。对于低维数据使用特定的数据结构可以达到O(mlogm)；
（3）参数选择是困难的。虽然LOF算法通过观察不同的k值，然后取得最大离群点得分来处理该问题，但是，仍然需要选择这些值的上下界。
4、基于聚类的技术
一种利用聚类检测离群点的方法是丢弃远离其他簇的小簇。这个方法可以和其他任何聚类技术一起使用，但是需要最小簇大小和小簇与其他簇之间距离的阈值。这种方案对簇个数的选择高度敏感。使用这个方案很难将离群点得分附加到对象上。一种更系统的方法，首先聚类所有对象，然后评估对象属于簇的程度（离群点得分）（基于原型的聚类可用离中心点的距离来评估，对具有目标函数的聚类技术该得分反映删除对象后目标函数的改进（这个可能是计算密集的））。基于聚类的离群点：一个对象是基于聚类的离群点，如果该对象不强属于任何簇。离群点对初始聚类的影响：如果通过聚类检测离群点，则由于离群点影响聚类，存在一个问题：结构是否有效。为了处理该问题，可以使用如下方法：对象聚类，删除离群点，对象再次聚类（这个不能保证产生最优结果）。还有一种更复杂的方法：取一组不能很好的拟合任何簇的特殊对象，这组对象代表潜在的离群点。随着聚类过程的进展，簇在变化。不再强属于任何簇的对象被添加到潜在的离群点集合；而当前在该集合中的对象被测试，如果它现在强属于一个簇，就可以将它从潜在的离群点集合中移除。聚类过程结束时还留在该集合中的点被分类为离群点（这种方法也不能保证产生最优解，甚至不比前面的简单算法好，在使用相对距离计算离群点得分时，这个问题特别严重）。
对象是否被认为是离群点可能依赖于簇的个数（如k很大时的噪声簇）。该问题也没有简单的答案。一种策略是对于不同的簇个数重复该分析。另一种方法是找出大量小簇，其想法是（1）较小的簇倾向于更加凝聚，（2）如果存在大量小簇时一个对象是离群点，则它多半是一个真正的离群点。不利的一面是一组离群点可能形成小簇而逃避检测。
优缺点：
（1）基于线性和接近线性复杂度（k均值）的聚类技术来发现离群点可能是高度有效的；
（2）簇的定义通常是离群点的补，因此可能同时发现簇和离群点；
（3） 产生的离群点集和它们的得分可能非常依赖所用的簇的个数和数据中离群点的存在性；
（4）聚类算法产生的簇的质量对该算法产生的离群点的质量影响非常大。
新颖性和离群值检测
离群值检测：训练数据包含离群值，即与其他观测值相距甚远的观测值。离群检测估计器会尝试拟合训练数据最集中的区域，忽略异常观察。
新颖性检测：训练数据不受异常值的污染，有兴趣检测新观察值是否是异常值。该情况下离群值也称为新颖性。
离群值检测和新颖性检测均用于异常检测，离群值检测称为无监督异常检测，新颖性检测称为半监督异常检测。离群值检测的情况下，离群值/异常不能形成密集的群集，可假设离群值/异常位于低密度区域；新颖性检测的情况下，只要新颖性/异常位于训练数据的低密度区域，就可以形成密集的簇。
通过对玩具数据集进行异常检测比较异常检测算法
数据集中包含一种或两种模式（高密度区域），以说明算法处理多模式数据的能力。
对于每个数据集，将生成15%的样本作为随机均匀噪声。该比例是OneClassSVM的nu参数和其他异常值检测算法的污染参数提供的值。离群值之间的决策边界以黑色显示，但是LOF除外，因为当采用LOF用于离群值检测时，没有适用于新数据的预测方法。
OneClassSVM对异常值敏感，对异常值检测执行的不好。当训练集不受异常值污染时，此估计器最适合新颖性检测。即不适用在高维中进行离群值检测或者不对基础数据的分布进行任何假设，OneClassSVM在这些情况下可能会根据其超参数给出有用的结果。
covariance EllipticEnvelope（协方差椭圆密度）假定数据是高斯分布并学习一个椭圆。在数据不是单峰时，会退化。此估计器对异常值具有鲁棒性。
IsolationFrorest和LocalOutlierFactor针对多模式数据集效果显着。LOF针对第三种数据集，明显优于其它三种估计器，该数据集中两种模式的密度不同。LOF的局部方面，即它仅将一个样本的异常评分与其邻居评分作比较，从何体现了该方法的优势。
针对最后一个均匀分布在超立方体中的数据集，很难说一个样本比另一个样本异常得多。除了OneClassSVM有些过拟合外，所有估计器都针对该情况提出不错的解决方案。针对这种情况，应该仔细观察样本的异常分数，性能好的估算器应该为所有样本分配相似的分数。
使用局部离群因子（LOF）进行离群值检测
LOF算法是一种无监督的异常检测方法，可计算给定数据点相对于其邻居的局部密度偏差。其中密度远低于其邻居的样本为异常值。
LOF算法的优势在于同时考虑了数据集的局部和全局属性：即使在异常样本具有不同底层密度的数据集中，仍能保持良好性能。问题不在于样本有多孤立，而在于样本相对于周围邻域有多孤立。
通常考虑的邻居数量（1）大于群集必须包含的最小样本数量，以便其他样本可以是相对于该群集的局部离散值；（2）小于可能是局部异常值的最大进距采样数，此类消息通常不可用，采用n_neighbors=20。
具有局部异常值的新颖性检验
LOF是一种无监督的异常检测方法，可计算给定数据点相对于其邻居的局部密度偏差，密度远低于其邻居的样本为异常值。LOF用于新颖性检验时，切勿在训练集上使用预测、决定函数、实例得分，会导致结果错误。只能对新的看不见的数据（不在训练集中）使用这些方法。
通常考虑邻居数量（1）大于群集必须包含的最小样本数，以便其他样本可以是相对于该群集的局部离群值；（2）小于可能是局部异常值的最大进距采样数，此类消息通常不可用，采用n_neighbors=20。
隔离林
在高维数据集中执行异常检测的一种有效方法是使用随机森林，分离的观察通过随机选择一个函数，随机选择所选择的特征的最大值和最小值之间的分割值。递归分区可用树结构表示，隔离样本所需的拆分数量等于从根节点到终止结点的路径长度。随机树的森林中的平均路径长度是对正态性和决策函数的度量。随机分区产生的异常路径明显较短，因此如果随机树森林为特定样本生成的较短路径，则该树代表的值很可能是异常的。
OneClassSVM
无监督的离群值检测，支持高维分布，基于libsvm
不假定数据分布的任何参数形式，可以更好的对数据的复杂形状进行建模，能够捕获真实的数据结构，难点在于调整核函数宽度参数，以便在数据散布矩阵的形状和数据过度拟合的风险间取得折中。
协方差椭圆密度
用于检测高斯分布数据集中的异常值的对象
经验协方差估计（作为非稳健估计）受到观测值异质结构的高度影响；鲁棒协方差估计能够集中于数据分布的主要模式，但是它坚持假设数据是高斯分布，产生了对数据结构的某些估计，在一定程度上是准确的。
HBOS单维效果极佳，但是标准差方法的mask 掩码效应严重。例如 数据通常在100以内，但是有两个异常点，500，1000000。这个算法就不能检出500这个异常点。
对比而言，孤立森林理论上更适合大数据的异常检测，且无掩码效应。孤立森林确定异常时训练只用样本数据。每颗树样本数量默认只有256个，默认只用100颗树。所以理论上25600个样本就能确定海量数据中的异常点了。
Sklearn的 isolation forest 例子默认是读入全量数据再采样。如果配上warm up 选项就能分批放入采样。
异常检测的深度学习研究综述