基于密度的OPTICS聚类算法解析

基于距离的聚类方法限于发现球状簇，为克服这一不足，研究者提出了基于密度的聚类方法，它的主要思想是只要一个区域中的点的密度（样本的数目）超过某个阈值则继续聚类。

给定数据对象集合D，下面首先给出基于密度聚类的相关定义：

定义4.8（对象p的ε-邻域）：一个对象p的ε-邻域记为Nε（p），定义为：Nε（p）=｛q∈D|dist（p， q）≤ε｝，即给定对象半径ε内的区域称为该对象的ε-邻域。

定义4.9（核心对象，core point）：如果一个对象p的ε-邻域至少包含最小数目（MinPts）个对象，则称对象p为核心对象。此外，如果一个对象p的ε-邻域包含对象数目少于最小数目（MinPts）个对象，称对象p为边界对象（border point）。

定义4.10（直接密度可达，directly density-reachable）：如果一个对象p是在另一对象q的ε-邻域内，且q是一个核心对象，则对象p从对象q出发是直接密度可达的。

也就是说，一个对象p是从另一对象q出发，关于ε， MinPts直接可达的，要求满足以下条件：

（1） p ∈ Nε（q）。

（2） |Nε（q）|MinPts（核心对象条件）。≥

直接密度可达对于一对核心对象而言具有对称性，但如果其中一个对象是核心对象，而另一个是边界对象，则不具备对称性。图4-16显示了非对称情形。

图4-16　核心对象与边界对象

定义4.11（密度可达，density-reachable）：如果存在一个对象链p1，p2，…，pn，p1=q，pn = p，对pi∈D （1≤i≤n），pi+1是从pi关于ε和MinPts直接密度可达的，则对象p是从对象q关于ε和MinPts密度可达的。

密度可达性是直接密度可达性的一个扩展，这个关系具有传递性，但不一定是对称的（当两个均为核心对象时，这个关系是对称的）。同一个簇C中的两个边界点可能相互不是密度可达的，因为核心点条件对它们不成立，但是，应该存在C中的一个核心点，这两个边界点都是从它密度可达的。

定义4.12（密度相连，density-connected）：如果对象集合D中存在一个对象o，使得对象p和q是从o关于ε和MinPts密度可达的，那么对象p和q是关于ε和MinPts密度相连的。

密度相连性是一个对称关系，图4-17、图4-18解释了定义4.11和定义4.12，这是一个二维向量空间中的样本数据点集。注：以上定义仅要求一个距离度量，所以可以应用于来自任何距离空间的数据点。

图4-17　密度可达

图4-18　密度相连

例4.6：如图4-17、图4-18所示，给定ε为圆的半径，MinPts=3。根据以上定义：

（1）在被标记的点中，o1，q，o2及r在ε-邻域内至少包含了三个点，所以它们都是核心对象。

（2） p是从o1直接密度可达的。o1是从q直接密度可达的，反之亦然。

（3）因为p是从o1直接密度可达的，o1是从q直接密度可达的，所以p是从q间接密度可达的。但由于p不是一个核心对象，所以q并不是从p密度可达的。同理，r和s是从o2密度可达的，而o2是从r密度可达的。

（4） o2，r和s是密度相连的。

直观地讲，一个簇是相对于密度可达性达到最大值的一个密度相连的点集，而噪声则相对一簇来定义，即为数据集中那些不属于任何簇的数据点集。下面给出它们的定义：

定义4.13（基于密度的簇，cluster）：设D是存储对象的数据库，关于ε和MinPts的簇C是满足下列条件的D的非空子集：

（1） p， q：如果p∈C且对象q是从对象p关于ε和MinPts密度可达，则q ∈ C。（最大性）

（2） p，q∈C：对象p和对象q关于ε和MinPts密度相连。

根据上面的条件，一个基于密度的簇即是基于密度可达性的最大的密度相连对象的集合。

需要注意的是，一个簇不仅包含核心对象，也包含不满足核心对象条件的边界对象，这些对象至少是从簇中的一个核心对象直接可达的（否则就是噪声对象）。

定义4.14（噪声，noise）：设C1 ， C2 ， …， Ck是数据库D关于εi和MinPtsi的簇，不属于任何簇Ci的数据库中点集称为噪声。

下面按照以上定义及符号，详细介绍两种基于密度的聚类算法：DBSCAN和OPTICS。

1）基于高密度连接区域的聚类方法：DBSCAN（density-based spatial clustering of application with noise）［4］(www.xing528.com)

DBSCAN算法是最基本的基于密度的聚类算法，算法通过递归地进行最近邻搜索，来检索直接密度可达的对象，即检查数据库中每个对象的ε-邻域，如果一个点p的ε-邻域Nε（ p）包含多于MinPts个点，则创建一个以p作为核心对象的新簇C；然后，检查C中每个未被处理过的点q的ε-邻域，如果Nε（q）包含多于MinPts个对象，那么q的邻域中所有未在C中的对象被加到簇C中来，并且下一步检查它们的ε-邻域N；循环这个过程直到不再有新的对象点能被加到当前的簇C中，过程结束。

DBSCAN算法将具有足够高密度的区域划分为簇，并可以在含有噪声的空间数据库中发现任意形状的簇。

2）通过对象排序识别聚类结构的聚类方法：OPTICS（ordering points to identify the clustering structure）（基于密度的簇排序）

给定参数ε和MinPts， DBSCAN可以对数据集中的对象进行聚类，但它却仍然依赖于用户对这些参数的选择，使得发现的簇是可接受的。同样，在其他许多聚类算法中也存在类似的问题。特别是在高维的现实数据上，这些参数是很难设置的，所以许多算法对这些参数是比较敏感的，参数的轻微变化会导致簇结构发生很大的变化。此外，高维数据集的分布通常也是偏斜的，因此，内在的簇结构也很难用一个全局的密度参数来刻画。

为了解决这些难题，提出了不考虑参数说明的OPTICS聚类分析方法，OPTICS算法并不显式地产生一个数据集合簇，而是生成代表数据的基于密度的簇结构的一个簇排序（cluster ordering），算法最后对每个对象给出两个值：核心距离和可达距离。

引入OPTICS来给出基于密度的簇的排序，基于这样一个观察：对一个恒定的MinPts值，相对较高密度（即邻域半径ε值较小）的簇包含在相对较低密度（即ε值较大）的密度相连的集合内。如图4-19所示，这里C1和C2是相对于ε2（ε2＜ε1）的基于密度的簇，C是相对于ε1的基于密度的簇，C完全包含了C1和C2，那么可以先选择相对于最小的ε的密度可达的对象，来保证先发现密度高的簇（ε值较小）。

图4-19　基于密度的簇的解释

定义4.15（核心距离，core distance）：设p是数据集D中的一个对象，Nε（ p）是p的ε-邻域，MinPts是一个自然数，且MinPts_distance（ p）是从p到其MinPts个邻居的距离，对象p的核心距离是使得p成为核心对象的最小的ε。如果p不是核心对象，则p的核心距离无定义。

即p的核心距离core_distance ε，MinPts（ p） = UNDEFINED，当Card（ Nε（ p） ） ＜MinPts；MinPts_distance（p），其他。

定义4.16（可达距离，reachable distance）：设p和o是数据集D中的对象，Nε （o）是o的ε-邻域，MinPts是一个自然数，一个对象p关于另一个对象o的可达距离是o的核心距离和o与p的欧几里得距离之间的较大值。如果o不是一个核心对象，o和p之间的可达距离无定义。

即p关于o的可达距离reachable_di stanceε，Min Pts（ p， o） =UNDEFINED，当Nε（o）＜MinPts； max（ core_ distance（ o） ， distance（ o， p） ），其他核心距离与可达距离如图4-20所示。

图4-20　核心距离与可达距离定义的解释

由以上定义，给出OPTICS算法的主要步骤（详细伪代码如图4-21所示）：

OPTICS算法的基本思想是生成代表数据的基于密度的簇结构的一个簇排序，并存储每个对象的核心距离和可达距离，依据这些信息从排序中提取关于距离ε′（ε′小于距离ε）的簇。

OPTICS得到每个点的核心距离和可达距离的过程如下：

从任意一个点o开始，搜索所有关于ε和MinPts从o可达的点，如果o是核心点，则给出这些从o可达的点的核心距离和可达距离；如果o是边界点，则没有点从o密度可达，OPTICS处理其他点。

过程ExpandClusterOrder如图4-21b所示：

方法OrderSeeds:: Update（ neighbour， centerobject）如图4-21c所示：

图4-21　OPTICS算法

为让读者更清楚了解算法过程，下面进一步详细解释说明过程ExpandClusterOrder和方法OrderSeeds:: Update。

（1）过程ExpandClusterOrder: IF Object.core_distance ＜＞ UNDEFINED条件检查对象Object是否为核心对象，如果对象Object不是生成距离ε的核心对象，则返回算法OPTICS主循环体，选择数据库中下一个未被处理的对象；如果对象Object是关于距离小于等于ε的核心对象，则收集关于ε和MinPts的直接密度可达对象。从当前核心对象直接密度可达的对象插入种子列表OrderSeeds中［处理由方法OrderSeeds:: Update（neighbour， centerobject）进行］，用于进一步扩展。OrderSeeds中的对象按照其直接密度可达的最近的核心对象的可达距离排序。

While循环的每一步，方法OrderSeeds: next（ ）选择种子列表中具有最小可达距离的对象为当前对象currentObject，再确定该对象的ε邻域及核心距离，并将该对象及其核心距离和可达距离写入文件OrderFile中。如果currentObjecct是核心对象，则进一步扩展更多的候选对象插入到种子列表OrderSeeds中。

（2）方法OrderSeeds:: Update：邻域中的每一个对象的可达距离由中心对象Centerobject决定。未包含在种子列表OrderSeeds中的对象仅插入该对象及其可达距离；对于已经存在于列表中的对象，若该对象的可达距离小于其当前可达距离，则将其向列表更顶端移动。

上述算法OPTICS的各步骤生成了关于ε和MinPts的数据库参数化簇排序，此后可以通过扫描簇排序，以及依据对象的可达距离和核心距离指定簇的隶属关系，从排序中提取任意关于MinPts和簇距离ε′ （ε′≤ε）的基于密度的簇。下述算法ExtractDBSCAN -Clustering（图4-22）描述了这一任务的实现：

图4-22　ExtractDBSCAN-Clustering算法

算法中，首先检查当前对象Object的可达距离是否大于簇距离ε′，该情况下，簇排序中位于当前对象之前的任何对象都不是关于ε′和MinPts密度可达的，因为如果对象Object从簇排序中的前一个对象是关于ε′和MinPts密度可达的，则其可达距离至多设置为ε′。因此，如果对象的可达距离大于ε′，观察对象的核心距离，若Object是关于ε′和MinPts的核心对象，则开始一个新的簇；否则Object被指定为“噪声”（注意，在簇排序中的第一个对象的可达距离通常是UNDEFINED，且假定UNDEFINED比任何一个已定义的距离大）；如果对象的可达距离小于ε′，则将该对象分配到当前簇中，因为它从簇排序中的前一个核心对象是关于ε′和MinPts密度可达的。