数据挖掘聚类分析PPT课件.ppt

数据挖掘 聚类分析 乐承毅 华东交通大学经济管理学院 1 内容 聚类的基本定义聚类方法的类型分裂方法分层方法基于密度的方法基于网格的方法基于模型的方法高维数据的聚类聚类评估Outlier分析总结 2 什么是聚类分析 聚类 数据对象集合同一组内数据间相似 或相关 不同组的数据间不相似 或不相关 聚类分析通过数据的特征找出数据间的相似性 并将相似数据对象形成聚类是一种无监督学习 无预先定义好的类 类内距离最小 3 聚类分析的应用 作为分析数据分布的独立工具将相似文档组合在一起用于浏览 将有相同功能的基因和蛋白质组合在一起 将价格波动相似的股票组合在一起作为其它算法的预处理减少数据量 澳大利亚降雨量聚类 4 什么不是聚类 有监督分类有类标号信息简单划分将学生按姓字母分成不同的组查询的结果外部说明组合成结果 5 聚类结果有多义性 6 什么是好的聚类 类内距离小 类间距离大聚类的质量取决于应用的相似性度量以及算法的实现聚类的质量同样体现在聚类方法能否发现隐藏的模式不相似度 相似度相似度表达为距离函数 典型的度量为 d i j 不同类型变量 其距离函数也不同基于应用和数据的语义 数据中不同变量应赋以不同的权系数聚类的质量有独立的 质量 函数度量聚类的 好坏 很难定义 足够相似 或 足够好 答案比较主观 7 不同类型数据的距离 数值型 Minkowski距离特殊情况 Euclidean L2 norm Manhattan L1 norm 二值型 Jaccard系数名词型 不匹配数顺序型 和数值型对待比例尺变量 现作Log变换矢量型 cosine测度混合型 权重混合 8 相似度的计算方法 连续型属性的相似度计算方法二值离散型属性的相似度计算方法多值离散型属性的相似度计算方法混合类型属性的相似度计算方法 9 1 连续型属性的相似度计算方法 欧氏距离 Euclideandistance 曼哈顿距离 Manhattandistance 明考斯基距离 Minkowskidistance 10 2 二值离散型属性的相似度计算方法 二元变量 binaryvariable 只有两个状态0或1 0表示该变量为空 1表示该变量存在例如 描述病人的变量smoker 1表示病人抽烟 而0表示病人不抽烟 对象i 对象j 11 2 二值离散型属性的相似度计算方法 对称的 二元变量的两个状态具有同等价值 并具有相同的权重例 性别是对称的二元变量对称的二元变量的相异度计算 简单匹配系数相似度 12 不对称的 二元变量的两个状态的输出不是同样重要例 疾病检查结果的肯定和否定 根据惯例 比较重要的输出结果是出现几率较小的例 HIV阳性是比较重要的结果 出现几率较小 而HIV阴性 正常情况 出现几率较大通常 比较重要的输出结果编码为1 另一种结果编码为0对于非对称的相似度 负匹配数目t被忽略 采用Jaccard系数 2 二值离散型属性的相似度计算方法 13 二元变量之间的相异度 例gender是对称的其余都不是对称的Y和P的值设置为1 而N的值设置为0 14 3 多值离散型属性的相似度计算方法 多值离散属性是二元变量的拓广 它可以取多于两种状态值 如 red yellow blue green方法1 简单匹配m 状态取值匹配的变量数目 p 变量总数方法2 可以用非对称的二元变量对标称变量编码 使用大量二元变量 对M个标称状态的每一个 创建一个新的二元变量 对于一个有特定状态值的对象 对应状态值的二元变量值置1 其余二元变量的值置0 15 4 混合类型属性的相似度计算方法 数据库可能包含所有六种类型对称的二元变量 不对称的二元变量 标称的 序数的 区间的 比例标度的如何计算混合类型变量描述的对象的相异度 方法1 将变量按类型分组 对每种类型的变量单独进行聚类分析如果这些分析得到兼容的结果 这种方法是可行的在实际的应用中 这种方法行不通方法2 将所有的变量一起处理 只进行一次聚类分析 将不同类型的变量组合在单个相异度矩阵中 把所有变量转换到共同的值域区间 0 0 1 0 上 16 5 向量对象 向量x和y 如两篇文章中词频出现的次数 余弦度量Tanimoto系数 17 数据挖掘对聚类分析的要求 可伸缩性处理不同属性类型的能力处理动态数据的能力发现任意聚类形状的能力输入参数对领域知识的弱依赖性能处理噪声和异常数据对输入数据的顺序不敏感处理高维数据的能力增加用户指定约束的能力结果的可解释性和可用性 18 内容 聚类的基本定义聚类方法的类型分裂方法分层方法基于密度的方法基于网格的方法基于模型的方法高维数据的聚类聚类评估Outlier分析总结 19 分裂方法 根据某种准则 如最小均方误差 将数据集分裂成互不重叠的若干组 且每组至少包含一个数据 典型方法 k means k medoids CLARANS 分裂聚类 20 分层方法 将数据集进行分层分解 聚类组织成分层树典型方法 Diana Agnes BIRCH ROCK CAMELEON 传统的分层聚类 非传统分层聚类 非传统的分层图 传统的分层图 21 基于密度的方法 基于密度函数和连接性 只要区域中的某个点的密度大过某个阈值 将其加到与之相近的聚类中当数据不规则 存在噪声或野值点时应用典型方法 DBSACN OPTICS DenClue 基于密度的6个聚类 22 其它方法 基于格网的方法基于多级粒度结构 将数据空间划分成有限个单元的格网结构典型方法 STING WaveCluster CLIQUE基于模型的方法 对每个聚类假设一个模型 对每个找出最佳的模型拟合典型方法 EM SOM COBWEB基于频繁模式的方法基于频繁模式的分析典型方法 p Cluster用户引导或基于约束的方法 考虑用户或应用指定的约束进行聚类典型方法 COD obstacles constrainedclustering基于连接的聚类 数据对象间以不同方式连接大规模连接可用于聚类 SimRank LinkClus 23 聚类的特征 质心 聚类的中心点半径 聚类内点到质心距离的均方根直径 据类所有点对间的距离的均方根 24 聚类间的距离 单连接 不同聚类元素间的最小距离 i e dist Ki Kj min tip tjq 全连接 不同聚类元素间的最大距离 i e dist Ki Kj max tip tjq 类平均 不同聚类元素间的平均距离 i e dist Ki Kj avg tip tjq 质心 两聚类质心间的距离 i e dist Ki Kj dist Ci Cj Medoid 两个聚类代表元素间的距离 i e dist Ki Kj dist Mi Mj Medoid 聚类内代表该聚类的元素 25 内容 聚类的基本定义聚类方法的类型分裂方法分层方法基于密度的方法基于网格的方法基于模型的方法高维数据的聚类聚类评估Outlier分析总结 26 分裂算法 将有n个对象的数据集D分裂成k个聚类 满足一定的约束条件 如最小均方距离 给定参数k 在分裂准则最优情况下 寻找k个聚类全局最优 遍历所有的分裂启发式方法 k means和k medoidsk means MacQueen 67 每个聚类由聚类中心表示k medoids或PAM Partitionaroundmedoids Kaufman Rousseeuw 87 每个聚类由其中的某个对象表示 27 K Means算法 给定k k means包括四个步骤 将数据集分裂成k个非空子集计算当前聚类的质心 质心为聚类的中心 将每个数据分配至和质心距离最短的聚类返回步骤2 直至所有的数据均不重新分配 K 2任意选取k个数据作为质心 分配至最相似的聚类 更新聚类质心 更新聚类质心 重分配 重分配 28 k 均值方法 随机地 选择 个初始聚类中心 29 k 均值方法 每一个点被安排到离某中心最近的那个聚类 30 k 均值方法 把每一个聚类中心移动到每一个聚类的均值上 31 k 均值方法 重新把这些点安排到中心最近的聚类问题 哪些点的聚类变了 32 k 均值方法 答 这 个点聚类变了 33 k 均值方法 重新计算聚类均值 34 k 均值方法 把聚类中心移到这些均值上 35 步骤 36 K Means算法特点 收敛性在欧式距离 余弦夹角和相关性等度量下 可在初始几个循环收敛 收敛条件通常修改为 很少发生改变 局部最优 如果到全局最优 需用模拟退火或遗传算法复杂度为O n K I d n 数据点数 K 聚类数 I 迭代次数 d 属性个数缺点定义均值 对分类属性不适用需预先定义k类聚类不能处理噪声或野值点不能发现非凸的数据集 37 K means算法的变化 k means在以下几方面变化初始k均值的选取相异度计算计算聚类均值的策略处理分类数据 k modes Huang 98 以众数代替聚类均值对分类数据使用新的距离度量基于频率的方法更新聚类众数 38 案例 39 1 初始化重心值 40 2 计算各点到重心的距离矩阵 41 3 根据距离分组 并重新计算重心 42 4 计算各点到重心的距离矩阵 43 5 根据距离分组 并重新计算重心 44 6 再次重复以上的步骤 45 K medoids算法 k means对离群点敏感很大的极端值可能扭曲数据的分布K Medoids 不是选取聚类的均值作为参考点 而是选取medoids为最靠近聚类中心的数据作为参考点 46 K medoids典型算法 PAM PartitioningAroundMedoids 1987 从初始中心点开始 若非中心点改善了聚类的总距离 则非中心点取代中心点对小数据集 PAM有效CLARA Kaufmann Rousseeuw 1990 CLARANS Ng Han 1994 随机采样 47 K medoids算法 例 TotalCost 20 0 1 2 3 4 5 6 7 8 9 10 0 1 2 3 4 5 6 7 8 9 10 K 2 任意选k个数据作初始中心点 将剩余的点针对中心点聚类 随机选取非中心点 Oramdom 计算总的交换代价 TotalCost 26 若聚类质量改善 交换O和Oramdom 循环直到无改变 48 PAM PartitioningAroundMedoids 1987 使用真实数据代表聚类任意选取k个代表对象对每个非代表数据h和选取的对象i 计算总的交换代价TCih对每对数据i和h IfTCih 0 以h取代i将每个非代表数据分配至最相似的代表对象重复步骤2和3 直到无改变 49 PAMClustering 寻找最佳的聚类中心 重新分配给Oi2 重新分配给Orandom3 不发生变化4 重新分配给Orandom 数据对象 簇中心替代前替代后图k 中心点聚类代价函数的四种情况 Orandom Oi Oj p Orandom Oi Oj p Orandom Oi Oj p Orandom Oi Oj p 50 PAMClustering 寻找最佳的聚类中心 为了判定一个非代表对象Orandom是否是当前一个代表对象Oj的好的替代 对于每一个非代表对象p 考虑下面的四种情况 第一种情况 p当前隶属于代表对象Oj 如果Oj被Orandom所代替 且p离Oi最近 i j 那么p被重新分配给Oi第二种情况 p当前隶属于代表对象Oj 如果Oj被Orandom代替 且p离Orandom最近 那么p被重新分配给Orandom第三种情况 p当前隶属于Oi i j 如果Oj被Orandom代替 而p仍然离Oi最近 那么对象的隶属不发生变化第四种情况 p当前隶属于Oi i j 如果Oj被Orandom代替 且p离Orandom最近 那么p被重新分配给Orandom 51 PAM的问题 在有噪声和野值情况下 PAM比k Means更鲁棒中心点代表不受噪声和野值的影响PAM小数据集性能好 但不适用于大数据集每次循环的复杂度O k n k 2 n 数据个数 k 聚类个数基于采样的方法CLARA ClusteringLARgeApplications 52 CLARA ClusteringLargeApplications 1990 CLARA KaufmannandRousseeuwin1990 建立在统计分析包上 如SPlus从数据集中抽取多个样本 对每个样本应用PAM 返回最好的聚类结果作为输出处理能力 比PAM处理更大的数据集缺点 样本大小影响效率如果样本是有偏的 基于抽样的好的聚类不一定代表整个数据集的好的聚类 53 CLARANS Randomized CLARA 1994 CLARANS AClusteringAlgorithmbasedonRandomizedSearch NgandHan 94 每一步动态抽取近邻样本聚类过程可看作搜索一个图 图中的每个节点是一个潜在的解 kmedoids集合 若找到局部最优 重新随机选取新的节点 搜索新的局部最优优点 比PAM和CLARA更有效并具有可伸缩性 54 内容 聚类的基本定义聚类方法的类型分裂方法分层方法基于密度的方法基于网格的方法基于模型的方法高维数据的聚类聚类评估Outlier分析总结 55 分层方法 层次的聚类方法将数据对象组成一棵聚类的树根据层次分解是自底向上 还是自顶向下形成 层次的聚类方法可以进一步分为凝聚的 agglomerative 和分裂的 divisive 层次聚类纯粹的层次聚类方法的聚类质量受限于如下特点 一旦一个合并或分裂被执行 就不能修正最近的研究集中于凝聚层次聚类和迭代重定位方法的集成使用距离矩阵作为聚类标准 该方法不需要输入聚类数目k 但需要终止条件 56 57 常用的距离度量方法 四个广泛采用的簇间距离度量方法最小距离 dmin Ci Cj minp Ci p Cj p p 最大距离 dmax Ci Cj maxp Ci p Cj p p 平均值的距离 dmean Ci Cj mi mj 平均距离 davg Ci Cj p Ci p Cj p p ninj其中 p p 是两个对象p和p 之间的距离mi是簇Ci的平均值 ni是簇Ci中对象的数目 距离度量的聚类 采用最小距离dmin Ci Cj 来衡量簇间的距离时 称它为最近邻聚类算法 KNN Nearest neighborclusteringalgorithms 当最近两个簇之间的距离超过用户给定的阈值聚类就终止 使用最小距离的凝聚层次聚类算法也称为最小生成树算法 采用最大距离dmax Ci Cj 来衡量簇间的距离时 称它为最远邻聚类算法 KFN Farthest neighborclusteringalgorithms 当最近两个簇之间的最大距离超过用户给定的阈值聚类就终止 使用均值距离和平均距离是两种折中办法 可以克服离群点敏感性问题 58 分层聚类 距离矩阵作为准则 无需以聚类数k作为输入 但需有中止条件Agglomerative 聚合 所有的单个点作为初始聚类每一步 将最接近的聚类融合 直到只有一个聚类 或k个聚类 Divisive 分裂 所有数据点作为一个聚类每一步 将聚类分裂到每个聚类只有一个点 或有k个聚类 59 AGNES AgglomerativeNesting 基本算法 最常用的算法 计算近邻矩阵每个数据点均为一个聚类Repeat融合两个最近的聚类更新近邻矩阵Until只有一个聚类 60 操作步骤特点 类的个数不需事先定好需确定距离矩阵运算量要大 适用于处理小样本数据 61 Dendrogram 显示聚类的融合过程 将数据集分裂成嵌套式树形结构 聚类树 称为树状图 将树状图在理想的层级切开 得到数据的聚类 相连的分量形成聚类 62 例 初始情况 单个点作为聚类和近邻矩阵 ProximityMatrix 63 例 中间过程 多个融合步后 形成多个聚类 C1 C4 C2 C5 C3 ProximityMatrix 64 例 中间过程 融合两个最接近的聚类 C2和C5 并更新邻近矩阵 C1 C4 C2 C5 C3 ProximityMatrix 65 例 融合后 问题是怎样更新邻近矩阵 C1 C4 C2UC5 C3 C2UC5 C1 C1 C3 C4 C2UC5 C3 C4 ProximityMatrix 66 案例 67 1 计算距离矩阵 68 2 合并最近的两个cluster 69 3 重新计算距离矩阵 70 71 4 合并最近的两个cluster 72 5 重新计算距离矩阵 73 6 重复计算 74 7 得到图形 75 DIANA DivisiveAnalysis 聚合算法的逆序最终每个数据点形成一个聚类 76 分层聚类算法的扩展 聚合聚类算法的缺点伸缩性差 时间复杂度至少为O n2 n为数据个数不能回溯取消之前的聚合中间结果分层和基于距离的聚类集成BIRCH 1996 使用CF 树 并渐进地调整子聚类的质量ROCK 1999 通过近邻和连接关系对分类数据聚类CHAMELEON 1999 使用动态模型分层聚类 77 BIRCH 利用层次方法的平衡迭代简化和聚类 Birch BalancedIterativeReducingandClusteringusingHierarchies渐次地构造CF树 聚类特征树 多阶段聚类的分层结构阶段1 扫描数据库 建立一棵存放于内存的初始CF树 它可视作数据的多层压缩 试图保留数据的内在聚类结构阶段2 使用某个聚类算法对CF树的叶节点聚类 把稀疏的聚类当作野值点删除而把稠密的聚类合并为更大的聚类线性尺度 寻找单次扫描数据库的聚类算法 以少数几次扫描数据库改善质量缺点 只能处理数值型数据 对数据的输入顺序敏感 78 BIRCH中的聚类特征矢量 聚类特征 CF CF N LS SS N 数据点数量LS N个点的线性和 SS N个点的平方和 CF 5 16 30 54 190 3 4 2 6 4 5 4 7 3 8 79 BIRCH中的CF树 聚类特征 给定子聚类的统计特征 子聚类的0 1 2阶矩记录聚类或存储所需的关键测量信息CF树是高度平衡树 储存了分层聚类的聚类特征非叶节点有后代或 孩子 节点非叶节点保存了后代节点的CF和CF树有两个参数平横因子 B 孩子的最大数量门限 L 叶子节点的中的子聚类最大直径 80 CF树结构 CF1 child1 CF3 child3 CF2 child2 CF5 child5 CF1 CF2 CF6 prev next CF1 CF2 CF4 prev next B 7L 6 Root 非叶节点 叶节点 叶节点 81 BIRCH算法 聚类直径每个输入点搜索最近的叶子节点将该点加入到该叶子节点处 更新CF树若节点直径 max diameter分裂叶子节点及其父节点算法复杂度为O n 问题对数据点的插入顺序敏感固定叶子结点数 聚类的结果不是用户所考虑的自然聚类倾向于形成圆形的聚类 使用直径 82 ROCK 分类属性数据的层次聚类算法 ROCK RObustClusteringusinglinKsS Guha R Rastogi K Shim ICDE 99主要思想使用连接度量相似性 邻近性不是基于距离的算法 基于抽样的聚类抽取随机样本以连接聚类标识数据某些应用很有效国会选举 蘑菇数据集 83 ROCK中的相似性度量 传统的度量分类属性数据效果不好 e g Jaccard系数例 两组事务C1 a b c a b d a b e a c d a c e a d e b c d b c e b d e c d e C2 a b f a b g a f g b f g Jaccard系数导致错误的聚类结果C1 0 2 a b c b d e to0 5 a b c a b d C1 C2 couldbeashighas0 5 a b c a b f 基于Jaccard系数的相似性函数 Ex LetT1 a b c T2 c d e 84 ROCK中的连接度量 聚类C1 a b c a b d a b e a c d a c e a d e b c d b c e b d e c d e C2 a b f a b g a f g b f g 近邻两个事务如果满足以下条件 则为近邻sim T1 T2 threshold令T1 a b c T2 c d e T3 a b f T1 a b d a b e a c d a c e b c d b c e a b f a b g T2 a c d a c e a d e b c e b d e b c d T3 a b c a b d a b e a b g a f g b f g 连接相似性两个事务的连接相似性为共有近邻的个数link T1 T2 4 有四个共有的近邻 a c d a c e b c d b c e link T1 T3 3 有三个共有的近邻 a b d a b e a b g 85 ROCK算法 方法计算相似度矩阵使用连接相似性运行聚合分层聚类算法当数据集很大对事务抽样对抽样数据聚类问题 必须保证聚类是互连的聚类内的任意两个事务有良好的互连性忽略了两个聚类的邻近性两个独立的聚类可能也是互连的 86 CHAMELEON 利用动态建模的层次聚类算法 基于动态模型度量相似性若两个聚类的互连性很高且靠得又很近 则融合此两聚类CURE 以多个代表对象聚类 忽略了对象间得互连性 Rock忽略了聚类得邻近度信息两阶段算法图划分算法 将对象聚成多个相对较小的聚类聚合分层聚类算法 循环混合子聚类找出真正的聚类 87 CHAMELEON算法过程 构造 K NN 稀疏图 图划分 融合划分 最终聚类 数据集 K NNGraph若q为p的k个最近邻之一 则p q相连 相对互连度 c1 c2的互连度相对内部连接度的规范化相对邻近度 c1 c2的邻近度相对内部邻近度的规范化 88 CHAMELEON 对复杂对象聚类 89 内容 聚类的基本定义聚类方法的类型分裂方法分层方法基于密度的方法基于网格的方法基于模型的方法高维数据的聚类聚类评估Outlier分析总结 90 基于密度的方法 基于密度聚类 局部聚类准则 如密度连接点主要特征 发现任意形状的聚类处理噪声一次扫描数据库需要密度参数作为中止条件几个算法 DBSCAN Ester etal KDD 96 OPTICS Ankerst etal SIGMOD 99 DENCLUE Hinneburg D Keim KDD 98 CLIQUE Agrawal etal SIGMOD 98 moregrid based 91 基于密度的算法 基本概念 两个参数 Eps 邻域的最大半径MinPts 以o为中心 以Eps为半径的空间 某点EPS邻域内 最少的数据点数P点邻域NEps p q属于D dist p q MinPts 92 密度可达和密度相连 Density reachable 密度可达 若存在数据点链p1 pn p1 q pn p使pi 1为从pi直接密度可达 则称点p是从点q关于Eps MinPts密度可达的Density connected 密度相连 若存在点o 点p和点q均是从点o关于Eps和MinPts密度可达的 则称点p和q是关于Eps MinPtsi密度相连的 p q p1 93 DBSCAN DensityBasedSpatialClusteringofApplicationswithNoise依赖聚类基于密度的概念 聚类定义为密度相连的点的最大集合在有噪声的空间数据库中 发现任意形状的聚类 94 DBSCAN算法 算法任意选择点p从p出发 得到所有关于Eps和MinPts密度可达的点若p为核心点 则得到聚类若p为边界点 若p无密度可达点 则DBSCAN访问数据库的下一点重复以上过程 直到所有点均访问到复杂度O n2 使用空间索引O nlogn 95 DBSCAN 对参数敏感 96 OPTICS ACluster OrderingMethod 1999 OPTICS OrderingPointsToIdentifytheClusteringStructure产生一个基于密度的聚类结构排序聚类排序包含的信息等价于从一个广泛的参数设置获得的基于密度的聚类可用于自动或交互的聚类分析 包括发现内在的聚类结构可用图形化方式可视化显示 97 OPTICS 对DBSCAN的扩展 同时处理一组距离参数核心距离D点p成为核心点的最小距离Epsq到p的可达距离rp和q之间的欧式距离和p的核心距离的大值Max core distance p d q p 每个点 对象 存储了核心距离和可达距离 D MinPts 5Eps 3cm o p1 p2 r p1 o 3cm r p2 o 4cm 98 数据集的聚类排序 可达距离 对象 点 聚类顺序 无定义 99 DENCLUE 基于统计密度函数主要特点坚实的数学基础适合于有大量的噪声数据对高维数据集 可对任意形状的聚类形成紧致的数学描述比已有算法块 e g DBSCAN 但需大量的参数 y在x上的影响 X总的影响 x在xi方向的梯度 100 DENCLUE 基本思想 数据点对邻域的影响 以影响函数描述数据空间的整体密度用所有数据点的影响函数和建模通过识别密度吸引点确定聚类密度吸引点 全局密度函数的局部极大值点中心定义聚类 给每个密度吸引点赋以其吸引点的密度任意形状聚类 融合沿高密度路径相连的密度吸引点 101 中心定义和任意形状的聚类 102 内容 聚类的基本定义聚类方法的类型分裂方法分层方法基于密度的方法基于格网的方法基于模型的方法高维数据的聚类聚类评估Outlier分析总结 103 基于格网的聚类方法 使用多分辨率格网结构几种方法STING aSTatisticalINformationGridapproach byWang YangandMuntz 1997 WaveClusterbySheikholeslami Chatterjee andZhang VLDB 98 使用小波变换的多分辨率方法CLIQUE Agrawal etal SIGMOD 98 处理高维数据 在高维数据聚类讲述 104 STING方法 AStatisticalInformationGridApproach空间区域划分成矩形单元对多级分辨率对应有多级单元 105 STING聚类算法 每个高层单元划分为多个低层单元预先计算每个格网单元属性的统计信息 用于查询高层单元的统计参数可从低层单元统计参数计算得到count mean stdev min max分布类型 正态 均匀等 使用自顶向下的方法回答查询从预先选定的层开始 通常单元数目较少对当前层的每个单元计算其置信区间删除不相关的单元处理完当前层后 继续处理下一低层的单元重复以上过程 直到最低层 106 STING算法分析 优点 独立于查询 容易并行化 递增更新效率高 复杂度为O K K为最低层的单元数缺点 所有的边界要么是垂直的 要么水平的 无斜的边界 107 WaveCluster ClusteringbyWaveletAnalysis对特征空间进行小波变换如何应用小波变换查找聚类在数据空间施加多维网格 缩减数据多维空间数据对象由n维特征空间表示在每个特征空间施加小波变换 找出特征空间的稠密区多级小波变换将形成从粗到精的多个尺度 108 WaveCluster算法 输入参数每个维度上的格网单元数小波变换及其分解级数小波变换有利于聚类 使用帽形滤波器加强点聚类区域 同时抑制边界区域的弱信息有效去除野值点 具有多分辨率特性 代价较小主要特点 复杂度O N 在不同尺度发现任何形状的聚类对噪声和输入顺序不敏感适应于低维数据既是基于格网也是基于密度的 109 小波变换实例 首先将数据量化到格网空间 然后作小波变换a 尺度1 highresolutionb 尺度2 mediumresolutionc 尺度3 lowresolution 110 内容 聚类的基本定义聚类方法的类型分裂方法分层方法基于密度的方法基于格网的方法基于模型的方法高维数据的聚类Outlier分析总结 111 基于模型的方法 什么是基于模型的聚类 在给定数据和数学模型间作最优拟合假设 数据是多个概率分布的混合典型方法统计方法EM Expectationmaximization AutoClass及其学习方法COBWEB CLASSIT神经网络方法SOM Self OrganizingFeatureMap 112 EM法 ExpectationMaximization EM 流行的迭代求精算法k means的扩展每个对象赋以分配到聚类的权系数 概率 基于权系数 计算均值基本思想给出参数向量的初始估计根据参数向量产生的混合密度对每个对象重新打分重新打分后的对象又用来更新参数如果对象得分属于同一分量 则属于同一聚类算法很快收敛 但不是全局最优 113 EM算法 初始猜测 随机选取k个聚类中心基于两步反复求精参数期望步 用以下概率将Xi赋给聚类Ci最大化步 估计模型的参数 114 概念聚类 概念聚类一种机器学习聚类方法给定一组位标记的对象 产生对象的分类模式找出每组对象的特征描述 class COBWEB Fisher 87 一种流行的 简单的 增量概念聚类方法以分类树的形式创建层次聚类每个节点代表一个概念 包含该概念的概率描述 汇总分类在该节点下的对象 115 COBWEB聚类方法 分类树 116 神经网络方法 神经网络方法将每个聚类表达为一个标本 作为聚类的 原型 根据距离度量 新的对象可分布到其标本最相似的聚类典型方法SOM Soft OrganizingfeatureMap 竞争学习包括多个单元的分层结构对正在处理的对象 神经元以 胜者第一 的方式竞争 117 自组织特征映射 SOMs 又称拓扑有序映射 orKohonenSelf OrganizingFeatureMap KSOMs 用低维 2维或3维 目标空间的点来表示高维源空间中的所有点 尽可能保持点之间的距离和邻近关系和k means相似 聚类的中心往往处于特征或属性空间的一个低维流形中聚类通过若干单元竞争当前对象来进行权重向量最接近当前对象的单元为赢家调整获胜单元及其最近邻的权重SOMs被认为和大脑的处理过程类似 118 SOM用于web文档聚类 图左 对12088网络文档聚类结果图右 关键词 mining 下钻挖掘的结果 119 内容 聚类的基本定义聚类方法的类型分裂方法分层方法基于密度的方法基于格网的方法基于模型的方法高维数据的聚类聚类评估Outlier分析总结 120 高维数据的聚类 高维数据的聚类广泛的应用 文本文档 DNA结构数据主要的挑战 许多步相关的维度隐藏了聚类距离变得没有意义 数据稀疏时 不同维的数据点距离相同聚类只存在子空间方法特征变换 大多数维度相关时才有效当特征高度相关或冗余时 PCA SVD有效特征选择 在寻找存在好的聚类的子空间时有用子空间聚类 在所有的子空间内聚类CLIQUE ProClus和基于频繁模式的聚类 121 维数灾难 在一个维度上的数据集显得比较拥挤通过增加一个维度 拉伸数据 使其进一步分离增加更多的维度将进一步分离数据 高维数据更加稀疏此时距离无意义 稀疏后的数据点距离相同 122 子空间聚类 聚类只存在某些子空间内子空间聚类 在所有的子空间搜索聚类 123 CLIQUE ClusteringInQUEst 自动识别高维数据的子空间 比原始空间更好地聚类CLIQUE可认为是基于格网和基于密度的在每个维度将数据化分成相同数量的等分区间将m维数据空间划分成互不重叠的矩形单元若单元内的数据占总数据量的比例超过输入模型参数 则认为其是稠密的子空间内最大的连通稠密单元为一个聚类 124 主要步骤 划分数据空间 找出位于分割单元内数据点的数量按Apriori原则识别处包含聚类的子空间识别聚类确定所有感兴趣子空间的稠密单元确定所有感兴趣子空间的连通稠密单元为聚类生成一个最小描述为每个聚类确定覆盖连通稠密单元聚类的最大区域为每个聚类确定一个最小覆盖 125 Salary 10 000 20 30 40 50 60 age 5 4 3 1 2 6 7 0 3 126 CLIQUE的优缺点 优点自动找出高维子空间 这些空间存在高密度聚类对输入数据的顺序不敏感 不需假定规范的分布和输入的大小成线性伸缩 随着数据的维度增加 有很好的伸缩性缺点方法的简化降低了聚类的精度 127 内容 聚类的基本定义聚类方法的类型分裂方法分层方法基于密度的方法基于格网的方法基于模型的方法高维数据的聚类聚类评估Outlier分析总结 128 聚类评估 聚类评估估计在数据集上进行聚类的可行性和被聚类方法产生的结果的质量聚类评估的任务估计聚类趋势 评估数据集是否存在非随机结构 仅当数据中存在非随机结构时 聚类分析才有意义 确定数据集中的簇数 在聚类之前 估计簇数测定聚类质量 聚类之后 评估结果簇的质量 129 估计聚类趋势 例 一个在数据空间均匀分布的数据集 130 估计聚类趋势 利用霍普金斯统计量 HopkinsStatistic 测试空间随机性 131 确定数据集中的簇数 实验方法对于n个点的数据集 簇数 n 2 每个簇约有 2n个点肘方法 Elbowmethod 给定k 0 使用某种聚类算法对数据集聚类 并计算簇内方差和var k 绘制var关于k的曲线 曲线的第一个 或最显著的 拐点暗示 正确的 簇数交叉验证方法将数据集分为m个部分用m 1个部分建立一个聚类模型 用剩余部分检验聚类的质量对测试集中的每个点 找出最近的质心 用测试集中所有点与它们的最近质心之间的距离的平方和来度量聚类模型拟合测试集的程度对任意k 0 重复上述步骤m次 对于不同的k值 比较总体质量度量 选取最佳拟合数据的簇数 132 测定聚类质量 两种方法外在方法 supervised i e 有基准可用用某种聚类质量度量对聚类结果和基准进行比较例 BCubed精度和召回率内在方法 unsupervised i e 无基准可用通过考察簇的分离情况和簇的紧凑情况来评估聚类例 轮廓系数 133 测定聚类质量 外在方法 Bcubed精度和召回率设D o1 on 是对象的集合 C是D中的一个聚类 设L oi 1 i n 是基准确定的oi的类别 C oi 是C中oi的类别 两个对象oi和oj之间在聚类C中的关系的正确性为 134 134 测定聚类质量 外在方法 精度和召回率一个对象的精度是指同一个簇中有多少个其他对象与该对象同属一个类别一个对象的召回率反映有多少个同一类别的对象被分配到在相同的簇中Bcubed精度 Bcubed召回率 135 测定聚类质量 内在方法 轮廓系数 对象o的轮廓系数定义为a o 是对象o与o所属的簇的其他对象之间的平均距离 b o 是o到不属于o的所有簇的最小平均距离a o 反映o所属的簇的紧凑性 该值越小 簇越紧密b o 反映o与其他簇的分离程度 该值越大 o与其他簇越分离 136 136 测定聚类质量 内在方法 轮廓系数轮廓系数的取值为 1 1 当o的轮廓系数值接近1时 包含o的簇是紧凑的 并且远离其他簇 当o的轮廓系数值为负时 意味着在期望情况下 o距离其他簇的对象比距离与自己同在簇的对象更近聚类质量度量 采用数据集中所有对象的轮廓系数的平均值 137 内容 聚类的基本定义聚类方法的类型分裂方法分层方法基于密度的方法基于格网的方法基于模型的方法高维数据的聚类聚类评估Outlier分析总结 138 什么是Outlier 离群点 野值点 孤立点 分析 什么是outliers 数据集和其余的数据有着显著的不同对象的集合 它们与数据的其它部分不一致例子 Sports MichaelJordon TigerWoods 孤立点可能是度量或执行错误所导致的孤立点也可能是固有的数据变异性的结果离群点的来源数据来源于异类 如欺诈 入侵 不寻常的实验结果等数据变量固有变化引起 如顾客的新的购买模式 基因突变等数据测量和收集误差 139 离群点分析 问题 在大数据集中定义并查找出outliers离群点检测中的困难1 在时间序列样本中发现离群点一般比较困难 因为这些离群点可能会隐藏在趋势 季节性或者其他变化中 2 对于维度为非数值型的样本 在检测过程中需要多加考虑 比如对维度进行预处理等 3 针对多维数据 离群点的异常特征可能是多维度的组合 而不是单一维度就能体现的 140 离群点检测的应用 应用 信用卡欺诈检测电信欺诈检测顾客分割 确定极低或极高收入的客户的消费行为医疗分析 发现对多种治疗方式的不寻常的反应 入侵检测 欺诈检测 医疗 公共卫生 生态系统 141 四种常见的离群点检测方法 142 基于统计的离群点检测 离群点的概率定义 离群点是一个对象 关于数据的概率分布模型 它具有低概率 基于统计的离群点检测的思路 143 基于统计的离群点检测 不和谐检验的两个过程 工作假设 备择假设如果某个样本点不符合工作假设 那么我们认为它是离群点 如果它符合备选假设 我们认为它是符合某一备选假设分布的离群点 实例 例如我们设儿童上学的具体年龄总体服从正态分布 所给的数据集是某地区随机选取的开始上学的20名儿童的年龄具体的年龄特征如下 年龄 6 7 6 8 9 10 8 11 7 9 12 7 11 8 13 7 8 14 9 12 那么 相应的统计参数是 均值 9 1 标准差 2 3 如果选择数据分布的阈值为 阈值 均值 2 标准差故在 4 5 13 7 区间以外的数据都是潜在的离群点 将最大值取整为13 所以年龄为14的孩子可能是个例外 而且由均值可知 此地的孩子普遍上学较晚 教育部门以后可据此作一些政策上的改进 144 基于统计的离群点检测 基于统计的离群点检测的优缺点 145 基于距离的离群点检测 基于距离的outlier 若数据集T中至少有p部分对象与对象O的距离大于D 则称O为DB p D outlier挖掘基于距离的outlier算法 Knorr Ng VLDB 98 基于索引的算法嵌套循环算法基于单元的算法 146 基于距离和 distancesum based DS 检测算法 与DB p d 孤立点一样 DS孤立点挖掘算法使用同样的距离公式 如绝对距离或欧式距离 但不根据p和d来判定孤立点 而是先计算数据对象两两之间的距离 再计算每个对象与其他对象的距离之和 设M为用户期望的孤立点个数 则距离之和最大的前M个对象即为要挖掘的孤立点 这样可消除用户设置参数p和d的需要 基于距离的离群点检测 147 案例 孤立点挖掘在高等学校科技统计数据分析中的应用孤立点实验数据源 选自全国普通高等学校科技统计数据上报基表中的数据 甘肃省2010年科技统计上报数据中的一所高校数据 基于距离的离群点检测 148 对基表中的数据 如选取科技人员职称和学历作为最终测试对象 因职称只有院士 正高 副高 讲师 助教和其它职称共六种职称 而学历只有高中以下 中专 大专 本科 硕士和博士共六种职称 职称和学历跨度小 检测出来的孤立点孤立程度相对较低 故选取跨度较大的出生年月作为测试对象 选取三个指标 出生年月 学位和职称作为检测属性 实验及结果分析用DS算法时 取M 20 算法返回距离的值最大的20个教师信息如表1所示 通过分析 可以发现孤立点数据中存在两种典型的孤立点类别 1 孤立点数据远远偏离于正常值的范围序号1 4 噪声 2 孤立点数据偏离于正常值的范围可能是录入错误 可能是真实数据 基于距离的离群点检测 149 基于密度的离群点检测 基于距离的Outlier检测是基于全局距离分布的当数据不是均匀分布时 在识别outliers时就存在困难例 C1包含400稀疏分布的点 C2包含100个紧致的点 2outlier点o1