柚子快報(bào)激活碼778899分享：算法筆記：OPTICS 聚類

http://yzkb.51969.com/

1 基本介紹

OPTICS(Ordering points to identify the clustering structure)是一基于密度的聚類算法

OPTICS算法是DBSCAN的改進(jìn)版本

在DBCSAN算法中需要輸入兩個(gè)參數(shù)：???和 MinPts?，選擇不同的參數(shù)會(huì)導(dǎo)致最終聚類的結(jié)果千差萬別，因此DBCSAN對(duì)于輸入?yún)?shù)過于敏感?機(jī)器學(xué)習(xí)筆記：DBSCAN_dbscan參數(shù)選取-CSDN博客OPTICS算法的提出就是為了幫助DBSCAN算法選擇合適的參數(shù)，降低輸入?yún)?shù)的敏感度

OPTICS主要針對(duì)輸入?yún)?shù)?過敏感做的改進(jìn)OPTICS和DBSCNA的輸入?yún)?shù)一樣（ ? 和 MinPts? ），雖然OPTICS算法中也需要兩個(gè)輸入?yún)?shù)，但該算法對(duì) ? 輸入不敏感（一般將 ? 固定為無窮大）【不太清楚為什么不直接不輸入ε呢？】同時(shí)該算法中并不顯式的生成數(shù)據(jù)聚類，只是對(duì)數(shù)據(jù)集合中的對(duì)象進(jìn)行排序，得到一個(gè)有序的對(duì)象列表

通過該有序列表，可以得到一個(gè)決策圖通過決策圖可以不同 ? 參數(shù)的數(shù)據(jù)集中檢測(cè)簇集，即：先通過固定的 MinPts? 和無窮大的 ? 得到有序列表，然后得到?jīng)Q策圖，通過決策圖可以知道當(dāng) ? 取特定值時(shí)（比如 ?=3 ）數(shù)據(jù)的聚類情況。

1.1 和DBSCAN相似的概念

ε、minPts、核心點(diǎn)、邊緣點(diǎn)、噪點(diǎn)、密度直達(dá)（直接密度可達(dá)）、密度可達(dá)、密度相連 這些概念可見“機(jī)器學(xué)習(xí)筆記：DBSCAN_dbscan參數(shù)選取-CSDN博客

?1.2 OPTICS新的定義

1.2.1 核心距離

換句話說，如果x不是核心點(diǎn)，那么cd(x)就沒有意義

1.2.2 可達(dá)距離

也是，如果x不是核心點(diǎn)，那么rd(y,x)沒有意義如果y在x的ε領(lǐng)域內(nèi)，那么rd(y,x)=cd(x)；如果在x的ε領(lǐng)域外，那么就是d(y,x)

1.3 算法思想

假設(shè)數(shù)據(jù)集為，OPTICS算法的目標(biāo)是輸出一個(gè)有序排列，以及每個(gè)元素的兩個(gè)屬性值：核心距離，可達(dá)距離。

1.3.1 OPTICS算法的數(shù)據(jù)結(jié)構(gòu)

1.4 算法流程

輸入：數(shù)據(jù)集，領(lǐng)域參數(shù)ε（一般等于∞），MinPts

創(chuàng)建兩個(gè)隊(duì)列，有序隊(duì)列O和結(jié)果隊(duì)列R

有序隊(duì)列用來存儲(chǔ)核心對(duì)象及其該核心對(duì)象的密度直達(dá)對(duì)象，并按可達(dá)距離升序排列

理解為待處理的數(shù)據(jù)結(jié)果隊(duì)列用來存儲(chǔ)樣本點(diǎn)的輸出次序

已經(jīng)處理完的數(shù)據(jù)如果D中所有點(diǎn)都處理完畢或者不存在核心點(diǎn)，則算法結(jié)束。否則：

選擇一個(gè)未處理（即不在結(jié)果隊(duì)列R中）且為核心對(duì)象的樣本點(diǎn) p將 p 放入結(jié)果隊(duì)列R中，并從X中刪除 p找到 X 中 p 的所有密度直達(dá)樣本點(diǎn) x，計(jì)算 x 到 p 的可達(dá)距離

如果 x 不在有序隊(duì)列O 中，則將 x 以及可達(dá)距離放入 O 中若 x 在O中，則如果 x 新的可達(dá)距離更小，則更新 x 的可達(dá)距離最后對(duì)O中數(shù)據(jù)按可達(dá)距離從小到大重新排序。如果有序隊(duì)列O為空，則回到步驟2，否則：

取出O 中第一個(gè)樣本點(diǎn) y（即可達(dá)距離最小的樣本點(diǎn)），放入 R 中從 D 和 O 中刪除 y如果 y 不是核心對(duì)象，則重復(fù)步驟 3（即找 O 中剩余數(shù)據(jù)可達(dá)距離最小的樣本點(diǎn)）如果 y 是核心對(duì)象，則

找到 y 在 D 中的所有密度直達(dá)樣本點(diǎn)計(jì)算到 y 的可達(dá)距離所有 y 的密度直達(dá)樣本點(diǎn)更新到 O 中對(duì)O中數(shù)據(jù)按可達(dá)距離從小到大重新排序。重復(fù)步驟2、3，直到算法結(jié)束。最終可以得到一個(gè)有序的輸出結(jié)果，以及相應(yīng)的可達(dá)距離。

1.5 舉例

樣本數(shù)據(jù)集為：D = {[1, 2], [2, 5], ?[8, 7], [3, 6], ?[8, 8], [7, 3], [4,5]}

假設(shè)eps = inf，min_samples=2，則數(shù)據(jù)集D在OPTICS算法上的執(zhí)行步驟如下：

計(jì)算所有的核心對(duì)象和核心距離

因?yàn)?eps 為無窮大，則顯然每個(gè)樣本點(diǎn)都是核心對(duì)象因?yàn)?min_samples=2，則每個(gè)核心對(duì)象的核心距離就是離自己最近樣本點(diǎn)到自己的距離（樣本點(diǎn)自身也是鄰域元素之一）

索引0123456元素(1, 2)(2, 5)(8, 7)(3, 6)(8, 8)(7, 3)(4, 5)核心距離3.161.411.01.411.03.611.41隨機(jī)在 D 中選擇一個(gè)核心對(duì)象

假設(shè)選擇?0 號(hào)元素，將 0 號(hào)元素放入 R 中，并從 D 中刪除因?yàn)?eps = inf，則其他所有樣本點(diǎn)都是 0 號(hào)元素的密度直達(dá)對(duì)象計(jì)算其他所有元素到 0 號(hào)元素的可達(dá)距離（計(jì)算所有元素到 0 號(hào)元素的歐氏距離)按可達(dá)距離排序，添加到序列 O 中此時(shí)D{1,2,3,4,5,6},R{0},O{1,6,3,5,2,4}

索引0123456核心對(duì)象元素(1, 2)(2, 5)(8, 7)(3, 6)(8, 8)(7, 3)(4, 5)核心距離3.161.411.01.411.03.611.41第一次可達(dá)距離--3.168.604.479.216.084.240此時(shí) O 中可達(dá)距離最小的元素是 1 號(hào)元素

取出 1 號(hào)元素放入 R ，并從 D 和 O?中刪除因?yàn)?1 號(hào)元素是核心對(duì)象，找到?1?號(hào)元素在 D 中的所有密度直達(dá)對(duì)象（剩余的所有樣本點(diǎn)），并計(jì)算可達(dá)距離同時(shí)更新 O此時(shí) D{2,3,4,5,6} R{0,1} O{3,6,5,2,4}

索引0123456核心對(duì)象元素(1, 2)(2, 5)(8, 7)(3, 6)(8, 8)(7, 3)(4, 5)核心距離3.161.411.01.411.03.611.41第二次可達(dá)距離----6.321.416.705.382.01此時(shí) O 中可達(dá)距離最小的元素是 3?號(hào)元素

取出 3?號(hào)元素放入 R ，并從 D 和 O 中刪除因?yàn)?3?號(hào)元素是核心對(duì)象，找到 3?號(hào)元素在 D 中的所有密度直達(dá)對(duì)象（剩余的所有樣本點(diǎn)），并計(jì)算可達(dá)距離同時(shí)更新 O此時(shí)D{2,4,5,6} R{0,1,3} O{6,5,2,4}

索引0123456核心對(duì)象元素(1, 2)(2, 5)(8, 7)(3, 6)(8, 8)(7, 3)(4, 5)核心距離3.161.411.01.411.03.611.41第三次可達(dá)距離----5.09--5.395.01.413此時(shí) O 中可達(dá)距離最小的元素是 6?號(hào)元素

取出 6?號(hào)元素放入 R ，并從 D 和 O 中刪除因?yàn)?6?號(hào)元素是核心對(duì)象，找到 6?號(hào)元素在 D 中的所有密度直達(dá)對(duì)象（剩余的所有樣本點(diǎn)），并計(jì)算可達(dá)距離,同時(shí)更新 O此時(shí)D{2,4,5},R{0,1,3,6},O(5,2,4}

索引0123456核心對(duì)象元素(1, 2)(2, 5)(8, 7)(3, 6)(8, 8)(7, 3)(4, 5)核心距離3.161.411.01.411.03.611.41第四次可達(dá)距離----4.47--5.03.61--6此時(shí) O 中可達(dá)距離最小的元素是 5 號(hào)元素

取出 5 號(hào)元素放入 R ，并從 D 和 O 中刪除因?yàn)?5 號(hào)元素是核心對(duì)象，找到 5 號(hào)元素在 D 中的所有密度直達(dá)對(duì)象（剩余的所有樣本點(diǎn)），并計(jì)算可達(dá)距離，同時(shí)更新 O。注意本次計(jì)算的4號(hào)元素到5號(hào)元素的可達(dá)距離是5.10，大于5.0，因此不更新4號(hào)元素的可達(dá)距離此時(shí)D{2,4}R{0,1,3,6,5} O(2,4)

索引0123456核心對(duì)象元素(1, 2)(2, 5)(8, 7)(3, 6)(8, 8)(7, 3)(4, 5)核心距離3.161.411.01.411.03.611.41第五次可達(dá)距離----4.12-- 5.0 (5.10) ----5此時(shí) O 中可達(dá)距離最小的元素是 2?號(hào)元素

取出 2?號(hào)元素放入 R ，并從 D 和 O 中刪除因?yàn)?2?號(hào)元素是核心對(duì)象，找到 2?號(hào)元素在 D 中的所有密度直達(dá)對(duì)象，并計(jì)算可達(dá)距離，同時(shí)更新 O

索引0123456核心對(duì)象元素(1, 2)(2, 5)(8, 7)(3, 6)(8, 8)(7, 3)(4, 5)核心距離3.161.411.01.411.03.611.41第六次可達(dá)距離--------1.0----2

所以最后的R:(0,1,3,6,5,2,4)?,對(duì)應(yīng)的可達(dá)距離為：{∞，3.16，1.41，1.41，3.61，4.12，1.0}

按照最終的輸出順序繪制可達(dá)距離圖

可以發(fā)現(xiàn)，可達(dá)距離呈現(xiàn)兩個(gè)波谷，也即表現(xiàn)為兩個(gè)簇，波谷越深，表示簇越緊密只需要在兩個(gè)波谷之間取一個(gè)合適的 eps 分隔值（圖中藍(lán)色的直線），使用 DBSCAN 算法就會(huì)聚類為兩個(gè)簇。即第一個(gè)簇的元素為：0、1、3、6、5；第二個(gè)簇的元素為：2、4。

1.4 和DBSCAN的異同

OPTICS算法與DBSCAN算法有許多相似之處，可以被視為DBSCAN的一種泛化，它將eps要求從單一值放寬到值范圍DBSCAN和OPTICS之間的關(guān)鍵區(qū)別在于，OPTICS算法構(gòu)建了一個(gè)可達(dá)性圖，為每個(gè)樣本分配了一個(gè)可達(dá)性距離和在集群排序?qū)傩灾械奈恢?/p>

這兩個(gè)屬性在模型擬合時(shí)被賦值，并用于確定集群成員資格

1.5 可達(dá)性距離

OPTICS生成的可達(dá)性距離允許在單個(gè)數(shù)據(jù)集中提取可變密度的集群

結(jié)合可達(dá)性距離和數(shù)據(jù)集排序產(chǎn)生了一個(gè)可達(dá)性圖，其中點(diǎn)密度在Y軸上表示，點(diǎn)的排序使得附近的點(diǎn)相鄰平行于x軸“切割”可達(dá)性圖產(chǎn)生了類似DBSCAN的結(jié)果:

所有在“切割”線以上的點(diǎn)被分類為噪聲每當(dāng)從左到右閱讀時(shí)出現(xiàn)間斷時(shí)，就標(biāo)志著一個(gè)新的集群OPTICS的默認(rèn)集群提取方法是查看圖中的陡峭斜坡以找到集群，可以使用xi參數(shù)定義什么算作陡峭斜坡

1.6 計(jì)算復(fù)雜度

空間索引樹用于避免計(jì)算完整的距離矩陣，并允許在大量樣本集上有效地使用內(nèi)存對(duì)于大型數(shù)據(jù)集，可以通過HDBSCAN獲得類似（但不完全相同）的結(jié)果。

HDBSCAN實(shí)現(xiàn)是多線程的，并且比OPTICS具有更好的算法運(yùn)行時(shí)間復(fù)雜性，但以較差的內(nèi)存擴(kuò)展為代價(jià)

2?sklearn.cluster.OPTICS

class sklearn.cluster.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,

memory=None,

n_jobs=None)

2.1 主要參數(shù)

min_samples int > 1 或介于0和1之間的浮點(diǎn)數(shù)，默認(rèn)為5 點(diǎn)被視為核心點(diǎn)時(shí)，鄰域中的樣本數(shù)量 如果是浮點(diǎn)數(shù)，表示樣本數(shù)量的一部分 max_eps 兩個(gè)樣本被視為彼此鄰域的最大距離。 np.inf的默認(rèn)值將識(shí)別所有規(guī)模的聚類； 降低max_eps將導(dǎo)致更短的運(yùn)行時(shí)間 metric str或可調(diào)用，默認(rèn)為'minkowski' 用于距離計(jì)算的度量?？梢允褂?來自scikit-learn：['cityblock', 'cosine', 'euclidean', 'l1', 'l2', 'manhattan'] 來自scipy.spatial.distance：['braycurtis', 'canberra', 'chebyshev', 'correlation', 'dice', 'hamming', 'jaccard', 'kulsinski', 'mahalanobis', 'minkowski', 'rogerstanimoto', 'russellrao', 'seuclidean', 'sokalmichener', 'sokalsneath', 'sqeuclidean', 'yule'] p閔可夫斯基度量的參數(shù)xi float在0和1之間，默認(rèn)為0.05 確定可達(dá)性圖中構(gòu)成聚類邊界的最小陡度。 例如，可達(dá)性圖中的向上點(diǎn)被定義為一個(gè)點(diǎn)與其后繼的比率最多為1-xi。 僅在cluster_method='xi'時(shí)使用 min_cluster_size int > 1 或介于0和1之間的浮點(diǎn)數(shù)，默認(rèn)為None OPTICS聚類中的最小樣本數(shù)量，表示為絕對(duì)數(shù)量或樣本數(shù)量的一部分（至少為2）。如果為None，則使用min_samples的值。 僅在cluster_method='xi'時(shí)使用。 algorithm {'auto', 'ball_tree', 'kd_tree', 'brute'}，默認(rèn)為'auto' 用于計(jì)算最近鄰居的算法： 'ball_tree'將使用BallTree。 'kd_tree'將使用KDTree。 'brute'將使用蠻力搜索。 'auto'（默認(rèn)）將嘗試根據(jù)傳遞給fit方法的值決定最合適的算法。 leaf_size傳遞給BallTree或KDTree的葉子大小。這會(huì)影響構(gòu)建和查詢的速度，以及存儲(chǔ)樹所需的內(nèi)存。最佳值取決于問題的性質(zhì)。cluster_method str，默認(rèn)為'xi' 使用計(jì)算的可達(dá)性和排序提取聚類的方法?？赡艿闹凳恰皒i”和“dbscan”

2.2. 舉例

from sklearn.cluster import OPTICS

import numpy as np

X = np.array([[1, 2], [1, 4], [1, 0],

[10, 2], [10, 4], [10, 0]])

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

op.labels_

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

op.ordering_

#array([0, 1, 2, 3, 4, 5])

#按聚類順序排列的樣本索引列表

op.reachability_

#array([inf, 2., 2., 9., 2., 2.])

#按對(duì)象順序索引的每個(gè)樣本的可達(dá)距離

op.core_distances_

#array([inf, 2., 2., 9., 2., 2.])

#每個(gè)樣本成為核心點(diǎn)的核心距離

#永遠(yuǎn)不會(huì)成為核心的點(diǎn)的距離為無窮大。

參考內(nèi)容：機(jī)器學(xué)習(xí)筆記（十一）聚類算法OPTICS原理和實(shí)踐_optics聚類_大白兔黑又黑的博客-CSDN博客

（4）聚類算法之OPTICS算法 - 知乎 (zhihu.com)

柚子快報(bào)激活碼778899分享：算法筆記：OPTICS 聚類

http://yzkb.51969.com/

相關(guān)鏈接