第六讲聚类及贝叶斯分类

1、聚类（Cluster）聚类目的在将相似的事物归类。 聚类分析又称为“同质分组”或者“无监督的分类”，指把一组数据分成不同的“簇”，每簇中的数据相似而不同簇间的数据则距离较远。相似性可以由用户或者专家定义的距离函数加以度量。 好的聚类方法应保证不同类间数据的相似性尽可能地小，而类内数据的相似性尽可能地大。 12/13/2022 聚类分析的基本思想是认为所研究的数据集中的数据或者属性之间存在着程度不同的相似性。于是从数据集中取出一批数据，具体找出一些能够度量数据值之间或者属性之间相似程度的量，以这些量为中心作为划分类型的依据，把一些相似程度较大的数据或属性聚合为一类，把另外一些彼此之间相似程度较大

2、的样品又聚合为另一类，关系密切的聚合到一个小的分类单位，关系疏远的聚合到一个大的分类单位，直到所有数据或属性都聚合完毕，把不同的类型一一划分出来。聚类分析示例数据集聚类分析的数据集聚类分析的数据集没有类别属性没有类别属性比较常用的距离有 绝对值距离 欧氏距离 明斯基距离2022-2-135Hierarchical Clustering层次聚类法 该方法是利用距离矩阵作为分类标准，将n个样品各作为一类；计算n个样品两两之间的距离，构成距离矩阵；合并距离最近的两类为一新类；计算新类与当前各类的距离；再合并、计算，直至只有一类为止。Step 0Step 1Step 2Step 3Step 4bdce

3、aa bd ec d ea b c d eStep 4Step 3Step 2Step 1Step 0agglomerative(AGNES)divisive(DIANA)K均值算法均值算法 K均值（k-means）是一种简便、实用的无监督聚类分析算法。这种算法在已知簇的个数时，可很好地实现数据的聚类分析。 基本思想 （1）首先，随机选择k个数据点做为聚类中心； （2）然后，计算其它点到这些聚类中心点的距离，通过对簇中距离平均值的计算，不断改变这些聚类中心的位置，直到这些聚类中心不再变化为止。2022-2-137K-Means Clustering K-均值聚类方法 Example：01234

4、5678910012345678910012345678910012345678910012345678910012345678910012345678910012345678910012345678910012345678910K=2Arbitrarily choose K object as initial cluster centerAssign each objects to most similar centerUpdate the cluster meansUpdate the cluster meansreassignreassign K K均值的流程均值的流程 由流程图可知，k

5、-均值算法是一种基于对数据集进行划分的方法进行聚类的算法。它是不断趋于最优解的试探过程。每一次迭代都试图使簇中心的选择更加接近于数据集的实际簇中心。输出N输入读入标准化归一化初始化簇计算簇平均值更改簇中心重新决定点归何簇Y簇中心是否变化K均值算法均值算法 优势优势（1）算法简单；（2）执行和收敛过程相对较快，是一种常见的聚类算法。 局限性局限性（1）算法要求簇是密集的、簇和簇之间的差异比较大；（2）数据集的平均值的计算必须有适当的定义；（3）对于某些孤立数据和“噪声”点敏感等。 Nave Bayes算法 微软朴素贝叶斯算法是SAS中最简单的算法，通常用作理解数据基本分组的起点,说的简单一点就是

6、处理数据的分类 虽然该算法既可用于预测也可用于分组，但最常用于模型构建的早期阶段，更常用于分组而不是预测某个具体的值 定义定义 事件组A1，A2，An (n可为)，称为样本空间S的一个划分，若满足：.,.,2 , 1,),(,)(;)(1njijiAAiiSAijiniiA1A2AnBNave Bayes 分类定理定理 设设A A1 1，, A, An n是是S S的一个划分，且的一个划分，且P(AP(Ai i) 0) 0，(i (i1 1，n)n)，则对任何事件则对任何事件B B S S，有有 ),.,1( ,)|()()|()()|(1njABPAPABPAPBAPniiijjj式子就称为

7、贝叶斯公式贝叶斯公式。贝叶斯定理回顾贝叶斯定理回顾)()/()()|(BPABPAPBAP例子：例子：已知某种疾病的发病率为已知某种疾病的发病率为0.1%, 0.1%, 该种疾病患者一个月该种疾病患者一个月以内的死亡率为以内的死亡率为90%90%；且知未患该种疾病的人一个月以内的；且知未患该种疾病的人一个月以内的死亡率为死亡率为0.1%0.1%；现从人群中任意抽取一人，问此人在一个月；现从人群中任意抽取一人，问此人在一个月内死亡的概率是多少？若已知此人在一个月内死亡，则此人内死亡的概率是多少？若已知此人在一个月内死亡，则此人是因该种疾病致死的概率为多少？是因该种疾病致死的概率为多少？45. 0

8、002. 09 . 0001. 0)()/()()|(00189. 0999. 0*001. 09 . 0*001. 0002. 0)()|()()|()(BPABPAPBAPAPABPAPABPBPAB：某人患有该种疾病，：某人在一个月内死亡答：设贝叶斯定理回顾贝叶斯定理回顾贝叶斯公式给出了贝叶斯公式给出了结果结果事件事件B B已发生的条件下，已发生的条件下，原因原因属于属于事件事件A Ai i的条件概率的条件概率. . 从这个意义上讲，它是一个从这个意义上讲，它是一个“执果索因执果索因”的条的条件概率计算公式件概率计算公式. .相对于事件相对于事件B B而言而言 ，概率论中，概率论中把把P

9、(Ai)P(Ai)称为先验概率（称为先验概率（Prior ProbabilityPrior Probability），），而把而把P(Ai|B)P(Ai|B)称为后验概率称为后验概率 （Posterior Posterior ProbabilityProbability），这是在已有附加信息（即事件），这是在已有附加信息（即事件B B已发生）之后对事件发生的可能性做出的重新已发生）之后对事件发生的可能性做出的重新认识，体现了已有信息带来的知识更新认识，体现了已有信息带来的知识更新. . 贝叶斯定理回顾贝叶斯定理回顾分类问题(,120K)X 对于去年退税否 婚姻状况婚姻中可征税收入这个人会不会逃

10、税?分类问题贝叶斯分类方法 把每一个属性（输入） 和分类变量（输出）都看作随机变量 对于具有属性值(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 )?)()()|()|(212121

11、nnnAAAPCPCAAAPAAACP简单贝叶斯简单贝叶斯 假设在给定的类别上属性变量 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/10 Nk 是类别C=Ck.的数量 对离散属性: P(Ai | Ck) = |Aik|/ Nk |Aik| 是属性值为Ai 且属于Ck的记录数量 例如:P

12、(婚姻状况=婚姻中|否) = 4/7P(去年退税=是|是)=0 对于连续属性: (sqlserver不能处理连续型属性) 离散化 把属性的范围划分为许多段： 每一段设定一个有序值 这样会违反独立性假设 估计概率密度 假定属性服从正态分布 估计该属性分布的参数 (例如, 均值和标准差) 在得到概率密度之后，我们可以使用它估计条件概率P(Ai|c)分类问题分类问题 每一对(Ai,ci)的正态分布: 例如对于(收入,逃税=否): 在逃税=否的情况下，可征税收入的 样本均值= 110 样本方差= 2975222)(221)|(ijijiAijjiecAP2(120 110)2(2975)1(120 |

13、)0.00722(54.54)Pe收入否分类问题 每一对(Ai,ci)的正态分布: 例如对于(收入,逃税=否): 在逃税=否的情况下，可征税收入的 样本均值= 110 样本方差= 2975222)(221)|(ijijiAijjiecAP2(120 110)2(2975)1(120|)0.00722 (54.54)Pe收入否l思路：看p（逃税=否| X）是否大于p （逃税=是| X）lp（逃税=否| X）=p（逃税=否） P(X|逃税=否）/ p(B)lp（逃税=是| X）=p（逃税=是） P(X|逃税=是）/ p(B)lP(X|逃税=否）= P(去年退税=否|逃税=否) P(婚姻中| 逃税=

14、否) P(收入=120K| 逃税=否)lP(X|逃税=是）=P(去年退税=否| 逃税=是) P(婚姻中| 逃税=是) P(收入=120K| 逃税=是)分类问题(,120K)X 对于去年退税否 婚姻状况婚姻中可征税收入)()/()()|(BPABPAPBAPP(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(否)

15、 P(X|是)P(是) 0.0024*0.3 0*0.7 所以： P(否|X) P(是|X) = 逃税 = 否0027. 02013004. 0)()|(021. 020706. 0)()|(0042. 01341331310131)|(06. 072727676)|(NPNAPMPMAPNAPMAPA: （胎生是，会飞否，水中生活是，有腿否）M: 哺乳动物N: 非哺乳动物P(A|M)P(M) P(A|N)P(N)= 哺乳动物哺乳动物分类问题 这个算法之所以称为“朴素”，是因为所有属性的重要性是一样的，没有谁高谁低一说。它是一种运用算术原则来理解数据的方法 对此算法的另一个理解就是：所有属性都

16、是独立的，互不相关的。从字面来看，该算法只是计算所有属性之间的关联。 虽然该算法既可用于预测也可用于分组，但最常用于模型构建的早期阶段，更常用于分组而不是预测某个具体的值。通常要将所有属性标记为简单输入或者既是输入又是可预测的，因为这就可以要求算法在执行的时候考虑到所有属性 很常见的一种情况是，在输入中包含大量属性，然后处理模型再评估结果，如果结果看起来没什么意义，我们经常减少包含的属性数量，以便更好地理解关联最紧密的关系。贝叶斯方法的不足贝叶斯方法的不足 (1) 贝叶斯方法最有争议之处就是先验信息的使用。先贝叶斯方法最有争议之处就是先验信息的使用。先验信息来源于经验或者以前的实验结论，没有确

17、定的理论验信息来源于经验或者以前的实验结论，没有确定的理论依据作支持，因此在很多方面颇有争议。由于很多工作都依据作支持，因此在很多方面颇有争议。由于很多工作都是基于先验信息的，如果先验信息不正确，或者存在误差，是基于先验信息的，如果先验信息不正确，或者存在误差，那么最后导致的结论就会是不可想象的。尤其是在数据挖那么最后导致的结论就会是不可想象的。尤其是在数据挖掘中，挖掘出的知识也是不可预知的，就是说不知道挖掘掘中，挖掘出的知识也是不可预知的，就是说不知道挖掘出的知识是有用的还是无用的，甚至是错误的。虽然知识出的知识是有用的还是无用的，甚至是错误的。虽然知识发现中有一步是进行知识评估，但是这种评

18、估并不能总是发现中有一步是进行知识评估，但是这种评估并不能总是知识的可用性和有效性，特别不能确定先验信息是否正确知识的可用性和有效性，特别不能确定先验信息是否正确时，这种评估更带有不确定性。时，这种评估更带有不确定性。 (2) 处理数据复杂性高，因此时间和空间消耗也比较大。处理数据复杂性高，因此时间和空间消耗也比较大。贝叶斯方法要进行后验概率的计算、区间估计、假设检验贝叶斯方法要进行后验概率的计算、区间估计、假设检验等，大量的计算是不可避免的。等，大量的计算是不可避免的。 如果我们拥有大量的数据，而且对数据的了解又很少，这时候可以使用朴素贝叶斯算法。 例如：公司可能由于兼并了一家竞争对手而获得

19、了大量的销售数据，在处理这些数据的时候，可以用朴素贝叶斯算法作为起点。 应该了解的是，SQLSERVER中这个算法有一个明显的局限：就是只能处理离散的内容类型，如果选择的数据结构中包含有内容类型不是Discrete的数据列，那么朴素贝叶斯算法建立的挖掘模型会忽略这些数据 实例：办信用卡意愿分析412/13/202242解：首先根据训练样本计算各属性相对于不同分类结果的条件概率： P(办卡)=7/10 P(不办卡)=3/10 P(女性|办卡)=5/7 P(女性|不办卡)=1/3 P(年龄=3145|办卡)=3/7P(年龄=3145|不办卡)=1/3 P(学生=否|办卡)=5/7 P(学生=否|不办卡)=0/3 P(收入=中|办卡)=2/7 P(收入=中|不办卡)=2/32/13/2022判断：X=(女性，年龄介于3145之间，不具学生身份，收入中等)会不会办理信用卡。 其次，再应用朴素贝氏分类器进行类别预测： 计算 P(办卡)P(女性|办卡)P(年龄3145|办卡)P(不是学生|办卡)P(收入中|办卡) =15/3430.044 P(不办卡)P(女性|不办卡)P(年龄3145|不办卡)P(不是