基于谱聚类的高维类别属性数据流离群点挖掘算法

doi:10.13229/j.cnki.jdxbgxb20210511

吉林大学学报(工学版) ›› 2022, Vol. 52 ›› Issue (6): 1422-1427.doi: 10.13229/j.cnki.jdxbgxb20210511

• 计算机科学与技术 • 上一篇

基于谱聚类的高维类别属性数据流离群点挖掘算法

康耀龙¹(),冯丽露²,张景安³,陈富⁴

^1.山西大同大学计算机与网络工程学院，山西大同 037009
^2.山西大同大学教育科学与技术学院，山西大同 037009
^3.山西大同大学计算机网络中心，山西大同 037009
^4.山西大同大学数学与统计学院，山西大同 037009

收稿日期:2021-06-07 出版日期:2022-06-01 发布日期:2022-06-02
作者简介:康耀龙（1979-），男，副教授，硕士. 研究方向：数据挖掘，大数据技术.E-mail：yaolong_king@126.com
基金资助:
国家自然科学基金项目(61803241);大同市平台基地计划项目(2020196);山西省社会科学院（山西省人民政府发展研究中心）2021年度规划一般项目(YWYB202153)

Outlier mining algorithm for high dimensional categorical data streams based on spectral clustering

Yao-long KANG¹(),Li-lu FENG²,Jing-an ZHANG³,Fu CHEN⁴

^1.School of Computer and Network Engineering，Shanxi Datong University，Datong 037009，China
^2.School of Education Science and Technology，Shanxi Datong University，Datong 037009，China
^3.Computer Network Center，Shanxi Datong University，Datong 037009，China
^4.School of Mathematics and Statistics，Shanxi Datong University，Datong 037009，China

Received:2021-06-07 Online:2022-06-01 Published:2022-06-02

摘要/Abstract

摘要：

为及时发现数据流中的异常数据、降低网络潜在威胁，提出了基于谱聚类的高维类别属性数据流离群点挖掘算法。分析了数据流具有有序性、高速性和高维性等特征，并探究了离群点的主要来源；利用属性权值量化方法，引入信息熵，将具有较强关联性的数据流合并，进而对数据流进行降维以减少干扰；采用谱聚类算法设置关键尺度参数，通过亲和矩阵计算样本与目标之间的距离，将谱聚类变换为无向图分割问题，获取特征矩阵，提取显著的离群点特征；使用距离挖掘方式，在数据流中加入数据块，判断两个邻近数据块之间的概率分布情况，设定滑动窗口，获取数据与滑动窗口间的距离，再与设定的阈值做比较，将离群点加入到集合中完成挖掘。仿真实验结果证明，对于不同大小和不同维度的数据流，该算法所需的执行时间分别在42 s和40 s内，对于数据流大小和维度具有较好的伸缩性，且挖掘出的离群点数据与实际相符。

关键词: 计算机应用, 谱聚类算法, 高维类别属性, 数据流, 离群点挖掘, 滑动窗口

Abstract:

In order to discover abnormal data in the data stream in time and reduce potential threats to the network， a high-dimensional category attribute data stream outlier mining algorithm based on spectral clustering is proposed. The characteristics of orderliness, high speed and high dimensionality of data streams are analyzed, and the main sources of outliers are explored.Using the attribute weight quantization method, introducing information entropy, merging the data streams with strong relevance, and then reducing the dimensionality of the data streams to reduce interference. The spectral clustering algorithm is used to set key scale parameters, the distance between the sample and the target is calculated by the affinity matrix, the spectral clustering is transformed into an undirected graph segmentation problem, the feature matrix is obtained, and the significant outlier features are extracted.Using the distance mining method, data blocks is added to the data stream, the probability distribution between two adjacent data blocks is judged, a sliding window is set, the distance between the data and the sliding window is obtained, and then compare with the set threshold. Outliers are added to the set to complete the mining.

The simulation results show that for data streams of different sizes and dimensions, the execution time required by the algorithm is within 42 s and 40 s respectively, and it has good scalability for the size and dimensions of data streams, and the outlier data mined is consistent with the reality.

Key words: computer application, spectral clustering algorithm, high dimensional category attribute, data flow, outlier mining, sliding window

中图分类号:

TP274

康耀龙,冯丽露,张景安,陈富. 基于谱聚类的高维类别属性数据流离群点挖掘算法[J]. 吉林大学学报(工学版), 2022, 52(6): 1422-1427.

Yao-long KANG,Li-lu FENG,Jing-an ZHANG,Fu CHEN. Outlier mining algorithm for high dimensional categorical data streams based on spectral clustering[J]. Journal of Jilin University(Engineering and Technology Edition), 2022, 52(6): 1422-1427.

图/表 5

表1

图1

图2

图3

图4

参考文献 10

1	江峰, 王凯郦, 于旭, 等. 基于粗糙熵的离群点检测方法及其在无监督入侵检测中的应用[J]. 控制与决策, 2020, 35(5): 1199-1204.
	Jiang Feng, Wang Kai-li, Yu Xu, et al. A rough entropy-based approach to outlier detection and its application in unsupervised intrusion detection[J]. Control and Decision, 2020, 35(5): 1199-1204.
2	杨晓玲, 冯山, 袁钟. 基于相对距离的反k近邻树离群点检测[J]. 电子学报, 2020, 48(5): 937-945.
	Yang Xiao-ling, Feng Shan, Yuan Zhong. Outlier detection based on reversed k-nearest neighborhood MST of relative distance measure[J]. Acta Electronica Sinica, 2020, 48(5): 937-945.
3	叶福兰. 基于离群点检测的不确定数据流聚类算法研究[J]. 中国电子科学研究院学报, 2019, 14(10): 1094-1099.
	Ye Fu-lan. Clustering algorithm for uncertain data stream based on outlier detection[J]. Journal of China Academy of Electronics and Information Technology, 2019, 14(10): 1094-1099.
4	毛亚琼, 田立勤, 王艳, 等. 引入局部向量点积密度的数据流离群点快速检测算法[J]. 计算机工程, 2020, 46(11): 132-138, 147.
	Mao Ya-qiong, Tian Li-qin, Wang Yan, et al. Fast outlier detection algorithm in data stream with local density of vector dot product [J]. Computer Engineering, 2020, 46(11): 132-138, 147.
5	谢娟英, 丁丽娟, 王明钊. 基于谱聚类的无监督特征选择算法[J]. 软件学报, 2020, 31(4): 1009-1024.
	Xie Juan-ying, Ding Li-juan, Wang Ming-zhao. Spectral clustering based unsupervised feature selection algorithms[J]. Journal of Software, 2020, 31(4): 1009-1024.
6	杨梓樱, 濮晓龙, 徐嘉辉. 基于控制过度遗漏发现概率的高维数据流异常诊断[J]. 数理统计与管理, 2020, 39(3): 495-510.
	Yang Zi-ying, Pu Xiao-long, Xu Jia-hui. High-dimensional fault diagnosis by controlling missed discovery excessive probability[J]. Journal of Applied Statistics and Management, 2020, 39(3): 495-510.
7	邓丽, 刘庆连, 邬群勇, 等. 基于数据流时空特征的WSN异常检测及异常类型识别[J]. 传感技术学报, 2019, 32(9): 1374-1380.
	Deng Li, Liu Qing-lian, Wu Qun-yong, et al. Anomaly detection and type identification based on spatio-temporal characteristics of data streams in wireless sensor network[J]. Chinese Journal of Sensors and Actuators, 2019, 32(9): 1374-1380.
8	陈少波. 多维稀疏数据流异常数据关联挖掘仿真[J].计算机仿真, 2019, 36(9): 342-345.
	Chen Shao-bo. Multidimensional sparse data flow anomaly data association mining simulation[J]. Computer Simulation, 2019, 36(9): 342-345.
9	张艳梅, 陆伟, 杨余旺. 一种基于关联频繁模式的振动数据流挖掘框架[J]. 数据采集与处理, 2019, 34(5): 872-882.
	Zhang Yan-mei, Lu Wei, Yang Yu-wang. Novel data mining framework for vibration data stream based on associated frequency patterns[J]. Journal of Data Acquisition and Processing, 2019, 34(5): 872-882.
10	程士卿, 郝问裕, 李晨, 等. 低秩张量分解的多视角谱聚类算法[J]. 西安交通大学学报, 2020, 54(3): 119-125, 133.
	Cheng Shi-qing, Hao Wen-yu, Li Chen, et al. Multi-view clustering by low-rank tensor decomposition[J]. Journal of Xi'an Jiaotong University, 2020, 54(3): 119-125, 133.

相关文章 15

[1]	刘铭,杨雨航,邹松霖,肖志成,张永刚. 增强边缘检测图像算法在多书识别中的应用[J]. 吉林大学学报(工学版), 2022, 52(4): 891-896.
[2]	魏晓辉,苗艳微,王兴旺. Rhombus sketch：自适应和准确的流数据sketch[J]. 吉林大学学报(工学版), 2022, 52(4): 874-884.
[3]	方世敏. 基于频繁模式树的多来源数据选择性集成算法[J]. 吉林大学学报(工学版), 2022, 52(4): 885-890.
[4]	李大湘,陈梦思,刘颖. 基于STA⁃LSTM的自发微表情识别算法[J]. 吉林大学学报(工学版), 2022, 52(4): 897-909.
[5]	陈雪云,贝学宇,姚渠,金鑫. 基于G⁃UNet的多场景行人精确分割与检测[J]. 吉林大学学报(工学版), 2022, 52(4): 925-933.
[6]	康苏明,张叶娥. 基于Hadoop的跨社交网络局部时序链路预测算法[J]. 吉林大学学报(工学版), 2022, 52(3): 626-632.
[7]	王学智,李清亮,李文辉. 融合迁移学习的土壤湿度预测时空模型[J]. 吉林大学学报(工学版), 2022, 52(3): 675-683.
[8]	王雪,李占山,吕颖达. 基于多尺度感知和语义适配的医学图像分割算法[J]. 吉林大学学报(工学版), 2022, 52(3): 640-647.
[9]	欧阳继红,郭泽琪,刘思光. 糖尿病视网膜病变分期双分支混合注意力决策网络[J]. 吉林大学学报(工学版), 2022, 52(3): 648-656.
[10]	毛琳,任凤至,杨大伟,张汝波. 双向特征金字塔全景分割网络[J]. 吉林大学学报(工学版), 2022, 52(3): 657-665.
[11]	曲优,李文辉. 基于锚框变换的单阶段旋转目标检测方法[J]. 吉林大学学报(工学版), 2022, 52(1): 162-173.
[12]	赵宏伟,霍东升,王洁,李晓宁. 基于显著性检测的害虫图像分类[J]. 吉林大学学报(工学版), 2021, 51(6): 2174-2181.
[13]	刘洲洲,张倩昀,马新华,彭寒. 基于优化离散差分进化算法的压缩感知信号重构[J]. 吉林大学学报(工学版), 2021, 51(6): 2246-2252.
[14]	王生生,陈境宇,卢奕南. 基于联邦学习和区块链的新冠肺炎胸部CT图像分割[J]. 吉林大学学报(工学版), 2021, 51(6): 2164-2173.
[15]	孙东明,胡亮,邢永恒,王峰. 基于文本融合的物联网触发动作编程模式服务推荐方法[J]. 吉林大学学报(工学版), 2021, 51(6): 2182-2189.

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed

数据块	离群度为0.02时的离群点数量	离群度为0.04时的离群点数量
1	100	200
2	80	160
3	110	185
4	95	210
5	105	205
6	110	170
7	70	160

基于谱聚类的高维类别属性数据流离群点挖掘算法

Outlier mining algorithm for high dimensional categorical data streams based on spectral clustering

RICH HTML

PDF (PC)

摘要/Abstract

引用本文

使用本文

图/表 5

参考文献 10

相关文章 15

Metrics

本文评价

推荐阅读 0