原文鏈接：聚類（一）：DBSCAN算法實(shí)現(xiàn)（r語(yǔ)言）
微信公眾號(hào)：機(jī)器學(xué)習(xí)養(yǎng)成記? ? 搜索添加微信公眾號(hào)：chenchenwings
DBSCAN（Density-BasedSpatial Clustering of Applications with Noise）么夫，一種基于密度的聚類方法箕别，即找到被低密度區(qū)域分離的稠密區(qū)域嗅义，要求聚類空間中的一定區(qū)域內(nèi)所包含對(duì)象（點(diǎn)或其他空間對(duì)象）的數(shù)目不小于某一給定閾值。
Some points
一讳癌、兩個(gè)參數(shù)。
1奶浦，距離參數(shù)（Eps）
2私痹，鄰域內(nèi)點(diǎn)最少個(gè)數(shù)（MinPts）
二、根據(jù)基于中心的密度進(jìn)行點(diǎn)分類匠抗。
密度的基于中心的方法使得點(diǎn)分為三類：
1故源，核心點(diǎn)。稠密區(qū)域內(nèi)部的點(diǎn)汞贸。該點(diǎn)以Eps為半徑的區(qū)域內(nèi)點(diǎn)的個(gè)數(shù)不少于MinPts（包括自身）绳军。
2，邊界點(diǎn)矢腻。稠密區(qū)邊緣上的點(diǎn)门驾，不是核心點(diǎn)，但在某個(gè)或多個(gè)核心點(diǎn)鄰域內(nèi)踏堡。
3猎唁，噪聲點(diǎn)。稀疏區(qū)域中的點(diǎn)顷蟆，既非核心點(diǎn)也非邊界點(diǎn)诫隅。
4，密度可達(dá)帐偎。如果點(diǎn)p在核心點(diǎn)q的Eps鄰域內(nèi)逐纬，則稱p是從q出發(fā)可以直接密度可達(dá)。如果存在點(diǎn)鏈p1,p2, …, pn削樊，p1=q豁生，pn=p兔毒，pi+1是從pi直接密度可達(dá)，則稱點(diǎn)p是從q關(guān)于r和M密度可達(dá)的甸箱，密度可達(dá)是單向的育叁。
算法流程
從某點(diǎn)出發(fā)，將密度可達(dá)的點(diǎn)聚為一類芍殖，不斷進(jìn)行區(qū)域擴(kuò)張豪嗽，直至所有點(diǎn)都被訪問(wèn)。
R語(yǔ)言實(shí)現(xiàn)
在R中實(shí)現(xiàn)DBSCAN聚類豌骏，可以使用fpc包中的dbscan()函數(shù)龟梦。在下面的例子中，我們使用factoextra包中的數(shù)據(jù)集multishapes進(jìn)行演示窃躲。
如下可查看聚類后的結(jié)果：
具體每個(gè)樣本點(diǎn)的分類結(jié)果计贰，可用db$cluster查看，其中0表示噪聲點(diǎn)蒂窒，如下隨機(jī)顯示50個(gè)點(diǎn)的分類結(jié)果：
選擇最優(yōu)的Eps值
方法為計(jì)算每個(gè)點(diǎn)到其最近鄰的k個(gè)點(diǎn)的平均距離躁倒。k的取值根據(jù)MinPts由用戶指定。R語(yǔ)言中刘绣，使用dbscan包中的kNNdistplot（）函數(shù)進(jìn)行計(jì)算樱溉。
由圖可知，拐點(diǎn)處基本在0.15左右纬凤，因此可以認(rèn)為最優(yōu)Eps值在0.15左右福贞。
自定義距離公式
dbscan()函數(shù)中計(jì)算距離公式為歐式距離，在一些特定的場(chǎng)合無(wú)法使用停士，比如要計(jì)算地圖上兩點(diǎn)的距離挖帘，就要應(yīng)用特定的計(jì)算地圖上兩點(diǎn)的距離公式。
R里面的很多函數(shù)都是開(kāi)源的恋技，因此拇舀，直接運(yùn)行fpc::dbscan可以看到此函數(shù)的原程序。我們用geosphere包中的distm()函數(shù)對(duì)原程序中的距離計(jì)算公式進(jìn)行修改蜻底，實(shí)現(xiàn)地圖上兩點(diǎn)距離的計(jì)算骄崩。
將原程序中的distcomb函數(shù)改為如下形式：
將修改過(guò)的dbscan函數(shù)重新命名為disdbscan，重新將數(shù)據(jù)進(jìn)行聚類：
DBSCAN優(yōu)缺點(diǎn)
優(yōu)點(diǎn)：
（1）聚類速度快薄辅，且能夠有效處理噪聲點(diǎn)要拂。
（2）能發(fā)現(xiàn)任意形狀的空間聚類。
（3）聚類結(jié)果幾乎不依賴于點(diǎn)遍歷順序站楚。
（4）不需要輸入要?jiǎng)澐值木垲悅€(gè)數(shù)脱惰。
缺點(diǎn)：
（1）當(dāng)數(shù)據(jù)量增大時(shí)，要求較大的內(nèi)存支持I/O消耗也很大窿春；
（2）當(dāng)空間聚類的密度不均勻拉一、聚類間距差相差很大時(shí)采盒，聚類質(zhì)量較差。
微信公眾號(hào)：機(jī)器學(xué)習(xí)養(yǎng)成記? ? 搜索添加微信公眾號(hào)：chenchenwings
掃描二維碼蔚润，關(guān)注我們磅氨。
如需轉(zhuǎn)載，請(qǐng)?jiān)陂_(kāi)篇顯著位置注明作者和出處嫡纠，并在文末放置機(jī)器學(xué)習(xí)養(yǎng)成記二維碼和添加原文鏈接悍赢。
快來(lái)關(guān)注我們吧！
