第5章 聚类分析.ppt

聚类分析 根据同类事物应具有相近特性 而不同事物在这些特性上差异较大的假定 将所研究的事务进行分类 这种研究方法被称为聚类cluster 聚类分析是在没有或不用样本所属类别信息的情况下 依据样本集数据的内在结构 在样本间相似性度量的基础上对样本进行分类的方法 聚类分析 分类与聚类的区别分类 用已知类别的样本训练集来设计分类器 有监督 聚类 用事先不知样本的类别 而利用样本的先验知识来构造分类器 无监督学习 有监督学习是让计算机去学习我们已经建立好的分类系统 无监督学习看起来非常困难 目标是我们不告诉计算机怎么做 而是让它 计算机 自己去学习怎样做一些事情 主要步骤 1 数据预处理 2 为衡量数据点间的相似度定义一个距离函数 3 聚类或分组 4 评估输出 数据预处理包括选择数量 类型和特征的标度 它依靠特征选择和特征抽取 特征选择选择重要的特征 特征抽取把输入的特征转化为一个新的显著特征 它们经常被用来获取一个合适的特征集来为避免 维数灾 进行聚类 数据预处理还包括将孤立点移出数据 孤立点是不依附于一般数据行为或模型的数据 因此孤立点经常会导致有偏差的聚类结果 因此为了得到正确的聚类 我们必须将它们剔除 既然类似性是定义一个类的基础 那么不同数据之间在同一个特征空间相似度的衡量对于聚类步骤是很重要的 由于特征类型和特征标度的多样性 距离度量必须谨慎 它经常依赖于应用 例如 通常通过定义在特征空间的距离度量来评估不同对象的相异性 很多距离度都应用在一些不同的领域 一个简单的距离度量 如Euclidean距离 经常被用作反映不同数据间的相异性 一些有关相似性的度量 例如PMC和SMC 能够被用来特征化不同数据的概念相似性 在图像聚类上 子图图像的误差更正能够被用来衡量两个图形的相似性 将数据对象分到不同的类中是一个很重要的步骤 数据基于不同的方法被分到不同的类中 划分方法和层次方法是聚类分析的两个主要方法 划分方法一般从初始划分和最优化一个聚类标准开始 CrispClustering 它的每一个数据都属于单独的类 FuzzyClustering 它的每个数据可能在任何一个类中 CrispClustering和FuzzyClusterin是划分方法的两个主要技术 划分方法聚类是基于某个标准产生一个嵌套的划分系列 它可以度量不同类之间的相似性或一个类的可分离性用来合并和分裂类 其他的聚类方法还包括基于密度的聚类 基于模型的聚类 基于网格的聚类 评估聚类结果的质量是另一个重要的阶段 聚类是一个无管理的程序 也没有客观的标准来评价聚类结果 一般来说 几何性质 包括类间的分离和类内部的耦合 一般都用来评价聚类结果的质量 聚类图示 聚类中没有任何指导信息 完全按照数据的分布进行类别划分 分类图示 训练数据 待分类数据 什么是聚类分析 聚类分析仅根据在数据中发现的描述对象及其关系的信息 将数据对象分组 其目标是 组内的对象相互之间是相似的 二不同组中的对象是不同的 聚类分析的应用 商业将顾客划分成若干个组 以便进一步分析和开展营销活动 信息检索万维网包含数以亿计的web网页 搜索引擎可能返回数以千计的页面 可以使用聚类将搜索结果分成若干个簇 每个簇捕获查询的某个特定方面 例如一个电影查询可以返回诸如评论 新片预告 影星和电影院等 实际应用 为什么需要聚类 对相似的文档或超链接进行聚类 由于类别数远小于文档数 能够加快用户寻找相关信息的速度 聚类分析原理介绍 什么是自然分组结构Naturalgrouping 我们看看以下的例子 有16张牌如何将他们分为一组一组的牌呢 聚类分析原理介绍 分成四组每组里花色相同组与组之间花色相异 花色相同的牌为一副Individualsuits 聚类分析原理介绍 分成四组符号相同的牌为一组 符号相同的的牌Likefacecards 聚类分析原理介绍 分成两组颜色相同的牌为一组 颜色相同的配对Blackandredsuits 聚类分析原理介绍 这个例子告诉我们 分组的意义在于我们怎么定义并度量 相似性 Similar因此衍生出一系列度量相似性的算法 聚类分析中的数据类型 1 数据结构 1 数据矩阵 DataMatrix 数据矩阵用p个变量 也称为度量或属性 来表示n个对象 这种数据结构是关系表的形式 或者看成n p n个对象 p个变量 的矩阵 2 相异度矩阵 DissimilarityMatrix 相异度矩阵存储n个对象两两之间的近似性 表现形式是一个n n维的矩阵 在此 d i j 是对象i和对象j之间相异性的量化表示 通常是一个非负的数值 当对象i和j越相似或 接近 时 其值越接近0 两个对象越不同 其值越大 而且d i j d j i d i i 0 相异度计算 区间标度变量是一个粗略线性标度的连续度量 典型的例子包括重量和高度 经度和纬度坐标以及大气温度等 区间标度变量对象间的相异度d i j 是基于对象间的距离来计算的 最常用的距离度量方法是欧几里得距离 曼哈坦距离 明考斯基距离 欧几里得距离的定义如下 这里的和是数据对象i j的m个属性值 曼哈坦距离的定义如下 以上的d i j 都满足如下的数学要求 1 非负性 d i j 0 是一个非负的数值 2 一个对象与自身的距离是0 即d i i 0 3 对称性 d i j d j i 4 三角不等式 d i j d i k d k j 表示从对象i到对象j的直接距离不会大于途经任何其他对象k的距离 明考斯基距离是欧几里德距离和曼哈坦距离的概化 它的定义如下 这里的q是一个正整数 当q 1时 表示曼哈坦距离 当q 2时表示欧几里德距离 1 区间标度变量 2 聚类分析中的相似度 二元变量 对称的二元变量 如果它的两个状态是同等价值的 并有相同的权重 那么该二元变量是对称的 如属性 性别 在这种条件下 评价两个对象之间相似度的最著名的系数是简单匹配系数 其定义如下 d i j a d a b c d 如果两个状态的输出不是同样重要 那么该二元变量是不对称的 例如一个疾病检查的肯定和否定的结果 根据惯例 我们将比较重要的输出结果 通常也是出现几率较小的结果编码为1 如 HIV阳性 二将另一种结果编码为0 例如 HIV阴性 给定两个不对称的二元变量 两个都取值1的情况被认为比两个都取值0的情况更有意义 因此 这样的二元变量经常被认为好像只有一个状态 这种变量的相似度评价系数是Jaccard系数 即d i j a a b c 如下的表包含了属性name gender trait 1 trait 2 trait 3和trait 4 这里的name是对象的id gender是一个对称的属性 剩余的trait属性是不对称的 描述了希望找到笔友的人的个人特点 假设有一个服务是适合发现合适的笔友 Namegendertrait 1trait 2trait 3trait 4KevanMNPPNCarolineFNPPNErikMPNNP对不对称的属性值 值P为1 N为0假设对象 潜在笔友 间的距离是只根据不对称变量来计算的 1 计算对象间的简单匹配系数2 计算对象间的Jaccard系数3 你认为哪两个人将成为笔友 哪两个会是最不相容的 簇的例子 StarPower 1910Hertzsprung Russell 发光度与温度之间的关系 80 通过原子核聚变由氢转化为氮产生能量 三个簇代表了在恒星生存周期中星体所处的完全不同的阶段 在每个簇中发光度和温度的关系是一致的 但各簇间的关系并不相同 因为它们产生热和光的过程根本不同 落在主序列上的80 的星星是通过原子核聚变由氢转化为氦产生能量的 这就是所有的星星都要经历的一个活跃的周期 几十亿年后 氢原子会消耗殆尽 依据其质量的差异 星体或者开始利用氦进行聚变 或者聚变就此停止 在后一种情况中 星星的核心部分就会崩溃 这个过程中会产生大量的热 与此同时 外层气体在远离核心处膨胀 形成一个巨大的火球 最终 外层气体剥离 残留的星核开始冷却 星球变成一个白色的矮星 簇算法 K 均值 K 均值簇 划分簇的方法每个簇与一个质心相联系每个点被分到与其质心最近的那个质心所在的簇中簇数K必须被指定基本的算法非常简单 K 均值簇 两个不同的K 均值簇 次最优簇 最优簇 最初的点 初始质心的重要性 初始质心的重要性 评价簇 什么样的簇是好的 衡量簇内相似程度的一个标准度量是方差 簇内的每一个成员与均值之差的平方和 因此 最佳簇可能是有最低方差的那一组 但这个度量没有考虑簇的大小 一个类似的度量可能是平均方差 即总的方差除以簇的大小 假设数据对象集合S如表所示 作为一个聚类分析的二维样本 要求的簇的数量k 2 1 选择O1 0 2 O2 0 0 为初始的簇中心 2 对剩余的每个对象 根据其与各个簇中心的距离 采用欧氏距离 将它赋给最近的簇 对O3 显然 故将O3分配给C2 同理 将O4分配给C2 O5分配给C1 更新 得到新簇C1 O1 O5 和C2 O2 O3 O4 计算平方误差准则 单个方差是 E1和E2总体平方误差是 E E1 E2 3 计算新的簇的质心M1 0 5 2 2 2 2 2