聚类是一种常用的属于无监督学习的数据处理方法, 由聚类所挖掘出的信息可以为进一步深入地分析数据提供理论基础^[1]. 聚类采用定量数学思想, 按照数据间的相似程度将其归到几个群, 其结果满足各个群内相似性较强, 而各群体之间相似性较小的特点. 同一组样本有时会因为不同的目的、数据输入方式、所选的分群特征或数据属性, 形成不同的分群结果. 聚类是数据挖掘的重要手段^[2], 聚类算法分为: 划分聚类、层次聚类、密度聚类、网格聚类、图论聚类等^[3].

快速峰值算法是2014年6月Rodriguez Alex在Science上提出的一种新型聚类算法, 该算法能自动选出样本的类中心, 而且能克服一般方法对数据要求的缺陷, 可以实现对非球形数据进行高效聚类^[4]. 该算法选定聚类中心: 1)较大的局部密度, 即中心点相邻点的密度值均小于该点; 2)与其他密度更高的点之间的“距离”较大. DPC算法原理简单、聚类高效^[5], 在各个领域都有广泛的应用^{[6, 7]}, 例如应用于高速公路收费数据分析^[8]及异常事件挖掘^[9]等. 然而, 通过聚类算法的评价^[10], DPC算法的缺点也十分明显, 需要根据经验值设定参数截断距离; 需要根据计算出的局部密度以及距离两个值生成用于选择聚类中心的决策图, 并人为在其中选取这两个值都较大的点为聚类中心. 这种选择存在较高的主观性与不稳定性, 严重影响后续非中心点的分配、优化以及噪声点的发现^[11].

现今为止, 已有多种改进的DPC算法, 例如: K近邻密度峰值聚类^[12-14], 结合K近邻的概念重新定义截断距离和局部密度的度量方法, 避免截止距离的人为设置; 基于果蝇算法的密度峰值聚类^[15-17], 利用果蝇优化算法得到最优截止距离, 进而完成对局部密度和与密度更高的点的距离的计算; 布谷鸟优化的密度峰值快速搜索聚类算法^[18], 利用布谷鸟优化截止距离, 引入余弦相似度原理, 将方向与实际距离相结合, 能够更好的划分边界区域内的数据点; 除此之外, 还有热扩散密度峰值聚类^[19]、自适应聚合策略优化的密度峰值聚类算法^[20]等等. 但是现有的改进算法仍有改进的余地.

果蝇优化算法(Fruit fly Optimization Algorithm, FOA)是一种新的群体智能方法^{[21, 22]}, 通过迭代搜索寻找最优解. 与此同时, 已有诸多学者致力于改进FOA算法, 例如新型改进果蝇优化算法^[23]、改进的变步长果蝇优化算法^[24]、改进步长与策略的果蝇优化算法^[25]等. 但是果蝇优化算法还存在许多不足.

本文引入改进的自调节步长果蝇优化算法^[26], 该算法根据当前浓度差值变化率, 对步长进行相应调整, 用过迭代计算, 得到最佳截止距离. 本文以更高的效率与准确率的得到这一关键参数, 并计算密度与距离的乘积, 根据乘积值自适应的选出备选聚类中心, 再从备选聚类中心中, 以同一类仅有一个中心为原则选出真正的聚类中心, 然后对其他非中心数据点进行分配, 最后通过类的边缘区域对聚类结果进行优化.

1 算法原理 1.1 密度峰值聚类算法

DPC算法主要分3个步骤进行: 计算距离矩阵、选取聚类中心、剩余点的分配及优化.

1.1.1 计算距离矩阵

密度峰值算法的输入为待处理数据点的距离矩阵, 即每个点之间相似性. 在进行距离计算之前, 首先将原始数据的不同字段进行标准化处理, 使各维度的数据具有相同的量级; 然后计算数据间的距离, 最后输出距离矩阵. 本文选取欧几里得方式来计算距离 $d({x_i},{x_j})$ , 并输出为若干行、三列的矩阵, 其中前两列表示两个数据点的序号, 第三列为前两列表示的两个数据点之间的距离, 例如矩阵的第1行为: 1号数据、2号数据、1号2号数据间的距离, 第2行为: 1号数据、3号数据、1号3号数据间的距离, 以此类推, 与此距离矩阵即为快速峰值算法的输入.

1.1.2 聚类中心的选择

聚类中心的特征是局部密度大而且与其它密度更大的点相距很远.

某点的局部密度 ${\rho _i}$ 是以截止距离为半径的圆内的点的个数:

${\rho _i} = \sum\nolimits_j {\chi \left( {{d_{ij}} - {d_c}} \right)} $

(1)

式中, $i$ 与 $j$ 为两个互异的数据点, 当a小于0时, $\chi \left( a \right) = 1$ , 反之 $\chi \left( a \right) = 0$ . ${d_{ij}}$ 为 $i$ 点与 $j$ 点之间的距离, ${d_c}$ 为截止距离, 由用户根据经验值设定. 一般而言 ${d_c}$ 的选取原则为: 将距离 ${\delta _i}$ 按递增方式进行排序并编号, 找出所有距离个数的1%~2%所对应的序号, 将 ${d_c}$ 设置为该序号对应的距离值.

某一数据的 ${\delta _i}$ 值被定义为:

${\delta _i} = \mathop {\min }\limits_{j:{\rho _j} > {\rho _i}} \left( {{d_{ij}}} \right)$

(2)

对于密度最高的点, 由于不存在更高点, 故将其 ${\delta _i}$ 值定义为该点与其余所有的数据之间距离的最大值.

${\delta _i} = {\max _j}\left( {{d_{ij}}} \right)$

(3)

计算出各点的这两个量之后, 将所有的数据点以 $\rho $ 和 $\delta $ 作为两个维度进行可视化输出, 所输出的图形称为决策图.

1.1.3 非聚类中心点的分配及优化

在找到聚类中心之后, 确定类的数量, 然后合理分配剩余点. 分配原则是: 每个剩余点逐个被分到与其距离最近的有较高密度的点所在的类簇, 且此操作以单步执行, 直到把所有的点全部分配到对应的类为止.

一般的聚类方法优化都是以使目标函数在每一次的迭代中达到最优为原则而实现的. 本文提出的算法中优化的方法为: 先为每个类划分一个边界区域, 边界区域的定义是分配给某一类簇的点距离另一类簇的点的距离小于截止距离 ${d_c}$ ; 接着在每个边界区域内找出密度最高的点并标记其密度为 ${\rho _b}$ , 遍历类内的各个点, 密度大于 ${\rho _b}$ 的点被分到类内, 反之被标记为噪声.

1.2 自调节步长果蝇优化算法 1.2.1 果蝇优化算法

FOA模仿果蝇搜寻食物源, 果蝇通过嗅觉可以轻易的捕捉到范围内目标源散发的气味, 然后利用其视觉进行追踪, 不断的更新果蝇群位置, 逐渐靠近目标源. 算法的主要步骤如下:

1)初始化种群:

果蝇数量为 ${S_{{\rm{ize\_num}}}}$ 和算法所需循环执行总次数 ${M_{{\rm{ax\_times}}}}$ . 在确定活动区域中随机给定果蝇群体一个起点 ${S_{{\rm{tart}}\_X}}$ , ${S_{{\rm{tart}}\_Y}}$ .

2)给每个果蝇个体随机的方向与距离, 用嗅觉寻找食物:

${X_i} = {S_{{\rm{tart}}\_X}} + {R_{{\rm{andom\_Value}}}}$

(4)

${Y_i} = {S_{{\rm{tart}}\_Y}} + {R_{{\rm{andom\_Value}}}}$

(5)

3)计算果蝇到坐标原点的距离 ${D_i}$ 以及味道浓度判别值 ${S_i}$ :

${D_i} = {\left( {X_i^2 + Y_i^2} \right)^{0.5}}$

(6)

${S_i} = {1 / {{D_i}}}$

(7)

4)将浓度判别值 ${S_i}$ 带入判定函数 ${F_{{\rm{unction}}}}\left( {{S_i}} \right)$ 求出其 ${S_{{\rm{mell}}}}_{\_i}$ , 此处判定函数为使用果蝇优化算法对某一函数求解最优解时的判定函数, 根据实际被求解函数而定:

${S_{{\rm{mell\_}}i}} = {F_{{\rm{unction}}}}\left( {{S_i}} \right)$

(8)

5)找出群体中浓度最优的果蝇(本文以最小值为最优解):

$\left[ {{b_{{\rm{est}}}}\_{S_{{\rm{mell\_best}}}}\_{i_{{\rm{ndex}}}}} \right] = \min \left( {{S_{{\rm{mell}}}}} \right)$

(9)

6)保留最佳浓度值 ${S_{{\rm{mell\_best}}}}$ 与其坐标, 果蝇群体根据视觉飞往最优位置:

${S_{{\rm{mell\_best\_}}i}} = {b_{{\rm{est\_smell}}}}$

(10)

${S_{{\rm{tart\_}}X}} = X\left( {{b_{{\rm{est\_smell}}}}} \right)$

(11)

${S_{{\rm{tart\_}}Y}} = Y\left( {{b_{{\rm{est\_smell}}}}} \right)$

(12)

7)迭代寻优: 重复步骤2)、3)、4)、5), 判断: ${S_{{\rm{mell\_best\_}}i}} < {S_{{\rm{mell\_best\_}}{i - 1}}}$ , 如果上式取值为真, 则转到步骤6), 否则继续迭代进行优化.

1.2.2 自调节步长果蝇优化算法(SFO)

传统的FOA算法的搜索半径是固定不变的, 即每一代果蝇以固定步长随机在寻找食物. 在算法迭代开始时, 较大的步长有利于全局搜索寻优, 而且可以有效的跳出局部最优. 但是, 寻优后期, 较大的步长会导致较弱的局部搜索, 可能会错过最佳值, 同时收敛精度也会减小. 较小的步长虽然可以提升收敛度, 但是在迭代前期降低了寻优速率. 传统的FOA算法难以权衡全局搜索能力和局部探索能力, 自调节步长果蝇优化算法根据浓度差值变化率的大小对步长进行动态更改; 并且在改变步长过程中引入指数与三角函数机制, 使步长变化具有非均匀性和随机性. 在迭代初期为了加快全局搜索速率, 适当增加步长值, 迭代后期为了能让算法能对局部进行精细搜索, 适当减小步长值, 该算法针对原果蝇算法的全局寻优速率慢和局部收敛精度不高而做出了改良. 算法的主要改进步骤如下:

1)求出当前迭代果蝇群中的最优浓度 $\min $ $ \left( {{S_{{{\rm{mell}}\_}i}}} \right)$ 与最差浓度 $\max \left( {{S_{{{\rm{mell}}\_}i}}} \right)$ 之差, 前一代果蝇群中的最优浓度 $\min \left( {{S_{{\rm{mell\_}}{i - 1}}}} \right)$ 与最差浓度 $\max \left( {{S_{{{\rm{mell}}\_}{i - 1}}}} \right)$ 之差, 将差值作对比, 得出浓度差值变化率 $ {S_{\rm Rate}}$ :

${S_{\rm Rate}} = \frac{{\min \left( {{S_{{\rm{mell\_}}i}}} \right) - \max \left( {{S_{{\rm{mell\_}}i}}} \right)}}{{\min \left( {{S_{{\rm{mell\_}}{i - 1}}}} \right) - \max \left( {{S_{{\rm{mell\_}}{i - 1}}}} \right)}}$

(13)

本文将最小值设为最优值, 将最大值设为差值. 由图1可以看出果蝇寻优迭代前期的浓度差值变化率变化较大, 需要适当增加步长加快全局寻优, 而随着进入迭代后期, 浓度差值变化率变小, 逐渐趋近于1, 并稳定在0.7~1.3的范围内, 说明果蝇群体距离食物源已经非常靠近, 浓度波动较小, 这时需要减小步长, 以提升精确度.

2)步长改进: 根据 ${S_{\rm Rate}}$ 的取值范围, 对步长进行相应的修改:

如果 ${S_{\rm Rate}} \le 0.7$ 或者 ${S_{\rm Rate}} \ge 1.3$ :

${L_i} = {L_{i - 1}} - \left( {1 - \frac{{{t_{{\rm{imes\_}}i}}}}{{{M_{{\rm{axtimes}}}}}}} \right) \times {D_{{\rm{ynamic\_factor}}}} \times 0.7$

(14)

步长调节因子:

${D_{{\rm{ynamic\_factor}}}} = \exp \left( {{m_{{\rm{up}}}} \times {S_{\rm Rate}}} \right) \times \sin \left( {{\rm{rem}}\left( {{t_{{\rm{imes}}}}_{\_i},\pi } \right)} \right)$

(15)

如果 $ 0.7 < {S_{\rm Rate}} < 1.3$ :

${L_i} = {L_{i - 1}} - \left( {1 - \frac{{{t_{{\rm{imes\_}}i}}}}{{{M_{{\rm{axtimes}}}}}}} \right) \times {D_{{\rm{ynamic\_factor}}}} \times 1.3$

(16)

步长调节因子:

${D_{{\rm{ynamic\_factor}}}} = \exp \left( {{m_{{\rm{down}}}} \times {S_{\rm Rate}}} \right) \times \sin \left( {{\rm{rem}}\left( {{t_{{\rm{imes\_}}i}},\pi } \right)} \right)$

(17)

式中, ${L_i}$ 与 ${L_{i - 1}}$ 分别为当前果蝇寻优迭代步长和上一次果蝇寻优迭代步长; ${m_{{\rm{up}}}}$ 和 ${m_{{\rm{down}}}}$ 分别在不同所属浓度差值变化率时所采用的步长动态变化参数, 需要增大步长时采用 ${m_{{\rm{up}}}}$ (取值大于1, 本文取1.3), 需要减小步长时采用 ${m_{{\rm{down}}}}$ (取值为(0,1), 本文取0.7); ${t_{{\rm{imes\_}}i}}$ 为当前执行算法所处的运行次数; ${M_{{\rm{axtimes}}}}$ 为算法所需循环执行次数的最大值. 根据每次求的浓度差值变化率 ${S_{\rm Rate}}$ , 确定其所属范围, 对步长进行相应的修改.

图2为步长调节因子在取值连续的情况下所显示的结果. 指数机制可以使步长变化具有非均匀性, 在果蝇寻优迭代过程中, 如果浓度变化较大, 那么要适当增加步长, 非均匀变化的步长相对于原果蝇算法中的固定步长更容易捕捉到最优值, 有利于全局搜索.

3)果蝇个体位置计算:

${X_i} = {S_{{\rm{tart}}\_X}} + {L_i} \times {X_{i - 1}} \times {R_{{\rm{andom\_Value}}}}$

(18)

${Y_i} = {S_{{\rm{tart}}\_Y}} + {L_i} \times {Y_{i - 1}} \times {R_{{\rm{andom}}\_{\rm{Value}}}}$

(19)

当浓度差值变化率较小时, 浓度变化率比较稳定, 这时候果蝇迭代寻优可能进入两种状态, 第一种状态是进入迭代后期, 要适当的减小步长进行局部探索, 第二种状态是果蝇寻优迭代陷入局部最优化, 那么引入三角函数机制是利用三角函数变化的特性, 使得步长变化随机, 提高了算法跳出局部极值的能力.

在同样设置种群规模为20, 最大迭代次数为1000时, 对比FOA和SFO的测试性能, 采用平均值代表平均精度值, 方差代表测试稳定性. 对于不同的测试函数, FOA在多数猜测是函数下未能达到理想精度, 容易陷入局部最佳, SFO算法均达到了目标精度, 且方差相对较小, 证明本文算法具有更好的稳定性和优越性.

1.3 基于自调节步长果蝇优化的自适应密度峰值聚类算法 1.3.1 信息熵

信息熵为系统不稳定性的度量. 已知空间中的数据集 $D = \left\{ {{x_1},{x_2}, \cdots ,{x_n}} \right\}$ 包含n个数据, 每个数据的密度函数值为:

${\varphi _i} = \sum\limits_{j = 1}^n {{e^{{{\left( {\frac{{\left\| {{x_i} - {x_j}} \right\|}}{\sigma }} \right)}^2}}}} $

(20)

则密度估计可以定义为:

$H = - \sum\limits_{i = 1}^n {\frac{{{\varphi _i}}}{Z}\log \left( {\frac{{{\varphi _i}}}{Z}} \right)} $

(21)

其中, $Z = \displaystyle\sum\limits_{i = 1}^n {{\varphi _i}} $ 为标准化因子.

1.3.2 基于自调节步长果蝇优化的自适应密度峰值聚类

对小规模数据集进行聚类时, 密度峰值聚类算法采取指数方式计算数据密度, 计算公式如下:

${\rho _i} = \sum\limits_{j \ne i} {\exp \left( { - {{\left( {\frac{{{d_{ij}}}}{{{d_c}}}} \right)}^2}} \right)} $

(22)

对比式(20)、(22)发现, 如果选择高斯核函数进行每个数据点密度的计算, 截断距离参数 ${d_c}$ 与 $\sigma $ 具有的意义是统一的, 优化 $\sigma $ 本质上就是对截断距离参数 ${d_c}$ 的优化. 而且, 若将整个数据集看成一个系统, 一个好的聚类结果是系统最稳定, 数据间关系确定性最好的状态, 因此, 以信息熵最小值为判定依据, 利用FOA算法的全局寻优特性, 对 $\sigma $ 进行优化, 优化后得出的 $\sigma $ 值即为最优的截断距离参数 ${d_c}$ .

将式(21)所示的信息熵函数作为自调节步长果蝇优化算法的浓度判定函数 ${F_{{\rm{unction}}}}\left( {{S_i}} \right)$ 进行优化, 求出最优 $\sigma $ 值, 即截断距离 ${d_c}$ . 按式(1)~(3)计算得到 $\rho _i^{}$ 和 $\delta _i^{}$ 后, 自适应的选择聚类中心.

聚类中心的 $\rho _i^{}$ 和 $\delta _i^{}$ 两个值都较大, 本文引入 $\gamma _i^{}$

$\gamma _i^{} = \rho _i^{} \times \delta _i^{}$

(23)

则 $\gamma _i^{}$ 较大的点, 就很有可能是聚类中心; 换言之, 聚类中心的 $\gamma _i^{}$ 一定较大, 可以先挑出 $\gamma _i^{}$ 值较大的点, 在从中去选择真正的聚类中心. 将 $\gamma _i^{}$ 值按降序排序. 定义临界点 $P$ , 表示 $\gamma _{[1 \sim P]}^{}$ 与 $\gamma _{[P \sim n]}^{}$ 变化程度最大的点, 本文用 $\gamma _i^{}$ 值降序排列图的斜率来表示其变化程度, 则P服从以下条件:

$P = \max \left\{ {i\left| {\left| {\left| {{k_i}} \right| - \left| {{k_{i + 1}}} \right|} \right| \ge \beta ,i = 1,2, \cdots ,n - 2} \right.} \right\}\;$

(24)

$ \beta = \alpha (j)/(n - 2) $

(25)

$ \alpha (j) = \sum\limits_{j = 1}^{n - 2} {\left\| {{k_j}| - |{k_{j + 1}}} \right\|} $

(26)

式中, ${k_i}$ 表示第 $i$ 个点和第 $i + 1$ 个点之间的线段的斜率; $\alpha \left( j \right)$ 表示在 $\gamma _i^{}$ 值降序排列图中两个邻居点的斜率差的总和; $\beta $ 表示斜率差的平均值; $i$ 是斜率差大于等于均值 $\beta $ 的点中序号最大的点及临界点.

那么聚类中心就可能存在于式(27)表示的范围内, 称这个范围内的点为伪中心.

${s_p}_q = \left\{ {q\left| {\gamma _q^{} \ge \gamma _p^{},q = 1,2, \cdots ,p} \right.} \right\}$

(27)

在同一范围内存在多个伪中心, 因此需要将同一范围内多余的伪聚类中心排除. 在密度峰值算法中, 聚类中心与密度点更高的点相距较远, 因此, 本文取同一区域中的第1个伪中心作为聚类中心, 判断其他的伪中心到该点的距离, 若小于 $d\left( {{x_i},{N_k}\left( {{x_i}} \right)} \right)$ 则将其消除; 如果大于, 则将其作为新的聚类中心. 在聚类过程中自适应的根据实际数据选出聚类中心, 聚类中心个数即为最终聚类数目.

1.4 算法流程及复杂度分析 1.4.1 算法流程

算法1. 基于自调节步长果蝇优化的自适应快速峰值聚类算法

输入: 样本数据集X, 参数m, n

输出: 数据的分类标签y

1)初始化果蝇群体规模以及最大迭代次数;

2)将浓度测定值带入信息熵函数, 确定果蝇个体的味道浓度;

3)按式(14)~(17)自调节步长并得到最优 $\scriptstyle\sigma $ 值, 即截断距离 $\scriptstyle{d_c}$ ;

4)计算原始数据的距离矩阵作为输入并根据式(1)(2)(3)计算局部密度和到高密度点的距离;

5)按式(23)~(27)选择聚类中心;

6)分配其他非中心点并完成结果优化;

7)聚类结果可视化并输出分类标签.

1.4.2 算法复杂度分析

假设果蝇群体大小为S, 最大迭代次数为M, 个体浓度跟新计算量为O(1), 计算浓度差值变化率所需的时间复杂度为O(M), 并且动态调整步长的时间复杂度为O(M), 所以计算最优截止距离部分的时间复杂度为O((N+2)*M). 假设由自调节步长果蝇优化的自适应密度峰值聚类算法(Adaptive Density Peak Clustering based on Fruit fly Optimization of Self-adjusting step-size, SFO-ADPC)处理的数据集有N个数据点, 则存储每个数据点与其他点的距离的时间复杂度为O(N²), 计算每个数据点的局部密度及距离所需的时间复杂度为O(2N), 计算边界区域需要的时间复杂度为O(N²). 综上, 本文所提算法的时间复杂度为O((N+2)*M+(N+1)*N).

2 实验与结果分析 2.1 实验数据集

为测试所提SFO-ADPC算法的准确性和有效性, 本文选择了5个人工数据集和5个常用于聚类测试的真实数据集. 表1中为本文所用数据集, 包括环形、月牙形、聚集、火焰、螺旋形、Iris、Wine和Soybean数据集. 5个人工数据集的数据分布情况如图3所示, 图中数据点横纵坐标均为数值, 无具体物理意义, 故无单位.

聚集和火焰数据是典型的聚类算法性能测试数据, 环形、月牙形和螺旋形数据为测试算法能否准确地对非球形数据聚类的典型数据集. Iris是鸢尾花卉数据集, 其中有150个样本, 属于3个类别, 每个类别有50个样本, 每个样本具有4个属性, 即花萼长宽以及花瓣长宽. 3个类别分别为Setosa, Versicolour和Virginica. Wine是酒数据集, 有178个样本, 每个样本有13个属性, 属于3个类别, 每个类别数量不同. Soybean数据集是大豆疾病数据集, 包含47个数据, 每个数据包含35个属性, 分为4类, 是线性可分的, 其所有属性都可作为分类属性. Ecoli数据集是大肠杆菌数据, 由336个样本组成, 每个样本有7个属性, 分为8类. Seeds数据集包含210个样本, 每个样本有7个属性, 每个样本分为3个类.

2.2 实验数据集

本文主要使用两个评价指标来测试所提的算法: 内部轮廓系数(Silhouette)和外部F值(F-measure).

1) Silhouette指标

对于其中的一个样本点 $i$ 来说, 需要计算两个量: $a\left( i \right)$ 与 $b\left( i \right)$ ,

那么 $i$ 向量轮廓系数就如下式:

$S\left( i \right) = \frac{{b\left( i \right) - a\left( i \right)}}{{\max \left\{ {a\left( i \right),b\left( i \right)} \right\}}}$

(28)

$a\left( i \right)$ : $i$ 向量与同一类中每个点的不相似性的平均值.

$b\left( i \right)$ : $i$ 向量与其他类的点的不相似性的最小平均值.

使用所有数据S平均值评估簇的紧密性和可索引性. S介于–1和1范围内, 对于同一数据集, S越大聚类越好.

2) F-measure指标

F-measure是一种结合准确率和召回率的外部评估指标. 对于真实类 ${P_j}$ 与聚类所产生的类 ${C_i}$ , 分别定义准确率 $P\left( {i,j} \right)$ 和召回率 $R\left( {i,j} \right)$ . 其表示为:

$P\left( {i,j} \right) = \frac{{\left| {{P_j} \cap {C_i}} \right|}}{{\left| {{C_i}} \right|}}$

(29)

$R\left( {i,j} \right) = \frac{{\left| {{P_j} \cap {C_i}} \right|}}{{\left| {{P_j}} \right|}}$

(30)

$P\left( {i,j} \right)$ 和 $R\left( {i,j} \right)$ 的都介于0和1之间, 且两者的数值大小与相对应的正确率和召回率成正比.

相应的F-measure指标计算:

$F\left( {{P_j},{C_i}} \right) = \frac{{2 \times P\left( {{P_j},{C_i}} \right) \times R\left( {{P_j},{C_i}} \right)}}{{P\left( {{P_j},{C_i}} \right) + R\left( {{P_j},{C_i}} \right)}}$

(31)

将各类F-measure指标作平均则可以求出最终F-measure值, 其表示为:

$F = \sum\limits_j {\frac{{\left| {{P_j}} \right|}}{N}} \mathop {\max }\limits_i F\left( {{P_j},{C_i}} \right)$

(32)

上述公式中N为数据总个数, 计算所得F-measure值越大, 则算法准确程度越高.

2.3 实验结果与分析

本文将所提算法SFO-ADPC与FODPC、DPC、DBSCAN、K-Means在数据集上比较. 图4中分别为K-Means在环形、月牙形、聚集、火焰、以及螺旋数据集上的聚类结果, 图5中分别为DBSCAN在环形、月牙形、聚集、火焰、以及螺旋数据集上的聚类结果, 图6中分别为DPC在环形、月牙形、聚集、火焰、以及螺旋数据集上的聚类结果, 图7中分别为FODPC在环形、月牙形、聚集、火焰、以及螺旋数据集上的聚类结果, 图8中分别为SFO-ADPC在环形、月牙形、聚集、火焰、以及螺旋数据集上的聚类结果.

测试算法中使用的数据集分布大多为非球形的, K-Means无法准确对其进行聚类, 同时, 聚集数据集虽然是球形分布的, 但由于样本量分布不均匀, K-Means仍然无法达到最好的聚类效果. DBSCAN可以有效地对测试数据集进行聚类, 但其参数确定过程较为繁琐, 不同的数据集的聚类参数相差较大, 用户需要花费大量的时间用于调参.

DPC及其改进算法可以有效对非球形数据进行聚类, 同时聚类的准确率大大提高, FODPC及本文提出的SCFO-ADPC给出了更好的截断距离, 克服DPC需要人工设置截断距离的缺陷; 同时, 本文算法提供的截断距离更好, 提升了聚类准确率. 并且, 本文所提算法能够自适应的选择聚类中心, 改善了原始DPC算法需要手动选取聚类中心的缺陷.

表2中列出了上述5种算法在5个人工数据集及5个真实数据集的聚类效果评价得分.

上述5种聚类算法应用于实际数据时, SCFO-ADPC的准确率及召回率更高, 本文所提算法能有效的对任何形状的数据进行聚类, 对于具有较高维度的数据集也可有效进行聚类, 并且聚类效率及效果有一定提高.

3 结语

本文提出了一种基于自调节步长果蝇优化的自适应密度峰值聚类算法(SCFO-DPC). SCFO-DPC算法通过可自调节步长的果蝇优化算法得到最佳截止距离, 解决了需要根据人工设置截止距离参数的问题, 并且得到的参数优于其他优化算法; 能够自适应的选择聚类中心, 有效的解决了人工选择聚类中心为聚类算法带来的不稳定性. 通过测试, SCFO-DPC算法在对人工数据集、UCI真实数据集的处理上具有相当大的优越性, 比FODPC、DPC、DBSCAN和K-Means算法更准确有效, 且受人为影响更少.