大数据,数据挖掘

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

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

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

王　茜　杨正宽

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

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

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

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

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

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

ｔｈ　

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

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

ｔｈ　

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

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

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

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

６］

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

１　引言

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

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

１］

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

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

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

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

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

２］

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

［］

他们定Ｐｉｚａｕｔｉ …… 此处隐藏：467字，全部文档内容请下载后查看。喜欢就下载吧 ……