基于网格的多密度增量聚类算法

计算机与现代化

基于网格的多密度增量聚类算法

1.成都农业科技职业学院基础部，四川成都611130；
2.成都工业职业技术学院交通运输系，四川成都610081

收稿日期:2014-09-01 出版日期:2014-11-27 发布日期:2014-12-10
作者简介: 李光兴（1956-），男，四川仁寿人，成都农业科技职业学院副教授，研究方向：数据挖掘与人工智能；尹冀川（1960-），男，四川成都人，成都工业职业技术学院副教授，研究方向：数据挖掘。

Multi-density Incremental Clustering Algorithm Based on Grid

1. Department of Fundamental Courses, Chengdu Vocational College of Agricultural Science and Technology, Chengdu 611130, China;
2. Department of Transportation, Chengdu Industrial Vocational Technical College, Chengdu 610081, China

Received:2014-09-01 Online:2014-11-27 Published:2014-12-10

摘要/Abstract

摘要：

提出一种基于网格的多密度增量聚类算法MICG,定义含网格单元间的相对密度和重心距离的判别函数。当数据集的部分数据发生变动后，不需要对全部数据重新聚类，只需分析有数据变更

的单元与邻居单元的关系，结合原有的聚类结果形成新的聚类，有效地提高了聚类分析的效率。时间复杂度与空间复杂度同数据集大小、属性个数成线性关系。实验结果表明，MICG算法能够处理任意形

状和不同密度的类，有效地解决数据更新时的增量聚类问题。

关键词: , 网格聚类, 增量聚类, 多密度, 单元, 判别函数

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

李光兴1，尹冀川2，唐俊1. 基于网格的多密度增量聚类算法[J]. 计算机与现代化.

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

参考文献

［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]	苏金库, 桂智明. 基于时空特征的短时出租车流量预测[J]. 计算机与现代化, 2023, 0(05): 32-38.
[2]	杨骏, 王劲林, 倪宏, 盛益强, . 工控网络异常检测中基于灵敏度的动态迁移算法[J]. 计算机与现代化, 2023, 0(05): 46-51.
[3]	赵婧华, 杨秋翔. 基于AU-GCN与注意力机制的微表情识别[J]. 计算机与现代化, 2023, 0(03): 48-53.
[4]	栗伟松, 汤敏芳, 何征岭, 王鹏, 杜利东, 方震, 陈贤祥. 基于自注意力机制和单导联心电信号的自动睡眠分期算法#br#[J]. 计算机与现代化, 2022, 0(12): 50-59.
[5]	李静元, 张珂, 杨东裕. 基于雾计算的工业互联网安全数据访问方法[J]. 计算机与现代化, 2022, 0(12): 118-122.
[6]	周慧, 徐名海, 许晓东. 基于Attention-BIGRU-CRF的中文分词模型[J]. 计算机与现代化, 2022, 0(08): 7-12.
[7]	唐洁, 文元美. 基于3CNN-BiGRU的睡眠自动分期研究[J]. 计算机与现代化, 2022, 0(02): 120-126.
[8]	刁说. 禁忌搜索在栅格地图中的应用[J]. 计算机与现代化, 2021, 0(10): 8-14.
[9]	陈春燕, 刘梦赤. 基于粒子群遗传算法的智能组卷策略[J]. 计算机与现代化, 2021, 0(08): 16-23.
[10]	赵宇轩, 胡怀湘. 基于BiGRU-Attention-CNN模型的垃圾邮件检测方法[J]. 计算机与现代化, 2021, 0(04): 122-126.
[11]	宋鑫, 樊志强, . 基于Laguerre 前向神经网络的信息服务性能建模方法 [J]. 计算机与现代化, 2021, 0(03): 1-6.
[12]	魏健, 赵红涛, 刘敦楠, 加鹤萍 . 基于集成模型的超短时负荷预测方法[J]. 计算机与现代化, 2021, 0(03): 12-17.
[13]	冯云霞, 衣鹏, 韩正亮, 宋波. 基于CNN-BGRU-CRF的中文电子病历实体抽取方法[J]. 计算机与现代化, 2020, 0(11): 60-64.
[14]	李涛1,刘寰1,李亚玲2,向筱铭1 . 省级气象资料传输监控平台的设计及实现[J]. 计算机与现代化, 2019, 0(08): 117-.
[15]	段桂芹1，邹臣嵩2，刘锋2. 基于优化初始聚类中心的K中心点算法[J]. 计算机与现代化, 2019, 0(04): 1-.