Clustering Algorithm for High Dimensional Data Stream Based on Projection and Density

doi:10.3969 /j.issn.1674-0696.2013.04.41

Abstract

Abstract: A clustering algorithm for high dimensional data stream based on the projection and density ( HpDenStream) is proposed，which is based on the classical data stream clustering algorithm． This algorithm combines with the sliding window technical，and it uses the projection clustering algorithm to reduce the data dimensionality of dimensional data streams and then adopts the density clustering algorithm to detect the anomaly data detection． The simulation results show that the algorithm not only takes up smaller storage space and less workload，but also improves the efficiency of the implementation of the algorithm．

Key words: data stream, clustering algorithm, projection, dimension reduction, density, anomaly detection

摘要： 在经典数据流的聚类算法基础之上，提出了一种基于投影和密度的高维数据流聚类算法———HpDenStream，该算法结合滑动窗口技术，采用投影算法对高维数据流进行降维处理，并运用密度聚类算法对降维后的数据进行异常数据检测。仿真实验结果表明: 该方法占用的存储空间小，算法的工作量少，并提高了算法的执行效率。

关键词: 数据流, 聚类算法, 投影, 降维, 密度, 异常检测

CLC Number:

TP392

Wang Ｒenhong，Wang Jiawei，Liang Zongbao. Clustering Algorithm for High Dimensional Data Stream Based on Projection and Density[J]. Journal of Chongqing Jiaotong University(Natural Science), 2013, 32(4): 725-728.

汪仁红，王家伟，梁宗保. 基于投影和密度的高维数据流聚类算法[J]. 重庆交通大学学报（自然科学版）, 2013, 32(4): 725-728.

References

[1] 汪成亮，陆志坚，庞栩．一种数据流趋势分析方法的研究与应用[J]．计算机系统应用，2010， 19( 1) : 152-155．
Wang Chengliang，Lu Zhijian，Pang Xu．Ｒesearch and application of an algorithm for trend analysis of data streams [J]． Computer System ＆ Application，2010，19( 1) : 152-155．
[2] 黄树成，曲亚辉．数据流分类技术研究综述[J]．计算机应用研究， 2009，26( 10) : 3604-3609．
Huang Shucheng，Qu Yahui． Survey on data streams classification technologies[J]． Application Ｒesearch of Computers，2009，26( 10) : 3604-3609．
[3] Guha S，Mishra N，Motwani Ｒ，et al． Clustering Data Streams [C]/ /Proceedings of the 41st Annual Symposium on Foundations of Computer Science． California: IEEE，2000: 71-80．
[4] 张继超．数据流的变化检测算法及其在实时汇率数据流异常检测中的应用[D]．郑州: 郑州大学，2005．
Zhang Jichao． Change Detection Scheme of Data Stream and the Application of Detecting the Abnormal Data Blocks in Exchange Ｒate Data Stream[D]． Zhengzhou: Zhengzhou University，2005．
[5] 史金成．基于相关性的数据流聚类及其应用研究[D]．合肥: 合肥工业大学， 2007．
Shi Jincheng．Ｒesearch on Data Stream Clustering and its Applications Based on Correlations [D]． Hefei: Hefei University of Technology，2007．
[6] Xu Ｒui，Donald Wunsch． Survey of clustering algorithms [J]．IEEE Transactions on Neural Networks，2005，16( 3) : 634-678．
[7] 陈铭，吉根林．一种基于相似维的高维子空间聚类算法[J]．南京师大学报: 自然科学版，2010， 33( 4) : 119-122．
Chen Ming，Ji Genlin． A subspace clustering algorithm for high dimensional data based on similar dimension [J]． Journal of NanjingNormal University: Natural Science，2010，33( 4) : 119-122．
[8] 任家东，周玮玮，何海涛．高维数据流的自适应子空间聚类算法[J]．计算机科学与探索， 2010，4( 9) : 859-964．
Ｒen Jiadong，Zhou Weiwei，He Haitao． Adaptive clustering algorithm for mining subspace clusters in high-dimensional data stream[J]． Journal of Frontiers of Computer Science and Technology，2010，4( 9) : 859-964．
[9] 颜晓龙，沈鸿．一种适用于高维数据流的子空间聚类方法[J]．计算机应用， 2007， 27( 7) : 1680-1684． Yan Xiaolong，Shen Hong． Subspace clustering method for high dimensional data streams [J]． Computer Applications，2007，27( 7) : 1680-1684．
[10] 周晓云，孙志挥，张柏礼，等．高维数据流子空间聚类发现及维护算法[J]．计算机研究与发展， 2006，43( 5) : 834-840．
Zhou Xiaoyun，Sun Zhihui，Zhang Baili，et al． An efficient discovering and maintenance algorithm of subspace clustering over high dimensional data streams[J]． Journal of Computer Ｒesearch and Development，2006，43( 5) : 834-840．
[11] 李子杰，郑成．流数据和传统数据存储及管理方法比较研究[J]．计算机技术与发展，2009，19( 4) : 101-104．
Li Zijie，Zheng Cheng． Comparative study on methods of storage and management of stream and traditional data [J]． Computer Technology and Development，2009，19( 4) : 101-104．
[12] 王家伟，汪仁红，罗宪，等．基于数据流的桥梁健康监测海量数据处理[J]．计算机系统应用，2011，20( 12) : 158-161．
Wang Jiawei，Wang Ｒenhong，Luo Xian，et al． Processing of massive data based on data stream and bridge health monitoring[J]． Computer System ＆ Application，2011，20( 12) : 158-161．

[1]	XU Tao1,2, REN Qiliang1, LI Jinyan3, LIN Wei1. Road State Recognition Clustering Algorithm Based on Improved Particle Swarm Optimization and K-means [J]. Journal of Chongqing Jiaotong University(Natural Science), 2026, 45(2): 47-56.
[2]	XU Guangxiang1，CHEN Qinzhi1，LI Fan2，ZHOU Qiankai3，WANG Duoyin1. Discussion on the Verification Method of Bridge Clearance Width under Cross-Currents Exceeding the Limit [J]. Journal of Chongqing Jiaotong University(Natural Science), 2025, 44(5): 1-7.
[3]	CHEN Zhongzhang1, DUAN Muzi1, CAI Shengyu1, SU Weifeng1, LI Pengfei2. Mechanical and Microscopic Properties of High-Performance Concrete Prepared by Tunneling Excavation Materials [J]. Journal of Chongqing Jiaotong University(Natural Science), 2025, 44(2): 34-42.
[4]	GONG Xiaoxing, DONG Peixin. Traffic Flow Anomaly Data Detection Model Based on Improved Isolation Forest Algorithm [J]. Journal of Chongqing Jiaotong University(Natural Science), 2024, 43(5): 61-69.
[5]	XU Minyao1, WANG Yao1, QIN Yu2,3. Boundary Effect of Concrete Based on Random Aggregate [J]. Journal of Chongqing Jiaotong University(Natural Science), 2024, 43(3): 17-25.
[6]	LI Wenli1,2, LI Chao1, LI Zhongfeng1, YI Fan1, LI An1. Safety Test and Evaluation Method for Autonomous Vehicles Based on Ramp Merging Data [J]. Journal of Chongqing Jiaotong University(Natural Science), 2024, 43(2): 84-91.
[7]	HE Zhaoyi1, ZHANG Yu2, SONG Gang2, XU Diping3, WU Zhou3. Literature Review and Prospect of Asphalt Pavement Compaction Detection Based on Ground Penetrating Radar [J]. Journal of Chongqing Jiaotong University(Natural Science), 2024, 43(11): 1-10.
[8]	FENG Haixia，NING Erwei，WANG Qi，LI Jian. Cause Analysis of Traffic Accidents in Jinan Based on GIS [J]. Journal of Chongqing Jiaotong University(Natural Science), 2023, 42(5): 124-131.
[9]	YANG Tao1, ZHANG Xinyu1, GAO Qiankun1, WANG Lidong2, WANG Lei2. Vertical Random Vibration of Train-Track-Bridge System Considering Dimension-Reduced Simulation of Track Irregularity [J]. Journal of Chongqing Jiaotong University(Natural Science), 2023, 42(2): 19-27.
[10]	JIAO Liudan, TANG Lian, HUO Xiaosen, ZHANG Yu. Urban Waterlogging Disaster Resilience Evaluation Based on RAGA-PP [J]. Journal of Chongqing Jiaotong University(Natural Science), 2023, 42(11): 72-79.
[11]	WU Bo1, ZHU Linping1, LI Yangbo1, LIU Cong1, XIA Chengming2. Evaluation Method and Application of Tunnel Construction Safety Risk Based on K-Means Clustering Model [J]. Journal of Chongqing Jiaotong University(Natural Science), 2023, 42(11): 80-87.
[12]	ZHANG Zhiqing, SONG Xin, FU Jinxiu. Evaluation Method of Urban Road Cross-Section Based on Projection Pursuit Method [J]. Journal of Chongqing Jiaotong University(Natural Science), 2022, 41(12): 41-47.
[13]	PAN Yiyong, GUAN Xingyu. Stochastic Fundamental Diagram Model of Traffic Flow Speed-Density Relationship Based on Quantile Regression [J]. Journal of Chongqing Jiaotong University(Natural Science), 2022, 41(07): 20-26.
[14]	LI Nan, QIANG Yigeng, FAN Rui. Aircraft Flight Trajectory Clustering Based on Trajectory Compression [J]. Journal of Chongqing Jiaotong University(Natural Science), 2021, 40(01): 1-6.
[15]	YE Zhen, HE Mingguang, LIANG Keke. Location Method of Taxi Service Stations Based on Service Demands [J]. Journal of Chongqing Jiaotong University(Natural Science), 2019, 38(03): 75-82.