聚类及贝叶斯分类.ppt

聚类 Cluster 聚类目的在将相似的事物归类 聚类分析又称为 同质分组 或者 无监督的分类 指把一组数据分成不同的 簇 每簇中的数据相似而不同簇间的数据则距离较远 相似性可以由用户或者专家定义的距离函数加以度量 好的聚类方法应保证不同类间数据的相似性尽可能地小 而类内数据的相似性尽可能地大 1 2020 3 25 聚类分析的基本思想是认为所研究的数据集中的数据或者属性之间存在着程度不同的相似性 于是从数据集中取出一批数据 具体找出一些能够度量数据值之间或者属性之间相似程度的量 以这些量为中心作为划分类型的依据 把一些相似程度较大的数据或属性聚合为一类 把另外一些彼此之间相似程度较大的样品又聚合为另一类 关系密切的聚合到一个小的分类单位 关系疏远的聚合到一个大的分类单位 直到所有数据或属性都聚合完毕 把不同的类型一一划分出来 比较常用的距离有 绝对值距离欧氏距离明斯基距离 2020 3 25 4 HierarchicalClustering层次聚类法 该方法是利用距离矩阵作为分类标准 将n个样品各作为一类 计算n个样品两两之间的距离 构成距离矩阵 合并距离最近的两类为一新类 计算新类与当前各类的距离 再合并 计算 直至只有一类为止 K均值算法 K均值 k means 是一种简便 实用的无监督聚类分析算法 这种算法在已知簇的个数时 可很好地实现数据的聚类分析 基本思想 1 首先 随机选择k个数据点做为聚类中心 2 然后 计算其它点到这些聚类中心点的距离 通过对簇中距离平均值的计算 不断改变这些聚类中心的位置 直到这些聚类中心不再变化为止 2020 3 25 6 K MeansClusteringK 均值聚类方法 Example 0 1 2 3 4 5 6 7 8 9 10 0 1 2 3 4 5 6 7 8 9 10 K 2ArbitrarilychooseKobjectasinitialclustercenter Assigneachobjectstomostsimilarcenter Updatetheclustermeans Updatetheclustermeans reassign reassign K均值的流程 由流程图可知 k 均值算法是一种基于对数据集进行划分的方法进行聚类的算法 它是不断趋于最优解的试探过程 每一次迭代都试图使簇中心的选择更加接近于数据集的实际簇中心 K均值算法 优势 1 算法简单 2 执行和收敛过程相对较快 是一种常见的聚类算法 局限性 1 算法要求簇是密集的 簇和簇之间的差异比较大 2 数据集的平均值的计算必须有适当的定义 3 对于某些孤立数据和 噪声 点敏感等 Na veBayes算法 微软朴素贝叶斯算法是SAS中最简单的算法 通常用作理解数据基本分组的起点 说的简单一点就是处理数据的分类虽然该算法既可用于预测也可用于分组 但最常用于模型构建的早期阶段 更常用于分组而不是预测某个具体的值 定义事件组A1 A2 An n可为 称为样本空间S的一个划分 若满足 A1 A2 An B Na veBayes分类 定理设A1 An是S的一个划分 且P Ai 0 i 1 n 则对任何事件B S 有 式子就称为贝叶斯公式 贝叶斯定理回顾 例子 已知某种疾病的发病率为0 1 该种疾病患者一个月以内的死亡率为90 且知未患该种疾病的人一个月以内的死亡率为0 1 现从人群中任意抽取一人 问此人在一个月内死亡的概率是多少 若已知此人在一个月内死亡 则此人是因该种疾病致死的概率为多少 贝叶斯定理回顾 贝叶斯公式给出了 结果 事件B已发生的条件下 原因 属于事件Ai的条件概率 从这个意义上讲 它是一个 执果索因 的条件概率计算公式 相对于事件B而言 概率论中把P Ai 称为先验概率 PriorProbability 而把P Ai B 称为后验概率 PosteriorProbability 这是在已有附加信息 即事件B已发生 之后对事件发生的可能性做出的重新认识 体现了已有信息带来的知识更新 贝叶斯定理回顾 分类问题 这个人会不会逃税 分类问题 贝叶斯分类方法 把每一个属性 输入 和分类变量 输出 都看作随机变量对于具有属性值 A1 A2 An 的观测记录目标是预测类别C特别地 我们想找能够最大化P C A1 A2 An 的C值能否从直接数据中估计P C A1 A2 An 贝叶斯分类方法 方法 使用贝叶斯定理对于分类变量C的所有值计算后验概率P C A1 A2 An 选择C使得P C A1 A2 An 最大等价于选择C使得P A1 A2 An C P C 最大如何估计P A1 A2 An C 简单贝叶斯 假设在给定的类别上属性变量Ai相互独立 P A1 A2 An C P A1 Cj P A2 Cj P An Cj 对所有的Ai和Cj计算P Ai Cj 如果对某一个Cj P Cj P Ai Cj 最大 新的数据点就被分类到Cj 分类问题 类别 P Ck Nk N例如 P C 否 7 10 P C 是 3 10Nk是类别C Ck 的数量对离散属性 P Ai Ck Aik Nk Aik 是属性值为Ai且属于Ck的记录数量例如 P 婚姻状况 婚姻中 否 4 7P 去年退税 是 是 0 对于连续属性 sqlserver不能处理连续型属性 离散化把属性的范围划分为许多段 每一段设定一个有序值这样会违反独立性假设估计概率密度假定属性服从正态分布估计该属性分布的参数 例如 均值和标准差 在得到概率密度之后 我们可以使用它估计条件概率P Ai c 分类问题 分类问题 每一对 Ai ci 的正态分布 例如对于 收入 逃税 否 在逃税 否的情况下 可征税收入的样本均值 110样本方差 2975 分类问题 每一对 Ai ci 的正态分布 例如对于 收入 逃税 否 在逃税 否的情况下 可征税收入的样本均值 110样本方差 2975 思路 看p 逃税 否 X 是否大于p 逃税 是 X p 逃税 否 X p 逃税 否 P X 逃税 否 p B p 逃税 是 X p 逃税 是 P X 逃税 是 p B P X 逃税 否 P 去年退税 否 逃税 否 P 婚姻中 逃税 否 P 收入 120K 逃税 否 P X 逃税 是 P 去年退税 否 逃税 是 P 婚姻中 逃税 是 P 收入 120K 逃税 是 分类问题 P X 逃税 否 P 去年退税 否 逃税 否 P 婚姻中 逃税 否 P 收入 120K 逃税 否 4 7 4 7 0 0072 0 0024P X 逃税 是 P 去年退税 否 逃税 是 P 婚姻中 逃税 是 P 收入 120K 逃税 是 1 0 1 2 10 9 0因为 P X 否 P 否 P X 是 P 是 0 0024 0 3 0 0 7 所以 P 否 X P 是 X 逃税 否 A 胎生 是 会飞 否 水中生活 是 有腿 否 M 哺乳动物N 非哺乳动物 P A M P M P A N P N 哺乳动物 分类问题 这个算法之所以称为 朴素 是因为所有属性的重要性是一样的 没有谁高谁低一说 它是一种运用算术原则来理解数据的方法对此算法的另一个理解就是 所有属性都是独立的 互不相关的 从字面来看 该算法只是计算所有属性之间的关联 虽然该算法既可用于预测也可用于分组 但最常用于模型构建的早期阶段 更常用于分组而不是预测某个具体的值 通常要将所有属性标记为简单输入或者既是输入又是可预测的 因为这就可以要求算法在执行的时候考虑到所有属性 很常见的一种情况是 在输入中包含大量属性 然后处理模型再评估结果 如果结果看起来没什么意义 我们经常减少包含的属性数量 以便更好地理解关联最紧密的关系 贝叶斯方法的不足 1 贝叶斯方法最有争议之处就是先验信息的使用 先验信息来源于经验或者以前的实验结论 没有确定的理论依据作支持 因此在很多方面颇有争议 由于很多工作都是基于先验信息的 如果先验信息不正确 或者存在误差 那么最后导致的结论就会是不可想象的 尤其是在数据挖掘中 挖掘出的知识也是不可预知的 就是说不知道挖掘出的知识是有用的还是无用的 甚至是错误的 虽然知识发现中有一步是进行知识评估 但是这种评估并不能总是知识的可用性和有效性 特别不能确定先验信息是否正确时 这种评估更带有不确定性 2 处理数据复杂性高 因此时间和空间消耗也比较大 贝叶斯方法要进行后验概率的计算 区间估计 假设检验等 大量的计算是不可避免的 如果我们拥有大量的数据 而且对数据的了解又很少 这时候可以使用朴素贝叶斯算法 例如 公司可能由于兼并了一家竞争对手而获得了大量的销售数据 在处理这些数据的时候 可以用朴素贝叶斯算法作为起点 应该了解的是 SQLSERVER中这个算法有一个明显的局限 就是只能处理离散的内容类型 如果选择的数据结构中包含有内容类型不是Discrete的数据列 那么朴素贝叶斯算法建立的挖掘模型会忽略这些数据 实例 办信用卡意愿分析 40 2020 3 25 41 解 首先根据训练样本计算各属性相对于不同分类结果的条件概率 P 办卡 7 10P 不办卡 3 10P 女性 办卡 5 7P 女性 不办卡 1 3P 年龄 31 45 办卡 3 7P 年龄 31 45 不办卡 1 3P 学生 否 办卡 5 7P 学生 否 不办卡 0 3P 收入 中 办卡 2 7P 收入 中 不办卡 2 3 2020 3 25 判断 X 女性 年龄介于31 45之间 不具学生身份 收入中等 会不会办理信用卡 其次 再应用朴素贝氏分类器进行类别预测 计算P 办卡 P 女性 办卡 P 年龄31 45 办卡 P 不是学生 办卡 P 收入中 办卡 15 343 0 044P 不办卡 P 女性 不办卡 P 年龄31 45 不办卡 P 不是学生 不办卡 P 收入中等 不办卡 00 044 0 42 2020 3 25 43 2020 3 25 训练样本中对于 女性 年龄介于31 45之间 不具学生身份 收入中等 的个人 按照朴素贝叶斯分类会将其分到办信用卡一类中 办卡的概率是 0 044 0 044 0 1 正规化分类的结果P 会 P 会 P 不会 聚类分析的基本思想是在样品之间定义距离 在变量之间定义相似系数 距离或相似系数代表样品或变量之间的相似程度 按相似程度的大小 将样品或变量逐一归类 关系密切的类聚集到一个小的分类单位 然后逐步扩大 使得关系疏远的聚合到一个大的分类单位 直到所有的样品或变量都聚集完毕 形成一个表示亲属关系的谱系图 依次按照某些要求对某些样品或变量进行分类 聚类和分类的主要区别是 在进行聚类分析以前 对总体到底有几种类型并不知道 对已知数据分几类需在聚类的过程中探索调整 而分类是在事前已知道分为哪些类 贝叶斯方法用于聚类的挖掘算法目前并不广泛 目前主要是用简单贝叶斯学习模型来进行聚类 由于贝叶斯方法的主要特点是通过先验信息来推得后验知识 如果将贝叶斯方法进行聚类 其基本思想就是