先决条件: DBSCAN 集群
OPTICS Clustering 代表Ordering Points To identify Cluster Structure 。它从 DBSCAN 聚类算法中汲取灵感。它为 DBSCAN 聚类的概念增加了两个术语。他们是:-
这种聚类技术不同于其他聚类技术,因为这种技术没有明确地将数据分割成簇。相反,它会生成可达距离的可视化,并使用此可视化对数据进行聚类。
伪代码:
以下伪代码已从算法的维基百科页面中引用。
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 集群: