浙大数据挖掘7聚类分析.pptx

聚类分析什么是聚类分析？聚类（簇）：数据对象的集合在同一个聚类（簇）中的对象彼此相似不同簇中的对象则相异聚类分析将物理或抽象对象的集合分组成为由类似的对象组成的多个类的过程聚类是一种无指导的学习：没有预定义的类编号聚类分析的数据挖掘功能作为一个独立的工具来获得数据分布的情况作为其他算法（如：特征和分类）的预处理步骤聚类分析的典型应用模式识别空间数据分析在GIS系统中，对相似区域进行聚类，产生主题地图检测空间聚类，并给出它们在空间数据挖掘中的解释图像处理商务应用中，帮市场分析人员发现不同的顾客群万维网对WEB上的文档进行分类对WEB日志的数据进行聚类，以发现相同的用户访问模式什么是好的聚类分析？一个好的聚类分析方法会产生高质量的聚类高类内相似度低类间相似度作为统计学的一个分支，聚类分析的研究主要是基于距离的聚类；一个高质量的聚类分析结果，将取决于所使用的聚类方法聚类方法的所使用的相似性度量和方法的实施方法发现隐藏模式的能力数据挖掘对聚类分析的要求 (1)可扩展性(Scalability)大多数来自于机器学习和统计学领域的聚类算法在处理数百条数据时能表现出高效率处理不同数据类型的能力数字型；二元类型，分类型/标称型，序数型,比例标度型等等发现任意形状的能力基于距离的聚类算法往往发现的是球形的聚类，其实现实的聚类是任意形状的用于决定输入参数的领域知识最小化对于高维数据，参数很难决定，聚类的质量也很难控制处理噪声数据的能力对空缺值、离群点、数据噪声不敏感数据挖掘对聚类分析的要求 (2)对于输入数据的顺序不敏感同一个数据集合，以不同的次序提交给同一个算法，应该产生相似的结果高维性高维的数据往往比较稀松，而且高度倾斜基于约束的聚类找到既满足约束条件，又具有良好聚类特性的数据分组可解释性和可用性聚类要和特定的语义解释和应用相联系聚类分析中的数据类型许多基于内存的聚类算法采用以下两种数据结构数据矩阵：用p个变量来表示n个对象也叫二模矩阵，行与列代表不同实体相异度矩阵：存储n个对象两两之间的临近度也叫单模矩阵，行和列代表相同的实体相异度计算许多聚类算法都是以相异度矩阵为基础，如果数据是用数据矩阵形式表示，则往往要将其先转化为相异度矩阵。相异度d(i,j)的具体计算会因所使用的数据类型不同而不同，常用的数据类型包括：区间标度变量二元变量标称型、序数型和比例标度型变量混合类型的变量区间标度变量区间标度度量是一个粗略线性标度的连续度量，比如重量、高度等选用的度量单位将直接影响聚类分析的结果，因此需要实现度量值的标准化，将原来的值转化为无单位的值，给定一个变量f的度量值，可使用以下方法进行标准化：计算平均的绝对偏差其中计算标准化的度量值(z-score)使用平均的绝对偏差往往比使用标准差更具有健壮性对象间的相似度和相异度(1)对象间的相似度和相异度是基于两个对象间的距离来计算的Euclidean距离i=(xi1,xi2,…,xip)和j=(xj1,xj2,…,xjp)是两个p维数据对象Manhattan距离对象间的相似度和相异度(2)Manhattan距离和Euclidean距离的性质d(i,j) ? 0d(i,i) = 0d(i,j) = d(j,i)d(i,j) ? d(i,k) + d(k,j)Minkowski距离上式中，q为正整数，如果q=1则表示Manhattan距离，如果q=2则表示Euclidean距离二元变量 (1)一个二元变量只有两种状态：0或1；e.g. smoker来表示是否吸烟一个对象可以包含多个二元变量。二元变量的可能性表：如何计算两个二元变量之间的相似度？Object jObject i二元变量 (2)对称的 VS. 不对称的 二元变量对称的二元变量指变量的两个状态具有同等价值，相同权重；e.g. 性别基于对称的二元变量的相似度称为恒定的相似度，可以使用简单匹配系数评估它们的相异度：不对称的二元变量中，变量的两个状态的重要性是不同的；e.g. HIV阳性 VS HIV阴性基于不对称的二元变量的相似度称为非恒定的相似度，可以使用Jaccard系数评估它们的相异度二元变量的相异度——示例P228 例8.1 二元变量之间的相异度 （病人记录表）Name是对象标识gender是对称的二元变量其余属性都是非对称的二元变量如过Y和P（positive阳性）为1，N为0，则：标称变量标称变量是二元变量的推广，它可以具有多于两个的状态值。比如：红、绿、蓝、黄。对于标称型变量，值之间的排列顺序是不重要的。计算标称变量所描述的对象（一个对象可以包含多个标称变量）i和j之间的相异度方法一：简单匹配方法m: 匹配的数目，即对象i和j取值相同的变量的数目 (也可加上权重)方法二：对M个标称状态中的每个状态创建一个新的二元变量，并用非对称的二元变量