改算法可以用于实时路况的gps点的去噪,伪码如下:
输入:
E: 对象半径
Minpst: 给定D中E领域以内成为核心点的最小点数
D: 集合
目标:找到多个联通的最大相互密度直接可达的点的集合
repeat:
判断点是否是核心点
记录该点的直接密度可达点
util 所有输入点完成遍历
repeat:
将该点的相互直接密度可达的点加入同一组
util 所有核心对象的领域都完成遍历
该算法的好处是:
能用于去噪
发现任意形状的聚类
不需要事先知道聚类的个数
缺陷:
需要预先定义 对象半径和最小距离
如何找到这样的E呢?一种做法是遍历输入点根据Minpts找到最大的E值,再根据每个点的E值,找到一个变化最快的点(求导)。用改点的E作为最终的E。
参考:
http://baike.baidu.com/view/3063170.htm#5
http://xccds1977.blogspot.com/2012/06/r.html
http://en.wikipedia.org/wiki/DBSCAN#Algorithm
http://en.wikipedia.org/wiki/OPTICS_algorithm
http://en.wikipedia.org/wiki/Hierarchical_clustering
-
CN200910237940-异常车速数据的识别方法和装置