一坷牛、算法描述
? ??????DBSCAN(Density-Based Spatial Clustering of Applications with Noise，具有噪聲的基于密度的聚類方法)是一種很典型的密度聚類算法很澄，和K-Means京闰，BIRCH這些一般只適用于凸樣本集的聚類相比，DBSCAN既可以適用于凸樣本集痴怨，也可以適用于非凸樣本集忙干。DBSCAN算法的顯著優(yōu)點(diǎn)是聚類速度快且能夠有效處理噪聲點(diǎn)和發(fā)現(xiàn)任意形狀的空間聚類。
????????該算法利用基于密度的聚類的概念浪藻，即要求聚類空間中的一定區(qū)域內(nèi)所包含對(duì)象（點(diǎn)或其他空間對(duì)象）的數(shù)目不小于某一給定閾值。過濾低密度區(qū)域乾翔，發(fā)現(xiàn)稠密度樣本點(diǎn)爱葵。同一類別的樣本，他們之間的緊密相連的反浓，也就是說萌丈，在該類別任意樣本周圍不遠(yuǎn)處一定有同類別的樣本存在。
二雷则、基本概念
????????DBSCAN密度定義：DBSCAN是基于一組鄰域來描述樣本集的緊密程度的辆雾，參數(shù)?(?, MinPts)?用來描述鄰域的樣本分布緊密程度。其中月劈，??描述了某一樣本的鄰域距離閾值度迂，MinPts?描述了某一樣本的距離為?的鄰域中樣本個(gè)數(shù)的閾值藤乙。
三、密度可達(dá)和密度相連直觀解釋
????????從上圖可以很容易看出理解上述定義惭墓，圖中MinPts=5坛梁，紅色的點(diǎn)都是核心對(duì)象，因?yàn)槠?-鄰域至少有5個(gè)樣本腊凶。黑色的樣本是非核心對(duì)象划咐。所有核心對(duì)象密度直達(dá)的樣本在以紅色核心對(duì)象為中心的超球體內(nèi)，如果不在超球體內(nèi)钧萍，則不能密度直達(dá)褐缠。圖中用綠色箭頭連起來的核心對(duì)象組成了密度可達(dá)的樣本序列。在這些密度可達(dá)的樣本序列的?-鄰域內(nèi)所有的樣本相互都是密度相連的风瘦。
????????由密度可達(dá)關(guān)系導(dǎo)出的最大密度相連的樣本集合队魏，即為我們最終聚類的一個(gè)類別，或者說一個(gè)簇弛秋。這個(gè)DBSCAN的簇里面可以有一個(gè)或者多個(gè)核心對(duì)象器躏。如果只有一個(gè)核心對(duì)象，則簇里其他的非核心對(duì)象樣本都在這個(gè)核心對(duì)象的?-鄰域里蟹略；如果有多個(gè)核心對(duì)象登失，則簇里的任意一個(gè)核心對(duì)象的?-鄰域中一定有一個(gè)其他的核心對(duì)象，否則這兩個(gè)核心對(duì)象無法密度可達(dá)挖炬。這些核心對(duì)象的??-鄰域里所有的樣本的集合組成的一個(gè)DBSCAN聚類簇揽浙。
四、DBSCAN聚類算法流程
1意敛、DBSCAN發(fā)現(xiàn)簇的過程
?????????初始馅巷，給定數(shù)據(jù)集D中所有對(duì)象都被標(biāo)記為“unvisited”，DBSCAN隨機(jī)選擇一個(gè)未訪問的對(duì)象p草姻，標(biāo)記p為“visited”钓猬，并檢查p的?-領(lǐng)域是否至少包含MinPts個(gè)對(duì)象。如果不是撩独，則p被標(biāo)記為噪聲點(diǎn)敞曹。否則為p創(chuàng)建一個(gè)新的簇C，并且把p的?-領(lǐng)域中所有對(duì)象都放在候選集合N中综膀。DBSCAN迭代地把N中不屬于其他簇的對(duì)象添加到C中澳迫。在此過程中，對(duì)應(yīng)N中標(biāo)記為“unvisited”的對(duì)象 P'?,DBSCAN把它標(biāo)記為“visited”剧劝，并且檢查它的?-領(lǐng)域橄登，如果 P' 的?-領(lǐng)域至少包含MinPts個(gè)對(duì)象，則P' 的?-領(lǐng)域中的對(duì)象都被添加到N中。DBSCAN繼續(xù)添加對(duì)象到C拢锹，直到C不能擴(kuò)展谣妻，即直到N為空。此時(shí)簇C完成生成面褐，輸出拌禾。
? ? ?為了找到下一個(gè)簇，DBSCAN從剩下的對(duì)象中隨機(jī)選擇一個(gè)未訪問過的對(duì)象展哭。聚類過程繼續(xù)湃窍，直到所有對(duì)象都被訪問。
還需考慮三個(gè)問題：
????????第一個(gè)是一些異常樣本點(diǎn)或者說少量游離于簇外的樣本點(diǎn)匪傍，這些點(diǎn)不在任何一個(gè)核心對(duì)象在周圍您市，在DBSCAN中，我們一般將這些樣本點(diǎn)標(biāo)記為噪音點(diǎn)役衡。DBSCAN算法很容易檢測異常點(diǎn)茵休。
????????第二個(gè)是距離的度量問題，即如何計(jì)算某樣本和核心對(duì)象樣本的距離手蝎。在DBSCAN中榕莺，一般采用最近鄰思想，采用某一種距離度量來衡量樣本距離棵介，比如歐式距離钉鸯。這和KNN分類算法的最近鄰思想完全相同。對(duì)應(yīng)少量的樣本邮辽，尋找最近鄰可以直接去計(jì)算所有樣本的距離唠雕，如果樣本量較大，則一般采用KD樹或者球樹來快速的搜索最近鄰吨述。
????????第三種問題岩睁，某些樣本可能到兩個(gè)核心對(duì)象的距離都小于?，但是這兩個(gè)核心對(duì)象由于不是密度直達(dá)揣云，又不屬于同一個(gè)聚類簇捕儒，那么如果界定這個(gè)樣本的類別呢？一般來說邓夕，此時(shí)DBSCAN采用先來后到肋层，先進(jìn)行聚類的類別簇會(huì)標(biāo)記這個(gè)樣本為它的類別。也就是說BDSCAN的算法不是完全穩(wěn)定的算法翎迁。
2、DBSCAN算法流程
五净薛、DBSCAN算法優(yōu)缺點(diǎn)
優(yōu)點(diǎn)：
? ? ? ? 和傳統(tǒng)的K-Means算法相比汪榔，DBSCAN最大的不同就是不需要輸入類別數(shù)k，當(dāng)然它最大的優(yōu)勢是可以發(fā)現(xiàn)任意形狀的聚類簇，而不是像K-Means痴腌，一般僅僅使用于凸的樣本集聚類雌团。同時(shí)它在聚類的同時(shí)還可以找出異常點(diǎn)，對(duì)數(shù)據(jù)集中的異常點(diǎn)不敏感士聪。一般來說锦援，如果數(shù)據(jù)集是稠密的，并且數(shù)據(jù)集不是凸的剥悟，那么用DBSCAN會(huì)比K-Means聚類效果好很多灵寺。如果數(shù)據(jù)集不是稠密的，則不推薦用DBSCAN來聚類区岗。
缺點(diǎn)：
????????1略板、如果樣本集的密度不均勻、聚類間距差相差很大時(shí)慈缔，聚類質(zhì)量較差叮称，這時(shí)用DBSCAN聚類一般不適合。
? ? ? ? 2藐鹤、調(diào)參相對(duì)于傳統(tǒng)的K-Means之類的聚類算法稍復(fù)雜瓤檐，主要需要對(duì)距離閾值?，鄰域樣本數(shù)閾值MinPts聯(lián)合調(diào)參娱节，不同的參數(shù)組合對(duì)最后的聚類效果有較大影響挠蛉。一般這兩個(gè)參數(shù)的確定靠經(jīng)驗(yàn)值。如果覺得經(jīng)驗(yàn)值聚類的結(jié)果不滿意括堤，可以適當(dāng)調(diào)整?和MinPts的值碌秸，經(jīng)過多次迭代計(jì)算對(duì)比，選擇最合適的參數(shù)值悄窃。如果MinPts不變讥电，?取得值過大，會(huì)導(dǎo)致大多數(shù)點(diǎn)都聚到同一個(gè)簇中轧抗，?過小恩敌，會(huì)導(dǎo)致一個(gè)簇的分裂；如果?不變横媚，MinPts的值取得過大纠炮，會(huì)導(dǎo)致同一個(gè)簇中點(diǎn)被標(biāo)記為離群點(diǎn)，?過小灯蝴，會(huì)導(dǎo)致發(fā)現(xiàn)大量的核心點(diǎn)恢口。
????????3、不適合高維數(shù)據(jù)穷躁，可以先進(jìn)行降維操作
? ? ? ? 4耕肩、Sklearn中效率很慢，可以先執(zhí)行數(shù)據(jù)削減策略
六、分類效果演示
