人工智能——DBSCAN密度聚類（Python）from sklearn.datasets import make_blobs:聚類資料生成器

目錄

​​1 概述​​

​​1.1 概念​​

​​1.2 DBSCAN資料點分類​​

​​2 DBSCAN算法流程 ​​

​​2.1 DBSCAN算法流程：​​

​​2.2 舉例​​

​​3 案例1（Python實作 ）​​

​​3.1 案例​​

​​3.2 Python實作​​

​​3.3 結果 ​​

​​3.4 拓展​​

​​4 案例2（Python實作）​​

​​4.1 代碼​​

​​4.2 結果​​

​​5 案例3（Python原碼實作）​​

​​5.1 代碼 ​​

​​5.2 結果 ​​

​​5.3 資料 ​​

​​6 參考​​

1 概述

上一次講解了人工智能——K-Means聚類算法（Python），這節課分享密度聚類：

1.1 概念

密度聚類，即基于密度的聚類(density-based clustering)，此類算法假設聚類結構能通過樣本分布的緊密程度确定。前面所講的都是把距離(歐式距離，闵科夫斯基距離，曼哈頓距離等)作為兩個樣本或者兩個簇之間相似度的評價名額，是以導緻了最終聚類結構大都是球狀簇或者凸形集合，對任意形狀的聚類簇比較吃力，同時對噪聲資料不敏感，而基于密度的聚類算法可以發現任意形狀的聚類，且對帶有噪音點的資料起着重要的作用。

DBSCAN算法

是一種基于密度的聚類算法：

•

聚類的時候不需要預先指定簇的個數

•

最終的簇的個數不定

1.2 DBSCAN資料點分類

DBSCAN算法将資料點分為三類：

•

核心點：在半徑Eps内含有超過MinPts數目的點

•

邊界點：在半徑Eps内點的數量小于MinPts，但是落在核心點的鄰域内

•

噪音點：既不是核心點也不是邊界點的點

2 DBSCAN算法流程

2.1 DBSCAN算法流程：

1.将所有點标記為核心點、邊界點或噪聲點；

2.删除噪聲點；

3.為距離在Eps之内的所有核心點之間賦予一條邊；

4.每組連通的核心點形成一個簇；

5.将每個邊界點指派到一個與之關聯的核心點的簇中（哪一個核心點的半徑範圍之内）。

2.2 舉例

有如下13個樣本點，使用DBSCAN進行聚類：

（1）取Eps=3，MinPts=3，依據DBSACN對所有點進行聚類（曼哈頓距離）。

（2）• 對每個點計算其鄰域Eps=3内的點的集合。

         • 集合内點的個數超過MinPts=3的點為核心點

         • 檢視剩餘點是否在核心點的鄰域内，若在，則為邊界點，否則為噪聲點。

（3）将距離不超過Eps=3的點互相連接配接，構成一個簇，核心點鄰域内的點也會被加入到這個簇中。 則下側形成3個簇。

3 案例1（Python實作 ）

3.1 案例

資料介紹：

現有大學校園網的日志資料，290條大學生的校園網使用情況資料，資料包

括使用者ID，裝置的MAC位址，IP位址，開始上網時間，停止上網時間，上

網時長，校園網套餐等。利用已有資料，分析學生上網的模式。

實驗目的：

通過DBSCAN聚類，分析學生

上網時間

和

上網時長

的模式。

實驗過程：

•

使用算法： DBSCAN聚類算法

•

實作過程：

資料執行個體：

3.2 Python實作

from sklearn.cluster import DBSCAN

DBSCAN主要參數

：

(1)eps: 兩個樣本被看作鄰居節點的最大距離

(2)min_samples: 簇的樣本數

(3)metric：距離計算方式

例：sklearn.cluster.DBSCAN(eps=0.5, min_samples=5, metric='euclidean')

#*===================1. 建立工程，導入sklearn相關包===========================**
import numpy as np
import sklearn.cluster as skc
from sklearn import metrics
from sklearn.cluster import DBSCAN
import matplotlib.pyplot as plt

#*=================2. 讀入資料并進行處理=====================================**
mac2id = dict()                             #mac2id是一個字典：key是mac位址value是對應mac位址的上網時長以及開始上網時間
onlinetimes = []                            #value:對應mac位址的上網時長以及開始上網時間
f = open('TestData.txt', encoding='utf-8')
for line in f:
    mac = line.split(',')[2]                 #讀取每條資料中的mac位址
    onlinetime = int(line.split(',')[6])     #上網時長
    starttime = int(line.split(',')[4].split(' ')[1].split(':')[0])   #開始上網時間
    if mac not in mac2id:                    #mac2id是一個字典：key是mac位址value是對應mac位址的上網時長以及開始上網時間
        mac2id[mac] = len(onlinetimes)
        onlinetimes.append((starttime, onlinetime))
    else:
        onlinetimes[mac2id[mac]] = [(starttime, onlinetime)]
real_X = np.array(onlinetimes).reshape((-1, 2))
X = real_X[:, 0:1]

#*==============3上網時間聚類，建立DBSCAN算法執行個體，并進行訓練，獲得标簽=============**
db = skc.DBSCAN(eps=0.01, min_samples=20).fit(X)  # 調 用 DBSCAN 方 法 進 行 訓 練 ，labels為每個資料的簇标簽
labels = db.labels_

#*=============4. 輸出标簽，檢視結果===========================================**
print('Labels:')                         #列印資料被記上的标簽，計算标簽為-1，即噪聲資料的比例。
print(labels)
raito = len(labels[labels[:] == -1]) / len(labels)
print('Noise raito:', format(raito, '.2%'))

n_clusters_ = len(set(labels)) - (1 if -1 in labels else 0)   #計算簇的個數并列印，評價聚類效果
print('Estimated number of clusters: %d' % n_clusters_)
print("Silhouette Coefficient: %0.3f" % metrics.silhouette_score(X, labels))

for i in range(n_clusters_):               #列印各簇标号以及各簇内資料
    print('Cluster ', i, ':')
    print(list(X[labels == i].flatten()))

#*==========5.畫直方圖，分析實驗結果========================================**
plt.hist(X, 24)
plt.show()


      

3.3 結果 

 轉換直方圖分析

 觀察：上網時間大多聚集在22：00和23：00

3.4 拓展

資料分布 vs 聚類：

3-1. 上網時間聚類，建立DBSCAN算法執行個體，并進行訓練，獲得标簽（上面已經分析過了）

3-2. 上網時長聚類，建立DBSCAN算法執行個體，并進行訓練，獲得标簽：

 結果：

Label表示樣本的類别，-1表示DBSCAN劃分為噪聲。

（1）按照上網時長DBSCAN聚了5類，右圖所示，顯示了每個聚類的樣本數量、聚

類的均值、标準差。

（2）時長聚類效果不如時間的聚類效果明顯。

4 案例2（Python實作）

4.1 代碼

from sklearn.datasets import make_blobs:聚類資料生成器

import numpy as np
import matplotlib.pyplot as plt
from sklearn import datasets
from sklearn.cluster import DBSCAN
#matplotlib inline
X1, y1=datasets.make_circles(n_samples=5000, factor=.6,
                                      noise=.05)
X2, y2 = datasets.make_blobs(n_samples=1000, n_features=2, centers=[[1.2,1.2]], cluster_std=[[.1]],
               random_state=9)

X = np.concatenate((X1, X2))      #矩陣合并
#展示樣本資料分布
plt.scatter(X[:, 0], X[:, 1], marker='o')
plt.show()
#eps和min_samples 需要進行調參
y_pred = DBSCAN(eps = 0.1, min_samples = 10).fit_predict(X)
#分類結果
plt.scatter(X[:, 0], X[:, 1], c=y_pred)
plt.show()      

4.2 結果

h2       

5 案例3（Python原碼實作）

5.1 代碼 

python中的zip()函數詳解

python中的map函數

#*============================導入相關庫=====================================**
import numpy as np
import numpy.random as random
from  numpy.core.fromnumeric import *      #檢視矩陣或者數組的維數
import matplotlib.pyplot as plt



#*========================計算兩個向量之間的歐式距離========================**
def calDist(X1 , X2 ):
    sum = 0
    for x1 , x2 in zip(X1 , X2):     #轉換成浮點型
        sum += (x1 - x2) ** 2
    return sum ** 0.5

#*==================擷取一個點的ε-鄰域（記錄的是索引）=====================**
def getNeibor(data , dataSet , e):
    res = []
    for i in range(shape(dataSet)[0]):
        if calDist(data , dataSet[i])<e:
            res.append(i)
    return res

#*===================密度聚類算法=======================================**
def DBSCAN(dataSet , e , minPts):
    coreObjs = {}#初始化核心對象集合
    C = {}
    n = shape(dataSet)[0]
    #找出所有核心對象，key是核心對象的index，value是ε-鄰域中對象的index
    for i in range(n):
        neibor = getNeibor(dataSet[i] , dataSet , e)
        if len(neibor)>=minPts:
            coreObjs[i] = neibor
    oldCoreObjs = coreObjs.copy()
    k = 0#初始化聚類簇數
    notAccess = list(range(n))#初始化未通路樣本集合（索引）
    while len(coreObjs)>0:
        OldNotAccess = []
        OldNotAccess.extend(notAccess)
        cores = coreObjs.keys()
        #随機選取一個核心對象
        randNum = random.randint(0,len(cores))
        cores=list(cores)
        core = cores[randNum]
        queue = []
        queue.append(core)
        notAccess.remove(core)
        while len(queue)>0:
            q = queue[0]
            del queue[0]
            if q in oldCoreObjs.keys() :
                delte = [val for val in oldCoreObjs[q] if val in notAccess]#Δ = N(q)∩Γ
                queue.extend(delte)#将Δ中的樣本加入隊列Q
                notAccess = [val for val in notAccess if val not in delte]#Γ = Γ\Δ
        k += 1
        C[k] = [val for val in OldNotAccess if val not in notAccess]
        for x in C[k]:
            if x in coreObjs.keys():
                del coreObjs[x]
    return C


#*=====================預處理資料====================================**
def loadDataSet(filename):
    dataSet = []
    fr = open(filename)
    for line in fr.readlines():
        curLine = line.strip().split(',')
        fltLine = map(float, curLine)
        dataSet.append(list(fltLine))
    return dataSet

def draw(C , dataSet):
    color = ['r', 'y', 'g', 'b', 'c', 'k', 'm']
    for i in C.keys():
        X = []
        Y = []
        datas = C[i]
        for j in range(len(datas)):
            X.append(dataSet[datas[j]][0])
            Y.append(dataSet[datas[j]][1])
        plt.scatter(X, Y, marker='o', color=color[i % len(color)], label=i)
    plt.legend(loc='upper right')
    plt.show()


#*============================主函數===============================**
def main():
    dataSet = loadDataSet("密度聚類.csv")
    print(dataSet)
    C = DBSCAN(dataSet, 0.11, 5)
    draw(C, dataSet)

if __name__ == '__main__':
    main()      

5.2 結果 

5.3 資料 

6 參考