聚类分析
聚类分析
什么是聚类分析? 聚类(簇):数据对象的集合 a在同一个聚类(簇)中的对象彼此相似 口不同簇中的对象则相异 聚类分析 a将物理或抽象对象的集合分组成为由类似的对象组成的多个 类的过程 聚类是一种无指导的学习:没有预定义的类编号 ■聚类分析的数据挖掘功能 ¤作为一个独立的工具来获得数据分布的情况 口作为其他算法(如:特征和分类)的预处理步骤
什么是聚类分析？ ◼ 聚类（簇）：数据对象的集合 ❑ 在同一个聚类（簇）中的对象彼此相似 ❑ 不同簇中的对象则相异 ◼ 聚类分析 ❑ 将物理或抽象对象的集合分组成为由类似的对象组成的多个 类的过程 ◼ 聚类是一种无指导的学习：没有预定义的类编号 ◼ 聚类分析的数据挖掘功能 ❑ 作为一个独立的工具来获得数据分布的情况 ❑ 作为其他算法（如：特征和分类）的预处理步骤
聚类分析的典型应用 模式识另 空间数据分析 a在G|S系统中,对相似区域进行聚类,产生主题地图 ¤检测空间聚类,并给出它们在空间数据挖掘中的解释 口图像处理 经济学(尤其是市场研究) 万维网 口对WEB上的文档进行分类 口劝WEB日志的数据进行聚类,以发现相同的用户访问模式
聚类分析的典型应用 ◼ 模式识别 ◼ 空间数据分析 ❑ 在GIS系统中，对相似区域进行聚类，产生主题地图 ❑ 检测空间聚类，并给出它们在空间数据挖掘中的解释 ❑ 图像处理 ◼ 经济学（尤其是市场研究） ◼ 万维网 ❑ 对WEB上的文档进行分类 ❑ 对WEB日志的数据进行聚类，以发现相同的用户访问模式
聚类分析应用实例 ■市场营销:帮市场分析人员从客户基本库中发现不同 的客户群,从而可以对不同的客户群采用不同的营销 策略 土地使用:在地球监测数据库中,发现相同的土地使 用区域 保险业:发现汽车保险中索赔率较髙的客户群 ■城市规划:根据房子的类型、价值和地理位置对其进 行分组 地震研究:将观测到的震中点沿板块断裂带进行聚类, 得出地震高危区
聚类分析应用实例 ◼ 市场营销：帮市场分析人员从客户基本库中发现不同 的客户群，从而可以对不同的客户群采用不同的营销 策略 ◼ 土地使用：在地球监测数据库中，发现相同的土地使 用区域 ◼ 保险业：发现汽车保险中索赔率较高的客户群 ◼ 城市规划：根据房子的类型、价值和地理位置对其进 行分组 ◼ 地震研究：将观测到的震中点沿板块断裂带进行聚类， 得出地震高危区
什么是好的聚类分析? 个好的聚类分析方法会产生高质量的聚类 a高类内相似度 a低类间相似度 作为统计学的一个分支,聚类分析的研究主要 是基于距离的聚类;一个高质量的聚类分析结 果,将取决于所使用的聚类方法 a聚类方法的所使用的相似性度量和方法的实施 ¤方法发现隐藏模式的能力
什么是好的聚类分析？ ◼ 一个好的聚类分析方法会产生高质量的聚类 ❑ 高类内相似度 ❑ 低类间相似度 ◼ 作为统计学的一个分支，聚类分析的研究主要 是基于距离的聚类；一个高质量的聚类分析结 果，将取决于所使用的聚类方法 ❑ 聚类方法的所使用的相似性度量和方法的实施 ❑ 方法发现隐藏模式的能力
数据挖掘对聚类分析的要求(1) 可扩展性( Scalability) 口大多数来自于机器学习和统计学领域的聚类算法在处理数百 条数据时能表现出高效率 处理不同数据类型的能力 ¤数字型;二元类型,分类型/标称型,序数型,比例标度型等 ■发现任意形状的能力 口基于距离的聚类算法往往发现的是球形的聚类,其实现实的 聚类是任意形状的 用于决定输入参数的领域知识最小化 ¤对于高维数据,参数很难决定,聚类的质量也很难控制 处理噪声数据的能力 口对空缺值、孤立点、数据噪声不敏感
数据挖掘对聚类分析的要求 (1) ◼ 可扩展性(Scalability) ❑ 大多数来自于机器学习和统计学领域的聚类算法在处理数百 条数据时能表现出高效率 ◼ 处理不同数据类型的能力 ❑ 数字型；二元类型，分类型/标称型，序数型,比例标度型等 等 ◼ 发现任意形状的能力 ❑ 基于距离的聚类算法往往发现的是球形的聚类，其实现实的 聚类是任意形状的 ◼ 用于决定输入参数的领域知识最小化 ❑ 对于高维数据，参数很难决定，聚类的质量也很难控制 ◼ 处理噪声数据的能力 ❑ 对空缺值、孤立点、数据噪声不敏感
数据挖掘对聚类分析的要求(2) 对于输入数据的顺序不敏感 口同一个数据集合,以不同的次序提交给同一个算法, 应该产生相似的结果 高维度 口高维度的数据往往比较稀松,而且高度倾斜 基于约束的聚类 ¤找到既满足约束条件,又具有良好聚类特性的数据 分组 可解释性和可用性 口聚类要和特定的语义解释和应用相联系
数据挖掘对聚类分析的要求 (2) ◼ 对于输入数据的顺序不敏感 ❑ 同一个数据集合，以不同的次序提交给同一个算法， 应该产生相似的结果 ◼ 高维度 ❑ 高维度的数据往往比较稀松，而且高度倾斜 ◼ 基于约束的聚类 ❑ 找到既满足约束条件，又具有良好聚类特性的数据 分组 ◼ 可解释性和可用性 ❑ 聚类要和特定的语义解释和应用相联系
聚类分析中的数据类型 许多基于内存的聚类「x1…x…xm 算法采用以下两种数 据结构 口数据矩阵:用p个变量 来表示n个对象 nl n 也叫二模矩阵,行与列 代表不同实体 口相异度矩阵:存储n个 d(2,D)0 对象两两之间的近似性 dl(3,1)d(3,2)0 ■也叫单模矩阵,行和列 代表相同的实体 d(n,1)d(n,2)
聚类分析中的数据类型 ◼ 许多基于内存的聚类 算法采用以下两种数 据结构 ❑ 数据矩阵：用p个变量 来表示n个对象 ◼ 也叫二模矩阵，行与列 代表不同实体 ❑ 相异度矩阵：存储n个 对象两两之间的近似性 ◼ 也叫单模矩阵，行和列 代表相同的实体 np ... x nf ... x n1 x ... ... ... ... ... i p ... x i f ... x i 1 x ... ... ... ... ... 1p ... x 1f ... x 11 x ( ,1) ( ,2) ... 0 : : : ) (3,2) d n d n ... d(3,1 d 0 d(2,1) 0 0
相异度计算 许多聚类算法都是以相异度矩阵为基础,如果 数据是用数据矩阵形式表示,则往往要将其先 转化为相异度矩阵。 相异度()的具体计算会因所使用的数据类型 不同而不同,常用的数据类型包括: 口区间标度变量 口二元变量 ¤标称型、序数型和比例标度型变量 口混合类型的变量
相异度计算 ◼ 许多聚类算法都是以相异度矩阵为基础，如果 数据是用数据矩阵形式表示，则往往要将其先 转化为相异度矩阵。 ◼ 相异度d(i,j)的具体计算会因所使用的数据类型 不同而不同，常用的数据类型包括： ❑ 区间标度变量 ❑ 二元变量 ❑ 标称型、序数型和比例标度型变量 ❑ 混合类型的变量
区间标度变量 区间标度度量是一个粗略线性标度的连续度量,比如重量、高度 选用的度量单位将直接影响聚类分 果,因此需要实现廈量 看的标法化,将原来的值转化为无 值,给定一个变量f度 量值,可使用以下转化 口计算平均的绝对偏差 n(x-m, 1+1x2/ -m, 1++1x -m, D 其中 m1=(x1;+x xs 口计算标准化的度量值(z- score) -m 使用平均的绝对偏差往往比使用标准差更具有健壮性
区间标度变量 ◼ 区间标度度量是一个粗略线性标度的连续度量，比如重量、高度 等 ◼ 选用的度量单位将直接影响聚类分析的结果，因此需要实现度量 值的标准化，将原来的值转化为无单位的值，给定一个变量f的度 量值，可使用以下转化： ❑ 计算平均的绝对偏差 ❑ 其中 ❑ 计算标准化的度量值(z-score) ◼ 使用平均的绝对偏差往往比使用标准差更具有健壮性 ... ). 1 2 1 f f f nf (x x x n m = + + + 1(| | | | ... | |) f 1f f 2 f f nf mf x m x m x n s = − + − + + − f if f if s x m z − =