北京大学信息管理系《数据挖掘导论》讲义第四章聚类分析北京大学信息管理系2016年秋
北京大学信息管理系 《数据挖掘导论》讲义 第四章 聚类分析 北京大学信息管理系 2016 年秋
北京大学信息管理系数据挖掘导论第四章目录第四章聚类分析4.1概述：14.1.1什么是聚类分析...4.1.2基本聚类方法概述，4.1.3文本聚类....34.2数据间的相似性度量44.2.1数据对象间的距离4.2.2数据对象间的相似系数.4.2.3数据类间的距离.4.2.4数据标准化..4.3基本聚类方法.4.3.1k-均值聚类方法4.3.2层次聚类方法.84.3.3聚类要注意的问题..104.4基于密度的聚类（待更新）104.5聚类结果的评估，104.5.1基于用户验证的评估方法.114.5.2基于真实数据的聚类结果评估..114.6聚类分析的案例与软件操作114.6.1K-MEANS聚类案例(SPSSModeler).114.6.2K-MEANS聚类案例(R语言)..154.6.3层次聚类案例（SPSS）.204.6.4层次聚类案例（R语言）.23参考文献.271
北京大学信息管理系 数据挖掘导论 第四章 1 目录 第四章 聚类分析. 1 4.1 概述. 1 4.1.1 什么是聚类分析.1 4.1.2 基本聚类方法概述.2 4.1.3 文本聚类.3 4.2 数据间的相似性度量. 4 4.2.1 数据对象间的距离.4 4.2.2 数据对象间的相似系数.5 4.2.3 数据类间的距离.5 4.2.4 数据标准化.7 4.3 基本聚类方法. 7 4.3.1 k-均值聚类方法 .7 4.3.2 层次聚类方法.8 4.3.3 聚类要注意的问题.10 4.4 基于密度的聚类（待更新）. 10 4.5 聚类结果的评估. 10 4.5.1 基于用户验证的评估方法.11 4.5.2 基于真实数据的聚类结果评估.11 4.6 聚类分析的案例与软件操作. 11 4.6.1 K-MEANS 聚类案例(SPSS Modeler).11 4.6.2 K-MEANS 聚类案例(R 语言) .15 4.6.3 层次聚类案例（SPSS）.20 4.6.4 层次聚类案例（R 语言）.23 参考文献. 27
北京大学信息管理系数据挖掘导论第四章第四章聚类分析假设你是某超市的客户关系主管，现想把所有客户分成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-