计算机工程 ›› 2011, Vol. 37 ›› Issue (4): 37-39.doi: 10.3969/j.issn.1000-3428.2011.04.014

• 软件技术与数据库 • 上一篇    下一篇

基于KNN图的空间离群点挖掘算法

张忠平,徐晓云,王 培   

  1. (燕山大学信息科学与工程学院,河北 秦皇岛 066004)
  • 出版日期:2011-02-20 发布日期:2011-02-17
  • 作者简介:张忠平(1972-),男,副教授、博士后,主研方向:数据挖掘,网格计算;徐晓云、王 培,硕士研究生
  • 基金项目:
    国家自然科学基金资助项目(60773100);河北省教育厅科研计划基金资助项目(2006143)

Spatial Outlier Mining Algorithm Based on KNN Graph

ZHANG Zhong-ping, XU Xiao-yun, WANG Pei   

  1. (College of Information Science and Engineering, Yanshan University, Qinhuangdao 066004, China)
  • Online:2011-02-20 Published:2011-02-17

摘要: 空间数据集中离群数据与正常数据之间的非空间属性值相差较大。针对该情况,提出一种基于K-最邻近(KNN)图的空间离群点挖掘算法。该算法通过所有对象的K近邻关系构造KNN图,将相邻对象非空间属性值的差作为2个对象点间的边权值,利用裁边策略去掉权值较高的边,从而识别出空间离群点和离群区域。实验结果表明,该算法的时间性能优于POD算法。

关键词: 空间离群点, K-最邻近图, 非空间属性值

Abstract: Aiming at the problem that the non-spatial attribute differences between outlier and normal data are very large, this paper propose a spatial outlier mining algorithm based on K-Nearest Neighbor(KNN) graph. It constructs a KNN graph based on K neighbor relationship in spatial domain, assigns the non-spatial attribute differences as edge weights, and cuts high-weight edges to identify spatial outliers and outlier region. Experimental result shows that time performance of this algorithm is superior to POD algorithm.

Key words: spatial outlier, K-Nearest Neighbor(KNN) graph, non-spatial attribute value

中图分类号: