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

发布于:2021-07-27 03:12:06

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

【摘 要】数据挖掘技术的快速发展,有效带动了各 个领域的发展,而离群点检测技术,作为数据挖掘技术中的 重要组成,自然也成为了社会各界关注的主要课题之一。该 检测方式属于数据挖掘知识中的重要研究方向,像电子商务 欺诈行为检测等,都属于其检测范畴。论文将重点就以网格 划分为基础的高维大数据集离群点检测算法展开深度研究, 期望能够为国内离群点研究工作发展,提供一定助力。

【Abstract】The rapid development of data mining technology has effectively promoted the development of various fields. And the outlier detection technology, as an important component of data mining technology, has become one of the main topics of attention from all walks of life. The detection method belongs to the important research direction in the data mining knowledge, such as the detection of electronic commerce fraud and so on, which all belong to the detection category. This paper will focus on the depth study of high-dimensional large data set outlier detection algorithm based on grid division, hoping to provide some help for the development of outlier research in China.

【关键词】离群点检测;检测算法;网络划分;高维大 数据 【Keywords】outlier detection; detection algorithm; network partition; high dimensional large data 【中图分类号】TP311.13 【文献标志码】A 【文章编 号】1673-1069(2018)03-0139-02 1 引言 由于基于统计分析、密度以及偏差等所实施的离群点检 测方式,都存在着一定的不足,像对于用户预先设置参数过 于依赖或者检测精准度不高等,需要进行改进,对该种检测 算法发展与推广形成了直接阻碍。在此种背景下,大数据和 高维空间集中离群点检测为离群点检测开辟出了新的发展 方向,对高维空间特性以及高维空间大数据集离群点高效检 测等内容研究,已经成为业界学者关注的主要课题,对于离 群点检测发展有着较为突出的现实意义。 2 网格划分方式 网格单元划分是此种离群点检测算法展开的关键,通常 相关人员会按照高维空间维度,实施等距离单元格划分。此 种方式虽然具有一定优势, 但也有着不可忽视的问题: 第一, 此种方式划分所得到的网格单元数量,由于和数据集维度存 在着指数级相关的联系,所以其与高维大数据集空间划分需 求存在着一定出入;第二,因为维度距离数值是有关人员事

先进行设定的,且其与检测算法开展有着直接关联,所以如 果数值发生相应变化,很有可能就会对最终检测计算结果产 生不良影响[1]。其中,若距离数值设置过大,则可能会出现 非边界网格单元被忽略或被删除的情况,会使离群点出现丢 失的状况; 而如果数值设置过小, 则会直接网格单元计算量, 且可能会造成聚类点无法被完全检测的情况。因此有学者提 出,在不同维中实施不同间隔的划分方式,此种方式会按照 空间维实际情况,合理进行间隔距离设置,可以有效解决等 距离划分所存在的各项问题,能够有效提高算法落实效率, 是目前较为认可的一种网格划分方式。 3 以网络划分为基础的高维大数据集离群点检测算法 3.1 算法流程和描述 3.1.1 算法流程 3.1.1.1 数据集预处理 在数据集预处理阶段之中,主要分为过滤以及扫描两部 分内容。此阶段主要负责进行数据集读入和构建动态哈希 表,会将数据集存储到物理内存之中。当对读入数据集实施 扫描时,能够完成所有数据点映射任务,每个维度的数据点 都会映射到与之相对的网格单元之内,且可以借助哈希表储 存结果,实现对输入数据信息的动态化读入[2]。此种算法可 以实现对所有网格单元数据点数的实时计算,且可以对数据 计算准确度进行保证,相关人员会按照事先所设定的阀值完

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

阶段,检测算法需要重点负责对上一阶段的数据进行整理, 并要对候选离群点集展开局部偏离因子的计算。同时要借助 空间局部偏离因子算法,对此算法执行过程进行改进与优 化, 要展开对筛选后候选离群点集的计算, 进而找到最高值,

并将其视作待挖掘的离群点目标,以为后续工作开展奠定良 好基础。 3.1.2 算法描述 在执行过程中,①输入对象,像 D={X1,X2,…,Xn} 以及区分网格单元类型参数值等;②输出对象,即数据集中 所存在的空间离群点集。在此过程中,首先需要对数据集进 行第一次描述,要在维中取出相应的数据点数值,并会将其 按照相应维度实施排列,且会完成每一维度的等分间隔计 算;其次会进行第二次扫描,会对所有维度中的数据点所属 网格单元进行计算,并构建起哈希函数,以保证能够将所有 维度内的网格单元映射到哈希表之内;再次对哈希表进行扫 描,以完成对边界单元网格的判断,确保非边界网格单元以 及边界单元所包围的聚类点可以得到及时处理;最后要按照 广度优先原则,对哈希表进行扫描并完成对集合对象的计 算,同时要按照所设定的参数,选出最终的输出结果[3]。 3.2 算法性能分析 此种离群点检测方式,会先借助网格划分方式,完成对 离群点网格的过滤与划分,会有效减少后续检测以及筛选工 作量,更加便于对候选离群点集实施检测,可以选取出更多 与相应条件相满足的待挖掘离群点,离群点挖掘与计算效率 较高,可以在规定时间内完成各项计算工作。同时为了保证 网格单元性质判断速度,迅速确定网格单元属于稠密型还是

边界型,以便迅速找到聚类网格单元并对其进行处理,此种 算法会运用哈希表对网格单元信息进行存储,并完成上述一 系列操作,与初始数据集点数量相比,在处理之后所需要进 行计算的集点数量极少,不仅聚类区域查找与处理较为迅 速,且可以有效规避网格单元个数增加的问题,如果将其运 用到大规数据离群点检测计算之中,会得到较为理想的执行 效率,算法优*衔飨浴 3.3 算法实验验证 为对算法可行性与效率展开分析,笔者设置了相应算法 验证实验。本次实验的空间邻居数维度距离数值为 50,而网 格之间的距离为 5,离群点数为 80,且稠密网格单元数据点 的阀值为 25[4]。 经过实验表明,与其他检测算法相比,此种算法执行效 率优*衔怀觯抑葱惺奔淇梢员豢刂圃诤侠矸段е冢 能够在完成网格划分之后,实现对聚类区域的有效筛选和过 滤,所需要实施离群点检测的对象能够得到有所压缩,可以 省去不必要的计算工作时间与工作量, 所以此?N 算法不但可 行,且执行效率较为理想,值得进行推广与进一步研究。 4 结语 通过分析可以发现,以网格划分为基础的高维离群点检 测方式,是一项较为高效的离群点挖掘技术,该方式会通过 对数据空间维进行同等距离划分的方式,完成对数据空间的

划分,进而形成多个没有交集的网格单元,以实现对所有检 测对象的逐一检测与处理,整体检测效率与精准度更加理 想,更加适合大数据时代离群点挖掘需要,因此该项检测算 法将成为今后离群点研究领域重点研究课题,还需要业界同 仁的不断努力。 【参考文献】 【1】*ɡ恚沤鹑迹患胰.一种基于改进 KNN 的大数据离群点检测算法[J].计算机与现代化,2017(5) : 67-70. 【2】李俊丽,芦彩林.离群点检测算法研究[J].计算机与 数字工程,2017,45(6) :1045-1048. 【3】 余大龙.基于特征选择的数据降维算法研究[D].合肥: 安徽大学,2017. 【4】苟杰,马自堂,张?闯?.PODKNN:面向大数据集 的并行离群点检测算法[J].计算机科学, 2016, 43 (7) : 251-254.


相关推荐

最新更新

猜你喜欢