文档介绍：空间数据挖掘中的聚类算法
朱屹, 刘安丰
(中南大学,软件学院,湖南长沙,410075)
摘要:本文系统综述了文献中发表的大量空间聚类算法,依据这些算法的特点,将它们归纳为两类:划分聚类算法、层次聚类算法。针对划分聚类算法,重点分析了PAM、CLARA和CLARANS算法。针对层次聚类算法,重点综述了凝聚和分解层次聚类,分析了BIRCH、CURE、CHAMELEON算法。比较了这些算法的复杂度,并介绍了相关应用。
关键词:聚类算法;聚类分析;数据挖掘;空间数据库
引言
随着数据挖掘技术的出现,学者们开始采用各种方法从大型数据库的数据中发现知识,同样也利用数据挖掘技术对空间数据进行分析。这种空间数据挖掘的方法很好地弥补了传统空间统计分析的不足,很快受到了学者的重视。空间数据挖掘,也称基于空间数据库的数据挖掘和知识发现(Spatial Data Mining and Knowledge Discovery),作为数据挖掘的一个新的分支,是指从空间数据库中提取用户感兴趣的空间模式与特征、空间与非空间数据的普遍关系及其它一些隐含在数据库中的普遍的数据特征[1]。
目前大多数空间数据挖掘方法都是基于空间聚类与关联规则发现。空间聚类方法是空间数据挖掘中的主要方法之一,是在一个比较大的多维数据集中根据距离的度量找出簇或稠密区域. 聚类算法无需背景知识,能直接从空间数据库中发现有意义的空间聚类结构[2]。在无先验知识的情况下,聚类分析技术是进行数据挖掘时的首选[3],因而运用空间数据聚类方法来处理海量数据,对于提取大型空间数据库中有用的信息和知识具有十分重要的现实意义。
概述
目前,针对聚类分析提出了许多算法,这些算法可大致分为两类:划分聚类算法、层次聚类算法。划分聚类算法依据对象相似性来分配对象,如k-means
[4]和k-medioid。层次聚类法是一系列连续的合并和分解过程,可以自上向下连续分解,也可以自下向上连续合并。基于格网的聚类算法也可视为层次聚类算法。基于位置的聚类算法依赖局部对象之间的关系来聚类,既可以基于密度,也可以基于随机分布聚类。对于空间数据聚类,则是基于空间数据的特点对聚类算法进行改进, 从而使之适用于空间对象的特性,如DBSCAN 算法[5] 、CLATIN算法[6]、DDSC算法[7]等。
划分聚类
划分算法大多数是在PAM(Partition Around Medoids)算法、CLARA(Clustering Large Applications)算法和CLARANS(Clustering Large Application based upon Randomized Search) [8]算法的基础之上发展起来的。在数据量较大,计算复杂度较高时,PAM和CLARA算法效率较低。因此为了提高效率,提出了基于随机搜索的CLARANS算法。实验表明CLARANS优于PAM与CLARA。后有学者在CLARANS上进一步发展了新的划分聚类算法,进行了推广,提出了概念聚类的方法。
PAM算法
PAM算法[4]首先在n个对象中随机选取k个对象作为中心点。将余下的n-k个对象(非选择对象)依据与中心点距离或相异程度最小原则划分到上述k个聚类中。即如果是未选择对象,是中心点,当
是以为中心点的聚类。表示对象与中心