当前位置:   article > 正文

【异常检测】数据挖掘领域常用异常检测算法总结以及原理解析(二)_孤立森林算法通过随机选择特征来构建多棵孤立树,然后将数据点映射到这些树上

孤立森林算法通过随机选择特征来构建多棵孤立树,然后将数据点映射到这些树上

【异常检测】数据挖掘领域常用异常检测算法总结以及原理解析(二)


一、基于树的方法

基于树的异常检测方法能够处理非线性关系,并且在处理大型数据集时相对高效。但它们对于高维数据的处理能力往往较弱,并且在异常点不是特别稀有时的检测效果会下降。

1. 孤立森林(Isolation Forest)

孤立森林是一种高效的异常检测算法,它基于一个简单的假设:异常数据点通常是稀少的,且与正常数据点相比有着显著的不同。因此,相比于正常数据点,异常数据点更容易被“孤立”。孤立森林通过构建多棵“孤立树”来随机地“孤立”每个数据点。在每棵孤立树中,算法随机选择一个特征并随机选择该特征的一个切分值,以此将数据分成两部分。这个切分过程重复进行,直到每个点都被孤立或达到了树的限定高度。异常点因其少数特征的不同,通常在这个过程中较早地被孤立,因此它们在孤立树中的路径会更短。

算法原理

  • 1.孤立的概念:孤立森林的基本思想是,异常点因为数值特征的不同,相比于正常点更容易被孤立。这种方法不是构建一个正常数据的模型,而是直接识别出异常点。
  • 2.构建孤立树(iTrees):算法首先从数据集中随机抽取一个样本子集,然后为这个子集构建一棵孤立树。在构建树的过程中,每次随机选择一个特征及其一个随机切分值,将数据集分为两部分,直到数据点被孤立(即无法进一步分割)或达到预设的树的最大高度。
  • 3.孤立路径长度:对于每个数据点,其在树中的路径长度被用作异常评分的依据。路径长度是从根节点到达该点的边数。异常点因为更易被孤立,通常在树中的路径较短。
  • 4.构建森林:重复上述步骤,构建多棵孤立树,形成一个“森林”。每棵树都是独立构建的,且基于数据集的不同随机子集。
  • 5.评分机制:最后,数据点的异常得分是基于在所有树中的平均路径长度。较短的平均路径长度表明该点更有可能是异常。

适用场景

  • 1.大规模数据集:孤立森林算法在处理大规模数据集时效率很高,尤其是在数据维度不是特别高的情况下。
  • 2.不需要先验知识:由于该算法不依赖于数据的分布假设,因此适用于不了解数据分布的场景。
  • 3.处理多维数据:孤立森林能够处理多维特征空间中的数据,使其适用于多种类型的数据集。
  • 4.在线异常检测:孤立森林支持在线学习,可以应用于实时异常检测系统。

孤立森林的优点在于其简单高效,尤其适合处理大规模数据集。它不需要先验知识,且对数据分布的假设较少。然而,孤立森林可能在处理包含大量噪声的数据集时表现不佳,同时对参数选择(如树的数量和深度)敏感。

孤立森林也有其局限性。例如,当数据集中的异常点不是特别稀有或者异常点与正常点在特征空间中有重叠时,该算法的性能可能会受到影响。此外,孤立森林对高维数据的处理能力也不如低维数据,因为在高维空间中,所有点都倾向于互相“孤立”。因此,在应用孤立森林之前,需要仔细考虑数据集的特性和问题的具体需求。

二、基于聚类的方法

基于聚类的异常检测是一种无监督学习方法,它依赖于聚类算法来识别数据中的异常或离群值。这种方法的核心思想是,正常数据点会形成聚类,而异常数据点则不会归入这些聚类,或者与任何聚类的中心距离较远。

1、K-均值聚类(k-Means Clustering)

K-Means聚类进行异常数据检测是一种常见的无监督学习方法。

算法原理
1.聚类过程:

  • 初始化:首先随机选择K个点作为初始聚类中心。
  • 分配:将每个数据点分配到最近的聚类中心,形成K个聚类。
  • 更新:重新计算每个聚类的中心,即计算聚类内所有点的均值。
  • 迭代:重复分配和更新步骤,直到聚类中心不再显著变化或达到预设的迭代次数。
    2.异常检测:
  • 在K-Means聚类完成后,数据点被分配到了最近的聚类中。
  • 异常点通常是那些距离其所属聚类中心较远的点。
  • 通过设置一个距离阈值,可以识别那些与聚类中心距离超过该阈值的数据点作为异常。

应用场景
1.数据具有球形聚类:

  • K-Means最适用于数据点在空间中自然形成球形或近似球形聚类的情况。

2.异常是离群值:

  • 当异常数据表现为与大部分数据点明显不同且分散的离群值时,K-Means特别有效。

3.大规模数据集:

  • K-Means算法相对简单且易于扩展,适合处理大规模数据集。

4.在线性空间中分布的数据:

  • 当数据分布在线性空间中,K-Means能够更有效地识别出聚类。

异常检测关键点

  • 选择K值:K值的选择对于检测异常至关重要。一个不合适的K值可能导致正常数据被错误地标记为异常,或者忽略真正的异常点。
  • 距离度量:K-Means通常使用欧几里得距离作为度量,但在某些情况下,可能需要考虑其他距离度量方法。
  • 数据预处理:在应用K-Means之前,数据预处理(如归一化或标准化)是必要的,因为K-Means对于数据的尺度非常敏感。
  • 异常点的定义:异常点的定义取决于具体应用。通常,距离聚类中心较远的点被认为是异常的,但具体多远算“异常”需要根据数据的特性和应用场景来确定。
  • 局限性:K-Means假设聚类是凸形的,对于非球形聚类或大小差异很大的聚类,其效果可能不佳。此外,如果异常点足够多,以至于形成自己的聚类,K-Means可能无法有效地检测它们。

2. 基于密度的聚类(DBSCAN)

使用DBSCAN聚类进行异常数据检测是一种流行的聚类方法。

算法原理
1.核心概念:

  • 核心点:在指定半径ε内至少有MinPts个点的点。
  • 边界点:在ε半径内少于MinPts但在核心点的ε邻域内的点。
  • 噪声点:既不是核心点也不是边界点的点。

2.聚类过程:

  • 识别核心点:首先识别所有核心点。
  • 扩展聚类:从一个核心点开始,将所有在其ε邻域内的点加入到相同的聚类中。如果这些点中有其他核心点,则继续扩展聚类。
  • 边界点和噪声点:边界点可能属于一个或多个聚类,而噪声点不属于任何聚类。

3.异常检测:

  • 在DBSCAN聚类完成后,噪声点被视为异常点。
  • 这些点既不属于任何核心点生成的聚类,也不足以成为核心点。

应用场景
1.数据聚类形状不规则

  • 当数据集中的聚类形状不规则或者聚类的大小和密度差异较大时,DBSCAN特别有效。

2.噪声和异常点检测

  • DBSCAN天然适合于识别和处理噪声和异常点。

3.不需要指定聚类数量

  • 与K-Means不同,DBSCAN不需要预先指定聚类的数量。

4.数据空间中有密度差异的区域

  • 对于具有高密度区域和低密度区域的数据集,DBSCAN能够有效地区分。

异常检测关键点

  • 参数选择:ε和MinPts是DBSCAN的两个关键参数,需要根据数据集的特性仔细选择。
  • 缩放敏感性:像所有基于距离的算法一样,DBSCAN对于数据的缩放非常敏感,因此数据预处理(如归一化)是重要的。
  • 局限性:当数据集中不同聚类的密度差异较大时,选择一个合适的ε和MinPts对于所有聚类都有效可能比较困难。
  • 效率问题:对于非常大的数据集,DBSCAN的计算效率可能是一个问题,尤其是在计算密度达到要求的区域时。

三、基于降维的方法

基于降维的异常检测方法是一类利用数据降维技术来发现异常模式的方法。降维的目标是减少数据集的维度,同时保留足够的信息。在异常检测中,降维有助于突出异常点,因为异常通常在降维后更容易被识别。

1. 主成分分析(Principal Component Analysis,PCA)

PCA(Principal Component Analysis)主成分分析是一种常用的降维技术,它通过线性变换将高维数据转换为低维数据,保留数据中最重要的信息。在异常检测中,PCA可以用来减少数据的维度,提取最重要的特征,从而帮助识别异常值或异常模式。

算法原理

  • 1.数据预处理:对数据进行标准化处理,使得每个特征具有相同的尺度,以避免某些特征对PCA结果产生过大影响。
  • 2.协方差矩阵计算:PCA通过计算特征之间的协方差矩阵来找到数据中的主成分。协方差矩阵描述了不同特征之间的相关性程度。
  • 3.特征值分解:对协方差矩阵进行特征值分解(或奇异值分解),得到特征值和对应的特征向量。
  • 4.特征向量选择:根据特征值的大小排序特征向量,选择最大的k个特征值对应的特征向量(k为降维后的目标维度)。
  • 5.投影数据:使用选定的特征向量构建投影矩阵,将原始数据投影到新的低维空间中。

应用步骤

  • 1.数据准备:收集并预处理数据,确保数据质量良好,并进行必要的标准化处理。
  • 2.PCA模型训练:对预处理后的数据应用PCA模型,通过计算协方差矩阵、特征值分解等步骤来找到主成分。
  • 3.选择主成分数量:通过解释方差比或者累积贡献率等方法确定保留的主成分数量,这个数量决定了降维后的维度。
  • 4.降维处理:使用选择的主成分对数据进行投影,从高维空间映射到低维空间。
  • 5.异常检测:在降维后的空间中,应用适当的异常检测算法(如基于距离、密度或者模型的方法)来识别异常样本或异常模式。

适用场景

  • 1.高维数据:当数据具有很高的维度时,PCA可以帮助降低计算复杂度,并揭示数据中的主要特征。
  • 2.特征相关性:当数据中存在相关性较高的特征时,PCA可以去除冗余信息,减少噪音对异常检测的影响。
  • 3.可解释性:PCA提供了主成分,这些成分对应于原始数据中的最大方差,能够提供较好的可解释性,有助于理解数据的结构。
  • 4.异常检测:PCA可以帮助提取最重要的特征,使异常点在降维后更容易被检测到。
# 使用Elliptic Envelope进行异常检测
envelope = EllipticEnvelope(contamination=0.05)  # contamination表示异常值的比例
envelope.fit(data_pca)

# 预测异常值
outliers_predicted = envelope.predict(data_pca)
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6

2. 自编码器(AutoEncoder)

AutoEncoder(自编码器)是一种无监督学习神经网络模型,用于学习数据的低维表示,是一种非线性降维方法(PCA是线性降维),在异常检测中,AutoEncoder通常被用来降低数据维度,并尝试重构输入数据,通过比较重构数据与原始数据的差异来识别异常。

根据正常数据训练出来的AutoEncoder,能够将正常样本重建还原,但是却无法将异于正常分布的数据点较好地还原,导致还原误差较大。因此如果一个新样本被编码,解码之后,它的误差超出正常数据编码和解码后的误差范围,则视作为异常数据。需要注意的是,AutoEncoder训练使用的数据是正常数据(即无异常值),这样才能得到重构后误差分布范围是多少以内是合理正常的。所以AutoEncoder在这里做异常检测时,算是一种有监督学习的方法。

算法原理

  • 1.编码器(Encoder):将输入数据映射到低维空间的过程。编码器网络层将原始输入数据压缩到一个潜在表示(latent representation)或编码后的低维向量。
  • 2.解码器(Decoder):将编码后的数据映射回原始输入空间的过程。解码器网络层尝试将编码后的潜在表示映射回原始维度,重建与原始输入尽可能相似的数据。
  • 3.损失函数(Loss Function):自编码器的目标是尽可能准确地重构原始输入。因此,损失函数通常是衡量重构数据与原始输入之间差异的函数。
  • 4.训练过程:通过最小化重构误差(损失函数)来训练模型。模型通过学习数据的内部表示,捕捉了数据中的主要特征,从而能够重构正常模式的数据。

应用步骤

  • 1.数据准备:收集并预处理数据,确保数据质量良好,并进行必要的标准化处理。
  • 2.构建AutoEncoder模型:设计并构建AutoEncoder模型,包括编码器和解码器部分。选择合适的网络结构和超参数。
  • 3.模型训练:使用正常的训练数据来训练AutoEncoder模型,使其学习数据的潜在表示。
  • 4.重构数据:使用训练好的模型对输入数据进行重构,并计算重构数据与原始数据之间的差异或重构误差。
  • 5.异常检测:根据重构误差设定阈值,当重构误差超过阈值时,将数据标记为异常。

适用场景

  • 1.复杂数据结构:适用于处理具有复杂特征结构和高维度的数据。
  • 2.无标签数据:AutoEncoder是一种无监督学习方法,适用于无标签数据的异常检测。
  • 3.特征学习:AutoEncoder能够学习数据的潜在表示,从而能够捕捉数据中的主要特征,对于异常检测有较好的表现。
  • 4.噪声鲁棒性:AutoEncoder在训练过程中有一定的噪声鲁棒性,对一些噪声数据有一定的容忍度。

四、基于分类的方法

1. 单类支持向量机(One-Class SVM)

这是一种适用于高维数据的无监督算法,通过构造一个超平面来区分正常点和异常点。

算法原理

  • 1.支持向量机基础:SVM是一种监督学习算法,用于分类和回归。在One-Class SVM中,使用了SVM的思想,但在训练时只使用了正常类别的样本。
  • 2.目标函数:One-Class SVM的目标是找到一个超平面,使得正常样本被嵌入到超平面的一侧,并使得在该侧的正常样本最大化。这个超平面被称为“决策边界”或“分隔超平面”。
  • 3.核函数:One-Class SVM通常使用核函数来将样本映射到高维空间,以便更好地找到在高维空间中的决策边界。
  • 4.松弛变量:在训练过程中,One-Class SVM引入了松弛变量(slack variables),以容忍一些正常样本位于决策边界的错误一侧。

应用步骤

  • 1.数据准备:收集并预处理数据,确保正常样本的数据质量良好,并进行必要的标准化处理。
  • 2.模型训练:使用仅包含正常样本的训练集来训练One-Class SVM模型。在训练过程中,模型学习正常数据的特征,构建一个表示正常数据分布的决策边界。
  • 3.模型评估:使用训练好的模型对新样本进行评估。如果一个样本位于决策边界错误一侧,可能被认为是异常。
  • 4.调整参数:根据实际情况调整One-Class SVM的超参数,例如核函数的选择、松弛变量的权重等,以提高模型性能。

适用场景:

  • 1.无监督异常检测:One-Class SVM属于无监督学习,适用于只有正常样本的情况,无需异常标签。
  • 2.高维数据:One-Class SVM在处理高维数据时表现良好,例如图像、文本等。
  • 3.非常规分布:适用于正常样本分布相对单一或特殊的情况,对于正常样本的分布有一定的假设。
  • 4.异常样本较少:当异常样本相对较少时,One-Class SVM可以更好地适应。

五、基于时序预测的方法

1. 差分自回归移动平均模型(ARIMA)

ARIMA(差分自回归移动平均模型)是一种经典的时间序列分析方法,常用于预测时间序列数据。虽然ARIMA本身不是专门用于异常检测的算法,但可以通过对时间序列数据的残差进行分析,来检测异常

算法原理

  • 1.ARIMA模型:ARIMA是一个基于时间序列数据建模的方法,其核心思想是通过差分、自回归和移动平均来捕捉数据中的趋势、季节性和随机成分。
  • 2.差分操作:ARIMA模型中的差分操作用于消除数据的非平稳性,使其变得更加平稳。通过对时间序列数据进行差分,可以得到一个差分序列,使得数据在趋势和季节性方面更加稳定。
  • 3.模型建立:ARIMA模型有三个主要参数:p(自回归阶数)、d(差分次数)、q(移动平均阶数)。通过分析自相关图(ACF)和偏自相关图(PACF),可以选择合适的p、d、q值。
  • 4.残差分析:建立ARIMA模型后,通过对模型残差进行分析,可以检查模型是否能够很好地捕捉数据中的模式。如果残差中存在异常值,可能表明模型对数据的拟合不够好。

应用步骤

  • 1.数据准备:收集并预处理时间序列数据,确保数据质量良好,并进行必要的差分操作以使数据平稳。
  • 2.模型建立:通过对自相关图(ACF)和偏自相关图(PACF)的分析,选择合适的ARIMA模型参数(p、d、q)。
  • 3.训练模型:使用选定的参数训练ARIMA模型。
  • 4.残差分析:分析模型的残差,可以使用残差图、残差的自相关图等来检查是否存在异常值。
  • 5.异常检测:根据残差分析的结果,如果发现残差中存在异常值,可以将这些异常值标记为异常。

适用场景:

  • 1.时间序列数据:ARIMA主要用于时间序列数据,适用于具有一定趋势和季节性的数据。
  • 2.稳定性:ARIMA对于稳定的时间序列数据表现良好,不适用于非平稳性的数据。
  • 3.趋势和季节性:适用于具有明显趋势和季节性的数据,可以通过ARIMA模型较好地拟合这些模式。
  • 4.异常检测要求不高:ARIMA对于异常检测的要求相对较低,适用于一般性的异常检测任务。如果异常值对于任务的影响较大,可能需要考虑其他更专门的异常检测方法。
model = ARIMA(data, order=(2, 1, 3))
results = model.fit()
results.forecast(5)
  • 1
  • 2
  • 3

总结

欢迎关注我的公众号~

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/小舞很执着/article/detail/855424
推荐阅读
相关标签
  

闽ICP备14008679号