收稿日期! !"#$%"&%!!! 修回日期! !"#$%"4%!3 ( ( 基金项目! 江苏高校优势学科建设工程资助项目! 国家自然科学基金 资 助 项目
"3##3$##2# !江苏高校哲学社会科学重点研究基地重大招标资助项 目 "!"#"*15J"!&# !中国制 造业发展研 究院 !"#! 年度开放 课题资助项 目
"-)!"#!"!""%3#
作者简介!张丽杰"#436%#$女$黑龙江双城人$讲师$博士$主要研究方向为灾害管理" HEPEG=7>#2$AB?C# A
具有稳定饱和度的
*Q%B:N
算法
!
张丽杰
8!D
"南京信息工程大学 8A气象灾害预报预警与评估协同创新中心! DA中国制造业发展研究院$ 南京 !#""66#
摘(要! 在 1I-\K,算法基础上提出 --%1I-\K,算法$克服了现有密度聚类方法存在的一些问题$在不增加算
法时间复杂度的情况下
$避免了空间邻近点被划入噪声簇和不同簇空间位置叠加等问题% 提出饱和度概念$保
证同一簇内部非空间属性分布的稳定性$ 并以热带气旋生成海域为例$证明这种算法可以取得很好的聚类效果%
关键词! 密度聚类! 非空间属性! 稳定饱和度
中图分类号! LN#&!LN$"#e2(((文献标志码! K(((((文章编号! #""#%$24'"!"#6#"3%#43!%"6
;?E
!#"A$424 OPAE::9A#""#%$24'A!"#6A"3A"##
-F8DHG:8F@S8FE?9 ;G9:EFQ?[1I-\K,8H<?SEF7C
0ZK,W/E%PEG
8!D
" ,!8)--,2)(,3&*/>##)*,3&)# 8/#3/()# P)(/+,<36:*,-%,3&)# )4Q/3/)()-)9&+,-5&<,<3/(<! 2!8$&#, >#<3&3%3/)4Q,#%4,+3%(	 5/*/-)N7/#3! O,#K
Z	 ;#&*/(<&30)4>#4)(7,3&)# @+&/#+/6D/+$#)-)90! O,#Z	 !#""66! 8$&#,$
!"#$%&'$% L7E:R8RGSRS?R?:G; 8:F8DHG:8F@S8FE?9 ;G9:EFQBH@:FGSE9<8H<?SEF7C! U7EB7 ?TGSB8CG:?CGRS?DHGC:?[1I-\K,
8H<?SEF7CAVF8::E<9G; F78F8T?E;:F7G:R8BG8;P8BG9FR?E9F:F?9?E:GBH@:FGS:
! RSGTG9FG; ;E[[GSG9F:R8FE8HBH@:FGS:B?TGSUEF7 ?F7%
GS:89; ;?G:93 FE9BSG8:GF7GFECGB?CRHGjEFQAJG89U7EHGEFECR?SFG; F7G:8F@S8FE?9 B?9BGRFF?G9:@SG9?9%:R8FE8H8FFSED@FG
UEF7E9 F7G:8CGBH@:FGS;E:FSED@FG:F8DEHEFQA`E98HHQ! EFBH@ :FGSG; F7GFS?REB8HBQBH?9G[?SC8FE?9 U8FGS:DQ--%1I-\K,8H<?%
SEF7C
! RS?TGF78FF7G8H<?SEF7CB89 ?DF8E9 <??; BH@:FGSE9<SG:@HF:A
()* +,%-#% ;G9:EFQBH@:FGSE9<# 9?9%:R8FE8H8FFSED@FG:# :F8DHG:8F@S8FE?9
((随着人们对空间信息需求的增加!用于处理空间信息的各
种聚类 方法也 迅速 发展 起来( 例 如! 1I-\K," ;G9:EFQ%D8:G;
:R8FE8HBH@:FGSE9<?[8RRHEB8FE?9:UEF7 9?E:G$
&#'
算法可以发现任
意形状的空间聚类#基于密度的自适应聚类方法 L`\LJf
&!'
可
以实现移动对象轨迹聚类#1Y,\/XY算法可以通过核密度估
计!得到区域内点数据空间分布局部概率密度估计函数!以此
来确定空间聚类
&$'
( 类似的算法还有很多!它们促进了空间
聚类算法领域的发展
&6 _3'
( 由于 1I-\K,算法提出较早!聚
类效果) 时间复杂度和算法复杂度的综合评价较高!在空间聚
类算法领域得到了广泛的应用!已经成为很多学者进一步完善
的主要方法
( 学者们对 1I-\K,算法主要进行两个方面的改
进%
8$对其效率和聚类效果进行改进( 例如! fNLV\-" ?S;G%
SE9<R?E9F:F?E;G9FE[QF7GBH@:FGSE9<:FS@BF@SG$ 算法就是基于 1I%
-\K,的概念!为自动交互的聚类分析计算出一个增强聚类顺
序
&&'
#还有的算法针对非均匀数据集等问题提出了改进
&4 _##'
(
这类研究既拓展了 1I-\K,算法的功能!也提高了该类算法
的效率
&#! _#2'
(
D$增加处理对象的属性维度( 例如!可以处理空间和非
空间属性的 W1I-\K," <G9GS8HE=G; ;G9:EFQ%D8:G; :R8FE8HBH@:FG%
SE9<?[8RRHEB8FE?9:UEF7 9?E:G$算法!即根据用户自定义集的加
权势 " UGE<7FG; B8S;E98HEFQ$ 函 数 和 指 定 的 最 小 阈 值 " CE9%
UGE<7F
$!按照 1I-\K,方法进行聚类!可以发现符合具体条件
的聚类
!但不能发现自然聚类
'
( 学者们针对这一问题提出
了建设性的观点
&#&'
!但并没有真正地解决这一问题( -L%1I%
-\K,"89 8H<?SEF7C[?SBH@:FGSE9<:R8FE8H%FGCR?S8H;8F8$算法可以
实现空间属性)非空间属性和时间属性的自然聚类
'
!不需要
用户给定最小阈值!允许一个聚类内部非空间属性值存在微小
差异!同时也提出了非均匀数据集的解决方案!但又引起了其
他问题!本文将在后面详细论述(
非空间属性与空间属性的结合是一种现实需要!如气象信
息) 经济信息)动物迁徙信息等!单纯地分析空间信息或非空间
信息都不能满足人们的需要
( 所以!完善 1I-\K,算法处理
多维属性的能力
!既可以扩展 1I-\K,的应用范围!也可以解
决其他领域的现实问题
( 本文针对 1I-\K,算法处理非空间
属性信息能力的不足!提出具有稳定饱和度的密度聚类算法
--%1I-\K,( 它解决了不同簇的空间位置叠加)同一簇的非空
间属性分布不均匀)不能针对 "%# 属性聚类等问题(
"
(问题分析
1I-\K,聚类算法创建之初!只能用来解决空间属性的聚
类问题( 它要求用户首先计算一个恰当的 YR:和 JE9RF:( YR:
为一个足够小的圆形半径!JE9RF:为圆形中包括的最少点数(
通过不停地搜索!将连通的且 YR:邻域中至少包括 JE9RF:个点
的点集合并成簇!零散的点划入噪声簇( 使用 1I-\K,算法!在
含有噪声的空间数据库中!可发现任意形状的聚类( 但 1I%
第 $# 卷第 3 期
!"#6 年 3 月(
计 算 机 应 用 研 究
KRRHEB8FE?9 .G:G8SB7 ?[\?CR@FGS:
^?He$# ,?e3
*@HA!"#6