基于密度的局部特异数据挖掘方法优化方案

2025-09-29 理论教育版权反馈

【摘要】：E.Knorr和R.Ng等在文献[109]中同时提出了一种基于网格构架的挖掘DB-outlier的方法。首先，全部的数据空间被分割成边长为l的网格。①如果Cx，y中的对象数＞k，那么Cx，y中的所有对象均不是特异对象。M.M.Breuning等认为文献[106]中关注一个对象是否是特异的，而很多的应用中，给出一个对象的特异程度值更有意义。从[定义2.7]和[定义2.8]出发，M.M.Breuning等定义了一个度量对象p的特异程度的因子Local Outlier Factor，记为LOF[106]。

E.Knorr和R.Ng等在文献[109]中同时提出了一种基于网格构架的挖掘DB-outlier的方法。首先，全部的数据空间被分割成边长为l的网格。称在x行和y列的单元格为Cx，y，依据式（2.26）和式（2.27）定义其L1邻居和L2邻居。

L1(Cx,y)={Cu,v|u=x±1,v=y±1,Cu,v≠Cx,y}　(2.26)

L2(Cx,y)={Cu,v|u=x±3,v=y±3,Cu,v≠Cx,y}　(2.27)

根据[定义2.7]，给定一正整数k，E.Knorr和R.Ng等提出的算法根据[性质2.3]编制。(https://www.chuimin.cn)

【性质2.3】①如果Cx，y中的对象数＞k，那么Cx，y中的所有对象均不是特异对象。②如果Cx，y∪L1（Cx，y）中的对象数＞k，那么Cx，y中的所有对象均不是特异对象。③如果Cx，y∪L1（Cx，y）∪L2（Cx，y）中的对象数≤k，那么每一个Cx，y∪L1（Cx，y）∪L2（Cx，y）中对象均是特异对象。

可以看出，此方法将对象VS对象的处理过程简化为单元-by-单元的处理过程，从而获得了时间效率。令|D|=N，每个点的属性维数为α，此方法总的时间复杂度为O（c2+N）。其中，c是一个与维数及每维划分的格数有关的常数。

M.M.Breuning等认为文献[106]中关注一个对象是否是特异的，而很多的应用中，给出一个对象的特异程度值更有意义。从[定义2.7]和[定义2.8]出发，M.M.Breuning等定义了一个度量对象p的特异程度的因子Local Outlier Factor，记为LOF（p）[106]。令|D|=N，每个点的属性维数为α，计算每个点LOF（p）的时间复杂度是O（αN2）。He Zengyou等人提出了一种基于聚类的方法，提出了CBLOF（Cluster-Based Local Outlier Factor）因子及计算算法，其时间复杂度降低到O（N）[107]。

基于密度的局部特异数据挖掘方法优化方案

相关推荐