双类型异质网中基于排序和聚类的离群点检测方法

doi:10.3969/j.issn.0372-2112.2018.02.004

电子学报 ›› 2018, Vol. 46 ›› Issue (2): 281-288.DOI: 10.3969/j.issn.0372-2112.2018.02.004

双类型异质网中基于排序和聚类的离群点检测方法

彭涛^1,2, 杨妮亚¹, 徐原博¹, 王冰冰¹, 刘露¹

1. 吉林大学计算机科学与技术学院, 吉林长春 130012;
2. 符号计算与知识工程教育部重点实验室(吉林大学), 吉林长春 130012

收稿日期:2016-09-26 修回日期:2016-11-14 出版日期:2018-02-25
- 通讯作者:
- 刘露
- 作者简介:
- 彭涛,男,1977年生,博士、教授.主要研究方向为数据挖掘、信息检索、机器学习.;杨妮亚,女,1992年生,硕士.主要研究方向为数据挖掘、机器学习.;徐原博,男,1990年生,博士.主要研究方向为数据挖掘、机器学习.;王冰冰,女,1990年生,硕士.主要研究方向为数据挖掘、搜索引擎.
- 基金资助:
- 国家自然科学基金 (No.60903098）; 吉林大学研究生创新基金 (No.2016183，No.2016184）

An Outlier Detection Method Based on Ranking and Clustering in Bi-typed Heterogeneous Network

PENG Tao^1,2, YANG Ni-ya¹, XU Yuan-bo¹, WANG Bing-bing¹, LIU Lu¹

1. College of Computer Science and Technology, Jilin University, Changchun, Jilin 130012, China;
2. Key Laboratory of Symbolic Computation and Knowledge Engineering(Jilin University), Ministry of Education, Changchun, Jilin 130012, China

Received:2016-09-26 Revised:2016-11-14 Online:2018-02-25 Published:2018-02-25
- Corresponding author:
- LIU Lu
- Supported by:
- National Natural Science Foundation of China (No.60903098); Postgraduate Innovation Fund of Jilin University (No.2016183, No.2016184)

摘要/Abstract

摘要： 挖掘隐藏在网络中不同于正常数据对象的离群点是数据挖掘的重要任务之一.目前，针对双类型异质信息网络离群点检测的研究工作相对较少，原本适用于同质网络的离群点检测方法将很难适用于双类型异质网络.为此，提出了异质信息网络中基于排序和聚类的离群点检测方法（RKBOutlier）.从异质信息网络中抽取两种类型的对象以及链接两种对象的语义信息，将待检测的数据作为属性对象，将另一类型数据作为目标对象，对目标对象进行聚类来检测属性对象在各个聚类中的分布情况，数据分布异常的对象即为离群点.将排序和聚类相结合来显著提高聚类的准确度.实验结果表明，RKBOutlier可以在双类型异质信息网络中有效地检测出离群点.

关键词: 离群点检测, 排序, 聚类, 目标对象, 属性对象

Abstract: Mining the outliers that are different from normal data objects in the network is one of the important tasks in data mining. At present, the research aiming at outlier detection in bi-typed heterogeneous information network is relatively small. The methods which are applicable to homogeneous network can not be applied to bi-typed heterogeneous networks. Therefore, we propose a Rank-Kmeans Based Outlier detection method, called RKBOutlier, in heterogeneous information network. The two kinds of the objects and the connected semantic information are extracted from the heterogeneous information network. One type of the objects is regarded as the attribute objects, another type of the objects is regarded as the target objects. We perform cluster partitioning on target objects to detect the distribution of the attribute objects in each cluster. The objects which are abnormal at data distribution are considered to be the outliers. Ranking and clustering are combined to significantly improve the accuracy of clustering. The experimental results show that RKBOutlier can effectively detect outliers in bi-typed heterogeneous information network.

Key words: outlier detection, ranking, clustering, target object, attribute object

中图分类号:

TP391

彭涛, 杨妮亚, 徐原博, 等. 双类型异质网中基于排序和聚类的离群点检测方法[J]. 电子学报, 2018, 46(2): 281-288.

PENG Tao, YANG Ni-ya, XU Yuan-bo, et al. An Outlier Detection Method Based on Ranking and Clustering in Bi-typed Heterogeneous Network[J]. Acta Electronica Sinica, 2018, 46(2): 281-288.

参考文献

[1] Aggarwal C C,Yu P S.Outlier detection for high dimensional data[J].Acm Sigmod Record,2001,30(2):37-46.
[2] Koc L,Mazzuchi T A,Sarkani S.A network intrusion detection system based on a Hidden Naïve Bayes multiclass classifier[J].Expert Systems with Applications,2012,39:13492-13500.
[3] Kaganov A,Lakhany A,Chow P.FPGA acceleration of multifactor cdo pricing[J].ACM Transactions on Reconfigurable Technology and Systems (TRETS),2011,4(2):20-25.
[4] Kuklisova-Murgasova M,Quaghebeur G,Rutherford M A,et al.Reconstruction of fetal brain MRI with intensity matching and complete outlier removal[J].Medical Image Analysis,2012,16(8):1550-1564.
[5] Gunisetti L.Outlier detection and visualization of large datasets[A].Proceedings of the International Conference on Emerging Trends in Technology[C].New York:ACM,2011.522-524.
[6] Aktolga E,Ros I,Assogba Y.Detecting outlier sections in us congressional legislation[A].Proceedings of the International ACM SIGIR Conference on Research and Development in Information Retrieval,SIGIR 2011[C].New York:ACM,2011.235-244.
[7] Zimek A,Gaudet M,Campello R J G B,et al.Subsampling for efficient and effective unsupervised outlier detection ensembles[A].ACM SIGKDD International Conference on Knowledge Discovery and Data Mining[C].New York:ACM,2013.428-436.
[8] Zimek A,Campello R J G B,Sander J.Data perturbation for outlier detection ensembles[A].Proceedings of the 26th International Conference on Scientific and Statistical Database Management[C].New York:ACM,2014.13:1-12.
[9] Pillutla M R,Raval N,Bansal P,et al.LSH based outlier detection and its application in distributed setting[A].Proceedings of the 20th ACM International Conference on Information and Knowledge Management[C].New York:ACM,2011.2289-2292.
[10] 江峰,杜军威,眭跃飞等.基于边界和距离的离群点检测[J].电子学报,2010,38(3):700-705. Jiang Feng,Du Junwei,Mu Yuefei,et al.Outlier detection based on boundary and distance[J].Acta Electronica Sinica,2010,38(3):700-705.(in Chinese)
[11] 江峰,杜军威,葛艳等.基于粗糙集理论的序列离群点检测[J].电子学报,2011,39(2):345-350. Jiang Feng,Du Junwei,Ge Yan,et al.Sequence outlier detection based on rough set theory[J].Acta Electronica Sinica,2011,39(2):345-350.(in Chinese)
[12] Dalmia A,Gupta M,Varma V.Query-based graph cuboid outlier detection[A].Proceedings of the 2015 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining 2015[C].New York:ACM,2015.705-712.
[13] Manish G,Gao J,Sun Y Z,et al.Integrating community matching and outlier detection for mining evolutionary community outliers[A].Proceedings of the 18th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining[C].New York:ACM,2012.859-867.
[14] Basu S,Banerjee A,Mooney R J.Semi-supervised clustering by seeding[A].18th International Conference on Machine Learning[C].San Francisco,CA:Morgan Kaufmann,2002.27-34.
[15] Van d H M,Mandl R,Hulshoff P H.Normalized cut group clustering of resting-state FMRI data[J].Plos One,2008,3(4):e2001.
[16] Sun Y Z,Yu Y,Han J W.Ranking-based clustering of heterogeneous information networks with star network schema[A].Proceedings of the 15th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining[C].New York:ACM,2009.797-806.
[17] Zhuang H,Zhang J,Brova G,et al.Mining query-based subnetwork outliers in heterogeneous information networks[A].IEEE International Conference on Data Mining[C].Piscataway,NJ:IEEE,2014.1127-1132.
[18] Gupta M,Gao J,Han J.Community distribution outlier detection in heterogeneous information networks[A].Joint European Conference on Machine Learning and Knowledge Discovery in Databases[C].Berlin:Springer,2013.557-573.
[19] Qi G J,Aggarwal C C,Huang T S.On clustering heterogeneous social media objects with outlier links[A].Proceedings of the 5th ACM International Conference on Web Search and Data Mining[C].New York:ACM,2012.553-562.
[20] Sun Y Z,Han J W,Zhao P X,et al.RankClus:Integrating clustering with ranking for heterogeneous information network analysis[A].Proceedings of the 12th International Conference on Extending Database Technology:Advances in Database Technology[C].New York:ACM,2009.565-576.
[21] Steinbach M,Karypis G,Kumar V.A comparison of document clustering techniques[A].KDD Workshop on Text Mining[C].Piscataway,NJ:IEEE,2000.400(1):525-526.
[22] Han J W,Kamber M,Pei J.Data Mining Concepts and Techniques[M].Third Edition,San Francisco,CA:Morgan Kaufmann,2012.102-120.
[23] Zhang K,Hutter M,Jin H.A new local distance-based outlier detection approach for scattered real-world data[A].Advances in Knowledge Discovery and Data Mining[C].Berlin:Springer,2009.813-822.
[24] Tzeng J Y,Byerley W,Devlin B,et al.Outlier detection and false discovery rates for whole-genome DNA matching[J].Journal of the American Statistical Association,2003.98(461):236-246.
[25] Croft W B,Metzler D,Strohman T.Search Engines:Information Retrieval in Practice[M].Reading:Addison-Wesley,2010.23-37.
[26] Ley M.The DBLP computer science bibliography:Evolution,research issues,perspectives[A].String Proceedings and Information Retrieval[C].Berlin:Springer,2002.1-10.
[27] Tang J,Zhang J,Yao L,et al.Arnetminer:Extraction and mining of academic social networks[A].Proceedings of the 14th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining[C].New York:ACM,2008.990-998.

双类型异质网中基于排序和聚类的离群点检测方法

An Outlier Detection Method Based on Ranking and Clustering in Bi-typed Heterogeneous Network

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

[1]	曹阳, 高旻, 余俊良, 范琪琳, 荣文戈, 文俊浩. 基于双图混合随机游走的社会化推荐模型[J]. 电子学报, 2023, 51(2): 286-296.
[2]	张少波, 原刘杰, 毛新军, 朱更明. 基于本地差分隐私的K-modes聚类数据隐私保护方法[J]. 电子学报, 2022, 50(9): 2181-2188.
[3]	王波, 王悦, 王伟, 侯嘉尧. 开放环境下自适应聚类优化包络的相机来源取证[J]. 电子学报, 2022, 50(8): 1840-1850.
[4]	钟沛龙, 黎明, 何超, 陈昊. 基于SOM聚类和自适应算子选择的高维多目标进化算法[J]. 电子学报, 2022, 50(8): 1959-1974.
[5]	李凯, 张可心. 结构α-熵的加权高斯混合模型的子空间聚类[J]. 电子学报, 2022, 50(3): 718-725.
[6]	汪禹宏, 张屹. 基于适应度指导交配限制策略的重组算子与多目标优化研究[J]. 电子学报, 2022, 50(3): 710-717.
[7]	路皓翔, 刘振丙, 张静, 王子民. 结合多尺度循环卷积和多聚类空间的红外图像增强[J]. 电子学报, 2022, 50(2): 415-425.
[8]	赵嘉, 王刚, 吕莉, 樊棠怀. 面向流形数据的测地距离与余弦互逆近邻密度峰值聚类算法[J]. 电子学报, 2022, 50(11): 2730-2737.
[9]	高雷阜, 张梦瑶, 赵世杰. 融合簇边界移动与自适应合成的混合采样算法[J]. 电子学报, 2022, 50(10): 2517-2529.
[10]	范书平, 万里, 姚念民, 张岩, 马宝英. 基于关键用例获取的测试用例排序方法[J]. 电子学报, 2022, 50(1): 149-156.
[11]	江巨浪, 刘国明, 朱柱, 黄忠, 郑江云. 基于快速模糊聚类的动态多直方图均衡化算法[J]. 电子学报, 2022, 50(1): 167-176.
[12]	欧阳丹彤, 刘扬, 宋金彩, 王浩然, 张立明. 结合结构特征基于测试集重排序的故障诊断方法[J]. 电子学报, 2022, 50(1): 63-71.
[13]	吕阳, 钱斌, 胡蓉, 张梓琪. 增强人工蜂群算法求解半导体最终测试调度问题[J]. 电子学报, 2021, 49(9): 1708-1715.
[14]	孟海宁, 冯锴, 朱磊, 张贝贝, 童新宇, 黑新宏. 基于Laplacian图谱的短文本聚类算法[J]. 电子学报, 2021, 49(9): 1716-1723.
[15]	张屹, 陆逸舟, 王帅, 陆曈曈. 基于多源交配选择策略的重组算子与多目标优化研究[J]. 电子学报, 2021, 49(9): 1754-1760.