ML算法：OPTICS聚类说明详细指南

先决条件： DBSCAN集群

OPTICS Clustering代表确定集群结构的订购点。它从DBSCAN聚类算法中获得启发。它为DBSCAN群集的概念增加了两个术语。他们是：-

核心距离：这是将给定点分类为核心点所需的最小半径。如果给定的点不是核心点, 则其核心距离是不确定的。

可达距离：相对于另一个数据点q(Let)定义。点p和q之间的可达距离是p的核心距离和p和q之间的欧几里德距离(或其他距离度量)中的最大值。请注意, 如果q不是核心点, 则未定义可达距离。

从某种意义上说, 该聚类技术不会将数据显式分段为聚类, 因此它与其他聚类技术不同。相反, 它会生成可到达距离的可视化, 并使用此可视化对数据进行聚类。

伪代码：

以下伪代码已从维基百科页面算法的

OPTICS(DB, eps, MinPts)

    #Repeating the process for all points in the database
    for each point pt of DB

       #Initializing the reachability distance of the selected point
       pt.reachable_dist = UNDEFINED
    for each unprocessed point pt of DB

       #Getting the neighbours of the selected point
       #according to the definitions of epsilon and
       #minPts in DBSCAN
       Nbrs = getNbrs(pt, eps)

       mark pt as processed
       output pt to the ordered list

       #Checking if the selected point is not noise
       if (core_dist(pt, eps, Minpts) != UNDEFINED)

          #Initializing a priority queue to get the closest data point
          #in terms of Reachability distance
          Seeds = empty priority queue

          #Calling the update function
          update(Nbrs, pt, Seeds, eps, Minpts)

          #Repeating the process for the next closest point
          for each next q in Seeds
             Nbrs' = getNbrs(q, eps)
             mark q as processed
             output q to the ordered list
             if (core_dist(q, eps, Minpts) != UNDEFINED)
                update(Nbrs', q, Seeds, eps, Minpts)

下面给出了用于更新功能的伪代码：

update(Nbrs, pt, Seeds, eps, MinPts)

    #Calculating the core distance for the given point
    coredist = core_dist(pt, eps, MinPts)

    #Updating the Reachability distance for each neighbour of p
    for each obj in Nbrs
       if (obj is not processed)
          new_reach_distance = max(coredist, dist(pt, obj))

          #Checking if the neighbour point is in seeds
          if (obj.reachable_dist == UNDEFINED)

              #Updation step
              obj.reachabled_dist = new_reach_distance
              Seeds.insert(obj, new_reach_distance)
          else               
              if (new_reach_distance <obj.reachable_dist)

                 #Updation step
                 o.reachable_dist = new_reach_distance
                 Seeds.move-up(obj, new_reach_distance)

OPTICS集群与DBSCAN集群：

1. 内存成本：OPTICS群集技术需要更多的内存, 因为它维护一个优先级队列(最小堆)来确定下一个数据点(就可达距离而言)与当前正在处理的点最接近。它也需要更多的计算能力, 因为最近的邻居查询比DBSCAN中的半径查询更复杂。
2. 参数更少：OPTICS聚类技术不需要维护epsilon参数, 仅在上面的伪代码中给出以减少花费的时间。这导致减少了参数调整的分析过程。

3. 此技术不会将给定的数据隔离到群集中。它仅产生可到达距离图, 并且在程序员的解释下相应地将点聚类。

首先, 你的面试准备可通过以下方式增强你的数据结构概念：Python DS课程。

---