基于网格聚类中边界点的处理

江先伟（福建船政交通职业学院 福建 福州 350007）

0 引言

基于网格的聚类方法是运用网格技术，把对象空间量化为有限数目的网格单元，形成一个网格结构，所有的聚类操作都在这个网格结构上进行。一个网格单元的邻居是指与其有共同边界的或有共同点的那些网格单元。一个网格单元包含对象的数目超过给定的密度阈值MinPts，则认为它是高密度单元，否则视其为低密度单元。连接相邻密集单元的最大区域就形成一个“簇”，在这个区域内的所有对象属于这个簇。对孤立点，在聚类过程中应该将其丢弃，如果一个低密度单元的相邻的网格单元中存在高密度单元，那么该单元中的点可能是簇的边界点，也可能是噪声点，为此，可利用边界处理技术作进一步处理。

聚类的边界代表了一种潜在的模式，对数据挖掘有着重要的意义。但是目前涉及边界的算法并不多，对其研究远远不够。另一方面，边界点处于某些簇的相邻位置，许多聚类算法（如基于网格的方法）不能准确地把这些边界点划分到对应的簇中，从而降低了聚类结果的质量。

1 相关工作

1.1 边界点的定义

在DBSCAN算法中，第一次提出了边界点的概念。算法是基于密度定义了簇的边界点，即如果一个对象不是核心点（所谓核心点指的是某对象的ε-邻域内至少包含最小数目MinPts个对象），且它是从某个核心点直接密度可达的 （即该对象落入某核心点的ε-邻域内），则定义该对象为边界点。

Chen Xia等提出了聚类边界点检测算法BORDER[1]，其边界点的定义如下：