北京大学：《大数据分析与挖掘》课程教学资源（讲义）第四章聚类分析.pdf_大学文库

北京大学信息管理系数据挖掘导论第四章第四章聚类分析假设你是某超市的客户关系主管，现想把所有客户分成5个组，分配的原则自然是每个组内的客户尽可能相似、组间客户尽可能相异，从而可以针对每组客户的共同特点，开发相应的促销活动。那么，如何根据现有数据进行自动分组？与分类不同，每个客户的类别未知，因此我们需要通过对大量客户的描述属性与购买行为进行分析，找出有意义的分组方法。聚类就是这样的一种工具，它把数据对象集划分成多个组或族，使得族内的对象具有较高的相似性，并且与其它族中的对象尽可能不相似。相似性和相异性通过描述对象的属性值来评估，通常涉及距离度量。本章将从聚类方法的概述出发，学习数据对象与数据类间的相似性度量方法，并具体介绍三种专门的聚类算法。4.1概述聚类是最常用的数据分析技术之一，它已有很长的历史，并且几乎在所有领域中都被用到，例如电子商务、电子政务、信息资源管理、经济学、社会学、医学、心理学、植物学、生物学、考古学等等。近几年由于在线文档和互联网的快速发展，文本文档的聚类也成为一个较为活跃的研究领域。本节首先对聚类分析做进一步定义，然后概述将数据对象集划分为簇的基本聚类方法，最后介绍聚类分析技术在文本信息处理领域中的应用。4.1.1什么是聚类分析聚类是对数据对象进行划分的一种过程，与分类不同的是，它所划分的类是未知的。在数据分类（dataclassification）中，我们需要事先给定一个分类体系和训练样本集，如天网的中文网页分类体系，它将所有的网页分为12个大类，即任何网页的内容将属于这12个大类中某一个（或两个）类别，训练样本集中的每一个网页被人工标号为属于某一类样本。这种利用已标记样本集进行对未知样本进行类别划分的方法称为"有监督的学习”（supervisedlearning）方法。而聚类是一个“无简单的学习”（unsupervisedlearning）过程，即聚类算法不需要“教师"的指导，不需要提供训练数据，仅根据该组数据对象的特征而进行的一种自然的划分。聚类分析（clusteranalysis）是一个“无监督的学习”过程，它将数据对象划分为多个类或簇，使得在同一个簇中个体的具有较高的相似度，而不同簇中的个体差别较大。中国古语有“物以类聚人以群分”之说，但根据什么来聚类？假设我们把中国的县分类，就有多种方法，可以按照自然条件来分，比如考虑降水、土地、日照、湿度等：也可考虑收入、教育水准、医疗条件、基础设施等社会指标。也就是说，既可以用某一项来聚类，也可以同时考虑多项指标来聚类。例4.1饮料的聚类分析。表4-1给出了16种饮料的四种变量取值（热量、咖啡因、钠及价格），我们可以根据该数据做哪些聚类分析？1

北京大学信息管理系数据挖掘导论第四章 1 第四章聚类分析假设你是某超市的客户关系主管，现想把所有客户分成 5 个组，分配的原则自然是每个组内的客户尽可能相似、组间客户尽可能相异，从而可以针对每组客户的共同特点，开发相应的促销活动。那么，如何根据现有数据进行自动分组？与分类不同，每个客户的类别未知，因此我们需要通过对大量客户的描述属性与购买行为进行分析，找出有意义的分组方法。聚类就是这样的一种工具，它把数据对象集划分成多个组或簇，使得簇内的对象具有较高的相似性，并且与其它簇中的对象尽可能不相似。相似性和相异性通过描述对象的属性值来评估，通常涉及距离度量。本章将从聚类方法的概述出发，学习数据对象与数据类间的相似性度量方法，并具体介绍三种专门的聚类算法。 4.1 概述聚类是最常用的数据分析技术之一，它已有很长的历史，并且几乎在所有领域中都被用到，例如电子商务、电子政务、信息资源管理、经济学、社会学、医学、心理学、植物学、生物学、考古学等等。近几年由于在线文档和互联网的快速发展，文本文档的聚类也成为一个较为活跃的研究领域。本节首先对聚类分析做进一步定义，然后概述将数据对象集划分为簇的基本聚类方法，最后介绍聚类分析技术在文本信息处理领域中的应用。 4.1.1 什么是聚类分析聚类是对数据对象进行划分的一种过程，与分类不同的是，它所划分的类是未知的。在数据分类（data classification）中，我们需要事先给定一个分类体系和训练样本集，如天网的中文网页分类体系，它将所有的网页分为 12 个大类，即任何网页的内容将属于这 12 个大类中某一个（或两个）类别，训练样本集中的每一个网页被人工标号为属于某一类样本。这种利用已标记样本集进行对未知样本进行类别划分的方法称为“有监督的学习”（supervised learning）方法。而聚类是一个“无简单的学习”（unsupervised learning）过程，即聚类算法不需要“教师”的指导，不需要提供训练数据，仅根据该组数据对象的特征而进行的一种自然的划分。聚类分析（cluster analysis）是一个“无监督的学习” 过程，它将数据对象划分为多个类或簇，使得在同一个簇中个体的具有较高的相似度，而不同簇中的个体差别较大。中国古语有“物以类聚人以群分”之说，但根据什么来聚类？假设我们把中国的县分类，就有多种方法，可以按照自然条件来分，比如考虑降水、土地、日照、湿度等；也可考虑收入、教育水准、医疗条件、基础设施等社会指标。也就是说，既可以用某一项来聚类，也可以同时考虑多项指标来聚类。例 4.1 饮料的聚类分析。表 4-1 给出了 16 种饮料的四种变量取值（热量、咖啡因、钠及价格），我们可以根据该数据做哪些聚类分析？

北京大学信息管理系数据挖掘导论第四章表 4-116种饮料品牌的聚类饮料编号热量咖啡因钠价格1207.203.3015.502.80236.805.9012.903.30372.207.308.202.404.404.0036.7010.5059.203.50121.704.1064.0010.203.3089.107146.704.309.701.80857.602.2013.602.10995.90.008.501.301010.603.50199.00.001149.808.006.303.70121.5016.604.706.30133.707.702.0038.501413.102.20.004.20154.707.204.10118.8016107.00.008.304.20（1）对变量进行聚类（即数据中的列，如热量、咖啡因、钠、价格），对变量的聚类又称为R型聚类，在SPSSModeler的k-均值聚类中需要把数据阵进行转置才可直接分析；（2）对观测值进行聚类，（即数据中的行，16种不同品牌的饮料），如仅根据热量这项对不同饮料聚类，或同时根据四个变量进行聚类等，对观测值的聚类又称为Q型聚类。4.1.2基本聚类方法概述文献中有大量的聚类算法，很难对其提出一个简洁的分类，因为这些类别可能交叉重叠，从而使得一种方法具有几种类别的特征。但是一般而言，主要的基本聚类方法可以分成如下几类：（1）划分聚类（partitionalclustering）：给定一个n个对象的集合，划分聚类构建数据的k个子集，并且k<n。也就是说它把数据划分为k个组，使得每个组至少包含一个对象。一般来说，划分聚类是将数据对象集划分成不重叠的子集（即互斥子集），但在模糊划分技术中，可以适当放宽。使用划分聚类的前提是用户指定簇的个数，但有时用户并不能确定到底需要划分成多少个簇才能达到最好效果，这时可用层次聚类法确定大概的簇数目。（2）层次聚类（hierarchicalclustering）：根据层次分解的形成步骤，可分为自底向上方法和自顶向下方法。自底向上方法将每个对象作为单独的一个组，然后逐次合并相近的对象或组，直到所有的组合并成一个组（即层次的最顶层），或者满足某个终止条件：自顶向下方法将所有的对象置于一个组中，在每次相继迭代中，一个簇被划分成更小的簇，直到最终每个对象在单独的一个簇中，或满足某终止条件。层次聚类的缺陷在于一旦一个步骤完成，就不能被撤销，也就是说某个步骤进行了错误的划分后，无法更正该错误。（3）基于密度聚类（density-basedclustering）：基于对象之间的距离进行聚类时，往往只能发现球状簇，而当现实中的簇为任意形状时，或有噪声和孤立点时，常常使用基于密度的方法进行聚类。该方法的主要思想是，只要邻域中的密度（数据点的数目）超过某个阈值，才能继续进行划分，也就是说，对给定簇中的每个数据点，在给定半径的邻域中必须至少包含最少数目的点。如图4-1所示，两个圆形簇并没有合并，因为它们之间的桥消失在噪声中。2

北京大学信息管理系数据挖掘导论第四章 2 表 4-1 16 种饮料品牌的聚类（1）对变量进行聚类（即数据中的列，如热量、咖啡因、钠、价格），对变量的聚类又称为 R 型聚类，在 SPSS Modeler 的 k-均值聚类中需要把数据阵进行转置才可直接分析；（2）对观测值进行聚类，（即数据中的行，16 种不同品牌的饮料），如仅根据热量这一项对不同饮料聚类，或同时根据四个变量进行聚类等，对观测值的聚类又称为 Q 型聚类。 4.1.2 基本聚类方法概述文献中有大量的聚类算法，很难对其提出一个简洁的分类，因为这些类别可能交叉重叠，从而使得一种方法具有几种类别的特征。但是一般而言，主要的基本聚类方法可以分成如下几类：（1）划分聚类（partitional clustering）：给定一个 n 个对象的集合，划分聚类构建数据的 k 个子集，并且 k≤n。也就是说它把数据划分为 k 个组，使得每个组至少包含一个对象。一般来说，划分聚类是将数据对象集划分成不重叠的子集（即互斥子集），但在模糊划分技术中，可以适当放宽。使用划分聚类的前提是用户指定簇的个数，但有时用户并不能确定到底需要划分成多少个簇才能达到最好效果，这时可用层次聚类法确定大概的簇数目。（2）层次聚类（hierarchical clustering）：根据层次分解的形成步骤，可分为自底向上方法和自顶向下方法。自底向上方法将每个对象作为单独的一个组，然后逐次合并相近的对象或组，直到所有的组合并成一个组（即层次的最顶层），或者满足某个终止条件；自顶向下方法将所有的对象置于一个组中，在每次相继迭代中，一个簇被划分成更小的簇，直到最终每个对象在单独的一个簇中，或满足某终止条件。层次聚类的缺陷在于一旦一个步骤完成，就不能被撤销，也就是说某个步骤进行了错误的划分后，无法更正该错误。（3）基于密度聚类（density-based clustering）：基于对象之间的距离进行聚类时，往往只能发现球状簇，而当现实中的簇为任意形状时，或有噪声和孤立点时，常常使用基于密度的方法进行聚类。该方法的主要思想是，只要邻域中的密度（数据点的数目）超过某个阈值，才能继续进行划分，也就是说，对给定簇中的每个数据点，在给定半径的邻域中必须至少包含最少数目的点。如图 4-1 所示，两个圆形簇并没有合并，因为它们之间的桥消失在噪声中

北京大学信息管理系数据挖掘导论第四章图4-1基于密度的簇4.1.3文本聚类在信息检索中，文本聚类的早期应用主要是为了提高系统的查准率与查全率，并被用于寻找给定文本的相近文本，目前主要用于浏览文本、显示文本集合、组织搜索引擎的返回结果，如搜索引擎Vivisimo将查询结果进行聚类，这有利于用户快速定位自己所需要的信息。例4.2文本聚类。遍布全球的新闻机构每天都会发布不计其数的新闻文章。假设一个网站想要收集这些新闻文章并提供一种整合的新闻服务，那么它必须要根据某种主题层次来组织这些收集到的文章。问题是，这些主题应怎么选择和组织？一种可能的方法是雇用一批专家来做这项工作，但是，通过人力来组织是十分昂贵而且耗时的，这使得这种方法对于新闻和其他具有实时性要求的任务来说并不合适。把未经分类的新闻文章全部扔给用户也显然不是一种可选的方法。尽管分类方法能够把新闻分类到一些事先定义好的类别中去，但是由于分类方法需要训练数据，这使得分类方法在这里并不可行，因为训练数据需要大量的人力标注。更进一步，新闻主题是时刻都在快速变化的，从而训练数据也需要随之发生变化，这使得人力标注变得不可能。显然，聚类成为解决这个问题的一种方案。它根据新闻文章内容的相似度自动地把它们归类。在文本或网页聚类中，使用最多的聚类方法是：k-均值聚类与层次聚类方法、或这两种基本方法的改进形式。其他方法包括：自组织特征映射、遗传算法等等。进行文本聚类的大致步骤可概括如下：对给定的文本集合，（1）首先需要对各个文本进行预处理，包括词法分析，英文的词干提取、中文分词或命名实体识别等：（2）然后进行特征选取、或特征抽取等，构造文本集合的特征向量空间；（3）计算各个文本之间的相似度或距离，即：构造文本间的相异度（或相似度）矩阵：（4）选择某一种聚类算法进行聚类：（5）根据实际应用，进行类别选择与类别命名；（6）将聚类结果以适当的形式（如列表或可视化等形式）输出；（7）对聚类结果进行评估，以检验聚类结果的质量。如结果不好，可以返回到前面的某一步进行重新聚类。图4-3

北京大学信息管理系数据挖掘导论第四章 3 图 4-1 基于密度的簇 4.1.3 文本聚类在信息检索中，文本聚类的早期应用主要是为了提高系统的查准率与查全率，并被用于寻找给定文本的相近文本，目前主要用于浏览文本、显示文本集合、组织搜索引擎的返回结果，如搜索引擎 Vivisimo 将查询结果进行聚类，这有利于用户快速定位自己所需要的信息。例 4.2 文本聚类。遍布全球的新闻机构每天都会发布不计其数的新闻文章。假设一个网站想要收集这些新闻文章并提供一种整合的新闻服务，那么它必须要根据某种主题层次来组织这些收集到的文章。问题是，这些主题应怎么选择和组织？一种可能的方法是雇用一批专家来做这项工作，但是，通过人力来组织是十分昂贵而且耗时的，这使得这种方法对于新闻和其他具有实时性要求的任务来说并不合适。把未经分类的新闻文章全部扔给用户也显然不是一种可选的方法。尽管分类方法能够把新闻分类到一些事先定义好的类别中去，但是由于分类方法需要训练数据，这使得分类方法在这里并不可行，因为训练数据需要大量的人力标注。更进一步，新闻主题是时刻都在快速变化的，从而训练数据也需要随之发生变化，这使得人力标注变得不可能。显然，聚类成为解决这个问题的一种方案。它根据新闻文章内容的相似度自动地把它们归类。在文本或网页聚类中，使用最多的聚类方法是：k-均值聚类与层次聚类方法、或这两种基本方法的改进形式。其他方法包括：自组织特征映射、遗传算法等等。进行文本聚类的大致步骤可概括如下：对给定的文本集合，（1）首先需要对各个文本进行预处理，包括词法分析，英文的词干提取、中文分词或命名实体识别等；（2）然后进行特征选取、或特征抽取等，构造文本集合的特征向量空间；（3）计算各个文本之间的相似度或距离，即：构造文本间的相异度（或相似度）矩阵；（4）选择某一种聚类算法进行聚类；（5）根据实际应用，进行类别选择与类别命名；（6）将聚类结果以适当的形式（如列表或可视化等形式）输出；（7）对聚类结果进行评估，以检验聚类结果的质量。如结果不好，可以返回到前面的某一步进行重新聚类。图 4-

北京大学信息管理系数据挖掘导论第四章2为文本聚类的一般过程。文档集合词法分析特征选取计算文档间的相似度1结果评估类别生成与描述聚类算法结果输出图4-2文本聚类的一般过程4.2数据间的相似性度量假设需要对100个学生进行分类。当我们仅知道他们的数学成绩时，只好按照数学成绩进行分类，这些成绩在直线上可以形成100个点，这样就可以把接近的点放到一类：如果还知道他们的物理成绩，这样数学和物理成绩就形成二维平面上的100个点，也可以按照距离远近来分类。三维或者更高维的情况也是类似，只不过三维以上的图形无法直观地画出来而已。在例4.1的饮料数据中，每种饮料都有四个变量值，若想测量其距离，就是四维空间点的问题。为了度量样本间的接近或相似程度，需要定义一些用于划分类别的计量指标。常用的统计指标有距离和相似系数。“距离”属于相异性测度指标，“相似系数"属于相似性测度指标。距离和相似系数成某种反比关系，如sim(d,d)=1/(1+d)，其中，sim(d,d)表示数据对象d;与d间的相似系数，dj表示数据对象d;与d;间的距离。4.2.1数据对象间的距离对于有n个特征属性的数据对象集合来说，m个数据对象可以看作n维空间中的m个点，此时，每一个数据对象被表示为一个n维向量。进而我们可以用点间的距离来度量数据对象间的距离。最常用的距离度量方法是欧几里得距离，定义如下：d, =/(wn-Wt) +(w2-Wj2) +...+(wm-Wm)2其中，第i个数据对象与第j个数据对象分别用（wa,Wi2,"Wm）和(wjsWj2Wm）表示；d表示第i个数据对象与第j个数据对象间的距离。另一个度量方法是曼哈坦距离，其定义如下：d, -=W,-w,|+/W2-wj2|+...+[wm-wm|上面的两种度量方法都满足对距离函数的如下要求：d,≥0，即距离是一个非负的数值；d.=0，即一个文档与自身的距离为0;d,=dn，即距离函数具有对称性；d,≤d+d，即距离函数满足三角不等式；4

北京大学信息管理系数据挖掘导论第四章 4 2 为文本聚类的一般过程。 4.2 数据间的相似性度量假设需要对 100 个学生进行分类。当我们仅知道他们的数学成绩时，只好按照数学成绩进行分类，这些成绩在直线上可以形成 100 个点，这样就可以把接近的点放到一类；如果还知道他们的物理成绩，这样数学和物理成绩就形成二维平面上的 100 个点，也可以按照距离远近来分类。三维或者更高维的情况也是类似，只不过三维以上的图形无法直观地画出来而已。在例 4.1 的饮料数据中，每种饮料都有四个变量值，若想测量其距离，就是四维空间点的问题。为了度量样本间的接近或相似程度，需要定义一些用于划分类别的计量指标。常用的统计指标有距离和相似系数。“距离”属于相异性测度指标，“相似系数”属于相似性测度指标。距离和相似系数成某种反比关系，如 sim(di,dj)=1/(1+dij)，其中，sim(di,dj)表示数据对象 di与 dj 间的相似系数，dij 表示数据对象 di与 dj 间的距离。 4.2.1 数据对象间的距离对于有 n 个特征属性的数据对象集合来说，m 个数据对象可以看作 n 维空间中的 m 个点，此时，每一个数据对象被表示为一个 n 维向量。进而我们可以用点间的距离来度量数据对象间的距离。最常用的距离度量方法是欧几里得距离，定义如下： 2 2 2 1 1 2 2 ( ) ( ) ( ) ij i j i j in jn d w w w w w w        其中，第 i 个数据对象与第 j 个数据对象分别用 1 2 ( , , , ) w w w i i in 和 1 2 ( , , , ) w w w j j jn 表示；dij 表示第 i 个数据对象与第 j 个数据对象间的距离。另一个度量方法是曼哈坦距离，其定义如下： 1 1 2 2 | | | | | | d w w w w w w ij i j i j in jn        上面的两种度量方法都满足对距离函数的如下要求： 0 ij d  ，即距离是一个非负的数值； 0 ii d  ，即一个文档与自身的距离为 0； ij ji d d  ，即距离函数具有对称性； ij ik kj d d d   ，即距离函数满足三角不等式；图 4-2 文本聚类的一般过程

北京大学信息管理系数据挖掘导论第四章明考斯基距离是欧几里得距离和曼哈坦距离的概化，定义如下：d,=(/w-w,P+/W2-w2P+...+/wm-Wm/P)/,其中q是一个正整数，当9=1时，它表示曼哈坦距离：当9-2时，它表示欧几里得距离。如果对每一个变量根据其重要性赋予一个权重，就得到加权的明考斯基距离：d, =(u /w,-w,IP+uz /w2 -w,2 P +..+u, /wn-wm )"p4.2.2数据对象间的相似系数对于有n个特征属性的数据对象集合来说，我们也可以用相似系数来度量它们之间的相近程度，用sim(i.j)表示第i个向量与第j个向量之间的相似系数，则我们有：（1）Vi,j[sim(i,j)飞1，即绝对值总不大于1(2）Vi,jsim(i,j)=sim(j,i)，即满足对称性常见的几种相似系数有：（1）Pearson相关系数（PearsonCorrelationCoefficient）（2）余弦系数（Cosinecoefficient)）>WikWjksim(i,j) =n27WikWjkk=1（3）重叠系数（Overlapcoefficient)）E wuwksim(i,j) =min("- i.Z" w.)（4）雅可比系数（Jaccard coefficient）E WisWjksim(i, j) =DnZk-I Wi+Zk-I Wik -Zkl Wiu wjk对于二值的情况，相似系数的计算还有其它的度量指标。此外，需要指出的是数据对象之间不同度量指标的选择，所得到的聚类结果存在一定的差异，需要结合具体情况来考察哪些度量指标对那些数据更有效。4.2.3数据类间的距离按照距离来聚类需要明确两个概念：一个是点和点之间的距离，一个是类和类之间的距离。如何测量4.2.1节主要介绍了数据点之间距离的测量方法，本节将对数据类间的距离测量做简单介绍。由一个点组成的类是最基本的类，如果每一类都由一个点组成，那么点间的距离就是类间距离。但是如果某一类包含不止一个点，那么就要确定类间距离。设D和D2是两个数据类，分别包括ml和m2个数据对象，用s(Di,D2)表示两类对象之间的距离，s(di,d2)表示对象di和对象d2之间的距离，并假设这两个数据对象集合都具有n个特征属性。我们结合图4-3来说明如下几种对象类之间距离的常见度量方法，其中图中虚线5

北京大学信息管理系数据挖掘导论第四章 5 明考斯基距离是欧几里得距离和曼哈坦距离的概化，定义如下： 1 / 1 1 2 2 (| | | | | | ) p p p p ij i j i j in jn d w w w w w w        ，其中 q 是一个正整数，当 q=1 时，它表示曼哈坦距离；当 q=2 时，它表示欧几里得距离。如果对每一个变量根据其重要性赋予一个权重，就得到加权的明考斯基距离： 1 / 1 1 1 2 2 2 ( | | | | | | ) p p p p ij i j i j n in jn d u w w u w w u w w        4.2.2 数据对象间的相似系数对于有 n 个特征属性的数据对象集合来说，我们也可以用相似系数来度量它们之间的相近程度，用 sim(i,j)表示第 i 个向量与第 j 个向量之间的相似系数，则我们有：（1）   i j sim i j , | ( , ) | 1 ，即绝对值总不大于 1 （2）   i j sim i j sim j i , ( , ) ( , ) ，即满足对称性常见的几种相似系数有：（1）Pearson 相关系数（Pearson Correlation Coefficient）（2）余弦系数 (Cosine coefficient) 1 2 2 1 1 ( , ) n ik jk k n n ik jk k k w w sim i j w w        （3）重叠系数 (Overlap coefficient) 1 1 1 ( , ) min( , ) n ik jk k n n ik jk k k w w sim i j w w        （4）雅可比系数 ( Jaccard coefficient) 1 1 1 1 ( , ) n ik jk k n n n ik jk ik jk k k k w w sim i j w w w w            对于二值的情况，相似系数的计算还有其它的度量指标。此外，需要指出的是数据对象之间不同度量指标的选择，所得到的聚类结果存在一定的差异，需要结合具体情况来考察哪些度量指标对那些数据更有效。 4.2.3 数据类间的距离按照距离来聚类需要明确两个概念：一个是点和点之间的距离，一个是类和类之间的距离。如何测量 4.2.1 节主要介绍了数据点之间距离的测量方法，本节将对数据类间的距离测量做简单介绍。由一个点组成的类是最基本的类，如果每一类都由一个点组成，那么点间的距离就是类间距离。但是如果某一类包含不止一个点，那么就要确定类间距离。设 D1 和 D2是两个数据类，分别包括 m1 和 m2 个数据对象，用 s(D1,D2)表示两类对象之间的距离, s(d1,d2)表示对象 d1 和对象 d2 之间的距离，并假设这两个数据对象集合都具有 n 个特征属性。我们结合图 4-3 来说明如下几种对象类之间距离的常见度量方法，其中图中虚线

北京大学信息管理系数据挖掘导论第四章量在各分量上计算其算术平均值后所得的向量。设Da为D的重心，即D=ja,：则s(D D,s DaDam4.2.4数据标准化选用的度量单位将直接影响聚类分析的结果，如将高度由“米”改为厘米”，重量由“克”改为“千克”，就可能产生非常不同的聚类结果。为了避免对度量单位的依赖，数据应当进行标准化，有多种方法，在此我们介绍三种方法：最小--最大规范化、Z-score规范化和按小数定标规范化。（1）最小-最大规范化：对原始数据进行线性变换。设minx和maxx分别为变量x的最小值与最大值。则最小-最大规范化通过计算ww-min.(new_max,- new_min,)+ new_min,max,-min将x的值w映射到区间[new_minx,new_maxx]中的w。（2）Z-score规范化：变量x的值基于x的平均值和标准差规范化。x的值w被规范化为W，由下式计算：w'=W-aa其中，a和分别为x的平均值和标准差。（3）小数定标规范化：通过移动x取值的小数位置进行规范化。小数点的移动位置依赖于x取值的最大数的绝对值。x的值w被规范化为w，由下式计算："-其中，j是使得Max(/w"D<1的最小整数。如：w=985，则j=3，此时w2=0.985。4.3基本聚类方法4.3.1k-均值聚类方法典型的划分方法包括k-均值方法、k-中心点方法及其它们的变形。本节主要介绍k-均值方法。k-均值方法（k-meansmethod）是一个简单高效、应用广泛的聚类方法。前面说过，划分聚类要求先说好要分多少个类。假定分3类，那么需要事先确定3个点为“聚类种子”，也就是说，把这3个点作为三类中每一类的基石：然后根据和这三个点的距离远近，把所有点分成三类，再把这三类的中心（即均值）作为新的基石或种子，再重新按照距离分类；如此选代下去，直到达到停止选代的要求（比如各个类最后变化不大，或者选代次数太多）。显然，前面对聚类种子的选择并不必太认真，因为它们很可能最后被分到同一类中。图4-4较为详细地对这一过程进行了描绘。首先随机选择k个对象作为初始值，用以代表一个簇的平均值或中心，其中k是用户指定的参数，即所期望的簇的个数。对剩余的数据对象，根据它与各个簇中心的距离将它赋给最近的簇。然后重新计算每个簇的平均值。这个过程不断重复，直至每个数据对象所属的簇不再发生变化。7

北京大学信息管理系数据挖掘导论第四章 7 量在各分量上计算其算术平均值后所得的向量。设 DG 为 D 的重心，即 1 1 n G j D d m j   ；则 1 2 1 2 ( , ) ( , ) G G s D D s D D  4.2.4 数据标准化选用的度量单位将直接影响聚类分析的结果，如将高度由“米”改为“厘米”，重量由“克” 改为“千克”，就可能产生非常不同的聚类结果。为了避免对度量单位的依赖，数据应当进行标准化，有多种方法，在此我们介绍三种方法：最小-最大规范化、Z-score 规范化和按小数定标规范化。（1）最小-最大规范化：对原始数据进行线性变换。设 minx和 maxx分别为变量 x 的最小值与最大值。则最小-最大规范化通过计算 ' min ( _ max _ min ) _ min max min x x x x x x w w new new new      将 x 的值 w 映射到区间[new_minx, new_maxx]中的 w’。（2）Z-score 规范化：变量 x 的值基于 x 的平均值和标准差规范化。x 的值 w 被规范化为 w’，由下式计算： ' w a w    其中，a 和 σ 分别为 x 的平均值和标准差。（3）小数定标规范化：通过移动 x 取值的小数位置进行规范化。小数点的移动位置依赖于 x 取值的最大数的绝对值。x 的值 w 被规范化为 w’，由下式计算： ' 10j w w  其中，j 是使得 Max(|w’|)<1 的最小整数。如：|w|=985，则 j=3，此时 w’=0.985。 4.3 基本聚类方法 4.3.1 k-均值聚类方法典型的划分方法包括 k-均值方法、k-中心点方法及其它们的变形。本节主要介绍 k-均值方法。 k-均值方法（k-means method）是一个简单高效、应用广泛的聚类方法。前面说过，划分聚类要求先说好要分多少个类。假定分 3 类，那么需要事先确定 3 个点为“聚类种子”，也就是说，把这 3 个点作为三类中每一类的基石；然后根据和这三个点的距离远近，把所有点分成三类，再把这三类的中心（即均值）作为新的基石或种子，再重新按照距离分类；如此迭代下去，直到达到停止迭代的要求（比如各个类最后变化不大，或者迭代次数太多）。显然，前面对聚类种子的选择并不必太认真，因为它们很可能最后被分到同一类中。图 4-4 较为详细地对这一过程进行了描绘。首先随机选择 k 个对象作为初始值，用以代表一个簇的平均值或中心，其中 k 是用户指定的参数，即所期望的簇的个数。对剩余的数据对象，根据它与各个簇中心的距离将它赋给最近的簇。然后重新计算每个簇的平均值。这个过程不断重复，直至每个数据对象所属的簇不再发生变化

北京大学信息管理系数据挖掘导论第四章UpdateAssigntheeachclusterobjectsmeanstomostsimilarreassignreassigncenterK=2Arbitrarily chooseKobject as initialcluster centerUpdatetheclustermeans图4-4k-均值算法的过程stepl：任意选择k个点作为初始的类的中心（即图中的红色点）step2：根据类中数据对象据初始类中心的距离，将每个数据对象赋给最相近的类step3：更新类的平均值step4：重复以上过程step5：直到不再发生变化，即没有对象进行被重新分配时过程结束。该算法试图找出使平方误差值最小的k个划分，所以当结果簇是密集的，并且簇与簇之间区分明显时，它的效果较好。但是由于该算法在每次迭代时，都要计算每个小类的均值作为该类的代表元，因此该算法对异常数据十分敏感，因为少量的该类数据对平均值会产生较大影响。从算法复杂度来说，该算法易于实现且效率较高，时间复杂度为O(tkn）。其中，n为数据点的个数，k是聚类的个数，t是循环选代的次数，由于k和t通常都远远小于n，因此该算法相对于数据点数目而言常常是线性时间内可以完成的。目前，k-均值方法有多种变形形式，不同改进在于初始k个数据对象的选择策略：相异度的计算方法；如何计算类的平均值等。产生较好聚类结果的一个有趣策略是，首先用层次聚类方法决定结果簇的个数，并找到初始的聚类，然后用迭代重定位来改进聚类结果4.3.2层次聚类方法层次聚类方法能对数据对象进行层次化的组织，即一个大的主题可以包含若干个小的主题，形成一个目录层次结构，尽管该目录结构可能并不十分精确。层次聚类方法通常用树图来表示其聚类过程。例4.2文档层次聚类。图4-5给出了一个文档聚类的例子，在树的最底层包含5个文档（dl，d2，d3，d4，d5）。在上一层中，聚类点6包含两个文档dl和d2，聚类点7包含另两个文档d4和d5。随着我们自下而上遍历该树，聚类的数目越来越少，用户可以选择查看在树的任意层次上的聚类。8

北京大学信息管理系数据挖掘导论第四章 8 图 4-4 k-均值算法的过程 step1：任意选择 k 个点作为初始的类的中心（即图中的红色点） step2：根据类中数据对象据初始类中心的距离，将每个数据对象赋给最相近的类 step3：更新类的平均值 step4：重复以上过程 step5：直到不再发生变化，即没有对象进行被重新分配时过程结束。该算法试图找出使平方误差值最小的 k 个划分，所以当结果簇是密集的，并且簇与簇之间区分明显时，它的效果较好。但是由于该算法在每次迭代时，都要计算每个小类的均值作为该类的代表元，因此该算法对异常数据十分敏感，因为少量的该类数据对平均值会产生较大影响。从算法复杂度来说，该算法易于实现且效率较高，时间复杂度为 O tkn ( )。其中，n 为数据点的个数，k 是聚类的个数，t 是循环迭代的次数，由于 k 和 t 通常都远远小于 n，因此该算法相对于数据点数目而言常常是线性时间内可以完成的。目前，k-均值方法有多种变形形式，不同改进在于初始 k 个数据对象的选择策略；相异度的计算方法；如何计算类的平均值等。产生较好聚类结果的一个有趣策略是，首先用层次聚类方法决定结果簇的个数，并找到初始的聚类，然后用迭代重定位来改进聚类结果。 4.3.2 层次聚类方法层次聚类方法能对数据对象进行层次化的组织，即一个大的主题可以包含若干个小的主题，形成一个目录层次结构，尽管该目录结构可能并不十分精确。层次聚类方法通常用树图来表示其聚类过程。例 4.2 文档层次聚类。图 4-5 给出了一个文档聚类的例子，在树的最底层包含 5 个文档（d1，d2，d3，d4，d5）。在上一层中，聚类点 6 包含两个文档 d1 和 d2，聚类点 7 包含另两个文档 d4 和 d5。随着我们自下而上遍历该树，聚类的数目越来越少，用户可以选择查看在树的任意层次上的聚类

北京大学：《大数据分析与挖掘》课程教学资源（讲义）第四章 聚类分析

北京大学：《大数据分析与挖掘》课程教学资源（讲义）第四章聚类分析