·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--)1<6, (2)令聚类数k=1.根据式(2)确定邻域半径 则停止继续更新，此时得到更新t次后的最佳聚类 Eps,为接下来迭代搜索最佳的聚类数做准备工作. 中心v0(m=l,2,…,k)和隶属度(m= (3)计算每个数据样本x=1,2,…,n)在其 1,2,…,kmj=1,2,…,n),然后按照样本对各个聚 邻域半径范围内相邻数据样本个数count,作为其 类的隶属度划分样本聚类结果；否则令1=t+1,返 密度： 回步骤(8). [count;=num (x;), (5) 3算法仿真和性能评估 subject to d(x,x)Eps. 其中num(x:)表示符合与x:距离小于或等于Eps 为了验证本文提出的基于密度的模糊自适应聚 的样本个数. 类算法的有效性，以UCI机器学习数据库中四个数 (4)如果此时聚类数k=1,找出密度最大的样 据集(Iris、Wine、Breast Cancer和Seed数据集)以及 本作为第一个聚类中心，按照式(6)计算每个样 两个人工数据集作为实验数据进行测试.表1列出 本对其隶属度u(=1,2,,n).否则转到(5) 了实验中使用的数据集 (5)按照式(3)确定第k个聚类中心o,并根 表1实验数据 据式(6)确定每个样本对各个聚类的隶属度u周(m Table 1 Experiment dataset =1,2,…,kj=1,2,…,n)0a 数据集 样本数 聚类数 属性 Iris 150 3 4 h= 1 (6) d(v,x) Wine 178 13 三1 d(vo,x） Breast Cancer 683 2 9 其中u表示在聚类数为k时x,对第m个聚类的 Seed 210 3 7 隶属程度 Dataset_3_2 300 3 2 (6)按照式(1)计算此时的聚类有效性指标 Dataset_5_2 250 V因.判断是否需要继续对聚类数进行迭代，如果满 3.1参数对DBSCAN算法的影响 足IV因-V-”1>E,则令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 ·