心智圖資源庫 DBSCAN
密度聚類演算法,包含定義、DBSCAN涉及的幾個概念、演算法步驟、 DBSCAN的優缺點等
編輯於2023-12-23 14:05:37Einhundert Jahre Einsamkeit ist das Meisterwerk von Gabriel Garcia Marquez. Die Lektüre dieses Buches beginnt mit der Klärung der Beziehungen zwischen den Figuren. Im Mittelpunkt steht die Familie Buendía, deren Wohlstand und Niedergang, interne Beziehungen und politische Kämpfe, Selbstvermischung und Wiedergeburt im Laufe von hundert Jahren erzählt werden.
Einhundert Jahre Einsamkeit ist das Meisterwerk von Gabriel Garcia Marquez. Die Lektüre dieses Buches beginnt mit der Klärung der Beziehungen zwischen den Figuren. Im Mittelpunkt steht die Familie Buendía, deren Wohlstand und Niedergang, interne Beziehungen und politische Kämpfe, Selbstvermischung und Wiedergeburt im Laufe von hundert Jahren erzählt werden.
Projektmanagement ist der Prozess der Anwendung von Fachwissen, Fähigkeiten, Werkzeugen und Methoden auf die Projektaktivitäten, so dass das Projekt die festgelegten Anforderungen und Erwartungen im Rahmen der begrenzten Ressourcen erreichen oder übertreffen kann. Dieses Diagramm bietet einen umfassenden Überblick über die 8 Komponenten des Projektmanagementprozesses und kann als generische Vorlage verwendet werden.
Einhundert Jahre Einsamkeit ist das Meisterwerk von Gabriel Garcia Marquez. Die Lektüre dieses Buches beginnt mit der Klärung der Beziehungen zwischen den Figuren. Im Mittelpunkt steht die Familie Buendía, deren Wohlstand und Niedergang, interne Beziehungen und politische Kämpfe, Selbstvermischung und Wiedergeburt im Laufe von hundert Jahren erzählt werden.
Einhundert Jahre Einsamkeit ist das Meisterwerk von Gabriel Garcia Marquez. Die Lektüre dieses Buches beginnt mit der Klärung der Beziehungen zwischen den Figuren. Im Mittelpunkt steht die Familie Buendía, deren Wohlstand und Niedergang, interne Beziehungen und politische Kämpfe, Selbstvermischung und Wiedergeburt im Laufe von hundert Jahren erzählt werden.
Projektmanagement ist der Prozess der Anwendung von Fachwissen, Fähigkeiten, Werkzeugen und Methoden auf die Projektaktivitäten, so dass das Projekt die festgelegten Anforderungen und Erwartungen im Rahmen der begrenzten Ressourcen erreichen oder übertreffen kann. Dieses Diagramm bietet einen umfassenden Überblick über die 8 Komponenten des Projektmanagementprozesses und kann als generische Vorlage verwendet werden.
DBSCAN
簡介
演算法思想:針對每一個核心點,若其鄰近區域的密度大於閾值,則將其加到與之相近的簇
DBSCAN涉及的幾個概念
Eps鄰域:給定一個物件p、半徑d,以物件p為球心,半徑d畫球:
核心點:給定一個物件p、數量minpts,其鄰域內物件數量大於minpts:
邊界點:給定一個物件p、數量minpts,其鄰域內物件數量小於minpts,但其在其他核心點領域內
異常點:給定一個物件p、數量minpts,其鄰域內物件數量小於minpts,也不在其他核心點領域內
直接密度可達:核心點到其鄰近區域內的任一資料點均表現為直接密度可達:
密度可達:核心點p到其鄰域內一點q,即p->q;核心點q到其鄰域內一點n,即q->n;那麼p->n稱為密度可達
密度相連:若存在核心點o,o->p;o->q,則稱p與q為密度相連:
演算法步驟
第一步:遍歷並標記所有樣本點
第二步:任選一個沒有加簇標籤的點
核心點:將與其密度可達的所有樣本點整合為一個新簇
邊界點:跳過邊界點,掃描下一個樣本點
第三步:循環步驟二,直到所有點都掃描
DBSCAN的優缺點
優點
對噪音不敏感
可以發現任意形狀的簇
無需人為設定聚類數量
缺點
模型對參數Eps與minpts十分敏感
當資料的密度不均勻、聚類間距差相差很大時,聚類品質較差
最佳化
針對參數敏感問題
方法:透過引入核心距離與可達距離,使聚類演算法對輸入的參數不敏感。即OPTICS算法
OPTICS
演算法思想:透過計算所有樣本的可達距離,抵消Eps參數的敏感度
幾個概念
核心距離:滿足minpts的最小距離
可達距離:樣本點與核心點的歐式距離與核心點的核心距離的較小值
演算法步驟
第一步:已知資料集D,建立兩個隊列,有序隊列O和結果隊列R(有序隊列用來儲存核心對象及其該核心對象的密度直達對象,並按可達距離升序排列;結果佇列用來儲存樣本點的輸出次序。
第二步:如果D中所有點都處理完畢或不存在核心點,則演算法結束。否則,選擇一個未處理(即不在結果佇列R中)且為核心物件的樣本點 p,先將 p 放入結果佇列R中,並從D中刪除 p。然後找到D 中p 的所有密度直達樣本點x,計算x 到p 的可達距離,如果x 不在有序隊列O 中,則將x 以及可達距離放入O 中,若x 在O 中,則如果x 新的可達距離更小,則更新x 的可達距離,最後對O 中資料按可達距離從小到大重新排序
第三步:如果有序隊列O 為空,則回到步驟2,否則取出O 中第一個樣本點y(即可達距離最小的樣本點),放入R 中,並從D 和O 中刪除y。如果y 不是核心對象,則重複步驟3(即找O 中剩餘資料可達距離最小的樣本點);如果y 是核心對象,則找到y 在D 中的所有密度直達樣本點,併計算到y 的可達距離,然後依照步驟2將所有y 的密度直達樣本點更新到O 中
第四步:重複步驟2、3,直到演算法結束,最後得到一個有順序的輸出結果,以及對應的可達距離
舉例說明
已知資料集如圖:
第一步:計算核心點到其他點的可達距離
第二步:可達距離排序,選擇較小的樣本點,重複步驟一:
第三步:輸出核心物件及其可達距離,並分割聚類,核心物件:[0, 1, 3, 6, 5, 2, 4],可達距離:[inf, 3.16227766, 4.12310563, 1.41421356, 1. ,3.60555128, 1.41421356]