扩展LDBSCAN 算法在图上的应用

 一 、 背景和正确性分析
SCAN 和 LDBSCAN :

SCAN 是基于密度的聚类算法。一个社交网络能被看成是一个图,在这个图上面一个社交
个体能被看成是一个节点, 个体之间的关系则可以被视作一条边。 这种有现实关系映射到图
的思想可以有许多的应用和扩展。 聚类算法就是一种用于发现社交网络中节点间关系的基本
方法。

在社交网络的聚类中,首先要考察的是节点间的连通性,再由连通性的定义找到连通分
量,因为在社交网络中关注的不是节点和节点之间的距离,因此节点间的是否连通不看是
否存在一条边,而是着眼于节点和节点的相似度,只有相似度高的节点才是连通的,相似
度高的点彼此相连就形成了连通分量,从而就形成了一个聚类。相似度不够高的点,也就
是不被其他节点可达的,不在连通分量里面,不属于一个聚类。
但是在真实世界中的多维数据集经常会出现十分偏斜、离散的(相对于高斯密度分布而
言)的分布,这种分布的全局性很难被 SCAN 聚类算法所揭露,因为 SCAN 聚类算法使
用一种全局的特征分析量。
而 LDBSCAN 聚类本来是基于距离的聚类算法,它有一个优点就是不像 SCAN 聚类一样
使用固定的相似度作为参数,它使用MinPts 作为一个参数,去考量某个节点的 MinPts
个最靠近它的节点。也就是说 LDBSCAN 的聚类是有某个点附近的点的分布决定的,由此
聚出来的类可以有相对离散也可以有相对稠密的。由于这种特性,我们可以把这个本来是
基于距离的一种聚类方法推广到图上面。我们知道,社交网络的聚类很重要的一个概念就
是相似度,所以为了把 LDBSCAN 推广到社交图上面,我们需要引进相似度。那么以相似
度作为距离,这就相当于用相似度进行聚类了。
为了验证 LDBSCAN 的正确性,我们可以用 SCAN 的聚类效果和 LDBSCAN 的效果进行
比较。
由于 SCAN 使用的是全局的特征分析量,所以我们需要经过反复调试 LDBSCAN 的 pct
等 参 数 , 尤 其 是 p c t , 这 直 接 影 响 local outlier factor (LOF).
LOF的主要影响因子就是 pct ,通过调节 pct 的值,
直到 LDBSCAN 聚出来的类的子集和 SCAN 聚出来的最主要那个类(所谓主要就是最大)
足够相似为止。
按照论文上面的参考值设置 SCAN 的参数为  《扩展LDBSCAN 算法在图上的应用》, 得出最大的聚类有 184543个点,聚类记作
C1。将 LDBSCAN 的参数 pct 设置为 0.11,lofub 设置为 1,得出最大的聚类有 186091 个点,聚类记作C2 。
C1和C2 相比,相同的点有 170317 个。然后再将 pct 稍作变化,精确到 0.001,结果发现就算是变化 0.001 的单位, LDBSCAN 聚出来的类都会产生很大的变化,这种变化体现在C1和C2 的共同节点变少。这也说明了,在 LDBSCAN 在 pct 变化的时候,节点之间的连通性会发生变化,导致聚类结果发生变化。这体现了基于密度聚类算法的特性,因为如果用距离去聚类的话,缓慢改变

参数导致的结果变化也是很缓慢的。


二、 LDBSCAN  聚类 算法 说明文档

略去….CSDN的编辑器太恶心….

 

三 、 实验测试结果 
《扩展LDBSCAN 算法在图上的应用》

《扩展LDBSCAN 算法在图上的应用》

《扩展LDBSCAN 算法在图上的应用》

 《扩展LDBSCAN 算法在图上的应用》

《扩展LDBSCAN 算法在图上的应用》


《扩展LDBSCAN 算法在图上的应用》

点赞