一种改进的DBSCAN算法及其应用

计算机工程与应用 ›› 2014, Vol. 50 ›› Issue (8): 72-76.

一种改进的DBSCAN算法及其应用

李双庆，慕升弟

重庆大学计算机学院，重庆 400044

出版日期:2014-04-15 发布日期:2014-05-30

Improved DBSCAN algorithm and its application

LI Shuangqing, MU Shengdi

College of Computer Science, Chongqing University, Chongqing 400044, China

Online:2014-04-15 Published:2014-05-30

摘要/Abstract

摘要： 对网络流量等大规模数据，基于密度的DBSCAN聚类算法收敛时间过长、对某些流量聚类效果欠佳。在基于隐马尔科夫模型（Hidden Markov Model，HMM）的流量识别研究背景下，提出一种改进的DBSCAN算法，从减少每次区域查询次数及查询时间两方面提高算法的时间效率和准确率。并创新性地采用分治策略将新算法应用于自动构建网络协议的HMM模型。实验结果表明，改进的DBSCAN算法在保证聚类准确率的同时大大提高了时间效率，并能通过对网络流数据包进行聚类，正确完成网络协议HMM模型的自动建模。

关键词: DBSCAN算法, 隐马尔科夫模型（HMM）, 分治, 自动建模

Abstract: For massive data such as network traffic, DBSCAN has weakness of greatly time consuming, it has poor clustering effect for some network protocol as well. In the context of network traffic classification via HMM, an improved DBSCAN algorithm is put forward. The algorithm improves the time efficiency and accuracy by reducing the time of querying. The improved algorithm is used to construct the HMM of network traffic automatically based on the divided-and-
conquer strategy. The experimental result shows that the algorithm improves time efficiency greatly. It can correctly build the HMM model for traffic.

Key words: DBSCAN algorithm, Hidden Markov Model（HMM）, divide-and-conquer, automatically modeling

李双庆，慕升弟. 一种改进的DBSCAN算法及其应用[J]. 计算机工程与应用, 2014, 50(8): 72-76.

LI Shuangqing, MU Shengdi. Improved DBSCAN algorithm and its application[J]. Computer Engineering and Applications, 2014, 50(8): 72-76.

[1]	王亮，冶继民. 整合DBSCAN和改进SMOTE的过采样算法[J]. 计算机工程与应用, 2020, 56(18): 111-118.
[2]	王光，林国宇. 改进的自适应参数DBSCAN聚类算法[J]. 计算机工程与应用, 2020, 56(14): 45-51.
[3]	李文杰，闫世强，蒋莹，张松芝，王成良. 自适应确定DBSCAN算法参数的算法研究[J]. 计算机工程与应用, 2019, 55(5): 1-7.
[4]	胡健1，朱海湾2，毛伊敏2. 基于自适应蜂群优化的DBSCAN聚类算法[J]. 计算机工程与应用, 2019, 55(14): 105-114.
[5]	潘晓英1，2，赵倩1，赵普1. 时空属性关系标签的频繁轨迹模式挖掘[J]. 计算机工程与应用, 2019, 55(10): 83-89.
[6]	刘任涛1，2，陈卫1. 近邻搜索在多孔材料格点模型建模中的应用[J]. 计算机工程与应用, 2018, 54(7): 239-244.
[7]	张文元，谈国新，朱相舟. 停留点空间聚类在景区热点分析中的应用[J]. 计算机工程与应用, 2018, 54(4): 263-270.
[8]	黄伟婷1，赵红2. 动态误分类代价下代价敏感属性选择分治算法[J]. 计算机工程与应用, 2018, 54(3): 166-171.
[9]	宋董飞，徐华. DBSCAN算法研究及并行化实现[J]. 计算机工程与应用, 2018, 54(24): 52-56.
[10]	廉西猛1，2，单联瑜1，隋志强1，赵翠霞1. 基于四面体剖分的并行地质块体建模方法[J]. 计算机工程与应用, 2018, 54(21): 246-250.
[11]	刘志民，宁爱兵，黄飞，何咏梅，张惠珍. 加权分治与皇冠技术求解最大加权独立集[J]. 计算机工程与应用, 2017, 53(9): 26-30.
[12]	李阳，马骊，樊锁海. 基于动态近邻的DBSCAN算法[J]. 计算机工程与应用, 2016, 52(20): 80-85.
[13]	任建华，高立明. 基于聚类的两段式孤立点检测算法[J]. 计算机工程与应用, 2016, 52(20): 98-102.
[14]	支志兵，宁爱兵，陈吉珍，王永斐，杨晓芳. 最大团问题的加权分治算法[J]. 计算机工程与应用, 2016, 52(2): 50-53.
[15]	林俊锋，黄常标，祁杨停. 三角网格模型分治加工中区域分割算法的研究[J]. 计算机工程与应用, 2015, 51(12): 184-188.