空间平滑搜索CLARANS算法  

Search Space Smoothing CLARANS Algorithm

作　　者：宗瑜[1] 江贺[2] 张宪超[2] 单世民[2] 

机构地区：[1]大连理工大学电子与信息工程学院,辽宁大连116621 [2]大连理工大学软件学院,辽宁大连116621

出　　处：《小型微型计算机系统》2008年第4期667-671,共5页Journal of Chinese Computer Systems

基　　金：国家自然科学基金重大项目(90412007)资助;国家自然科学基金项目(60503003)资助;辽宁省博士启动基金(20051082)资助;大连理工大学青年教师培养基金资助;安徽省教育厅自然科学基金(KJ2008B133)资助

摘　　要：CLARANS是一种有效且广泛应用于空间数据挖掘的聚类算法,非常适合发现多边形的聚类结果.CLARANS的实质是随机重启搜索优化算法.由于搜索空间的表面粗糙不平,布满了局部最优解的"陷阱",因此CLARANS算法易受局部最优解的影响.空间平滑技术允许启发式搜索有效地避开局部最优解的"陷阱".本文给出了基于空间平滑搜索的CLARANS算法(CLARANS algorithm based on Search Space Smoothing-CLARANS-SSS),设计合理的噪声法空间平滑策略能够移除搜索空间中大部分的局部最优解.实验结果表明空间平滑搜索对于CLARANS算法非常有效.CLARANS is an efficient and effective clustering method especially in spatial data mining. It is applicable to locate objects with polygon shape. The essential of CLARANS is an optimization algorithm based on randomize start search. Due to the rugged terrain surface of search space, local search often gets stuck at a locally optimum configuration. So CLARANS is effective to locally optimum. Search space smoothing allows a local search heuristics to escape from a poor, local optimum. In this paper, CLARANS algorithm based on search space smoothing is proposed. By designing a proper Nosing smoothing function, we can easily wipe off the most of local optimum point. Experiment result demonstrated that the space smoothing is very efficient for CLARANS.

关 键 词：聚类分析 空间平滑搜索 CLARANS 

分 类 号：TP311[自动化与计算机技术—计算机软件与理论]