基于自适应蜂群优化的DBSCAN聚类算法
发布时间：2021-04-16 15:16
针对传统的DBSCAN（Density-Based Spatial Clustering of Application with Noise,DBSCAN）聚类算法全局参数设置不合理、参数选取困难、无法识别重叠模块的问题,以及人工蜂群优化算法（Artificial Bees Colony,ABC）后期收敛速度慢、易陷入局部最优等缺陷进行了研究,提出一种基于自适应人工蜂群优化DBSCAN的聚类算法IABC-DBSCAN。该算法将截断选择机制与锦标赛选择机制相结合,提出一种截断-锦标赛选择机制（TruncationChampionship Selection Mechanism,TCSM）,以增强种群多样性、避免跟随蜂选择蜜源陷入局部最优的缺陷;提出一种自适应步长策略（Adaptive Step Strategy,ASS）动态调整跟随蜂的搜索方式,以提高算法局部搜索能力和聚类速度;根据改进的IABC算法动态调节DBSCAN算法中的最优参数,将蜜源位置对应ε邻域,蜜源的适应度大小对应DBSCAN的聚类效果,并在多种测试函数和数据集上进行验证。实验结果表明,该算法不仅有效克服ABC和DBSCA...
【文章来源】：计算机工程与应用. 2019,55(14)北大核心CSCD
【文章页数】：10 页
【部分图文】：
不同Minpts取值的f-measure对比
面改进后的IABC算法具有较强的全局和局部的寻优能力，从而进一步提高聚类效果。而P-DBSCAN算法虽然也是采用群智能算法来优化DBSCAN算法的参数选取，但忽略了群智能优化算法普遍存在的缺陷，即易陷入局部最优，由于没针对这一问题进行优化，因此聚类效果不佳。为进一步分析IABC-DBSCAN的聚类性能，分别从各类算法识别功能模块的数目、簇平均大小和覆盖蛋白0.20.30.40.50.60.70.80.91.0匹配率阈值706050403020100被识别的已知功能模块的比例/%IABC-DBSCANABC-DBSCAN图2基于不同优化算法检测功能模块的对比结果偈聚类数目18001600140012001000800600400200时间开销/sIABC-DBSCANABC-DBSCAN501001502002503003504004505005506006500图3各算法时间开销对比图时间点123456789101112ε0.5780.6250.6970.5240.6630.5860.5750.4870.6530.5590.5140.601Minpts333333333333precision0.67950.77350.86750.68590.56440.71390.80120.67150.75230.72670.62180.7428recall0.47550.58870.48910.70230.50910.73540.67450.58410.67540.60210.61790.6453f-measure0.55950.66850.62550.69400.53530.72440.73240.62470.71170.65850.61980.7428表812个动态子网的最优参数及其聚类性能precision1.00.90.80.70.60.50.40.30.20.10Valuerecallf-measureDBSCANOPTICSP-DBSCANACC-DBSCANIABC-DBSCAN图4各
2019，55（14）ComputerEngineeringandApplications计算机工程与应用断-锦标赛选择机制和自适应步长策略分别优化了跟随蜂的蜜源选择机制和局部搜索策略，避免算法后期早熟、陷入局部最优的缺陷，提高算法的搜索和开发能力，进而提高DBSCAN的聚类效果。为进一步验证IABC算法在收敛速度上的优越性，比较在相同聚类数目下，采用两种算法所花费的时间开销。图3为两种算法的时间开销对比图。从图中可以明显看出，IABC-DBSCAN算法的时间开销始终比ABC-DBSCAN算法低，并且随着聚类数目的增加，两种算法的时间花费差值也逐渐增大。由于原始蜂群算法后期，种群多样性下降，搜索无目的性，因此无用的搜索次数增加，从而导致后期收敛速度变慢且很难跳出局部最优，因此ABC-DBSCAN算法后期花费时间更长。而IABC-DBSCAN因为采取了自适应的截断-锦标赛选择机制TCSM和步长搜索策略ASS，能够自适应地根据全局最优解信息，加快寻优速度和提高寻优精度，因此相比于ABC-DBSCAN，IABC-DASCAN算法时间性能大大降低。4.2.5性能分析为评估IABC-DBSCAN算法聚类性能，分别将IABC-DBSCAN算法应用于各个动态子网中独立运行10次，取10次结果的平均值分析。表8为IABC-DBSCAN算法在12个动态子网的最优参数和聚类结果，在不同瞬态子网上该算法的最优参数和聚类性能都有所不同。这12个动态动态子网上分别设置ε和MinPts的不同取值，能够在一定程度上避免全局参数设置不合理的缺陷，从而更进一步提高聚类性能。为验证IABC-DBSCAN算法在动态加权网络的有效性，分别与聚类算法DBSCAN[2]、OPTICS[3]，ACC-DBSCAN[6]和P-DBSCAN[7]进行对比实验。所有算法都是基于相同的动态加权PPI网络，以CYC2008作为标准复合物。图4为各算法在准确率、召
【参考文献】：
期刊论文
[1]基于动态加权PPI网络的关键蛋白质识别算法[J]. 杨书新,鲁纪华,汤达荣. 计算机应用研究. 2019(02)
[2]基于knee points的改进多目标人工蜂群算法[J]. 刘明辉,李炜. 计算机工程与应用. 2018(02)
[3]基于人工蜂群智能技术的属性异常点检测[J]. 朱焕雄,刘波. 计算机科学与探索. 2017(12)
[4]具有学习及十字交叉搜索的人工蜂群算法[J]. 黄珊,高兴宝. 计算机科学与探索. 2017(12)
[5]动态分配聚类中心的改进K均值聚类算法[J]. 程艳云,周鹏. 计算机技术与发展. 2017(02)
[6]一种基于k-均值的DBSCAN算法参数动态选择方法[J]. 王兆丰,单甘霖. 计算机工程与应用. 2017(03)
[7]一种结合蚁群聚类算法的DBSCAN算法[J]. 许芳芳. 池州学院学报. 2014(06)
[8]基于数据场的改进DBSCAN聚类算法[J]. 杨静,高嘉伟,梁吉业,刘杨磊. 计算机科学与探索. 2012(10)
[9]基于蜂群和广度优先遍历的PPI网络聚类[J]. 田建芳,雷秀娟. 模式识别与人工智能. 2012(03)
[10]蛋白质相互作用网络的蜂群信息流聚类模型与算法[J]. 雷秀娟,田建芳. 计算机学报. 2012(01)
硕士论文
[1]不同选择策略的人工植物算法[D]. 李鹏.太原科技大学 2014
本文编号：3141671
【文章来源】：计算机工程与应用. 2019,55(14)北大核心CSCD
【文章页数】：10 页
【部分图文】：
不同Minpts取值的f-measure对比
面改进后的IABC算法具有较强的全局和局部的寻优能力，从而进一步提高聚类效果。而P-DBSCAN算法虽然也是采用群智能算法来优化DBSCAN算法的参数选取，但忽略了群智能优化算法普遍存在的缺陷，即易陷入局部最优，由于没针对这一问题进行优化，因此聚类效果不佳。为进一步分析IABC-DBSCAN的聚类性能，分别从各类算法识别功能模块的数目、簇平均大小和覆盖蛋白0.20.30.40.50.60.70.80.91.0匹配率阈值706050403020100被识别的已知功能模块的比例/%IABC-DBSCANABC-DBSCAN图2基于不同优化算法检测功能模块的对比结果偈聚类数目18001600140012001000800600400200时间开销/sIABC-DBSCANABC-DBSCAN501001502002503003504004505005506006500图3各算法时间开销对比图时间点123456789101112ε0.5780.6250.6970.5240.6630.5860.5750.4870.6530.5590.5140.601Minpts333333333333precision0.67950.77350.86750.68590.56440.71390.80120.67150.75230.72670.62180.7428recall0.47550.58870.48910.70230.50910.73540.67450.58410.67540.60210.61790.6453f-measure0.55950.66850.62550.69400.53530.72440.73240.62470.71170.65850.61980.7428表812个动态子网的最优参数及其聚类性能precision1.00.90.80.70.60.50.40.30.20.10Valuerecallf-measureDBSCANOPTICSP-DBSCANACC-DBSCANIABC-DBSCAN图4各
2019，55（14）ComputerEngineeringandApplications计算机工程与应用断-锦标赛选择机制和自适应步长策略分别优化了跟随蜂的蜜源选择机制和局部搜索策略，避免算法后期早熟、陷入局部最优的缺陷，提高算法的搜索和开发能力，进而提高DBSCAN的聚类效果。为进一步验证IABC算法在收敛速度上的优越性，比较在相同聚类数目下，采用两种算法所花费的时间开销。图3为两种算法的时间开销对比图。从图中可以明显看出，IABC-DBSCAN算法的时间开销始终比ABC-DBSCAN算法低，并且随着聚类数目的增加，两种算法的时间花费差值也逐渐增大。由于原始蜂群算法后期，种群多样性下降，搜索无目的性，因此无用的搜索次数增加，从而导致后期收敛速度变慢且很难跳出局部最优，因此ABC-DBSCAN算法后期花费时间更长。而IABC-DBSCAN因为采取了自适应的截断-锦标赛选择机制TCSM和步长搜索策略ASS，能够自适应地根据全局最优解信息，加快寻优速度和提高寻优精度，因此相比于ABC-DBSCAN，IABC-DASCAN算法时间性能大大降低。4.2.5性能分析为评估IABC-DBSCAN算法聚类性能，分别将IABC-DBSCAN算法应用于各个动态子网中独立运行10次，取10次结果的平均值分析。表8为IABC-DBSCAN算法在12个动态子网的最优参数和聚类结果，在不同瞬态子网上该算法的最优参数和聚类性能都有所不同。这12个动态动态子网上分别设置ε和MinPts的不同取值，能够在一定程度上避免全局参数设置不合理的缺陷，从而更进一步提高聚类性能。为验证IABC-DBSCAN算法在动态加权网络的有效性，分别与聚类算法DBSCAN[2]、OPTICS[3]，ACC-DBSCAN[6]和P-DBSCAN[7]进行对比实验。所有算法都是基于相同的动态加权PPI网络，以CYC2008作为标准复合物。图4为各算法在准确率、召
【参考文献】：
期刊论文
[1]基于动态加权PPI网络的关键蛋白质识别算法[J]. 杨书新,鲁纪华,汤达荣. 计算机应用研究. 2019(02)
[2]基于knee points的改进多目标人工蜂群算法[J]. 刘明辉,李炜. 计算机工程与应用. 2018(02)
[3]基于人工蜂群智能技术的属性异常点检测[J]. 朱焕雄,刘波. 计算机科学与探索. 2017(12)
[4]具有学习及十字交叉搜索的人工蜂群算法[J]. 黄珊,高兴宝. 计算机科学与探索. 2017(12)
[5]动态分配聚类中心的改进K均值聚类算法[J]. 程艳云,周鹏. 计算机技术与发展. 2017(02)
[6]一种基于k-均值的DBSCAN算法参数动态选择方法[J]. 王兆丰,单甘霖. 计算机工程与应用. 2017(03)
[7]一种结合蚁群聚类算法的DBSCAN算法[J]. 许芳芳. 池州学院学报. 2014(06)
[8]基于数据场的改进DBSCAN聚类算法[J]. 杨静,高嘉伟,梁吉业,刘杨磊. 计算机科学与探索. 2012(10)
[9]基于蜂群和广度优先遍历的PPI网络聚类[J]. 田建芳,雷秀娟. 模式识别与人工智能. 2012(03)
[10]蛋白质相互作用网络的蜂群信息流聚类模型与算法[J]. 雷秀娟,田建芳. 计算机学报. 2012(01)
硕士论文
[1]不同选择策略的人工植物算法[D]. 李鹏.太原科技大学 2014
本文编号：3141671
本文链接：https://www.wllwen.com/kejilunwen/sousuoyinqinglunwen/3141671.html
