应用相似度测量的图离群点检测方法

李涛 1; 2; 肖南峰 2

doi:10.7652/xjtuxb201408012

您当前的位置：

首页 >

文章列表页 >

应用相似度测量的图离群点检测方法

更新时间：2025-07-09

- 应用相似度测量的图离群点检测方法
- A Graph Anomalies Detection Method Based on Graph Similarity
- 西安交通大学学报 2014年48卷第8期页码：67-72+79
- 作者机构：
  
  1. 华南农业大学现代教育技术中心,广州,510640
  2. 华南理工大学计算机科学与工程学院,广州,510640
- 作者简介：
- 基金信息：
  
  : 2013-12-10。作者简介: 李涛(1978—),男,博士生;肖南峰(通信作者),男,教授,博士生导师。基金项目: 国家自然科学基金资助项目(61171141),广东省产学研省部合作专项资金资助项目(2012B091100448)
- DOI：10.7652/xjtuxb201408012
  中图分类号： TP391
- 网络首发：2014-08-10，
  
  纸质出版：2014
- 稿件说明：
移动端阅览
李涛 1, 2, 肖南峰 2. 应用相似度测量的图离群点检测方法[J]. 西安交通大学学报, 2014,48(8):67-72+79.

A Graph Anomalies Detection Method Based on Graph Similarity[J]. 2014, 48(8): 67-72+79.
李涛 1, 2, 肖南峰 2. 应用相似度测量的图离群点检测方法[J]. 西安交通大学学报, 2014,48(8):67-72+79. DOI： 10.7652/xjtuxb201408012.

A Graph Anomalies Detection Method Based on Graph Similarity[J]. 2014, 48(8): 67-72+79. DOI： 10.7652/xjtuxb201408012.

摘要

针对传统离群点检测方法精确度不高的问题

提出了一种同时基于全局和局部视野综合考虑的离群点检测方法

并将其成功应用于事务图数据集的离群点检测。该方法利用极大公共频繁子图来测量任意两个事务图之间的相似度

提出利用基于公共近邻的裁剪方法对相似矩阵进行裁剪

通过计算数据结点的往返距离得出各个结点的离群值评分

弥补了传统基于稳态分布随机游走的离群点检测方法的缺陷。实验结果表明:该方法在事务图数据离群点检测方面的性能明显优于基于subdue的方法

精确度和错误报警率以及召回率提高了约10%。

Abstract

An anomalies detection method based on considering both the global and the local perspectives is proposed to solve the low accuracy problem in traditional anomalies detection

and is successfully applied to outlier detection in transaction graph data sets. The method evaluates the similarity between any two graphs based on maximum common frequent subgraph

and then cuts out the similarity matrix based on common neighbor. The round-trip distance for a data node is calculated and is used as its anomalies score

that makes up the defect of traditional outlier detection methods based on the steady-state distribution and random walk. Experiments in real datasets show that the performance of the proposed method is better than the performance of the method based on subdue. The precision

the recall rate and the false alarm rate are improved by about 10%.

关键词

Keywords

references

HAN Jiawei. Data mining: concepts and technology[M]. 3rd ed. San Francisco, CA, USA: Morgan Kaufmann, 2012.

林海. 离群检测及离群释义空间查找算法研究[D]. 重庆: 重庆大学, 2012.[3] 于浩, 王斌, 肖刚, 等. 基于距离的不确定离群点检测[J]. 计算机研究与发展, 2010, 47(3): 474-484.

YU Hao, WANG Bin, XIAO Gang, et al. Distance-based outlier detection on uncertain data[J]. Journal of Computer Research and Development, 2010, 47(3): 474-484.

HASSANZADEH R, NAYAK R. A semi-supervised graph-based algorithm for detecting outliers in online-social-networks[C]∥Proceedings of the 28th Annual ACM Symposium on Applied Computing. New York, USA: ACM, 2013: 577-582.

MOONESINGHE H, TAN P N. Outrank: a graph-based outlier detection framework using random walk[J]. International Journal on Artificial Intelligence Tools, 2008, 17(1): 19-36.

EGOZI A, KELLER Y, GUTERMAN H. A probabilistic approach to spectral graph matching[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2013, 35(1): 18-27.

AKOGLU L, MCGLOHON M, FALOUTSOS C. Oddball: spotting anomalies in weighted graphs[J]. Lecture Notes in Computer Science, 2010, 6119: 410-421.

MULLER E, SANCHEZ P I, MULLE Y, et al. Ranking outlier nodes in subspaces of attributed graphs[C]∥Proceedings of the 2013 IEEE 29th International Conference on Data Engineering Workshops. Piscataway, NJ, USA: IEEE, 2013: 216-222.

GUO Yanrong, WU Guorong, JIANG Jianguo, et al. Robust anatomical correspondence detection by hierarchical sparse graph matching[J]. IEEE Transactions on Medical Imaging, 2013, 32(2): 268-277.

GUPTA M, GAO Jing, SUN Yizhou, et al. Integrating community matching and outlier detection for mining evolutionary community outliers[C]∥Proceedings of the 18th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York, USA: ACM, 2012: 859-867.

杨茂林. 离群检测算法研究[D]. 武汉: 华中科技大学, 2012.

AGGARWAL C C, ZHAO Yuchen, YU P S. Outlier detection in graph streams[C]∥Proceedings of the 2011 IEEE 27th International Conference on Data Engineering. Piscataway, NJ, USA: IEEE, 2011: 399-409.

CAO Lijun, LIU Xiyin, WANG Zhiping, et al. The spatial outlier mining algorithm based on the KNN graph[J]. Journal of Software, 2013, 8(12): 3158-3165.

YAN Sifeng, HAN Jiawei. Span: graph-based subs-tructure pattern mining[C]∥Proceedings of the 2002 IEEE International Conference on Data Mining. Piscataway, NJ, USA: IEEE, 2002: 721-724.

NOBLE C C, COOK D J. Graph-based anomaly detection[C]∥Proceedings of the 9th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York, USA: ACM, 2003: 631-636.

浏览量

下载量

CSCD

文章被引用时，请邮件提醒。

提交

工具集

关联资源

采用SHAP的高压涡轮级高维设计空间数据挖掘

基于免疫记忆克隆的特征选择

高效的用户访问预测新算法

基于视觉原理的分类算法

采用聚类特征的基本概率分配生成方法及应用