Multi-density Incremental Clustering Algorithm Based on Grid

Abstract

Abstract:

This paper presents a multi-density incremental clustering algorithm based on grid (MICG), the discriminant function taking into account relative density and

gravity distance between grid cells is introduced. When a portion of the data sets changed, without re-clustering all the data, this algorithm could formulate a new cluster

according to original clustering result merely based on the relationship between the unit with changed data set and neighbored unit. This approach effectively improved

efficiency of cluster analysis. The time complexity and space complexity are linear with the size of dataset and the number of attributes. The experimental results show that

MICG algorithm can process cluster with any shape or different densities, and can solve the increment clustering problem effectively when the data is updated.

Key words: , grid clustering, incremental clustering, multi-density, cell, discriminant function

LI Guang-xing1, YIN Ji-chuan2, TANG jun1. Multi-density Incremental Clustering Algorithm Based on Grid[J]. Computer and Modernization.

References

［1］ Garmire L X, Garmire D G, Huang W, et al. A global clustering algorithm to identify long intergenic non-coding RNA-with applications in mouse macrophages［J］. PloS One,

2011,6(9):e24051.
［2］ Ji Zexuan, Sun Quansen, Xia Denshen. A modified possibilistic fuzzy c-means clustering algorithm for bias field estimation and segmentation of brain MR image［J］.

Computerized Medical Imaging and Graphics, 2011,35(5):383-397.
［3］孔辉，陈婷，王杰贵. 基于动态聚类分析的雷达载频模式识别［J］. 计算机工程与应用, 2009，45（12）:205-207,232. 
［4］徐玉华，张崇巍，徐海琴. 基于聚类的迭代双向最近点机器人位姿估计［J］. 机器人， 2010，32(3):352-357.
［5］ Ester M, Kriegel H P, Sander J, et al. Incremental clustering for mining in a data warehousing environment［C］//VLDB98. 1998:323-333. 
［6］ Yooseph S, Li W, Sutton G. Gene identification and protein classification in microbial metagenomic sequence data via incremental clustering［J］. BMC Bioinformatics,

2008,9(1):182.
［7］ Young S, Arel I, Karnowski T P, et al. A fast and stable incremental clustering algorithm［C］//2010 Seventh International Conference on Information Technology:New

Generations (ITNG). 2010:204-209.

［8］张忠平,陈丽萍,王爱杰,等. 基于自适应模糊C-均值的增量式聚类算法［J］. 计算机工程， 2009，35(6): 60-62. 
［9］ Lughofer E. Extensions of vector quantization for incremental clustering［J］. Pattern Recognition, 2008,41(3):995-1011
［10］Hsu C C, Huang Y P. Incremental clustering of mixed data based on distance hierarchy［J］. Expert Systems with Applications：An International Journal, 2008,35（3）：

1177-1185.
［11］刘建晔，李芳. 一种基于密度的高性能增量聚类算法［J］. 计算机工程， 2006，32( 21) : 76-78.
［12］Goyal N, Goyal P, Venkatramaiah K, et al. An efficient density based incremental clustering algorithm in data warehousing environment［C］//2009 International Conference

on Computer Engineering and Applications, IPCSIT. 2011,2：482-486.
［13］刘青宝，侯东风，邓苏，等. 基于相对密度的增量式聚类算法［J］. 国防科技大学学报， 2006，28（5）：73-79.
［14］刘建晔，李芳. 一种基于密度的高性能增量聚类算法［J］. 计算机工程， 2006，32（21）：76-78.
［15］印桂生,于翔,宁慧. 一种基于网格的增量聚类算法［J］. 计算机应用研究, 2009,26(6):2038-2040.
［16］陈卓,贺明霞,刘相双. 基于扩展凝聚点和网格的增量聚类算法［J］. 哈尔滨工业大学学报, 2006,38(8):1382-1385.
［17］李光兴. 二分网格的多密度聚类［J］. 计算机工程与设计, 2012,33(5):1876-1880.
［18］李光兴，唐俊，易林，等. 一种自动计算参数的多密度网格聚类算法［J］. 计算机与数字工程, 2014,42(7):1141-1145.

[1]	FU Hong-lin, ZHANG Tai-hong, YANG Ya-ting, Aizimaiti Aiwanier, MA Bo. Scenes Text Modification Network for Uyghur Based on Generative Adversarial Network [J]. Computer and Modernization, 2024, 0(01): 41-46.
[2]	LI Xiang, ZHUANG Yi. Critical Fault Point Identification Method for Routing Algorithms Using XGBoost [J]. Computer and Modernization, 2023, 0(11): 75-81.
[3]	LI Shi-yue, MENG Jia-na, YU Yu-hai, LI Xue-ying, XU Ying-ao. Aspect Based Sentiment Analysis Model Based on Knowledge Enhancement [J]. Computer and Modernization, 2023, 0(10): 1-8.
[4]	LIU Rui-xue, LI Wen, LIU Fang, DU Shou-guo. Prediction of Time Series with Missing Value Based on Tensor Autoregressive Completion [J]. Computer and Modernization, 2023, 0(09): 51-58.
[5]	TANG Yu-lin, HUANG Deng-shan, CHEN Shu-lu, CHEN Peng-ming. SFIM Image Fusion Method Combining IHS and Adaptive Filtering [J]. Computer and Modernization, 2023, 0(09): 70-76.
[6]	MAO Ming-yang, XU Sheng-chao. Continuous Attribute Discretization Algorithm of Rough Sets for BP Neural Networks Based on Particle Swarm Optimization#br# [J]. Computer and Modernization, 2023, 0(09): 115-119.
[7]	LIU Xian-zhuo, DENG Wei-si, XIE En-yan. Adaptive Protection System for Distribution Network Considering Grid Connection of Distributed Generation [J]. Computer and Modernization, 2023, 0(09): 120-126.
[8]	WANG Jia-chen, ZHANG Hong-xin, LIU Qing-hua, . CT Image Generation of Pneumonia Based on Generative Adversarial Network [J]. Computer and Modernization, 2023, 0(07): 20-24.
[9]	LUO Wei, LIU Si-yuan, XU Jian-xiang, DONG Tian-pei. Improved Solar Cell Defect Detection Algorithm Based on YOLOv5s [J]. Computer and Modernization, 2023, 0(07): 119-126.
[10]	ZHANG Jun, SU Wen-hao. Optimization Method of Hadoop File Archiving Based on LZO [J]. Computer and Modernization, 2023, 0(06): 1-6.
[11]	SU Jin-ku, GUI Zhi-ming. Prediction of Short-term Taxi Flow Based on Spatio-temporal Characteristics [J]. Computer and Modernization, 2023, 0(05): 32-38.
[12]	PENG Sui, XU Liang, ZHANG Zhi-qiang, LOU Yuan-yuan, YU Hao, QIN Xiao-hui. Probabilistic Voltage Stability Evaluation Algorithm Based on Mixed Vine Copula and ILHS [J]. Computer and Modernization, 2022, 0(12): 6-12.
[13]	WANG Ying-ying, ZHUANG Yi, SUN Yi-fan. Reliability Evaluation Model of BP Neural Network Based on Particle Swarm Optimization [J]. Computer and Modernization, 2022, 0(12): 42-49.
[14]	WEN Zi-xin, LI Shao-ying, WANG Bin-cheng, LIU Bo, . Face Clustering Method Based on Nearest Neighborhood Aggregation [J]. Computer and Modernization, 2022, 0(12): 81-87.
[15]	GAO Feng, ZHUANG Yi, LIU Xiao. A Trusted Transmission Scheme of SDN Based on Path Tracking Feedback [J]. Computer and Modernization, 2022, 0(12): 102-110.