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

大数据,数据挖掘

第３８卷　第１０期２０１１年１０月计算机科学

ＣｏｍｕｔｅｒｃｉｅｎｃｅＳＶｏｌ．３８Ｎｏ．１０

Ｏｃｔ２０１１一种基于加权ＫＮＮ的大数据集下离群检测算法

王　茜　杨正宽

（）重庆大学计算机学院　重庆４０００４４

摘　要　传统ＫＮＮ算法是在基于距离的离群检测算法的基础上提出的一种在大数据集下进行离群点挖掘的算法，然而ＫＮＮ算法只以最近的第ｋ个邻居的距离作为判断是否是离群点的标准有时也失准确性。给出了一种在大数据集下基于ＫＮＮ的离群点检测算法，即在传统ＫＮＮ方法的基础上为每个数据点增加了权重，权重值为与最近的ｋ个邻居的平均距离，离群点为那些与第ｋ个邻居的距离最大且相同条件下权重最大的点。算法能提高离群点检测的准确性，通过实验验证了算法的可行性，并与传统ＫＮＮ算法的性能进行了对比。关键词　离群点，数据挖掘，权重，划分中图法分类号　ＴＰ３９１　　　文献标识码　Ａ　

ＡｌｏｒｉｔｈｍｆｏｒＯｕｔｌｉｅｒＤｅｔｅｃｔｉｏｎｉｎＬａｒｅＤａｔａｓｅｔＢａｓｅｄｏｎＷｅｉｈｔｅｄＫＮＮ　　　　　　　　　　ｇｇｇ

ＷＡＮＧ　ＱｉａｎＺｈｅｎｋｕａｎ　ＹＡＮＧ　－ｇ

（，，）ＣｏｌｌｅｅｏｆＣｏｍｕｔｅｒＳｃｉｅｎｃｅＣｈｏｎｉｎＵｎｉｖｅｒｓｉｔＣｈｏｎｉｎ４０００４４，Ｃｈｉｎａ　　　ｇｐｇｑｇｙｇｑｇ　　

ＡｂｓｔｒａｃｔｒａｄｉｔｉｏｎａｌＫＮＮｉｓａｎａｄｖａｎｃｅｄａｌｏｒｉｔｈｍｂａｓｅｄｏｎｔｈｅｄｉｓｔａｎｃｅｏｆｏｕｔｌｉｅｒｄｅｔｅｃｔｉｏｎａｌｏｒｉｔｈｍｏｎｌａｒｅｄａｔａ　Ｔ　　　　　　　　　　　　　　　　－ｇｇｇ

ｔｈ　

ｓｅｔ．Ｈｏｗｅｖｅｒｔｈｉｓａｌｏｒｉｔｈｍｏｎｌｕｓｅｓｔｈｅｋｎｅａｒｅｓｔｎｅｉｈｂｏｒａｓｔｈｅｃｒｉｔｅｒｉｏｎｆｏｒｏｕｔｌｉｅｒｗｈｉｃｈｉｓｉｎａｃｃｕｒａｔｅｕｎｄｅｒｃｅｒ　　　　　　　　　　　　　　　　－ｇｙｇ　

ｔａｉｎｃｏｎｄｉｔｉｏｎ．ＴｈｉｓａｗｅｉｈｔｅｄＫＮＮｏｕｔｌｉｅｒｄｅｔｅｃｔｉｏｎａｌｏｒｉｔｈｍｆｏｒｌａｒｅｄａｔａｓｅｔｓ．Ｉｎｔｈｉｓａｌｏｒｉｔｈｍ，ａａｅｒｒｅｓｅｎｔｅｄ　　　　　　　　　　　　　　ｇｇｇｇｐｐｐｆａｃｔｏｒｉｓｒｅｓｅｎｔｅｄ．Ｉｔｒｅｒｅｓｅｎｔｓｔｈｅａｖｅｒａｅｄｉｓｔａｎｃｅｏｆｉｔｓｋｎｅａｒｅｓｔｎｅｉｈｂｏｒｓ．Ｔｈｅｏｕｔｌｉｅｒｓａｒｅｔｈｏｓｅｈａｖｉｎｔｈｅｗｅｉｈｔ　　　　　　　　　　　　　　　ｐｐｇｇｇｇ　

ｔｈ　

’ｌａｒｅｓｔｄｉｓｔａｎｃｅｗｉｔｈｉｔｓｋｎｅｉｈｂｏｒａｎｄｈａｖｉｎｔｈｅｂｉｅｓｔｗｅｉｈｔｕｎｄｅｒｔｈｅｓａｍｅｃｏｎｄｉｔｉｏｎ．Ｔｈｅａｌｏｒｉｔｈｍｉｍｒｏｖｅｓ　　　　　　　　　　　　　　ｇｇｇｇｇｇｇｐ　

ｔｈｅａｃｃｕｒａｃｏｆｔｈｅｏｕｔｌｉｅｒｄｅｔｅｃｔｉｏｎａｌｏｒｉｔｈｍ．Ｅｘｅｒｉｍｅｎｔｒｅｓｕｌｔｓｈｏｗｓｔｈａｔｔｈｅａｌｏｒｉｔｈｍｉｓｆｅａｓｉｂｌｅｃｏｍａｒｅｄｗｉｔｈｔｈｅ　　　　　　　　　　　　　　　ｙｇｐｇｐ　ｔｒａｄｉｔｉｏｎａｌＫＮＮ．　

，，，ＫｅｗｏｒｄｓｕｔｌｉｅｒＤａｔａｍｉｎｉｎＷｅｉｈｔＰａｒｔｉｔｉｏｎ　Ｏ　ｇｇｙ　

时间复杂度，后者对数据的维数具有指数的时间复杂Ｏ（Ｎ２）度，尤其在超过４维以后效率明显降低，所以它们在高维大数据集下都不具效率。针对其不足，Ｒａｍａｓｗａｍｕｓｅｏｋ等ｙ与ｋｙ

６］

。他们对离人提出了一种在大数据集下挖掘离群点的方法［

１　引言

离群点检测作为知识发现的重要部分，被广泛地应用于入侵检测、故障诊断及恶劣天气预报等领域。近年欺诈识别、

来，随着人们对离群数据挖掘重要性认识的不断加深，以及其越来越广泛的应用，离群点挖掘成为了数据挖掘领域的热点之一。离群点检测算法大致可分为：基于分布的方法、基于深度的方法、基于距离的方法、基于密度的方法和基于聚类的方法。基于分布的方法采用标准统计分布模型，那些偏离模型

１］

；的点被认为是离群点［基于深度的方法主要采用几何学的

群点的定义为前ｎ个与其最近第ｋ个邻居的距离最大的点被避免了基于距离的离群点检测算法需要用户认为是离群点，

设定距离参数值ｄ的局限，它使用基于划分的方法并对数据且数据的维数对算法的执集中的点Ｎ有线性的时间复杂度，

行时间影响不大，但它只以与最近第ｋ个邻居的距离作为判断离群点的标准有时也不够准确，即无法判断在与最近的第

方法，把数据对象组织到数据空间的不同层面中，那些在较浅

２］

；层面的数据更有可能是离群点［基于密度的方法为数据集ｋ个邻居的距离相同时哪个点更可能是离群点。Ａｕｉｕｌｌｉ与ｇ

［］

他们定Ｐｉｚａｕｔｉ对基于距离的离群点给出了一个新的定义７，义前ｎ个离群点是权重最大的前ｎ个点，权重是数据点与其但其在权重相同的情况下无法判最近ｋ个邻居的距离之和，

断哪些点更可能是离群点。近年来基于ＫＮＮ的离群点检测

［］

的应用层出不穷，如ＦｕｚｚＫＮＮ８在处理时流数据上有较高ｙ　［］

／／的效率；ＡＧＡＫＮＮ９能有效处理生物学上的基因数据；ＯＣ［０］

针对数据集产生最优聚类结果。其它高效的基于距ＫＮＮ１

［１］

，离的离群点检测算法有Ｒ其ｅｎ等人的Ｂｅｉｈｂｏｒｓ方法１－Ｎｙｇ

，中的点定义局部离群因素（且用ＬＬＯＦ）ＯＦ来计算数据对象的离群程度，离群点被认为是离群程度比较大及与周围的邻

３］

；基于聚类的方法认为离群点是那居点关系比较疏离的点［

４］

。些数据集聚类后的副产品［

［５］

基于距离的离群方法最早由Ｋ其主ｎｏｒｒ与Ｎｇ提出，要思想是将数据看作空间中的点，而离群点被定义为与数据

集中大多数点之间的距离都大于某个阈值的那些点，它使用，算法ｎ前者对数据集中的点Ｎ具有ｅｓｔｅｄｌｏｏｅｌｌｂａｓｅｄ－－ｐ和ｃ

使用了一种新颖的垂直数据结构来检测离群点。

）到稿日期：资助。２０１０１１０５２０１１０５０２６１０７３０５８－－　返修日期：－－　　本文受国家自然科学基金项目（

，，王　茜（女，博士，副教授，硕士生导师，主要研究方向为信息安全、电子商务、远程教育课件工具；杨正宽（男，硕士生，主要研１９６４－）１９８６－）究方向为数据挖掘。

·１７７·