基于改进密度峰值聚类算法的轨迹行为分析

doi:10.3778/j.issn.1002-8331.2012-0173

摘要/Abstract

摘要： 为了深入挖掘校园无线网络轨迹行为数据信息，采用基于密度的聚类方法对校园内用户的轨迹行为进行特征聚类。由于基于密度的聚类算法通常采用距离作为相似性度量方式，为了有效衔接此类聚类算法，先将用户相似度矩阵通过转换函数转变为距离矩阵。引入离群点检测算法，将离群点检测算法与聚类算法相结合，减少参数的输入个数，增加聚类的聚合程度。改进后的聚类算法可以有效检测出数据轨迹的异常，帮助高校通过对学生上网记录的处理找到浏览信息与大部分同学不一致的人，缩小目标范围，进行有针对性的处理。通过定性分析和实验对比验证，确定两种基于离群点检测的共享最近邻的快速搜索密度峰值聚类适用于校园无线网络行为轨迹相似度矩阵的处理，邓恩指数等聚类内部指标及整体性能优于同类算法。

关键词: 聚类分析, 密度峰值, 离群点检测, 校园无线网络

Abstract: In order to dig deeper into the information of campus wireless network trajectory behavior data, a density-based clustering method is used to cluster the trajectory behavior of users on campus. Density-based clustering algorithms usually use distance as a similarity measurement, in order to effectively connect to this type of clustering algorithm, the user similarity matrix is first transformed into a distance matrix through a conversion function. In addition, an outlier detection algorithm is introduced. It combines the outlier detection algorithm and the clustering algorithm. The improved clustering algorithm can not only reduce the input parameters number, but also increase the clustering degree. It can effectively detect anomalies in the data trajectory, to help colleges and universities find people whose browsing information is inconsistent with most of their classmates through the processing of student online records. It can also narrow the target range and conduct targeted processing. Through qualitative analysis and experimental comparison, two kinds of fast search density peak clustering based on outlier detection and sharing nearest neighbor are determined to be suitable for the processing of campus wireless network behavior trajectory similarity matrix, and the internal indicators such as Dunn index are better than original algorithms.

Key words: cluster analysis, peak density, outlier detection, campus wireless network

吕奕, 刘漫丹. 基于改进密度峰值聚类算法的轨迹行为分析[J]. 计算机工程与应用, 2022, 58(17): 314-324.

LYU Yi, LIU Mandan. Network User Analysis Based on Improved Density Peak Clustering Algorithm[J]. Computer Engineering and Applications, 2022, 58(17): 314-324.

参考文献

[1] 吴洁.基于无线路由器日志的用户行为模式分析[D].西安：长安大学，2019.
WU J.Analysis of user behavior patterns based on wireless router logs[D].Xi’an：Chang’an University，2019.
[2] 吴笛，杜云艳，易嘉伟，等.基于密度的轨迹时空聚类分析[J].地球信息科学学报，2015，17（10）：1162-1171.
WU D，DU Y Y，YI J W，et al.Density-based spatiotemporal clustering analysis of trajectories[J].Journal of Geoinformation Science，2015，17（10）：1162-1171.
[3] 穆桃，陈伟，陈松健.基于多层网络流量分析的用户分类方法[J].计算机应用，2017，37（3）：705-710.
MU T，CHEN W，CHEN S J.User classification method based on multiple-layer network traffic analysis[J].Journal of Computer Applications，2017，37（3）：705-710.
[4] 李旭.基于聚类技术的校园网络用户行为数据分析研究[D].济南：山东师范大学，2016.
LI X.Research on data analysis of campus network user behavior based on clustering technology[D].Jinan：Shandong Normal University，2016.
[5] FUCHS J，ISENBERG P，BEZERIANOS A，et al.Teaching clustering algorithms with educlust：experience report and future directions[J].IEEE Computer Graphics and Applications，2020，40（2）：98-102.
[6] 王国琼.大数据可视化对某高校学生行为分析的呈现[D].济南：山东大学，2016.
WANG G Q.Presentation of big data visualization to the analysis of student behavior in a university[D].Jinan：Shandong University，2016.
[7] 姜妍.聚类算法在校园无线网用户行为分析中的应用研究[D].天津：天津理工大学，2018.
JIANG Y.Research on the application of clustering algorithm in the user behavior analysis of campus wireless network[D].Tianjin：Tianjin University of Technology，2018.
[8] LIU R，WANG H，YU X.Shared-nearest-neighbor-based clustering by fast search and find of density peaks[J].Information Sciences，2018，450：200-226.
[9] RODRIGUEZ A，LAIO A.Clustering by fast search and find of density peaks[J].Science，2014，344（6191）：1492-1496.
[10] 方敏佳，刘漫丹.基于校园无线网络的时空轨迹相似性度量[J].计算机工程与设计，2020，41（11）：3001-3008.
FANG M J，LIU M D.Analysis of users’ spatial-temporal trajectory based on campus wireless network[J].Computer Engineering and Design，2020，41（11）：3001-3008.
[11] RAFIEI D，MENDELZON A.Efficient retrieval of similar time sequences using DFT[C]//5th International Conference of Foundations of Data Organization，1998：249-257.
[12] VLACHOS M，KOLLIOS G，GUNOPULOS D.Discovering similar multidimensional trajectories[C]//18th International Conference on Data Engineering，2002：673-684.
[13] KANTARDZIC M.Data mining：concepts，models，methods，and algorithms[M].2nd ed.New York：John Wiley & Sons，2011.
[14] BREUNIG M M，KRIEGEL H P，NG R T，et al.LOF：identifying density-based local outliers[C]//2000 ACM SIGMOD International Conference on Management of Data，2000：93-104.
[15] 吴俊.基于DBSCAN和LOF的网络入侵异常检测算法优化研究[D].福州：福州大学，2017.
WU J.The optimization research on network intrusion anomaly detection algorithm based on DBSCAN and LOF[D].Fuzhou：Fuzhou University，2017.
[16] DUNN J C J J O C.Well-separated clusters and optimal fuzzy partitions[J].Journal of Cybernetics，1974，4（1）：95-104.
[17] ROUSSEEUW P.Silhouettes：a graphical aid to the interpretation and validation of cluster analysis[J].Journal of Computational and Applied Mathematics，1987，20（1）：53-65.
[18] FAHAD A，ALSHATRI N，TARI Z，et al.A survey of clustering algorithms for big data：taxonomy and empirical analysis[J].IEEE Transactions on Emerging Topics in Computing，2014，2（3）：267-279.
[19] DAVIES D L，BOULDIN D W J I T O P A，INTELLIGENCE M.A cluster separation measure[J].IEEE Transactions on Pattern Analysis and Machine Intelligence，1979，1（2）：224-227.
[20] CALI?SKI T，HARABASZ J J C I S.A dendrite method for cluster analysis[J].Communications in Statistics-Theory and Methods，1974，3（1）：1-27.