聚类分析（六）基于密度的聚类算法 — OPTICS

1  什么是OPTICS算法

在前面介绍的DBSCAN算法中，有两个初始参数E（邻域半径）和minPts(E邻域最小点数)需要用户手动设置输入，并且聚类的类簇结果对这两个参数的取值非常敏感，不同的取值将产生不同的聚类结果，其实这也是大多数其他需要初始化参数聚类算法的弊端。

为了克服DBSCAN算法这一缺点，提出了OPTICS算法（Ordering Pointsto 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产生的排序信息来提取类簇。

算法描述如下：

大家或许会很疑惑，这里不也有输入参数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

如图，按照算法，分三个阶段输出了三波值

{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 {

   privateString name; // 样本点名

privatedoubledimensioin[];//样本点的维度

privatedoublecoreDistance;//核心距离，如果该点不是核心对象，则距离为-1

privatedoublereachableDistance;//可达距离

publicDataPoint(){

}

publicDataPoint(DataPointe){

this.name=e.name;

this.dimensioin=e.dimensioin;

this.coreDistance=e.coreDistance;

this.reachableDistance=e.reachableDistance;

}

publicDataPoint(doubledimensioin[],Stringname){

this.name=name;

this.dimensioin=dimensioin;

this.coreDistance=-1;

this.reachableDistance=-1;

}

publicStringgetName(){

returnname;

}

publicvoidsetName(Stringname){

this.name=name;

}

publicdouble[]getDimensioin(){

returndimensioin;

}

publicvoidsetDimensioin(double[]dimensioin){

this.dimensioin=dimensioin;

}

publicdoublegetCoreDistance(){

returncoreDistance;

}

publicvoidsetCoreDistance(doublecoreDistance){

this.coreDistance=coreDistance;

}

publicdoublegetReachableDistance(){

returnreachableDistance;

}

publicvoidsetReachableDistance(doublereachableDistance){

this.reachableDistance=reachableDistance;

}

}

packagecom.optics;

importjava.util.ArrayList;

importjava.util.Collections;

importjava.util.Comparator;

importjava.util.List;

publicclassClusterAnalysis{

classComparatorDpimplementsComparator<DataPoint>{

publicintcompare(DataPointarg0,DataPointarg1){

doubletemp=arg0.getReachableDistance()-arg1.getReachableDistance();

inta=0;

if(temp<0){

a=-1;

}else{

a=1;

}

returna;

}

}

publicList<DataPoint>startAnalysis(List<DataPoint>dataPoints,

doubleradius,intObjectNum){

List<DataPoint>dpList=newArrayList<DataPoint>();

List<DataPoint>dpQue=newArrayList<DataPoint>();

inttotal=0;

while(total<dataPoints.size()){

if(isContainedInList(dataPoints.get(total),dpList)==-1){

List<DataPoint>tmpDpList=isKeyAndReturnObjects(dataPoints.get(total),

dataPoints,radius,ObjectNum);

if(tmpDpList!=null&&tmpDpList.size()>0){

DataPointnewDataPoint=newDataPoint(dataPoints.get(total));

dpQue.add(newDataPoint);

}

}

while(!dpQue.isEmpty()){

DataPointtempDpfromQ=dpQue.remove(0);

DataPointnewDataPoint=newDataPoint(tempDpfromQ);

dpList.add(newDataPoint);

List<DataPoint>tempDpList=isKeyAndReturnObjects(tempDpfromQ,

dataPoints,radius,ObjectNum);

System.out.println(newDataPoint.getName()+":"+newDataPoint.getReachableDistance());

if(tempDpList!=null&&tempDpList.size()>0){

for(inti=0;i<tempDpList.size();i++){

DataPointtempDpfromList=tempDpList.get(i);

intindexInList=isContainedInList(tempDpfromList,

dpList);

intindexInQ=isContainedInList(tempDpfromList,dpQue);

if(indexInList==-1){

if(indexInQ>-1){

intindex=-1;

for(DataPointdataPoint:dpQue){

index++;

if(index==indexInQ){

if(dataPoint.getReachableDistance()>tempDpfromList

.getReachableDistance()){

dataPoint

.setReachableDistance(tempDpfromList

.getReachableDistance());

}

}

}

}else{

dpQue.add(newDataPoint(tempDpfromList));

}

}

}

//TODO：对Q进行重新排序

Collections.sort(dpQue,newComparatorDp());

}

}

System.out.println("------");

total++;

}

returndpList;

}

publicvoiddisplayDataPoints(List<DataPoint>dps){

for(DataPointdp:dps){

System.out.println(dp.getName()+":"+dp.getReachableDistance());

}

}

privateintisContainedInList(DataPointdp,List<DataPoint>dpList){

intindex=-1;

for(DataPointdataPoint:dpList){

index++;

if(dataPoint.getName().equals(dp.getName())){

returnindex;

}

}

return-1;

}

privateList<DataPoint>isKeyAndReturnObjects(DataPointdataPoint,List<DataPoint>dataPoints,doubleradius,intObjectNum){

List<DataPoint>arrivableObjects=newArrayList<DataPoint>();//用来存储所有直接密度可达对象

List<Double>distances=newArrayList<Double>();//欧几里得距离

doublecoreDistance;//核心距离

for(inti=0;i<dataPoints.size();i++){

DataPointdp=dataPoints.get(i);

doubledistance=getDistance(dataPoint,dp);

if(distance<=radius){

distances.add(distance);

arrivableObjects.add(dp);

}

}

if(arrivableObjects.size()>=ObjectNum){

List<Double>newDistances=newArrayList<Double>(distances);

Collections.sort(distances);

coreDistance=distances.get(ObjectNum-1);

for(intj=0;j<arrivableObjects.size();j++){

if(coreDistance>newDistances.get(j)){

if(newDistances.get(j)==0){

dataPoint.setReachableDistance(coreDistance);

}

arrivableObjects.get(j).setReachableDistance(coreDistance);

}else{

arrivableObjects.get(j).setReachableDistance(newDistances.get(j));

}

}

returnarrivableObjects;

}

returnnull;

}

privatedoublegetDistance(DataPointdp1,DataPointdp2){

doubledistance=0.0;

double[]dim1=dp1.getDimensioin();

double[]dim2=dp2.getDimensioin();

if(dim1.length==dim2.length){

for(inti=0;i<dim1.length;i++){

doubletemp=Math.pow((dim1[i]-dim2[i]),2);

distance=distance+temp;

}

distance=Math.pow(distance,0.5);

returndistance;

}

returndistance;

}

publicstaticvoidmain(String[]args){

ArrayList<DataPoint>dpoints=newArrayList<DataPoint>();

double[]a={2,3};

double[]b={2,4};

double[]c={1,4};

double[]d={1,3};

double[]e={2,2};

double[]f={3,2};

double[]g={8,7};

double[]h={8,6};

double[]i={7,7};

double[]j={7,6};

double[]k={8,5};

double[]l={100,2};//孤立点

double[]m={8,20};

double[]n={8,19};

double[]o={7,18};

double[]p={7,17};

double[]q={8,21};

dpoints.add(newDataPoint(a,"a"));

dpoints.add(newDataPoint(b,"b"));

dpoints.add(newDataPoint(c,"c"));

dpoints.add(newDataPoint(d,"d"));

dpoints.add(newDataPoint(e,"e"));

dpoints.add(newDataPoint(f,"f"));

dpoints.add(newDataPoint(g,"g"));

dpoints.add(newDataPoint(h,"h"));

dpoints.add(newDataPoint(i,"i"));

dpoints.add(newDataPoint(j,"j"));

dpoints.add(newDataPoint(k,"k"));

dpoints.add(newDataPoint(l,"l"));

dpoints.add(newDataPoint(m,"m"));

dpoints.add(newDataPoint(n,"n"));

dpoints.add(newDataPoint(o,"o"));

dpoints.add(newDataPoint(p,"p"));

dpoints.add(newDataPoint(q,"q"));

ClusterAnalysisca=newClusterAnalysis();

List<DataPoint>dps=ca.startAnalysis(dpoints,2,4);

ca.displayDataPoints(dps);

}

}