dbscan演算法

① DBSCAN原理是怎麼樣的

DBSCAN（Density-Based Spatial Clustering of Applications with Noise）聚類演算法，它是一種基於高密度連通區域的、基於密度的聚類演算法，能夠將具有足夠高密度的區域劃分為簇，並在具有雜訊的數據中發現任意形狀的簇。我們總結一下DBSCAN聚類演算法原理的基本要點：
DBSCAN演算法需要選擇一種距離度量，對於待聚類的數據集中，任意兩個點之間的距離，反映了點之間的密度，說明了點與點是否能夠聚到同一類中。由於DBSCAN演算法對高維數據定義密度很困難，所以對於二維空間中的點，可以使用歐幾里德距離來進行度量。
DBSCAN演算法需要用戶輸入2個參數：一個參數是半徑（Eps），表示以給定點P為中心的圓形鄰域的范圍；另一個參數是以點P為中心的鄰域內最少點的數量（MinPts）。如果滿足：以點P為中心、半徑為Eps的鄰域內的點的個數不少於MinPts，則稱點P為核心點。
DBSCAN聚類使用到一個k-距離的概念，k-距離是指：給定數據集P={p(i); i=0,1,…n}，對於任意點P(i)，計算點P(i)到集合D的子集S={p(1), p(2), …, p(i-1), p(i+1), …, p(n)}中所有點之間的距離，距離按照從小到大的順序排序，假設排序後的距離集合為D={d(1), d(2), …, d(k-1), d(k), d(k+1), …,d(n)}，則d(k)就被稱為k-距離。也就是說，k-距離是點p(i)到所有點（除了p(i)點）之間距離第k近的距離。對待聚類集合中每個點p(i)都計算k-距離，最後得到所有點的k-距離集合E={e(1), e(2), …, e(n)}。
根據經驗計算半徑Eps：根據得到的所有點的k-距離集合E，對集合E進行升序排序後得到k-距離集合E』，需要擬合一條排序後的E』集合中k-距離的變化曲線圖，然後繪出曲線，通過觀察，將急劇發生變化的位置所對應的k-距離的值，確定為半徑Eps的值。
根據經驗計算最少點的數量MinPts：確定MinPts的大小，實際上也是確定k-距離中k的值，DBSCAN演算法取k=4，則MinPts=4。
另外，如果覺得經驗值聚類的結果不滿意，可以適當調整Eps和MinPts的值，經過多次迭代計算對比，選擇最合適的參數值。可以看出，如果MinPts不變，Eps取得值過大，會導致大多數點都聚到同一個簇中，Eps過小，會導致已一個簇的分裂；如果Eps不變，MinPts的值取得過大，會導致同一個簇中點被標記為雜訊點，MinPts過小，會導致發現大量的核心點。
DBSCAN演算法，需要輸入2個參數，這兩個參數的計算都來自經驗知識。半徑Eps的計算依賴於計算k-距離，DBSCAN取k=4，也就是設置MinPts=4，然後需要根據k-距離曲線，根據經驗觀察找到合適的半徑Eps的值，下面的演算法實現過程中，我們會詳細說明。對於演算法的實現，首先我們概要地描述一下實現的過程：
1）解析樣本數據文件。
2）計算每個點與其他所有點之間的歐幾里德距離。
3）計算每個點的k-距離值，並對所有點的k-距離集合進行升序排序，輸出的排序後的k-距離值。
4）將所有點的k-距離值，在Excel中用散點圖顯示k-距離變化趨勢。
5）根據散點圖確定半徑Eps的值。）根據給定MinPts=4，以及半徑Eps的值，計算所有核心點，並建立核心點與到核心點距離小於半徑Eps的點的映射。
6）根據得到的核心點集合，以及半徑Eps的值，計算能夠連通的核心點，得到雜訊點。
7）將能夠連通的每一組核心點，以及到核心點距離小於半徑Eps的點，都放到一起，形成一個簇。
8）選擇不同的半徑Eps，使用DBSCAN演算法聚類得到的一組簇及其雜訊點，使用散點圖對比聚類效果。

② spark中有dbscan演算法嗎

看清楚dbscan演算法中有兩個關鍵的參數是 EPS, and Min group threshold. 直觀的想法是，如果你的eps很大，min-group-threshold 也很大的時候，那你得到的聚類的類數目就會少很多，那你搜索的時候就可能很快收斂。

③ 聚類演算法的演算法起源

俗話說：「物以類聚，人以群分」，在自然科學和社會科學中，存在著大量的分類問題。所謂類，通俗地說，就是指相似元素的集合。
聚類分析起源於分類學，在古老的分類學中，人們主要依靠經驗和專業知識來實現分類，很少利用數學工具進行定量的分類。隨著人類科學技術的發展，對分類的要求越來越高，以致有時僅憑經驗和專業知識難以確切地進行分類，於是人們逐漸地把數學工具引用到了分類學中，形成了數值分類學，之後又將多元分析的技術引入到數值分類學形成了聚類分析。聚類分析內容非常豐富，有系統聚類法、有序樣品聚類法、動態聚類法、模糊聚類法、圖論聚類法、聚類預報法等。

④ 有哪些常用的聚類演算法

【聚類】聚類分析是直接比較各對象之間的性質，根據在對象屬性中發現的描述對象及其關系的信息，將數據對象分組。其目標是，組內的對象相互之間是相似的（相關的），而不同組中的對象是不同的（不相關的）。組內的相似性（同質性）越大，組間差別越大，聚類就越好。

聚類的目標是通過對無標記訓練樣本的學習來揭示數據的內在性質及規律，是無監督學習過程。在無監督學習中，訓練樣本標記信息是未知的。聚類試圖將數據集中的樣本劃分為若干個通常不相交的子集，每個子集稱為一個「簇」，每個簇可能對應於一些潛在的類別，這些類別概念對聚類演算法而言事先是未知的，聚類過程僅能自動形成簇結構，簇所對應的概念語義需要由使用者來把握和命名。

⑤ 所有的聚類演算法都要指定"簇"數嗎

一,K-Means聚類演算法原理
k-means 演算法接受參數 k
；然後將事先輸入的n個數據對象劃分為
k個聚類以便使得所獲得的聚類滿足：同一聚類中的對象相似度較高；而不同聚類中的對象相似度較小.聚類相似度是利用各聚類中對象的均值所獲得一個「中心對
象」（引力中心）來進行計算的.

⑥ DBSCAN原理和演算法偽代碼，與kmeans，OPTICS區別

DBSCAN（Density-Based Spatial Clustering of Applications with Noise）聚類演算法，它是一種基於高密度連通區域的、基於密度的聚類演算法，能夠將具有足夠高密度的區域劃分為簇，並在具有雜訊的數據中發現任意形狀的簇。我們總結一下DBSCAN聚類演算法原理的基本要點：
DBSCAN演算法需要選擇一種距離度量，對於待聚類的數據集中，任意兩個點之間的距離，反映了點之間的密度，說明了點與點是否能夠聚到同一類中。由於DBSCAN演算法對高維數據定義密度很困難，所以對於二維空間中的點，可以使用歐幾里德距離來進行度量。
DBSCAN演算法需要用戶輸入2個參數：一個參數是半徑（Eps），表示以給定點P為中心的圓形鄰域的范圍；另一個參數是以點P為中心的鄰域內最少點的數量（MinPts）。如果滿足：以點P為中心、半徑為Eps的鄰域內的點的個數不少於MinPts，則稱點P為核心點。
DBSCAN聚類使用到一個k-距離的概念，k-距離是指：給定數據集P={p(i); i=0,1,…n}，對於任意點P(i)，計算點P(i)到集合D的子集S={p(1), p(2), …, p(i-1), p(i+1), …, p(n)}中所有點之間的距離，距離按照從小到大的順序排序，假設排序後的距離集合為D={d(1), d(2), …, d(k-1), d(k), d(k+1), …,d(n)}，則d(k)就被稱為k-距離。也就是說，k-距離是點p(i)到所有點（除了p(i)點）之間距離第k近的距離。對待聚類集合中每個點p(i)都計算k-距離，最後得到所有點的k-距離集合E={e(1), e(2), …, e(n)}。
根據經驗計算半徑Eps：根據得到的所有點的k-距離集合E，對集合E進行升序排序後得到k-距離集合E』，需要擬合一條排序後的E』集合中k-距離的變化曲線圖，然後繪出曲線，通過觀察，將急劇發生變化的位置所對應的k-距離的值，確定為半徑Eps的值。
根據經驗計算最少點的數量MinPts：確定MinPts的大小，實際上也是確定k-距離中k的值，DBSCAN演算法取k=4，則MinPts=4。
另外，如果覺得經驗值聚類的結果不滿意，可以適當調整Eps和MinPts的值，經過多次迭代計算對比，選擇最合適的參數值。可以看出，如果MinPts不變，Eps取得值過大，會導致大多數點都聚到同一個簇中，Eps過小，會導致已一個簇的分裂；如果Eps不變，MinPts的值取得過大，會導致同一個簇中點被標記為雜訊點，MinPts過小，會導致發現大量的核心點。
我們需要知道的是，DBSCAN演算法，需要輸入2個參數，這兩個參數的計算都來自經驗知識。半徑Eps的計算依賴於計算k-距離，DBSCAN取k=4，也就是設置MinPts=4，然後需要根據k-距離曲線，根據經驗觀察找到合適的半徑Eps的值，下面的演算法實現過程中，我們會詳細說明。對於演算法的實現，首先我們概要地描述一下實現的過程：
1）解析樣本數據文件。2）計算每個點與其他所有點之間的歐幾里德距離。3）計算每個點的k-距離值，並對所有點的k-距離集合進行升序排序，輸出的排序後的k-距離值。4）將所有點的k-距離值，在Excel中用散點圖顯示k-距離變化趨勢。5）根據散點圖確定半徑Eps的值。）根據給定MinPts=4，以及半徑Eps的值，計算所有核心點，並建立核心點與到核心點距離小於半徑Eps的點的映射。7）根據得到的核心點集合，以及半徑Eps的值，計算能夠連通的核心點，得到雜訊點。8）將能夠連通的每一組核心點，以及到核心點距離小於半徑Eps的點，都放到一起，形成一個簇。9）選擇不同的半徑Eps，使用DBSCAN演算法聚類得到的一組簇及其雜訊點，使用散點圖對比聚類效果。
演算法偽代碼：
演算法描述：
演算法：DBSCAN
輸入：E——半徑
MinPts——給定點在E鄰域內成為核心對象的最小鄰域點數。
D——集合。
輸出：目標類簇集合
方法：Repeat
1）判斷輸入點是否為核心對象
2）找出核心對象的E鄰域中的所有直接密度可達點。
Until 所有輸入點都判斷完畢。
Repeat
針對所有核心對象的E鄰域內所有直接密度可達點找到最大密度相連對象集合，中間涉及到一些密度可達對象的合並。Until 所有核心對象的E領域都遍歷完畢
DBSCAN和Kmeans的區別：
1)K均值和DBSCAN都是將每個對象指派到單個簇的劃分聚類演算法，但是K均值一般聚類所有對象，而DBSCAN丟棄被它識別為雜訊的對象。
2)K均值使用簇的基於原型的概念，而DBSCAN使用基於密度的概念。
3)K均值很難處理非球形的簇和不同大小的簇。DBSCAN可以處理不同大小或形狀的簇，並且不太受雜訊和離群點的影響。當簇具有很不相同的密度時，兩種演算法的性能都很差。
4)K均值只能用於具有明確定義的質心（比如均值或中位數）的數據。DBSCAN要求密度定義（基於傳統的歐幾里得密度概念）對於數據是有意義的。
5)K均值可以用於稀疏的高維數據，如文檔數據。DBSCAN通常在這類數據上的性能很差，因為對於高維數據，傳統的歐幾里得密度定義不能很好處理它們。
6)K均值和DBSCAN的最初版本都是針對歐幾里得數據設計的，但是它們都被擴展，以便處理其他類型的數據。
7)基本K均值演算法等價於一種統計聚類方法（混合模型），假定所有的簇都來自球形高斯分布，具有不同的均值，但具有相同的協方差矩陣。DBSCAN不對數據的分布做任何假定。
8)K均值DBSCAN和都尋找使用所有屬性的簇，即它們都不尋找可能只涉及某個屬性子集的簇。
9)K均值可以發現不是明顯分離的簇，即便簇有重疊也可以發現，但是DBSCAN會合並有重疊的簇。
10)K均值演算法的時間復雜度是O(m)，而DBSCAN的時間復雜度是O(m^2)，除非用於諸如低維歐幾里得數據這樣的特殊情況。
11)DBSCAN多次運行產生相同的結果，而K均值通常使用隨機初始化質心，不會產生相同的結果。
12)DBSCAN自動地確定簇個數，對於K均值，簇個數需要作為參數指定。然而，DBSCAN必須指定另外兩個參數：Eps（鄰域半徑）和MinPts（最少點數）。
13)K均值聚類可以看作優化問題，即最小化每個點到最近質心的誤差平方和，並且可以看作一種統計聚類（混合模型）的特例。DBSCAN不基於任何形式化模型。
DBSCAN與OPTICS的區別：
DBSCAN演算法，有兩個初始參數E（鄰域半徑）和minPts(E鄰域最小點數)需要用戶手動設置輸入，並且聚類的類簇結果對這兩個參數的取值非常敏感，不同的取值將產生不同的聚類結果，其實這也是大多數其他需要初始化參數聚類演算法的弊端。
為了克服DBSCAN演算法這一缺點，提出了OPTICS演算法（Ordering Points to identify the clustering structure）。OPTICS並 不顯示的產生結果類簇，而是為聚類分析生成一個增廣的簇排序（比如，以可達距離為縱軸，樣本點輸出次序為橫軸的坐標圖），這個排序代表了各樣本點基於密度 的聚類結構。它包含的信息等價於從一個廣泛的參數設置所獲得的基於密度的聚類，換句話說，從這個排序中可以得到基於任何參數E和minPts的DBSCAN演算法的聚類結果。
OPTICS兩個概念：
核心距離：對象p的核心距離是指是p成為核心對象的最小E』。如果p不是核心對象，那麼p的核心距離沒有任何意義。
可達距離：對象q到對象p的可達距離是指p的核心距離和p與q之間歐幾里得距離之間的較大值。如果p不是核心對象，p和q之間的可達距離沒有意義。
演算法描述：OPTICS演算法額外存儲了每個對象的核心距離和可達距離。基於OPTICS產生的排序信息來提取類簇。

⑦ 哪種聚類演算法可以不需要指定聚類的個數，而且可以生成聚類的規則

一,K-Means聚類演算法原理
k-means 演算法接受參數 k
；然後將事先輸入的n個數據對象劃分為
k個聚類以便使得所獲得的聚類滿足：同一聚類中的對象相似度較高；而不同聚類中的對象相似度較小.聚類相似度是利用各聚類中對象的均值所獲得一個「中心對
象」（引力中心）來進行計算的.
K-means演算法是最為經典的基於劃分的聚類方法,是十大經典數據挖掘演算法之一.K-means演算法的基本思想是：以空間中k個點為中心進行聚類,對最靠近他們的對象歸類.通過迭代的方法,逐次更新各聚類中心的值,直至得到最好的聚類結果.
假設要把樣本集分為c個類別,演算法描述如下：
（1）適當選擇c個類的初始中心；
（2）在第k次迭代中,對任意一個樣本,求其到c個中心的距離,將該樣本歸到距離最短的中心所在的類；
（3）利用均值等方法更新該類的中心值；
（4）對於所有的c個聚類中心,如果利用（2）（3）的迭代法更新後,值保持不變,則迭代結束,否則繼續迭代.
該演算法的最大優勢在於簡潔和快速.演算法的關鍵在於初始中心的選擇和距離公式.

⑧ 聚類演算法有哪幾種

聚類分析計算方法主要有： 層次的方法(hierarchical method)、劃分方法(partitioning method)、基於密度的方法(density-based method)、基於網格的方法(grid-based method)、基於模型的方法(model-based method)等。其中，前兩種演算法是利用統計學定義的距離進行度量。

k-means 演算法的工作過程說明如下：首先從n個數據對象任意選擇 k 個對象作為初始聚類中心;而對於所剩下其它對象，則根據它們與這些聚類中心的相似度(距離)，分別將它們分配給與其最相似的(聚類中心所代表的)聚類;然 後再計算每個所獲新聚類的聚類中心(該聚類中所有對象的均值);不斷重復這一過程直到標准測度函數開始收斂為止。一般都採用均方差作為標准測度函數. k個聚類具有以下特點：各聚類本身盡可能的緊湊，而各聚類之間盡可能的分開。

其流程如下：

(1)從 n個數據對象任意選擇 k 個對象作為初始聚類中心;

(2)根據每個聚類對象的均值(中心對象)，計算每個對象與這些中心對象的距離;並根據最小距離重新對相應對象進行劃分;

(3)重新計算每個(有變化)聚類的均值(中心對象);

(4)循環(2)、(3)直到每個聚類不再發生變化為止(標准測量函數收斂)。

優點： 本演算法確定的K個劃分到達平方誤差最小。當聚類是密集的，且類與類之間區別明顯時，效果較好。對於處理大數據集，這個演算法是相對可伸縮和高效的，計算的復雜度為 O(NKt)，其中N是數據對象的數目，t是迭代的次數。

缺點：

1. K 是事先給定的，但非常難以選定;

2. 初始聚類中心的選擇對聚類結果有較大的影響。

⑨ dbscan聚類演算法是什麼

DBSCAN是基於密度空間的聚類演算法，與KMeans演算法不同，它不需要確定聚類的數量，而是基於數據推測聚類的數目，它能夠針對任意形狀產生聚類。

DBSCAN使用的方法很簡單，它任意選擇一個沒有類別的核心對象作為種子，然後找到所有這個核心對象能夠密度可達的樣本集合，即為一個聚類簇。接著繼續選擇另一個沒有類別的核心對象去尋找密度可達的樣本集合，這樣就得到另一個聚類簇。

DBSCAN演算法需要首先確定兩個參數：

1、epsilon：在一個點周圍鄰近區域的半徑。

2、minPts：鄰近區域內至少包含點的個數。

通常根據以上兩個參數，結合epsilon-neighborhood的特徵，可以把樣本中的點分成核點、邊緣點、離群點三類。

⑩ 聚類演算法有哪幾種

聚類分析計算方法主要有： 層次的方法(hierarchical method)、劃分方法(partitioning method)、基於密度的方法(density-based method)、基於網格的方法(grid-based method)、基於模型的方法(model-based method)等。其中，前兩種演算法是利用統計學定義的距離進行度量。
k-means 演算法的工作過程說明如下：首先從n個數據對象任意選擇 k 個對象作為初始聚類中心;而對於所剩下其它對象，則根據它們與這些聚類中心的相似度(距離)，分別將它們分配給與其最相似的(聚類中心所代表的)聚類;然 後再計算每個所獲新聚類的聚類中心(該聚類中所有對象的均值);不斷重復這一過程直到標准測度函數開始收斂為止。一般都採用均方差作為標准測度函數. k個聚類具有以下特點：各聚類本身盡可能的緊湊，而各聚類之間盡可能的分開。
其流程如下：
(1)從 n個數據對象任意選擇 k 個對象作為初始聚類中心;
(2)根據每個聚類對象的均值(中心對象)，計算每個對象與這些中心對象的距離;並根據最小距離重新對相應對象進行劃分;
(3)重新計算每個(有變化)聚類的均值(中心對象);
(4)循環(2)、(3)直到每個聚類不再發生變化為止(標准測量函數收斂)。
優點： 本演算法確定的K個劃分到達平方誤差最小。當聚類是密集的，且類與類之間區別明顯時，效果較好。對於處理大數據集，這個演算法是相對可伸縮和高效的，計算的復雜度為 O(NKt)，其中N是數據對象的數目，t是迭代的次數。
缺點：
1. K 是事先給定的，但非常難以選定;
2. 初始聚類中心的選擇對聚類結果有較大的影響。