python实现dbscan算法
DBSCAN 算法是一种基于密度的空间聚类算法。该算法利用基于密度的聚类的概念,即要求聚类空间中的一定区域内所包含对象(点或其它空间对象)的数目不小于某一给定阀值。DBSCAN 算法的显著优点是聚类速度快且能够有效处理噪声点和发现任意形状的空间聚类。但是由于它直接对整个数据库进行操作且进行聚类时使用了一个全局性的表征密度的参数,因此也具有两个比较明显的弱点:
1. 当数据量增大时,要求较大的内存支持 I/0 消耗也很大;
2. 当空间聚类的密度不均匀、聚类间距离相差很大时,聚类质量较差。
DBSCAN算法的聚类过程
DBSCAN算法基于一个事实:一个聚类可以由其中的任何核心对象唯一确定。等价可以表述为: 任一满足核心对象条件的数据对象p,数据库D中所有从p密度可达的数据对象所组成的集合构成了一个完整的聚类C,且p属于C。
先上结果
大致流程
先根据给定的半径 r 确定中心点,也就是这类点在半径r内包含的点数量 n 大于我们的要求(n>=minPionts) 然后遍历所有的中心点,将互相可通达的中心点与其包括的点分为一组 全部分完组之后,没有被纳入任何一组的点就是离群点啦!
导入相关依赖
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()
结果
紫色点就是离散点
(资源库 www.zyku.net)
原文链接:https://blog.csdn.net/program_G/article/details/117082408
上一篇:详解python字符串驻留技术
栏 目:Python教程
下一篇:Python源码解析之List
本文标题:python实现dbscan算法
本文地址:https://www.zyku.net/python/9721.html
您可能感兴趣的文章
- 01-16放射医学中级题库-放射医学中级题库应
- 12-01必剪添加视频标签方法介绍
- 02-07opporeno5设置快捷锁屏方法
- 09-15小米小爱同学上线工作打卡介绍
- 09-15iPhone年年焕新规则更改介绍
- 03-01华为手环6复制实体门禁卡教程
- 09-24OPPOK9Pro怎么唤醒语音助手
- 07-18ASP.NET编程简单实现生成静态页面的方
- 01-11一帆视频-一帆视频应用软件功能介绍
- 07-05高德地图新能源模式开启方法介绍
- 08-14华为耳机查找定位教程一览
- 06-10PHP获取数组中单列值的方法
- 01-28小米note9全面屏手势关闭方法
- 05-10执行docker ps命令,提示 "Cannot conne
- 03-04wordpress上传中文名附件乱码问题的解
- 09-14淘宝逛逛萌宠治愈所怎么上传视频
- 09-19铁路12306网页老人模式开启方法介绍
- 01-12如何修改CKEditor的内容CSS样式
- 12-05荣耀x20如何设置休眠时间
- 03-01华为mate40Pro相机专业模式打开方法
最近更新
阅读排行
猜你喜欢
- 08-13微信身份证过期更新技巧
- 07-05Linux fgrep命令
- 01-14潜江停车-潜江停车应用软件功能介绍
- 03-04wordpress自定义系统默认发信人的方法
- 01-11JCHealth-JCHealth应用软件功能介绍
- 06-30帝国CMS如何自动生成sitemap.xml网站
- 12-26律邦智库-律邦智库应用软件功能介绍
- 04-06小米11青春版恢复出厂设置方法
- 07-05Linux userconf命令
- 03-01vivox60pro双击熄屏设置方法