论文标题：A survey of density based clustering algorithms (基于密度的聚类算法综述)

期刊：Frontiers of Computer Science

作者：Panthadeep BHATTACHARJEE , Pinaki MITRA

DOI：10.1007/s11704-019-9059-3

微信链接：点击此处阅读微信文章

原文信息

标题：

A survey of density based clustering algorithms

原文链接：

https://journal.hep.com.cn/fcs/EN/10.1007/s11704-019-9059-3

引用格式：

Panthadeep BHATTACHARJEE, Pinaki MITRA. A survey of density based clustering algorithms. Front. Comput. Sci., 2021, 15(1): 151308

1.导读

聚类以一种无监督学习的方式将数据划分为多个簇，在现实生活中具有广泛应用场景。常用的聚类算法可以分为三类，即：层次法、划分法和基于密度的方法（如图1所示）。本文对基于密度的方法(Density Based Clustering Algorithms, DBCLAs) 进行了详细的介绍，因为其能够自动检测出任意形状和数量的簇，相比其它两类聚类算法具有较大的优势。本文进一步根据如下四个方面对基于密度的方法进行归类，即：密度定义、参数敏感性、运行方式和数据类型。此外，本文介绍了基于密度的聚类方法的相关应用场景以及有待改进的方向。

2.基于密度的聚类算法

在以往的综述文献中，也有一些关于基于密度的聚类算法的介绍。与现有综述相比，本文内容更加完善和齐全，从更多的角度对大量现有工作进行了介绍和比较。本文的特色之处如表1所示。

本文将 DBCLAs 按照密度定义、参数敏感性、运行方式和数据类型四个方面进行分类，如图5所示。

密度定义

根据密度的计算方式，本文将DBCLAs方法分为四类：基于点的方法、基于网格的方法、概率方法、数据依赖方法。

(a) 基于点的方法：该类方法根据临域内点的数量计算密度；

(b) 基于网格的方法：该类方法通过寻找数据密集的网格形成聚集的簇，其中网格的密度由其内部的样本数量决定。基于网格的方法尤其适合应用于高维数据；

(c) 概率方法：使用概率模型的聚类方法可以根据特定的密度函数计算数据的密度，可以应用于高维、大规模数据集。这种方法用于处理高维的海量数据集，例如多媒体数据集；

(d) 数据依赖：该类方法使用依赖于数据的相异性度量来计算数据对象实例之间的相似度。因此，通过确定目标附近的点的数量来计算密度。例如，在MBSCAN[29]中，相似度是基于包含两个数据点的最小区域中的质量计算的。然后，通过查找与目标点之间的质量小于设定的阈值的点的数量计算密度。

参数敏感性

许多DBCLAs依赖于使用对聚类效果影响较大的参数。此外，还有一些算法可以自适应的调整参数值，这类算法依赖于数据分布来计算参数值。基于参数依赖性，本文将DBCLAs分为两类：参数敏感型方法和参数自适应变化的方法。

(a) 参数敏感型方法：聚类算法的效果依赖于参数的取值；

(b) 参数自适应变化的方法：聚类算法的效果对参数的取值变化不敏感。

运行方式

大多数 DBCLAs 以串行模式执行，但是为了提高效率，研究人员提出了并行算法和分布式算法。本文根据算法的执行方式将基于密度的聚类方法分为三类：串行、并行和分布式方法。

(a) 串行：该类方法以串行方式一个接一个地执行其各个模块；

(b) 并行：该类方法将数据分发到多台机器同时执行；

(c) 分布式：大多数分布式聚类方法通过聚合各个节点上获得的局部结果来生成全局模型，算法的计算复杂度和效果在很大程度上取决于信息聚合的效果。

数据类型

一些DBCLAs仅适用于特定的数据集，例如空间、非空间、图像或其他多媒体数据集。基于算法适用的数据集类型，本文将DBCLA分为三类：空间、非空间、多媒体/其他。

(a) 空间：空间数据集指的是地球表面的具体位置；

(b) 非空间：当数据集与任何地理位置都无关，都被称为非空间数据。

(c) 媒体/其他：多媒体数据集包括图像、视频、图形。与空间数据集相比，在此类数据集上获得好的效果通常非常困难。

根据上述四个角度，可以将现有的DBCLAs进行划分，如图6 所示。

3.实验效果对比

本文对一些现有的 DBCLAs 进行了实验对比，例如 DBSCAN 和 STING 的运行效率对比：

SNN-DBSCAN 在不同数据集的效果展示：

4.未来研究方向

（1）异构数据集：大多现有工作仅关注同构数据集，但在异构数据集上的效果未知。随着网络数据量的增加，以及同时处理结构化和非结构化数据需求的增加，基于密度的聚类方法还有待改进。

（2）簇内密度变化：簇内密度显著变化的聚类仍然是一个有待研究的问题，现有的少量相关工作的效果往往对参数敏感，而且无法很好的处理高维数据集。

（3）基于图的应用：现实世界中很多应用都可以归纳为图数据，DBCLAs在图数据中的作用仍然有待开发。

（4）社交网络：DBCLAs 在社交网络领域的作用仍然是一个有趣的挑战。一个最近的研究使用基于密度的聚类算法，利用空间-文本信息，对Twitter上的文本异质性识别聚类。DBCLAs在这一领域的应用可能会带来有意义的结果。

摘要

Density based clustering algorithms (DBCLAs) rely on the notion of density to identify clusters of arbitrary shapes, sizes with varying densities. Existing surveys on DBCLAs cover only a selected set of algorithms. These surveys fail to provide an extensive information about a variety of DBCLAs proposed till date including a taxonomy of the algorithms. In this paper we present a comprehensive survey of various DBCLAs over last two decades along with their classification. We group the DBCLAs in each of the four categories: density definition, parameter sensitivity, execution mode and nature of data and further divide them into various classes under each of these categories. In addition, we compare the DBCLAs through their common features and variations in citation and conceptual dependencies. We identify various application areas of DBCLAs in domains such as astronomy, earth sciences, molecular biology, geography, multimedia. Our survey also identifies probable future directions of DBCLAs where involvement of density based methods may lead to favorable results.

解读：魏通 东南大学

审核：张琨 合肥工业大学

Frontiers of Computer Science

Frontiers of Computer Science （FCS）是由教育部主管、高等教育出版社和北京航空航天大学共同主办、SpringerNature 公司海外发行的英文学术期刊。本刊于 2007 年创刊，双月刊，全球发行。主要刊登计算机科学领域具有创新性的综述论文、研究论文等。本刊主编为周志华教授，共同主编为熊璋教授。编委会及青年 AE 团队由国内外知名学者及优秀青年学者组成。本刊被 SCI、Ei、DBLP、INSPEC、SCOPUS 和中国科学引文数据库（CSCD）核心库等收录，为 CCF 推荐期刊；两次入选“中国科技期刊国际影响力提升计划”；入选“第4届中国国际化精品科技期刊”；入选“中国科技期刊卓越行动计划项目”。

《前沿》系列英文学术期刊

由教育部主管、高等教育出版社主办的《前沿》（Frontiers）系列英文学术期刊，于2006年正式创刊，以网络版和印刷版向全球发行。系列期刊包括基础科学、生命科学、工程技术和人文社会科学四个主题，是我国覆盖学科最广泛的英文学术期刊群，其中13种被SCI收录，其他也被A&HCI、Ei、MEDLINE或相应学科国际权威检索系统收录，具有一定的国际学术影响力。系列期刊采用在线优先出版方式，保证文章以最快速度发表。

中国学术前沿期刊网

http://journal.hep.com.cn