一种基于加权KNN的大数据集下离群检测算法_王茜(2)

大数据,数据挖掘

本文提出了一种基于加权ＫＮＮ的高效离群检测算法，离群点定义为那些具有最大的与第ｋ个邻居的距离和权重的其权重为与最近的ｋ个邻居的平均距离。算法由两部分点，

组成，其首先将数据集划分成互不相交的子集，使用基于划分的算法找到候选子集，然后从候选子集中利用加权的思想寻找离群点，通过一些剪枝方法减少对一些非离群点的计算。

因为Ｂ维数比较高的ＩＲＣＨ在聚类数据时对数据量比较大、数据具有较好的时间性能。算法将数据集中的点聚集成一些并用聚类中点的ＭＢ聚类小的聚类划分，Ｒ来代表这些划分，（后的划分生成一棵索引树Ｃ此树结构是一棵平衡树，Ｆｒｅｅ－Ｔ除叶子节点外，中间节点都包含指向其孩子节点和父节点的树叶节点是一个聚类，我们这里称为划分）并通过剪枝索引，

方法从这些划分中找到有可能包含离群点的候选划分。第二阶段是寻找离群点，使用加权的方式在候选划分包含的点中找到前ｎ个离群点。３．２　算法描述

３．２．１　候选划分计算阶段

为了找出候选划分，需要计算每个划分Ｐ距离的上界值（），和下界值（且对划分中包含的任意点Ｐ．ｕｅｒＰ．ｌｏｗｅｒ）ｐｐ

ｋ

（有Ｐ．ｌｏｗｅｒ≤Ｄｕｅｒ。因此首先介绍Ｐ．ｕｅｒ≤Ｐ．ｐ，ｐ）ｐｐｐｐ

和Ｐ．以ＭＡｌｏｗｅｒ的计算方法：ＸＤＩＳＴ和ＭＩＮＤＩＳＴ为标准

２　相关定义

）定义２．１　基于距离的离群点（ＤｉｓｔａｎｃｅａｓｅｄＯｕｔｌｉｅｒｓ－Ｂ　

ｋ

（表示点ｐ与其最近定义１　对数据集上任意点ｐ，Ｄｐ）

的第ｋ个邻居的距离，ｎ表示需要找到的离群点个数，ｋ表示最近邻居数。当且仅当数据集中最多只有ｎ－１个点ｐ′满足

［ｋ６］

，。则点ｐ是ＤｋＤｋ（′）＞Ｄ（ｎ离群点ｐｐ）

性质１　若点ｐ在其Ｄ／即Ｎ２邻域内的点数大于ｋ，（（／））则点ｐ与其Ｄ／ＮｂｒＤ２ｋ，２邻域内的所有点均不是＞ｐ，离群点。其中Ｄ表示前ｎ个离群点Ｄｋ距离的最小值，Ｎｂｒ（（／））表示点ｐ的Ｄ领域内的邻居，表示点Ｄ）Ｎ（ＮｂｒＤ２ｐ，ｐ，

）２领域内的邻居数。因为Ｎ（Ｎｂｒ（Ｄ）Ｎｂｒ≥Ｎ（ｐ在Ｄ／ｐ，（／））即点ｐ与其Ｄ领域内的任意点ｑ之间的距离Ｄ２ｋ，＞ｐ，

本文数据集中各点之间的距离采用欧氏距离ｄｉｓｔ（≤Ｄ，ｐ，ｑ）的平方。

２．２　数据点与最小边界矩形之间距离的定义

［６］

，最小边界矩形（表ｍｉｎｉｍｕｍｂｏｕｎｄｉｎｒｅｃｔａｎｌｅＭＢＲ）　ｇｇ　

寻找ｔ个最靠近Ｐ的划分，ｔ个划分包含的数据点至少达到ｋ个，Ｐ．ｕｅｒ为ｔ个划分中离Ｐ最远的那个划分到Ｐ的最近ｐｐ距离，而Ｐ．ｌｏｗｅｒ为ｔ个划分中离Ｐ最远的那个划分到Ｐ的最远距离。

（具体计算过程为：输入参数为Ｒ包含所有划分的索ｏｏｔ

ｋ

，。首先用两个集合引）离群点的最小Ｄ值）ｍｉｎＤｋＤｉｓｔ（

其为ｌｏｗｅｒＨｅａｅｒＨｅａｐ和ｕｐｐｐ来保存满足如下条件的划分，与当前划分具有最近的下界值和上界值，且在ｌｏｗｅｒＨｅａｐ与

示的是数据集中距离相近点集合的边界值表示的这样的一个…，，集合。δ维下的数据点ｐ表示为ｐ＝［δ维下１，２，ｐｐｐδ］的边界矩形Ｒ用其主对角线上的两个端点来表示，两个端点，…，，为ｒ＝［且ｒｒｒｒｒ′＝［ｒ′，ｒ′，ｒ′］ｒ′，１≤１，２，…，１２ｉ≤ｉδ］δ

ｕｅｒＨｅａｏｗｅｒＨｅａｅｒ－ｐｐｐ中降序排列。然后通过ｌｐ和ｕｐｐ

更新方式为：如果新扫描Ｈｅａｌｏｗｅｒ与Ｐ．ｕｅｒ，ｐ来更新Ｐ．ｐｐ到的一个划分Ｑ与当前划分Ｐ有ＭＩＮＤＩＳＴ（Ｑ，Ｐ）ｌｏｗ－＜Ｐ．

则把划分Ｑ加入ｌ如果ｌｅｒ，ｏｗｅｒＨｅａｏｗｅｒＨｅａｐ中，ｐ中包含的点多于ｋ个，则删除其中离Ｐ最远的划分，此时如果ｌｏｗ－则Ｐ．ｅｒＨｅａｌｏｗｅｒ更新为ｌｏｗｅｒＨｅａｐ中的数据点多于ｋ个，ｐ中离Ｐ最远的划分与Ｐ间的最近距离。Ｐ．ｕｅｒ的更新也ｐｐ，是一样。如果Ｐ．则划分Ｑ中不可ｕｅｒ值小于ｍｉｎＤｋＤｉｓｔｐｐ算法停止。算法首先从根节点开始寻找，如能包含有离群点，

果其不是叶子节点，则把当前节点的孩子节点插入以该节点与划分Ｐ间的距离升序排列的链表中。对于链表中的任意节点，如果其与Ｐ的最近距离大于Ｐ的下界值且与Ｐ的最远距离大于Ｐ的上界值，则把此节点从链表中删除，这样就可以减少很多不必要的计算。算法具体步骤如下：

ｋ

；输入：离群点的最小Ｄ值ＣＦｒｅｅ的根节点Ｒｏｏｔ－Ｔ

ｉｎ。≤

定义２　数据点ｐ与矩形Ｒ之间的最小距离当ｐｒｉ－ｉ，ｉ＜ｉｐ２δ

ＭＩＮＤＩＳＴ（Ｒ）＝∑ｉｘｘｒ′，当ｒ′＝１ｉ，ｉ＝ｐ，ｉ－ｉｉ＜ｉ。ｐｐ其它０，

定义３　数据点与矩形Ｒ之间的最大距离

ｒｒ′ｉ＋ｉ

′－ｐｉｉ，当ｐｉ＜２δ２。ＭＡＸＤＩＳＴ（Ｒ）＝∑ｉ＝１ｘｘｉ，ｉ＝ｐ，其它ｒｉ－ｉ，ｐ

定义４　矩形Ｒ与Ｓ之间的最小距离

ｒｓ′，当ｓ′＜ｒｉ－ｉｉｉ２δ

ＭＩＮＤＩＳＴ（Ｒ，Ｓ）＝∑ｉｘｘｒ′，当ｒ′＜ｓ＝１ｉ，ｉ＝ｉ－ｉｉｉ。其它０，

定义５　矩形Ｒ与Ｓ之间的最大距离

２δ｛｝。ＭＡＸＤＩＳＴ（Ｒ，Ｓ）＝∑ｉｘｘａｘｓ′－ｒｒ′－ｓ｜｜，｜｜＝１ｉ，ｉ＝ｍｉｉｉｉ

；邻居数ｋ；当前划分Ｐ。ｍｉｎＤＫＤｉｓｔ

步骤１　初始化Ｐ．ｌｏｗｅｒ＝Ｐ．ｕｅｒ＝∞，ｌｏｗｅｒＨｅａｐｐｐ＝

ｕｅｒＨｅａｐｐｐ＝Φ。

步骤２　从树的根节点开始生成一个节点链表，如果当前节点是叶子节点，则用叶子节点划分Ｑ计算ＭＩＮＤＩＳＴ（Ｐ，，和ＭＡ否则转到步骤６。Ｑ）ＸＤＩＳＴ（Ｐ，Ｑ）

步骤３　如果Ｍ则把划分ＱＩＮＤＩＳＴ（Ｐ，Ｑ）ｌｏｗｅｒ，≤Ｐ．插入以Ｐ．如果ＭＡｌｏｗｅｒ降序排列的ｌｏｗｅｒＨｅａＸＤＩＳＴｐ中；（则把当前划分Ｑ中插入以Ｐ．Ｐ，Ｑ）ｕｅｒ，ｕｅｒ降序≤Ｐ．ｐｐｐｐ排列的ｕｅｒＨｅａｐｐｐ中。

步骤４　如果｜则删除ｌｌｏｗｅｒＨｅａｏｗｅｒＨｅａ｜≥ｋ，ｐｐ的队首元素，此时又如果有｜则Ｐ．ｌｏｗｅｒＨｅａｋ，ｌｏｗｅｒ＝ＭＩＮＤ｜≥－ｐ，其中Ｑ为ｌ如果ＩＳＴ（Ｐ，Ｑ）ｏｗｅｒＨｅａｐ中的当前队首划分；则删除ｕ此时又如ｕｅｒＨｅａｋ，ｅｒＨｅａ｜｜≥ｐｐｐｐｐｐ的队首元素，

，果有｜则Ｐ．其中ｕｅｒＨｅａｋ，ｕｅｒ＝ＭＡＸＤＩＳＴ（Ｐ，Ｑ）｜≥ｐｐｐｐｐ

２．３　数据点权重的定义

定义６　对数据集上的点ｐ，其权重定义为Ｗｋ（＝ｐ）

ｋ

（（））／其中ｎ表示离ｐ最近的第ｉ个ｄｉｓｔｎｋ，∑ｉ＝１ｉ（ｉ（ｐ，ｐ）ｐ）

（）表示点ｐ到它的最近第ｉ个邻居的距离，邻居，ｄｉｓｔｎｉ（ｐ，ｐ）即点ｐ的权重为其到最近的ｋ个邻居的平均距离。

３　基于加权的离群点检测算法

３．１　算法思想

算法是在大数据集下进行离群点挖掘，其分为两个阶段。第一个阶段是寻找候选划分，由于数据量比较大，为了提高算

［２］法的时间效率，开始阶段采用了Ｂ算法进行预聚类，ＩＲＣＨ１

·１７８·