《数据挖掘2015最新精品课程完整课件(第14讲)---基于密度的聚类》由会员分享，可在线阅读，更多相关《数据挖掘2015最新精品课程完整课件(第14讲)---基于密度的聚类（32页珍藏版）》请在金锄头文库上搜索。
1、基于密度的聚类方法 1 2 基于密度的聚类方法 划分和层次方法旨在发现球状簇 他们很难发现任意形状的簇 改进思想 将簇看作数据空间中由低密度区域分隔开的高密度对象区域 这是基于密度的聚类方法的主要策略 基于密度的聚类方法可以用来过滤噪声孤立点数据 发现任意形状的簇 DBSCAN 基于高密度连通区域聚类OPTICS 通过点排序识别聚类结构DENCLUE 基于密度分布函数的聚类 3 DBSCAN 基于密度的簇是密度相连的点的集合主要思想寻找被低密度区域分离的高密度区域只要临近区域的密度 单位大小上对象或数据点的数目 超过某个阈值 就继续聚类 4 DBSCAN 两个参数 Eps 邻域的最大半径Min
2、Pts 一个核心对象以Eps为半径的邻域内的最小顶点数 5 DBSCAN 密度 制定半径 Eps 内点的个数如果一个对象的Eps邻域至少包含最小数目MinPts个对象 则称该对象为核心对象 Corepoint 如果一个对象是非核心对象 但它的邻域中有核心对象 则称该对象为边界点 Borderpoint 除核心对象和边界点之外的点是噪声点 Noisepoint DBSCAN 核心 边界和噪声点 7 DBSCAN 密度可达的 Density reachable 对于对象p和核心对象q 关于E和MinPts 我们称p是从q 关于E和MinPts 直接密度可达 若对象p在对象q的E邻域内 如果存在一个
3、对象链p1 pn p1 q pn p pi 1是从pi关于Eps和MinPts直接密度可达的 则对象p是从对象q关于Eps和MinPts密度可达的 密度可达性是直接密度可达性的传递闭包 这种关系是非对称的 只有核心对象之间是相互可达的 8 DBSCAN 密度相连的 Density connected 如果对象集合D中存在一个对象o 使得对象p和q是从o关于Eps和MinPts密度可达的 那么对象p和q是关于Eps和MinPts密度相连的 密度相连性是一个对称的关系 DBSCAN算法概念示例 如图所示 用一个相应的半径表示 设MinPts 3 请分析Q M P S O R这5个样本点之间的关系
4、解答 根据以上概念知道 由于有标记的各点 M P O和R的 近邻均包含3个以上的点 因此它们都是核对象 M 是从P 直接密度可达 而Q则是从 M 直接密度可达 基于上述结果 Q是从P 密度可达 但P从Q无法 密度可达 非对称 类似地 S和R从O是 密度可达 的 O R和S均是 密度相连 的 基于密度方法的聚类 DBSCAN DBSCAN算法根据以上的定义在数据库中发现簇和噪声 簇可等价于集合D中簇核心对象密度可达的所有对象的集合 DBSCAN通过检查数据集中每个对象的 邻域来寻找聚类 如果一个点p的 邻域包含多于MinPts个对象 则创建一个p作为核心对象的新簇C 然后 DBSCAN从C中寻找
5、未被处理对象q的 邻域 如果q的 邻域包含多MinPts个对象 则还未包含在C中的q的邻点被加入到簇中 并且这些点的 邻域将在下一步中进行检测 这个过程反复执行 当没有新的点可以被添加到任何簇时 该过程结束 具体如下 DBSCAN算法步骤 输入 数据集D 参数MinPts 输出 簇集合 1 首先将数据集D中的所有对象标记unvisited 2 do 3 从D中随机选取一个unvisited对象p 并将p标记为visited ifp的 邻域包含的对象数至少为MinPts个创建新簇C 并把p添加到c中 令N为p的 邻域中对象的集合 7 forN中每个点piifpi是unvisited标记pi为vi
6、sited ifpi的 邻域至少有MinPts个对象 把这些对象添加到N ifpi还不是任何簇的对象 将pi添加到簇C中 12 endfor 13 输出C 14 Else标记p为噪声 15 Untill没有标记为unvisited的对象 基于密度方法的聚类 DBSCAN 下面给出一个样本事务数据库 见下表 对它实施DBSCAN算法 根据所给的数据通过对其进行DBSCAN算法 以下为算法的步骤 设n 12 用户输入 1 MinPts 4 样本事务数据库 DBSCAN聚类过程 第1步 在数据库中选择一点1 由于在以它为圆心的 以1为半径的圆内包含2个点 小于4 因此它不是核心点 选择下一个点 第2
7、步 在数据库中选择一点2 由于在以它为圆心的 以1为半径的圆内包含2个点 因此它不是核心点 选择下一个点 第3步 在数据库中选择一点3 由于在以它为圆心的 以1为半径的圆内包含3个点 因此它不是核心点 选择下一个点 DBSCAN聚类过程 第4步 在数据库中选择一点4 由于在以它为圆心的 以1为半径的圆内包含5个点 因此它是核心点 寻找从它出发可达的点 直接可达4个 间接可达3个 聚出的新类 1 3 4 5 9 10 12 选择下一个点 DBSCAN聚类过程 第5步 在数据库中选择一点5 已经在簇1中 选择下一个点 第6步 在数据库中选择一点6 由于在以它为圆心的 以1为半径的圆内包含3个点 因
8、此它不是核心点 选择下一个点 DBSCAN聚类过程 第7步 在数据库中选择一点7 由于在以它为圆心的 以1为半径的圆内包含5个点 因此它是核心点 寻找从它出发可达的点 聚出的新类 2 6 7 8 11 选择下一个点 DBSCAN聚类过程 第8步 在数据库中选择一点8 已经在簇2中 选择下一个点 第9步 在数据库中选择一点9 已经在簇1中 选择下一个点 第10步 在数据库中选择一点10 已经在簇1中 选择下一个点 第11步 在数据库中选择一点11 已经在簇2中 选择下一个点 第12步 选择12点 已经在簇1中 由于这已经是最后一点所有点都以处理 程序终止 基于密度方法的聚类 DBSCAN 算法执
9、行过程 19 DBSCAN OriginalPoints Clusters 特点 抗噪声能处理任意形状聚类 基于密度方法的聚类 优点能克服基于距离的算法只能发现 类圆形 的聚类的缺点 可发现任意形状的聚类 有效地处理数据集中的噪声数据 数据输入顺序不敏感缺点输入参数敏感 确定参数 MinPts困难 若选取不当 将造成聚类质量下降 由于在DBSCAN算法中 变量 MinPts是全局惟一的 当空间聚类的密度不均匀 聚类间距离相差很大时 聚类质量较差 计算密度单元的计算复杂度大 需要建立空间索引来降低计算量 且对数据维数的伸缩性较差 这类方法需要扫描整个数据库 每个数据对象都可能引起一次查询 因此当
10、数据量大时会造成频繁的I O操作 OPTICS算法 尽管dbscan能够根据给定的输入参数 和MinPts聚类对象 但是它把选择能产生可接受的聚类结果的参数值的责任留给了用户 这是许多其他算法都存在的问题 但是对于高维数据而言设定准确的参数非常困难 参数设置有细微的不同都可能导致差别很大的聚类结果 全局参数不能很好地刻画其内在的聚类结构 OPTICS算法 下图中所描述的数据集不能通过一个全局密度参数同时区分出簇A B C C1 C2和C3 只能得到A B C或C1 C2和C3 对于C1 C2和C3而言A B C都是噪声 对于固定的MinPts值 和两个 1 2 关于 1的MinPts簇C一定是
11、关于 2和MinPts簇C 的子集 这就意味着 如果两个对象在同一个基于密度的簇中 则它们也是在同一个具有较低密度要求的簇中 23 OPTICS 通过点排序识别聚类结构 对于真实的 高维的数据集合而言 参数的设置通常是依靠经验 难以确定 绝大多数算法对参数值是非常敏感的 设置的细微不同可能导致差别很大的聚类结果 OPTICS算法通过对象排序识别聚类结构 OPTICS没有显式地产生一个数据集合簇 它为自动和交互的聚类分析计算一个簇排序 这个次序代表了数据的基于密度的聚类结构 较稠密中的对象在簇排序中相互靠近 24 OPTICS 簇排序选择这样的对象 即关于最小的E值 它是密度可达的 以便较高密度
12、 较低E值 的簇先完成 对象p的核心距离 使p成为核心对象的最小 如果p不是核心对象 那么p的核心距离没有任何意义 可达距离 对象q到对象p的可达距离是指p的核心距离和p与q之间欧几里得距离之间的较大值 如果p不是核心对象 p和q之间的可达距离没有意义 OPTICS算法 核心距离与可达距离 假设 6mm MinPts 5 P的核心距离是p于第四个最近的数据对象之间的距离 q1到p的可达距离是p的核心距离 3mm 因为它比q1到p的欧氏距离大 q2关于p的可达距离是p到q2的欧氏距离 它大于p的核心距离 OPTICS算法 OPTICS算法并不显式的产生数据及聚类 而是输出簇排序 clustero
13、rdering 这个排序是所有分析对象的线性表 并且代表数据基于密度的聚类结构 较稠密簇中的对象在簇排序中相互靠近 这个排序等价于从较广泛的参数设置中得到基于密度的聚类 这样optics不需要用户提供特定密度阈值 簇排列可以用来提取基本聚类信息 导出内在的聚类结构 也可以提供聚类的可视化 OPTICS算法 为了构造不同的类 对象需要按特定的次序处理 这个次序选择这样的对象 及关于最小的 值 它是密度可达的 以便较高密度 较低 值 的簇先完成 optics算法计算给定数据库中所有对象的排序 并且存储每个对象核心距离和相应的可达距离 optics维护一个称作orderseeds的表来来产生输出排列
14、 orderseeds中的对象按到各自的最近核心对象的可达距离排序 及按每个对象的最小可达距离排序 28 OPTICS 通过点排序识别聚类结构 算法思路首先检查数据对象集合D中任一个对象的E 邻域 设定其可达距离为 未定义 并确定其核心距离 然后将对象及其核心距离和可达距离写入文件 如果P是核心对象 则将对象P的E 邻域内的对象N P 插入到一个种子队列中 包含在种子队列中的对象p 按到其直接密度可达的最近的核心对象q的可达距离排序 种子队列中具有最小可达距离的对象被首先挑选出来 确定该对象的E一邻域和核心距离 然后将其该对象及其核心距离和可达距离写入文件中 如果当前对象是核心对象 则更多的用
15、于扩展的后选对象被插入到种子队列中 这个处理一直重复到再没有一个新的对象被加入到当前的种子队列中 29 OPTICS 通过点排序识别聚类结构 Step1 有序种子队列初始为空 结果队列初始为空 Step2 如果所有点处理完毕 算法结束 否则选择一个未处理对象 即不在结果队列中 放入有序种子队列 Step3 如果有序种子队列为空 返回Step2 否则选择种子队列中的第一个对象P进行扩张 Step3 1 如果P不是核心节点 转Step4 否则 对P的E邻域内任一未扩张的邻居q进行如下处理Step3 1 1 如果q已在有序种子队列中且从P到q的可达距离小于旧值 则更新q的可达距离 并调整q到相应位置以保证队列的有序性 Step3 1 2 如果q不在有序种f队列中 则根据P到q的可达距离将其插入有序队列 Step4 从有序种子队列中删除P 并将P写入结果队列中 返回Step3 OPTICS 通过点排序识别聚类结构 数据集的排序可以用图形描述 有助于可视化和理解数据集中聚类结构 例如下图是一个简单的二维数据集的可达图 其中三个高斯 凸起 反映数据集中比较稠密的部分 30 参数的影响 减小 则可达距离为无穷大的点增多 MinPts减小 核心对象增多 图象更尖锐 不同密度 形状 大小的簇
