找回密码
 立即注册

本文来自

电脑/上网

电脑/上网

订阅|关注

致力于提供软件新闻发布,和软件知识学习,包括常用软件应用技巧及评测,创意设计相关的图文及视频教程

Python——DBSCAN聚类

[复制链接]
490 wsh9308 发表于 2017-9-14 13:24:53
密度聚类(Density-based Clustering)假设聚类结构能够通过样本分布的紧密程度来确定。DBSCAN是常用的密度聚类算法,它通过一组邻域参数(?,MinPts)来描述样本分布的紧密程度。给定数据集D={x? 1,x? 2,x? 3,...,x? N},数据集属性定义如下。
?-邻域:N?(x? i)={x? j∈D|distance(x? i,x? j)≤?},N?(x? i)包含了样本集D中与x? i距离不大于?的所有样本。
核心对象core object:若|N?(x? i)|≥MinPts,则称x? i是一个核心对象。即:若x? i的?-邻域中至少包含MinPts个样本,则称x? i是一个核心对象。
密度直达directly density-reachable:若x? i是一个核心对象,且x? j∈N?(x? i),则称x? j由x? i密度直达,记作x? i– x? j。
密度可达density-reachable:对于x? i和x? j,若存在样本序列(p? 0,p? 1,p? 2,...,p? m,p? m+1),其中p? 0=x? i,p? m+1=x? j,p? s∈D,s=1,2,...,m。如果p? s+1由p? s,s=1,2,...,m密度直达,则称x? j由x? i密度可达,记作x? i~ x? j。
密度相连density-connected:对于x? i和x? j,若存在x? k,使得x? i和x? j均由x? k密度可达,则称x? j由x? i密度相连,记作x? i~x? j。
DBSCAN算法的定义:给定邻域参数(?,MinPts),一个簇C?D是满足下列性质的非空样本子集:
接性connectivity:若x? i∈C,x? j∈C,则x? i~x? j
大性maximality:若x? i∈C,且→xi~ x? j,则x? j∈C
即一个簇是有密度可达关系导出的最大的密度相连样本集合。
DBSCAN算法的思想:若x? 为核心对象,则x? 密度可达的所有样本组成的集合X=
{x? ?∈D|x? ~ x? ?},可以证明X就是满足连接性与最大性的簇。于是DBSCAN算法首选任选数据集中的一个核心对象作为种子seed,再由此出发确定相应的聚类簇。
下面给出DBSCAN算法:
初始化核心对象集合为空集:Ω=?
寻找核心对象:遍历所有的样本点x? i,i=1,2,...,N,计算N?(x? i),如果|N?(x? i)|≥MinPts,则Ω=Ω?{x? i}
迭代:以任一未访问过的核心对象为出发点,找出有其密度可达的样本生成的聚类簇,直到所有的核心对象都被访问为止
class sklearn.cluster.DBSCAN(eps=0.5,min_samples=5,metric='euclidean',algorithm='auto',leaf_size=30,p=None,random_state=None)
参数
min_samples:MinPts参数,用于判断核心对象。
metric:一个字符串或可调用对象,用于计算距离。如果是字符串,则必须是在metrics.pairwise.calculate_distance中指定。
algorithm:一个字符串,用于计算两点间距离并找出最近邻的点,可以为如下:
‘auto’:由算法自动取舍合适的算法。
‘ball_tree’:用ball树来搜索。
‘kd_tree’:用kd树搜索。
‘brute’:暴力搜索。
leaf_size:一个整数,用于指定当algorithm=ball_tree或kd_tree时,树的叶节点大小。该参数会影响构建树,搜索最近邻的速度,同时影响树的内存。
random_state:被废弃的接口,将在scikit-learn v 0.18中移除。
components_:核心样本的一份副本。
labels_:每个样本所属的簇标记。对于噪声样本,其簇标记为-1副本。
fit(X[,y,sample_weight]):训练模型。
fit_predict(X[,y,sample_weight]):训练模型并预测每个样本所属的簇标记。
import matplotlib.pyplot as plt
from sklearn.datasets.samples_generator import make_blobs
from sklearn import mixture
from sklearn.svm.libsvm import predict
def create_data(centers,num=100,std=0.7):
X,labels_true = make_blobs(n_samples=num,centers=centers, cluster_std=std)
return X,labels_true
X,labels_true = create_data(centers,1000,0.5)
plt.plot(X[:, 0], X[:, 1], 'o', markeredgecolor='k', markersize=14)
plt.show()

predict_labels = clst.fit_predict(X)
print("ARI:%s"%adjusted_rand_score(labels_true,predict_labels))
print("Core sample num:%d"%len(clst.core_sample_indices_))
predicted_labels = clst.fit_predict(X)
ARIs.append(adjusted_rand_score(labels_true,predicted_labels))
Core_nums.append(len(clst.core_sample_indices_))
fig = plt.figure(figsize=(10,5))
ax = fig.add_subplot(1,2,1)
ax.plot(epsilons,ARIs,marker = '+')
ax.set_xscale('log')
ax.set_xlabel(r"$\epsilon$")
ax.set_ylim(0,1)
ax.set_ylabel('ARI')
ax = fig.add_subplot(1,2,2)
ax.plot(epsilons,Core_nums,marker='o')
ax.set_xscale('log')
ax.set_xlabel(r"$\epsilon$")
ax.set_ylabel('Core_num')
fig.suptitle("DBSCAN")
plt.show()
centers = [[1,1],[1,2],[2,2],[10,20]]
X,labels_true = create_data(centers,1000,0.5)
test_DBSCAN_epsilon(X,labels_true)

?参数的影响结果如上图所示:
可以看到ARI指数随着?的增长,先上升后保持平稳,最后悬崖式下降。悬崖式下降是因为我们产生的训练样本的间距比较小,最远的两个样本之间的距离不超过30,当?过大时,所有的点都在一个邻域中。
样本核心数量随着?的增长而上升,这是因为随着?的增长,样本点的邻域在扩展,则样本点邻域中的样本会增多,这就产生了更多满足条件的核心样本点。但是样本集中的样本数量有限,因此核心样本点的数量增长到一定数目后会趋于稳定。
下面接着考察MinPts参数的影响:
def test_DBSCAN_min_samples(*data):
X,labels_true=data
min_samples=range(1,100)
ARIs=[]
Core_nums=[]
for num in min_samples:
clst=cluster.DBSCAN(min_samples=num)
predicted_labels=clst.fit_predict(X)
ARIs.append(adjusted_rand_score(labels_true, predicted_labels))
Core_nums.append(len(clst.core_sample_indices_))
fig=plt.figure(figsize=(10,5))
ax=fig.add_subplot(1,2,1)
ax.plot(min_samples,ARIs,marker='+')
ax.set_xlabel("min_samples")
ax.set_ylim(0,1)
ax.set_ylabel('ARI')
ax=fig.add_subplot(1,2,2)
ax.plot(min_samples,Core_nums,marker='o')
ax.set_xlabel("min_samples")
ax.set_ylabel('Core_nums')
fig.suptitle("DBSCAN")
plt.show()
centers = [[1,1],[1,2],[2,2],[10,20]]
X,labels_true = create_data(centers,1000,0.5)
test_DBSCAN_min_samples(X,labels_true)

MinPts参数的影响结果如下:
可以看出ARI指数随着MinPts的增长,平稳地下降。而核心样本数量随着MinPts的增长基本呈线性下降,这是因为随着MinPts的增长,样本点的邻域中必须包含更多的样本才能使它成为一个核心点。因此产生的样本点数量越来越少。
Centos 7中的HaDoop伪分布式安装
Haiyang_Duan:
如有需要:本次安装所需的hadoop2.7.3以及jdk1.8下载地址:http://pan.bai...

本帖子中包含更多资源

您需要 登录 才可以下载或查看,没有帐号?立即注册

x
温馨提示:
1、在论坛里发表的文章仅代表作者本人的观点,与本网站立场无关。
2、论坛的所有内容都不保证其准确性,有效性,时间性。阅读本站内容因误导等因素而造成的损失本站不承担连带责任。
3、若因线路及非本站所能控制范围的故障导致暂停服务期间造成的一切不便与损失,论坛不负任何责任。
4,本网站内容均摘自其他网站,如涉及侵权定当第一时间删除
5、如侵犯您的权益请联系936144721@qq.com



上一篇:Effective C++ 1.0
下一篇:肉碎豆腐的做法,肉碎豆腐怎么做好吃,肉碎豆腐的家常
转载请说明出处,本文地址:http://bbs.imicun.com/thread-15469114-1-1.html
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

快速回复 返回顶部 返回列表