《聚类分析》PPT课件.ppt

医药信息分析与决策,第三章 聚类分析,本章要点,一、引言二、聚类标准三、k-means算法四、EM算法五、案例分析,2,医学信息分析与决策课程组,*,一、引言,对某城市年龄范围为25岁55岁的中青年人群进行调查。调查数据项包括年龄、性别等项。,*,3,医学信息分析与决策课程组,一、引言,*,4,医学信息分析与决策课程组,血脂高的,都没有冠心病,分类1的血脂较高的人多，有冠心心脏病的人多；而分类6的血脂普遍正常，且都没有冠心病。,聚类（Cluster Analysis）是一个将数据集划分为若干组或类的过程。将一组物理的或抽象的对象，根据它们之间的相似程度，分为若干组，其中相似的对象构成一组，这一过程称为聚类过程。,*,5,医学信息分析与决策课程组,一、引言,一、引言,对在坐的各位同学进行聚类，你们看看可以分成哪些类？,*,6,医学信息分析与决策课程组,一、引言,从上面的讨论可以发现知道分类的数目后更容易进行划分？不知道分类数怎么办需要确定分类标准？如何把数据输入计算机，如何让计算机进行计算？每个元素是否只能属于某一类软聚类硬聚类,*,7,医学信息分析与决策课程组,二、聚类标准,输入模式可用向量表示，比较不同模式的相似性可转化为比较两个向量的距离，因而可用模式向量间的距离作为聚类判据。传统模式识别中常用到的两种聚类判据是欧式最小距离法和余弦法,*,8,医学信息分析与决策课程组,二、聚类标准,欧氏距离法,*,9,医学信息分析与决策课程组,X1（0,2）X2（0,0）,二、聚类标准,余弦法,*,10,医学信息分析与决策课程组,X1（0,2）X2（5,0）,三、k-means算法,k-means算法以距离值的平均值对聚类成员进行分配，如果一个对象属于一个聚类，则该数据一定比较靠近聚类的中心,*,11,医学信息分析与决策课程组,三、k-means算法,对二维坐标中的5个点X1,X2,X3,X4,X5作聚类分析。5个二维样本为：X1（0,2），X2（0,0），X3（1.5,0），X4（5,0），X5（5,2）。假设要求的簇的数量k=2。,*,12,医学信息分析与决策课程组,三、k-means算法,*,13,医学信息分析与决策课程组,三、k-means算法,*,14,医学信息分析与决策课程组,三、k-means算法,*,15,医学信息分析与决策课程组,三、k-means算法,*,16,医学信息分析与决策课程组,三、k-means算法,k-means聚类被认为是硬聚类，因为每一个对象只能被分配到一个聚类。类与类之间不相互连接，并且也不相互重叠，计算步骤如下：1）选择一个含有随机选择样本的k个簇的初始划分，计算这些簇的质心（簇的平均值）。2）根据欧氏距离把每个样本重新分配到距离它最近的簇质心。3）计算被分配到每个簇的样本的均值向量，作为新的簇的质心。4）重复2,3直到k个簇的质心点不再发生变化或准则函数收敛。,*,17,医学信息分析与决策课程组,三、k-means算法,k-means算法的准则函数通常用平方误差标准准则，其定义如下：,*,18,医学信息分析与决策课程组,三、k-means算法,练习：对二维坐标中的6个点X1,X2,X3,X4,X5,X6作聚类分析。6个二维样本为：X1（0,2），X2（0,0），X3（1.5,0），X4（5,0），X5（5,2），X6（0,20）。假设要求的簇的数量k=2。,*,19,医学信息分析与决策课程组,三、k-means算法,*,20,医学信息分析与决策课程组,三、k-means算法,*,21,医学信息分析与决策课程组,这种分法有意义吗?,三、k-means算法,从前面的例子可以看出主要存在如下两点不足：k-Means方法只有在簇的平均值被定义的情况下才能使用。这可能不适用于某些应用。要求用户必须事先给出k(要生成的簇的数目)可以算是该方法的一个缺点。k-Means方法不适用于发现非凸面形状的簇，而且,它对于“噪声”和孤立点数据是敏感的，少量的该种数据能够对平均值产生极大的影响。,*,22,医学信息分析与决策课程组,*,23,医学信息分析与决策课程组,作业：1.P127,一（3）2.预习EM算法,Conclusion,*,24,医学信息分析与决策课程组,四、EM算法,现实世界很多数据是不完整的，即数据存在残缺问题。例如数据集中缺少一些变量，更一般的情况是，任何含有隐含变量(不能直接观察到的变量)的模型都可以被归纳为数据残缺问题。EM(Expectation Maximization，期望最大化)是K-Means方法的一种扩展。它不把对象分配给一个确定的簇，而是根据对象与簇之间的隶属关系发生的概率来分配对象。EM算法是解决数据残缺问题的一种出色算法。,*,25,医学信息分析与决策课程组,四、EM算法,EM算法基本思想：EM算法不是为每一个维选择一个点，然后计算距离，而是把每一维作为一个钟型曲线，并计算平均值和标准差。当某一个点落到一个钟型曲线内时，它以某一概率分配给某一聚类。每一个聚类的曲线可以重叠，所以每一点可以属于多个聚类，且每一聚类有不同的概率。这种技术被认为是软聚类，因为该算法允许聚类之间重叠，并且允许模糊的边界。,*,26,医学信息分析与决策课程组,四、EM算法,EM算法的步骤：估计步骤（Estimate）和最大化步骤(Maximize)，EM算法的名字由这两个步骤的英文单词的第一个字母组成。具体情况如下：令D=x(1),x(n)为n个观察到的数据向量。设H=z(1),z(n)表示隐藏变量z的n个值，与观察到的数据点D一一对应观察到数据的对数似然函数为：,*,27,医学信息分析与决策课程组,四、EM算法,*,28,医学信息分析与决策课程组,四、EM算法,EM算法在以下两者间交替：固定参数，使F相对于分布Q最大化；固定分布Q=p(H),使F相对于参数最大化。具体分为如下两个步骤：,*,29,医学信息分析与决策课程组,五、案例分析,对某城市年龄范围为25岁55岁的中青年人群进行调查。各属性的含义如下：,*,30,医学信息分析与决策课程组,五、案例分析,*,31,医学信息分析与决策课程组,五、案例分析,Microsoft聚类分析通过其查看器来解释，SQL Server Analysis Server提供的聚类分析查看器有4个选项卡。聚类之间是相互联系的，通过单独的某一个视图难以理解挖掘模型，但可以同时使用这些视图。聚类的目的之一是给每一类贴上标签,*,32,医学信息分析与决策课程组,五、案例分析,（1）获得顶层视图,*,33,医学信息分析与决策课程组,血脂高的,都没有冠心病,分类1的血脂较高的人多，有冠心心脏病的人多；而分类6的血脂普遍正常，且都没有冠心病。,五、案例分析,（1）获得顶层视图,*,34,医学信息分析与决策课程组,分类1,五、案例分析,（2）选择一个聚类并且找出与其它聚类之间的区别，以聚类1为例：分类特征视图，该视图通过以递减概率显示属性来描述聚类事例的特征,*,35,医学信息分析与决策课程组,这个聚类的成员喜欢早起，工作强度大等，然而这些信息还不能作为该类的标识，可能其它类也喜欢早起和工作强度大,五、案例分析,点击分类对比选项卡，将分类1与它的补充进行了比较。,*,36,医学信息分析与决策课程组,这里可以看到冠心病才是类1最重要的特征。,五、案例分析,（3）确定一个聚类如何区别于相邻的聚类这个聚类可能非常相似于其它的聚类，并且在这个时候所做的标识适用于所有这些聚类。与聚类1相似的聚类强度都不大，相对来说，与类8和类10相似性大点。通过比较类1和8，可以看出这两个聚类的重要差异是劳动强度和是否早起；通过比较类1和10，可以看出这两个聚类的重要差异是是否养宠物。,*,37,医学信息分析与决策课程组,五、案例分析,（4）验证判断是否正确通过比较聚类与其相邻的聚类，并且对聚类进行改进的时候，就有可能出现误导的情况:两个聚类之间的差别可能是由一个属性引起的，该属性在这两个聚类中都不常见，但是在其中一个聚类中更少见。通过对聚类1进行进一步验证，发现可以用“冠心病”标识“聚类1”，即聚类1的主要特征是有“冠心病”。,*,38,医学信息分析与决策课程组,五、案例分析,（5）对聚类进行标识 聚类1为“冠心病”,*,39,医学信息分析与决策课程组,五、案例分析,结论：冠心病高发人群有如下特点：高血脂，高血压，很少运动，经常熬夜，工作压力大，有家族新血压或心脏病病史，都不养宠物。同时发现男性比例显著高于女性的发病率等。可以对这些因素进一步进行分析，对冠心病的预防、治疗及其医疗保健等有重要的指导作用。,*,40,医学信息分析与决策课程组,*,41,医学信息分析与决策课程组,Thank You,