第5期 刘贝贝，等：基于密度的统计合并聚类算法 ·713· (k≤n),则C:满足如下条件：1)C≠⑦，(i=1,2, 凝聚式层次聚类算法[o采用“自底向上”的方 …,k),即每一子集至少含有一个数据点；2)C:∩C= 式进行。一开始将数据集的每个数据点看作一类， ☑，(1≤i≠j≤k),即每个数据点只能属于一个子集： 然后进行一系列的合并操作，直到满足终止条件或 3)UC,=X,即每个数据点必须归属于某一子集。 所有数据点归为一类时停止凝聚。大部分层次聚类 数据点x,(=1,2,…,n)对子集C(i=1,2,…,k)的 算法都是采用凝聚式聚类，代表性的算法有基于代 隶属关系可用隶属函数u:表示，当u:=1时，x:∈ 表点的CURE算法I]、基于稠密点的DBSCAN算 C:,当u=0时，x华C:,其中隶属函数u∈{0,1}且 法I2J、NBC(neighborhood based clustering)算法B] 满足∑4，=1，j,0<∑西，<n,i。硬聚 以及基于核心点的MulCA(multilevel core--sets based aggregation)算法[4]等。 类的代表算法有K-means算法s]和Ncuts(normal- 随着信息技术的迅猛发展，数据源开始不断膨 ized cuts)算法[6]。二者都是致力于得到使目标函 胀，数据结构也变得日渐复杂，具有类内相异、类间 数达到最值的最优聚类。K-means算法取误差平方 相似、噪声和重叠现象的数据集层出不穷，这对于计 和函数作为目标函数，对初始聚类中心和异常点较 算机领域中一些易受噪声点和数据集大小影响的经 为敏感，且面对非凸数据集易陷入局部最优。Ncuts 典聚类算法（如K-means、Ncuts等）来说，是一种巨 算法取规范割函数为目标函数，将数据集的聚类问 大的挑战。 题转化为空间中带权无向图的最优划分问题。 在寻求更优的聚类算法的道路上，人们开始将 Ncuts算法可以聚类任意形状的数据，但大数据聚类 其他专业领域的知识同聚类算法相结合，统计思想 问题对其相似性矩阵的存储和特征向量的计算都是 逐步被应用于聚类算法中。早期统计聚类方法有 种挑战。 GMDD算法[1s]和EM算法[16]等。GMDD算法将数 在模糊聚类中，数据点的类别归属是不明确的， 据点和噪声点看作是由不同混合高斯分布生成的点 一个数据点可以属于所有类别。模糊聚类隶属度的 集，利用一个增强的模型模拟估计含有噪声点的原 取值由硬聚类中只能取0或1变为可以取[0,1]的 始模型。EM算法是一种迭代算法，用于含有隐变 任意值，该值用来表示每个数据点属于各个类别的 量的概率参数模型的最大似然估计或极大后验概率 可能性，仍然满足任意数据点对所有类别的隶属度 估计。2004年，针对复杂的图像分割问题，NoCk和 之和为1。代表性的模糊聚类算法有FCM算法[刀 Nielsen提出了统计区域合并算法(statistical region 和PCM(possibilitic C means)算法[8]。FCM算法利 merging,SRM)u7]。具体地，该算法将像素点作为 用数据点对每一类别的隶属度构成了一个隶属矩 最基本的区域，把像素的3个颜色特征看做3组独 阵，然后将算法的目标函数转变为一个与隶属矩阵 立随机变量，对每一组独立随机变量，根据独立有限 相关的函数，通过优化该目标函数完成聚类。为克 差分不等式得出合并的判定准则，利用像素点梯度 服FCM对噪声敏感的缺点，Krishnapuram和Keller 值从小到大的排序获得合并顺序，依据合并准则和 提出了PCM算法。该算法舍弃了FCM算法中每一 合并顺序，结合像素或区域进行迭代生长。通过控 点对各类别隶属度总和为1的约束条件，使得噪声 制每组独立随机变量的个数，SRM算法实现了对复 点具有很小的隶属度值，从而增加了算法对噪声的 杂图像中目标的快速分割和有效提取。 鲁棒性。 受SRM方法的启发，本文提出了一种基于密度 层次聚类算法又称为树聚类算法。它的主要思 的统计合并聚类算法(density-based statistical mer- 想是对给定的数据集依照相似性矩阵进行层次分 ging clustering,DSMC),该算法主要包括2个步骤： 解，使得聚类结果可以由二叉树或系统树图来描述， 1)根据数据点的密度信息获得合并顺序及每 即树状嵌套结构为H={H,H2,…,H,},（q≤ 数据点的k邻域。首先利用数据点的空间位置信 n),n为数据点的个数，当C:∈Hm,CeH,且m>l, 息及多维特征信息，计算数据点之间的相似性得到 有C:∈C,或C:∩C=对所有i成立，j≠i,m,l= 相似性矩阵，确定每一数据点的k邻域。然后将稠 1,2,…,9。层次聚类算法又分为分裂式和凝聚式 密点与其k邻域中所有点的相似性的最小值作为数 2种。 据点的密度信息，将密度从大到小的排序作为合并 分裂式层次聚类算法采用“自顶向下”的方式 的顺序。 进行。将数据集看作一类，根据类内最大相似性的 2)按照合并顺序依次将稠密点与其k邻域中 原则将数据集逐渐细分，直到满足终止条件或每一 的数据点进行合并判定。将数据点的每个特征看作 个数据点构成一类时停止分裂，例如MONA(mono- 一组独立随机变量，根据独立有限差分不等式得出 thetic analysis)算法[9]和DIANA(divisive analysis) 的合并判定准则判断两点是否合并。当2个数据点 算法[9]等。 对其任意的特征具有相同的期望时，划分为同一类（ｋ≤ｎ），则 Ｃｉ 满足如下条件：１） Ｃｉ ≠∅，（ ｉ ＝ １，２， …，ｋ），即每一子集至少含有一个数据点；２）Ｃｉ∩Ｃｊ ＝ ∅，（１≤ｉ≠ｊ≤ｋ），即每个数据点只能属于一个子集； ３）∪ｋ ｉ＝１Ｃｉ ＝Ｘ，即每个数据点必须归属于某一子集。 数据点 ｘｊ（ｊ ＝ １，２，…，ｎ）对子集 Ｃｉ（ｉ ＝ １，２，…，ｋ）的 隶属关系可用隶属函数 ｕｉｊ表示，当 ｕｉｊ ＝ １ 时，ｘｊ∈ Ｃｉ，当 ｕｉｊ ＝ ０ 时，ｘｊ∉Ｃｉ，其中隶属函数 ｕｉｊ∈｛０，１｝且 满足 ∑ ｋ ｉ ＝ １ ｕｉｊ ＝ １，∀ｊ，０ ＜ ∑ ｎ ｊ ＝ １ ｕｉｊ ＜ ｎ，∀ｉ。 硬聚 类的代表算法有 Ｋ⁃ｍｅａｎｓ 算法［ ５ ］ 和 Ｎｃｕｔｓ（ ｎｏｒｍａｌ⁃ ｉｚｅｄ ｃｕｔｓ）算法［ ６ ］ 。 二者都是致力于得到使目标函 数达到最值的最优聚类。 Ｋ⁃ｍｅａｎｓ 算法取误差平方 和函数作为目标函数，对初始聚类中心和异常点较 为敏感，且面对非凸数据集易陷入局部最优。 Ｎｃｕｔｓ 算法取规范割函数为目标函数，将数据集的聚类问 题转化 为 空 间 中 带 权 无 向 图 的 最 优 划 分 问 题。 Ｎｃｕｔｓ 算法可以聚类任意形状的数据，但大数据聚类 问题对其相似性矩阵的存储和特征向量的计算都是 种挑战。 在模糊聚类中，数据点的类别归属是不明确的， 一个数据点可以属于所有类别。 模糊聚类隶属度的 取值由硬聚类中只能取 ０ 或 １ 变为可以取［０，１］的 任意值，该值用来表示每个数据点属于各个类别的 可能性，仍然满足任意数据点对所有类别的隶属度 之和为 １。 代表性的模糊聚类算法有 ＦＣＭ 算法［ ７ ］ 和 ＰＣＭ（ｐｏｓｓｉｂｉｌｉｔｉｃ Ｃ ｍｅａｎｓ）算法［ ８ ］ 。 ＦＣＭ 算法利 用数据点对每一类别的隶属度构成了一个隶属矩 阵，然后将算法的目标函数转变为一个与隶属矩阵 相关的函数，通过优化该目标函数完成聚类。 为克 服 ＦＣＭ 对噪声敏感的缺点，Ｋｒｉｓｈｎａｐｕｒａｍ 和 Ｋｅｌｌｅｒ 提出了 ＰＣＭ 算法。 该算法舍弃了 ＦＣＭ 算法中每一 点对各类别隶属度总和为 １ 的约束条件，使得噪声 点具有很小的隶属度值，从而增加了算法对噪声的 鲁棒性。 层次聚类算法又称为树聚类算法。 它的主要思 想是对给定的数据集依照相似性矩阵进行层次分 解，使得聚类结果可以由二叉树或系统树图来描述， 即树状嵌套结构为 Ｈ ＝ ｛Ｈ１ ， Ｈ２ ，…， Ｈｑ ｝，（ ｑ≤ ｎ），ｎ 为数据点的个数，当 Ｃｉ∈Ｈｍ ， Ｃｊ∈Ｈｌ且 ｍ＞ｌ， 有 Ｃｉ∈Ｃｊ或 Ｃｉ∩Ｃｊ ＝ ∅对所有 ｉ 成立，ｊ≠ｉ，ｍ，ｌ ＝ １，２，…，ｑ。 层次聚类算法又分为分裂式和凝聚式 ２ 种。 分裂式层次聚类算法采用“自顶向下” 的方式 进行。 将数据集看作一类，根据类内最大相似性的 原则将数据集逐渐细分，直到满足终止条件或每一 个数据点构成一类时停止分裂，例如 ＭＯＮＡ（ｍｏｎｏ⁃ ｔｈｅｔｉｃ ａｎａｌｙｓｉｓ） 算法［９ ］ 和 ＤＩＡＮＡ（ ｄｉｖｉｓｉｖｅ ａｎａｌｙｓｉｓ） 算法［ ９ ］等。 凝聚式层次聚类算法［１０］ 采用“自底向上”的方 式进行。 一开始将数据集的每个数据点看作一类， 然后进行一系列的合并操作，直到满足终止条件或 所有数据点归为一类时停止凝聚。 大部分层次聚类 算法都是采用凝聚式聚类，代表性的算法有基于代 表点的 ＣＵＲＥ 算法［１１ ］ 、基于稠密点的 ＤＢＳＣＡＮ 算 法［１ ２ ］ 、ＮＢＣ（ｎｅｉｇｈｂｏｒｈｏｏｄ ｂａｓｅｄ ｃｌｕｓｔｅｒｉｎｇ）算法［１３ ］ 、 以及基于核心点的 ＭｕｌＣＡ（ｍｕｌｔｉｌｅｖｅｌ ｃｏｒｅ⁃ｓｅｔｓ ｂａｓｅｄ ａｇｇｒｅｇａｔｉｏｎ）算法［１４ ］等。 随着信息技术的迅猛发展，数据源开始不断膨 胀，数据结构也变得日渐复杂，具有类内相异、类间 相似、噪声和重叠现象的数据集层出不穷，这对于计 算机领域中一些易受噪声点和数据集大小影响的经 典聚类算法（如 Ｋ⁃ｍｅａｎｓ、Ｎｃｕｔｓ 等）来说，是一种巨 大的挑战。 在寻求更优的聚类算法的道路上，人们开始将 其他专业领域的知识同聚类算法相结合，统计思想 逐步被应用于聚类算法中。 早期统计聚类方法有 ＧＭＤＤ 算法［１ ５ ］和 ＥＭ 算法［１ ６ ］等。 ＧＭＤＤ 算法将数 据点和噪声点看作是由不同混合高斯分布生成的点 集，利用一个增强的模型模拟估计含有噪声点的原 始模型。 ＥＭ 算法是一种迭代算法，用于含有隐变 量的概率参数模型的最大似然估计或极大后验概率 估计。 ２００４ 年，针对复杂的图像分割问题，Ｎｏｃｋ 和 Ｎｉｅｌｓｅｎ 提出了统计区域合并算法（ ｓｔａｔｉｓｔｉｃａｌ ｒｅｇｉｏｎ ｍｅｒｇｉｎｇ，ＳＲＭ） ［１ ７ ］ 。 具体地，该算法将像素点作为 最基本的区域，把像素的 ３ 个颜色特征看做 ３ 组独 立随机变量，对每一组独立随机变量，根据独立有限 差分不等式得出合并的判定准则，利用像素点梯度 值从小到大的排序获得合并顺序，依据合并准则和 合并顺序，结合像素或区域进行迭代生长。 通过控 制每组独立随机变量的个数，ＳＲＭ 算法实现了对复 杂图像中目标的快速分割和有效提取。 受 ＳＲＭ 方法的启发，本文提出了一种基于密度 的统计合并聚类算法（ ｄｅｎｓｉｔｙ⁃ｂａｓｅｄ ｓｔａｔｉｓｔｉｃａｌ ｍｅｒ⁃ ｇｉｎｇ ｃｌｕｓｔｅｒｉｎｇ，ＤＳＭＣ），该算法主要包括 ２ 个步骤： １）根据数据点的密度信息获得合并顺序及每 一数据点的 ｋ 邻域。 首先利用数据点的空间位置信 息及多维特征信息，计算数据点之间的相似性得到 相似性矩阵，确定每一数据点的 ｋ 邻域。 然后将稠 密点与其 ｋ 邻域中所有点的相似性的最小值作为数 据点的密度信息，将密度从大到小的排序作为合并 的顺序。 ２） 按照合并顺序依次将稠密点与其 ｋ 邻域中 的数据点进行合并判定。 将数据点的每个特征看作 一组独立随机变量，根据独立有限差分不等式得出 的合并判定准则判断两点是否合并。 当 ２ 个数据点 对其任意的特征具有相同的期望时，划分为同一类 第 ５ 期 刘贝贝，等：基于密度的统计合并聚类算法 ·７１３·