聚類演算法適用於什麼類型的數據

㈠ 聚類分析中常見的數據類型有哪些

聚類分析，又稱群分析，即建立一種分類方法：將一批樣品或者指標（變數），按照它們在性質上的親疏、相似程度進行分類。
按其聚類的方法，數據類型有以下六種：
①系統聚類分析：開始每個對象自成一類，然後將最相似的兩類合並，合並過後重新計算新類與其它類的距離或相近性程度。這一過程一直繼續下去直到所有的對象歸為一類為止

②調優法（動態聚類法）：首先對n個對象進行初步分類，然後根據分類的損失函數盡可能小的原則對其進行調整，直到分類合理為止；
③最優分割法（有序樣品聚類法）：開始將所有樣品看成一類，然後根據某種最優准則將他們分割為二類、三類，一直分割到所需要的K類為止；
④模糊聚類法：利用模糊集理論來處理分類的問題，他將經濟領域中最有模糊特徵的兩態數據或多態數據具有明顯的分類效果；
⑤圖論據類法：利用圖論中最小支撐樹的概念來處理分類問題；
⑥聚類預報法：聚類預報彌補了回歸分析和判別分析的不足。
按分類對象的不同：聚類分為R型和Q型

㈡ k均值聚類法適用於均為連續型的變數對嗎

對。k均值聚類演算法是一種迭代求解的聚類分析演算法，其步驟是，預將數據分為K組，則隨機選取K個對象作為初始的聚類中心，K均值聚類適用於連續型變數，演算法快速、簡單，對大數據集有較高的效率並且是可伸縮性的，並且通常要求已知的類別數。然後計算每個對象與各個種子聚類中心之間的距離，把每個對象分配給距離它最近的聚類中心。聚類中心以及分配給它們的對象就代表一個聚類。

㈢ 16種常用的數據分析方法-聚類分析

聚類（Clustering）就是一種尋找數據之間內在結構的技術。聚類把全體數據實例組織成一些相似組，而這些相似組被稱作簇。處於相同簇中的數據實例彼此相同，處於不同簇中的實例彼此不同。

聚類分析定義

聚類分析是根據在數據中發現的描述對象及其關系的信息，將數據對象分組。目的是，組內的對象相互之間是相似的（相關的），而不同組中的對象是不同的（不相關的）。組內相似性越大，組間差距越大，說明聚類效果越好。

聚類效果的好壞依賴於兩個因素：1.衡量距離的方法（distance measurement） 2.聚類演算法（algorithm）

 

聚類分析常見演算法

K-均值聚類也稱為快速聚類法，在最小化誤差函數的基礎上將數據劃分為預定的類數K。該演算法原理簡單並便於處理大量數據。

K-均值演算法對孤立點的敏感性，K-中心點演算法不採用簇中對象的平均值作為簇中心，而選用簇中離平均值最近的對象作為簇中心。

也稱為層次聚類，分類的單位由高到低呈樹形結構，且所處的位置越低，其所包含的對象就越少，但這些對象間的共同特徵越多。該聚類方法只適合在小數據量的時候使用，數據量大的時候速度會非常慢。

 

案例

有20種12盎司啤酒成分和價格的數據，變數包括啤酒名稱、熱量、鈉含量、酒精含量、價格。

 

問題一：選擇那些變數進行聚類？——採用「R 型聚類」

 

現在我們有4個變數用來對啤酒分類，是否有必要將4個變數都納入作為分類變數呢？熱量、鈉含量、酒精含量這3個指標是要通過化驗員的辛苦努力來測定，而且還有花費不少成本。

所以，有必要對4個變數進行降維處理，這里採用spss R型聚類（變數聚類），對4個變數進行降維處理。輸出「相似性矩陣」有助於我們理解降維的過程。

4個分類變數各自不同，這一次我們先用相似性來測度，度量標准選用pearson系數，聚類方法選最遠元素，此時，涉及到相關，4個變數可不用標准化處理，將來的相似性矩陣里的數字為相關系數。若果有某兩個變數的相關系數接近1或-1，說明兩個變數可互相替代。

只輸出「樹狀圖」就可以了,從proximity matrix表中可以看出熱量和酒精含量兩個變數相關系數0.903，最大，二者選其一即可，沒有必要都作為聚類變數，導致成本增加。

至於熱量和酒精含量選擇哪一個作為典型指標來代替原來的兩個變數，可以根據專業知識或測定的難易程度決定。（與因子分析不同，是完全踢掉其中一個變數以達到降維的目的。）這里選用酒精含量，至此，確定出用於聚類的變數為：酒精含量，鈉含量，價格。

        

問題二：20 中啤酒能分為幾類？—— 採用「Q 型聚類」

 

現在開始對20中啤酒進行聚類。開始不確定應該分為幾類，暫時用一個3-5類范圍來試探。Q型聚類要求量綱相同，所以我們需要對數據標准化，這一回用歐式距離平方進行測度。

主要通過樹狀圖和冰柱圖來理解類別。最終是分為4類還是3類，這是個復雜的過程，需要專業知識和最初的目的來識別。

這里試著確定分為4類。選擇「保存」，則在數據區域內會自動生成聚類結果。

問題三：用於聚類的變數對聚類過程、結果又貢獻么，有用么？——採用「單因素方差分析」

 

聚類分析除了對類別的確定需討論外，還有一個比較關鍵的問題就是分類變數到底對聚類有沒有作用有沒有貢獻，如果有個別變數對分類沒有作用的話，應該剔除。

這個過程一般用單因素方差分析來判斷。注意此時，因子變數選擇聚為4類的結果，而將三個聚類變數作為因變數處理。方差分析結果顯示，三個聚類變數sig值均極顯著，我們用於分類的3個變數對分類有作用，可以使用，作為聚類變數是比較合理的。

 

問題四：聚類結果的解釋？——採用」均值比較描述統計「

聚類分析最後一步，也是最為困難的就是對分出的各類進行定義解釋，描述各類的特徵，即各類別特徵描述。這需要專業知識作為基礎並結合分析目的才能得出。

我們可以採用spss的means均值比較過程，或者excel的透視表功能對各類的各個指標進行描述。其中，report報表用於描述聚類結果。對各類指標的比較來初步定義類別，主要根據專業知識來判定。這里到此為止。

以上過程涉及到spss層次聚類中的Q型聚類和R型聚類，單因素方差分析，means過程等，是一個很不錯的多種分析方法聯合使用的案例。

 

聚類分析的應用

聚類分析是細分市場的有效工具，被用來發現不同的客戶群，並且它通過對不同的客戶群的特徵的刻畫，被用於研究消費者行為，尋找新的潛在市場。

 

聚類分析被用來對動植物和基因進行分類，以獲取對種群固有結構的認識。

 

聚類分析可以通過平均消費來鑒定汽車保險單持有者的分組，同時可以根據住宅類型、價值、地理位置來鑒定城市的房產分組。

 

聚類分析被用來在網上進行文檔歸類。

 

聚類分析通過分組聚類出具有相似瀏覽行為的客戶，並分析客戶的共同特徵，從而幫助電子商務企業了解自己的客戶，向客戶提供更合適的服務。

 

㈣ 常用的聚類方法有哪幾種

聚類分析的演算法可以分為劃分法、層次法、基於密度的方法、基於網格的方法、基於模型的方法。

1、劃分法，給定一個有N個元組或者紀錄的數據集，分裂法將構造K個分組，每一個分組就代表一個聚類，K<N。

2、層次法，這種方法對給定的數據集進行層次似的分解，直到某種條件滿足為止。

3、基於密度的方法，基於密度的方法與其它方法的一個根本區別是：它不是基於各種各樣的距離的，而是基於密度的。這樣就能克服基於距離的演算法只能發現「類圓形」的聚類的缺點。

4、圖論聚類方法解決的第一步是建立與問題相適應的圖，圖的節點對應於被分析數據的最小單元，圖的邊（或弧）對應於最小處理單元數據之間的相似性度量。

5、基於網格的方法，這種方法首先將數據空間劃分成為有限個單元的網格結構,所有的處理都是以單個的單元為對象的。

6、基於模型的方法，基於模型的方法給每一個聚類假定一個模型，然後去尋找能夠很好的滿足這個模型的數據集。

(4)聚類演算法適用於什麼類型的數據擴展閱讀：

在商業上，聚類可以幫助市場分析人員從消費者資料庫中區分出不同的消費群體來，並且概括出每一類消費者的消費模式或者說習慣。

它作為數據挖掘中的一個模塊，可以作為一個單獨的工具以發現資料庫中分布的一些深層的信息，並且概括出每一類的特點，或者把注意力放在某一個特定的類上以作進一步的分析；並且，聚類分析也可以作為數據挖掘演算法中其他分析演算法的一個預處理步驟。

許多聚類演算法在小於 200 個數據對象的小數據集合上工作得很好；但是，一個大規模資料庫可能包含幾百萬個對象，在這樣的大數據集合樣本上進行聚類可能會導致有偏的結果。

許多聚類演算法在聚類分析中要求用戶輸入一定的參數，例如希望產生的簇的數目。聚類結果對於輸入參數十分敏感。參數通常很難確定，特別是對於包含高維對象的數據集來說。這樣不僅加重了用戶的負擔，也使得聚類的質量難以控制。

㈤ 聚類演算法有哪些分類

聚類演算法的分類有：

1、劃分法

劃分法(partitioning methods)，給定一個有N個元組或者紀錄的數據集，分裂法將構造K個分組，每一個分組就代表一個聚類，K小於N。而且這K個分組滿足下列條件：

（1） 每一個分組至少包含一個數據紀錄；

（2）每一個數據紀錄屬於且僅屬於一個分組（注意：這個要求在某些模糊聚類演算法中可以放寬）；

2、層次法

層次法(hierarchical methods)，這種方法對給定的數據集進行層次似的分解，直到某種條件滿足為止。具體又可分為「自底向上」和「自頂向下」兩種方案。

例如，在「自底向上」方案中，初始時每一個數據紀錄都組成一個單獨的組，在接下來的迭代中，它把那些相互鄰近的組合並成一個組，直到所有的記錄組成一個分組或者某個條件滿足為止。

3、密度演算法

基於密度的方法(density-based methods)，基於密度的方法與其它方法的一個根本區別是：它不是基於各種各樣的距離的，而是基於密度的。這樣就能克服基於距離的演算法只能發現「類圓形」的聚類的缺點。

4、圖論聚類法

圖論聚類方法解決的第一步是建立與問題相適應的圖，圖的節點對應於被分析數據的最小單元，圖的邊（或弧）對應於最小處理單元數據之間的相似性度量。因此，每一個最小處理單元數據之間都會有一個度量表達，這就確保了數據的局部特性比較易於處理。圖論聚類法是以樣本數據的局域連接特徵作為聚類的主要信息源，因而其主要優點是易於處理局部數據的特性。

5、網格演算法

基於網格的方法(grid-based methods)，這種方法首先將數據空間劃分成為有限個單元（cell）的網格結構,所有的處理都是以單個的單元為對象的。這么處理的一個突出的優點就是處理速度很快，通常這是與目標資料庫中記錄的個數無關的，它只與把數據空間分為多少個單元有關。

代表演算法有：STING演算法、CLIQUE演算法、WAVE-CLUSTER演算法；

6、模型演算法

基於模型的方法(model-based methods)，基於模型的方法給每一個聚類假定一個模型，然後去尋找能夠很好的滿足這個模型的數據集。這樣一個模型可能是數據點在空間中的密度分布函數或者其它。它的一個潛在的假定就是：目標數據集是由一系列的概率分布所決定的。

通常有兩種嘗試方向：統計的方案和神經網路的方案。

(5)聚類演算法適用於什麼類型的數據擴展閱讀：

聚類演算法的要求：

1、可伸縮性

許多聚類演算法在小於 200 個數據對象的小數據集合上工作得很好；但是，一個大規模資料庫可能包含幾百萬個對象，在這樣的大數據集合樣本上進行聚類可能會導致有偏的結果。

我們需要具有高度可伸縮性的聚類演算法。

2、不同屬性

許多演算法被設計用來聚類數值類型的數據。但是，應用可能要求聚類其他類型的數據，如二元類型(binary)，分類/標稱類型（categorical/nominal），序數型（ordinal）數據，或者這些數據類型的混合。

3、任意形狀

許多聚類演算法基於歐幾里得或者曼哈頓距離度量來決定聚類。基於這樣的距離度量的演算法趨向於發現具有相近尺度和密度的球狀簇。但是，一個簇可能是任意形狀的。提出能發現任意形狀簇的演算法是很重要的。

4、領域最小化

許多聚類演算法在聚類分析中要求用戶輸入一定的參數，例如希望產生的簇的數目。聚類結果對於輸入參數十分敏感。參數通常很難確定，特別是對於包含高維對象的數據集來說。這樣不僅加重了用戶的負擔，也使得聚類的質量難以控制。

5、處理「雜訊」

絕大多數現實中的資料庫都包含了孤立點，缺失，或者錯誤的數據。一些聚類演算法對於這樣的數據敏感，可能導致低質量的聚類結果。

6、記錄順序

一些聚類演算法對於輸入數據的順序是敏感的。例如，同一個數據集合，當以不同的順序交給同一個演算法時，可能生成差別很大的聚類結果。開發對數據輸入順序不敏感的演算法具有重要的意義。

㈥ 用於數據挖掘的聚類演算法有哪些，各有何優勢

K均值聚類：最適合處理大數據，適用於大樣本的個案聚類，分類數明確，適用於連續性變數；
系統聚類：適用於個案或變數聚類，對分類數沒有要求，連續性和分類型變數均適用；
兩步聚類：1）分類變數和連續變數均可參與二階聚類；2）可自動確定分類數；3）適用於大數據集；4）用戶可自己定製用於運算的內存容量

㈦ 系統聚類適用於連續變數還是離散變數

連續變數和離散變數都適用系統聚類。

系統聚類法（分層聚類法）：

1、基本思想：開始將每個樣本自成一類；然後求兩兩之間的距離，將距離最近的兩類合成一類；如此重復，直到所有樣本都合為一類為止。

2、適用范圍：既適用於樣本聚類，也適用於變數聚類。並且距離分類准則和距離計算方法都有多種，可以依據具體情形選擇。

快速聚類法（K-均值聚類法）：

1、基本思想：按照指定分類數目，選擇個初始聚類中心；計算每個觀測量（樣本）到各個聚類中心的距離，按照就近原則將其分別分到放入各類中；重新計算聚類中心，繼續以上步驟；滿足停止條件時（如最大迭代次數等）則停止。

2、使用范圍：要求用戶給定分類數目，只適用於樣本聚類（Q型），不適用於變數聚類（R型）。

㈧ 用於數據挖掘的聚類演算法有哪些，各有何優勢

1、層次聚類演算法

1.1聚合聚類

1.1.1相似度依據距離不同：Single-Link:最近距離、Complete-Link：最遠距離、Average-Link：平均距離

1.1.2最具代表性演算法

1）CURE演算法
特點：固定數目有代表性的點共同代表類
優點：識別形狀復雜，大小不一的聚類，過濾孤立點
2）ROCK演算法
特點：對CURE演算法的改進
優點：同上，並適用於類別屬性的數據
3）CHAMELEON演算法
特點：利用了動態建模技術
1.2分解聚類

1.3優缺點

優點：適用於任意形狀和任意屬性的數據集；靈活控制不同層次的聚類粒度，強聚類能力
缺點：大大延長了演算法的執行時間，不能回溯處理

2、分割聚類演算法
2.1基於密度的聚類

2.1.1特點

將密度足夠大的相鄰區域連接，能有效處理異常數據，主要用於對空間數據的聚類
2.1.2典型演算法

1）DBSCAN：不斷生長足夠高密度的區域
2）DENCLUE：根據數據點在屬性空間中的密度進行聚類，密度和網格與處理的結合
3）OPTICS、DBCLASD、CURD：均針對數據在空間中呈現的不同密度分不對DBSCAN作了改進
2.2基於網格的聚類

2.2.1特點

利用屬性空間的多維網格數據結構，將空間劃分為有限數目的單元以構成網格結構；
1）優點：處理時間與數據對象的數目無關，與數據的輸入順序無關，可以處理任意類型的數據
2）缺點：處理時間與每維空間所劃分的單元數相關，一定程度上降低了聚類的質量和准確性
2.2.2典型演算法

1）STING：基於網格多解析度，將空間劃分為方形單元，對應不同解析度
2）STING+：改進STING，用於處理動態進化的空間數據
3）CLIQUE：結合網格和密度聚類的思想，能處理大規模高維度數據
4）WaveCluster：以信號處理思想為基礎
2.3基於圖論的聚類

2.3.1特點

轉換為組合優化問題，並利用圖論和相關啟發式演算法來解決，構造數據集的最小生成數，再逐步刪除最長邊
1）優點：不需要進行相似度的計算
2.3.2兩個主要的應用形式

1）基於超圖的劃分
2）基於光譜的圖劃分
2.4基於平方誤差的迭代重分配聚類

2.4.1思想

逐步對聚類結果進行優化、不斷將目標數據集向各個聚類中心進行重新分配以獲最優解
2.4.2具體演算法

1）概率聚類演算法
期望最大化、能夠處理異構數據、能夠處理具有復雜結構的記錄、能夠連續處理成批的數據、具有在線處理能力、產生的聚類結果易於解釋
2）最近鄰聚類演算法——共享最近鄰演算法SNN
特點：結合基於密度方法和ROCK思想，保留K最近鄰簡化相似矩陣和個數
不足：時間復雜度提高到了O(N^2)
3）K-Medioids演算法
特點：用類中的某個點來代表該聚類
優點：能處理任意類型的屬性；對異常數據不敏感
4）K-Means演算法
1》特點：聚類中心用各類別中所有數據的平均值表示
2》原始K-Means演算法的缺陷：結果好壞依賴於對初始聚類中心的選擇、容易陷入局部最優解、對K值的選擇沒有準則可依循、對異常數據較為敏感、只能處理數值屬性的數據、聚類結構可能不平衡
3》K-Means的變體
Bradley和Fayyad等：降低對中心的依賴，能適用於大規模數據集
Dhillon等：調整迭代過程中重新計算中心方法，提高性能
Zhang等：權值軟分配調整迭代優化過程
Sarafis：將遺傳演算法應用於目標函數構建中
Berkh in等：應用擴展到了分布式聚類
還有：採用圖論的劃分思想，平衡聚類結果，將原始演算法中的目標函數對應於一個各向同性的高斯混合模型
5）優缺點
優點：應用最為廣泛；收斂速度快；能擴展以用於大規模的數據集
缺點：傾向於識別凸形分布、大小相近、密度相近的聚類；中心選擇和雜訊聚類對結果影響大
3、基於約束的聚類演算法

3.1約束

對個體對象的約束、對聚類參數的約束；均來自相關領域的經驗知識
3.2重要應用

對存在障礙數據的二維空間按數據進行聚類,如COD(Clustering with Obstructed Distance)：用兩點之間的障礙距離取代了一般的歐式距離
3.3不足

通常只能處理特定應用領域中的特定需求
4、用於高維數據的聚類演算法

4.1困難來源因素

1）無關屬性的出現使數據失去了聚類的趨勢
2)區分界限變得模糊
4.2解決方法

1)對原始數據降維
2)子空間聚類
CACTUS：對原始空間在二維平面上的投影
CLIQUE：結合基於密度和網格的聚類思想，借鑒Apriori演算法
3)聯合聚類技術
特點：對數據點和屬性同時進行聚類
文本：基於雙向劃分圖及其最小分割的代數學方法
4.3不足：不可避免地帶來了原始數據信息的損失和聚類准確性的降低

㈨ 聚類分析聚類演算法中包含哪些數據類型

聚類分析聚類演算法中包含哪些數據類型
許多基於內存的聚類演算法採用以下兩種數據結構：
(1)數據矩陣(Data Matrix，或稱對象一變盤結構)：用p個變數來表示n個對象，例如使用年齡、身高、性別、體重等屬性變數來表示對象人，也叫二模矩陣，行與列代表不同實體：

(2)相異度矩陣(Dissimilarity Matrix，又稱為對象一對象結構)：存儲所有成對的n個對象兩兩之間的近似性(鄰近度)，也叫單模矩陣，行和列代表相同的實體。其中d(ij)是對象i和對象j之間的測量差或相異度。d(i，f)是一個非負的數值，d(ij)越大，兩個對象越不同；d (i，j)越接近於0，則兩者之間越相似(相近)。

許多聚類演算法都是以相異度矩陣為基礎的，如果數據是用數據矩陣形式表示，則往往要將其先轉化為相異度矩陣。
相異度d(i,j)的具體計算會因所使用的數據類型不同而不同，常用的數據類型包括：區間標度變數，二元變數，標稱型、序數型和比例標度型變數，混合類型的變數。

㈩ 聚類演算法--DBSCAN

       DBSCAN(Density-Based Spatial Clustering of Applications with Noise，具有雜訊的基於密度的聚類方法)是一種很典型的密度聚類演算法，和K-Means，BIRCH這些一般只適用於凸樣本集的聚類相比，DBSCAN既可以適用於凸樣本集，也可以適用於非凸樣本集。 基於密度的帶有雜訊的空間聚類，可用於異常值監測，通俗來說就是基於密度的聚類演算法 ！

        聚類就是對大量未知標注的數據集，按數據的內在相似性將數據集劃分為多個類別，使類別內的數據相似度較大而類別間的數據相似度較小。聚類演算法是無監督的演算法。

DBSCAN演算法的目的： 是基於密度尋找被低密度區域分離的高密度樣本分為三類： 

稠密區域內部的點（核心點）： 在半徑Eps內含有超過MinPts數目的點 

稠密區域邊緣上的點（邊緣點）： 在半徑Eps內點的數量小於MinPts（即不是核心點），但是其鄰域內至少包含一個核心點 

稀疏區域中的點（雜訊或者背景點）： 任何不是核心點或者邊界點的點

特點 ： 發現任意形狀的簇、對雜訊數據不敏感、一次掃描、需要密度參數作為停止條件，計算量大和復雜度高 。

    DBSCAN是一種基於密度的聚類演算法，這類密度聚類演算法一般假定類別可以通過樣本分布的緊密程度決定。同一類別的樣本，他們之間的緊密相連的，也就是說，在該類別任意樣本周圍不遠處一定有同類別的樣本存在。

    通過將緊密相連的樣本劃為一類，這樣就得到了一個聚類類別。通過將所有各組緊密相連的樣本劃為各個不同的類別，則我們就得到了最終的所有聚類類別結果。

    前面我們定性描述了密度聚類的基本思想，在這里我們就看看DBSCAN是如何描述密度聚類的。DBSCAN是基於一組鄰域來描述樣本集的緊密程度的，參數(ϵϵ, MinPts)用來描述鄰域的樣本分布緊密程度。其中，ϵϵ描述了某一樣本的鄰域距離閾值，MinPts描述了某一樣本的距離為ϵϵ的鄰域中樣本個數的閾值。

    假設我們的樣本集是D=(x1,x2,...,xm)(x1,x2,...,xm)，則DBSCAN具體的密度描述定義如下：

        1） ϵϵ-鄰域：對於xj∈Dxj∈D，其ϵϵ-鄰域包含樣本集D中與xjxj的距離不大於ϵϵ的子樣本集，即Nϵ(xj)={xi∈D|distance(xi,xj)≤ϵ}Nϵ(xj)={xi∈D|distance(xi,xj)≤ϵ}, 這個子樣本集的個數記為|Nϵ(xj)||Nϵ(xj)|

        2）核心對象：對於任一樣本xj∈Dxj∈D，如果其ϵϵ-鄰域對應的Nϵ(xj)Nϵ(xj)至少包含MinPts個樣本，即如果|Nϵ(xj)|≥MinPts|Nϵ(xj)|≥MinPts，則xjxj是核心對象。

        3）密度直達：如果xixi位於xjxj的ϵϵ-鄰域中，且xjxj是核心對象，則稱xixi由xjxj密度直達。注意反之不一定成立，即此時不能說xjxj由xixi密度直達, 除非且xixi也是核心對象。

        4）密度可達：對於xixi和xjxj,如果存在樣本樣本序列p1,p2,...,pTp1,p2,...,pT,滿p1=xi,pT=xjp1=xi,pT=xj, 且pt+1pt+1由ptpt密度直達，則稱xjxj由xixi密度可達。也就是說，密度可達滿足傳遞性。此時序列中的傳遞樣本p1,p2,...,pT−1p1,p2,...,pT−1均為核心對象，因為只有核心對象才能使其他樣本密度直達。注意密度可達也不滿足對稱性，這個可以由密度直達的不對稱性得出。

       5）密度相連：對於xixi和xjxj,如果存在核心對象樣本xkxk，使xixi和xjxj均由xkxk密度可達，則稱xixi和xjxj密度相連。注意密度相連關系是滿足對稱性的。

從下圖可以很容易看出理解上述定義，圖中MinPts=5，紅色的點都是核心對象，因為其ϵϵ-鄰域至少有5個樣本。黑色的樣本是非核心對象。所有核心對象密度直達的樣本在以紅色核心對象為中心的超球體內，如果不在超球體內，則不能密度直達。圖中用綠色箭頭連起來的核心對象組成了密度可達的樣本序列。在這些密度可達的樣本序列的ϵϵ-鄰域內所有的樣本相互都是密度相連的。

    DBSCAN的聚類定義很簡單： 由密度可達關系導出的最大密度相連的樣本集合，即為我們最終聚類的一個類別，或者說一個簇 。

    這個DBSCAN的簇裡面可以有一個或者多個核心對象。如果只有一個核心對象，則簇裡面其他的非核心對象樣本都在這個核心對象的ϵϵ-鄰域里；如果有多個核心對象，則簇里的任意一個核心對象的ϵϵ-鄰域中一定有一個其他的核心對象，否則這個核心對象無法密度可達。這些核心對象的ϵϵ-鄰域里所有的樣本的集合組成的一個DBSCAN聚類簇。

       那麼怎麼才能找到這樣的簇樣本集合呢？DBSCAN使用的方法很簡單，它任意選擇一個沒有類別的核心對象作為種子，然後找到所有這個核心對象能夠密度可達的樣本集合，即為一個聚類簇。接著繼續選擇另一個沒有類別的核心對象去尋找密度可達的樣本集合，這樣就得到另一個聚類簇。一直運行到所有核心對象都有類別為止。基本上這就是DBSCAN演算法的主要內容了，但是我們還有三個問題沒有考慮。

    1）一些異常樣本點或者說少量游離於簇外的樣本點，這些點不在任何一個核心對象的周圍，在DBSCAN中，我們一般將這些樣本點標記為噪音點。

    2）距離的度量問題，即如何計算某樣本和核心對象樣本的距離。在DBSCAN中，一般採用最近鄰思想，採用某一種距離度量來衡量樣本距離，比如歐式距離。這和KNN分類演算法的最近鄰思想完全相同。對應少量的樣本，尋找最近鄰可以直接去計算所有樣本的距離，比如樣本量較大，則一般採用KD樹或者球樹來快速的搜索最近鄰。

    3）某些樣本可能到兩個核心對象的距離都小於ϵϵ，但是這兩個核心對象由於不是密度直達，又不屬於同一個聚類簇，那麼如何界定這個樣本的類別呢？一般來說，此時DBSCAN採用先來後到，先進行聚類的類別簇會標記這個樣本為它的類別。也就是說DBSCAN的演算法不是完全穩定的演算法。

DBSCAN通過檢查數據集中的每個對象的ε-鄰域來尋找聚類，如果一個點p的ε-鄰域包含對於m個對象，則創建一個p作為核心對象的新簇。然後，DBSCAN反復地定址這些核心對象直接密度可達的對象，這個過程可能涉及密度可達簇的合並。當沒有新的點可以被添加到任何簇時，該過程結束。演算法中的ε和m是根據先驗只是來給出的。

DBSCAN聚類演算法原理的基本要點：

    1.DBSCAN演算法需要選擇一種距離度量，對於待聚類的數據集中，任意兩個點之間的距離，反應了點之間的密度，說明了點與點是否能夠聚到同一類中。由於DBSCAN演算法對高維數據定義密度很困難，所以對於二維空間中的點，可以使用歐幾里得距離來進行度量。

    2.DBSCAN演算法需要用戶輸入2個參數： 一個參數是半徑(Eps)，表示以給定點P為中心的圓形鄰域的范圍；另一個參數是以點P為中心的鄰域內最少點的數量(MinPts)。如果滿足：以點P為中心、半徑為Eps的鄰域內的點的個數不少於MinPts，則稱點P為核心點 。

    3.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)} 。

    4.根據經驗計算半徑Eps：根據得到的所有點的 k-距離集合E ，對集合E進行 升序排序 後得到k-距離集合 E' ，需要擬合一條排序後的E'集合中k-距離的變化曲線圖，然後繪出曲線，通過觀察， 將急劇發生變化的位置所對應的k-距離的值，確定為半徑Eps的值 。

    5.根據經驗計算最少點的數量MinPts： 確定MinPts的大小，實際上也是確定k-距離中k的值 ，DBSCAN演算法中取k=4，則MinPts=4。

    6.另外，如果覺得經驗值聚類的結果不滿意，可以適當調整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的值

    6.根據給定MinPts=4，以及半徑Eps的值，計算所有核心點，並建立核心點與核心點距離小於半徑Eps的點映射。

    7.根據得到的核心點集合，以及半徑Eps的值，計算能夠連通的核心點，並得到離群點。

    8.將能夠連通的每一組核心點，以及到核心點距離小於半徑Eps的點，都放到一起，形成一個簇。

    9.選擇不同的半徑Eps，使用DBSCAN演算法聚類得到的一組簇及其離群點，使用散點圖對比聚類效果。

    和傳統的K-Means演算法相比，DBSCAN最大的不同就是不需要輸入類別數K，當然它最大的優勢是可以發現任意形狀的聚類簇，而不是像K-Means，一般僅僅使用於凸的樣本集聚類。同時它在聚類的同時還可以找出異常點，這點和BIRCH演算法類似。

    那麼我們什麼時候需要用DBSCAN來聚類呢？一般來說，如果數據集是稠密的，並且數據集不是凸的，那麼用DBSCAN會比K-Means聚類效果好很多。 如果數據集不是稠密的，則不推薦用DBSCAN來聚類 。

    優點：

        1）可以對任意形狀的稠密數據集進行聚類，相對的，K-Means之類的聚類演算法一般只適用於凸數據集。不用指明類別的數量，能靈活找到並分離各種形狀和大小的類。能很好地處理雜訊和離群點。

        2）可以在聚類的同時發現異常點，對數據集中的異常點不敏感。

        3）聚類結果沒有偏倚，相對的，K-Means之類的聚類演算法初始值對聚類結果有很大影響。

    缺點：

         1）在不同密度的類方面有一定難度。如果樣本集的密度不均勻、聚類間距差相差很大時，聚類質量較差，這時用DBSCAN聚類一般不適合( HDBSCAN適合密度不均勻問題 )。

        2）如果樣本集較大時，聚類收斂時間較長，此時可以對搜索最近鄰近時建立的KD樹或者球樹進行規模限制來改進。當數據量增大時，要求較大的內存支持I/O消耗也很大；演算法聚類效果依賴與距離公式選取，實際應用中常用歐式距離，對於高維數據，存在「維數災難」。

        3）調參相對於傳統的K-Means之類的聚類演算法稍復雜，主要需要對距離閾值ϵϵ，鄰域樣本數閾值MinPts聯合調參，不同的參數組合對最後的聚類效果有較大影響。

        4）對於從兩類均可達的邊界點，由於各個點是被隨機訪問的，因此DBSCAN不能保證每次都返回相同的聚類。

    DBSCAN類的重要參數分為兩類，一類是DBSCAN演算法本身的參數，一類是最近鄰度量的參數，下面我們對這些參數做一個總結。

    1） eps： DBSCAN演算法參數，即我們的ϵ-鄰域的距離閾值，和樣本距離超過ϵ的樣本點不在ϵ-鄰域內。 默認值是0.5 ，一般需要通過在多組值裡面選擇一個合適的閾值。eps過大，則更多的點會落在核心對象的ϵ-鄰域，此時我們的類別數可能會減少，本來不應該是一類的樣本也會被劃分為一類。反之則類別數可能會增大，本來是一類的樣本卻被劃分開。

   2） min_samples： DBSCAN演算法參數，即樣本點要成為核心對象所需要的ϵ-鄰域的樣本數閾值。默認值是5。一般需要通過在多組值裡面選擇一個合適的閾值。通常和eps一起調參。在eps一定的情況下，min_samples過大，則核心對象會過少，此時簇內部分本來是一類的樣本可能會被標為噪音點，類別數也會變多。反之min_samples過小的話，則會產生大量的核心對象，可能會導致類別數過少。

    3） metric： 最近鄰距離度量參數。可以使用的距離度量比較多，一般來說DBSCAN使用默認的歐式距離(即p=2的閔可夫斯基距離)就可以滿足我們的需求。可以使用的距離量度參數有：歐式距離、曼哈頓距離、切比雪夫距離、閔可夫斯基距離、帶權重閔可夫斯基距離、標准化歐式距離、馬氏距離。

還有一些其他不是實數的距離度量，一般在DBSCAN演算法用不上，這里也就不列了。

    4）algorithm：最近鄰搜索演算法參數，演算法一共有三種，第一種是蠻力實現，第二種是KD樹實現，第三種是球樹實現。這三種方法與K近鄰法(KNN)原理中演算法一致。對於這個參數，一共有4種可選輸入，"brute"對應第一種蠻力實現,"kd_tree"對應於第二種KD樹實現，"ball_tree"對應於第三種的球樹實現，"auto"則會在上面三種演算法中做權衡，選擇一個擬合最好的最優演算法。 需要注意的是，如果輸入樣本特徵是稀疏的時候，無論我們選擇哪種演算法，最後sklearn都會去用蠻力實現"brute" 。個人的經驗，一般情況使用默認的"auto"就夠了。如果數據量很大或者特徵也很多，用「auto」建樹時間可能會很長，效率不高，建議選擇KD樹實現「kd_tree」,此時如果發現"kd_tree"速度比較慢或者已經知道樣本分布不是很均勻時，可以嘗試用"ball_tree"。

    5） leaf_size ：最近鄰搜索演算法參數，為使用KD樹或者球樹時，停止建子樹的葉子節點數量的閾值。這個值越小，則生成的KD樹或者球樹就越大，層數越深，建樹時間越長，反之，則生成的KD樹或者球樹會小，層數較淺，建樹時間較短。默認是30，因為這個值一般隻影響演算法是運行速度和使用內存大小，因此一般情況下可以不管它。

    6） p ：最近鄰距離度量參數。只有用於閔可夫斯基距離和帶權重閔客服斯基距離中p值的選擇，p=1為曼哈頓距離，p=2為歐式距離。如果使用默認的歐式距離不需要管這個參數。

以上就是DBSCAN類的主要參數介紹，其實需要調參的就是兩個參數eps和min_samples，這兩個值的組合對最終的聚類效果有很大的影響。