OPTICS

一、直观理解：不急着定一个半径，先排出“密度可达顺序图”

DBSCAN 要求全局统一的 $\varepsilon$，但真实数据常有疏有密。OPTICS（Ordering Points To Identify the Clustering Structure）不急着输出唯一划分，而是生成样本的一个处理顺序和每个点的可达距离，画成可达图（reachability plot）：

• 山谷 = 密集簇；
• 山峰 = 簇边界或噪声；
• 不同深度的谷对应不同密度的簇。

像用等高线看地形：同一张图能读出高原上的小湖与盆地里的大湖，而不必先规定唯一水位线。

二、适用场景与优缺点

类型	说明
适用场景	簇密度差异大；想探索多尺度结构；DBSCAN 难选单一 $\varepsilon$；需要可达图展示。
核心优点	对 $\varepsilon$ 上界不那么苛刻；揭示层次密度结构；可从中提取类似 DBSCAN 的划分。
局限与缺点	概念与实现比 DBSCAN 重；提取簇仍需规则/参数；高维同样困难；MATLAB 版本函数可用性因工具箱而异。

三、核心原理

核心概念：

• 核心距离 $\mathrm{core\text{-}dist}(p)$：使 $p$ 成为核心点的最小半径（第 MinPts 近邻距离）；
• 可达距离 $\mathrm{reach\text{-}dist}(p,o)=\max\{\mathrm{core\text{-}dist}(o), d(o,p)\}$。

算法维护种子优先队列，按可达距离扩张，生成有序序列。可达图横轴为该顺序，纵轴为可达距离。在图上设阈值切割，或用 $\xi$ 方法自动提取簇，可得到类似多 $\varepsilon$ 的 DBSCAN 结果族。

当数据密度均匀时，OPTICS 提取结果接近 DBSCAN。

四、关键决策

决策点	建议
MinPts	同 DBSCAN，控制平滑与最小簇
$\varepsilon$ 上界	可取较大值以覆盖主结构；过小会截断
提簇方式	可达图人工谷底 / 阈值 / $\xi$ 方法
标准化	需要
与 DBSCAN	先 OPTICS 探结构，再定 DBSCAN 参数

五、MATLAB 示例

部分 MATLAB 版本提供 optics 或可通过 File Exchange / 自写。下面给出可达距离序的教学实现骨架与 DBSCAN 对照，便于论文复现核心思想。

rng(7);
X1 = 0.3*randn(40,2) + [0 0];          % 密簇
X2 = 1.2*randn(50,2) + [6 0];          % 疏簇
X = [X1; X2; 4*randn(10,2)];           % 噪声
Xz = zscore(X);
MinPts = 5;

% --- 简化 OPTICS：产出序与可达距离 ---
function [order, reach] = optics_simple(X, MinPts, epsCap)
    n = size(X,1);
    dist = pdist2(X, X);
    coreDist = zeros(n,1);
    for i = 1:n
        s = sort(dist(i,:));
        coreDist(i) = s(MinPts);  % 含自身则用 MinPts，严格实现需注意下标
    end
    processed = false(n,1);
    reach = inf(n,1);
    order = zeros(n,1);
    seeds = [];  % 将存 [idx, reach]
    t = 0;
    for i = 1:n
        if processed(i), continue; end
        t = t + 1; order(t) = i; processed(i) = true;
        if coreDist(i) > epsCap, continue; end
        % 扩展
        cand = find(dist(i,:) <= epsCap);
        for j = cand
            if processed(j), continue; end
            r = max(coreDist(i), dist(i,j));
            if r < reach(j)
                reach(j) = r;
            end
        end
        % 未处理点按可达距离优先（朴素实现）
        while true
            un = find(~processed);
            if isempty(un), break; end
            [rval, k] = min(reach(un));
            if isinf(rval), break; end
            j = un(k);
            t = t + 1; order(t) = j; processed(j) = true;
            if coreDist(j) > epsCap, continue; end
            cand = find(dist(j,:) <= epsCap);
            for p = cand
                if processed(p), continue; end
                r = max(coreDist(j), dist(j,p));
                if r < reach(p)
                    reach(p) = r;
                end
            end
        end
    end
    order = order(1:t);
    % 序上首点可达距离可定义为 coreDist 或 0
    reachPlot = reach(order);
    reachPlot(1) = 0;
end

epsCap = 2.0;
[order, reachAll] = optics_simple(Xz, MinPts, epsCap);
rp = reachAll(order);
rp(isinf(rp)) = max(rp(~isinf(rp))) * 1.2;

figure;
bar(rp, 1);
xlabel("OPTICS 顺序"); ylabel("可达距离");
title("可达图：谷=簇，峰=分隔/噪声");

% 用阈值从可达图提取簇（演示）
thresh = quantile(rp(rp>0), 0.4);
labels = zeros(size(Xz,1),1);
cid = 0; inCluster = false;
for t = 1:numel(order)
    if rp(t) <= thresh
        if ~inCluster
            cid = cid + 1; inCluster = true;
        end
        labels(order(t)) = cid;
    else
        inCluster = false; % 峰视为分隔，点可标噪声 0
    end
end

figure; gscatter(Xz(:,1), Xz(:,2), labels);
title("由 OPTICS 可达图阈值提取的簇");

% DBSCAN 对照
idx = dbscan(Xz, 0.5, MinPts);
figure; gscatter(Xz(:,1), Xz(:,2), idx);
title("DBSCAN 对照");

生产环境应使用经过验证的库实现（边界细节、种子队列、$\xi$ 提簇）。

六、如何解释结果

1. 可达图形态：几个主要谷、深浅差异对应密度差异；
2. 阈值/ξ：如何从序导出平面划分；
3. 与 DBSCAN：单一 $\varepsilon$ 是否无法同时保住密疏两簇；
4. 噪声：高峰点业务含义；
5. 报告：MinPts、$\varepsilon$ 上界、提簇规则、图与簇规模。

七、常见误区

1. 把 OPTICS 只当成“慢一点的 DBSCAN”

核心产出是序与可达图，划分是后处理。

2. MinPts 过小导致图锯齿

可达图噪声大，谷难辨。

3. 阈值乱切

应结合图的视觉结构与业务最小簇规模。

4. 高维直接上

同所有密度方法，先降维。

5. 自写实现不校验

与标准库在玩具数据上对照。

八、小结

OPTICS 用核心距离与可达距离生成点序和可达图，揭示多密度尺度下的聚类结构，弥补 DBSCAN 单一邻域半径的局限。

当 k-距离图或业务显示“有的团很紧、有的团很松”时，优先用 OPTICS 做探索，再导出可汇报的簇标签。