《一种新的基于网格压缩的聚类算法ＳＧＲＩＤＳ研究.doc》由会员分享，可在线阅读，更多相关《一种新的基于网格压缩的聚类算法ＳＧＲＩＤＳ研究.doc（8页珍藏版）》请在三一文库上搜索。
1、一种新的基于网格压缩的聚类算法研究doi:10.3969/j.issn.1001-3695.2009.09.020 Research of new clustering algorithm SGRIDSbased on grid data compression ZHAO Hui, LIU Xi-yu (College of Management & Economic, Shandong Normal University, Jinan 250014, China) Abstract:By introducing a new grid-based data compression framew
2、ork, conducted the study on the clustering algorithm SGRIDS which dealed with a large spatial databases. Considering that the input parameter has a great impact on the quality of clustering algorithms, improved the settlement of the value for density threshold, decreased the impact of input paramete
3、r, thus attaining a better clustering effect. Key words:cluster analysis; clustering algorithms; grid-based data compression; algorithm SGRIDS 随着计算机硬件和软件技术的飞速发展,尤其是数据库技术的普及,人们面临着日益扩张的数据海洋,原来的数据分析工具已无法有效地为决策者提供决策支持所需要的相关知识,从而形成一种独特的现象“丰富的数据、贫乏的知识”。数据挖掘1又称为数据库中知识发现(knowledge discovery from database,KD
4、D),它是一个从大量资料中抽取挖掘出未知的、有价值的模式或规律等知识的复杂过程。其目的在于大量的资料中发现人们感兴趣的知识。 常用的数据挖掘技术包括关联分析、异类分析、分类与预测、聚类分析以及演化分析等。聚类分析作为一种常用的数据挖掘方法得到了广泛的应用。 1 聚类演算法分析 1.1 常见聚类算法 聚类2分析是直接比较各事物之间的性质,将性质相近的归为一类,将性质差别较大的归为不同的类。目前,聚类分析已经被广泛地应用到许多领域中,包括模式识别、数据分析、图像处理以及市场研究等3。在商务上,聚类能够帮助市场分析人员从客户基本库中发现不同的客户群;在生物学上,聚类用于推到植物和动物的分类,对基因进
5、行分类;聚类也能对Web上的文?n进行分类等。 大体上,聚类算法4划分为如下几类: a)划分方法。给定一个包含n个对象或数据行,划分方法将数据集划分为k个子集(划分)。其中每个子集均代表一个聚类(kn)。代表算法为K-means算法、K-medoids算法等。 b)层次方法。该方法就是通过分解所给定的数据对象集来创建一个层次。它存在的缺陷就是进行(组)分解或合并之后无法回溯。将循环再定位与层次方法结合起来使用常常是有效的,如BIRCH和CURE就是基于这种组合方法设计的。 c)基于密度的方法。只要邻近区域的密度(对象或数据点的数目)超过某个阈值,就继续聚类。 d)基于网格的方法。该方法是将对象
6、空间划分为有限数目的单元以形成网格结构。在大部分基于网格方法的聚类算法中,所有的聚类操作都在网格数据结构上进行,网格中的数据压缩质量就决定了算法的聚类质量。本文在学习新的基于网格的数据压缩方法前提下,研究了处理大型空间数据集的聚类算法。 e)基于模型的方法。该方法就是为每个聚类假设一个模型,然后再去发现符合相应模型的数据对象。它根据标准统计方法并考虑到噪声或异常数据,可以自动确定聚类个数,因而它可以产生很鲁棒的聚类方法。 上述方法各有特点,在不同的领域以及数据特点下发挥了不同的作用,实现了数据的有效聚类。但是,面对目前巨大的空间数据库则明显显示出其不足。为此,需要探讨空间数据挖掘的新方法,实现
7、空间数据聚类。 1.2 空间数据聚类 卫星图像、摄影、医学器械、地理信息系统等各种应用获取的空间数据量十分巨大,由人工来详细分析这些资料非常昂贵,甚至是不可能的。空间数据聚类的任务是发现数据中自然存在的簇。空间数据指的是二维空间或三维空间中的点、多边形以及d-维空间中的点5。对空间数据进行聚类分析是一个热点研究问题。 空间数据库的典型特征是规模大且数据分布不规则。对于无法全部装入内存的大型空间数据集,基于划分的CLARANS6和基于密度的DBSCAN7要求对资料集的随机存取或多遍扫描的代价非常昂贵,而网格方法的压缩功能和它能发现任意形状簇的能力使得基于网格方法的聚类算法特别适用于处理大型空间数
8、据库,算法STING8和算法WaveCluster9都是成功的基于网格方法的空间数据聚类算法。 本文学习了一个新的基于网格的数据压缩方法,对能处理大型空间数据集的聚类算法SGRIDS(a scalable GRID-based clustering algorithm for very large spatial databases)10进行了研究改进及实验分析。 2 基于网格的聚类算法SGRIDS及改进 2.1 基于网格的数据压缩方法11 首先将空间数据均匀划分为中等粒度的网格,然后计算每个网格单元所包含的数据点数目。网格单元内数据的密度定义为它包含的数据点数目除以网格单元的体积。起初,读入
9、的数据和网格单元都被保存到内存中。设密度阈值是一个位于网格单元数据密度最大值与最小值之间的值。若一个网格单元密度超过,它被称为一个高密度网格单元。相邻的高密度网格单元被合并,形成大的高密度区域。为方便计算,只有形成矩形区域的合并才被允许。包含在每个高密度区域内的数据点数目及其均值被保存下来,数据点被丢弃。未被合并的网格单元内的数据点都被直接保存在内存中。最后,内存中保存的数据点为高密度区域、未被合并的网格单元以及落入这些网格单元内的数据点。 2.2 算法SGRIDS改进 算法SGRIDS中关于密度阈值的确定,采用如下方法: 找到每个网格单元的数据点个数count0的网格单元的最大密度值dmax
10、和最小密度值dmin。密度阈值=dmin+(dmax-dmin)。若一个网格单元的count,它被称为一个高密度网格单元。参数取经验值0,1,其取值对算法影响较大。因此,本文对算法中的取值作改进,并进行了实验分析。 以下为改进后的算法SGRIDS。 输入:数据集,网格划分参数,控制数据压缩周期的参数p。 输出:带簇标志的不均匀划分的网格。 a)将数据空间的每维均匀划分为段以构建初始的网格单元。 b)读入部分数据,将它们投影到网格数据结构中,计算每个网格单元包含的数据点个数count。 c)找到count0的网格单元密度值di,按从小到大的顺序排列,算计xn=di1-di2,找到最大的密度差xm
11、ax,取此时的=di2。若一个网格单元的count,它被称为一个高密度网格单元。 d)将相邻的高密度网格单元合并,形成较大的矩形区域,计算这些区域内数据点的数目和均值。将区域内的数据点从内存中删除。 e)读入一个新的数据点,若它落入某个区域,修改此区域的count与均值,将次数据点丢弃;若它落入区域外的网格单元,修改此网格单元的count,并将次数据点保存在内存。 f)若d)执行后,该步已读入p个数据点,转入c)。 g)若数据集中还有数据未读入,转入e)。 h)执行c)和d)。 i)将区域标志为簇,相连的区域属于同一个簇。 j)给内存中的数据分配簇标志。数据点被分配给离它最近的区域所属的簇。
12、2.3 实验分析 本文采用的实验支持系统是MODE-CES 12,系统主界面如图1所示。 实验系统用C#语言开发。实验的软件环境是Windows XP Professional操作系统、Microsoft Visual Studio .NET 2003集成开发环境,使用SQL Server 2000作为数据库,使用SQL Server 2000 Driver for ODBC作为数据库驱动程序;硬件环境是Intel Pentium 4的CPU,512 MB内存80 GB硬盘。 数据集DS如图2所示。在图2中,显示的黑色区域为数据集DS,此数据集使用文献9中生成数据集DS4的方法生成。 下面将以本文研究的SGRIDS算法对图2中的数据集进行聚类分析: a)读入要进行聚类分析的数据源; b)选择聚类算法,并输入算法需要的参数; c)点击“开始聚类”按钮进行聚类分析,聚类完成后将弹出一个关于聚类耗时与聚类有效性指数的对话框; d)查看聚类结果。 图3显示的是图2数据集DS在改进算法下的聚类结果。采用原演算法分析使用不同的值处理图2的数据源DS时得到的簇的数目如表1所示。 表1 使用不同的值,得到的簇的数目(=75,p=20 000) 0.30.40.50.60.7 簇的数目22222 对于簇内数据为均匀分布的数据集DS,只有