Page 173 - 计算机应用软件开发技术研究

第五章 基于数据挖掘技术的智能信息处理

簇，并可以在带有噪声的空间数据库中发现任意形状的聚类。
DBSCAN 通过检查数据库中的每个点的于邻域来寻找聚类，如果一个点 p
的今令肠域包含多于 min 夕 oints 个点，则创建一个以 p 为核心对象的新簇，然

后 DBscAN 反复地寻找从这些核心对象可以直接密度到达的对象（这个过程可
能会导致一些簇的合并），直到没有新点可以添加。
如果采用空间索引，DBSCAN 的计算复杂度是 O（nlogn），n 是对象个
数。同时，一邻域和 mill points 比较难确定。

2.OPTICS（Ord ering points to Ident ify the Clustering Strueture）
在 DBSCAN 方法中需要人为确定参数，这是影响聚类质量的主要因素之
一。OPTICS 的提出就是解决这个问题。OPTICS 没有显示地产生一个数据集合
簇，它为自动和交互的聚类分析计算一个簇次序，这个次序代表了数据的基于密

度的聚类结构，它包含的信息等同于从一个宽广的参数设置范围所获得的基于密
度的聚类。
3.DENCLUE（DEN sity 一 based CLUstEring）
该算法主要基于下面的想法：

每个数据点的影响可以用一个数学函数来形式化地模拟，它描述一个数据点
在邻域里的影响（影响函数）；数据空间的整体密度可以被模型化为所有数据点
的影响函数的总和；聚类可以通过确定密度吸引点来得到，这里的密度吸引点是
全局密度函数的局部最大。基于这些想法，我们能够形式化定义中心定义的簇和

任意形状的簇。如果密度吸引点 x 的密度大于一个闭值毛，那么 x 的中心定义簇
是一个被 x 密度吸引的子集 C，否则 x 是孤立点。一个任意形状的簇是子集 C 的
集合，每个是密度吸引的，有不小于阈值毛的密度函数值，并从每个区域到另一
个都存在一条路径 P，该路径上每个点的密度函数值都不小于阈值 ξ。

（四）基于网格的聚类方法
基于网格的聚类方法采用一个多分辨率的网格数据结构。它将空间向量化为
有限数目的单元，这些单元形成了网格结构，所有的聚类操作都在网格上进行。
这类方法的优点是处理速度快，处理时间与数据对象数无关，仅依赖于量化空间

中每一维上的单元数目。
1.STING（Statis tiealI nformation Grid）统计信息网格
STING 方法将空间区域划分为矩形单元，不同级别的分辨率对应不同级别

·161·