一种跳过平稳区域的流数据异常检测方法

摘要

本发明公开了一种跳过平稳区域的流数据异常检测方法，通过对窗口中的数据空间进行网格单元划分，得到非空网格单元；在窗口滑动过程中，以非空网格单元的权重累积净变作为区域内数据密度变化程度的度量，跳过更新相对平稳数据区域中数据点的局部可达密度和局部异常因子；仅将含有估计点的θK最近邻点的区域用于估计局部异常因子，减少对不必要的数据点进行遍历。最后通过非空网格单元中局部异常异常因子的上下界实现非空网格单元和数据点两个层级的异常检测，即首先识别出包含有前n个异常值的非空网格单元，再检索出前n个异常数据点。本发明解决现有算法难以有效处理大量流数据的难题，使桥梁健康监测系统能高效准确地识别异常数据，以便维护桥梁的健康安全。

权利要求

1.一种跳过平稳区域的流数据异常检测方法，其特征在于，该方法包括以下步骤：(1)数据预处理：从桥梁健康监测系统传感器中实时采集数据，根据系统采样频率和需要不同选择若干个采样时间间隔为一个窗口，将所述窗口中的数据进行缺失值补全、归一d

化操作，得到数据空间X；

d

(2)划分网格单元：将步骤(1)得到的数据空间X 分为对角线长度为θR的d维网格单元，所述网格单元包含非空网格单元，其中，i表示非空网格单元的索引，wi表示第i个非空网格单元的权重，kci表示第i个非空网格单元的中心坐标；将非空网格单元集合{|i＝1，...，m}作为权重分布网格G；其中，m表示非空网格单元的个数；θR为不同场景下非空网格单元个数与窗口中数据点数量之比；

prep

(3)更新数据分布：窗口滑动时，记窗口滑动前的权重分布网格为G ，记录消失在窗口中的消失数据点集合Sexp，同时记录新出现的新数据点集合Snew，将{|i＝1，...，m}分别作为第一分布网格Gexp和第二分布网格Gnew，对于第一分布网格Gexp遍历消失数据点集合Sexp，将消失数据点集合Sexp中的每一个数据点加入到对应的非空网格单元，并记录其权重，更新第一分布网格Gexp；对于第二分布网格Gnew遍历新数据点集合Snew，将新数据点集合Snew中的每一个数据点加入到对应的非空网格单元，并记录其权重，更新第二分布网格Gnew，随后将更新的第二分布网格Gnew和更新的第一分布网格Gexp对应非空网格单元的权重作差，将{|i＝1，...，m}作为净变权重分布网格ΔG，再由窗口滑动前的权重分布prep curr

网格G 加上净变权重分布网格ΔG可得到当前权重分布网格G ；

curr

(4)跳过平稳区域：遍历当前权重分布网格G 的中心坐标kci，计算数据点x与中心坐标kci的距离，取θK个最近的kci组成θK最近邻核中心集合KC(x)，遍历净变权重分布网格ΔG中的，当所述数据点x与净变权重分布网格ΔG中的kci的欧氏距离小于等于所述数据点x与其的第θK最近邻核中心 的欧氏距离时，将满足上述条件的kci对应的Δwi组成集合ΔWt(x)；则数据点x的局部密度累积误差为：其中，tl表示上次更新密度的窗口，tc表示当前窗口，Δwj表示集合ΔWt(x)中第j个非空网格单元的权重差；

curr

每次窗口滑动时重复计算当前权重分布网格G 中核中心kci的局部密度累积误差；当核中心kci局部密度累积误差E(kci)大于误差容许阈值时，更新该核中心所在网格单元中所有数据点x的局部可达密度和局部异常因子，更新数据点x的局部可达密度和局部异常因子时，找出包含数据点x的θK最近邻数据点的非空网格单元，再遍历该非空网格单元中的数据点，估计出数据点x的第θK距离邻域 对 中的所有数据点y计算出y的第θK距离θK_dist(y)，则y到x的局部可达距离为 得到局部可达密度 和局部异常因子

并记录每个非空网格单元内最小局部异常因子LOFmin(x)及最大局部异常因子LOFmax(x)；其中 是x的θK最近邻数据点的个数；

curr curr

(5)异常检测：设初始候选网格单元Gcand为空，用G ‑Gcand表示G 中除去存在于Gcandcurr

中的非空网格单元集合，遍历G ‑Gcand中的非空网格单元，若当前Gcand中所有非空curr

网格单元的权重之和大于等于n且该非空网格单元最小局部异常因子LOFmin(x)大于G ‑curr

Gcand中最大局部异常因子LOFmax(x)，则输出当前Gcand；否则将当前G ‑Gcand中的非空网格单元加入到Gcand，若当前Gcand中所有非空网格单元的权重之和小于n则继续遍历下curr

一非空网格单元，否则比较当前Gcand最小局部异常因子LOFmin(x)是否大于G ‑Gcand中最大局部异常因子LOFmax(x)，若是则继续遍历下一非空网格单元，若不是则不将加入到Gcand且继续遍历下一非空网格单元；通过上述过程得到Gcand，再Gcand中所有数据点的局部异常因子由大到小进行排序，选出前n个异常数据点。

说明书

一种跳过平稳区域的流数据异常检测方法

技术领域

[0001] 本发明涉及大数据领域中流数据异常检测技术，尤其涉及一种跳过平稳区域的流数据异常检测方法。

背景技术

[0002] 随着大数据技术的日益成熟，异常检测已经被广泛应用到金融反欺诈、医疗诊断、网络安全检测、工业健康监测系统等不同领域当中。在桥梁健康监测系统中，为保证时刻监
测桥梁的健康状态，大量的传感器装置和超高频的数据传输使得需要采集和处理的数据呈
指数级地增长，极大地增加了异常检测时间复杂度和所需计算资源，同时也增加了准确检
测出异常点的难度。

[0003] 目前，流数据异常检测大多采用了滑动窗口的思想，只对当前窗口中的数据进行检测，这样可以极大地减少计算量。尽管如此，为保证一定的准确率，单个窗口中的数据量
依旧十分庞大。基于密度的异常检测算法在窗口切换过程中，需要对窗口内所有数据点的
2
密度进行更新，而这一操作的最坏时间复杂度高达O(n)，其中n为数据点个数。这不仅需要
大量的计算资源，还会影响异常检测的时效性，导致错过采取措施应对风险的最佳时机。因
此，为确保桥梁健康监测系统能及时准确地识别出异常数据以便于相关专业人员采取措
施、应对风险，维持桥梁的健康安全，提出一种具有高准确率和高时效性的流数据异常检测
算法具有重要的现实意义。

发明内容

[0004] 本发明的目的在于克服现有方法的不足，提出了一种跳过平稳区域的流数据异常检测方法，该方法能高效准确地检测出流式数据中异常数据点，解决现有算法难以有效处
理大量流数据的难题，使桥梁健康监测系统能高效准确地识别异常数据，以便维护桥梁的
健康安全。

[0005] 本发明的目的是通过以下技术方案来实现的：一种跳过平稳区域的流数据异常检测方法，该方法包括以下步骤：

[0006] (1)数据预处理：从桥梁健康监测系统传感器中实时采集数据，根据系统采样频率和需要不同选择若干个采样时间间隔为一个窗口，将所述窗口中的数据进行缺失值补全、
d
归一化操作，得到数据空间X；

[0007] (2)划分网格单元：将步骤(1)得到的数据空间Xd分为对角线长度为θR的d维网格单元，所述网格单元包含非空网格单元，其中，i表示非空网格单元的索引，wi表示第i
个非空网格单元的权重，kci表示第i个非空网格单元的中心坐标；将非空网格单元集合{<
kci，wi>|i＝1，…，m}作为权重分布网格G；其中，m表示非空网格单元的个数；θR为不同场景
下非空网格单元个数与窗口中数据点数量之比；

[0008] (3)更新数据分布：窗口滑动时，记窗口滑动前的权重分布网格为Gprep，记录消失在窗口中的消失数据点集合Sexp，同时记录新出现的新数据点集合Snew，将{|i＝
1，...，m}分别作为第一分布网格Gexp和第二分布网格Gnew，对于第一分布网格Gexp遍历消失
数据点集合Sexp，将消失数据点集合Sexp中的每一个数据点加入到对应的非空网格单元，并
记录其权重，更新第一分布网格Gexp；对于第二分布网格Gnew遍历新数据点集合Snew，将新数
据点集合Snew中的每一个数据点加入到对应的非空网格单元，并记录其权重，更新第二分布
网格Gnew，随后将更新的第二分布网格Gnew和更新的第一分布网格Gexp对应非空网格单元的
权重作差，将{|i＝1，...，m}作为净变权重分布网格ΔG，再由窗口滑动前的权重
prep curr
分布网格G 加上净变权重分布网格ΔG可得到当前权重分布网格G ；

[0009] (4)跳过平稳区域：遍历当前权重分布网格Gcurr的中心坐标kci，计算数据点x与中心坐标kci的距离，取θK个最近的kci组成θK最近邻核中心集合KC(x)，遍历净变权重分布网
格ΔG中的，当所述数据点x与净变权重分布网格ΔG中的kci的欧氏距离小于等于
所述数据点x与其的第θK最近邻核中心 的欧氏距离时，将满足上述条件的kci对应的Δwi
组成集合ΔWt(x)；则数据点x的局部密度累积误差为：

[0010] 其中，tl表示上次更新密度的窗口，tc表示当前窗口，Δwj表示集合ΔWt(x)中第j个非空网格单元的权重差；

[0011] 每次窗口滑动时重复计算当前权重分布网格Gcurr中核中心kci的局部密度累积误差；当核中心kci局部密度累积误差E(kci)大于误差容许阈值时，更新该核中心所在网格单元中
所有数据点x的局部可达密度和局部异常因子，更新数据点x的局部可达密度和局部异常因子
时，找出包含数据点x的θK最近邻数据点的非空网格单元，再遍历该非空网格单元中的数据点，
估计出数据点x的第θK距离邻域 对 中的所有数据点y计算出y的第θK距离θK_
dist(y)，则y到x的局部可达距离为 得到局
部可达密度 和局部异常因子
并记录每个非空网格单元内最小局部异常因子LOFmin(x)及最大局部异常因子LOFmax(x)；其
中 是x的θK最近邻数据点的个数；

[0012] (5)异常检测：设初始候选网格单元Gcand为空，用Gcurr‑Gcand表示Gcurr中除去存在于curr
Gcand中的非空网格单元集合，遍历G ‑Gcand中的非空网格单元，若当前Gcand中所有
非空网格单元的权重之和大于等于n且该非空网格单元最小局部异常因子LOFmin(x)大于
curr curr
G ‑Gcand中最大局部异常因子LOFmax(x)，则输出当前Gcand；否则将当前G ‑Gcand中的非空
网格单元加入到Gcand，若当前Gcand中所有非空网格单元的权重之和小于n则继续遍
curr
历下一非空网格单元，否则比较当前Gcand最小局部异常因子LOFmin(x)是否大于G ‑Gcand中
最大局部异常因子LOFmax(x)，若是则继续遍历下一非空网格单元，若不是则不将加
入到Gcand且继续遍历下一非空网格单元；通过上述过程得到Gcand，再Gcand中所有数据点的局
部异常因子由大到小进行排序，选出前n个异常数据点。

[0013] 与现有技术相比，本发明的有益效果：本发明通过对数据空间进行网格单元划分，采用核中心与权重相结合的方式表示数据区域，在窗口滑动过程中，通过权重净变的累积
误差来选择性的更新数据局部密度。因为异常数据往往是少数部分，大多区域的数据密度
在连续窗口中较为稳定，极大地减少计算量，提高异常检测效率而且不会影响检测准确率。
除此之外，在更新过程中仅将包含有数据点的θK最近邻数据点的区域用于计算局部异常因
子，避免遍历整个数据空间的数据点，进一步的缩减计算量，从而提高效率。本发明以桥梁
健康监测系统为应用背景，提出了一种高效准确的流数据异常检测方法，解决了现有异常
检测方法在处理爆发式流数据时无法保证准确率和时效性的难题。

附图说明

[0014] 图1为本发明跳过平稳区域的流数据异常检测方法流程图；

[0015] 图2为窗口滑动时数据分布的方法流程图；

[0016] 图3为跳过平稳区域更新数据点局部可达密度和局部异常因子Gprep的方法流程图；

[0017] 图4为前n个异常数据点检测方法流程图。

具体实施方式

[0018] 下面结合附图，对本发明作进一步详细描述。

[0019] 如图1提供了本发明跳过平稳区域的流数据异常检测方法流程图，所述流数据异常检测方法通过对窗口中的数据空间进行网格单元划分，以单元区域内数据点个数wi作为
权重，结合非空网格单元中心坐标kci来表示非空网格单元。在窗口滑动过程中，以非空网
格单元的权重累积净变作为区域内数据密度变化程度的度量，跳过更新相对平稳数据区域
中数据点的局部可达密度和局部异常因子。在需要更新的区域内，仅将含有估计点θK最近
邻点的区域用于估计局部异常因子，减少对不必要的数据点进行遍历。最后通过非空网格
单元中局部异常异常因子的上下界实现非空网格单元和数据点两个层级的异常检测，即首
先识别出包含有前n个异常值的非空网格单元，再检索出前n个异常数据点。具体包括如下
步骤：

[0020] (1)数据预处理：从桥梁健康监测系统传感器中实时采集数据，根据系统采样频率和需要不同选择n个采样时间间隔为一个窗口，将所述窗口中的数据进行缺失值补全、归一
d
化操作，得到数据空间X；

[0021] (2)划分网格单元：将步骤(1)得到的数据空间Xd分为对角线长度为θR的d维网格单元，θR为不同场景下非空网格单元个数与窗口中数据点数量之比，θR应足够小，以减少计算
开销，但不能太小，以保持离群点检测精度，为此，通过从足够小的值增加θR来找到比率曲
线的第一个弯折。可以在第一弯折之后的范围内通过搜索确定使得召回率最大的θR。所述
网格单元包含非空网格单元，其中，i表示非空网格单元的索引，wi表示第i个非空
网格单元的权重，kci表示第i个非空网格单元的中心坐标；将非空网格单元集合{|
i＝1，...，m}作为权重分布网格G；其中，m表示非空网格单元的个数。通过划分网格单元，便
于后续对数据空间进行分区域的处理，减少对所有数据点的遍历，可以减少计算量，提高算
法时效性。

[0022] (3)更新数据分布的方法流程图如图2所示：窗口滑动时，伴随着旧数据点的消失和新数据点的进入，因此由权重分布网格管理的窗口数据分布需要进行相应的更新。记窗
prep
口滑动前的权重分布网格为G ，记录消失在窗口中的消失数据点集合Sexp，同时记录新出
现的新数据点集合Snew，将{|i＝1，...，m}分别作为第一分布网格Gexp和第二分
布网格Gnew，对于第一分布网格Gexp遍历消失数据点集合Sexp，将消失数据点集合Sexp中的每
一个数据点加入到对应的非空网格单元，并记录其权重，更新第一分布网格Gexp；对于第二
分布网格Gnew遍历新数据点集合Snew，将新数据点集合Snew中的每一个数据点加入到对应的
非空网格单元，并记录其权重，更新第二分布网格Gnew，随后将更新的第二分布网格Gnew和更
新的第一分布网格Gexp对应非空网格单元的权重作差，将{|i＝1，...，m}作为净
prep
变权重分布网格ΔG，再由窗口滑动前的权重分布网格G 加上净变权重分布网格ΔG可得
curr
到当前权重分布网格G 。净变权重分布网格ΔG可用于衡量各区域内数据分布的变化程
度，其中Δwi越小的单元网格数据分布变化程度越小，在更新数据点局部可达密度和局部
异常因子时可跳过这类变化程度小的平稳区域，因异常数据本身属于少数部分，大部分正
常数据区域会趋于平稳，则该方法可减少计算所需时间和空间资源。

[0023] (4)跳过平稳区域局部可达密度和局部异常因子的方法流程图如图3所示：根据步骤(3)中净变权重分布网格ΔG选择性的更新窗口中数据点的局部可达密度。根据局部密度
估计定义可知，如果数据点x的θK最近邻核中心和它的权重没有改变，那么数据点x的局部
curr
密度也不会改变。遍历当前权重分布网格G 的中心坐标kci，计算数据点x与中心坐标kci
的距离，取θK个最近的kci组成θK最近邻核中心集合KC(x)，遍历净变权重分布网格ΔG中的<
kci，Δwi>，当所述数据点x与净变权重分布网格ΔG中的kci的欧氏距离小于等于所述数据
点x与其的第θK最近邻核中心 的欧氏距离时，将满足上述条件的kci对应的Δwi组成集
合ΔWt(x)；则数据点x的局部密度累积误差为： 其中，
tl表示上次更新密度的窗口，tc表示当前窗口，Δwj表示集合ΔWt(x)中第j个非空网格单元
的权重差；为保证检测精度，用局部密度累积误差定量的描述数据点局部密度变化程度，当
超过阈值时表明会对检测结果造成影响，需及时更新其局部可达密度和局部异常因子。

[0024] 每次窗口滑动时重复计算当前权重分布网格Gcurr中核中心kci的局部密度累积误差；当核中心kci局部密度累积误差E(kci)大于误差容许阈值时，更新该核中心所在网格单元中
所有数据点x的局部可达密度和局部异常因子，更新数据点x的局部可达密度和局部异常因子
时，找出包含数据点x的θK最近邻数据点的非空网格单元，再遍历该非空网格单元中的数据点，
估计出数据点x的第θK距离邻域 对 中的所有数据点y计算出y的第θK距离θK_dist
(y)，则y到x的局部可达距离为 得到局部可
达密度 和局部异常因子 并
记录每个非空网格单元内最小局部异常因子LOFmin(x)及最大局部异常因子LOFmax(x)，以便
于后续异常检测；其中 是x的θK最近邻数据点的个数；

[0025] (5)异常检测方法流程图如图4所示：设初始候选网格单元Gcand为空，用Gcurr‑Gcandcurr cand curr cand
表示G 中除去存在于G 中的非空网格单元集合，遍历G ‑G 中的非空网格单元cand
wi>，若当前G 中所有非空网格单元的权重之和大于等于n且该非空网格单元最小局部异
curr cand cand
常因子LOFmin(x)大于G ‑G 中最大局部异常因子LOFmax(x)，则输出当前G ；否则将当
curr cand cand cand
前G ‑G 中的非空网格单元加入到G ，若当前G 中所有非空网格单元的权
cand
重之和小于n则继续遍历下一非空网格单元，否则比较当前G 最小局部异常因子LOFmin
curr cand
(x)是否大于G ‑G 中最大局部异常因子LOFmax(x)，若是则继续遍历下一非空网格单元，
cand cand
若不是则不将加入到G 且继续遍历下一非空网格单元；通过上述过程得到G ，
cand
再G 的中的所有数据点的局部异常因子由大到小进行排序，选出前n个异常数据点。对整
个窗口中所有数据点的局部异常因子进行排序需要极大的计算时间和空间资源，通过所述
方法可先查找出含有前n个异常点的网格单元，再对其中数据点的局部异常因子进行排序，
可有效减少对不必要的数据点进行排序操作，提高检测效率。

[0026] (6)异常报告：将检测出的前n个异常数据点相关信息，包括传感器编号、数据类型、异常分数等形成文本报告输出给相关专业人员，以便专业人员采取措施处理异常。