基本概念
①核心对象:若某个点的密度达到算法设定的阈值则其为核心点。(即r领域内点的数量不小于minPts)
②核心点-邻域的距离阈值:设定的半径r。
③直接密度可达:若某点p在点q的r邻域内,且q是核心点则p-q直接密度可达。
④密度可达:若有一个点的序列q0,q1,…..qk,对任意qi到qi+1是直接密度可达的,则称q0到qk密度可达,这实际上是直接密度可达的“传播”。
⑤密度相连:若从某核心点p出发,点q和点k都是密度可达的,则称点q和点k是密度相连的。
⑥边界点:属于一个类的非核心点,已经无法继续发展下线(也就是可被别的核心点探测到,但是它自己不满足r邻域内有minPts个点了)。
⑦ 噪声点:不属于任何簇的点是任何核心点都无法达到的密度。
算法点示例
DBSCAN算法流程
DBSCAN算法参数选择
半径r的选择,可以根据k距离来设定:找突变点。
k距离:给定数据集P={p(i);i=0,1,….,n},计算点P(i)到集合D的子集S中所有点之间的距离,距离按照从小到大的顺序排序,d(k)就被成为k-距离。
Minpts:k-距离中k的值,一般取得小一些,多次尝试。
DBSCAN算法的优势与劣势
Advantage:
①无需指定要分类的簇数
②可以找到任意形状的簇
③ 善于发现异常值(检测任务)
④两个参数就够了
Disadvantage:
①高维数据难(可以降维)
② 参数选择困难(参数对结果影响很大)
④Sklearn中效率很慢(可以做数据削减)
对比kmeans的两个示例,DBSCAN的正确分类
在r=1,minpts为4的情况下可以做到基本的正确聚类。
文章出处登录后可见!
已经登录?立即刷新