聚类分析

1第五章聚类分析主讲教师：魏宏喜(博士，副教授)E-mail:[e-mail]2第五章聚类分析（提纲）5.1聚类分析概述5.2相似性计算方法5.3常用聚类方法5.3.1划分方法k-means算法（k-均值算法）k-medoids算法（k-中心算法）5.3.2层次方法AGNES算法（合并聚类法）DIANA算法（分裂聚类法）5.4孤立点分析3第五章聚类分析（提纲）5.1聚类分析概述5.2相似性计算方法5.3常用聚类方法5.3.1划分方法k-means算法（k-均值算法）k-medoids算法（k-中心算法）5.3.2层次方法AGNES算法（合并聚类法）DIANA算法（分裂聚类法）5.4孤立点分析45.1聚类分析概述聚类分析的定义聚类分析(ClusterAnalysis)是一个将数据集中的所有数据，按照相似性划分为多个类别（Cluster,簇）的过程；簇是相似数据的集合。聚类分析是一种无监督(UnsupervisedLearning)分类方法：数据集中的数据没有预定义的类别标号（无训练集和训练的过程）。要求：聚类分析之后，应尽可能保证类别相同的数据之间具有较高的相似性，而类别不同的数据之间具有较低的相似性。55.1聚类分析概述聚类分析在数据挖掘中的作用：作为一个独立的工具来获得数据集中数据的分布情况；作为其他数据挖掘算法的预处理步骤。65.1聚类分析概述聚类分析在数据挖掘中的作用：作为一个独立的工具来获得数据集中数据的分布情况；首先，对数据集执行聚类，获得所有簇；然后，根据每个簇中样本的数目获得数据集中每类数据的大体分布情况。作为其他数据挖掘算法的预处理步骤。75.1聚类分析概述聚类分析在数据挖掘中的作用：作为一个独立的工具来获得数据集中数据的分布情况；作为其他数据挖掘算法的预处理步骤。首先，对数据进行聚类——粗分类；然后，分别对每个簇进行特征提取和细分类，可以有效提高分类精度。85.1聚类分析概述聚类分析的典型应用：空间数据分析图像处理——灰度图像的二值化（对灰度像素进行聚类）。万维网对WEB日志数据进行聚类，以发现类似的用户访问模式。金融领域用户交易数据的聚类分析，以获得奇异点（异常交易）。……95.1聚类分析概述常用的聚类分析方法：划分法（PartitioningMethods）：以距离作为数据集中不同数据间的相似性度量，将数据集划分成多个簇。属于这样的聚类方法有：k-means、k-medoids等。层次法（HierarchicalMethods）：对给定的数据集进行层次分解，形成一个树形的聚类结果。属于这样的聚类方法有：自顶向下法、自底向上法。10年龄80类别1类别2类别3收入60000300001500005.1聚类分析概述——划分法示例115.1聚类分析概述——层次法示例Step0Step1Step2Step3Step4bdceaabdecdeabcdeStep4Step3Step2Step1Step0agglomerative(AGNES)divisive(DIANA)12第五章聚类分析（提纲）5.1聚类分析概述5.2相似性计算方法5.3常用聚类方法5.3.1划分方法k-means算法（k-均值算法）k-medoids算法（k-中心算法）5.3.2层次方法AGNES算法（合并聚类法）DIANA算法（分裂聚类法）5.4孤立点分析135.2相似性计算方法在聚类分析中，样本之间的相似性通常采用样本之间的距离来表示。两个样本之间的距离越大，表示两个样本越不相似性，差异性越大；两个样本之间的距离越小，表示两个样本越相似性，差异性越小。特例：当两个样本之间的距离为零时，表示两个样本完全一样，无差异。145.2相似性计算方法在聚类分析中，样本之间的相似性通常采用样本之间的距离来表示。样本之间的距离是在样本的描述属性（特征）上进行计算的。在不同应用领域，样本的描述属性的类型可能不同，因此相似性的计算方法也不尽相同。连续型属性(如：重量、高度、年龄等)二值离散型属性(如：性别、考试是否通过等)多值离散型属性(如：收入分为高、中、低等)混合类型属性(上述类型的属性至少同时存在两种)155.2相似性计算方法5.2.1连续型属性的相似性计算方法5.2.2二值离散型属性的相似性计算方法5.2.3多值离散型属性的相似性计算方法5.2.4混合类型属性的相似性计算方法165.2相似性计算方法5.2.1连续型属性的相似性计算方法5.2.2二值离散型属性的相似性计算方法5.2.3多值离散型属性的相似性计算方法5.2.4混合类型属性的相似性计算方法175.2.1连续型属性的相似性计算方法假设两个样本Xi和Xj分别表示成如下形式：Xi=(xi1,xi2,…,xid)Xj=(xj1,xj2,…,xjd)它们都是d维的特征向量，并且每维特征都是一个连续型数值。对于连续型属性，样本之间的相似性通常采用如下三种距离公式进行计算。18欧氏距离（Euclideandistance）曼哈顿距离（Manhattandistance）闵可夫斯基距离（Minkowskidistance）d1k2jkikji)xx()x,x(dd1kjkikjixx)x,x(dq/1d1kqjkikji)xx()x,x(d5.2.1连续型属性的相似性计算方法q=2q=1195.2.1连续型属性的相似性计算方法Euclidean距离和Manhattan距离的性质：d(i,j)0d(i,i)=0d(i,j)=d(j,i)d(i,j)d(i,k)+d(k,j)205.2.1连续型属性的相似性计算方法欧式距离的示例01230123456p1p2p3p4pointxyp102p220p331p451DistanceMatrixp1p2p3p4p102.8283.1625.099p22.82801.4143.162p33.1621.41402p45.0993.16220215.2.1连续型属性的相似性计算方法曼哈顿距离的示例01230123456p1p2p3p4pointxyp102p220p331p451DistanceMatrixp1p2p3p4p10446p24024p34202p46420225.2相似性计算方法5.2.1连续型属性的相似性计算方法5.2.2二值离散型属性的相似性计算方法5.2.3多值离散型属性的相似性计算方法5.2.4混合类型属性的相似性计算方法235.2.2二值离散型属性的相似性计算方法二值离散型属性只有0和1两个取值。其中：0表示该属性为空，1表示该属性存在。例如：描述病人的是否抽烟的属性(smoker)，取值为1表示病人抽烟，取值0表示病人不抽烟。假设两个样本Xi和Xj分别表示成如下形式：Xi=(xi1,xi2,…,xip)Xj=(xj1,xj2,…,xjp)它们都是p维的特征向量，并且每维特征都是一个二值离散型数值。245.2.2二值离散型属性的相似性计算方法假设二值离散型属性的两个取值具有相同的权重，则可以得到一个两行两列的可能性矩阵。a=thenumberofattributeswhereXiwas1andXjwas1;b=thenumberofattributeswhereXiwas1andXjwas0;c=thenumberofattributeswhereXiwas0andXjwas1;d=thenumberofattributeswhereXiwas0andXjwas0.1010sumababcdcdsumacbdpXjXi255.2.2二值离散型属性的相似性计算方法如果样本的属性都是对称的二值离散型属性，则样本间的距离可用简单匹配系数(SimpleMatchingCoefficients,SMC)计算：SMC=(b+c)/(a+b+c+d)其中：对称的二值离散型属性是指属性取值为1或者0同等重要。例如：性别就是一个对称的二值离散型属性，即：用1表示男性，用0表示女性；或者用0表示男性，用1表示女性是等价的，属性的两个取值没有主次之分。265.2.2二值离散型属性的相似性计算方法如果样本的属性都是不对称的二值离散型属性，则样本间的距离可用Jaccard系数计算(JaccardCoefficients,JC)：JC=(b+c)/(a+b+c)其中：不对称的二值离散型属性是指属性取值为1或者0不是同等重要。例如：血液的检查结果是不对称的二值离散型属性，阳性结果的重要程度高于阴性结果，因此通常用1来表示阳性结果，而用0来表示阴性结果。27例：已知两个样本p=[1000000000]和q=[0000001001]a=0(thenumberofattributeswherepwas1andqwas1)b=1(thenumberofattributeswherepwas1andqwas0)c=2(thenumberofattributeswherepwas0andqwas1)d=7(thenumberofattributeswherepwas0andqwas0)5.2.2二值离散型属性的相似性计算方法28SMC=(b+c)/(a+b+c+d)=(1+2)/(0+1+2+7)=0.3JC=(b+c)/(a+b+c)=(1+2)/(0+1+2)=15.2.2二值离散型属性的相似性计算方法295.2相似性计算方法5.2.1连续型属性的相似性计算方法5.2.2二值离散型属性的相似性计算方法5.2.3多值离散型属性的相似性计算方法5.2.4混合类型属性的相似性计算方法305.2.3多值离散型属性的相似性计算方法多值离散型属性是指取值个数大于2的离散型属性。例如：成绩可以分为优、良、中、差。假设一个多值离散型属性的取值个数为N，给定数据集X={xi|i=1,2,…,total}。其中：每个样本xi可用一个d维特征向量描述，并且每维特征都是一个多值离散型属性，即：xi=(xi1,xi2,…,xid)。每维特征都是一个多值离散型属性。315.2.3多值离散型属性的相似性计算方法问题：给定两个样本xi=(xi1,xi2,…,xid)和xj=(xj1,xj2,…,xjd)，如何计算它们之间的距离？方法一：简单匹配方法。方法二：先将多值离散型属性转换成多个二值离散型属性，然后再使用Jaccard系数计算样本之间的距离。325.2.3多值离散型属性的相似性计算方法问题：给定两个样本xi=(xi1,xi2,…,xid)和xj=(xj1,xj2,…,xjd)，如何计算它们之间的距离？方法一：简单匹配方法。距离计算公式如下：其中：d为数据集中的属性个数，u为样本xi和xj取值相同的属性个数。dud)x,x(dji335.2.3多值离散型属性的相似性计算方法问题：给定两个样本xi=(xi1,xi2,…,xid)和xj=(xj1,xj2,…,xjd)，如何计算它们之间的距离？方法一：简单匹配方法。d(x1,x2)=(3-1)/3≈0.667样本序号年龄段学历收入x1青年研究生高x2青年本科低x3老年本科以下中x4中年研究生高345.2.3多值离散型属性的相似性计算方法问题：给定两个样本xi=(xi1,xi2,…,xid)和xj=(xj1,xj2,…,xjd)，如何计算它们之间的距离？方法一：简单匹配方法。d(x1,x3)=(3-0)/3=1样本序号年龄段学历收入x1青年研究生高x2青年本科低x3老年本科以下中x4中年研究生高355.2.3多值离散型属性的相似性计算方法问题：给定两个样本xi=(xi1,xi2,…,xid)和xj=(xj1,xj2,…,xjd)，如何计算它们之间的距离？方法一：简单匹配方法。d(x1,x4)=(3-2)/3≈0.333