第11期 王玲等：一种基于密度的模糊自适应聚类算法 ·1561· 的设置仍然会影响聚类结果.赵文等的提出了一种 度和类间分离度为主要衡量因素的评价聚类质量的 自适应调整E印s参数的算法，实现对不同密度数据 指标，其计算公式为 的聚类，但是该算法仍需要人为设置min Pts参数. V= maxd(v,v)mind (v,V) (1) 夏鲁宁和荆继武的首先使用Inverse Gaussian拟合 判断Es参数，同时通过分析噪声点数量的分布特 m=1=1 征选择合适的min Pts,然后利用DBSCAN算法对数 式中，k为聚类数，n为数据样本个数“m为第j(= 据进行聚类，但其对密度差异大的数据集聚类效果 1,2,…,n)个数据样本x:对m(m=1,2,…,k)类的 不佳.文献]提出了一种基于密度和网格的快速 隶属程度，vm和y。分别表示第m和第h个聚类中 聚类算法，它结合了网格算法，提高了运算效率和精 心(m≠h),d(x,vm)表示x和vm的距离.式(1)的 度.Wang等图提出一种基于“势”的数据样本密度 分子部分表示类间离散度，分母表示类内紧凑度，因 的度量方法，该算法可以在线更新数据样本的“势” 此该指标值越大表明聚类效果越好 从而选出密度较大的数据样本作为聚类中心.以上 1.2算法思想 这些算法虽然在一定程度上缓解了基于密度的聚类 假设数据集为具有n个样本的数据集合X= 算法对参数的敏感度，但是仍然无法保证聚类结果 {x:j=1,2,,n},DFAC算法首先对数据进行归 的正确性 一化预处理，然后通过计算样本间的距离自适应地 为了降低基于密度的聚类算法对参数设置的敏 判断邻域半径，根据邻域半径得到每个数据样本的 感性以及保证最终聚类结果的有效性，本文提出了 密度，并根据样本密度逐渐增加聚类中心，同时提出 一种基于密度的模糊自适应聚类算法(DFAC).算 一种新的模糊聚类有效性指标以判断当前的聚类效 法通过自适应地确定E即s邻域半径得到数据样本的 果，选出最佳聚类数和聚类中心.进一步通过最小 密度，基于样本密度逐渐增加聚类中心直到新的模 化聚类目标函数实现聚类结果的优化 糊聚类有效性指标达到最优时得到聚类中心和最佳 (1)基于邻域半径确定样本密度.由于x,= 聚类数，并进一步更新聚类结果，得到优化后的最终 1,2,…,n)的密度为数据样本在其邻域半径Eps范 聚类结果.因为算法无需设定参数，所以极大地提 围内相邻的数据样本个数，记为count,所以数据样 高了算法的自适应性，而且利用新的模糊聚类有效 本密度与邻域半径有关.为了保证算法的自适应 性指标也可以保证最终聚类结果的有效性.为了验 性，无需预先给定邻域参数E印s,根据以下公式自适 证算法的有效性，本文采用UCI数据库中的四个数 应地确定邻域半径： 据集(Iis、Wine、Breast Cancer和Seed数据集)以及 Eps min max [d(x:,x)]) (2) i=1j=1j≠i 两个人工数据集进行实验，并对实验结果进行分析 其中d(x:,x)表示样本x:和x:间的距离.确定邻 比较，结果表明DFAC算法可以消除密度聚类算法 域半径以后，统计每个样本在邻域半径范围内相邻 对参数的敏感性，并且改善了聚类算法的自适应性 的样本数作为其密度 和准确性 (2)基于样本密度递增地选择聚类中心.当聚 1相关知识 类数k=1,则根据每个样本xG=1,2,…,n)的密 度count;选择密度最大的样本为第一个聚类中心 1.1基本概念 .为了既保证新聚类中心的密度大又与己 本文在密度聚类算法的基础上对一些相关术语 有聚类中心有较大的差异，这里根据下式递增地选 作以下定义 择新的聚类中心： 定义1邻域半径、Eps-邻域：给定一个数据样 v=(xI j=argmax (D.xcount)}S.(3) 本P,以P为中心，E即s为半径的空间范围称为P的 其中S={0,0,…,0}表示已经选出的聚类 Eps一邻域，其中Eps称为邻域半径. k-1 定义2数据样本P的密度：数据样本P的 中心集合，D=∑d(vo,x)表示x与S集合中 Eps邻域内包含数据样本的数目，用符号count表示 聚类中心的距离之和 数据样本的密度. (3)基于模糊聚类有效性指标迭代地优化聚类 定义3模糊聚类有效性指标：聚类有效性指 结果.当聚类数为k时，根据式(1)得到的模糊聚类 标主要是针对模糊划分的聚类进行有效性评价.为 有效性指标V.如果满足IV因-V-)1>E(这里 了保证聚类有效性，本文提出一种新的以类内紧凑 ε是大于0的极小值)，则令聚类数k=k+1,根据样第 11 期 王 玲等: 一种基于密度的模糊自适应聚类算法 的设置仍然会影响聚类结果． 赵文等［5］提出了一种 自适应调整 Eps 参数的算法，实现对不同密度数据 的聚类，但是该算法仍需要人为设置 min Pts 参数． 夏鲁宁和荆继武［6］首先使用 Inverse Gaussian 拟合 判断 Eps 参数，同时通过分析噪声点数量的分布特 征选择合适的 min Pts，然后利用 DBSCAN 算法对数 据进行聚类，但其对密度差异大的数据集聚类效果 不佳． 文献［7］提出了一种基于密度和网格的快速 聚类算法，它结合了网格算法，提高了运算效率和精 度． Wang 等［8］提出一种基于“势”的数据样本密度 的度量方法，该算法可以在线更新数据样本的“势” 从而选出密度较大的数据样本作为聚类中心． 以上 这些算法虽然在一定程度上缓解了基于密度的聚类 算法对参数的敏感度，但是仍然无法保证聚类结果 的正确性． 为了降低基于密度的聚类算法对参数设置的敏 感性以及保证最终聚类结果的有效性，本文提出了 一种基于密度的模糊自适应聚类算法( DFAC) ． 算 法通过自适应地确定 Eps 邻域半径得到数据样本的 密度，基于样本密度逐渐增加聚类中心直到新的模 糊聚类有效性指标达到最优时得到聚类中心和最佳 聚类数，并进一步更新聚类结果，得到优化后的最终 聚类结果． 因为算法无需设定参数，所以极大地提 高了算法的自适应性，而且利用新的模糊聚类有效 性指标也可以保证最终聚类结果的有效性． 为了验 证算法的有效性，本文采用 UCI 数据库中的四个数 据集( Iris、Wine、Breast Cancer 和 Seed 数据集) 以及 两个人工数据集进行实验，并对实验结果进行分析 比较，结果表明 DFAC 算法可以消除密度聚类算法 对参数的敏感性，并且改善了聚类算法的自适应性 和准确性． 1 相关知识 1. 1 基本概念 本文在密度聚类算法的基础上对一些相关术语 作以下定义． 定义 1 邻域半径、Eps--邻域: 给定一个数据样 本 P，以 P 为中心，Eps 为半径的空间范围称为 P 的 Eps--邻域，其中 Eps 称为邻域半径． 定义 2 数据样本 P 的密度: 数据样本 P 的 Eps 邻域内包含数据样本的数目，用符号 count 表示 数据样本的密度． 定义 3 模糊聚类有效性指标: 聚类有效性指 标主要是针对模糊划分的聚类进行有效性评价． 为 了保证聚类有效性，本文提出一种新的以类内紧凑 度和类间分离度为主要衡量因素的评价聚类质量的 指标，其计算公式为 V = maxd( vm，vh ) + mind( vm，vh ) [ k ∑ k m = 1 ∑ n j = 1 μ2 m，j d( xj ，vm ] ) ． ( 1) 式中，k 为聚类数，n 为数据样本个数，μm，j为第 j( j = 1，2，…，n) 个数据样本 xj 对 m( m = 1，2，…，k) 类的 隶属程度，vm 和 vh 分别表示第 m 和第 h 个聚类中 心( m≠h) ，d( xj ，vm ) 表示 xj 和 vm 的距离． 式( 1) 的 分子部分表示类间离散度，分母表示类内紧凑度，因 此该指标值越大表明聚类效果越好． 1. 2 算法思想 假设数据集为具有 n 个样本的数据集合 X = { xj ; j = 1，2，…，n} ，DFAC 算法首先对数据进行归 一化预处理，然后通过计算样本间的距离自适应地 判断邻域半径，根据邻域半径得到每个数据样本的 密度，并根据样本密度逐渐增加聚类中心，同时提出 一种新的模糊聚类有效性指标以判断当前的聚类效 果，选出最佳聚类数和聚类中心． 进一步通过最小 化聚类目标函数实现聚类结果的优化． ( 1) 基于邻域半径确定样本密度． 由于 xj ( j = 1，2，…，n) 的密度为数据样本在其邻域半径 Eps 范 围内相邻的数据样本个数，记为 countj ，所以数据样 本密度与邻域半径有关． 为了保证算法的自适应 性，无需预先给定邻域参数 Eps，根据以下公式自适 应地确定邻域半径: Eps = minn i = 1 { max n j = 1; j≠i ［d( xi，xj ) ］} ． ( 2) 其中 d( xi，xj ) 表示样本 xi 和 xj 间的距离． 确定邻 域半径以后，统计每个样本在邻域半径范围内相邻 的样本数作为其密度． ( 2) 基于样本密度递增地选择聚类中心． 当聚 类数 k = 1，则根据每个样本 xj ( j = 1，2，…，n) 的密 度 countj 选择密度最大的样本为第一个聚类中心 v( 0) 1 ． 为了既保证新聚类中心 v( 0) k 的密度大又与已 有聚类中心有较大的差异，这里根据下式递增地选 择新的聚类中心: v( 0) k = { xj | j = argmax( Dj × countj ) } ; xjS． ( 3) 其中 S = { v( 0) 1 ，v( 0) 2 ，…，v( 0) k － 1 } 表示已经选出的聚类 中心集合，Dj = ∑ k －1 m = 1 d( v( 0) m ，xj) 表示 xj 与 S 集合中 聚类中心的距离之和． ( 3) 基于模糊聚类有效性指标迭代地优化聚类 结果． 当聚类数为 k 时，根据式( 1) 得到的模糊聚类 有效性指标 V( k) ． 如果满足| V( k) － V( k － 1) | ＞ ε( 这里 ε 是大于 0 的极小值) ，则令聚类数 k = k + 1，根据样 · 1651 ·