R 下載 DBSCAN 套件

在R裡面有許多套件支援 DBSCAN 的分群,其中一個最常見的就是dbscan,必須先安裝並導入。

install.packages("dbscan")
library(dbscan)

程式碼撰寫

以下是你的程式碼:

data=read.csv("./變數.csv", sep=",", header=T)

data[(data=="" | data==" " | data=="  ")]=NA

data$public=ifelse(is.na(data$public), 1, data$public)
data$private=ifelse(is.na(data$private), 0, data$private)
data$PPP=ifelse(is.na(data$PPP), 0, data$PPP)

data$urban=ifelse(is.na(data$urban), 0, data$urban)
data$urban.or.rural=ifelse(is.na(data$urban.or.rural), 1, data$urban.or.rural)
data$rural=ifelse(is.na(data$rural), 0, data$rural)

上面 data 的資料格式是 dataframe,不過在 dbscan() 的輸入資料必須是 matrix,因此我們必須先把 data 轉換為 matrix 的形式。注意第一個欄位是 DRTS 路線的名稱,並非 dbscan 可處理的欄位,必須先剔除之。

data_mat=as.matrix(data[, 2:18])

dbscan 演算法的分群方法說明如下。DBSCAN (Density-based spatial clustering of applications with noise)演算法是以密度為基礎,利用資料分布的密集度將密度高的區域形成數個群集,而相對密度低者或零散資料點則視為雜訊或偏離值。DBSCAN 必須設定兩參數,一是鄰近區域的半徑(Eps),為每次探訪資料點的半徑,半徑愈大,分群的數目可能愈少;另一參數則為鄰近區域的最小點數(MinPts),若半徑(Eps)內之資料點數大於最小點數(MinPts),則將所有點資料劃分至同一群集中,若小於最小點數(MinPts)則將該資料群視為雜訊。根據上述參數的設定即可重複執行迭代演算,直至當前所有點無法再分類至該群集中。接著再自一個未曾訪問的資料點中選取其一資料,重複上述步驟完成所有資料點的聚類,直至所有資料點皆訪問完畢。

DBSCAN 演算程序整理如下圖所示。圖中假設半徑(Eps)為 ε,最小點數(MinPts)為 4,亦即每一次尋找群集時,需檢查半徑內是否有 4 個點,若有 則將所有點劃分至同一群集中。步驟①乃以 A 點為中心, ε 為半徑,將 A、 B、C、 D 四點劃分於同一範圍內,故四點歸類於同一群集。接著步驟②再以 B 點為中心, ε 為半徑,將 A、 B、 C、 E、 F五點劃分於同一範圍中,故亦歸類於同一群集中。以次類推,及至所有圖中的點劃分完畢後,剩餘無法歸類在任何一群集中的點即為噪點(noise),如圖中的 I 點。

dbscan 函式中須設定最大搜尋半徑和最小分群數目,在 data 這個資料中,eps 就是指所有變數的幾何距離(Euclidean Distance),譬如(0,1,1)和(1,0,1)兩個樣本的距離就會是√2。在 data 這組資料中,因為所有的變數都是0或1,所以最大距離其實就是一組「全為0的資料」,和一組「全為1的資料」兩者間的距離,也就是17√2(我們總共有17個變數~)。如果我們 eps 半徑設定的越大,就會使所有 DRTS 路線被我們分類到同一個類群中,這樣其實不是合理的分類結果;但半徑設太小,反而會產生非常多噪點,也不是我們預期的結果。 MinPts 表示每一個類群中最少的 DRTS 路線數。以下我們先來做隨機試驗:

假設搜尋半徑設定為1,類群最少路線數是2條

db = dbscan(data_mat, eps=1, minPts=2)
db$cluster
##  [1]  1  2  1  0  0  2  3  2  4  0  5  6  0  0  4  0  0  5  7  8  8  6  6  3  7
## [26]  0  7  0  0  9  0  0  9  9  9  0  0  0 10  0 10 10  0  0 10

程式碼中db$cluster表示每一條路線所分到的類組,如果數字是0,表示該條路線為噪點,無法分類在任何一群中。接著可以把這組向量和原本我們的 data 資料合併,就可以更明確了解各路線的分群(如表格最後一欄位所示)。

cbind(data, cluster=db$cluster)
X public private PPP urban urban.or.rural rural virtual PT.stop D2D Door.to.station virtual.to.station fixed.route DRT mixed.route phone web APP cluster
BT let’s go 1 0 0 1 0 0 0 1 0 0 0 1 0 0 1 1 1 1
Mobility bus 1 0 0 1 0 0 0 0 1 0 0 0 1 0 1 1 1 2
Edmonton Transit Service 1 0 0 1 0 0 0 1 0 0 0 1 0 0 1 1 1 1
NRT OnDemand 1 0 0 0 0 1 0 1 1 0 0 0 0 1 1 0 1 0
Chair-A-Van 1 0 0 0 0 1 1 0 0 0 0 1 0 0 1 0 1 0
Wheel-Trans 1 0 0 1 0 0 0 0 1 0 0 0 1 0 1 0 0 2
Dial-a-Ride transit 1 0 0 0 1 0 0 1 1 0 0 0 0 1 1 0 1 3
Transit Plus (Handi-Transit) 1 0 0 1 0 0 0 0 1 0 0 0 1 0 1 1 0 2
Kan-go 1 0 0 0 1 0 0 0 0 1 0 0 0 1 1 1 0 4
Telebus 1 0 0 0 0 1 0 0 1 1 0 0 0 1 1 1 0 0
Keolis Downer 1 0 0 1 0 0 1 0 0 0 0 1 0 0 1 1 1 5
Butler Area Rural Transit (BART) 1 0 0 0 0 1 0 0 1 0 0 0 1 0 1 1 0 6
Bay area rapid transit (BART) 1 0 0 1 0 0 0 1 0 1 0 0 0 1 1 1 1 0
FlexRide (Call-n-Ride service) 1 0 0 0 1 0 1 1 0 1 0 0 0 1 1 1 1 0
Flex Service 1 0 0 0 1 0 0 0 1 1 0 0 0 1 1 1 0 4
NeighborLink 1 0 0 0 0 1 0 0 1 1 0 0 1 0 1 1 1 0
Pace On Demand 1 0 0 0 1 0 0 1 0 0 0 1 0 0 1 1 1 0
Ride on Flex 1 0 0 1 0 0 1 0 0 0 0 1 0 0 1 1 1 5
Access-A-Ride 1 0 0 0 1 0 0 0 1 0 0 0 1 0 1 1 0 7
Bee-Line Paratransit 1 0 0 0 1 0 1 0 1 0 0 1 1 0 1 0 0 8
Qualla Community Resident Transportation 1 0 0 0 1 0 1 0 1 0 0 1 1 0 1 0 0 8
Night Shuttle 1 0 0 0 0 1 0 0 1 0 0 0 1 0 1 0 0 6
Rural General Public Program 1 0 0 0 0 1 0 0 1 0 0 0 1 0 1 0 0 6
DARTS (Dial-A-Ride Transportation Services) 1 0 0 0 1 0 0 1 1 0 0 0 0 1 1 0 0 3
Rural General Public (RGP) 1 0 0 0 1 0 0 0 1 0 0 0 1 0 1 0 0 7
Tel-A-Ride Service 1 0 0 0 1 0 1 0 0 0 0 1 0 0 1 0 1 0
MetroAccess Paratransit 1 0 0 0 1 0 0 0 1 0 0 0 1 0 1 1 0 7
Netliner 1 0 0 0 1 0 1 1 0 0 0 1 0 0 1 1 0 0
Allygator 0 1 0 1 0 0 0 0 1 0 0 0 1 0 0 0 1 0
Berlkoenig 0 0 1 1 0 0 1 1 0 0 0 1 0 0 0 0 1 9
EcoBus 0 0 1 1 0 1 0 0 1 0 0 0 1 0 1 1 1 0
Ioki Shuttle 0 0 1 0 1 0 0 0 0 1 0 0 0 1 0 0 1 0
MOIA 0 0 1 1 0 0 1 0 0 0 0 1 0 0 0 0 0 9
IsarTiger 0 0 1 1 0 0 0 1 0 0 0 1 0 0 0 0 1 9
SSB Flex 0 0 1 1 0 0 1 0 0 0 0 1 0 0 0 0 1 9
Flexigo 0 0 1 0 1 0 0 0 1 1 0 0 0 1 0 1 1 0
R?sa’Est 0 0 1 0 1 0 0 0 0 0 1 1 0 0 1 1 1 0
Chronopro 0 0 1 1 1 0 0 0 0 1 0 0 0 1 0 0 0 0
ViaVan 0 1 0 1 0 0 1 0 0 0 0 1 0 0 0 0 0 10
Breng flex 0 0 1 0 1 0 1 1 0 0 0 1 0 0 1 0 1 0
Slide 0 1 0 1 0 0 1 0 0 0 0 1 0 0 0 0 1 10
London Smart Ride 0 1 0 1 0 0 1 0 0 0 0 1 0 0 0 0 1 10
ViaVan 1 0 0 0 1 0 1 0 0 0 0 1 0 0 0 0 0 0
Chariot 0 1 0 0 1 0 0 1 0 0 0 1 0 0 0 0 1 0
PickMeUp 0 1 0 1 0 0 1 0 0 0 0 1 0 0 0 0 1 10

但是這裡就會衍生一個問題,我們根本不知道如何界定這兩個參數,所以可以嘗試使用 for 迴圈,將 dbscan 進行多次試驗,尋找最合適的分組方法。如果我們的目標是希望噪點最少,也就是得到的分群結果中數字0會是最少的,但同時也希望能分出合理的群組數。此時可以用以下方法去做多次測試。

test=data.frame()
for (i in seq(0.1, 2, 0.1)){
  for (j in c(2:5)){
    # 執行 dbscan 分群
    db = dbscan(data_mat, eps=i, minPts=j)
    
    # 利用 temp 儲存 dbscan 的結果
    temp=cbind(data, cluster=db$cluster)
    
    # 計算噪點個數
    noise_num=nrow(temp[temp$cluster==0,])
    
    # 計算分群數
    cluster_num=length(unique(temp$cluster[temp$cluster!=0]))
    
    # 把上面的分群結果和噪點個數、分群數全部記錄起來
    test=rbind(test, data.frame(eps=i, minPts=j, noise_num=noise_num, cluster_num=cluster_num))
  }
}
試驗結果如下:
eps minPts noise_num cluster_num
2.0 2 0 1
2.0 3 0 1
2.0 4 0 1
2.0 5 2 1
1.8 2 3 2
1.8 3 3 2
1.9 2 3 2
1.9 3 3 2
1.8 4 6 2
1.9 4 6 2
1.5 2 7 7
1.5 3 7 7
1.6 2 7 7
1.6 3 7 7
1.7 2 7 7
1.7 3 7 7
1.8 5 7 2
1.9 5 7 2
1.0 2 18 10
1.1 2 18 10
1.2 2 18 10
1.3 2 18 10
1.4 2 18 10
1.5 4 19 3
1.6 4 19 3
1.7 4 19 3
1.5 5 20 3
1.6 5 20 3
1.7 5 20 3
1.0 3 28 5
1.1 3 28 5
1.2 3 28 5
1.3 3 28 5
1.4 3 28 5
0.1 2 32 6
0.2 2 32 6
0.3 2 32 6
0.4 2 32 6
0.5 2 32 6
0.6 2 32 6
0.7 2 32 6
0.8 2 32 6
0.9 2 32 6
1.0 4 41 1
1.1 4 41 1
1.2 4 41 1
1.3 4 41 1
1.4 4 41 1
0.1 3 42 1
0.2 3 42 1
0.3 3 42 1
0.4 3 42 1
0.5 3 42 1
0.6 3 42 1
0.7 3 42 1
0.8 3 42 1
0.9 3 42 1
0.1 4 45 0
0.1 5 45 0
0.2 4 45 0
0.2 5 45 0
0.3 4 45 0
0.3 5 45 0
0.4 4 45 0
0.4 5 45 0
0.5 4 45 0
0.5 5 45 0
0.6 4 45 0
0.6 5 45 0
0.7 4 45 0
0.7 5 45 0
0.8 4 45 0
0.8 5 45 0
0.9 4 45 0
0.9 5 45 0
1.0 5 45 0
1.1 5 45 0
1.2 5 45 0
1.3 5 45 0
1.4 5 45 0

從表格和圖形,我們可以發現若將半徑設定為 2,且最小路線數設定為 2,此時噪點數會是最少的,達成我們最小化噪點數的目的。但事實上觀察表格可以發現,在此情境下只分類程一群,表示所有 DRTS 路線都是在同一個分群中,並不是我們所預期的結果。或許可以挑半徑設定為 1.5,且最小路線數設定為 2 之情境,此時可以分成 7 條路線,且只有 7 個噪點。

最後再來看看我們「半徑設定為 1.5,最小路線數設定為 2」 的分類結果!!
X public private PPP urban urban.or.rural rural virtual PT.stop D2D Door.to.station virtual.to.station fixed.route DRT mixed.route phone web APP cluster
BT let’s go 1 0 0 1 0 0 0 1 0 0 0 1 0 0 1 1 1 1
Mobility bus 1 0 0 1 0 0 0 0 1 0 0 0 1 0 1 1 1 2
Edmonton Transit Service 1 0 0 1 0 0 0 1 0 0 0 1 0 0 1 1 1 1
NRT OnDemand 1 0 0 0 0 1 0 1 1 0 0 0 0 1 1 0 1 3
Chair-A-Van 1 0 0 0 0 1 1 0 0 0 0 1 0 0 1 0 1 4
Wheel-Trans 1 0 0 1 0 0 0 0 1 0 0 0 1 0 1 0 0 2
Dial-a-Ride transit 1 0 0 0 1 0 0 1 1 0 0 0 0 1 1 0 1 3
Transit Plus (Handi-Transit) 1 0 0 1 0 0 0 0 1 0 0 0 1 0 1 1 0 2
Kan-go 1 0 0 0 1 0 0 0 0 1 0 0 0 1 1 1 0 5
Telebus 1 0 0 0 0 1 0 0 1 1 0 0 0 1 1 1 0 5
Keolis Downer 1 0 0 1 0 0 1 0 0 0 0 1 0 0 1 1 1 1
Butler Area Rural Transit (BART) 1 0 0 0 0 1 0 0 1 0 0 0 1 0 1 1 0 2
Bay area rapid transit (BART) 1 0 0 1 0 0 0 1 0 1 0 0 0 1 1 1 1 0
FlexRide (Call-n-Ride service) 1 0 0 0 1 0 1 1 0 1 0 0 0 1 1 1 1 0
Flex Service 1 0 0 0 1 0 0 0 1 1 0 0 0 1 1 1 0 5
NeighborLink 1 0 0 0 0 1 0 0 1 1 0 0 1 0 1 1 1 2
Pace On Demand 1 0 0 0 1 0 0 1 0 0 0 1 0 0 1 1 1 1
Ride on Flex 1 0 0 1 0 0 1 0 0 0 0 1 0 0 1 1 1 1
Access-A-Ride 1 0 0 0 1 0 0 0 1 0 0 0 1 0 1 1 0 2
Bee-Line Paratransit 1 0 0 0 1 0 1 0 1 0 0 1 1 0 1 0 0 2
Qualla Community Resident Transportation 1 0 0 0 1 0 1 0 1 0 0 1 1 0 1 0 0 2
Night Shuttle 1 0 0 0 0 1 0 0 1 0 0 0 1 0 1 0 0 2
Rural General Public Program 1 0 0 0 0 1 0 0 1 0 0 0 1 0 1 0 0 2
DARTS (Dial-A-Ride Transportation Services) 1 0 0 0 1 0 0 1 1 0 0 0 0 1 1 0 0 3
Rural General Public (RGP) 1 0 0 0 1 0 0 0 1 0 0 0 1 0 1 0 0 2
Tel-A-Ride Service 1 0 0 0 1 0 1 0 0 0 0 1 0 0 1 0 1 4
MetroAccess Paratransit 1 0 0 0 1 0 0 0 1 0 0 0 1 0 1 1 0 2
Netliner 1 0 0 0 1 0 1 1 0 0 0 1 0 0 1 1 0 1
Allygator 0 1 0 1 0 0 0 0 1 0 0 0 1 0 0 0 1 0
Berlkoenig 0 0 1 1 0 0 1 1 0 0 0 1 0 0 0 0 1 6
EcoBus 0 0 1 1 0 1 0 0 1 0 0 0 1 0 1 1 1 0
Ioki Shuttle 0 0 1 0 1 0 0 0 0 1 0 0 0 1 0 0 1 7
MOIA 0 0 1 1 0 0 1 0 0 0 0 1 0 0 0 0 0 6
IsarTiger 0 0 1 1 0 0 0 1 0 0 0 1 0 0 0 0 1 6
SSB Flex 0 0 1 1 0 0 1 0 0 0 0 1 0 0 0 0 1 6
Flexigo 0 0 1 0 1 0 0 0 1 1 0 0 0 1 0 1 1 7
R?sa’Est 0 0 1 0 1 0 0 0 0 0 1 1 0 0 1 1 1 0
Chronopro 0 0 1 1 1 0 0 0 0 1 0 0 0 1 0 0 0 7
ViaVan 0 1 0 1 0 0 1 0 0 0 0 1 0 0 0 0 0 6
Breng flex 0 0 1 0 1 0 1 1 0 0 0 1 0 0 1 0 1 0
Slide 0 1 0 1 0 0 1 0 0 0 0 1 0 0 0 0 1 6
London Smart Ride 0 1 0 1 0 0 1 0 0 0 0 1 0 0 0 0 1 6
ViaVan 1 0 0 0 1 0 1 0 0 0 0 1 0 0 0 0 0 4
Chariot 0 1 0 0 1 0 0 1 0 0 0 1 0 0 0 0 1 0
PickMeUp 0 1 0 1 0 0 1 0 0 0 0 1 0 0 0 0 1 6

以上只是目前我想到的方法,或許還有更好的設定參數方法,可以思考看看!!