DBSCAN密度空間的聚類算法

聚類算法（DBSCAN）：（一般比k-means等效果好）

​ 通俗了解：随機找到一個核心點的時候，就建立一個簇，裡面的所有點，是它的下線，然後一直發展下線，一般邊界點就不會繼續發展了，裡面的核心點繼續發展下線，并且需要把通路的點标記為已通路，知道該核心點結束，繼續通路剩下的點找到一個新的核心，繼續發展下線，每次沒有下線發展的時候，開始新的一輪發展下線的時候，改點不是核心點，就是離群點了。

首先需定義的兩個超參數：eps：鄰域距離門檻值，min_samples樣本點成為核心點的樣本數門檻值

基本定義：

• 核心點：看其鄰域内，所包含點的個數，是否超過min_samples,超過就是核心點；
• 邊界點：在核心點内的點，繼續判斷，是否為核心點，非核心點，如果不是就是邊界點；
• 噪聲點：沒有被掃描到的點離群點，從任何一個核心點出發都是密度不可達的；
• 密度直接可達：點q在p的鄰域内，且p為核心點，則q是p的密度直達；
• 密度可達：有一個序列q0,q1，,q2…qk，對于任意qi到qi-1是直接密度可達的，則稱q0到q1…qk都是密度可達的，實際上是密度直接可達的傳播；
• 密度相連：從某核心點p出發，點q和點k都是密度可達的，則稱為q和k是密度相連的

算法基本流程：

​ 這裡引用下唐宇迪大佬的流程圖：

​ 個人感覺，我覺得這個流程第一步有點問題，如果不是核心點直接判定為離群點有點問題，如果選到了邊界點呢，你也判定為離群點了，感覺如果不是核心點直接跳過就行，如果剩下的所有點都沒有核心點了，那麼剩下的所有未标記的點才能被判定為離群點。

感覺這篇中寫的也比較簡潔而且準确，不是直接判定為離群點，而是判定為外圍點，後面再改判為離群點：聚類算法之DBSCAN算法之一：經典DBSCAN

1. 任意選擇一個點（既沒有指定到一個類也沒有特定為外圍點），計算它的NBHD(p,epsilon)判斷是否為核點。如果是，在該點周圍建立一個類，否則，設定為外圍點。
2. 周遊其他點，直到建立一個類。把directly-reachable的點加入到類中，接着把density-reachable的點也加進來。如果标記為外圍的點被加進來，修改狀态為邊緣點。
3. 重複步驟1和2，直到所有的點滿足在類中（核點或邊緣點）或者為外圍點

總結下，密度可達的動态擴充就是發展下線的過程，其實就是一個簇所有資料的關系就是密度相連。

展下線的過程，其實就是一個簇所有資料的關系就是密度相連。