Python реализует алгоритм DBSCAN

машинное обучение

Написанный в прошлом году алгоритм, реализованный на чистом питоне, опубликован. (Эффективность работы действительно спешит...)

Во время обхода вставляется слишком много циклов, что немного снижает эффективность операции. Вы должны компенсировать это хорошо. И это слишком вкусно ==

Здесь много введения в этот алгоритмWIKIиз

Первые результаты

image.png

Грубый процесс

  1. Сначала определяем центральную точку по заданному радиусу r, то есть количество точек n, содержащихся в радиусе r таких точек, больше нашего требования (n>=minPionts)
  2. Затем пройдите через все центральные точки,взаимно доступныйЦентральная точка сгруппирована с точками, которые она содержит
  3. После того, как все группы заполнены, баллы, не включенные ни в одну из групп, считаются выбросами!

Импорт связанных зависимостей

import numpy as np
import matplotlib.pyplot as plt
from sklearn import datasets

Найдите расстояние между точками (евклидово расстояние)

def cuircl(pointA,pointB):
    distance = np.sqrt(np.sum(np.power(pointA - pointB,2)))
    return distance

Найти временные кластеры, то есть определить все центральные точки, нецентральные точки

def firstCluster(dataSets,r,include):
    cluster = []
    m = np.shape(dataSets)[0]
    ungrouped = np.array([i for i in range (m)])
    for i in range (m):
        tempCluster = []
        #第一位存储中心点簇
        tempCluster.append(i)
        for j in range (m):
            if (cuircl(dataSets[i,:],dataSets[j,:]) < r and i != j ):
                tempCluster.append(j)
        tempCluster = np.mat(np.array(tempCluster))
        if (np.size(tempCluster)) >= include:
            cluster.append(np.array(tempCluster).flatten())
    #返回的是List
    center=[]
    n = np.shape(cluster)[0]
    for k in range (n):
        center.append(cluster[k][0])
    #其他的就是非中心点啦
    ungrouped = np.delete(ungrouped,center)
    #ungrouped为非中心点
    return cluster,center,ungrouped

Пройдите все центральные точки и соберите их

def clusterGrouped(tempcluster,centers):
    m = np.shape(tempcluster)[0]
    group = []
    #对应点是否遍历过
    position = np.ones(m)
    unvisited = []
    #未遍历点
    unvisited.extend(centers)
    #所有点均遍历完毕
    for i  in range (len(position)):
        coreNeihbor = []
        result = []
        #删除第一个
        #刨去自己的邻居结点，这一段就类似于深度遍历
        if position[i]:
        #将邻结点填入
            coreNeihbor.extend(list(tempcluster[i][:]))
            position[i] = 0
            temp = coreNeihbor
        #按照深度遍历遍历完所有可达点
        #遍历完所有的邻居结点
            while len(coreNeihbor) > 0 :
                #选择当前点
                present = coreNeihbor[0]
                for j in range(len(position)):
                    #如果没有访问过
                    if position[j] == 1:
                        same = []
                        #求所有的可达点
                        if (present in tempcluster[j]):
                            cluster = tempcluster[j].tolist()
                            diff = []
                            for x in cluster:
                                if x not in temp:
                                    #确保没有重复点
                                    diff.append(x)
                            temp.extend(diff)
                            position[j] = 0
                # 删掉当前点
                del coreNeihbor[0]
                result.extend(temp)
            group.append(list(set(result)))
        i +=1
    return group

Базовый алгоритм готов!

Генерация случайных данных типа концентрического круга для тестирования

#生成非凸数据 factor表示内外圈距离比
X,Y1 = datasets.make_circles(n_samples = 1500, factor = .4, noise = .07)


#参数选择，0.1为圆半径，6为判定中心点所要求的点个数，生成分类结果
tempcluster,center,ungrouped = firstCluster(X,0.1,6)
group = clusterGrouped(tempcluster,center)


#以下是分类后对数据进行进一步处理
num = len(group)
voice = list(ungrouped)
Y = []
for i in range (num):
   Y.append(X[group[i]])
flat = []
for i in range(num):
    flat.extend(group[i])
diff = [x for x in voice if x not in flat]
Y.append(X[diff])
Y = np.mat(np.array(Y))

рисунок~

color = ['red','blue','green','black','pink','orange']
for i in range(num):
    plt.scatter(Y[0,i][:,0],Y[0,i][:,1],c=color[i])
plt.scatter(Y[0,-1][:,0],Y[0,-1][:,1],c = 'purple')
plt.show()

результат:

Фиолетовые точки — это дискретные точки

image.png

Категории