DBSCAN 优化算法

Complexity

DBSCAN is designed for use with databases that can accelerate region queries, e.g. using an R* tree.
DBSCAN 被设计成能配合可加速 region query 的数据库结构，例如 R* 树。

complexity [kəm'pleksətɪ]：n. 复杂，复杂性，复杂错综的事物
database ['deɪtəbeɪs]：n. 数据库，资料库
region ['riːdʒ(ə)n]：n. 地区，范围，部位
query ['kwɪərɪ]：n. 疑问，质问，疑问号，查询 vt. 询问，对...表示疑问 vi. 询问，表示怀疑

DBSCAN visits each point of the database, possibly multiple times (e.g., as candidates to different clusters). For practical considerations, however, the time complexity is mostly governed by the number of regionQuery invocations. DBSCAN executes exactly one such query for each point, and if an indexing structure is used that executes a neighborhood query in $O(log n)$O(logn), an overall average runtime complexity of $O(n log n)$O(nlogn) is obtained (if parameter $\epsilon$ϵ is chosen in a meaningful way, i.e. such that on average only $O(log n)$O(logn) points are returned). Without the use of an accelerating index structure, or on degenerated data (e.g. all points within a distance less than $\epsilon$ϵ), the worst case run time complexity remains $O(n^2)$O(n2). The distance matrix of size $(n^{2} - n)/2$(n2−n)/2 can be materialized to avoid distance recomputations, but this needs $O(n^2)$O(n2) memory, whereas a non-matrix based implementation of DBSCAN only needs $O(n)$O(n) memory.
DBSCAN 对数据库里的每一点进行访问，可能多于一次 (例如作为不同聚类的候选者)，但在现实的考虑中，时间复杂度主要受 regionQuery 的调用次数影响，DBSCAN 对每点都进行刚好一次调用，且如果使用了特别的编号结构，则总平均时间复杂度为 $O(n log n)$O(nlogn)，最差时间复杂度则为 $O(n^2)$O(n2)。可以使用 $O(n^2)$O(n2) 空间复杂度的距离矩阵以避免重复计算距离，但若不使用距离矩阵，DBSCAN 的空间复杂度为 $O(n)$O(n)。

invocation [,ɪnvə(ʊ)'keɪʃ(ə)n]：n. 祈祷，符咒，(法院对另案的) 文件调取，(法权的) 行使
govern ['gʌv(ə)n]：vt. 管理，支配，统治，控制 vi. 居支配地位，进行统治
degenerate [dɪ'dʒen(ə)rət]：vt. 使退化，恶化 vi. 退化，堕落 adj. 退化的，堕落的 n. 堕落的人
candidate ['kændɪdeɪt; -dət]：n. 候选人，候补者，应试者

R contains implementations of DBSCAN in the packages dbscan and fpc. Both packages support arbitrary distance functions via distance matrices. The package fpc does not have index support (and thus has quadratic runtime and memory complexity) and is rather slow due to the R interpreter. The package dbscan provides a fast C++ implementation using k-d trees (for Euclidean distance only) and also includes implementations of DBSCAN*, HDBSCAN*, OPTICS, OPTICSXi, and other related methods.
https://cran.r-project.org/web/packages/dbscan/index.html
https://cran.r-project.org/web/packages/fpc/index.html

scikit-learn includes a Python implementation of DBSCAN for arbitrary Minkowski metrics, which can be accelerated using k-d trees and ball trees but which uses worst-case quadratic memory. A contribution to scikit-learn provides an implementation of the HDBSCAN* algorithm.
https://en.wikipedia.org/wiki/Scikit-learn
https://en.wikipedia.org/wiki/Minkowski_distance
https://github.com/scikit-learn-contrib/hdbscan

pyclustering library includes a Python and C++ implementation of DBSCAN for Euclidean distance only as well as OPTICS algorithm.
https://github.com/annoviko/pyclustering

R* tree
https://en.wikipedia.org/wiki/R*_tree

$k$k-d tree
https://en.wikipedia.org/wiki/K-d_tree

Ball tree
https://en.wikipedia.org/wiki/Ball_tree

quadratic [kwɒ'drætɪk]；adj. 二次的 n. 二次方程式

The current implementation uses ball trees and kd-trees to determine the neighborhood of points, which avoids calculating the full distance matrix (as was done in scikit-learn versions before 0.14).

Memory consumption for large sample sizes

This implementation is by default not memory efficient because it constructs a full pairwise similarity matrix in the case where kd-trees or ball-trees cannot be used (e.g. with sparse matrices). This matrix will consume $n^2$n2 floats. A couple of mechanisms for getting around this are:

• A sparse radius neighborhood graph (where missing entries are presumed to be out of eps) can be precomputed in a memory-efficient way and dbscan can be run over this with metric=‘precomputed’. See sklearn.neighbors.NearestNeighbors.radius_neighbors_graph.
• The dataset can be compressed, either by removing exact duplicates if these occur in your data, or by using BIRCH. Then you only have a relatively small number of representatives for a large number of points. You can then provide a sample_weight when fitting DBSCAN.

pairwise ['peə,waɪz]：adj. 成对发生的 adv. 成对地，成双地
similarity [sɪmə'lærətɪ]：n. 类似，相似点
mechanism ['mek(ə)nɪz(ə)m]：n. 机制，原理，途径，进程，机械装置，技巧
presume [prɪ'zjuːm]：vt. 假定，推测，擅自，意味着 vi. 相信，擅自行为
exact [ɪg'zækt; eg-]：adj. 准确的，精密的，精确的 vt. 要求，强求，急需 vi. 勒索钱财
ordering points to identify the clustering structure，OPTICS