OPTICS聚类

一、基础理解

二、算法原理

1. 已知数据集 D，创建两个队列，有序队列 O 和结果队列 R（有序队列用来存储核心对象及其该核心对象的密度直达对象，并按可达距离升序排列；结果队列用来存储样本点的输出次序。可以把有序队列里面放的理解为待处理的数据，而结果队列里放的是已经处理完的数据）。

2. 如果 D 中所有点都处理完毕或者不存在核心点，则算法结束。否则，选择一个未处理（即不在结果队列 R 中）且为核心对象的样本点 p，首先将 p 放入结果队列 R 中，并从 D 中删除 p。然后找到 D 中 p 的所有密度直达样本点 x，计算 x 到 p 的可达距离，如果 x 不在有序队列 O 中，则将 x 以及可达距离放入 O 中，若 x 在 O 中，则如果 x 新的可达距离更小，则更新 x 的可达距离，最后对 O 中数据按可达距离从小到大重新排序。

3. 如果有序队列 O 为空，则回到步骤 2，否则取出 O 中第一个样本点 y（即可达距离最小的样本点），放入 R 中，并从 D 和 O 中删除 y。如果 y 不是核心对象，则重复步骤 3（即找 O 中剩余数据可达距离最小的样本点）；如果 y 是核心对象，则找到 y 在 D 中的所有密度直达样本点，并计算到 y 的可达距离，然后按照步骤 2 将所有 y 的密度直达样本点更新到 O 中。

4. 重复步骤 2、3，直到算法结束。最终可以得到一个有序的输出结果，以及相应的可达距离。

三、数据实例

3.1、手动推导

1. 计算所有的核心对象和核心距离，因为 eps 为无穷大，则显然每个样本点都是核心对象。因为 min_samples=2，则每个核心对象的核心距离就是离自己最近样本点到自己的距离（样本点自身也是邻域元素之一），具体如上表所示。

2. 随机在 D 中选择一个核心对象，假设选择 0 号元素，将 0 号元素放入 R 中，并从 D 中删除。因为 eps = inf，则其他所有样本点都是 0 号元素的密度直达对象，计算其他所有元素到 0 号元素的可达距离（实际就是计算所有元素到 0 号元素的欧氏距离，如表 1 第一次可达距离），并按可达距离排序，添加到序列 O 中。

3. 此时 O 中可达距离最小的元素是 1 号元素，取出 1 号元素放入 R ，并从 D 和 O 中删除，因为 1 号元素是核心对象，找到 1 号元素在 D 中的所有密度直达对象（剩余的所有样本点），并计算可达距离，同时更新 O（如表 1 第二次可达距离）。

4. 此时 O 中可达距离最小的元素是 3 号元素，取出 3 号元素放入 R ，并从 D 和 O 中删除，因为 3 号元素是核心对象，找到 3 号元素在 D 中的所有密度直达对象（剩余的所有样本点），并计算可达距离，同时更新 O（如表 1 第三次可达距离）。

5. 此时 O 中可达距离最小的元素是 6 号元素，取出 6 号元素放入 R ，并从 D 和 O 中删除，因为 6 号元素是核心对象，找到 6 号元素在 D 中的所有密度直达对象（剩余的所有样本点），并计算可达距离，同时更新 O（如表 1 第四次可达距离）。

6. 此时 O 中可达距离最小的元素是 5 号元素，取出 5 号元素放入 R ，并从 D 和 O 中删除，因为 5 号元素是核心对象，找到 5 号元素在 D 中的所有密度直达对象（剩余的所有样本点），并计算可达距离，同时更新 O（如表 1 第五次可达距离）。注意本次计算的 4 号元素到 5 号元素的可达距离是 5.10，大于 5.0，因此不更新 4 号元素的可达距离（此处存疑）。

7. 此时 O 中可达距离最小的元素是 2 号元素，取出 2 号元素放入 R ，并从 D 和 O 中删除，因为 2 号元素是核心对象，找到 2 号元素在 D 中的所有密度直达对象（剩余的所有样本点），并计算可达距离，同时更新 O（如表 1 第六次可达距离）。

8. 此时 O 中可达距离最小的元素是 4 号元素，取出 4 号元素放入 R ，并从 D 和 O 中删除，因为 D 已空，O 也已空，程序结束。根据表 1，最终的结果序列 R 的元素索引输出顺序为：0、1、3、6、5、2、4，可达距离如表 1 最后一行所示。

from cmath import inf
from math import sqrt
import random
import matplotlib.pyplot as plt


eps = inf   # 默认核心距离无穷大，则每个点都是核心点
min_sample = 2   # 默认最小邻域样本数为2，核心距离就是离自己最近样本点到自己的距离（样本点自身也是邻域元素之一）
D = [[1, 2], [2, 5],  [8, 7], [3, 6],  [8, 8], [7, 3], [4,5]]
print("原数据D：", D)
O = [] # 排序队列
R = [] # 结果队列
S = [] # 可达距离

R.append(D.pop(random.randint(0,6)))    # 第一轮随机取
print("第1轮R：", R)
nums = 1
while True:
    if len(D)<=0:
        break
    else:
        O = [] # 排序队列
        for x in D:   # 计算R中的点与D中其他点的距离，并按距离升序
            x_d = sqrt((R[-1][0] - x[0])**2 + (R[-1][1] - x[1])**2)
            O.append([x, x_d])
            O = sorted(O, key=lambda x: x[1], reverse=False)
        print(f"第{nums}轮O：", O)
        S.append(round(O[0][1],2))
        print(f"第{nums}轮S：", S)
        D.remove(O[0][0])   # 将距离最小的点从D中删除
        print(f"第{nums+1}轮D：", D)
        R.append(O[0][0])   # 将距离最小的点加到R中
        print(f"第{nums+1}轮R：", R)
        nums+=1


plt.plot(range(len(S)), S, 'ro-')
plt.show()

3.2、使用算法验证

from sklearn.cluster import OPTICS
import numpy as np

X = np.array([[1, 2], [2, 5],  [8, 7],[3, 6],  [8, 8], [7, 3], [4,5]])

clustering = OPTICS(min_samples=2).fit(X)


print(clustering.core_distances_)
'''
array([3.16227766, 1.41421356, 1.  , 1.41421356, 1.  ,3.60555128, 1.41421356])
'''

print(clustering.ordering_)
'''
array([0, 1, 3, 6, 5, 2, 4])
'''

print(clustering.reachability_)
'''
array([inf, 3.16227766, 4.12310563, 1.41421356, 1.        ,3.60555128, 1.41421356])
'''

print(clustering.labels_)
'''
array([0, 0, 1, 0, 1, 0, 0])
'''

import sklearn

db = sklearn.cluster.DBSCAN(eps=3.8,min_samples=2).fit(X)
db.labels_

## array([0, 0, 1, 0, 1, 0, 0])

四、API调用

4.1、算法参数详解

from sklearn.cluster import OPTICS

OPTICS(*, min_samples=5, max_eps=inf, metric='minkowski', p=2, metric_params=None, cluster_method='xi', eps=None, xi=0.05, predecessor_correction=True, min_cluster_size=None, algorithm='auto', leaf_size=30, n_jobs=None)

4.2、实际调用案例

五、推荐阅读