|
OPTICS (Ordering points to Identify the Clustering Structure)在论文OPTICS: Ordering Points To Identify the Clustering Structure中提出。这个算法也在wiki中有。 源代码从buildClusterer开始看： database = databaseForName(getDatabase_Type(), filteredInstances); for (int i = 0; i < database.getInstances().numInstances(); i ) { DataObject dataObject = dataObjectForName( getDatabase_distanceType(), database.getInstances() .instance(i), Integer.toString(i), database); database.insert(dataObject); } database.setMinMaxValues(); 这部分在DBScan中讲过了。 UpdateQueue seeds = new UpdateQueue();
/** OPTICS-Begin */ Iterator iterator = database.dataObjectIterator(); while (iterator.hasNext()) { DataObject dataObject = (DataObject) iterator.next(); if (!dataObject.isProcessed()) { expandClusterOrder(dataObject, seeds); } } 对对样本进行循环，如果没处理过，调用expandClusterOrder，expandClusterOrder调用的第一个函数coreDistance： /** * Calculates the coreDistance for the specified DataObject. * The returned list contains three elements: * At index=0 --> list with all k next-neighbours; * At index=1 --> list with all dataObjects within epsilon; * At index=2 --> coreDistance as Double-value */ public List coreDistance(int minPoints, double epsilon, DataObject dataObject) { List list = k_nextNeighbourQuery(minPoints, epsilon, dataObject);
if (((List) list.get(1)).size() < minPoints) { list.add(new Double(DataObject.UNDEFINED)); return list; } else { List nextNeighbours_List = (List) list.get(0); PriorityQueueElement priorityQueueElement = (PriorityQueueElement)nextNeighbours_List .get(nextNeighbours_List.size() - 1); if (priorityQueueElement.getPriority() <= epsilon) { list.add(new Double(priorityQueueElement.getPriority())); return list; } else { list.add(new Double(DataObject.UNDEFINED)); return list; } } } k_nextNeighbourQuery返回的list中index=0是所有的k个邻居，index=1是所有epsilon邻域中的点。如果list.get(1).size()小于minPts，也就是它不是一个核心点，否则就是一个核心点，另外nextNeighbours_List是一个优先队列，所以它最后一个元素就是最远的点。
expandClusterOrder前一部分代码为： List list = database.coreDistance(getMinPoints(), getEpsilon(), dataObject); List epsilonRange_List = (List) list.get(1); dataObject.setReachabilityDistance(DataObject.UNDEFINED); dataObject.setCoreDistance(((Double) list.get(2)).doubleValue()); dataObject.setProcessed(true);
resultVector.addElement(dataObject); 得到coreDistance得到的结果，初始化一些变量。 if (dataObject.getCoreDistance() != DataObject.UNDEFINED) { update(seeds, epsilonRange_List, dataObject); while (seeds.hasNext()) { UpdateQueueElement updateQueueElement = seeds.next(); DataObject currentDataObject = (DataObject) updateQueueElement .getObject(); currentDataObject.setReachabilityDistance(updateQueueElement .getPriority()); List list_1 = database.coreDistance(getMinPoints(), getEpsilon(), currentDataObject); List epsilonRange_List_1 = (List) list_1.get(1); currentDataObject.setCoreDistance(((Double) list_1.get(2)) .doubleValue()); currentDataObject.setProcessed(true);
resultVector.addElement(currentDataObject);
if (currentDataObject.getCoreDistance() != DataObject.UNDEFINED) { update(seeds, epsilonRange_List_1, currentDataObject); } } } 先看一下update函数： private void update(UpdateQueue seeds, List epsilonRange_list, DataObject centralObject) { double coreDistance = centralObject.getCoreDistance(); double new_r_dist = DataObject.UNDEFINED;
for (int i = 0; i < epsilonRange_list.size(); i ) { EpsilonRange_ListElement listElement = (EpsilonRange_ListElement) epsilonRange_list.get(i); DataObject neighbourhood_object = listElement.getDataObject(); if (!neighbourhood_object.isProcessed()) { new_r_dist = Math.max(coreDistance, listElement.getDistance()); seeds.add(new_r_dist, neighbourhood_object, neighbourhood_object.getKey()); } } } 这里是判断epsilon领域中的点与centralObject的距离，这里seeds中保持的就是可达距离(reachability-distance)：
中文版的《数据挖掘：概念与技术》第275页，英文版420页有一个例子可以讲清core-distance和reachability-distance的关系。 回到expandClusterOrder中，下面的代码很像是DBScan中的，从一个邻居开始，去扩展这个簇。 先翻译一段wiki中的解释： 使用可达图（reachability-plot），簇的层次结构很容易得到，在下图中是一个2维露天，x轴是排过序的点，y轴是可达距离，因为属于一个簇的点s到它们最近的邻居有较低的可达距离值，所以簇在可达图中以谷(valley，by the way，数据挖掘那本书里的翻译有问题)的形式出现，谷越深，簇越紧密（denser）。 下图中展示了这一概念，在它的上半部分，一个显示了一部分的人工2维数据集。它的下半部分显示了用OPTICS算法计算的可达图，黑色的连线把簇与它对应的谷连起来了。红色的横线表示如何得到一个簇，红线所穿过的谷都是一个簇。如果这个线向下移，就会有更多的簇合并，特别是最上面的簇，即那些变密度特征。 在这幅图中蓝点被视为噪音，在可达图中没有关于它们的谷。
现在的问题是这个图是怎么来的，通过什么方式排的序呢？还是看expandClusterOrder函数，resultVector是最终结果。而且每次都是从seeds中取一个点，seeds是个优先队列，它以升序排序，也就是每次取的都是最小的可达距离，这样就形成了谷状的结构，因为后来越来越找不到一个簇可达距离小的点的了。
|
|
|
