聚类分析（五）——基于密度的聚类算法OPTICS 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.1 判断该拓展点是否是核⼼对象，如果不是，回到步骤3，否则找到该
拓展点所
有的直接密度可达点；
3.2 判断该直接密度可达样本点是否已经存在结果队列，是则不处理，
否则下⼀
步；
3.2 如果有序队列中已经存在该直接密度可达点，如果此时新的可达距
离⼩于旧
的可达距离，则⽤新可达距离取代旧可达距离，有序队列重新排序；
3.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:1.0
2->e:1.0
3->b:1.0
4->d:1.0
团总支5->c:1.4142135623730951
6->f:1.4142135623730951
------
7->g:1.4142135623730951
8->j:1.4142135623730951
9->k:1.4142135623730951
10->i:1.4142135623730951
11->h:1.4142135623730951
------
12->n:2.0
13->q:2.0
14->o:2.0
15->m:2.0
聚类分析（六）基于密度的聚类算法 <wbr>鈥 <wbr>OPTICS
如图，按照算法，分三个阶段输出了三波值
{a,e,b,d,c,f} ,{g,j,k,I,h},{n,q,o,m}
这和DBSCAN的类簇结果是⼀样的。不仅如此，我们通过分析有序图还能直接得到当参数
E=1.5,minPts=4时DBSCAN的类簇结果，只要在坐标图中找到Y值⼩于1.5的样本点即可，只有两类{a,
e,b,d,c,f} ,{g,j,k,I,h}，其他点被认为是孤⽴点，和DBSCAN聚类算法取E=1.5,minPts=4时的结果⼀致。
所以说，这个OPTICS聚类算法所得的簇排序信息等价于⼀个⼴泛的参数设置所获得的基于密度的聚类结果。
具体实现算法如下：
package com.optics;
public class DataPoint {
private String name; // 样本点名
private double dimensioin[]; // 样本点的维度
private double coreDistance; //核⼼距离，如果该点不是核⼼对象，则距离为-1
private double reachableDistance; //可达距离
public DataPoint(){
}
public DataPoint(DataPoint e){
this.name=e.name;
this.dimensioin=e.dimensioin;
}
public DataPoint(double dimensioin[],String name){
this.name=name;
this.dimensioin=dimensioin;
}
public String getName() {
return name;
}
public void tName(String name) {
this.name = name;
}
public double[] getDimensioin() {
return dimensioin;
}
public void tDimensioin(double[] dimensioin) {
this.dimensioin = dimensioin;
}
public double getCoreDistance() {
return coreDistance;
}
public void tCoreDistance(double coreDistance) {
}
public double getReachableDistance() {
return reachableDistance;
}
public void tReachableDistance(double reachableDistance) {
}
}
package com.optics;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;
public class ClusterAnalysis {
class ComparatorDp implements Comparator<DataPoint>{
public int compare(DataPoint arg0, DataPoint arg1) {
double ReachableDistance()-ReachableDistance(); int a = 0;
if (temp < 0) {
a = -1;
} el {
a = 1;
}
return a;
}
}
public List<DataPoint> startAnalysis(List<DataPoint> dataPoints,
double radius, int ObjectNum) {
List<DataPoint> dpList = new ArrayList<DataPoint>();
List<DataPoint> dpQue = new ArrayList<DataPoint>();
乡村旅游论文
int total = 0;
while (total < dataPoints.size()) {
if ((total), dpList) == -1 ) {
List<DataPoint> tmpDpList = (total),
dataPoints, radius, ObjectNum);
if(tmpDpList != null && tmpDpList.size() > 0){
DataPoint newDataPoint=new (total));
dpQue.add(newDataPoint);
}
}
while (!dpQue.isEmpty()) {
DataPoint tempDpfromQ = ve(0);
DataPoint newDataPoint=new DataPoint(tempDpfromQ);
dpList.add(newDataPoint);
List<DataPoint> tempDpList = isKeyAndReturnObjects(tempDpfromQ,
dataPoints, radius, ObjectNum);
System.out.Name()+":"+ReachableDistance()); if (tempDpList != null && tempDpList.size() > 0) {
for (int i = 0; i < tempDpList.size(); i++) {
DataPoint tempDpfromList = (i);
int indexInList = isContainedInList(tempDpfromList,
dpList);
int indexInQ = isContainedInList(tempDpfromList, dpQue);
if (indexInList == -1) {
if (indexInQ > -1) {
int index = -1;
for (DataPoint dataPoint : dpQue) {
奔的意思index++;
if (index == indexInQ) {
if (ReachableDistance() > tempDpfromList
.
getReachableDistance()) {
dataPoint
.tReachableDistance(tempDpfromList
.getReachableDistance());
}
普通话二甲什么水平
}
}
} el {
dpQue.add(new DataPoint(tempDpfromList));
}
}
}
// TODO：对Q进⾏重新排序
Collections.sort(dpQue, new ComparatorDp());
}
}
实习成绩System.out.println("------");
total++;
}
return dpList;
}
public void displayDataPoints(List<DataPoint> dps){
for(DataPoint dp: dps){
System.out.Name()+":"+dp.getReachableDistance());
}
}
