障碍约束下人工蜂群空间聚类算法研究

158 浏览量更新于2024-08-27 收藏 845KB PDF 举报

"这篇研究论文探讨了一种基于人工蜂群（Artificial Bee Colony, ABC）算法的带障碍约束的空间聚类方法。该算法旨在解决在存在障碍空间中的数据对象优化分区问题，将N个对象划分为K个聚类。通过与经典的k-均值和COE-CLARANS聚类算法进行比较，论文证明了ABC-CO算法在处理障碍约束条件下的聚类分析的合理性和实用性。" 文章详细内容: 在数据分析和挖掘领域，空间聚类是一种重要的技术，它能发现数据集中的自然群体或结构。然而，在现实世界中，数据往往受到各种障碍或限制条件的影响，使得传统的聚类算法可能无法有效地处理这类问题。这篇研究论文提出了一种创新的方法，即人工蜂群（Artificial Bee Colony）算法与障碍约束相结合的空间聚类算法（简称ABC-CO）。人工蜂群算法是受到蜜蜂寻找花粉源行为启发的一种全局优化算法，它具有简单、易于实现和能够找到全局最优解的特性。在ABC-CO算法中，人工蜂群被用于在考虑障碍的空间环境中寻找最佳聚类解决方案。每个“工蜂”代表一个潜在的聚类中心，它们在数据空间中搜索，同时避开障碍区域，以最大化聚类的质量。 ABC-CO算法的运行过程包括三个主要步骤：食物源的初始化、工蜂的搜索以及侦察蜂的选择。在初始阶段，随机选择一部分数据对象作为初始的聚类中心。接着，工蜂们根据障碍约束和距离函数进行迭代，不断调整聚类中心的位置，以期改善聚类效果。在此过程中，如果某个聚类中心落在障碍区域内，将重新选择新的位置。最后，侦察蜂负责检查并替换低质量的食物源，即聚类中心，以促进全局最优解的发现。为了验证ABC-CO算法的有效性，研究者将其与两种广泛使用的经典聚类算法——k-均值和COE-CLARANS进行了对比。k-均值算法基于距离度量，但对初始中心的选择敏感，且不适应处理非凸形状的聚类。而COE-CLARANS算法则是一种随机化聚类方法，能够在处理噪声和异常值时表现良好，但同样未考虑障碍因素。通过对比实验，ABC-CO算法在处理障碍约束的空间聚类问题上展现了更优的性能，表明其在处理复杂环境下的聚类任务时具有更高的适应性和准确性。总结来说，这篇研究论文提出了一个新颖的空间聚类策略，利用人工蜂群算法处理带有障碍的空间数据，解决了传统方法在处理这类问题时的局限性。通过与k-均值和COE-CLARANS的比较，ABC-CO算法展示了其在障碍空间聚类分析中的优势，为未来在地理信息系统、环境科学、遥感图像分析等领域应用提供了新的思路和工具。

COMPUTER MODELLING & NEW TECHNOLOGIES 2014 18(10) 324-328 Sun Li-ping, Luo Yong-long, Ding Xin-tao, Chen Fu-long

324

Operation Research and Decision Making

Spatial clustering algorithm with obstacles constraints

based on artificial bee colony

Li-ping Sun

1, 2

, Yong-long Luo

1, 2

, Xin-tao Ding

, Fu-long Chen

College of National Territorial Resources and Tourism, Anhui Normal University, Anhui, 241000, China

Engineering Technology Research Center of Network and Information Security, Anhui Normal University, Anhui, 241000, China

Received 1 August 2014, www.cmnt.lv

Abstract

Spatial clustering is one of practical data mining technique. In this paper, artificial bee colony (ABC) is used for clustering algorithm,

which aims to optimally partition N objects into K clusters in obstacle space. The ABC algorithm used for clustering analysis with

obstacles constraints, called The ABC algorithm used for clustering analysis with obstacles constraints ABC-CO, is proposed in the

paper. By comparison with the two classic clustering algorithms, k-medoids and COE-CLARANS, demonstrates the rationality and

usability of the ABC-CO algorithm.

Keywords: spatial clustering, artificial bee colony, obstructed distance; fitness calculation

1 Introduction

Spatial clustering is the organization of geographical data

set into homogenous groups, the aim of which is to group

spatial data points into clusters [1-3]. Most spatial

clustering algorithms apply Euclidean distance between

two sample points to measure the proximity of spatial

points. However, physical obstacles (e.g. rivers and

highways) often exist in real applications, which can

hinder straight reachability among sample points. As a

result, the clustering results, which utilize Euclidean

distance measure are often unreasonable. Taking the

simulated dataset in Figure 1a as an example, where the

points represent the location of consumers. The clustering

result shown in Figure 1b can be obtained, when the rivers

and hill as obstacles are not considered. Obviously, the

result is not realistic. If the obstacles are taken into

account, the clustering result in Figure 1c can be obtained.

River

lake

a) Spatial dataset with obstacles

b) Spatial clustering result ignoring obstacles

c) Spatial clustering result considering

obstacles

FIGURE 1 Spatial clustering in the presence of obstacles

At present, there are a few algorithms considering

obstacles constraints in the spatial clustering process [4-9].

There generally exists the shortcomings, including low

robustness and easy to fall into local optimum. Many

heuristic clustering algorithms have been introduced to

overcome local optima problem, such as evolutionary

algorithms [10, 11], swarm intelligence algorithms [12,

13] and so on [14, 15]. Artificial bee colony (ABC)

algorithm, which simulates the intelligent foraging

behaviour of a honey bee swarm, is a novel category of

heuristic algorithms. In this paper, ABC optimization

Corresponding author e-mail: ylluo@ustc.edu.cn

algorithm for optimization problems, which is proposed by

Karaboga [16], is applied to spatial clustering analysis.

Fathian and et al. proposed the application of honeybee

mating optimization in clustering [17]. Zhang and et al.

presented a novel artificial bee colony approach for

clustering which was compared with other heuristic

algorithms such as genetic algorithm, ant colony,

simulated annealing and tabu search [18]. Yan and et al.

designed a hybrid artificial bee colony (HABC) algorithm

for data clustering [19]. Karaboga and Ozturk applied

下载后可阅读完整内容，剩余4页未读，立即下载

weixin_38737630

粉丝: 1
资源: 929

障碍约束下人工蜂群空间聚类算法研究

【数据聚类】基于改进人工蜂群算法的K均值聚类算法Matlab代码.rar

基于改进人工蜂群算法的K均值聚类算法-喻金平-郑杰-梅宏标1

人工蜂群优化提升数据流聚类算法性能

改进人工蜂群的K-medoids聚类算法：提高精度与搜索能力

基于改进流形距离和人工蜂群的二阶段聚类算法

IABC_KMC_test_on_Iris_wine_glass_人工蜂群_人工蜂群算法K均值聚类算法_改进_k聚类改进_win

基于K_means的改进人工蜂群聚类算法

一种基于蜂群原理的划分聚类算法* (2011年)

基于变异精密搜索的蜂群聚类算法

基于蜂群原理的自适应划分聚类算法：无K值限制与高效性能

最新资源