基于网格划分的高维大数据集离群点检测算法研究

赵伯鑫

（河北软件职业技术学院，河北保定071000）

1 引言

由于基于统计分析、密度以及偏差等所实施的离群点检测方式，都存在着一定的不足，像对于用户预先设置参数过于依赖或者检测精准度不高等，需要进行改进，对该种检测算法发展与推广形成了直接阻碍。在此种背景下，大数据和高维空间集中离群点检测为离群点检测开辟出了新的发展方向，对高维空间特性以及高维空间大数据集离群点高效检测等内容研究，已经成为业界学者关注的主要课题，对于离群点检测发展有着较为突出的现实意义。

2 网格划分方式

网格单元划分是此种离群点检测算法展开的关键，通常相关人员会按照高维空间维度，实施等距离单元格划分。此种方式虽然具有一定优势，但也有着不可忽视的问题：第一，此种方式划分所得到的网格单元数量，由于和数据集维度存在着指数级相关的联系，所以其与高维大数据集空间划分需求存在着一定出入；第二，因为维度距离数值是有关人员事先进行设定的，且其与检测算法开展有着直接关联，所以如果数值发生相应变化，很有可能就会对最终检测计算结果产生不良影响[1]。其中，若距离数值设置过大，则可能会出现非边界网格单元被忽略或被删除的情况，会使离群点出现丢失的状况；而如果数值设置过小，则会直接网格单元计算量，且可能会造成聚类点无法被完全检测的情况。因此有学者提出，在不同维中实施不同间隔的划分方式，此种方式会按照空间维实际情况，合理进行间隔距离设置，可以有效解决等距离划分所存在的各项问题，能够有效提高算法落实效率，是目前较为认可的一种网格划分方式。

3 以网络划分为基础的高维大数据集离群点检测算法

3.1 算法流程和描述

3.1.1 算法流程

3.1.1.1 数据集预处理

在数据集预处理阶段之中，主要分为过滤以及扫描两部分内容。此阶段主要负责进行数据集读入和构建动态哈希表，会将数据集存储到物理内存之中。当对读入数据集实施扫描时，能够完成所有数据点映射任务，每个维度的数据点都会映射到与之相对的网格单元之内，且可以借助哈希表储存结果，实现对输入数据信息的动态化读入[2]。此种算法可以实现对所有网格单元数据点数的实时计算，且可以对数据计算准确度进行保证，相关人员会按照事先所设定的阀值完成对网格单元类型的判断工作，可以在最短时间内精准判断出网格单元的类型，并完成对稠密网格单元的处理，确保非稠密网格单元能够出现在候选离群点之内，以完成对剩余网格单元数量的计算，以保证算法有效性。

在具体进行处理过程中，①可以随机对数据子空间中的未访问点进行挑选，并按照事先所设定的维度间隔距离，对该点所在网格单元类型进行判断；②完成哈希函数构建，并确保所有网格单元信息能够准确、完整的体现在哈希表之中，并完成对网格单元中所有数据点数的计算，以便按照预先设定的数值，完成对网格单元类型评断；③对哈希表中所有标记为稠密型网格单元实施检测，确定其周边单元网格类型，并做好标记、记录；④要对上述步骤中标记为稠密类型的网格单元进行统一处理，并要对其中非边界网格单元聚类点进行删除，且要将删除之后剩余的单元网格归入到离群点集之内；⑤反复执行上述步骤，直至所有数据集点都映射到哈希表之后，再展开对数据空间中所有非边界网格聚类点与聚类区域的处理，以便在处理之后实施后期高效化计算。

3.1.1.2 离群点发现和检测

在离群点发现和检测阶段，检测算法需要重点负责对上一阶段的数据进行整理，并要对候选离群点集展开局部偏离因子的计算。同时要借助空间局部偏离因子算法，对此算法执行过程进行改进与优化，要展开对筛选后候选离群点集的计算，进而找到最高值，并将其视作待挖掘的离群点目标，以为后续工作开展奠定良好基础。

3.1.2 算法描述

在执行过程中，①输入对象，像D=｛X1,X2,…,Xn｝以及区分网格单元类型参数值等；②输出对象，即数据集中所存在的空间离群点集。在此过程中，首先需要对数据集进行第一次描述，要在维中取出相应的数据点数值，并会将其按照相应维度实施排列，且会完成每一维度的等分间隔计算；其次会进行第二次扫描，会对所有维度中的数据点所属网格单元进行计算，并构建起哈希函数，以保证能够将所有维度内的网格单元映射到哈希表之内；再次对哈希表进行扫描，以完成对边界单元网格的判断，确保非边界网格单元以及边界单元所包围的聚类点可以得到及时处理；最后要按照广度优先原则，对哈希表进行扫描并完成对集合对象的计算，同时要按照所设定的参数，选出最终的输出结果[3]。

3.2 算法性能分析

此种离群点检测方式，会先借助网格划分方式，完成对离群点网格的过滤与划分，会有效减少后续检测以及筛选工作量，更加便于对候选离群点集实施检测，可以选取出更多与相应条件相满足的待挖掘离群点，离群点挖掘与计算效率较高，可以在规定时间内完成各项计算工作。同时为了保证网格单元性质判断速度，迅速确定网格单元属于稠密型还是边界型，以便迅速找到聚类网格单元并对其进行处理，此种算法会运用哈希表对网格单元信息进行存储，并完成上述一系列操作，与初始数据集点数量相比，在处理之后所需要进行计算的集点数量极少，不仅聚类区域查找与处理较为迅速，且可以有效规避网格单元个数增加的问题，如果将其运用到大规数据离群点检测计算之中，会得到较为理想的执行效率，算法优势较为明显。

3.3 算法实验验证

为对算法可行性与效率展开分析，笔者设置了相应算法验证实验。本次实验的空间邻居数维度距离数值为50，而网格之间的距离为5，离群点数为80，且稠密网格单元数据点的阀值为25[4]。

经过实验表明，与其他检测算法相比，此种算法执行效率优势较为突出，且执行时间可以被控制在合理范围之内，能够在完成网格划分之后，实现对聚类区域的有效筛选和过滤，所需要实施离群点检测的对象能够得到有所压缩，可以省去不必要的计算工作时间与工作量，所以此种算法不但可行，且执行效率较为理想，值得进行推广与进一步研究。

4 结语

通过分析可以发现，以网格划分为基础的高维离群点检测方式，是一项较为高效的离群点挖掘技术，该方式会通过对数据空间维进行同等距离划分的方式，完成对数据空间的划分，进而形成多个没有交集的网格单元，以实现对所有检测对象的逐一检测与处理，整体检测效率与精准度更加理想，更加适合大数据时代离群点挖掘需要，因此该项检测算法将成为今后离群点研究领域重点研究课题，还需要业界同仁的不断努力。