机器学习

浅入浅出:PageRank算法 使用 TextRank 算法为文本生成关键字和摘要 基于物品的协同过滤 如何使用MapReduce实现基于物品的协同过滤(1) 如何使用MapReduce实现基于物品的协同过滤(2) 浅入浅出:K近邻算法 使用mahout下的朴素贝叶斯分类器对新闻分类 使用Affinity Propagation进行聚类 K-medoids聚类 矩阵分解在推荐系统中的应用:NMF和经典SVD实战 使用特征递归消除筛选特征 如何分配权重 比较NMF、PCA和VQ 方差和协方差 基于SVD的协同过滤 逻辑斯谛回归代码实现 隐语义模型和NMF(非负矩阵分解) 使用PCA处理MNIST数据集 使用GBDT选取特征 基于贝叶斯的文本分类系统的数据库设计 在hadoop1.2.1上安装mahout 0.9 Hadoop 2.4 实现Kmeans聚类算法 在Iris数据集上对比PCA、LDA、NMF 基于贝叶斯的文本分类实战 单层决策树 Logistic regression(逻辑斯蒂回归) 基于用户的协同过滤 词袋模型与文档-词矩阵 如何实现拼音与汉字的互相转换 梯度下降法 如何判定相似度 MovieLens数据集介绍 基于KNN的文本分类实战 Jasper文本分类系列博客阅读摘录 使用 Mean Shift进行聚类 朴素贝叶斯的三个常用模型:高斯、多项式、伯努利 使用决策树处理iris数据集 浅入浅出:从Kmeans到Kmeans++ 如何持久化scikit-learn中训练好的模型 浅入浅出:DBSCAN聚类算法(1) 浅入浅出:DBSCAN聚类算法(2) 2015阿里移动推荐算法比赛第一赛季总结 爬山算法 使用朴素贝叶斯分类器划分邮件 层次聚类 基于MapReduce的频繁项集挖掘 搜狗实体关系提取比赛

浅入浅出:DBSCAN聚类算法(1)


#机器学习


2014-03-14

DBSCAN是基于密度的聚类方法。

1、基本概念

由于每个对象在实际应用中涉及到数值,所以这里也把“对象”叫做“数据点”,在平面上,一个数据点是二维的,可以使用两个值来表示一个数据点,例如(1.2,3)。一个数据集里的所有数据点应具有相同的维度。

r邻域:给定数据点在以其为中心的半径r内的邻域称为该数据点的r邻域。这个r邻域包含了给定的那个数据点,否则应称为r去心邻域。

核心对象:如果某数据点的r邻域内至少包含了MinPts个数据点,那么该数据点叫做核心对象。至于MinPts个数据点是否应该包含该数据点看个人的算法实现,差别不大。

直接密度可达:若数据点p在核心对象q的r邻域内,则p从q出发是直接密度可达的。

密度可达:设数据点点序列p(1),p(2),p(3),...,p(n),其中p(1)是核心对象,p(2)是从p(1)出发直接密度可达,p(n)从p(1)出发是密度可达的。

噪声:如果某个数据点的r邻域内没有任何其他数据点,则意味着该数据点也不在其他任何数据点的r邻域内,该数据点可以看做为噪声。

2、基本思路

1、给定数据点集合D,邻域半径r,以及最小数目MinPts。 生成簇标识C。
2、选取一个未被标记的数据点p,判断该数据点是否为核心对象,若是核心对象则跳到步骤3,否则4。
3、将数据点p密度可达的所有数据点标记为C,表明这些数据点已被分类且属于簇C。
4、若数据点p是噪声点,将p标记为噪声点,否则标记为非噪声点的非核心对象。
5、更新簇标识C,跳回2,直到所有数据点被标记。

分析一下,可以发现,如何获取某数据点在r邻域内的其他数据点是略有难度的。在维基百科中给出了两种解决思路:一种是构造距离矩阵,一种是使用空间索引。

3、更多

资料[1]给出了dbscan的较详细内容,包括伪代码、时间复杂度问题和优缺点。资料[2]列出了当前较有名的一些空间索引方法,其中包括R tree。如果要通过中文版速成R tree,请参考资料[3]。关于dbscan的matlab实现,请见资料[4]。

下篇文章讲述dbscan的matlab实现,链接:浅入浅出:DBSCAN聚类算法(2)

4、资料

  1. 关于dbscan
  2. 关于空间索引
  3. 关于R树
  4. DBSCAN的matlab实现

( 本文完 )