1、第第7 7章章 聚类分析聚类分析OUTLINES一、引言二、聚类标准三、k-means算法四、EM算法五、利用Microsoft SQL Server 2005实践聚类分析算法 2医学数学挖掘SQL SERVER 2005 案例分析一、引言一、引言v 对某城市年龄范围为25岁55岁的中青年人群进行调查。调查数据项包括年龄、性别等项。3医学数学挖掘SQL SERVER 2005 案例分析一、引言一、引言4血脂高的血脂高的都都没有冠心病没有冠心病分类1的血脂较高的人多，有冠心心脏病的人多；而分类6的血脂普遍正常，且都没有冠心病。医学数学挖掘SQL SERVER 2005 案例分析一、引言一、引言v
2、 聚类（Cluster Analysis）是一个将数据集划分为若干组或类的过程。将一组物理的或抽象的对象，根据它们之间的相似程度，分为若干组，其中相似的对象构成一组，这一过程称为聚类过程。5医学数学挖掘SQL SERVER 2005 案例分析一、引言一、引言对在坐的各位同学进行聚类，对在坐的各位同学进行聚类，你们看看可以分成哪些类？你们看看可以分成哪些类？6医学数学挖掘SQL SERVER 2005 案例分析一、引言一、引言v 从上面的讨论可以发现从上面的讨论可以发现知道分类的数目后更容易进行划分不知道分类数怎么办？需要确定分类标准如何把数据输入计算机，如何让计算机进行计算？每个元素是否只能属
3、于某一类？软聚类硬聚类7医学数学挖掘SQL SERVER 2005 案例分析二、聚类标准二、聚类标准v 输入模式可用向量表示，比较不同模式的相似性可转化为输入模式可用向量表示，比较不同模式的相似性可转化为比较两个向量的距离，因而可用模式向量间的距离作为聚比较两个向量的距离，因而可用模式向量间的距离作为聚类判据。类判据。v 传统模式识别中常用到的两种聚类判据是欧式最小距离法传统模式识别中常用到的两种聚类判据是欧式最小距离法和余弦法。和余弦法。8医学数学挖掘SQL SERVER 2005 案例分析二、聚类标准二、聚类标准v 欧氏距离法欧氏距离法9)()(iTiiXXXXXXX1（0,2）X2（0,
4、0）20)-0,2-0(0)-0,2-0(T21XX医学数学挖掘SQL SERVER 2005 案例分析二、聚类标准二、聚类标准v 余弦法余弦法10iiTXXXXcosX1（0,2）X2（5,0）0525,00,2cosT医学数学挖掘SQL SERVER 2005 案例分析三、三、k-meansk-means算法算法v k-means算法以距离值的平均值对聚类成员进行分配，如果一个对象属于一个聚类，则该数据一定比较靠近聚类的中心11医学数学挖掘SQL SERVER 2005 案例分析三、三、k-meansk-means算法算法v 对二维坐标中的5个点X1,X2,X3,X4,X5作聚类分析。5个
5、二维样本为：X1（0,2），X2（0,0），X3（1.5,0），X4（5,0），X5（5,2）。假设要求的簇的数量k=2。12医学数学挖掘SQL SERVER 2005 案例分析三、三、k-meansk-means算法算法13医学数学挖掘SQL SERVER 2005 案例分析三、三、k-meansk-means算法算法14医学数学挖掘SQL SERVER 2005 案例分析三、三、k-meansk-means算法算法15医学数学挖掘SQL SERVER 2005 案例分析三、三、k-meansk-means算法算法16医学数学挖掘SQL SERVER 2005 案例分析三、三、k-means
6、k-means算法算法v k-means聚类被认为是硬聚类，因为每一个对象只能被分配到一个聚类。类与类之间不相互连接，并且也不相互重叠，计算步骤如下：1）选择一个含有随机选择样本的k个簇的初始划分，计算这些簇的质心（簇的平均值）。2）根据欧氏距离把每个样本重新分配到距离它最近的簇质心。3）计算被分配到每个簇的样本的均值向量，作为新的簇的质心。4）重复2,3直到k个簇的质心点不再发生变化或准则函数收敛。17医学数学挖掘SQL SERVER 2005 案例分析三、三、k-meansk-means算法算法v k-means算法的准则函数通常用平方误差标准准则，其定义如下：其中E为数据集中所有对象的平
7、方误差总和；X代表每个样本；mi为簇Ci的平均值（质心）。该准则使生成的类别尽可能地紧凑和独立。1821|ikiiXCEXm医学数学挖掘SQL SERVER 2005 案例分析三、三、k-meansk-means算法算法v 练习：对二维坐标中的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医学数学挖掘SQL SERVER 2005 案例分析三、三、k-meansk-means算法算法20医学数学挖掘SQL SERVER 2005 案例分析三、
8、三、k-meansk-means算法算法v 从前面的例子可以看出主要存在如下两点不足：从前面的例子可以看出主要存在如下两点不足：nk-Means方法只有在簇的平均值被定义的情况下才能使用。这可能不适用于某些应用。要求用户必须事先给出k(要生成的簇的数目)可以算是该方法的一个缺点。nk-Means方法不适用于发现非凸面形状的簇，而且,它对于“噪声”和孤立点数据是敏感的，少量的该种数据能够对平均值产生极大的影响。21医学数学挖掘SQL SERVER 2005 案例分析四、四、EMEM算法算法v 现实世界很多数据是不完整的，即数据存在残缺问题。例如数据集中缺少一些变量，更一般的情况是，任何含有隐含变
9、量(不能直接观察到的变量)的模型都可以被归纳为数据残缺问题。v EM(Expectation Maximization，期望最大化)是K-Means方法的一种扩展。它不把对象分配给一个确定的簇，而是根据对象与簇之间的隶属关系发生的概率来分配对象。EM算法是解决数据残缺问题的一种出色算法。22医学数学挖掘SQL SERVER 2005 案例分析四、四、EMEM算法算法v EMEM算法基本思想：算法基本思想：nEM算法不是为每一个维选择一个点，然后计算距离，而是把每一维作为一个钟型曲线，并计算平均值和标准差。当某一个点落到一个钟型曲线内时，它以某一概率分配给某一聚类。n每一个聚类的曲线可以重叠，所
10、以每一点可以属于多个聚类，且每一聚类有不同的概率。n这种技术被认为是软聚类，因为该算法允许聚类之间重叠，并且允许模糊的边界。23医学数学挖掘SQL SERVER 2005 案例分析四、四、EMEM算法算法v EMEM算法的步骤：估计步骤（算法的步骤：估计步骤（EstimateEstimate）和最大化步骤）和最大化步骤(Maximize)(Maximize)，EMEM算法的名字由这两个步骤的英文单词的第算法的名字由这两个步骤的英文单词的第一个字母组成。具体情况如下：一个字母组成。具体情况如下：n令D=x(1),x(n)为n个观察到的数据向量。设H=z(1),z(n)表示隐藏变量z的n个值，与观
11、察到的数据点D一一对应n观察到数据的对数似然函数为：24 log|log,|Hlp Dp D H医学数学挖掘SQL SERVER 2005 案例分析四、四、EMEM算法算法25 log,|,|log,|log1 log,|log ,HHHHHlp D Hp D HQ HQ Hp D HQ HQ HQ Hp D HQ HQ HF Q医学数学挖掘SQL SERVER 2005 案例分析四、四、EMEM算法算法v EMEM算法在以下两者间交替：固定参数算法在以下两者间交替：固定参数，使，使F F相对于分布相对于分布Q Q最大化；固定分布最大化；固定分布Q=p(H),Q=p(H),使使F F相对于参数
12、相对于参数最大化。具体最大化。具体分为如下两个步骤：分为如下两个步骤：261:argmax,kkkQEQF Q步骤1:argmax,kkkMF Q步骤医学数学挖掘SQL SERVER 2005 案例分析v 对某城市年龄范围为25岁55岁的中青年人群进行调查。各属性的含义如下：27属性含义属性含义属性含义ID主键Tiredness熬夜familial medical history家族心血管病史Sex性别Exercise运动锻炼习惯fatness肥胖情况Age年龄Diet个人饮食偏好hypertension血压Profession工作压力状况sitting-up早起习惯blood sugar血糖
13、Marital Status婚姻状况petting养宠物blood fat血脂Own car是否有车drink喝酒diabetes糖尿病Emotion情绪状态smoking吸烟coronary heart disease冠心（心脏）病医学数学挖掘SQL SERVER 2005 案例分析五、Microsoft SQL Server 2005实践聚类分析28医学数学挖掘SQL SERVER 2005 案例分析五、Microsoft SQL Server 2005实践聚类分析v MicrosoftMicrosoft聚类分析通过其查看器来解释，聚类分析通过其查看器来解释，SQL Server SQL
14、Server Analysis ServerAnalysis Server提供的聚类分析查看器有提供的聚类分析查看器有4 4个选项卡。聚个选项卡。聚类之间是相互联系的，通过单独的某一个视图难以理解挖类之间是相互联系的，通过单独的某一个视图难以理解挖掘模型，但可以同时使用这些视图。掘模型，但可以同时使用这些视图。v 聚类的目的之一是给每一类贴上标签聚类的目的之一是给每一类贴上标签29医学数学挖掘SQL SERVER 2005 案例分析五、Microsoft SQL Server 2005实践聚类分析v（1 1）获得顶层视图）获得顶层视图30血脂高的血脂高的都没有冠心病都没有冠心病分类1的血脂较高
15、的人多，有冠心心脏病的人多；而分类6的血脂普遍正常，且都没有冠心病。医学数学挖掘SQL SERVER 2005 案例分析五、Microsoft SQL Server 2005实践聚类分析v（1 1）获得顶层视图）获得顶层视图31分类分类1医学数学挖掘SQL SERVER 2005 案例分析五、Microsoft SQL Server 2005实践聚类分析v（2 2）选择一个聚类并且找出与其它聚类之间的区别，以聚）选择一个聚类并且找出与其它聚类之间的区别，以聚类类1 1为例：分类特征视图，该视图通过以递减概率显示属性为例：分类特征视图，该视图通过以递减概率显示属性来描述聚类事例的特征来描述聚类事
16、例的特征32这个聚类的成这个聚类的成员喜欢早起，员喜欢早起，工作强度大等，工作强度大等，然而这些信息然而这些信息还不能作为该还不能作为该类的标识，可类的标识，可能其它类也喜能其它类也喜欢早起和工作欢早起和工作强度强度大。大。医学数学挖掘SQL SERVER 2005 案例分析五、Microsoft SQL Server 2005实践聚类分析v 点击分类对比选项卡，将分类点击分类对比选项卡，将分类1 1与它的补充进行了比较。与它的补充进行了比较。33这里可以这里可以看到冠心看到冠心病才是类病才是类1最重要的最重要的特征。特征。医学数学挖掘SQL SERVER 2005 案例分析五、Microso
17、ft SQL Server 2005实践聚类分析v（3 3）确定一个聚类如何区别于相邻的聚类）确定一个聚类如何区别于相邻的聚类这个聚类可能非常相似于其它的聚类，并且在这个时候所做的标识适用于所有这些聚类。与聚类1相似的聚类强度都不大，相对来说，与类8和类10相似性大点。通过比较类1和8，可以看出这两个聚类的重要差异是劳动强度和是否早起；通过比较类1和10，可以看出这两个聚类的重要差异是是否养宠物。34医学数学挖掘SQL SERVER 2005 案例分析五、Microsoft SQL Server 2005实践聚类分析v（4 4）验证判断是否正确）验证判断是否正确通过比较聚类与其相邻的聚类，并且
18、对聚类进行改进的时候，就有可能出现误导的情况:两个聚类之间的差别可能是由一个属性引起的，该属性在这两个聚类中都不常见，但是在其中一个聚类中更少见。通过对聚类1进行进一步验证，发现可以用“冠心病”标识“聚类1”，即聚类1的主要特征是有“冠心病”。35医学数学挖掘SQL SERVER 2005 案例分析五、Microsoft SQL Server 2005实践聚类分析v（5 5）对聚类进行标识）对聚类进行标识 聚类1为“冠心病”36医学数学挖掘SQL SERVER 2005 案例分析五、Microsoft SQL Server 2005实践聚类分析v 结论：结论：冠心病高发人群有如下特点：高血脂，
19、高血压，很少运动，经常熬夜，工作压力大，有家族新血压或心脏病病史，都不养宠物。同时发现男性比例显著高于女性的发病率等。可以对这些因素进一步进行分析，对冠心病的预防、治疗及其医疗保健等有重要的指导作用。37五、Microsoft SQL Server 2005实践聚类分析医学数学挖掘SQL SERVER 2005 案例分析作业作业根据图根据图7-27-2中数据，修改中数据，修改EMEM算法的相关参数，看看结果有算法的相关参数，看看结果有何不同，并分析原因。何不同，并分析原因。在针对图在针对图7-27-2进行聚类分析的基础上标识其它类。进行聚类分析的基础上标识其它类。单击图单击图7-67-6中的中
20、的“挖掘模型挖掘模型”，单击右键选择，单击右键选择“设置算法设置算法参数参数”，将，将CLUSTER COUNT CLUSTER COUNT 设置为设置为8 8，然后处理并查看模，然后处理并查看模型，试着对其进行解释。型，试着对其进行解释。38医学数学挖掘SQL SERVER 2005 案例分析小结小结聚类是一种强大的工具。聚类可用来理解数据，也可以用来做数据分析的关键步骤。聚类分析可以按相似性对数据进行分组，并且可以对数据进行深入的分析，获得其它方法不可能获得的信息。一旦数据聚类完之后，聚类的结果就可以应用于市场竞争、异常检测、趋势分析或者进一步分析等。本章7.4.2的案例分析中，可以对每一
21、类进行标识，然后对感兴趣的类作进一步分析。比如类1，当发现冠心病高发人群具有的特点时，可以对“高血脂，高血压，很少运动，经常熬夜，工作压力大，有家族新血压或心脏病病史，都不养宠物”进行关联分析和回归分析，从而可进一步得出降低冠心病的预防策略。本章详细的介绍了聚类分析的基本概念、工作原理和常用算法及其特点，重点介绍了k-means和EM算法。在学习本章后，读者将了解不同聚类算法的优缺点，学会k-means算法，掌握利用SQL Server 2005数据挖掘工具做聚类分析。通过对SQL Server 2005聚类分析模型查看器的详细介绍，不但让读者学会了利用Sql Server 2005做聚类分析，而且让读者进一步理解了EM算法的基本原理及其在医学领域的应用。39医学数学挖掘SQL SERVER 2005 案例分析
