利用K均值算法进行聚类时需要事先知道簇的个数,也就是 k 值。不同的是,基于密度聚类的算法却可以在无需事先获知聚类个数的情况下找出形状不规则的簇,例如图10-11所示的情况。
图10-11 密度聚类
密度聚类的基本思想是:
(1)簇是数据空间中稠密的区域,簇与簇之间由对象密度较低的区域所隔开;
(2)一个簇可以被定义为密度连通点的一个最大集合;
(3)发现任意形状的簇。
著名的DBSCAN(Density-based spatial clustering of applications with noise)算法就是密度聚类的经典算法。
DBSCAN算法中有两个重要参数: ε 和MinPts,前者为定义密度时的邻域半径,后者是定义核心点时的阈值(也就是可以构成一个簇所需之最小的数据点数)。由此,还可以定义一个对象的 ε- 邻域 N ε 为以该对象为中心半径为 ε 范围内的所有对象。
如图10-12所示, N ε ( p ):{ q | d ( p , q )≤ ε }。
图10-12 ε -邻域
另外一个重要概念是“高密度”:如果一个对象的 ε- 邻域中至少包含MinPts个对象,那么它就是高密度的。例如,在图10-12中,假设MinPts=4,则有
(1)点 p 的 ε- 邻域是高密度的;
(2)点 q 的 ε- 邻域是低密度的。
接下来,基于上面给出的概念,就可以定义三种类型的点:核心点(Core)、边界点(Border)和噪声点(Noise或Outlier)。
(1)如果一个点的 ε- 邻域内有超过特定数量(MinPts)的点,那么它就是一个核心点。这些点也就是位于同一簇内部的点;
(2)如果一个点的 ε- 邻域内包含的点数少于MinPts,但它又属于一个核心点的邻域,则它就是一个边界点;
(3)如果一个点既不是核心点也不是边界点,那么它就是一个噪声点。
可见,核心点位于簇的内部,它确定无误地属于某个特定的簇;噪声点是数据集中的干扰数据,它不属于任何一个簇;而边界点是一类特殊的点,它位于一个或几个簇的边缘地带,可能属于一个簇,也可能属于另外一个簇,其归属并不明确。图10-13分别给出了这三类点的例子,其中MinPts=5。
图10-13 核心点、边界点与噪声点
接下来讨论密度可达(Density-reachability)这个概念。如果对象 p 是一个核心点,而对象 q 位于 p 的 ε- 邻域内,那么 q 就是从对象 p 直接密度可达的。易见,密度可达性是非对称的。例如,在图10-12中,点 q 是从点 p 直接密度可达的;而点 p 则不是从点 q 直接密度可达的。
密度可达又分两种情况,即直接密度可达和间接密度可达。例如,在图10-14中,点 p 是从点 p 2 直接密度可达的。点 p 2 是从点 p 1 直接密度可达的。点 p 1 是从点 q 直接密度可达的。于是, q → p 1 → p 2 → p 就形成了一个链。那么,点 p 就是从点 q 间接密度可达的。此外,还可以看出,点 q 不是从点 p 密度可达的。
图10-14 直接密度可达和间接密度可达
密度可达关系不具有对称性,即如果 p m 是从 p 1 密度可达的,那么 p 1 不一定是从 pm 密度可达的。因为从上述定义可知, p 1 , p 2 ,…, p m -1 必须是核心点,而 p m 可以是核心点,也可以是边界点。当 p m 为边界点时, p 1 就不可能是从 p m 密度可达的。
DBSCAN算法描述如下。
遍历数据集 D 中的每个对象 o :
如果 o 还没有被分类,那么:
如果 o 是一个核心点,那么:
收集从 o 出发所有的密度可达对象并将它们划入一个新簇
否则:
将 o 标记成噪声点
可见,DBSCAN算法需要访问 D 中的所有结点(某些结点可能还需要访问多次),所以该算法的时间复杂度主要取决于区域查询(获取某结点的 ε- 邻域)的次数。由此而得的DBSCAN算法,其时间复杂度为 O ( N 2 )。如果使用k-d树等高级数据结构,其复杂度可以降为 O ( N log N )。
DBSCAN算法中使用了统一的 ε 值,因此数据空间中所有结点邻域大小是一致的。当数据密度和簇之间的距离分布不均匀时,如果选取较小的 ε 值,则较稀疏的簇中之结点密度不会小于MinPts,从而被认为是边界点而不被用于所在簇点进一步扩展。这样做的结果是,较为稀疏的簇可能被划分成多个性质相似的簇;与此相反,如果选取较大的 ε 值,则离得较近而密度较大的簇将很可能被合并成同一个簇,它们之间的差异将被忽略。显然,在这种情况下,要选取一个合适的 ε 值并非易事。尤其对于高维数据, ε 值的合理选择将变得更加困难。最后,关于MinPts值的选取有一个指导性的原则,即MinPts值应不小于数据空间的维数加1。