文档介绍：... ... 1 什么是 OPTICS 算法在前面介绍的 DBSCAN 算法中,有两个初始参数 E(邻域半径)和 minPts( E 邻域最小点数)需要用户手动设置输入,并且聚类的类簇结果对这两个参数的取值非常敏感,不同的取值将产生不同的聚类结果,其实这也是大多数其他需要初始化参数聚类算法的弊端。为了克服 DBSCAN 算法这一缺点,提出了 OPTICS 算法( Ordering Points to identify the clustering structure )。 OPTICS 并不显示的产生结果类簇,而是为聚类分析生成一个增广的簇排序(比如,以可达距离为纵轴,样本点输出次序为横轴的坐标图),这个排序代表了各样本点基于密度的聚类结构。它包含的信息等价于从一个广泛的参数设置所获得的基于密度的聚类,换句话说,从这个排序中可以得到基于任何参数 E和 minPts 的 DBSCAN 算法的聚类结果。 2 OPTICS 两个概念核心距离: 对象 p的核心距离是指是 p成为核心对象的最小 E’。如果 p不是核心对象,那么p的核心距离没有任何意义。可达距离: 对象 q到对象 p的可达距离是指 p的核心距离和 p与q之间欧几里得距离之间的较大值。如果 p不是核心对象, p和q之间的可达距离没有意义。例如:假设邻域半径 E=2, minPts=3 ,存在点 A(2,3),B(2,4),C(1,4),D(1,3),E(2,2),F(3,2) 点 A为核心对象,在 A的 E领域中有点{A,B,C,D,E,F} ,其中 A的核心距离为 E’=1 , 因为在点 A的 E’邻域中有点{A,B,D,E}>3; 点 F到核心对象点 A的可达距离为,因为 A到 F的欧几里得距离,大于点 A的核心距离 1. 3 算法描述 OPTICS 算法额外存储了每个对象的核心距离和可达距离。基于 OPTICS 产生的排序信息来提取类簇。... ... 算法描述如下: 算法: OPTICS 输入:样本集 D,邻域半径 E,给定点在 E领域内成为核心对象的最小领域点数 MinPts 输出:具有可达距离信息的样本点输出排序方法: 1创建两个队列,有序队列和结果队列。(有序队列用来存储核心对象及其该核心对象的直接可达对象,并按可达距离升序排列;结果队列用来存储样本点的输出次序); 2如果所有样本集 D中所有点都处理完毕,则算法结束。否则,选择一个未处理(即不在结果队列中)且为核心对象的样本点,找到其所有直接密度可达样本点,如过该样本点不存在于结果队列中,则将其放入有序队列中,并按可达距离排序; 3如果有序队列为空,则跳至步骤 2,否则,从有序队列中取出第一个样本点(即可达距离最小的样本点)进行拓展,并将取出的样本点保存至结果队列中, 如果它不存在结果队列当中的话。判断该拓展点是否是核心对象,如果不是,回到步骤 3,否则找到该拓展点所有的直接密度可达点; 判断该直接密度可达样本点是否已经存在结果队列,是则不处理,否则下一步; 如果有序队列中已经存在该直接密度可达点,如果此时新的可达距离小于旧的可达距离,则用新可达距离取代旧可达距离,有序队列重新排序; 如果有序队列中不存在该直接密度可达样本点,则插入该点,并对有序队列重新排序; 4算法结束,输出结果队列中的有序样本点。大家或许会很疑惑,这里不也有输入参数 E和 MinPts 吗?其实这里的 E和 MinPts 只是起到算法辅助作用,也就是说 E和 MinPts 的细微变化并不会影响到样本点的相对输出顺序,这对我们分析聚类结果是没有任何影响。我们采用与先前 DBSCAN 相同的样本点集合, ... ... 对于样本点 a={2,3};b={2,4};c={1,4};d={1,3};e={2,2};f={3,2}; g={8,7};h={8,6};i={7,7};j={7,6};k={8,5}; l={100,2}; // 孤立点 m={8,20};n={8,19};o={7,18};p={7,17};q={8,21}; 并且使用相同的 E=2 MinPts=4 时,输出序列为 1->a: 2->e: 3->b: 4->d: 5->c: 6->f: ------ 7->g: 8->j: 9->k: 10->i: 11->h: ------ 12->n: 13->q: 14->o: ... ... 15->m