第6章 聚类分析

2020/2/16数据仓库与数据挖掘1第6章数据聚类2数据分类:在已知类标号的训练集基础上进行分类器设计工作的，所以分类方法又称为监督学习方法。聚类分析：又称为非监督学习方法；使用的数据集样本没有类标号。聚类分析方法可以将数据集划分为多个类别，由此可以给每个样本标注类标号。聚类之后的数据集可以直接用来进行科学分析，也可以作为其他方法的训练集。36．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所示)、离散型属性或者混合型属性。此外，不同类型描述属性的相似度的计算方法不同。56．2聚类分析概述聚类分析是数据挖掘应用的主要技术之一，它可以作为一个独立的工具来使用，将未知类标号的数据集划分为多个类别之后，观察每个类别中数据样本的特点，并且对某些特定的类别作进一步的分析。聚类分析还可以作为其他数据挖掘技术(例如分类学习、关联规则挖掘等)的预处理工作。聚类分析在科学数据分析、商业、生物学、医疗诊断、文本挖掘和Web数据挖掘等领域都有广泛应用。6对聚类分析的要求有以下几个方面。(1)可伸缩性。在以往的应用中，聚类分析方法所处理的数据集都是小数据集，而且比较有效。。面对大数据集，聚类分析方法对数据集的划分结果可能会与理想的划分存在着偏差。因此，对数据集的处理具有良好的可伸缩性是聚类分析的重要研究内容。(2)处理不同类型属性的能力。聚类分析中的许多算法都是针对具有连续型描述属性的数据集设计的。聚类算法可以处理不同类型属性的数据集，例如连续型属性、二值离散型属性、多值(大于2)离散型属性和混合类型属性等。(3)发现任意形状聚类的能力。许多聚类算法是基于欧氏距离和曼哈顿距离度量来计算数据样本之间的相似度的，基于这样的距离度量的算法倾向于将数据集划分为相近大小和密度的球形聚类。能够划分任意形状数据集的聚类方法是非常重要的。7(4)减小对先验知识和用户自定义参数的依赖性。许多聚类算法要求用户事先确定一些参数，如希望将数据集划分的类别数、选择数据集的初始划分方式等。减小对先验知识和用户自定义参数的依赖性，可以减轻用户进行参数设置的负担，也使得对聚类性能的控制相对容易。(5)处理噪声数据的能力。大多数数据库或者数据仓库中都包含孤立点、缺失值和错误的数据。噪声数据会干扰许多聚类算法的聚类性能，导致低质量的数据集划分。(6)可解释性和实用性。用户往往希望聚类结果是可解释的、可理解的并且是可用的，从而可以根据聚类结果进行研究和分析。在低维情况下，可以借助于可视化手段来展示聚类结果；在高维情况下，聚类结果很难被可视化，这时对数据降低维度会有所帮助。8通常聚类算法可以分为以下几类。(1)划分聚类方法。对于给定的数据集，划分聚类方法通过选择适当的初始代表点将数据样本进行初始聚类，之后通过迭代过程对聚类的结果进行不断的调整，直到使评价聚类性能的准则函数的值达到最优为止。(2)层次聚类方法。层次聚类方法将给定数据集分层进行划分，形成一个以各个聚类为结点的树型结构。层次聚类方法分为自底向上（凝聚型层次聚类）和自顶向下（分解型层次聚类）两种方式。(3)基于密度的聚类方法。基本原理：当临近区域的数据密度大于某个阈值时，就不断进行聚类，直到密度小于给定阈值为止。也就是说，每一个类别被看作一个数据区域，对于某个特定类别中的任一数据样本，在给定的范围内必须包含大于给定值的数据样本。基于密度的聚类方法可以用来去除噪声样本，形成的聚类形状也可以是任意的。9(4)基于网格的聚类方法。基于网格的聚类方法将原始的数据空间量化为有限数目的单元，并且由这些单元形成网格结构，所有的聚类操作都要在这个网格结构上进行。基于同格的聚类方法的处理速度较快，其处理时间与数据样本的数量无关，而是与量化空间中每一维上的单元数目有关。聚类分析已经被广泛地研究了许多年，主要集中在基于距离和相似度的算法方面。其中划分聚类方法k—means和层次聚类方法已经被加入到许多统计分析工具的软件包中，作为专门的聚类分析工具来使用。本章主要介绍划分聚类方法k-means和层次聚类方法的原理和算法步骤，并进行实例说明。10聚类分析方法将给定的数据集合划分为多个类别，其中每个类别中任意两个数据样本之间具有较高的相似度，而不同类别的数据样本之间具有较低的相似度。数据样本之间的相似度通常用样本间的距离来表示，而距离是通过数据样本的描述属性的具体取值来计算的。在不同的应用领域中，数据样本的描述属性的类型可能不同，因此相似度的计算方法也不同。下面分别介绍当描述属性为连续型属性、二值离散型属性、多值离散型属性以及混合类型属性时，数据样本之间的相似度计算方法。116．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)，即数据样本之间的距离满足三角不等式的性质。连续型属性可以用多种度量单位来表示，不同的度量单位会导致不同的聚类结果。度量单位越小，描述属性可能的值域就越大，对距离计算的影响越大，从而对聚类结果的影响也越大；度量单位越大，描述属性可能的值域就越小，对距离计算的影响越小，从而对聚类结果的影响也相应减小。146．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的情况被认为不重要，不必参与相似度的计算。176．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中，属性不再是“年龄段”、“学历”和“收入”，而是它们的每种具体取值。206．3．4混合类型属性的相似度计算方法在实际的应用中，数据集中包含的描述属性通常不只一种类型，可能是各种类型属性的混合体。对于包含混合类型属性的