第6章 聚类分析.ppt

2020 1 1 数据仓库与数据挖掘 1 第6章数据聚类 2 数据分类 在已知类标号的训练集基础上进行分类器设计工作的 所以分类方法又称为监督学习方法 聚类分析 又称为非监督学习方法 使用的数据集样本没有类标号 聚类分析方法可以将数据集划分为多个类别 由此可以给每个样本标注类标号 聚类之后的数据集可以直接用来进行科学分析 也可以作为其他方法的训练集 3 6 1引例表6 1给出了一个聚类分析的示例数据集 其中包含两个描述属性 不包含类别属性 聚类分析的任务是将这7个数据样本划分为多个聚类 即将相似度较高的样本归为一个类别 例如 对于表6 1中的数据集 可以使用样本之间的距离来表示相似度 两个样本之间的距离越近 它们属于一个聚类的可能性就越大 表6 1聚类分析示例数据集 4 聚类分析是将物理的或者抽象的数据集合射分为多个类别的过程 聚类之后的每个类别中任意两个数据样本之间具有较高的相似度 而不同类别的数据样本之间具有较低的相似度 相似度可以根据数据样本的描述属性的具体取值来计算 通常采用数据样本间的距离来表示 聚类分析中使用的数据集表示为x xi i 1 2 total 其中数据样本xi i 1 2 total 用d维特征向量xi xi1 xi2 xid 来表示 xi1 xi2 xid分别对应d个描述属性a1 a2 ad的具体取值 描述属性可以是连续型属性 如表6 1所示 离散型属性或者混合型属性 此外 不同类型描述属性的相似度的计算方法不同 5 6 2聚类分析概述聚类分析是数据挖掘应用的主要技术之一 它可以作为一个独立的工具来使用 将未知类标号的数据集划分为多个类别之后 观察每个类别中数据样本的特点 并且对某些特定的类别作进一步的分析 聚类分析还可以作为其他数据挖掘技术 例如分类学习 关联规则挖掘等 的预处理工作 聚类分析在科学数据分析 商业 生物学 医疗诊断 文本挖掘和web数据挖掘等领域都有广泛应用 6 对聚类分析的要求有以下几个方面 1 可伸缩性 在以往的应用中 聚类分析方法所处理的数据集都是小数据集 而且比较有效 面对大数据集 聚类分析方法对数据集的划分结果可能会与理想的划分存在着偏差 因此 对数据集的处理具有良好的可伸缩性是聚类分析的重要研究内容 2 处理不同类型属性的能力 聚类分析中的许多算法都是针对具有连续型描述属性的数据集设计的 聚类算法可以处理不同类型属性的数据集 例如连续型属性 二值离散型属性 多值 大于2 离散型属性和混合类型属性等 3 发现任意形状聚类的能力 许多聚类算法是基于欧氏距离和曼哈顿距离度量来计算数据样本之间的相似度的 基于这样的距离度量的算法倾向于将数据集划分为相近大小和密度的球形聚类 能够划分任意形状数据集的聚类方法是非常重要的 7 4 减小对先验知识和用户自定义参数的依赖性 许多聚类算法要求用户事先确定一些参数 如希望将数据集划分的类别数 选择数据集的初始划分方式等 减小对先验知识和用户自定义参数的依赖性 可以减轻用户进行参数设置的负担 也使得对聚类性能的控制相对容易 5 处理噪声数据的能力 大多数数据库或者数据仓库中都包含孤立点 缺失值和错误的数据 噪声数据会干扰许多聚类算法的聚类性能 导致低质量的数据集划分 6 可解释性和实用性 用户往往希望聚类结果是可解释的 可理解的并且是可用的 从而可以根据聚类结果进行研究和分析 在低维情况下 可以借助于可视化手段来展示聚类结果 在高维情况下 聚类结果很难被可视化 这时对数据降低维度会有所帮助 8 通常聚类算法可以分为以下几类 1 划分聚类方法 对于给定的数据集 划分聚类方法通过选择适当的初始代表点将数据样本进行初始聚类 之后通过迭代过程对聚类的结果进行不断的调整 直到使评价聚类性能的准则函数的值达到最优为止 2 层次聚类方法 层次聚类方法将给定数据集分层进行划分 形成一个以各个聚类为结点的树型结构 层次聚类方法分为自底向上 凝聚型层次聚类 和自顶向下 分解型层次聚类 两种方式 3 基于密度的聚类方法 基本原理 当临近区域的数据密度大于某个阈值时 就不断进行聚类 直到密度小于给定阈值为止 也就是说 每一个类别被看作一个数据区域 对于某个特定类别中的任一数据样本 在给定的范围内必须包含大于给定值的数据样本 基于密度的聚类方法可以用来去除噪声样本 形成的聚类形状也可以是任意的 9 4 基于网格的聚类方法 基于网格的聚类方法将原始的数据空间量化为有限数目的单元 并且由这些单元形成网格结构 所有的聚类操作都要在这个网格结构上进行 基于同格的聚类方法的处理速度较快 其处理时间与数据样本的数量无关 而是与量化空间中每一维上的单元数目有关 聚类分析已经被广泛地研究了许多年 主要集中在基于距离和相似度的算法方面 其中划分聚类方法k means和层次聚类方法已经被加入到许多统计分析工具的软件包中 作为专门的聚类分析工具来使用 本章主要介绍划分聚类方法k means和层次聚类方法的原理和算法步骤 并进行实例说明 10 聚类分析方法将给定的数据集合划分为多个类别 其中每个类别中任意两个数据样本之间具有较高的相似度 而不同类别的数据样本之间具有较低的相似度 数据样本之间的相似度通常用样本间的距离来表示 而距离是通过数据样本的描述属性的具体取值来计算的 在不同的应用领域中 数据样本的描述属性的类型可能不同 因此相似度的计算方法也不同 下面分别介绍当描述属性为连续型属性 二值离散型属性 多值离散型属性以及混合类型属性时 数据样本之间的相似度计算方法 11 6 3 1连续型属性的相似度计算方法连续型属性是指取值为连续值的属性 例如年龄 收入和距离等都是连续型属性 假设给定的数据集为x xm m 1 2 total x中的样本用d个描述属性a1 a2 ad来表示 并且d个描述属性都是连续型属性 数据样本xi xi1 xi2 xid xj xj1 xj2 xjd 其中 i1 xi2 xid和xj1 xj2 xjd分别是样本xi和xj对应d个描述属性a1 a2 ad的具体取值 样本xi和xj之间的相似度通常用它们之间的距离d xi xj 表示 距离越小 样本xi和xj越相似 距离越大 样本xi和xj越不相似 用连续型属性表示的数据样本xi和xj之间的距离d xi xj 的计算方法通常有如下3种方式 12 2 曼哈顿距离 manhattandistance 如公式 6 2 所示 3 明考斯基距离 minkowskidistarice 是欧氏距离和曼哈顿距离的一个推广 1 欧氏距离 euclideandistance 如公式 6 1 所示 当q的值为1时 明考斯基距离变为曼哈顿距离 当q的值为2时 明考斯基距离变为欧氏距离 13 上述三种距离满足如下的数学性质 1 d xi xj 0 即数据样本之间的距离是非负值 2 d xi xj 0 即数据样本与自身的距离为0 表示样本与自身之间的相似性最大 3 d xi xj d xj xi 即数据样本之间的距离是对称的 计算xi和xj之间的距离等价于计算xj和xi之间的距离 4 d xi xj d xi xk d xk xj 即数据样本之间的距离满足三角不等式的性质 连续型属性可以用多种度量单位来表示 不同的度量单位会导致不同的聚类结果 度量单位越小 描述属性可能的值域就越大 对距离计算的影响越大 从而对聚类结果的影响也越大 度量单位越大 描述属性可能的值域就越小 对距离计算的影响越小 从而对聚类结果的影响也相应减小 14 6 3 2二值离散型属性的相似度计算方法二值离散型属性是指只有两种取值的离散型属性 通常用1代表属性的一种取值 用0代表属性的另一种取值 假设给定的数据集为x xm m l 2 total x中的数据样本用d个描述属性a1 a2 ad来表示 并且d个描述属性都是二值离散型属性 数据样本xi xil xi2 xid xj xjl xj2 xjd 其中xi1 xi2 xid和xjl xj2 xjd的值是0或1 xi和xj之间的距离d xi xj 按照如下的步骤来计算 首先 统计两个数据样本的各个二值离散型属性的取值情况 xi和xj的各属性的取值情况如表6 2所示 15 在表6 2中 a11表示样本xi和xj取值同时为1的二值离散型属性个数 a10表示样本xi取值为1而样本xi取值为0的二值离散型属性个数 a01表示样本xi取值为0而样本xj取值为1的二值离散型属性个数 a00表示样本xi和xj取值同时为0的二值离散型属性个数 a11 a10 a01 a00的值等于数据集中的属性的总个数d 其次 根据数据样本的二值离散型属性的取值情况计算样本之间的距离d xi xj 需要说明的是 对称的二值离散型属性和不对称的二值离散型属性的d xi xj 的计算方法不同 下面分别进行介绍 1 对称的二值离散型属性是指其取值为1或0时同等重要 例如性别就是对称的二值离散型属性 用l表示性别为男 用0表示性别为女 或者用0 表示性别为男 用1表示性别为女都是等价的 两种取值没有主次之分 对于这种属性 d xi xj 的计算公式为 16 2 不对称的二值离散型属性是指其取值为1或0时不是同等重要 例如血液的检测结果是不对称的二值离散型属性 阳性结果的重要程度要远远高于阴性结果 通常用1来表示重要的属性取值 例如阳性 而用0来表示另一种取值 例如阴性 对于这种属性 d xi xj 的计算公式为 在公式 6 5 等号右边的分母中没有a00 这是因为样本xi和xj取值同时为0的情况被认为不重要 不必参与相似度的计算 17 6 3 3多值离散型属性的相似度计算方法多值离散型属性是指取值个数大于2的离散型属性 例如 年龄段可以分为老年 中年 青年 收入可以分为高 中 低 信誉度可以分为优 良 差等 假设一个多值离散型属性的取值个数为n 其中的每种取值可以用字母 符号或者整数集合来表示 假设给定的数据集为x xm m 1 2 total x中的样本用d个描述属性a1 a2 ad来表示 并且d个描述属性都是多值离散型属性 样本xi xi1 xi2 xid 和xj xjl xj2 xjd 之间的距离d xi xj 的计算公式为 其中 d为数据集中的属性个数 u为样本xi和xj取值相同的属性个数 例6 1 根据表6 3中给出的数据集 计算第一个数据样本和其他各个数据样本之间的相似度 18 表6 3包含多值离散型属性的数据集 解 从表6 3中可以看出 给定数据集包含 年龄段 学历 和 收入 3个属性 也就是说d 3 年龄段 属性的取值包含老年 青年 中年 学历 属性的取值包含本科以下 本科 研究生 收入 属性的取值包含高 中 低 根据公式 6 6 可以计算x 与其他3个样本之间的相似度 从上述计算可以看出 样本xi和xj之间的距离最小 表示它们之间的相似度最大 x1和x2的相似性较小 x1和x3没有相似性 19 多值离散型属性转化为二值离散型属性的具体做法是 为每个多值离散型属性的每种取值创建一个不对称的二值离散型属性 如果数据样本对于给定属性的值是其多种取值中的一种 那么这个取值标记为1 其他取值标记为0 例如 对于数据样本x1 在表6 3中 对应属性 年龄段 学历 和 收入 的取值为青年 研究生 高 而在表6 4中 只有属性 青年 研究生 和 高 的值为1 其余属性的值为0 对于表6 4中的数据集 就可以利用6 3 2节中的公式 6 5 来计算数据样本之间的相似度了 在实际的应用中 多值离散型属性也可以转化为二值离散型属性 表6 3中的数据可以转化为表6 4中的数据 在表6 4中 属性不再是 年龄段 学历 和 收入 而是它们的每种具体取值 20 6 3 4混合类型属性的相似度计算方法在实际的应用中 数据集中包含的描述属性通常不只一种类型 可能是各种类型属性的混合体 对于包含混合类型属性的数据集 数据样本之间的相似度计算方法需要考虑到每种属性自身的具体情况 通常有如下两种方法 1 将属性按照类型分组 则原来的数据集就变成了多个新的数据集 其中每个新的数据集中只包含一种类型的属性 之后对每个数据集进行单独的聚类分析 当这些分析可以得到兼容的结果时 这种方法是可行的 但是 在实际的应用中 根据每种类型的属性单独进行聚类分析往往不能得到令人满意的聚类结果 21 2 把混合类型的属性放在一起处理 进行一次聚类分析 假设给定的数据集为x xm m 1 2 total x中的数据样本用d个描述属性a1 a2 ad来表示 其中的属性包含多种类型 数据样本xi xi1 xik xid xj xjl xjk xjd 其中xik和xjk 1 k d 分别表示数据样本xi和xj对应第k个属性的具体取值 在进行聚类分析之前 对于连续型属性 将其各种取值进行标准化处理 对于多值离散型属性 可以按照6 3 3节中介绍的方法将其转换为不对称的二值离散型属性 完成上述预处理工作之后 数据样本xi和x 之间的距离d xi xj 按照如下的公式进行计算 22 在公式 6 7 中 dij k 表示数据样本xi和xj在第k个属性上的距离 dij k 可以根据第k个属性的具体类型来进行相应的计算 当第k个属性为连续型时 使用下式进行计算 略 当第k个属性为二值离散型属性或者多值离散型属性时 如果xik xjk 则dij k 0 否则 dij k 1 ij k 表示第k个属性对数据样本xi和xj之间距离计算的影响 它的取值情况如下 当xik或者xjk不存在 即属于样本xi或者xj对于属性k没有测量值时 ij k 0 当第k个属性为不对称的二值离散属性 并且xik xjk 0时 ij k 0 除了 和 所述的情况外 在其他情况下 ij k 1 23 6 4k means聚类算法聚类分析的研究成果主要集中在基于距离 或者称为基于相似度 的聚类方法 同类的数据样本应该是互相靠近的 不同类的样本应该相距较远 划分聚类方法是基于距离的聚类方法中的一种 k means聚类算法是划分聚类方法中最常用 最流行的经典算法 许多其他的方法都是k means聚类算法的变种 k means聚类算法将各个聚类子集内的所有数据样本的均值作为该聚类的代表点 算法的主要思想是通过迭代过程把数据集划分为不同的类别 使得评价聚类性能的准则函数达到最优 从而使生成的每个聚类类内紧凑 类间独立 k means聚类算法不适合处理离散型属性 但是对于连续型属性具有较好的聚类效果 24 划分聚类方法对数据集进行聚类时包含如下三个要点 1 选定某种距离作为数据样本间的相似性度量 可以根据实际需要选择欧氏距离 曼哈顿距离或者明考斯基距离中的一种来作为算法的相似性度量 其中最常用的是欧氏距离 2 选择评价聚类性能的准则函数 k means聚类算法使用误差平方和准则函数来评价聚类性能 给定数据集x 其中只包含描述属性 不包含类别属性 假设x包含k个聚类子集x1 x2 xk 各个聚类子集中的样本数量分别为n1 n2 nk 各个聚类子集的均值代表点 也称聚类中心 分别为m1 m2 mk 则误差平方和准则函数如公式 6 8 所示 6 4 1k means聚类算法的基本概念 25 其中 均值向量mi的表达式为 误差平方和准则函数表示数据集中的所有样本与相应聚类中心的方差之和 该准则的值达到最优时可以使各个聚类类内尽可能地紧凑 而各个聚类之间则尽可能地分开 注意 公式 6 8 和公式 6 9 中的样本p和均值mi都是特征向量 而不是单个的数值 此外 公式 6 8 中样本p与均值mi的距离采用的是欧氏距离 适合于对圆形或者球形的聚类子集进行分析 当然 也可以采用其他距离 如曼哈顿距离和明考斯基距离来对椭圆形或者椭球形的聚类子集进行分析 26 3 选择某个初始分类 之后用迭代的方法得到聚类结果 使得评价聚类的准则函数取得最优值 为了得到最优的聚类结果 首先要对给定数据集进行初始划分 通常的做法是事先从数据集中选择各个聚类的代表点 之后把其余的数据样本按照某种方式归类到相应的聚类中去 关于聚类初始代表点的选择 一般有以下几种方法 根据实际问题的特点 按照经验来确定聚类子集的数量 从数据中找出从直观上看来是比较合适的k个聚类的初始代表点 将数据集随机地分成志个聚类 之后计算每个聚类的均值 并且将这些均值作为各个聚类的初始代表点 随机地选择志个数据样本作为聚类的初始代表点 在上述选择代表点的方法中 第 种方法是k means聚类算法最常采用的方法 此外 以上聚类初始代表点的选择方法都是有启发性的 往往带有选择者自身的主观性 需要指出的是 聚类初始代表点的选择往往会影响聚类的最终性能 即得到的是局部最优解而不是全局最优解 27 基于上述分析 给出k means聚类算法的操作步骤如下图所示 28 k means聚类算法按照数据样本问的相似性把数据集聚类为若干个子集 聚类的结果使评价聚类性能的误差平方和准则函数的值达到最优 聚类过程中通常使用欧氏距离作为样本间的相似性度量 从而把给定数据集的特征空间划分为若干个子区间 每一个子区间相当于一个聚类 k means聚类算法中聚类子集的个数k是事先给定的 在此基础上再试图得到一个最优的聚类性能 当聚类子集的个数不能确定时 可以对不同的k值使用多次k means聚类算法 随着k值的增加 评价聚类性能的误差平方和准则函数的值会相应减小 由此 根据k值的变化可以得到一个误差平方和准则函数变化的曲线 从曲线的变化规律 结合实际问题的经验 找到一个相对最合适的聚类个数 29 6 5层次聚类方法层次聚类方法将给定的数据集按照自底向上或者自顶向下的方式分层进行处理 形成一个树形的聚类结构 自底向上的层次聚类方法称为凝聚型层次聚类 自顶向下的层次聚类方法称为分解型层次聚类 层次聚类方法与划分聚类方法不同 划分聚类方法需要通过迭代过程使评价聚类性能的准则函数达到最优 层次聚类方法不需要寻找最优的聚类结果 而是按照给定的相似性度量标准 一种方式是不断地将最相似的两个聚类子集进行合并 直到所有样本都属于一个类别或者满足给定的终止条件 另一种方式是将同一聚类子集中最不相似的部分分解为两个部分 直到每个样本单独构成一个类别或者满足给定的终止条件 30 不论是凝聚型层次聚类还是分解型层次聚类 它们在对数据集进行处理时如何来表示各个聚类之间的相似度呢 假设在某个聚类层次上 数据集x被划分为c个聚类子集x1 x2 xc 各个聚类子集中的样本数量分别为n1 n2 nc 对于聚类子集xi和xj 1 i j c 最常用的相似性度量有以下4种 6 5 1层次聚类方法的基本概念 1 最小距离 2 最大距离 31 3 均值距离 在公式 6 12 中 mi和mj分别是聚类子集xi和xj的均值向量 在上述4种相似性度量中 对于等号右边的d 除了均值距离只能处理连续型属性之外 其余的三种相似性度量可以根据数据集中包含的描述属性的不同 采用6 3节中相应的距离度量 4 平均距离 32 在层次聚类方法的两种分类中 凝聚型