DBSCAN算法理论和Python实现

傷城~ 2022-02-23 02:48 208阅读 0赞

*  [https://github.com/Sean16SYSU/MachineLearningImplement][https_github.com_Sean16SYSU_MachineLearningImplement]

## DBSCAN算法 ##

基于密度的聚类方法DBSCAN算法，是相当经典。  
算法思路很简单。  
**简述算法思路：**

1.  选取密度较高的点作为核心点
2.  通过一个核心点出发，把其领域的点都放入到广度优先搜索的队列中。
3.  将所有找到的点归结为一个类。之后，再从新的没有被访问过的点中找其他的核心点开始，又继续进行广度优先搜索。一直到所有的点都被访问过（即分配过了对对应的类别）

## Python实现 ##

*  导入数据

from sklearn import datasets
    import numpy as np 
    import matplotlib.pyplot as plt
    
    iris = datasets.load_iris()

*  算法实现

def DBSCAN(X, epsilon=1, MinPts=10):
        Nx = [0 for i in range(len(X))] 
        core_points = []
        for i, xi in enumerate(X):
            temp = np.array([np.linalg.norm(xi - cj) if i != j else np.inf for j, cj in enumerate(X)])
            Nx[i] =  set(np.where(temp < epsilon)[0])
            if len(Nx[i]) >= MinPts:
                core_points.append(i)
        k = 0
        not_visited = set([i for i in range(len(X))])
        
        Ck = [0 for i in range(len(X))] 
        if len(core_points) == 0:
            print("Not core_points")
        while len(core_points) > 0:
            not_visited_temp = not_visited
            
            o = core_points[np.random.randint(0, len(core_points))]
            Queue = [o]
            not_visited = not_visited - set(Queue)
            
            while len(Queue) > 0:
                q = Queue[0]
                Queue = Queue[1:]
                
                if len(Nx[q]) >= MinPts:
                    delta = Nx[q] & not_visited
                    Queue = Queue + list(delta)
                    not_visited = not_visited - delta
            Ck[k] = not_visited_temp - not_visited
            core_points = list(set(core_points) - Ck[k])
            k += 1
        Ans = np.zeros(len(X))
        for k_i in range(k):
            Ans[list(Ck[k_i])] = k_i
        return Ans

*  测试

test_y = DBSCAN(iris.data,)

*  画图

from sklearn.decomposition import PCA
    
    X_reduced = PCA(n_components=2).fit_transform(iris.data)
    plt.scatter(X_reduced[:, 0], X_reduced[:, 1], c=test_y, cmap=plt.cm.Set1)

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2ExOTk5MDQxMg_size_16_color_FFFFFF_t_70]

*  iris数据集其实是有三个类别的。应该是有些类别的数值数值波动特征不太明显。
 *  可以先做数据预处理之后，再做聚类，效果会好很多。

[https_github.com_Sean16SYSU_MachineLearningImplement]: https://github.com/Sean16SYSU/MachineLearningImplement
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2ExOTk5MDQxMg_size_16_color_FFFFFF_t_70]: /images/20220223/d1c5623e513c49479bb56824e54ab68b.png