亚洲免费在线-亚洲免费在线播放-亚洲免费在线观看-亚洲免费在线观看视频-亚洲免费在线看-亚洲免费在线视频

Python實現DBSCAN算法

系統 1964 0

? ? ? ?聲明:代碼的運行環境為Python3。Python3與Python2在一些細節上會有所不同,希望廣大讀者注意。本博客以代碼為主,代碼中會有詳細的注釋。相關文章將會發布在我的個人博客專欄《Python從入門到深度學習》,歡迎大家關注~


? ? ? ?K-Means算法、K-Means++算法以及Mean Shift算法都是基于距離的聚類算法,一般此類聚類的聚類結果都是球狀的簇,但當聚類結果是非球狀的時候,基于距離聚類的聚類算法得到的聚類結果并不是那么的好,然而,基于密度的聚類算法可以完美的解決此類問題。DBSCAN聚類算法是一種典型的基于密度的算法。

一、基本概念

? ? ? ?在DBSCAN算法中,有兩個基本的鄰域參數,分別是 鄰域和MinPts。其中 鄰域表示的是在數據集D中與樣本點 的距離不大于 的樣本。MinPts表示的是在樣本點 鄰域內的最少樣本點數目,基于此,在DBSCAN算法中數據點分為三類:核心點、邊界點、噪音點。

二、DBSCAN算法原理

? ? ? ?在DBSCAN算法中,由核心對象出發,找到與該核心對象密度可達的所有樣本形成一個聚類簇。其流程大致如下:

? ? ? ?(1)根據給定的鄰域參數 和MinPts確定所有的核心對象;

? ? ? ?(2)對每一個核心對象,選擇一個未處理過的核心對象,找到由其密度可達的樣本生成聚類簇;

? ? ? ?(3)重復上述過程。

? ? ? ?下面我們使用Python語言實現DBSCAN算法:

            
              def dbscan(data, eps, MinPts):
    '''
    DBSCAN算法
    :param data: 聚類的數據集
    :param eps: 半徑
    :param MinPts: 半徑內最少的數據點的個數
    :return: 返回每個樣本的類型、每個樣本所屬的類別
    '''
    m = np.shape(data)[0]
    # 區分核心點1,邊界點0和噪音點-1
    types = np.mat(np.zeros((1, m)))
    sub_class = np.mat(np.zeros((1, m)))
    # 用于判斷該點是否處理過,0表示未處理過
    dealed = np.mat(np.zeros((m, 1)))
    # 計算每個數據點之間的距離
    distance = dist(data)
    # 用于標記類別
    number = 1

    # 對每一個點進行處理
    for i in range(m):
        # 找到未處理的點
        if dealed[i, 0] == 0:
            # 找到第i個點到其他所有點的距離
            I = distance[i,]
            # 找到半徑eps內的所有點
            index = find_epsilon(I, eps)
            # 區分點的類型
            # 邊界點
            if len(index) > 1 and len(index) < MinPts + 1:
                types[0, i] = 0
                sub_class[0, i] = 0
            # 噪音點
            if len(index) == 1:
                types[0, i] = -1
                sub_class[0, i] = -1
                dealed[i, 0] = 1
            # 核心點
            if len(index) >= MinPts + 1:
                types[0, i] = 1
                for x in index:
                    sub_class[0, x] = number
                # 判斷核心點是否密度可達
                while len(index) > 0:
                    dealed[index[0], 0] = 1
                    I = distance[index[0],]
                    tmp = index[0]
                    del index[0]
                    index_1 = find_epsilon(I, eps)

                    if len(index_1) > 1:  # 處理非噪音點
                        for x1 in index_1:
                            sub_class[0, x1] = number
                        if len(index_1) >= MinPts + 1:
                            types[0, tmp] = 1
                        else:
                            types[0, tmp] = 0

                        for j in range(len(index_1)):
                            if dealed[index_1[j], 0] == 0:
                                dealed[index_1[j], 0] = 1
                                index.append(index_1[j])
                                sub_class[0, index_1[j]] = number
                number += 1

    # 最后處理所有未分類的點為噪音點
    index_2 = ((sub_class == 0).nonzero())[1]
    for x in index_2:
        sub_class[0, x] = -1
        types[0, x] = -1

    return types, sub_class
            
          

? ? ? ?其中,dist()方法用于計算每個數據點之間的距離,find_epsilon()方法用于找出距離小于等于epsilon樣本的下標,這兩個方法的實現過程如下:

(1)dist()方法

            
              def dist(data):
    '''
    計算每個數據點之間的距離
    :param data: 訓練數據
    :return: 返回計算結果
    '''
    m, n = np.shape(data)
    distance = np.mat(np.zeros((m, m)))
    for i in range(m):
        for j in range(i, m):
            tmp = 0
            for k in range(n):
                tmp += (data[i, k] - data[j, k]) * (data[i, k] - data[j, k])
            distance[i, j] = np.sqrt(tmp)
            distance[j, i] = distance[i, j]
    return distance
            
          

(2)find_epsilon()方法

            
              def find_epsilon(dist_i, eps):
    '''
    找出距離小于等于epsilon樣本下標
    :param dist_i: 樣本i和其他樣本之間的距離
    :param eps: 半徑
    :return: 返回距離小于等于eps樣本下標
    '''
    index = []
    n = np.shape(dist_i)[1]
    for j in range(n):
        if dist_i[0, j] <= eps:
            index.append(j)
    return index
            
          

? ? ? ?DBSCAN聚類算法的聚類結果是與 和MinPts有關系的,這里還需要定義一個 函數,當然也可以手動指定 的值:

            
              def epsilon(data, MinPts):
    '''
    計算最佳半徑
    :param data: 訓練數據
    :param MinPts: 半徑內數據點的個數
    :return:返回得到的最佳半徑
    '''
    m, n = np.shape(data)
    xMax = np.max(data, 0)
    xMin = np.min(data, 0)
    # np.prod()默認情況下計算所有元素的乘積
    eps = ((np.prod(xMax - xMin) * MinPts * math.gamma(0.5 * n + 1)) / (m * math.sqrt(math.pi ** n))) ** (1.0 / n)
    return eps
            
          

三、DBSCAN算法舉例

1、數據集:數據集有兩個特征,如下所示:

Python實現DBSCAN算法_第1張圖片

2、加載數據集

? ? ? ?我們此處使用如下方法加載數據集,也可使用其他的方式進行加載,此處可以參考我的另外一篇文章《Python兩種方式加載文件內容》。加載文件內容代碼如下:

            
              def load_data(file_path):
    '''
    加載數據
    :param file_path: 文件路徑
    :return: 以矩陣形式返回數據
    '''
    f = open(file_path)
    data = []
    for line in f.readlines():
        data_tmp = []
        lines = line.strip().split("\t")
        for x in lines:
            data_tmp.append(float(x.strip()))
        data.append(data_tmp)
    f.close()
    return np.mat(data)
            
          

3、保存聚類結果

? ? ? ?得到聚類結果之后,我們使用如下方法對聚類結果進行保存:

            
              def save_result(file_name, data):
    '''
    保存聚類結果
    :param file_name: 保存的文件名
    :param data: 需要保存的數據
    :return:
    '''
    f = open(file_name, "w")
    n = np.shape(data)[1]
    tmp = []
    for i in range(n):
        tmp.append(str(data[0, i]))
    f.write("\n".join(tmp))
    f.close()
            
          

4、調用DBSCAN算法

            
              if __name__ == "__main__":
    MinPts = 5  # 定義半徑內的最少的數據點的個數
    data = load_data("F://data.txt")
    eps = epsilon(data, MinPts)
    types, sub_class = dbscan(data, eps, MinPts)
    save_result("types", types)
    save_result("sub_class", sub_class)
            
          

5、得到的結果如下所示

Python實現DBSCAN算法_第2張圖片

? ? ? ? 你們在此過程中遇到了什么問題,歡迎留言,讓我看看你們都遇到了哪些問題。


更多文章、技術交流、商務合作、聯系博主

微信掃碼或搜索:z360901061

微信掃一掃加我為好友

QQ號聯系: 360901061

您的支持是博主寫作最大的動力,如果您喜歡我的文章,感覺我的文章對您有幫助,請用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧,狠狠點擊下面給點支持吧,站長非常感激您!手機微信長按不能支付解決辦法:請將微信支付二維碼保存到相冊,切換到微信,然后點擊微信右上角掃一掃功能,選擇支付二維碼完成支付。

【本文對您有幫助就好】

您的支持是博主寫作最大的動力,如果您喜歡我的文章,感覺我的文章對您有幫助,請用微信掃描上面二維碼支持博主2元、5元、10元、自定義金額等您想捐的金額吧,站長會非常 感謝您的哦!!!

發表我的評論
最新評論 總共0條評論
主站蜘蛛池模板: 99久久免费国产精品特黄 | 国产免费区 | 五月综合激情网 | 国产精品国偷自产在线 | 国内精品久久久久久久 | 青青国产成人久久91网 | 在线视频 中文字幕 | 全免费a级毛片免费看不卡 全免费a级毛片免费看视频免 | 欧美综合天天夜夜久久 | 久久国产精品吴梦梦 | 欧美乱大交xxxxx另类 | 4虎影院在线观看 | 精品综合网| 日日日日日 | 国内精品久久久久影院一蜜桃 | 亚洲欧美综合久久 | 五月激情五月婷婷 | 日本视频在线观看不卡高清免费 | 一个色在线 | 四虎影视1304t| 国内精品一区二区三区最新 | 99精品热线在线观看免费视频 | 国产成人香蕉在线视频网站 | 欧美第一精品 | 午夜欧美视频 | 国产精品伊人 | 欧美日韩色综合网站 | 香蕉视频在线观看www | 亚洲经典在线中文字幕 | 国产精品免费久久久久影院小说 | 欧美精品v国产精品v | 亚洲热线99精品视频 | 久久爱噜噜噜噜久久久网 | 日本三级11k影院在线 | 福利综合网 | 久久88| 色综合精品 | 国产亚洲美女精品久久久2020 | 奇米第四色视频 | 国内精品久久影院 | 成人在线黄色 |