数学建模之Clustering与聚类分析.pptVIP

基于密度聚类 (Density-Based Clustering) 主要特点: 发现任意形状的聚类 处理噪音 一遍扫描 需要密度参数作为终止条件 一些有趣的研究: DBSCAN: Ester, et al. (KDD’96) OPTICS: Ankerst, et al (SIGMOD’99). DENCLUE: Hinneburg D. Keim (KDD’98) CLIQUE: Agrawal, et al. (SIGMOD’98) * ?-邻域：给定对象半径?内的领域 核心对象 (Core object): 一个对象的?–邻域至少包含最小数目MinPts个对象 直接密度可达的(Directly density reachable, DDR): 给定对象集合D, 如果p是在q的?–邻域内, 而q是核心对象, 我们说对象p是从对象q直接密度可达的 密度可达的(density reachable): 存在 一个从p到q的DDR对象链 密度相连的(density-connected): 如果对象集合D中存在一个对象o，使得对象p和q是从o关于?和MinPts密度可达的，那么对象p和q是关于?和MinPts密度相连的 * 两个参数: Eps: 邻域的最大半径 MinPts: 在 Eps-邻域中的最少点数 NEps(p): {q belongs to D | dist(p,q) = Eps} 直接密度可达的: 点 p 关于Eps, MinPts 是从点q直接密度可达的, 如果 1) p 属于 NEps(q) 2) 核心点条件: |NEps (q)| = MinPts * p q MinPts = 5 Eps = 1 cm 密度可达: 点 p 关于Eps, MinPts 是从 q密度可达的, 如果 存在一个节点链 p1, …, pn, p1 = q, pn = p 使得 pi+1 是从pi直接密度可达的 密度相连的: 点 p关于 Eps, MinPts 与点 q是密度相连的, 如果 存在点 o 使得, p 和 q 都是关于Eps, MinPts 是从 o 密度可达的 * p q p1 p q o MinPts=3 q是从p密度可达； p不是从q密度可达（q非核心） S和r从o密度可达；o从r密度可达； r, s, o密度相连 * DBSCAN(Density Based Spatial Clustering of Applications with Noise) 一个基于密度的聚类算法 可以在带有“噪音”的空间数据库中发现任意形状的聚类 * Core Border Outlier Eps = 1cm MinPts = 5 算法 任意选取一个点 p 得到所有从p 关于 Eps 和 MinPts密度可达的点. 如果p 是一个核心点, 则找到一个聚类. 如果 p 是一个边界点, 没有从p 密度可达的点, DBSCAN 将访问数据库中的下一个点. 继续这一过程, 直到数据库中的所有点都被处理. DBSCAN的复杂度 采用空间索引, 复杂度为O(nlog n), 否则为O(n2) DBSCAN的缺点: 对用户定义的参数是敏感的, 参数难以确定(特别是对于高维数据), 设置的细微不同可能导致差别很大的聚类. （数据倾斜分布）全局密度参数不能刻画内在的聚类结构 * 聚类高维数据，应用广泛: text documents, DNA micro-array data；重要挑战: 多个不相关的维度掩盖聚类 距离函数变得没有意义—由于 equi-distance(高维空间，数据变稀疏) 聚类可能存在于某些子空间中 特征变换: 仅当大部分维度与聚类相关时有效 PCA SVD有效，当特征高度相关/冗余 特征选择: 缠绕wrapper 或 过滤方法 当数据有很好的聚类结构时，很有效 子空间聚类: 在所有可能的子空间中寻找clusters CLIQUE, ProClus, and frequent pattern-based clustering * 一维的数据相对压缩的 增加一个维度将沿此维“伸展” 数据点, 使得数据更分散 增加更多的维度将使得数据更稀疏—高维数据非常稀疏 距离变得没有意义—due to equi-distance * (graphs adapted from Parsons et al. KDD Explorations 2004) 聚类可能只存在于某些子空间 子空间聚类: find clusters in all the subspaces * * * * * * * * * * * * 全局最优: 穷举所有可能的划分 启发式方法: k-平均值(k- means)和 k-中心点