一种基于聚类模型的高维数据流离群点检测方法

摘要

本发明属于数据挖掘算法在高维数据流处理领域的应用，特别涉及到一种基于聚类模型的高维数据流离群点检测方法。该方法首先通过样本数据流进行聚类，再分析聚类结果中每一个簇的特征维，在计算测试数据集属于哪个簇的时候，只计算与该簇特征维相关的属性，忽略吊冗余属性的计算，从而有效的降低了计算量。如果发现某个数据点不属于任何簇，该点将形成新的簇，如果某个簇长时间没有吸收新的数据点且该簇的数据点个数很少，那么该簇即是包含离群点的簇。本发明具有在高维数据流离群点检测时的效率和准确率都比传统的基于滑动窗口的离群点检测算法要高的技术效果。

主权项

一种基于聚类模型的高维数据流离群点检测方法，具体包括如下步骤：步骤1、训练数据流处理，将训练数据集聚类分簇：根据数据项的属性将数据分簇，然后分析每个簇的特征维；如果某个簇没有特征维，那么计算的时候该簇的所有维都要参与计算，然后将得到的每个簇的特征维存储在位图中；特征维具体流程如下：(1)假设在t₀时刻有|C|个簇，簇中每个数据点的维度是d，创建一个大小为|C|*d的二维位图，用于记录所有簇的特征维，初始时位图中所有元素值为0；(2)遍历所有簇，对于任意一个簇C_i，计算该簇所有点在所有维度上的密度值，那么|C|个簇一共有|C|*d个密度值；密度值计算方式是用该维度上最大值减去最小值后再除以该簇数据点个数，密度值越小说明数据点在该维上越密集；(3)在|C|*d个密度值中计算出密度值最小的|C|*L个值，其中0<L<d，密度值为0的不参与计算；将位图中与对应最小密度值的维更新为1，所有簇的特征维就是对应所得位图中值为1的维；步骤2、对待测试数据流进行离群点检测：当接收到新的数据点后，首先衰减所有簇，分裂达到条件的簇，然后合并重叠簇，再检查当前簇的个数是否超过最大簇个数阈值K，超过阈值则合并相距最近的两个簇，标记为活跃簇，直至当前簇的个数不超过K；然后计算数据流中每个数据点与当前所有簇之间的距离，找到离该数据点最近的簇，并记录簇与簇之间最小距离阈值r2即mindist，如果r2小于定义的数据点与簇最小距离阈值r1即radius，那么该数据点被该簇吸收并更新该簇时间，否则以该点新建一个簇；所述分裂条件是簇中任意一个维度的直方图H(t)出现了两个或两个以上的显著峰值；步骤3、遍历所有簇，判断簇内个数：记录每个簇最后一次吸收数据点的时间T和该簇中包含的数据点个数N；如果T与当前时间差值大于时间阈值T_r，并且数据点个数N小于最小数据点阈值N_min，标记该簇为离群点簇；步骤4、输出离群点：遍历所有在步骤3中标记为离群点簇，输出离群点，并删除离群簇。