基于密度方法的聚类ppt课件.ppt

聚类分析 宋宜飞 主要内容 回顾密度聚类方法DBSCAN算法OPTICS算法网格聚类方法CLIQUE算法 回顾 聚类聚类 clustering 也称为聚类分析 指将样本分到不同的组中使得同一组中的样本差异尽可能的小 而不同组中的样本差异尽可能的大 聚类得到的不同的组称为簇 cluster 一个好的聚类方法将产生以下的聚类最大化类中的相似性最小化类间的相似性 回顾 聚类的分类 划分聚类方法层次聚类方法密度聚类方法网格聚类方法模型聚类方法 在基于划分的聚类中 任务就是将数据划分成K个不相交的点集 使每个子集中的点尽可能同质 基于划分的方法 其代表算法有k means算法 K medoids等 划分聚类方法 k means算法 k means算法基本步骤从n个数据对象任意选择k个对象作为初始聚类中心 根据每个聚类对象的均值 中心对象 计算每个对象与这些中心对象的距离 并根据最小距离重新对相应对象进行划分 重新计算每个 有变化 聚类的均值 中心对象 计算标准测度函数 当满足一定条件 如函数收敛时 则算法终止 如果条件不满足则回到步骤2 k means优缺点 主要优点 是解决聚类问题的一种经典算法 简单 快速 对处理大数据集 该算法是相对可伸缩和高效率的 当结果簇是密集的 它的效果较好 主要缺点在簇的平均值被定义的情况下才能使用 必须事先给出k 要生成的簇的数目 而且对初值敏感 对于不同的初始值 可能会导致不同结果 不适合于发现非凸面形状的簇或者大小差别很大的簇 而且 它对于 躁声 和孤立点数据是敏感的 层次聚类方法 层次聚类方法对给定的数据集进行层次的分解 直到某种条件满足为止 具体又可分为 凝聚的层次聚类 一种自底向上的策略 首先将每个对象作为一个簇 然后合并这些原子簇为越来越大的簇 直到某个终结条件被满足 分裂的层次聚类 采用自顶向下的策略 它首先将所有对象置于一个簇中 然后逐渐细分为越来越小的簇 直到达到了某个终结条件 层次凝聚的代表是AGNES算法 层次分裂的代表是DIANA算法 层次聚类优缺点 层次聚类方法是不可逆的 也就是说 当通过凝聚式的方法将两组合并后 无法通过分裂式的办法再将其分离到之前的状态 反之亦然 另外 层次聚类过程中调查者必须决定聚类在什么时候停止 以得到某个数量的分类 在不必要的情况下应该小心使用层次聚类方法 划分聚类方法层次聚类方法密度聚类方法 基于密度的聚类方法以数据集在空间分布上的稠密程度为依据进行聚类 无需预先设定簇的数量 因此特别适合对于未知内容的数据集进行聚类 网格聚类方法模型聚类方法 密度聚类方法 基于密度方法的聚类 密度聚类方法的指导思想是 只要一个区域中的点的密度大于某个域值 就把它加到与之相近的聚类中去 对于簇中每个对象 在给定的半径 的邻域中至少要包含最小数数目 MinPts 个对象 这类算法能克服基于距离的算法只能发现 类圆形 的聚类的缺点 可发现任意形状的聚类 且对噪声数据不敏感 代表算法有 DBSCAN OPTICS DENCLUE算法等 基于密度方法的聚类 DBSCAN DBSCAN Density BasedSpatialClusteringofApplicationswithNoise 一个比较有代表性的基于密度的聚类算法 与层次聚类方法不同 它将簇定义为密度相连的点的最大集合 能够把具有足够高密度的区域划分为簇 并可在有 噪声 的空间数据库中发现任意形状的聚类 传统基于中心的密度定义为 数据集中特定点的密度通过该点 半径之内的点计数 包括本身 来估计 显然 密度依赖于半径 传统的密度定义 基于中心的方法 基于密度方法的聚类 DBSCAN所用到的基本术语 定义对象的 邻域 给定对象在半径 内的区域 定义核心对象 如果一个对象的 邻域至少包含最小数目MinPts个对象 则称该对象为核心对象 例下图中 1cm MinPts 5 q是一个核心对象 定义直接密度可达 给定一个对象集合D 如果p是在q的 邻域内 而q是一个核心对象 我们说对象p从对象q出发是直接密度可达的 例在下图中 1cm MinPts 5 q是一个核心对象 对象p1从对象q出发是直接密度可达的 基于密度方法的聚类 DBSCAN所用到的基本术语 密度可达 定义密度可达的 如果存在一个对象链p1 p2 pn p1 q pn p 对pi D 1 i n pi 1是从pi关于 和MitPts直接密度可达的 则对象p是从对象q关于 和MinPts密度可达的 例在下图中 1cm MinPts 5 q是一个核心对象 p1是从q关于 和MitPts直接密度可达 p是从p1关于 和MitPts直接密度可达 则对象p从对象q关于 和MinPts密度可达的 基于密度方法的聚类 DBSCAN所用到的基本术语 图密度相连 图噪声 定义噪声 一个基于密度的簇是基于密度可达性的最大的密度相连对象的集合 不包含在任何簇中的对象被认为是 噪声 边界点 边界点不是核心点 但落在某个核心点的邻域内 噪声就是那些既不是边界点也不是核心点的对象 定义密度相连的 如果对象集合D中存在一个对象o 使得对象p和q是从o关于 和MinPts密度可达的 那么对象p和q是关于 和MinPts密度相连的 DBSCAN算法概念示例 如图所示 用一个相应的半径表示 设MinPts 3 请分析Q M P S O R这5个样本点之间的关系 直接密度可达 和 密度可达 概念示意描述 解答 根据以上概念知道 由于有标记的各点 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中寻找未被处理对象q的 邻域 如果q的 邻域包含多MinPts个对象 则还未包含在C中的q的邻点被加入到簇中 并且这些点的 邻域将在下一步中进行检测 这个过程反复执行 当没有新的点可以被添加到任何簇时 该过程结束 具体如下 基于密度方法的聚类 DBSCAN DBSCAN算法描述 输入 包含n个对象的数据库 半径 最少数目MinPts 输出 所有生成的簇 达到密度要求 1 REPEAT2 从数据库中抽取一个未处理过的点 3 IF抽出的点是核心点THEN找出所有从该点密度可达的对象 形成一个簇4 ELSE抽出的点是边缘点 非核心对象 跳出本次循环 寻找下一点 5 UNTIL所有点都被处理 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为visited 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步 在数据库中选择一点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个点 因此它不是核心点 选择下一个点 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 算法执行过程 DBSCAN的时间复杂性 时间复杂度DBSCAN算法要对每个数据对象进行邻域检查时间性能较低 DBSCAN的基本时间复杂度是O N 找出Eps领域中的点所需要的时间 N是点的个数 最坏情况下时间复杂度是O N2 在低维空间数据中 有一些数据结构如KD树 使得可以有效的检索特定点给定距离内的所有点 时间复杂度可以降低到O NlogN DBSCAM的空间复杂性 空间复杂度在聚类过程中 DBSCAN一旦找到一个核心对象 即以该核心对象为中心向外扩展 此过程中核心对象将不断增多 未处理的对象被保留在内存中 若数据库中存在庞大的聚类 将需要很大的存来存储核心对象信息 其需求难以预料 当数据量增大时 要求较大的内存支持I 0消耗也很大 低维或高维数据中 其空间都是O N 基于密度方法的聚类 优点能克服基于距离的算法只能发现 类圆形 的聚类的缺点 可发现任意形状的聚类 有效地处理数据集中的噪声数据 数据输入顺序不敏感缺点输入参数敏感 确定参数 MinPts困难 若选取不当 将造成聚类质量下降 由于在DBSCAN算法中 变量 MinPts是全局惟一的 当空间聚类的密度不均匀 聚类间距离相差很大时 聚类质量较差 计算密度单元的计算复杂度大 需要建立空间索引来降低计算量 且对数据维数的伸缩性较差 这类方法需要扫描整个数据库 每个数据对象都可能引起一次查询 因此当数据量大时会造成频繁的I O操作 OPTICS算法 由于在DBSCAN算法中 变量 MinPts是全局惟一的 当空间聚类的密度不均匀 聚类间距离相差很大时 聚类质量较差 许多现实的数据集内在的聚类结构不能够通过全局的密度参数来描述 数据空间中不同区域的聚类需要不同的局部密度 OPTICS算法 尽管dbscan能够根据给定的输入参数 和MinPts聚类对象 但是它把选择能产生可接受的聚类结果的参数值的责任留给了用户 这是许多其他算法都存在的问题 但是对于高维数据而言设定准确的参数非常困难 参数设置有细微的不同都可能导致差别很大的聚类结果 全局参数不能很好地刻画其内在的聚类结构 2019 12 19 33 可编辑 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一定是关于 2和MinPts簇C 的子集 这就意味着 如果两个对象在同一个基于密度的簇中 则它们也是在同一个具有较低密度要求的簇中 OPTICS算法 为了克服在聚类分析中使用一组全局参数的缺点 提出了OPTICS聚类分析方法 P为对象 数据集D 为距离值 N q 为邻域 MinPts 两个定义 P的核心距离 使得P成为核心对象的最小 是使p称为核心对象的最小半径阈值 若 N q MinPts 即P不是核心对象 核心距离则无定义 q关于对象P的可达距离 是使q从p密度可达的最小半径 p的核心距离和p q的欧几里得距离之间的较大值 p必须是核心对象且q在p的邻域内 若 N p MinPts 即P不是核心对象 则无定义否则 定义为Max 核心距离 p q OPTICS算法 例核心距离与可达距离 假设 6mm MinPts 5 P的核心距离是p于第四个最近的数据对象之间的距离 q1到p的可达距离是p的核心距离 3mm 因为它比q1到p的欧氏距离大 q2关于p的科大距离是p到q2的欧氏距离 它大于p的核心距离 OPTICS算法 OPTICS算法并不显式的产生数据及聚类 而是输出簇排序 clusterordering 这个排序是所有分析对象的线性表 并且代表数据基于密度的聚类结构 较稠密簇中的对象在簇排序中相互靠近 这个排序等价于从较广泛的参数设置中得到基于密度的聚类 这样optics不需要用户提供特定密度阈值 簇排列可以用来提取基本聚类信息 导出内在的聚类结构 也可以提供聚类的可视化 OPTICS算法 为了构造不同的类 对象需要按特定的次序处理 这个次序选择这样的对象 及关于最小的 值 它是密度可达的 以便较高密度 较低 值 的簇先完成 optics算法计算给定数据库中所有对象的排序 并且存储每个对象核心距离和相应的可达距离 optics维护一个称作orderseeds的表来来产生输出排列 orderseeds中的对象按到各自的最近核心对象的可达距离排序 及按每个对象的最小可达距离排序 OPTICS算法 寻找簇 Cluster orderoftheobjects 数据集的簇排序可以用图形描述 这有助于可视化和理解数据集中聚类结构 例如下图是一个简单的二维数据集的可达性图 OPTICS算法并不直接寻找各个簇 而是将基于密度查找簇所需要的信息记录下来 这些信息反映了数据空间基于密度的簇结构 同时从这些密度信息可以直接发现各个簇 OPTICS采取了两个方法来达到目标1 定义了对象的核心距离和可达距离 以反映对象附近的密度大小 2 在迭代查找可达对象时 对种子对象依可达距离进行排序 从而在簇扩展时优先扩展密度值较大区域的点 这样 OPTICS算法实现了数据库所有对象的排序 这一对象序列就可以反映出数据空间基于密度的簇结构信息 基于这些信息可以容易地确定合适的 值 并随之发现各个簇 另外 OPTICS还提供了自动的簇发现方法 OPTICS算法较好地解决了DBSCAN算法的对输入参数 敏感的问题 但是由于采用了复杂的处理方法以及额外的磁盘IPO操作 使得OPTICS实际运行的速度远远低于DBSCAN 不同密度 形状 大小的簇 参数的影响 减小 则可达距离为无穷大的点增多 MinPts减小 核心对象增多 图象更尖锐 基于网格的方法 Grid BasedMethods 聚类高维数据是聚类分析中一个非常重要的任务 而一般聚类方法无法处理这些数据 用户感兴趣的通常是某个高维数据空间的若干个子空间 对该空间内数据点的聚类要比原始空间更好一些 高维数据中 通常只有少数几维与某些簇相关 其他不相关的维数据可能会产生大量的噪声而屏蔽真实的簇 为聚类高维数据集便提出了基于网格的方法的聚类 基于网格的方法 Grid BasedMethods 将数据空间划分成为有限个单元 cell 的网格结构 所有的处理都是以单个单元为对象的 这种方法的主要优点是它的处理速度很快 处理时间独立于数据对象的数目 只与每一维所划分的单元数目有关代表算法有 CLIQUE算法 CLQUE是一个综合了基于密度和基于网格方法的聚类算法 对于大型数据库中的高维数据的聚类比较有效 在高维数据的子空间中识别稠密的聚类 所产生的理解结果与所给的输入数据无关 CLIQUE 高维度数据的自动子空间聚类算法 CLIQUE 聚类高维空间 CLIQUE的中心思想如下 给定一个多维数据点的大集合 数据点在数据空间中通常不是均衡分布的 CLIQUE区分空间中稀疏的和 拥挤的 区域 以发现数据集合全局分布模式 将数据空间中的每个维划分成等长且数量相等的间隔段 即单元 如果一个单元中的包含数据点超过了某个输入模型参数 则该单元是密集的 在CLIQUE中 一个聚类被定义为相连的密集单元的最大集合 问题描述 要能自动地识别一个高维数据的子空间限制在只对原始空间的子空间的搜索而不是使用一个新的维度为了识别数据点的密度 将数据空间划分并找出在每个单元中数据点的数量 聚类是子空间中相连的高密度单元的并集 即将聚类映射到轴对称的超矩形中 聚类在空间中的描述 设A A1 A2 Ad 是一个有界的 全部有序的域的集合 而S A1 A2 Ad是一个d维的数字空间 A1 A2 Ad定义为S的维 输入是由d维点集V v1 v2 vm 组成的 其中Vi Vi的第j个元素来自域Aj 将数据空间S划分成非重叠矩形单元 单元的划分方法是在每一个维上将维分割成 个等长的间隔段 是输入参数 每一个单元u是由每一个属性一个间隔段组成的交集 形式为 u1 u2 ud 其中ui li hi 是在Ai的划分中的右边界开放的间隔段 聚类在空间中的描述 一个点V 属于单元u u1 u2 ud 当对所有的ui 有li vi hi 一个单元的选择性 selectivity 单元内数据点的数量与单元的总数据点数量之比 称单元u是稠密的 若单元的选择性大于密度阈值 聚类在空间中的描述 两个k维单元u1 u2是连接的 即他们之间有一个公共面 若存在k 1维 假设是维At1 At2 Atk 1 单元u1 rt1 rt2 rtk 及u2 rt1 rt2 rtk 1 是相连的 则有rtj rtj 并且有htk ltk 或者htk ltk 若R C R 则称一个区域R包含于一个聚类C中 若没有其他R的超集包含于聚类C中 则称区域R是最大的 一个聚类的最小描述是具有最大区域的聚类的非冗余的覆盖 例子 一 在下图中 二维空间 age salary 划分成10 10格一个单元是间隔段的交集 例如单元u 30 age 35 1 salary 2 一个区域是单元的矩形的并集 A与B是两个区域 A 30 age 50 4 salary 8 B 40 age 60 2 salary 6 假设阴影部分是稠密的单元 A B是一个聚类 该聚类的最小描述为 30 age 50 4 salary 8 40 age 60 2 salary 6 例子 二 图二 原始数据空间的子空间中的聚类 在图二中 假设 20 没有2 维单元是稠密的 在原始数据空间中就没有聚类 但将数据点投影到维salary上 就有三个1维密度单元 其中两个是相连的 因此 在1维salary子空间上就有两个聚类 C 5 salary 7及D 2 salary 3 由于在age子空间中没有密度单元 故在该子空间中就没有聚类 CLIQUE算法 由以下几部分组成 1 含有聚类子空间的识别