一种基于密度的模糊自适应聚类算法

第36卷第11期 北京科技大学学报 Vol.36 No.11 2014年11月 Journal of University of Science and Technology Beijing Now.2014 一种基于密度的模糊自适应聚类算法 王 玲12)四，吴璐璐12)，付冬梅 1)北京科技大学自动化学院，北京1000832)北京科技大学钢铁流程先进控制教育部重点实验室，北京100083 ☒通信作者，E-mail:linda gh@sina.com 摘要针对密度聚类算法对邻域参数设置敏感的问题，提出一种基于密度的模糊自适应聚类算法.算法在无需预先设置聚 类数以及邻域参数的情况下，可以自适应地根据样本间距离关系确定邻域半径得到样本密度，并根据样本密度逐渐增加聚类 中心.为了保障聚类结果的正确性，同时提出一种新的模糊聚类有效性指标以判断最佳聚类数，消除了密度聚类算法对参数 的敏感性.用UCI基准数据集进行实验，发现本文算法在对数据进行聚类时，聚类质量较原始密度聚类算法在准确性和自适 应性方面均有显著提高 关键词聚类算法：模糊聚类：自适应：密度 分类号TP18 A density-based fuzzy adaptive clustering algorithm WANG Ling),WU Lu-Hu2,FU Dong-mei2) 1)School of Automation and Electrical Engineering,University of Science and Technology Beijing,Beijing 100083,China 2)Key Laboratory of Advanced Control of Iron and Steel Process (Ministry of Education),Beijing 100083,China Corresponding author,E-mail:linda_gh@sina.com ABSTRACT In order to solve the problem that the density clustering algorithm is sensitive to neighborhood parameters,this article introduces a density-based fuzzy adaptive clustering algorithm.Without predefined clustering number and neighborhood parameters, this algorithm adaptively determines the radius of neighborhood to obtain the density of each sample and increases cluster centers based on the density.A new validity measure for fuzzy clustering is proposed to choose the best clustering number so that the sensitivity of density clustering is eliminated.UCI benchmark data sets are used to compare the proposed algorithm and the traditional density cluste- ring algorithm.Experiment results demonstrate that the proposed algorithm improves the clustering accuracy and the adaptability effec- tively. KEY WORDS clustering algorithms;fuzzy clustering:adaptive:density 在众多的聚类算法中，基于密度的聚类算法由 法-习是一种经典的基于密度的聚类算法，虽然该 于具有能够发现任意形状的聚类，可伸缩性好等优 算法可以获得任意形状的聚类簇，但是需要预先设 点，在许多领域有着重要的应用.然而，绝大部分密 置邻域半径Eps(Epsilon neighborhood)和邻域范围 度聚类算法对输入参数敏感而且无法保证最终聚类 内最少对象数min Pts(minimum number of points) 结果正确性，这些缺点在一定程度上限制了密度聚 这两个参数，而且该算法的聚类结果对参数值敏感 类算法的应用. 为了改进DBSCAN聚类算法，文献B-4]先假定 基于密度的聚类算法主要思想是根据数据样本 min Pts参数，然后再分别采用遗传算法和距离排序 的稠密程度产生聚类簇，其中DBSCAN(density- 来估计E即s.虽然该算法在一定程度上可以降低密 based spatial clustering of applications with noise) 度聚类算法对参数设置的敏感性，但是min Pts参数 收稿日期：201405-28 基金项目：中央高校基本科研业务费资助项目(FRF-SD-]2-OO9B);北京科技大学研究生教有发展基金资助项目 DOI:10.13374/j.issn1001-053x.2014.11.020:http://journals.ustb.edu.cn

第 36 卷 第 11 期 2014 年 11 月 北京科技大学学报 Journal of University of Science and Technology Beijing Vol． 36 No． 11 Nov． 2014 一种基于密度的模糊自适应聚类算法 王 玲1，2) ，吴璐璐1，2) ，付冬梅1，2) 1) 北京科技大学自动化学院，北京 100083 2) 北京科技大学钢铁流程先进控制教育部重点实验室，北京 100083  通信作者，E-mail: linda_gh@ sina． com 摘 要 针对密度聚类算法对邻域参数设置敏感的问题，提出一种基于密度的模糊自适应聚类算法． 算法在无需预先设置聚 类数以及邻域参数的情况下，可以自适应地根据样本间距离关系确定邻域半径得到样本密度，并根据样本密度逐渐增加聚类 中心． 为了保障聚类结果的正确性，同时提出一种新的模糊聚类有效性指标以判断最佳聚类数，消除了密度聚类算法对参数 的敏感性． 用 UCI 基准数据集进行实验，发现本文算法在对数据进行聚类时，聚类质量较原始密度聚类算法在准确性和自适 应性方面均有显著提高． 关键词 聚类算法; 模糊聚类; 自适应; 密度 分类号 TP 18 A density-based fuzzy adaptive clustering algorithm WANG Ling1，2)  ，WU Lu-lu1，2) ，FU Dong-mei1，2) 1) School of Automation and Electrical Engineering，University of Science and Technology Beijing，Beijing 100083，China 2) Key Laboratory of Advanced Control of Iron and Steel Process ( Ministry of Education) ，Beijing 100083，China  Corresponding author，E-mail: linda_gh@ sina． com ABSTＲACT In order to solve the problem that the density clustering algorithm is sensitive to neighborhood parameters，this article introduces a density-based fuzzy adaptive clustering algorithm． Without predefined clustering number and neighborhood parameters， this algorithm adaptively determines the radius of neighborhood to obtain the density of each sample and increases cluster centers based on the density． A new validity measure for fuzzy clustering is proposed to choose the best clustering number so that the sensitivity of density clustering is eliminated． UCI benchmark data sets are used to compare the proposed algorithm and the traditional density cluste￾ring algorithm． Experiment results demonstrate that the proposed algorithm improves the clustering accuracy and the adaptability effec￾tively． KEY WOＲDS clustering algorithms; fuzzy clustering; adaptive; density 收稿日期: 2014--05--28 基金项目: 中央高校基本科研业务费资助项目( FＲF--SD--12--009B) ; 北京科技大学研究生教育发展基金资助项目 DOI: 10． 13374 /j． issn1001--053x． 2014． 11． 020; http: / /journals． ustb． edu． cn 在众多的聚类算法中，基于密度的聚类算法由 于具有能够发现任意形状的聚类，可伸缩性好等优 点，在许多领域有着重要的应用． 然而，绝大部分密 度聚类算法对输入参数敏感而且无法保证最终聚类 结果正确性，这些缺点在一定程度上限制了密度聚 类算法的应用． 基于密度的聚类算法主要思想是根据数据样本 的稠密程度产生聚类簇，其 中 DBSCAN ( density￾based spatial clustering of applications with noise) 算 法［1 － 2］是一种经典的基于密度的聚类算法，虽然该 算法可以获得任意形状的聚类簇，但是需要预先设 置邻域半径 Eps ( Epsilon neighborhood) 和邻域范围 内最少对象数 min Pts ( minimum number of points) 这两个参数，而且该算法的聚类结果对参数值敏感． 为了改进 DBSCAN 聚类算法，文献［3 － 4］先假定 min Pts 参数，然后再分别采用遗传算法和距离排序 来估计 Eps． 虽然该算法在一定程度上可以降低密 度聚类算法对参数设置的敏感性，但是 min Pts 参数

第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 ·

·1562 北京科技大学学报 第36卷 本密度确定新的聚类中心.反之，找到当前所有聚 p0e=0,m=1,2,…ka (8) 类有效性指标的最大值，其所对应的聚类结果便作 h9a=u,m=l,2,…,kaj=1,2,…,n. 为当前的聚类 (9) 2基于密度的模糊自适应聚类算法 (8)根据下式(10)和式(6)分别更新聚类中心 和隶属度矩阵，并根据下式(11)计算0. 为了能够自适应地实现对各种数据的聚类，本 文提出的算法能够在未知聚类数的情况下保证聚类 ]2x 结果的有效性，而且无需预先定义任何参数，所以可 ,m=1,2,,kc ]2 以提高算法的自适应性.下面详细介绍基于密度的 k=1 模糊自适应聚类算法的步骤： (10) (1)按照最大值最小值归一化方法可对数据进 行归一化，具体公式如下所示： a9e×d(v9x)]2.(1l) xa-min(x,） max (x.)-min (. 其中t(t≥1)表示更新次数，9表示更新1次后得 (4) 到的第m个聚类中心u,”表示更新t-1次后： 其中max(x)和min(x,)表示数据集中第i维变量 对m类的隶属程度. 的最大值和最小值. (9)假设更新t次以后满足IJ0--)1E,则令k=k+1,算法返回(5)： 在众多密度聚类算法中DBSCAN算法是应用 否则转到(7) 最为广泛的一种算法，但是如果DBSCAN算法的邻 (7)根据下列式(7)~式(9)得到最佳聚类数 域半径Eps和邻域范围内最少对象数min Pts这两 ka,聚类中心0l(m=l,2,,k)以及隶属度 个参数设置不当就会导致算法无法得到正确的聚类 u0(m=1,2,…,kaj=1,2,…,n） 结果.表2给出了给定不同的两个参数时，DBSCAN kbest =m arg maxV",m=1,2,..,; (7) 算法的聚类结果.由此可以看出min Pts和Eps不

北 京 科 技 大 学 学 报 第 36 卷 本密度确定新的聚类中心． 反之，找到当前所有聚 类有效性指标的最大值，其所对应的聚类结果便作 为当前的聚类． 2 基于密度的模糊自适应聚类算法 为了能够自适应地实现对各种数据的聚类，本 文提出的算法能够在未知聚类数的情况下保证聚类 结果的有效性，而且无需预先定义任何参数，所以可 以提高算法的自适应性． 下面详细介绍基于密度的 模糊自适应聚类算法的步骤: ( 1) 按照最大值最小值归一化方法［9］对数据进 行归一化，具体公式如下所示: x'ji = xji － min( x． i ) max( x． i ) － min( x． i ) ． ( 4) 其中 max( x． i ) 和 min( x． i ) 表示数据集中第 i 维变量 的最大值和最小值． ( 2) 令聚类数 k = 1． 根据式( 2) 确定邻域半径 Eps，为接下来迭代搜索最佳的聚类数做准备工作． ( 3) 计算每个数据样本 xj ( j = 1，2，…，n) 在其 邻域半径范围内相邻数据样本个数 countj 作为其 密度: countj = num( xi ) ， subject to d( xj ，xi { ) ≤Eps． ( 5) 其中 num( xi ) 表示符合与 xj 距离小于或等于 Eps 的样本个数． ( 4) 如果此时聚类数 k = 1，找出密度最大的样 本作为第一个聚类中心 v( 0) 1 ，按照式( 6) 计算每个样 本对其隶属度 μ ( k) 1，j ( j = 1，2，…，n) ． 否则转到( 5) ． ( 5) 按照式( 3) 确定第 k 个聚类中心 v( 0) k ，并根 据式( 6) 确定每个样本对各个聚类的隶属度 μ ( k) m，j ( m = 1，2，…，k; j = 1，2，…，n) ［10］． μ ( k) m，j = 1 ∑ k h = [ 1 d( v( 0) m ，xj ) d( v( 0) h ，xj ] ) 2 ． ( 6) 其中 μ ( k) m，j 表示在聚类数为 k 时 xj 对第 m 个聚类的 隶属程度． ( 6) 按照式( 1) 计算此时的聚类有效性指标 V( k) ． 判断是否需要继续对聚类数进行迭代，如果满 足| V( k) － V( k － 1) | ＞ ε，则令 k = k + 1，算法返回( 5) ; 否则转到( 7) ． ( 7) 根据下列式( 7) ～ 式( 9) 得到最佳聚类数 kbest，聚类中心 v( 0) m，best ( m = 1，2，…，kbest ) 以及隶属度 μ ( 0) m，j，best ( m = 1，2，…，kbest ; j = 1，2，…，n) ． kbest = m = arg maxVm，m = 1，2，…，k; ( 7) v( 0) m，best = v( 0) m ，m = 1，2，…，kbest ; ( 8) μ ( 0) m，j，best = μ ( kbest) m，j ，m = 1，2，…，kbest，j = 1，2，…，n． ( 9) ( 8) 根据下式( 10) 和式( 6) 分别更新聚类中心 和隶属度矩阵，并根据下式( 11) 计算 J( t) ． v( t) m，best = ∑ n k = 1 ［μ ( t －1) m，j，best］2 xj ∑ n k = 1 ［μ ( t －1) m，j，best］2 ，m = 1，2，…，kbest ． ( 10) J( t) = ∑ kbest m = 1 ∑ n j = 1 ［μ ( t) m，j，best × d( v( t) m，best，xj ) ］2 ． ( 11) 其中 t( t≥1) 表示更新次数，v( t) m，best表示更新 t 次后得 到的第 m 个聚类中心，μ ( t － 1) m，j，best表示更新 t － 1 次后 xj 对 m 类的隶属程度． ( 9) 假设更新 t 次以后满足 | J( t) － J( t － 1) | ＜ ε， 则停止继续更新，此时得到更新 t 次后的最佳聚类 中心 v( t) m，best ( m = 1，2，…，kbest ) 和隶属度 μ ( t) m，j，best ( m = 1，2，…，kbest ; j = 1，2，…，n) ，然后按照样本对各个聚 类的隶属度划分样本聚类结果; 否则令 t = t + 1，返 回步骤( 8) ． 3 算法仿真和性能评估 为了验证本文提出的基于密度的模糊自适应聚 类算法的有效性，以 UCI 机器学习数据库中四个数 据集( Iris、Wine、Breast Cancer 和 Seed 数据集) 以及 两个人工数据集作为实验数据进行测试． 表 1 列出 了实验中使用的数据集． 表 1 实验数据 Table 1 Experiment dataset 数据集 样本数 聚类数 属性 Iris 150 3 4 Wine 178 3 13 Breast Cancer 683 2 9 Seed 210 3 7 Dataset_3_2 300 3 2 Dataset_5_2 250 5 2 3. 1 参数对 DBSCAN 算法的影响 在众多密度聚类算法中 DBSCAN 算法是应用 最为广泛的一种算法，但是如果 DBSCAN 算法的邻 域半径 Eps 和邻域范围内最少对象数 min Pts 这两 个参数设置不当就会导致算法无法得到正确的聚类 结果． 表 2 给出了给定不同的两个参数时，DBSCAN 算法的聚类结果． 由此可以看出 min Pts 和 Eps 不 · 2651 ·

第11期 王玲等：一种基于密度的模糊自适应聚类算法 ·1563· 同时，DBSCAN算法得到的聚类结果也不相同.例 Accuracy的计算公式如下所示： 如Iis数据集，当min Pts为l0,Eps为0.1时得到 k 的聚类数为5；min Pts为l0,Eps为0.4时得到的聚 am Accuracy =】 (12) 类数为7：min Pts为l0,Eps为0.8时才能得到正确 n 的聚类数.对于其他数据集也有类似的结论，即稍 式中a.表示第m个聚类簇中算法聚类结果和实际 微改动DBSCAN的任意一个参数都会导致聚类结 聚类相一致的样本个数 果发生变化.而且对于不同的数据集，DBSCAN算 从表3中可以看出DFAC算法聚类正确率要高 法的参数取值范围也是不同的，这就导致在未知聚 于FCM和DBSCAN算法，而且DFAC算法能够自适 类数的情况下很难确定参数的取值.例如，对于Is 应地得到每个数据集正确的聚类数.其中对于 数据集min Pts的取值范围是D,l0],Eps的取值范 Wine、Seed和Breast Cancer数据集，DFAC算法聚类 围是D.1,l]:Wime数据集min Pts取值范围是l, 正确率均不低于90%，对Dataset_.3_2和Dataset_5_2 10],Eps的取值范围是0,20]：Seed数据集min 的聚类正确率均为100%，虽然DFAC算法对Iis Pts的取值范围是1,20]，Eps取值范围是D,2],这 的聚类正确率稍低，但仍然高于DBSCAN和FCM 就增加了参数取值的难度.DFAC算法则无需设定 算法 任何参数，而且根据模糊聚类有效性指标可以确定 表3DFAC和DBSCAN算法对各个数据集聚类的平均正确率 最佳的聚类结果，所以DFAC算法具有更好的自适 Table 3 Average accuracy of DFAC and DBSCAN algorithms to each 应性. dataset % 表2 数据集 参数对DBSCAN算法的影响 算法 Breast Table 2 Influence of parameters on DBSCAN algorithm Iris Wine Seed Dataset 3 2 Dataset 5_2 Cancer 数据集 min Pts Eps 聚类数 DBSCAN67.372.366.748.8 66.7 45.7 10 0.1 5 FCM 87.159.090.094.7 91.3 90.5 Iris 10 0.4 4 DFAC89.394.991.095.6 100 100 10 0.8 3 10 10 5 图1和图2分别给出DFAC算法对Dataset_3_2 Wine 10 14 2 和Dataset_.5_2的聚类效果.对各个聚类中的数据 10 20 3 样本分别用不同颜色进行标记，可以清晰地看到 20 1 4 DFAC算法对这两个二维数据集的聚类结果与原始 Seed 20 1.6 2 数据集的聚类完全吻合.图1中每个圆圈表示一个 20 1.5 3 数据样本.从图中每个数据样本的分布位置可以明 20 0.1 6 确地判断该数据集一共有3个聚类簇.图中黄色、 Breast Cancer 20 0.5 5 绿色和紫色点分别表示聚类结果中第一、第二和第 20 1 2 三个聚类簇的样本.可以看出本属于同一个聚类簇 20 0.1 的每个样本聚类结果均正确.图2也可得到类似的 Dataset_3_2 20 0.3 2 结论，黄色、绿色、紫色、黑色和蓝色共形成了5个聚 20 1 类，同样保证了样本聚类结果的正确性. 10 0.1 22 为了进一步验证DFAC对多类数据集的聚类有 Dataset_5_2 10 0.5 效性，这里使用如图3所示的一个二维数据集作为 10 1 5 验证数据集，图中每个黄色点代表一个数据样本. 从图中可以看出该数据集共有20个聚类簇.在选 3.2聚类效果测试 择聚类中心时，根据式(1)得到的不同聚类数对应 为了验证DFAC算法的聚类有效性，在多个数 的模糊聚类有效性指标值如图4所示.从图中可以 据集上进行聚类效果测试并与DBSCAN和FCM 看出当聚类数小于5时，模糊聚类有效性指标上升 (fuzzy c-means),算法的聚类效果进行对比.表3中 趋势明显，当聚类数在5~20之间时糊聚类有效性 给出了DFAC、FCM和DBSCAN算法对各个数据集 指标上升趋势缓慢，聚类数大于20以后模糊聚类有 进行多次聚类的平均正确率.其中算法聚类正确率 效性指标逐渐下降且趋于平稳，因此得到聚类数为

第 11 期 王 玲等: 一种基于密度的模糊自适应聚类算法 同时，DBSCAN 算法得到的聚类结果也不相同． 例 如 Iris 数据集，当 min Pts 为 10，Eps 为 0. 1 时得到 的聚类数为 5; min Pts 为 10，Eps 为 0. 4 时得到的聚 类数为 7; min Pts 为 10，Eps 为 0. 8 时才能得到正确 的聚类数． 对于其他数据集也有类似的结论，即稍 微改动 DBSCAN 的任意一个参数都会导致聚类结 果发生变化． 而且对于不同的数据集，DBSCAN 算 法的参数取值范围也是不同的，这就导致在未知聚 类数的情况下很难确定参数的取值． 例如，对于 Iris 数据集 min Pts 的取值范围是［1，10］，Eps 的取值范 围是［0. 1，1］; Wine 数据集 min Pts 取值范围是［1， 10］，Eps 的取值范围是［10，20］; Seed 数据集 min Pts 的取值范围是［1，20］，Eps 取值范围是［1，2］，这 就增加了参数取值的难度． DFAC 算法则无需设定 任何参数，而且根据模糊聚类有效性指标可以确定 最佳的聚类结果，所以 DFAC 算法具有更好的自适 应性． 表 2 参数对 DBSCAN 算法的影响 Table 2 Influence of parameters on DBSCAN algorithm 数据集 min Pts Eps 聚类数 10 0. 1 5 Iris 10 0. 4 4 10 0. 8 3 10 10 5 Wine 10 14 2 10 20 3 20 1 4 Seed 20 1. 6 2 20 1. 5 3 20 0. 1 6 Breast Cancer 20 0. 5 5 20 1 2 20 0. 1 1 Dataset_3_2 20 0. 3 2 20 1 3 10 0. 1 22 Dataset_5_2 10 0. 5 7 10 1 5 3. 2 聚类效果测试 为了验证 DFAC 算法的聚类有效性，在多个数 据集上进行聚类效果测试并与 DBSCAN 和 FCM ( fuzzy c-means) 算法的聚类效果进行对比． 表 3 中 给出了 DFAC、FCM 和 DBSCAN 算法对各个数据集 进行多次聚类的平均正确率． 其中算法聚类正确率 Accuracy［11］的计算公式如下所示: Accuracy = ∑ k m = 1 am n ． ( 12) 式中 am 表示第 m 个聚类簇中算法聚类结果和实际 聚类相一致的样本个数． 从表 3 中可以看出 DFAC 算法聚类正确率要高 于 FCM 和 DBSCAN 算法，而且 DFAC 算法能够自适 应地得到每个数据集正确的聚类数． 其 中 对 于 Wine、Seed 和 Breast Cancer 数据集，DFAC 算法聚类 正确率均不低于 90%，对 Dataset_3_2 和 Dataset_5_2 的聚类正确率均为 100% ，虽然 DFAC 算法对 Iris 的聚类正确率稍低，但仍然高于 DBSCAN 和 FCM 算法． 表 3 DFAC 和 DBSCAN 算法对各个数据集聚类的平均正确率 Table 3 Average accuracy of DFAC and DBSCAN algorithms to each dataset % 算法 数据集 Iris Wine Seed Breast Cancer Dataset_3_2 Dataset_5_2 DBSCAN 67. 3 72. 3 66. 7 48. 8 66. 7 45. 7 FCM 87. 1 59. 0 90. 0 94. 7 91. 3 90. 5 DFAC 89. 3 94. 9 91. 0 95. 6 100 100 图 1 和图 2 分别给出 DFAC 算法对 Dataset_3_2 和 Dataset_5_2 的聚类效果． 对各个聚类中的数据 样本分别用不同颜色进行标记，可以清晰地看到 DFAC 算法对这两个二维数据集的聚类结果与原始 数据集的聚类完全吻合． 图 1 中每个圆圈表示一个 数据样本． 从图中每个数据样本的分布位置可以明 确地判断该数据集一共有 3 个聚类簇． 图中黄色、 绿色和紫色点分别表示聚类结果中第一、第二和第 三个聚类簇的样本． 可以看出本属于同一个聚类簇 的每个样本聚类结果均正确． 图 2 也可得到类似的 结论，黄色、绿色、紫色、黑色和蓝色共形成了 5 个聚 类，同样保证了样本聚类结果的正确性． 为了进一步验证 DFAC 对多类数据集的聚类有 效性，这里使用如图 3 所示的一个二维数据集作为 验证数据集，图中每个黄色点代表一个数据样本． 从图中可以看出该数据集共有 20 个聚类簇． 在选 择聚类中心时，根据式( 1) 得到的不同聚类数对应 的模糊聚类有效性指标值如图 4 所示． 从图中可以 看出当聚类数小于 5 时，模糊聚类有效性指标上升 趋势明显，当聚类数在 5 ～ 20 之间时糊聚类有效性 指标上升趋势缓慢，聚类数大于 20 以后模糊聚类有 效性指标逐渐下降且趋于平稳，因此得到聚类数为 · 3651 ·

·1564· 北京科技大学学报 第36卷 3.0 。原始数据 聚类1 2.5 十聚类2 ×聚类3 2.0 1.5 1.0 05 10 1520253035 聚类数 图1 Dataset_32聚类结果 图4模糊聚类有效性指标折线图 Fig.1 DFAC clustering results of Dataset_3_2 Fig.4 Broken line graph of fuzzy clustering validity index ○原始数据 3.3效率测试 聚类1 为了验证算法的执行效率，图5给出DBSCAN 聚类2 5 ×聚类3 和DFAC算法对各个数据集进行聚类得到最佳聚类 聚类4 聚类5 结果所需要时间的柱状图.从图中可以看出，除 Breast Cancer数据集以外，DFAC算法对其余数据集 10 的运行时间均少于DBSCAN算法.其中DFAC算法 对ris、Wine、Seed、Breast Cancer、Dataset_3_2及 Dataset5_2数据集的运行时间分别为0.45、0.99、 0.90、10.79、1.37及2.74s.对比Iis和Wine这两 个数据集，它们的聚类数均为3且样本数相似，但 10 12 Wine数据维数远多于is,因此DFAC对Wine数据 图2 Dataset_52聚类结果 集的运行时间多于Iris.对比Wine和Seed数据集 Fig.2 DFAC clustering results of Dataset_5_2 可知，Wine数据集的样本数少于Seed数据集，但 20.图3中红色星状点表示根据式(3)得到的聚类 Wine数据维度大于Seed数据集，且二者聚类数相 中心.从图中可以看出算法选择的20个聚类中心 等，因此DFAC算法对这两个数据集的运行时间相 仅有2个聚类中心有误，由此可知基于自适应邻域 近.Dataset_32和Dataset_.5_2这两个数据集的样 半径计算样本密度选出的聚类中心的正确率较高. 本数以及维数都相近，但后者的聚类数多于前者，导 最终通过对聚类中心进一步更新，DFAC算法对此 致在搜索最佳聚类数时后者的运行时间多于前者. 数据集的聚类正确率为100%，也说明了DFAC算 Breast Cancer数据集的样本数最多且数据维度也较 法对聚类数较多数据集的有效性. 大，因此在众多数据集中运行时间最长.由此可以 得出数据集的数据量（其中包括样本数和数据维 原始数据来初始聚类中心 度)和聚类数都会影响DFAC算法的运行时间. 12 10 10 ODFAC 米 ▣DBSCAN 6 2 米 Can 32 5 10 15 Bre 数据集 图3多聚类数据集聚类中心的选择 图5算法运行时间对比 Fig.3 Initial cluster centers of a multi-cluster dataset Fig.5 Comparison of run time

北 京 科 技 大 学 学 报 第 36 卷 图 1 Dataset_3_2 聚类结果 Fig． 1 DFAC clustering results of Dataset_3_2 图 2 Dataset_5_2 聚类结果 Fig． 2 DFAC clustering results of Dataset_5_2 20． 图 3 中红色星状点表示根据式( 3) 得到的聚类 中心． 从图中可以看出算法选择的 20 个聚类中心 仅有 2 个聚类中心有误，由此可知基于自适应邻域 半径计算样本密度选出的聚类中心的正确率较高． 最终通过对聚类中心进一步更新，DFAC 算法对此 数据集的聚类正确率为 100% ，也说明了 DFAC 算 法对聚类数较多数据集的有效性． 图 3 多聚类数据集聚类中心的选择 Fig． 3 Initial cluster centers of a multi-cluster dataset 图 4 模糊聚类有效性指标折线图 Fig． 4 Broken line graph of fuzzy clustering validity index 3. 3 效率测试 为了验证算法的执行效率，图 5 给出 DBSCAN 和 DFAC 算法对各个数据集进行聚类得到最佳聚类 结果所需要时间的柱状图． 从图中可以看出，除 Breast Cancer 数据集以外，DFAC 算法对其余数据集 的运行时间均少于 DBSCAN 算法． 其中 DFAC 算法 对 Iris、Wine、Seed、Breast Cancer、Dataset _ 3 _ 2 及 Dataset_5_2 数据集的运行时间分别为 0. 45、0. 99、 0. 90、10. 79、1. 37 及 2. 74 s． 对比 Iris 和 Wine 这两 个数据集，它们的聚类数均为 3 且样本数相似，但 Wine 数据维数远多于 Iris，因此 DFAC 对 Wine 数据 图 5 算法运行时间对比 Fig． 5 Comparison of run time 集的运行时间多于 Iris． 对比 Wine 和 Seed 数据集 可知，Wine 数据集的样本数少于 Seed 数据集，但 Wine 数据维度大于 Seed 数据集，且二者聚类数相 等，因此 DFAC 算法对这两个数据集的运行时间相 近． Dataset_3_2 和 Dataset_5 _2 这两个数据集的样 本数以及维数都相近，但后者的聚类数多于前者，导 致在搜索最佳聚类数时后者的运行时间多于前者． Breast Cancer 数据集的样本数最多且数据维度也较 大，因此在众多数据集中运行时间最长． 由此可以 得出数据集的数据量( 其中包括样本数和数据维 度) 和聚类数都会影响 DFAC 算法的运行时间． · 4651 ·

第11期 王玲等：一种基于密度的模糊自适应聚类算法 ·1565· [4]Shi H Y,Ping L,Ji D G,et al.A statistical information-based 4结论 clustering approach in distance space.I Zhejiang Unir Sci A, 2005,6(1):71 DFAC算法通过自适应地确定邻域半径得到每 [5]Zhao W,Xia G S,Gou Z J,et al.An Improved DBSCAN Algo- 个样本的密度，并基于样本密度逐渐增加聚类中心， rithm.J Sichuan Norm Unin Nat Sci,2013(2):312 同时为了保证聚类结果的有效性提出一种新的模糊 (赵文，夏桂书，苟智坚，等.一种改进的DBSCAN算法.四 聚类有效性指标以判断聚类数为何值时聚类效果最 川师范大学学报：自然科学版，2013(2)：312) 佳.最终对聚类中心的更新进一步改善了算法的聚 6 Xia L N,Jing J W.SA-DBSCAN:a self-adaptive densitybased 类正确率.真实数据实验结果表明，DFAC算法无需 clustering algorithm.J Grad Sch Chin Acad Sci,2009,26(4): 530 预先定义聚类邻域参数，在未知聚类数的情况下，根 (夏鲁宁，荆继武.SA-DBSCAN:一种自适应基于密度聚类 据新的模糊聚类指标可以确定最佳聚类数，因此极 算法.中国科学院研究生院学报，2009,26(4)：530) 大提高了算法的自适应性，而且DFAC算法的准确 7]Huang M,Bian F.A grid and density based fast spatial clustering 性和效率较DBSCAN算法有显著的提高. algorithm /AICl'09 International Conference on Artificial Intelli- gence and Computational Intelligence.IEEE,2009:260 参考文献 8] Wang W,Li D Z,Vrbanek J.An evolving neuro-fuzzy technique [Ertoz L,Steinbach M,Kumar V.Finding clusters of different si- for system state forecasting.Neurocomputing,2012,87:111 zes,shapes,and densities in noisy high dimensional data//Siam Bai L.Theoretical Analysis and Effective Algorithms of Cluste Proceedings Series,2003:47 Learning [Dissertation].Taiyuan:Shanxi University,2012 Ester M,Kriegel H P,Sander J,et al.A density-based algorithm (白亮.聚类学习的理论分析与高效算法研究[学位论文」 for discovering clusters in large spatial databases with noise / 太原：山西大学，2012) Proceedings of the 2nd International Conference on Knowledge Dis- [10]Bezdek JC.Ehrlich R.Full W.FCM:the fuzzy c-means cluste- covery and Data Mining.Portland,1996:226 ring algorithm.Comput Geosci,1984,10(2):191 Lin C Y,Chang CC,Lin CC.A new density-based scheme for [11]Sun Y,Zhu Q M,Chen Z X.An iterative initial-points refine- clustering based on genetic algorithm.Fundam Inf,2005,68 ment algorithm for categorical data clustering.Pattern Recognit (4):315 Lt,2002,23(7):875

第 11 期 王 玲等: 一种基于密度的模糊自适应聚类算法 4 结论 DFAC 算法通过自适应地确定邻域半径得到每 个样本的密度，并基于样本密度逐渐增加聚类中心， 同时为了保证聚类结果的有效性提出一种新的模糊 聚类有效性指标以判断聚类数为何值时聚类效果最 佳． 最终对聚类中心的更新进一步改善了算法的聚 类正确率． 真实数据实验结果表明，DFAC 算法无需 预先定义聚类邻域参数，在未知聚类数的情况下，根 据新的模糊聚类指标可以确定最佳聚类数，因此极 大提高了算法的自适应性，而且 DFAC 算法的准确 性和效率较 DBSCAN 算法有显著的提高． 参 考 文 献 ［1］ Ertz L，Steinbach M，Kumar V． Finding clusters of different si￾zes，shapes，and densities in noisy high dimensional data / / Siam Proceedings Series，2003: 47 ［2］ Ester M，Kriegel H P，Sander J，et al． A density-based algorithm for discovering clusters in large spatial databases with noise / / Proceedings of the 2nd International Conference on Knowledge Dis￾covery and Data Mining． Portland，1996: 226 ［3］ Lin C Y，Chang C C，Lin C C． A new density-based scheme for clustering based on genetic algorithm． Fundam Inf，2005，68 ( 4) : 315 ［4］ Shi H Y，Ping L，Ji D G，et al． A statistical information-based clustering approach in distance space． J Zhejiang Univ Sci A， 2005，6( 1) : 71 ［5］ Zhao W，Xia G S，Gou Z J，et al． An Improved DBSCAN Algo￾rithm． J Sichuan Norm Univ Nat Sci，2013( 2) : 312 ( 赵文，夏桂书，苟智坚，等． 一种改进的 DBSCAN 算法． 四 川师范大学学报: 自然科学版，2013( 2) : 312) ［6］ Xia L N，Jing J W． SA-DBSCAN: a self-adaptive density-based clustering algorithm． J Grad Sch Chin Acad Sci，2009，26 ( 4) : 530 ( 夏鲁宁，荆继武． SA--DBSCAN: 一种自适应基于密度聚类 算法． 中国科学院研究生院学报，2009，26( 4) : 530) ［7］ Huang M，Bian F． A grid and density based fast spatial clustering algorithm / / AICI’09 International Conference on Artificial Intelli￾gence and Computational Intelligence． IEEE，2009: 260 ［8］ Wang W，Li D Z，Vrbanek J． An evolving neuro-fuzzy technique for system state forecasting． Neurocomputing，2012，87: 111 ［9］ Bai L． Theoretical Analysis and Effective Algorithms of Cluster Learning ［Dissertation〗． Taiyuan: Shanxi University，2012 ( 白亮． 聚类学习的理论分析与高效算法研究［学位论文〗． 太原: 山西大学，2012) ［10］ Bezdek J C，Ehrlich Ｒ，Full W． FCM: the fuzzy c-means cluste￾ring algorithm． Comput Geosci，1984，10( 2) : 191 ［11］ Sun Y，Zhu Q M，Chen Z X． An iterative initial-points refine￾ment algorithm for categorical data clustering． Pattern Ｒecognit Lett，2002，23( 7) : 875 · 5651 ·