点击查看第一章
点击查看第三章

第2章 数　　据

本章讨论一些与数据相关的问题，它们对于数据挖掘的成败至关重要。
数据类型　数据集的不同表现在多方面。例如，用来描述数据对象的属性可以具有不同的类型——定量的或定性的，并且数据集通常具有特定的性质，例如，某些数据集包含时间序列或彼此之间具有明显联系的对象。毫不奇怪，数据的类型决定我们应使用何种工具和技术来分析数据。此外，数据挖掘研究常常是为了适应新的应用领域和新的数据类型的需要而展开的。
数据的质量　数据通常远非完美。尽管大部分数据挖掘技术可以忍受某种程度的数据不完美，但是注重理解和提高数据质量将改进分析结果的质量。通常必须解决的数据质量问题包括存在噪声和离群点，数据遗漏、不一致或重复，数据有偏差或者不能代表它应该描述的现象或总体情况。
使数据适合挖掘的预处理步骤　通常，原始数据必须加以处理才能适合分析。处理一方面是要提高数据的质量，另一方面要让数据更好地适应特定的数据挖掘技术或工具。例如，有时需要将连续值属性（如长度）转换成离散的分类值的属性（如短、中、长），23以便应用特定的技术。又如，数据集属性的数目常常需要减少，因为属性较少时许多技术用起来更加有效。
根据数据联系分析数据　数据分析的一种方法是找出数据对象之间的联系，之后使用这些联系而不是数据对象本身来进行其余的分析。例如，我们可以计算对象之间的相似度或距离，然后根据这种相似度或距离进行分析——聚类、分类或异常检测。诸如此类的相似性或距离度量很多，要根据数据的类型和特定的应用做出正确的选择。
例2.1 与数据相关的问题　为了进一步解释这些问题的重要性，考虑下面的假想情况。你收到某个医学研究者发来的电子邮件，是关于你想要研究的一个项目的。邮件的内容如下：

尽管有些疑虑，你还是开始着手分析这些数据。文件的前几行如下：

粗略观察这些数据并未发现什么不对。你抛开疑虑，并开始分析。数据文件只有1000行，比你希望的小，24两天之后你认为你已经取得一些进展。你去参加会议，在等待其他人时，你开始与一位参与该项目工作的统计人员交谈。当听说你正在分析该项目的数据时，她请你向她简略介绍你的结果。

尽管这一场景代表一种极端情况，但它强调了“了解数据”的重要性。为此，本章将讨论上面提到的4个问题，列举一些基本难点和标准解决方法。

2.1　数据类型

通常，数据集可以看作数据对象的集合。数据对象有时也叫作记录、点、向量、模式、事件、案例、样本、实例、观测或实体。数据对象用一组刻画对象的特性（如物体质量或事件发生时间）的属性描述。属性有时也叫作变量、特性、字段、特征或维。
例2.2 学生信息　通常，数据集是一个文件，其中对象是文件的记录（或行），而每个字段（或列）对应于一个属性。例如，表2.1显示了包含学生信息的数据集。每行对应一个学生，而每列是一个属性，描述学生的某一方面，如平均绩点（GPA）或标识号（ID）。

基于记录的数据集在平展文件或关系数据库系统中是最常见的，但是还有其他类型的数据集和存储数据的系统。在2.1.2节，我们将讨论数据挖掘中经常遇到的其他类型的数据集。然而，我们先考虑属性。

2.1.1　属性与度量

本小节考虑使用何种类型的属性描述数据对象。首先定义属性，然后考虑属性类型的含义，最后介绍经常遇到的属性类型。

1.什么是属性

我们先更详细地定义属性。
定义2.1 属性（attribute）　对象的性质或特性，它因对象而异，或随时间而变化。例如，眼球颜色因人而异，而物体的温度随时间而变。注意：眼球颜色是一种符号属性，具有少量可能的值{棕色，黑色，蓝色，绿色，淡褐色，…}；而温度是数值属性，可以取无穷多个值。
追根溯源，属性并非数字或符号。然而，为了讨论和精细地分析对象的特性，我们为它们赋予了数字或符号。为了用一种明确定义的方式做到这一点，我们需要测量标度。
定义2.2测量标度（measurement scale）　将数值或符号值与对象的属性相关联的规则（函数）。形式上，测量过程是使用测量标度将一个值与一个特定对象的特定属性相关联。这看上去有点抽象，但是任何时候，我们总在进行这样的测量过程。例如，踏上体重秤称体重；将人分为男女；清点会议室的椅子数量，确定是否能够为所有与会者提供足够的座位。在所有这些情况下，对象属性的“物理值”都被映射到数值或符号值。
有了这些背景，我们就可以讨论属性类型，这对于确定特定的数据分析技术是否适用于某种具体的属性是非常重要的。

2.属性类型

我们通常将属性的类型称为测量标度的类型。从前面的讨论显而易见，属性可以用不同的测量标度来描述，并且属性的性质不必与用来度量它的值的性质相同。换句话说，用来代表属性的值可能具有不同于属性本身的性质，反之亦然。我们用两个例子来解释。
例2.3 雇员年龄和ID号　与雇员有关的两个属性是ID和年龄，这两个属性都可以用整数表示。然而，谈论雇员的平均年龄是有意义的，但是谈论雇员的平均ID却毫无意义。的确，我们希望ID属性所表达的唯一方面是它们互不相同。因而，对雇员ID的唯一合法操作就是判定它们是否相等。但在使用整数表示雇员ID时，并没暗示有此限制。对于年龄属性而言，用来表示年龄的整数的性质与该属性的性质大同小异。尽管如此，这种对应仍不完备，例如，年龄有最大值，而整数没有。
例2.4 线段长度　考虑图2.1，它展示了一些线段对象和如何用两种不同的方法将这些对象的长度属性映射到整数。从上到下，每条后继线段都是通过最上面的线段自我添加而形成的。这样，第二条线段是最上面的线段两次相连形成的，第三条线段是最上面的线段三次相连形成的，以此类推。从物理意义上讲，所有的线段都是第一条线段的倍数。这个事实由图右边的测量捕获，但未被左边的测量捕获。更准确地说，左边的测量标度仅仅捕获长度属性的序，而右边的标度同时捕获序和可加性的性质。因此，属性可以用一种不描述属性全部性质的方式测量。

知道属性的类型很重要，因为它告诉我们测量值的哪些性质与属性的基本性质一致，从而使得我们可以避免诸如计算雇员的平均ID这样的愚蠢行为。

3.属性的不同类型

一种指定属性类型的有用（和简单）的办法是，确定对应属性基本性质的数值的性质。例如，长度的属性可以有数值的许多性质。按照长度比较对象，确定对象的排序，以及谈论长度的差和比例都是有意义的。数值的如下性质（操作）常常用来描述属性。
1) 相异性：=和≠。
2) 序：<、≤、>和≥。
3) 加法：+和-。
4) 乘法：*和/。
给定这些性质，我们可以定义四种属性类型：标称（nominal）、序数（ordinal）、区间（interval）和比率（ratio）。表2.2给出这些类型的定义，以及每种类型上有哪些合法的统计操作等信息。每种属性类型拥有其上方属性类型上的所有性质和操作。因此，对于标称、序数和区间属性合法的任何性质或操作，对于比率属性也合法。换句话说，属性类型的定义是累积的。29当然，对于某种属性类型合适的统计操作，对其上方的属性类型就不一定合适。

标称和序数属性统称分类的（categorical）或定性的（qualitative）属性。顾名思义，定性属性（如雇员ID）不具有数的大部分性质。即便使用数（即整数）表示，也应当像对待符号一样对待它们。其余两种类型的属性，即区间和比率属性，统称定量的（quantitative）或数值的（numeric）属性。定量属性用数表示，并且具有数的大部分性质。注意：定量属性可以是整数值或连续值。
属性的类型也可以30用不改变属性意义的变换来描述。实际上，心理学家S.Smith Stevens最先用允许的变换（permissible transformation）定义了表2.2所示的属性类型。例如，如果长度分别用米和英尺度量，其属性的意义并未改变。
对特定的属性类型有意义的统计操作是：当使用保持属性意义的变换对属性进行变换时，它们产生的结果相同。例如，用米和英尺为单位进行度量时，同一组对象的平均长度数值是不同的，但是两个平均值都代表相同的长度。表2.3给出表2.2中四种属性类型的允许的（保持意义的）变换。

例2.5 温度标度　温度可以很好地解释前面介绍的一些概念。首先，温度可以是区间属性或比率属性，这取决于其测量标度。当温度用开尔文温标测量时，从物理意义上讲，2度的温度是1度的两倍；当温度用华氏或摄氏标度测量时则并非如此，因为这时1度温度与2度温度相差并不太多。31问题是从物理意义上讲，华氏和摄氏标度的零点是硬性规定的，因此，华氏或摄氏温度的比率并无物理意义。

4.用值的个数描述属性

区分属性的一种独立方法是根据属性可能取值的个数来判断。

• 离散的（discrete）　离散属性具有有限个值或无限可数个值。这样的属性可以是分类的（如邮政编码或ID号），也可以是数值的（如计数）。通常，离散属性用整数变量表示。二元属性（binary attribute）是离散属性的一种特殊情况，并只接受两个值，如真/假、是/否、男/女或0/1。通常，二元属性用布尔变量表示，或者用只取两个值0或1的整型变量表示。
• 连续的（continuous）　连续属性是取实数值的属性，如温度、高度或重量等属性。通常，连续属性用浮点变量表示。实践中，实数值能可以有限的精度测量和表示。

从理论上讲，任何测量标度类型（标称的、序数的、区间的和比率的）都可以与基于属性值个数的任意类型（二元的、离散的和连续的）组合。然而，有些组合并不常出现，或者没有什么意义。例如，很难想象一个实际数据集包含连续的二元属性。通常，标称和序数属性是二元的或离散的，而区间和比率属性是连续的。然而，计数属性（count attribute）是离散的，也是比率属性。

5.非对称的属性

对于非对称的属性（asymmetric attribute），出现非零属性值才是重要的。考虑这样一个数据集，其中每个对象是一个学生，而每个属性记录学生是否选修大学的某个课程。对于某个学生，如果他选修了对应某属性的课程，该属性取值1，否则取值0。由于学生只选修所有可选课程中的很小一部分，这种数据集的大部分值为0，因此，关注非零值将更有意义、32更有效。否则，如果在学生不选修的课程上做比较，则大部分学生都非常相似。只有非零值才重要的二元属性是非对称的二元属性。这类属性对于关联分析特别重要。关联分析将在第5章讨论。也可能有离散的或连续的非对称特征。例如，如果记录每门课程的学分，则结果数据集将包含非对称的离散属性或连续属性。

6.度量水平的总体评价

正如本章其余部分所描述的，数据有许多不同的类型。先前关于测量标度的讨论虽然有用，但并不完整，仍有一些局限。因此我们给出如下见解和指引。

• 相异性、有序性和有意义的区间及比率只是数据的四个属性——其他许多属性都是可能的。举例来讲，一些数据本质上是周期性的，例如地球表面上的位置或时间。再如，考虑值为集合的属性，其中每个属性值是一组元素的集合，例如去年看过的所有电影。如果第二个集合是第一个集合的子集，则定义第一个元素（电影）集合比第二个集合更大（包含）。但是，这种关系只是定义了一个与刚才定义的任何属性类型都不匹配的偏序。
• 用于表示属性值的数字或符号可能无法蕴含属性的所有性质，或者所蕴含的性质并不存在。例2.3给出了关于整数的说明，即ID的平均值和超出范围的年龄。
• 为分析目的数据经常进行转换——参见2.3.7节。通常将观测变量的分布改变为更容易分析的分布，例如高斯（正态）分布。这种转换只保留了原始值的顺序，其他的性质将会丢失。尽管如此，如果期望的结果是一个差异的统计检验或预测模型，那这种转换是合理的。
• 对任何数据分析的最终评估，包括对属性的操作，都是从专业领域的角度分析结果是否有意义。

总之，确定哪些操作可以在特定的属性或属性集合上执行，而不影响分析的完整性是十分具有挑战性的。幸运的是，既定的做法往往是一个可靠的指南，而有时候标准做法也有可能是错误的或有局限性的。

2.1.2　数据集的类型

数据集的类型有多种，并且随着数据挖掘的发展与成熟，还会有更多类型的数据集用于分析。本小节介绍一些很常见的类型。为方便起见，我们将数据集的类型分成三组：记录数据、基于图形的数据和有序数据。这些分类不能涵盖所有的可能性，肯定还存在其他的分组。

1.数据集的一般特性

在提供特定类型数据集的细节之前，我们先讨论适用于许多数据集的三个特性，即维度、分布和分辨率，它们对数据挖掘技术具有重要影响。
维度（dimensionality）　数据集的维度是数据集中的对象具有的属性数目。低维度数据往往与中、高维度数据有质的不同。事实上，分析高维数据有时会陷入所谓的维灾难（curse of dimensionality）。正因如此，数据预处理的一个重要动机就是减少维度，称为维归约（dimensionality reduction）。这些问题将在本章后面和附录B中更深入地讨论。
分布（distribution）　数据集的分布是构成数据对象的属性的各种值或值的集合出现的频率。同样，数据集的分布可以看作对数据空间各个区域中对象集中程度的描述。统计学家列举了许多分布的类型，如高斯分布（正态分布)，并描述了它们的性质（见附录C）。虽然描述分布的统计方法可以产生强大的分析技术，但是许多数据集的分布并没有被标准的统计分布很好地解释。
因此许多数据挖掘算法并没有为其分析的数据假定某个特定的统计分布。然而，分布的一般特性通常具有强烈的影响。例如，假设将类别属性用作类变量，其中一个类别在95％的情况下出现，而其他类别只在5%的情况下发生。正如4.11节所讨论的那样，这种分布的倾斜度（skewness）会使分类变得困难（倾斜度对数据分析有其他影响，这里不做讨论）。
倾斜数据的一个特例是稀疏性（sparsity）。对于稀疏的二进制、计数或连续数据，一个对象的大多数属性值为0。在许多情况下，非零项还不到1%。实际上，稀疏性是一个优点，因为通常只有非零值才需要存储和处理。这将节省大量的计算时间和存储空间。事实上，有些数据挖掘算法，如第5章介绍的关联规则挖掘算法，仅适合处理稀疏数据。最后，请注意稀疏数据集中的属性通常是非对称属性。
分辨率（resolution）　经常可以在不同的分辨率下得到数据，并且在不同的分辨率下数据的性质不同。例如，在几米的分辨率下，地球表面看上去很不平坦，但在数十公里的分辨率下却相对平坦。数据的模式也依赖于分辨率。如果分辨率太高，模式可能看不出，或者掩埋在噪声中；如果分辨率太低，模式可能不出现。例如，几小时记录一下气压变化可以反映出风暴等天气系统的移动；而在月的标度下，这些现象就检测不到。

2.记录数据

许多数据挖掘任务都假定数据集是记录（数据对象）的汇集，每个记录包含固定的数据字段（属性）集，如图2.2a所示。对于记录数据的大部分基本形式，记录之间或数据字段之间没有明显的联系，并且每个记录（对象）具有相同的属性集。记录数据通常存放在平展文件或关系数据库中。关系数据库当然不仅仅是记录的汇集，它还包含更多的信息，但是数据挖掘一般并不使用关系数据库的这些信息。35更确切地说，数据库是查找记录的方便场所。下面介绍不同类型的记录数据，并用图2.2加以说明。

事务数据或购物篮数据　事务数据（transaction data）是一种特殊类型的记录数据，其中每个记录（事务）涉及一系列的项。考虑一个杂货店。顾客一次购物所购买的商品的集合就构成一个事务，而购买的商品是项。这种类型的数据称为购物篮数据（market basket data），因为记录中的项是顾客“购物篮”中的商品。事务数据是项的集合的集族，但是也可以将它视为记录的集合，其中记录的字段是非对称的属性。这些属性常常是二元的，指出商品是否已买。36更一般地，这些属性还可以是离散的或连续的，例如表示购买的商品数量或购买商品的花费。图2.2b展示了一个事务数据集，每一行代表一位顾客在特定时间购买的商品。
数据矩阵　如果一个数据集族中的所有数据对象都具有相同的数值属性集，则数据对象可以看作多维空间中的点（向量），其中每个维代表对象的一个不同属性。这样的数据对象集可以用一个m×n的矩阵表示，其中，有m行（一个对象一行）n列（一个属性一列），也可以用列表示数据对象，用行表示属性。这种矩阵称作数据矩阵（data matrix）或模式矩阵（pattern matrix）。数据矩阵是记录数据的变体，但是，由于它由数值属性组成，可以使用标准的矩阵操作对数据进行变换和处理，因此，对于大部分统计数据，数据矩阵是一种标准的数据格式。图2.2c展示了一个样本数据矩阵。
稀疏数据矩阵　稀疏数据矩阵是数据矩阵的一种特殊情况，其中属性的类型相同并且是非对称的，即只有非零值才是重要的。事务数据是仅含0和1元素的稀疏数据矩阵的例子。另一个常见的例子是文档数据。特别地，如果忽略文档中词（术语）的次序——“词袋”法——则文档可以用词向量表示，其中每个词是向量的一个分量（属性），而每个分量的值是对应词在文档中出现的次数。文档集合的这种表示通常称作文档词矩阵（document-term matrix）。图2.2d显示了一个文档词矩阵。文档是该矩阵的行，而词是矩阵的列。实践应用时，仅存放稀疏数据矩阵的非零项。

3.基于图的数据

有时，图形可以方便而有效地表示数据。我们考虑两种特殊情况：（1）图捕获数据对象之间的联系；（2）数据对象本身用图表示。
带有对象之间联系的数据　对象之间的联系常常携带重要信息。在这种情况下，数据常常用图表示。一般把数据对象映射到图的结点，而对象之间的联系用对象之间的链和诸如方向、权值等链性质表示。考虑万维网上的网页，页面上包含文本和指向其他页面的链接。为了处理搜索查询，Web搜索引擎收集并处理网页，提取它们的内容。然而，众所周知，指向或出自每个页面的链接包含大量该页面与查询相关程度的信息，因而必须考虑。
图2.3a显示了相互链接的网页集。图数据的另一个重要例子是社交网络，其中的数据对象是人，人与人之间的联系是他们通过社交媒体进行的交互。
具有图对象的数据　如果对象具有结构，即对象包含具有联系的子对象，则这样的对象常常用图表示。例如，化合物的结构可以用图表示，其中结点是原子，结点之间的链是化学键。图2.3b给出化合物苯的分子结构示意图，其中包含碳原子（黑色）和氢原子（灰色）。图表示可以确定何种子结构频繁地出现在化合物的集合中，并且弄清楚这些子结构中是否有某种子结构与诸如熔点或生成热等特定的化学性质有关。频繁图挖掘是数据挖掘中分析这类数据的一个分支，将在6.5节讨论。

4.有序数据

对于某些数据类型，属性具有涉及时间或空间序的联系。下面介绍各种类型的有序数据，如图2.4所示。图2.3　不同的图形数据

时序事务数据　时序事务数据（sequential transaction data）可以看作事务数据的扩充，其中每个事务包含一个与之相关联的时间。考虑带有事务发生时间的零售事务数据。时间信息可以帮助我们发现“万圣节前夕糖果销售达到高峰”之类的模式。时间也可以与每个属性相关联，例如，每个记录可以是一位顾客的购物历史，包含不同时间购买的商品列表。使用这些信息，就有可能发现“购买DVD播放机的人趋向于在其后不久购买DVD”之类的模式。
图2.4a展示了一些时序事务数据。有5个不同的时间——t1、t2、t3、t4和t5，3位不同的顾客——C1、C2和C3，5种不同的商品——A、B、C、D和E。在图a上面的表中，每行对应一位顾客在特定的时间购买的商品。例如，在时间t3，顾客C2购买了商品A和D。下面的表显示相同的信息，但每行对应一位顾客。每行包含涉及该顾客的所有事务信息，其中每个事务包含一些商品和购买这些商品的时间，例如，顾客C3在时间t2购买了商品A和C。
时间序列数据　时间序列数据（time series data）是一种特殊的有序数据类型，其中每条记录都是一个时间序列（time series），即一段时间以来的测量序列。例如，金融数据集可能包含各种股票每日价格的时间序列对象。再例如，考虑图2.4c，该图显示明尼阿波利斯市从1982年到1994年的月平均气温的时间序列。在分析诸如时间序列的时间数据时，重要的是要考虑时间自相关（temporal autocorrelation），即如果两个测量的时间很接近，则这些测量的值通常非常相似。
序列数据　序列数据（sequence data）是一个38　～40数据集合，它是各个实体的序列，如词或字母的序列。除没有时间戳之外，它与时序数据非常相似，只是有序序列考虑项的位置。例如，动植物的遗传信息可以用称作基因的核苷酸的序列表示，与遗传序列数据有关的许多问题都涉及由核苷酸序列的相似性预测基因结构和功能的相似性。图2.4b显示用4种核苷酸表示的一段人类基因码。所有的DNA都可以由A、T、G和C四种核苷酸构造。
空间和时空数据　有些对象除了其他类型的属性之外，还具有空间属性，如位置或区域。空间数据的一个例子是从不同的地理位置收集的气象数据（降水量、气温、气压）。这些测量通常是随时间收集的，因此，这些数据由不同位置的时间序列组成。在这种情况下，我们将数据称为时空数据。虽然可以对每个特定的时间或位置分别进行分析，但对时空数据更完整的分析需要考虑数据的时间和空间两个方面。
空间数据的一个重要方面是空间自相关性（spatial autocorrelation），即物理上靠近的对象趋于在其他方面也相似。因此，地球上两个相互靠近的点通常具有相近的气温和降水量。值得注意的是，空间自相关性类似于时间自相关性。
空间和时空数据的重要例子是科学和工程数据集，其数据取自二维或三维网格上规则或不规则分布的点上的测量或模型输出结果。例如，地球科学数据集记录在各种分辨率（如每度）下经纬度球面网格点（网格单元）上测量的温度和气压，如经纬度都为1°。另一个例子是，在瓦斯气流模拟中，可以针对模拟中的每个网格点记录不同时刻的流速和方向。还有一种不同类型的时空数据来自在时间和空间中追踪物体（例如车辆）的轨迹。

5.处理非记录数据

大部分数据挖掘算法都是为记录数据或其变体（如事务数据和数据矩阵）设计的。通过从数据对象中提取特征，并使用这些特征创建对应于每个对象的记录，针对记录数据的技术也可以用于非记录数据。考虑前面介绍的化学结构数据。给定一个常见的子结构集合，每个化合物都可以用一个具有二元属性的记录表示，这些二元属性指出化合物是否包含特定的子结构。41这样的表示实际上是事务数据集，其中事务是化合物，而项是子结构。
在某些情况下，容易用记录形式表示数据，但是这类表示并不能捕获数据中的所有信息。考虑这样的时空数据，它由空间网格每一点上的时间序列组成。通常，这种数据存放在数据矩阵中，其中每行代表一个位置，而每列代表一个特定的时间点。然而，这种表示并不能明确地表示属性之间存在的时间联系以及对象之间存在的空间联系。但并不是说这种表示不合适，而是说分析时必须考虑这些联系。例如，在使用数据挖掘技术时，忽略属性的时间自相关性或数据对象的空间自相关性（即空间网格上的位置）并不是一个好主意。

2.2　数据质量

数据挖掘算法通常用于为其他目的收集的数据，或者在收集时未明确其目的。因此，数据挖掘常常不能“在数据源头控制质量”。相比之下，统计学的实验设计或调查中，其数据质量往往都达到了一定的要求。由于无法避免数据质量问题，因此数据挖掘着眼于两个方面：（1）数据质量问题的检测和纠正；（2）使用可以容忍低质量数据的算法。第一步的检测和纠正，通常称作数据清理（data cleaning）。
下面几小节讨论数据质量。尽管也讨论某些与应用有关的问题，但是关注的焦点是测量和数据收集问题。

2.2.1　测量和数据收集问题

期望数据完美是不现实的。人类的错误、测量设备的限制或数据收集过程中的漏洞都可能导致问题。数据的值乃至整个数据对象都可能会丢失。在有些情况下，可能有不真实或重复的对象，即对应于单个“实际”对象出现了多个数据对象。例如，对于一个最近住过两个不同地方的人，42可能有两个不同的记录。即使所有的数据都不缺，并且“看上去很好”，也可能存在不一致，如一个人身高2m，但体重只有2kg。
下面我们关注数据测量和收集方面的数据质量问题。我们先定义测量误差和数据收集错误，然后考虑涉及测量误差的各种问题：噪声、伪像、偏置、精度和准确率。最后讨论同时涉及测量和数据收集的数据质量问题：离群点、遗漏和不一致的值、重复数据。

1.测量误差和数据收集错误

术语测量误差（measurement error）是指测量过程中产生的问题。一个常见的问题是：在某种程度上，记录的值与实际值不同。对于连续属性，测量值与实际值的差称为误差（error）。术语数据收集错误（data collection error）是指诸如遗漏数据对象或属性值，或者不当地包含了其他数据对象等错误。例如，一种特定种类动物研究可能包含了相关种类的其他动物，它们只是表面上与要研究的种类相似。测量误差和数据收集错误可能是系统的也可能是随机的。
我们只考虑一般的错误类型。在特定的领域中，总有某些类型的错误是常见的，并且通常存在很好的技术，能检测并纠正这些错误。例如，人工输入数据时，键盘录入错误是常见的，因此许多数据输入程序具有检测技术，并通过人工干预纠正这类错误。

2.噪声和伪像

噪声是测量误差的随机部分。这通常涉及值被扭曲或加入了谬误对象。图2.5显示了被随机噪声干扰前后的时间序列。如果在时间序列上添加更多的噪声，形状将会消失。图2.6显示了三组添加一些噪声点（用“+”表示）前后的数据点集。注意，有些噪声点与非噪声点混在一起。

术语“噪声”通常用于包含时间或空间分量的数据。在这些情况下，常常可以使用信号或图像处理技术降低噪声，从而帮助发现可能“淹没在噪声中”的模式（信号）。尽管如此，完全消除噪声通常是困难的，而许多数据挖掘工作都关注设计鲁棒算法（robust algorithm），即在噪声干扰下也能产生可以接受的结果。
数据错误可能是更确定性现象的结果，如一组照片在同一地方出现条纹。数据的这种确定性失真常称作伪像（artifact）。

3.精度、偏置和准确率

在统计学和实验科学中，测量过程和结果数据是用精度和偏置度量的。我们给出标准的定义，随后简略加以讨论。对于下面的定义，我们假定对相同的基本量进行重复测量。
定义2.3 精度（precision）　（同一个量的）重复测量值之间的接近程度。
定义2.4 偏置（bias）　测量值与被测量之间的系统的变化。精度通常用值集合的标准差度量，而偏置用值集合的均值与测出的已知值之间的差度量。只有那些通过外部手段能够得到测量值的对象，偏置才是可确定的。假定我们有1g质量的标准实验室重量，并且想评估实验室的新天平的精度和偏置。我们称重5次，得到下列值：{1.015，0.990，1.013，1.001，0.986}。这些值的均值是1.001，因此偏置是0.001。用标准差度量，精度是0.013。
通常使用更一般的术语准确率表示数据测量误差的程度。
定义2.5准确率（accuracy）　被测量的测量值与实际值之间的接近度。
准确率依赖于精度和偏置，但是没有用这两个量表达准确率的公式。
准确率的一个重要方面是有效数字（significant digit）的使用。其目标是仅使用数据精度所能确定的数字位数表示测量或计算结果。例如，对象的长度用最小刻度为毫米的米尺测量，则我们只能记录最接近毫米的长度数据，这种测量的精度为±0.5mm。这里不再详细地讨论有效数字，因为大部分读者应当在先前的课程中接触过，并且在理工科和统计学教材中讨论得相当深入。
诸如有效数字、精度、偏置和准确率问题常常被忽视，但是对于数据挖掘、统计学和自然科学，它们都非常重要。通常，数据集并不包含数据精度信息，用于分析的程序返回的结果也没有这方面的信息。45但是，缺乏对数据和结果准确率的理解，分析者将可能出现严重的数据分析错误。

4.离群点

离群点（outlier）是在某种意义上具有不同于数据集中其他大部分数据对象的特征的数据对象，或是相对于该属性的典型值来说不寻常的属性值。我们也称其为异常（anomalous）对象或异常值。有许多定义离群点的方法，并且统计学和数据挖掘界已经提出了很多不同的定义。此外，区别噪声和离群点这两个概念是非常重要的。与噪声不同，离群点可以是合法的数据对象或值。例如，在欺诈和网络入侵检测中，目标就是在大量的正常对象或事件中找到异常对象或事件。第9章会更详细地讨论异常检测。

5.遗漏值

一个对象遗漏一个或多个属性值的情况并不少见。有时可能会出现信息收集不全的情况，例如有的人拒绝透露年龄或体重。还有些情况下，某些属性并不能用于所有对象，例如表格常常有条件选择部分，仅当填表人以特定的方式回答前面的问题时，条件选择部分才需要填写，但为简单起见存储了表格的所有字段。无论何种情况，在数据分析时都应当考虑遗漏值。
有许多处理遗漏值的策略（和这些策略的变种），每种策略适用于特定的情况。这些策略在下面列出，同时我们指出它们的优缺点。
删除数据对象或属性　一种简单而有效的策略是刪除具有遗漏值的数据对象。然而，即使不完整的数据对象也包含一些有用的信息，并且，如果许多对象都有遗漏值，则很难甚至不可能进行可靠的分析。尽管如此，如果某个数据集只有少量的对象具有遗漏值，则忽略它们可能是合算的。一种与之相关的策略是删除具有遗漏值的属性。然而，做这件事要小心，46因为被删除的属性可能对分析是至关重要的。
估计遗漏值　有时，遗漏值可以可靠地估计。例如，在考虑以大致平滑的方式变化的、具有少量但分散的遗漏值的时间序列时，遗漏值可以使用其他值来估计（插值）。另举一例，考虑一个具有许多相似数据点的数据集，与具有遗漏值的点邻近的点的属性值常常可以用来估计遗漏的值。如果属性是连续的，则可以使用最近邻的平均属性值；如果属性是分类的，则可以取最近邻中最常出现的属性值。为了更具体地解释，考虑地面站记录的降水量，对于未设地面站的区域，降水量可以使用邻近地面站的观测值估计。
在分析时忽略遗漏值　许多数据挖掘方法都可以修改，以忽略遗漏值。例如，假定正在对数据对象聚类，需要计算各对数据对象间的相似性。如果某对数据对象的一个对象或两个对象的某些属性有遗漏值，则可以仅使用没有遗漏值的属性来计算相似性。当然，这种相似性只是近似的，但是除非整个属性数目很少，或者遗漏值的数量很大，否则这种误差影响不大。同样，许多分类方法都可以修改，以便于处理遗漏值。

6.不一致的值

数据可能包含不一致的值。比如地址字段列出了邮政编码和城市名，但是有的邮政编码区域并不包含在对应的城市中。这可能是人工输入该信息时颠倒了两个数字，或许是在扫描手写体时错读了一个数字。无论导致不一致值的原因是什么，重要的是能检测出来，并且如果可能的话，纠正这种错误。
有些不一致类型容易检测，例如人的身高不应当是负的。另一些情况下，可能需要查阅外部信息源，例如当保险公司处理赔偿要求时，它将对照顾客数据库核对赔偿单上的姓名与地址。
检测到不一致后，有时可以对数据进行更正。产品代码可能有“校验”数字，或者可以通过一个备案的已知产品代码列表复核产品代码，如果发现它不正确但接近一个已知代码，则纠正它。纠正不一致需要额外的或冗余的信息。
例2.6 不一致的海洋表面温度　该例解释实际的时间序列数据中的不一致性。这些数据是在海洋的不同点测量的海洋表面温度（SST）。最初人们利用船或浮标使用海洋测量方法收集SST数据，而最近开始使用卫星来收集这些数据。为了创建长期的数据集，需要使用这两种数据源。然而，由于数据来自不同的数据源，两部分数据存在微妙的不同。这种差异显示在图2.7中，该图显示了各年度之间SST值的相关性。如果某两个年度的SST值是正相关的，则对应于这两年的位置为白色，否则为黑色。（季节性的变化从数据中删除，否则所有的年都是高度相关的。）数据汇集在一起的地方（1983年）有一个明显的变化。在1958～1982年和1983～1999年两组中，每组内的年相互之间趋向于正相关，但与另一组的年负相关。这并不意味着该数据不能用，但是分析者应当考虑这种差异对数据挖掘分析的潜在影响。

7.重复数据

数据集可以包含重复或几乎重复的数据对象。许多人都收到过重复的邮件，因为它们以稍微不相同的名字多次出现在数据库中。为了检测并删除这种重复，必须处理两个主要问题。首先，如果两个对象实际代表同一个对象，则对应的属性值必然不同，必须解决这些不一致的值；其次，需要避免意外地将两个相似但并非重复的数据对象（如两个人具有相同姓名）合并在一起。术语去重复（deduplication）通常用来表示处理这些问题的过程。
在某些情况下，两个或多个对象在数据库的属性度量上是相同的，但是仍然代表不同的对象。这种重复是合法的。但是，如果某些算法设计中没有专门考虑这些属性可能相同的对象，就还是会导致问题。本章习题13就是这样的一个例子。

2.2.2　关于应用的问题

数据质量问题也可以从应用角度考虑，表达为“数据是高质量的，如果它适合预期的应用”。特别是对工商界，数据质量的这种提议非常有用。类似的观点也出现在统计学和实验科学中，那里强调精心设计实验来收集与特定假设相关的数据。与测量和数据收集一样，许多数据质量问题与特定的应用和领域有关。我们这里仍然只考虑一些一般性问题。
时效性　有些数据在收集后就开始老化。比如说，如果数据提供正在发生的现象或过程的快照，如顾客的购买行为或Web浏览模式，则快照只代表有限时间内的真实情况。如果数据已经过时，则基于它的模型和模式也已经过时。49
相关性　可用的数据必须包含应用所需要的信息。考虑构造一个模型，预测交通事故发生率。如果忽略了驾驶员的年龄和性别信息，那么除非这些信息可以间接地通过其他属性得到，否则模型的准确率可能是有限的。
确保数据集中的对象相关不太容易。一个常见问题是抽样偏置（sampling bias），指样本包含的不同类型的对象与它们在总体中的出现情况不成比例。例如调查数据只反映对调查做出响应的那些人的意见。（抽样的其他问题将在2.3.2节进一步讨论。）由于数据分析的结果只能反映现有的数据，抽样偏置通常会导致不正确的分析。
关于数据的知识　理想情况下，数据集附有描述数据的文档。文档的质量好坏决定它是支持还是干扰其后的分析。例如，如果文档标明若干属性是强相关的，则说明这些属性可能提供了高度冗余的信息，我们通常只保留一个属性。（考虑销售税和销售价格。）然而，如果文档很糟糕，例如，没有告诉我们某特定字段上的遗漏值用-9999表示，则我们的数据分析就可能出问题。其他应该说明的重要特性是数据精度、特征的类型（标称的、序数的、区间的、比率的）、测量的刻度（如长度用米还是英尺）和数据的来源。

2.3　数据预处理

本节我们考虑应当采用哪些预处理步骤，让数据更加适合挖掘。数据预处理是一个广泛的领域，包含大量以复杂的方式相关联的不同策略和技术。我们将讨论一些最重要的思想和方法，并试图指出它们之间的相互联系。具体地说，我们将讨论如下主题。

• 聚集
• 抽样
• 维归约50
• 特征子集选择
• 特征创建
• 离散化和二元化
• 变量变换

粗略地说，这些主题分为两类，即选择分析所需要的数据对象和属性，以及创建/改变属性。这两种情况的目标都是改善数据挖掘分析工作，减少时间，降低成本，提高质量。细节参见以下几小节。
术语注记：在下面的内容中，我们有时根据习惯用法，使用特征（feature）或变量（variable）指代属性（attribute）。

2.3.1　聚集

有时，“少就是多”，而聚集就是如此。聚集（aggregation）将两个或多个对象合并成单个对象。考虑一个由事务（数据对象）组成的数据集，它记录一年中不同日期在各地（Minneapolis Chicago……）商店的商品日销售情况，见表2.4。对该数据集的事务进行聚集的一种方法是，用一个商店的事务替换该商店的所有事务。这把每天出现在一个商店的成百上千个事务记录归约成单个日事务，而每天的数据对象的个数减少为商店的个数。

在这里，一个显而易见的问题是如何创建聚集事务，即在创建代表单个商店或日期的聚集事务时，如何合并所有记录的每个属性的值。定量属性（如价格）通常通过求和或求平均值进行聚集。定性属性（如商品）可以忽略，也可以用更高层次的类别来概括，例如电视和电子产品。
表2.4中的数据也可以看作多维数组，其中每个属性是一个维。从这个角度，聚集是删除属性（如商品类型）的过程，或者是压缩特定属性不同值个数的过程，如将日期的可能值从365天压缩到12个月。这种类型的聚集通常用于联机分析处理（OnLine Analytical Processing，OLAP），OLAP的引用在参考文献中给出。
51聚集的动机有多种。首先，数据归约导致的较小数据集需要较少的内存和处理时间，因此可以使用开销更大的数据挖掘算法。其次，通过高层而不是低层数据视图，聚集起到了范围或标度转换的作用。在前面的例子中，在商店位置和月份上的聚集给出数据按月、按商店，而不是按天、按商品的视图。最后，对象或属性群的行为通常比单个对象或属性的行为更加稳定。这反映了统计学事实：相对于被聚集的单个对象，诸如平均值、总数等聚集量具有较小的变异性。对于总数，实际变差大于单个对象的（平均）变差，但是变差的百分比较小；而对于均值，实际变差小于单个对象的（平均）变差。聚集的缺点是可能丢失有趣的细节。在商店的例子中，按月的聚集就丢失了星期几具有最高销售额的信息。
例2.7 澳大利亚降水量　该例基于澳大利亚从1982年到1993年的降水量。我们把澳大利亚国土按经纬度0.5°乘以0.5°大小分成3030个网格。图2.8a的直方图显示了这些网格单元上的平均月降水量的标准差。而图2.8b的直方图显示了相同位置的平均年降水量的标准差。可见，平均年降水量比平均月降水量的变异性小。所有降水量的测量（以及它们的标准差）都以厘米（cm）为单位。

2.3.2　抽样

抽样是一种选择数据对象子集进行分析的常用方法。在统计学中，抽样长期用于数据的事先调查和最终的数据分析。52在数据挖掘中，抽样也非常有用。然而，在统计学和数据挖掘中，抽样的动机并不相同。统计学家使用抽样的原因是获取感兴趣的整个数据集的代价太高并且太费时间，而数据挖掘人员进行抽样，通常是因为处理所有数据所需的内存或时间方面的计算成本太高。在某些情况下，使用抽样的算法可以压缩数据量，以便可以使用更好但开销较大的数据挖掘算法。
有效抽样的主要原理如下：如果样本是有代表性的，则使用样本与使用整个数据集的效果几乎一样。反过来说，若样本近似地具有与原数据集相同的（感兴趣的）性质，则称样本是有代表性的。如果数据对象的均值（平均值）是感兴趣的性质，而样本具有近似于原数据集的均值，则样本就是有代表性的。由于抽样是一个统计过程，特定样本的代表性是不一样的，因此最好能做的就是选择一个抽样方案，以确保以很高的概率得到有代表性的样本。如下所述，这涉及选择适当的样本容量以及抽样技术。

1.抽样方法

有许多抽样技术，但是这里只介绍少量最基本的抽样技术及其变种。最简单的抽样是简单随机抽样（simple random sampling）。53对于这种抽样，选取任何特定项的概率相等。随机抽样有两种变种（其他抽样技术也一样）：（1）无放回抽样——每个选中项立即从构成总体的所有对象集中删除；（2）有放回抽样——对象被选中时不从总体中删除。在有放回抽样中，相同的对象可能被多次抽出。当样本与数据集相比相对较小时，两种方法产生的样本差别不大。但是对于分析，有放回抽样较为简单，因为在抽样过程中，每个对象被选中的概率保持不变。
当总体由不同类型的对象组成并且每种类型的对象数量差别很大时，简单随机抽样不能充分地代表不太频繁出现的对象类型。在分析需要所有类型的代表时，这可能出现问题。例如，当为稀有类构建分类模型时，样本中适当地提供稀有类是至关重要的，因此需要提供具有不同频率的感兴趣的项的抽样方案。分层抽样（stratified sampling）就是这样的方法，它从预先指定的组开始抽样。在最简单的情况下，尽管每组的大小不同，但是从每组抽取的对象个数相同。另一种变种是从每一组对象抽取的样本数量正比于该组的大小。
例2.8 抽样与信息损失　一旦选定抽样技术，就需要选择样本容量。较大的样本容量增大了样本具有代表性的概率，但也抵消了抽样带来的许多好处。反过来，使用较小容量的样本，可能丢失模式或检测出错误的模式。图2.9a显示了包含8000个二维点的数据集，而图2.9b和图2.9c显示了从该数据集抽取的容量分别为2000和500的样本。该数据集的大部分结构都出现在2000个点的样本中，但是许多结构在500个点的样本中丢失了。

例2.9 确定合适的样本容量　为了说明确定合适的样本容量需要系统的方法，考虑下面的任务。

使用抽样可以有效地解决该问题。一种方法是取数据点的一个小样本，逐对计算点之间的相似性，然后形成高度相似的点组。从每个点组取一个点，则可以得到具有代表性的点的集合。然而，按照该方法，我们需要确定样本的容量，它以很高的概率确保得到期望的结果，即从每个簇至少找出一个代表点。图2.10b显示了随着样本容量从10变化到60，从10个组的每一个组中得到一个对象的概率。有趣的是，使用容量为20的样本，只有很小的机会（20%)得到包含所有10个组的样本。即便使用容量为30的样本，得到不包含所有10个组中对象的样本的概率也很高（几乎40%）。该问题将在第7章习题4讨论聚类时进一步考察。

2.渐进抽样

由于可能很难确定合适的样本容量，因此有时需要使用自适应（adaptive）或渐进抽样（progressive sampling）方法。这些方法从一个小样本开始，然后增加样本容量直至得到足够容量的样本。尽管这种技术不需要在一开始就确定正确的样本容量，但是需要评估样本的方法，确定它是否足够大。
例如，假定使用渐进抽样来学习一个预测模型。尽管预测模型的准确率随样本容量的增加而增加，但是在某一点准确率的增加趋于稳定。我们希望在稳定点停止增加样本容量。通过掌握模型准确率随样本逐渐增大的变化情况，并通过选取接近于当前容量的其他样本，我们可以估计出与稳定点的接近程度，从而停止抽样。

2.3.3　维归约

数据集可能包含大量特征。考虑一个文档的集合，其中每个文档是一个向量，其分量是文档中每个词出现的频率。在这种情况下，通常有成千上万的属性（分量），每个代表词汇表中的一个词。再看一个例子，考虑包含过去30年各种股票日收盘价的时间序列数据集。在这种情况下，属性是特定日期的价格，也数以千计。
维归约有多方面的好处。关键的好处是，如果维度（数据属性的个数）较低，许多数据挖掘算法的效果就会更好。部分是因为维归约可以删除不相关的特征并降低噪声，另一部分是因为维灾难。（维灾难在下面解释。）还有一个好处是维归约可以使模型更容易理解，因为模型可能只涉及较少的属性。此外，维归约也可以更容易让数据可视化。即使维归约没有将数据归约到二维或三维，数据也可以通过观察属性对或三元组属性达到可视化，并且这种组合的数目也会大大减少。最后，使用维归约降低了数据挖掘算法的时间和内存需求。
术语“维归约”通常用于这样的技术：通过创建新属性，将一些旧属性合并在一起以降低数据集的维度。通过选择旧属性的子集得到新属性，这种维归约称为特征子集选择或特征选择。特征选择将在2.3.4节讨论。
下面简单介绍两个重要的主题：维灾难和基于线性代数方法（如主成分分析）的维归约技术。更多关于维归约的内容可查看附录B。

1.维灾难

维灾难是指这样的现象：随着数据维度的增加，许多数据分析变得非常困难。特别是随着维度增加，数据在它所占据的空间中越来越稀疏。因此，我们观测到的数据对象很可能不是总体数据对象的代表性样本。对于分类，这可能意味着没有足够的数据对象来创建模型，将所有可能的对象可靠地指派到一个类。对于聚类，点之间的密度和距离的定义（对聚类是至关重要的）失去了意义。（8.1.2节、8.4.6节和8.4.8节会进一步讨论。）结果是，对于高维数据，许多分类和聚类算法（以及其他的数据分析算法）都麻烦缠身——分类准确率降低，聚类质量下降。

2.维归约的线性代数技术

维归约的一些最常用的方法是使用线性代数技术，将数据由高维空间投影到低维空间，特别是对于连续数据。主成分分析（Principal Component Analysis，PCA）是一种用于连续属性的线性代数技术，它找出新的属性（主成分），这些属性是原属性的线性组合，是相互正交的（orthogonal），并且捕获了数据的最大变差。例如，前两个主成分是两个正交属性，是原属性的线性组合，尽可能多地捕获了数据的变差。奇异值分解（Singular Value Decomposition，SVD）是一种线性代数技术，它与PCA有关，并且也用于维归约。请参考附录A和B获取更多细节。

2.3.4　特征子集选择

降低维度的另一种方法是仅使用特征的一个子集。这种方法尽管看起来可能丢失信息，但是在存在冗余或不相关的特征的时候，情况并非如此。冗余特征重复了包含在一个或多个其他属性中的许多或所有信息。例如，一种产品的购买价格和所支付的销售税额包含许多相同的信息。不相关特征包含对于手头的数据挖掘任务几乎完全没用的信息，例如学生的ID号码对于预测学生的总平均成绩是不相关的。冗余和不相关的特征可能降低分类的准确率，影响所发现的聚类的质量。
尽管使用常识或领域知识可以立即消除一些不相关的和冗余的属性，但是选择最佳的特征子集通常需要系统的方法。特征选择的理想方法是：将所有可能的特征子集作为感兴趣的数据挖掘算法的输入，然后选取能产生最好结果的子集。这种方法的优点是反映了最终使用的数据挖掘算法的目的和偏爱。然而，由于涉及n个属性的子集多达2n个，这种方法在大部分情况下行不通，因此需要其他策略。有三种标准的特征选择方法：嵌入、过滤和包装。
嵌入方法（embedded approach）　特征选择作为数据挖掘算法的一部分是理所当然的。特别是在数据挖掘算法运行期间，算法本身决定使用哪些属性和忽略哪些属性。构造决策树分类器的算法（在第3章讨论）通常以这种方式运行。
过滤方法（filter approach）　使用某种独立于数据挖掘任务的方法，在数据挖掘算法运行前进行特征选择，例如我们可以选择属性的集合，它的属性对之间的相关度尽可能低。
包装方法（wrapper approach）　这些方法将目标数据挖掘算法作为黑盒，使用类似于前面介绍的理想算法，但通常并不枚举所有可能的子集来找出最佳属性子集。
由于嵌入方法与具体的算法有关，这里我们只进一步讨论过滤和包装方法。

1.特征子集选择体系结构

可以将过滤和包装方法放到一个共同的体系结构中。特征选择过程可以看作由四部分组成：子集评估度量、控制新的特征子集产生的搜索策略、停止搜索判断和验证过程。过滤方法和包装方法的唯一不同是它们使用了不同的特征子集评估方法。对于包装方法，子集评估使用目标数据挖掘算法；对于过滤方法，子集评估技术不同于目标数据挖掘算法。下面的讨论提供了该方法的一些细节，汇总在图2.11中。

从概念上讲，特征子集选择是搜索所有可能的特征子集的过程。可以使用许多不同类型的搜索策略，但是搜索策略的计算花费应当较低，并且应当找到最优或近似最优的特征子集。通常不可能同时满足这两个要求，因此需要折中。
搜索的一个不可缺少的组成部分是评估步骤，根据已经考虑的子集评价当前的特征子集。这需要一种评估度量，针对诸如分类或聚类等数据挖掘任务，确定属性特征子集的质量。对于过滤方法，这种度量试图预测实际的数据挖掘算法在给定的属性集上执行的效果如何；对于包装方法，评估包括实际运行目标数据挖掘应用，子集评估函数就是通常用于度量数据挖掘结果的评判标准。
因为子集的数量可能很大，考察所有的子集可能不现实，所以需要某种停止搜索判断。其策略通常基于如下一个或多个条件：迭代次数，子集评估的度量值是否最优或超过给定的阈值，一个特定大小的子集是否已经得到，使用搜索策略得到的选择是否可以实现改进。
最后，一旦选定特征子集，就要验证目标数据挖掘算法在选定子集上的结果。一种直截了当的评估方法是用全部特征的集合运行算法，并将使用全部特征得到的结果与使用该特征子集得到的结果进行比较。如果顺利的话，使用特征子集产生的结果将比使用所有特征产生的结果更好，或者至少几乎一样好。另一个验证方法是使用一些不同的特征选择算法得到特征子集，然后比较数据挖掘算法在每个子集上的运行结果。

2.特征加权

特征加权是另一种保留或删除特征的办法。特征越重要，赋予它的权值越大，而对于不太重要的特征，赋予它的权值较小。有时，这些权值可以根据特征的相对重要性的领域知识确定，也可以自动确定。例如，有些分类方法，如支持向量机（见第4章），产生分类模型，其中每个特征都赋予一个权值。具有较大权值的特征在模型中所起的作用更加重要。在计算余弦相似度时进行的对象规范化（2.4.5节）也可以看作一类特征加权。

2.3.5　特征创建

经常可以由原来的属性创建新的属性集，以更有效地捕获数据集中的重要信息。此外，新属性的数目可能比原属性少，使得我们可以获得前面介绍的维归约带来的所有好处。下面介绍两种创建新属性的相关方法：特征提取和映射数据到新的空间。

1.特征提取

由原始数据创建新的特征集称作特征提取（feature extraction)。考虑照片的集合，按照照片是否包含人脸分类。原始数据是像素的集合，因此对于许多分类算法都不适合。然而，如果对数据进行处理，提供一些较高层次的特征，诸如与人脸高度相关的某些类型的边和区域等，则会有更多的分类技术可以用于该问题。
可是，最常使用的特征提取技术都是高度针对具体领域的。对于特定的领域，如图像处理，在过去一段时间已经开发了各种提取特征的技术，但是这些技术在其他领域的应用却是有限的。因而，一旦将数据挖掘用于一个相对较新的领域，一个关键任务就是开发新的特征和特征提取方法。
虽然特征提取通常很复杂，但例2.10说明了它也可以相对简单。
例2.10 密度　考虑一个包含历史文物信息的数据集。该数据集包含每个文物的体积和质量，以及其他信息。为简单起见，假定这些文物使用少量材料（木材、陶土、铜、黄金）制造，并且我们希望根据制造材料对它们分类。在此情况下，由质量和体积特征构造的密度特征（即密度=质量/体积）可以很直接地产生准确的分类。尽管有一些人试图通过考察已有特征的简单数学组合来自动地进行特征提取，但是最常见的方法还是使用专家的意见构造特征。

2.映射数据到新的空间

使用一种完全不同的视角挖掘数据可能揭示出重要和有趣的特征。例如，考虑时间序列数据，它们常常包含周期模式。如果只有单个周期模式，并且噪声不多，则容易检测到该模式；另一方面，如果有大量周期模式，并且存在大量噪声，则很难检测这些模式。尽管如此，通过对该时间序列实施傅里叶变换（Fourier transform)，将它转换成频率信息明显的表示，就能检测到这些模式。在例2.11中，不必知道傅里叶变换的细节，只需要知道对于时间序列，傅里叶变换产生属性与频率有关的新数据对象就足够了。
例2.11 傅里叶分析　图2.12b中的时间序列是其他三个时间序列的和，其中两个显示在图2.12a中，其频率分别是每秒7个和17个周期，第三个时间序列是随机噪声。图2.12c显示功率频谱。在对原时间序列施加傅里叶变换后，可以计算功率频谱。（非正式地看，功率频谱正比于每个频率属性的平方。）尽管有噪声，图中有两个尖峰，对应于两个原来的、无噪声的时间序列的周期。值得注意的是，本例的要点是：好的特征可以揭示数据的重要性质。

也可以采用许多其他类型的变换。除傅里叶变换外，对于时间序列和其他类型的数据，经证实小波变换（wavelet transform)也是非常有用的。

2.3.6　离散化和二元化

有些数据挖掘算法，特别是某些分类算法，要求数据是分类属性形式。发现关联模式的算法要求数据是二元属性形式。这样，常常需要将连续属性变换成分类属性（离散化，discretization），并且连续和离散属性可能都需要变换成一个或多个二元属性（二元化（binarization）)。此外，如果一个分类属性具有大量不同值（类别），或者某些值出现不频繁，则对于某些数据挖掘任务，通过合并某些值减少类别的数目可能是有益的。
与特征选择一样，最佳的离散化和二元化方法是“对于用来分析数据的数据挖掘算法，产生最好结果”的方法。直接使用这种判别标准通常是不实际的。因此，离散化和二元化一般要满足这样一种判别标准，它与所考虑的数据挖掘任务的性能好坏直接相关。一般来说，63最佳的离散化取决于所使用的算法，以及其他被考虑的属性。然而，通常情况下，每个属性的离散化是相互独立的。

1.二元化

一种分类属性二元化的简单技术如下：如果有m个分类值，则将每个原始值唯一地赋予区间［0，m-1］中的一个整数。如果属性是有序的，则赋值必须保持序关系。（注意，即使属性原来就用整数表示，但如果这些整数不在区间［0，m-1］中，则该过程也是必需的。）然后，将这m个整数的每一个都变换成一个二进制数。由于需要n=log2m个二进位表示这些整数，因此要使用n个二元属性表示这些二进制数。例如，一个具有5个值{awful，poor，OK，good，great}的分类变量需要3个二元变量x1、x2、x3。变换见表2.5。

这样的变换可能导致复杂化，如无意之中建立了变换后的属性之间的联系。例如，在表2.5中，属性x2和x3是相关的，因为good值使用这两个属性表示。此外，关联分析需要非对称的二元属性，其中只有属性的出现（值为1）才是重要的。因此，对于关联问题，需要为每一个分类值引入一个二元属性，如表2.6所示。如果得到的属性的个数太多，则可以在二元化之前使用下一节介绍的技术减少分类值的个数。

同样，对于关联问题，可能需要用两个非对称的二元属性替换单个二元属性。考虑记录人的性别（男、女）的二元属性，对于传统的关联规则算法，该信息需要变换成两个非对称的二元属性，其中一个仅当是男性时为1，而另一个仅当是女性时为1。（对于非对称的二元属性，由于其提供一个二进制位信息需要占用存储器的两个二进制位，因而在信息的表示上不太有效。)

2.连续属性离散化

通常，离散化应用于在分类或关联分析中使用到的属性上。连续属性变换成分类属性涉及两个子任务：决定需要多少个分类值n，以及确定如何将连续属性值映射到这些分类值。在第一步中，将连续属性值排序后，通过指定n-1个分割点（split point)把它们分成n个区间。在颇为平凡的第二步中，将一个区间中的所有值映射到相同的分类值。因此，离散化问题就是决定选择多少个分割点和确定分割点位置的问题。结果可以用区间集合{（x0，x1］，（x1，x2］，…，（xn-1，xn)}表示，其中x0和xn可以分别为-∞或+∞，或者用一系列不等式x0＜x≤x1,…，xn-1＜x＜xn表示。
无监督离散化　用于分类的离散化方法之间的根本区别在于使用类信息（监督（supervised）)还是不使用类信息（无监督（unsupervised））。如果不使用类信息，则常使用一些相对简单的方法。例如，等宽（equal width）方法将属性的值域划分成具有相同宽度的区间，而区间的个数由用户指定。这种方法可能受离群点的影响而性能不佳，因此等频率（equal frequency）或等深（equal depth）方法通常更为可取。等频率方法试图将相同数量的对象放进每个区间。作为无监督离散化的另一个例子，可以使用诸如K均值（见第7章）等聚类方法。最后，目测检查数据有时也可能是一种有效的方法。
例2.12 离散化技术　本例解释如何对实际数据集使用这些技术。图2.13a显示了属于4个不同组的数据点，以及两个离群点——位于两边的大点。可以使用上述技术将这些数据点的x值离散化成4个分类值。（数据集中的点具有随机的y分量，可以更容易地看出每组有多少个点。）尽管目测检查该数据的方法的效果很好，但不是自动的，因此我们主要讨论其他三种方法。使用等宽、等频率和K均值技术产生的分割点分别如图2.13b、图2.13c和图2.13d所示，图中分割点用虚线表示。

在这个特定的例子中，如果用不同组的不同对象被指派到相同分类值的程度来度量离散化技术的性能，则K均值性能最好，其次是等频率，最后是等宽。更一般地说，最好的离散化将取决于应用场景并且通常涉及领域特定的离散化方法。例如，将人们的收入离散化为低收入、中等收入、高收入是基于经济因素的。
监督离散化　以分类为例，若某些数据对象的类标确定，那么根据类标对数据进行离散化通常能取得更好的分类结果。这并不奇怪，因为未使用类标号知识构造的区间常常包含混合的类标号。有一种概念上的简单方法是以极大化区间纯度的方式确定分割点，例如区间包含单个类别标签的程度。然而，实践中这种方法可能需要人为确定区间的纯度和最小的区间大小。
为了解决这一问题，一些基于统计学的方法用每个属性值来分隔区间，并通过合并类似于根据统计检验得出的相邻区间来创建较大的区间。这种自下而上的方法的替代方案是自上而下的方法，如平分初始值得到两个区间并得到最小熵。该技术只需要把每个值看作可能的分割点即可，因为假定区间包含有序值的集合。然后，取一个区间，通常选取具有最大（小）熵的区间，重复此分割过程，直到区间的个数达到用户指定的个数，或者满足终止条件。
无论是自下而上或是自上而下的策略，基于熵的方法是最有前途的离散化方法之一。首先，需要定义熵（entropy)。设k是不同的类标号数，mi是某划分的第i个区间中值的个数，而mij是区间i中类j的值的个数。第i个区间的熵ei由如下等式给出：

其中，Pij=mij/mi是第i个区间中类j的概率（值的比例）。该划分的总熵e是每个区间的熵的加权平均，即

其中，m是值的个数，wi=mi/m是第i个区间的值的比例，而n是区间个数。直观上，区间的熵是区间纯度的度量。如果一个区间只包含一个类的值（该区间非常纯），则其熵为0并且不影响总熵。如果一个区间中的值类出现的频率相等（该区间尽可能不纯），则其熵最大。
例2.13 两个属性离散化　基于熵的自上而下的方法用来独立地离散化图2.14所示的二维数据的属性x和y。在图2.14a所示的第一个离散化中，属性x和y被划分成三个区间。（虚线指示分割点。）在图2.14b所示的第二个离散化中，属性x和y被划分成五个区间。

这个简单的例子解释了离散化的两个特点。首先，在二维中，点类是很好分开的，但在一维中的情况并非如此。一般而言，分别离散化每个属性通常只能保证次最优的结果。其次，五个区间比三个好，但是，至少从熵的角度看，六个区间对离散化的改善不大。（没有给出六个区间的熵值和结果。）因而需要有一个终止标准，自动地发现划分的正确个数。

3.具有过多值的分类属性

分类属性有时可能具有太多的值。如果分类属性是序数属性，则可以使用类似于处理连续属性的技术，以减少分类值的个数。然而，如果分类属性是标称的，就需要使用其他方法。考虑一所大学，它有许多系，68因而系名属性可能具有数十个不同的值。在这种情况下，我们可以使用系之间联系的知识，将系合并成较大的组，如工程学、社会科学或生物科学。如果领域知识不能提供有用的指导，或者这样的方法会导致很差的分类性能，则需要使用更为经验性的方法，如仅当分组结果能提高分类准确率或达到某种其他数据挖掘目标时，才将值聚集到一起。

2.3.7　变量变换

变量变换（variable transformation）是指用于变量的所有值的变换。（尽管我们偶尔也用属性变换这个术语，但是遵循习惯用法，我们使用变量指代属性。）换言之，对于每个对象，变换都作用于该对象的变量值。例如，如果只考虑变量的量级，则可以通过取绝对值对变量进行变换。接下来的部分，我们讨论两种重要的变量变换类型：简单函数变换和规范化。69

1.简单函数

对于这种类型的变量变换，一个简单的数学函数分别作用于每一个值。如果x是变量，这种变换的例子包括

在统计学中，变量变换（特别是平方根、对数和倒数变换）常用来将不具有高斯（正态）分布的数据变换成具有高斯（正态）分布的数据。尽管这可能很重要，但是在数据挖掘中，其他理由可能更重要。假定感兴趣的变量是一次会话中的数据字节数，并且字节数的值域范围为1到10^9。这是一个很大的值域，使用常用对数变换将其进行压缩可能是有益的。这样的话，传输10^8和10^9字节的会话比传输10字节和1000字节的会话更为相似（9-8=1对3-1=2)。对于某些应用，如网络入侵检测，可能需要如此，因为前两个会话多半表示传输两个大文件，而后两个会话可能是两个完全不同的类型。
使用变量变换时需要小心，因为它们改变了数据的特性。尽管有时需要这样做，但是如果没有深入理解变换的特性，则可能出现问题。例如，变换1/x虽然压缩了大于1的值，但是却放大了0和1之间的值，举例来说，{1，2，3}变换成1，1/2，1/3，但是1，1/2，1/3变换成{1，2，3}，这样，对于所有的值集，变换1/x逆转了序。为了帮助弄清楚一个变换的效果，重要的是问如下问题：想要什么样的变换性质？需要保序吗？变换作用于所有的值，特别是负值和0吗？变换对0和1之间的值有何特别影响？本章习题17考察了变量变换的其他方面。

2.规范化或标准化

标准化或规范化的目标是使整个值的集合具有特定的性质。一个传统的例子是统计学中的“对变量标准化”。如果x是属性值的均值（平均值），而sx是它们的标准差，则变换创建一个新的变量，它具有均值0和标准差1。如果要以某种方法组合不同的变量，70则为了避免具有较大值域的变量左右分析结果，这种变换常常是必要的。例如，考虑使用年龄和收入两个变量对人进行比较。对于任意两个人，收入之差的绝对值（数百或数千元）多半比年龄之差的绝对值（小于150）大很多。如果没有考虑到年龄和收入值域的差别，则对人的比较将被收入之差所左右。例如，如果两个人之间的相似性或相异性使用本章后面的相似性或相异性度量来计算，则在很多情况下（如欧几里得距离）收入值将左右计算结果。
均值和标准差受离群点的影响很大，因此通常需要修改上述变换。首先，用中位数（median）（即中间值）取代均值。其次，用绝对标准差（absolute standard deviation）取代标准差。例如，如果x是变量，则x的绝对标准差为，其中xi是变量x的第i个值，m是对象的个数，而μ是均值或中位数。存在离群点时，计算值集的位置（中心）和发散估计的其他方法可以参考统计学书籍。这些更加稳健的方法也可以用来定义标准化变换。

2.4　相似性和相异性的度量

相似性和相异性是重要的概念，因为它们被许多数据挖掘技术所使用，如聚类、最近邻分类和异常检测等。在许多情况下，一旦计算出相似性或相异性，就不再需要原始数据了。这种方法可以看作将数据变换到相似性（相异性）空间，然后进行分析。的确，核方法（Kernel method）是实现这种思想的强大方法。我们将在2.4.7节简单介绍这些核方法，并在4.9.4节的分类中对其进行更全面地讨论。
首先，我们讨论基本要素——相似性和相异性的高层定义，并讨论它们之间的联系。为方便起见，我们使用术语邻近度（proximity）表示相似性或相异性。由于两个对象之间的邻近度是两个对象对应属性之间的邻近度的函数，因此首先介绍如何度量仅包含一个简单属性的对象之间的邻近度。
然后考虑具有多个属性的对象的邻近度度量。这包括Jaccard和余弦相似性度量，这二者适用于像文档这样的稀疏数据，以及相关性和欧几里得距离度量，后二者适用于时间序列这样的稠密数据或多维点。我们也考虑互信息，它可以应用于多种类型的数据，并且适用于检测非线性关系。在本次讨论中，我们只考虑具有相对同类属性的对象，通常为二元值或者连续值。
接下来，我们考虑与邻近度度量相关的若干重要问题。这包括如何在物体具有不同类型的属性时计算物体之间的邻近度，以及在计算数值对象之间的距离时如何解决变量之间的规模差异和相关性。本节最后简略讨论如何选择正确的邻近度度量。
虽然本节重点介绍数据对象之间的邻近度计算，但也可以在属性之间计算邻近度。例如，对于图2.2d所示的文档项矩阵，可以用余弦方法来计算两个文档或两个项（词）之间的相似度。知道两个变量强相关有助于消除冗余。具体而言，后面讨论的相关性和互信息度量常常用于此目的。

2.4.1　基础

1.定义

两个对象之间的相似度（similarity）的非正式定义是这两个对象相似程度的数值度量。因而，两个对象越相似，它们的相似度就越高。通常，相似度是非负的，并常常在0（不相似）和1（完全相似）之间取值。
两个对象之间的相异度（dissimilarity）是这两个对象差异程度的数值度量。对象越类似，它们的相异度就越低。通常，术语距离（distance）用作相异度的同义词，正如我们将介绍的，距离常常用来表示特定类型的相异度。有时，相异度在区间［0，1］中取值，但是相异度在0和∞之间取值也很常见。

2.变换

通常使用变换把相似度转换成相异度或反之，或者把邻近度变换到一个特定区间，如［0,1］。例如，我们可能有相似度，其值域从1到10，但是我们打算使用的特定算法或软件包只能处理相异度，或只能处理［0，1］区间的相似度。之所以在这里讨论这些问题，是因为在稍后讨论邻近度时，我们将使用这种变换。此外，这些问题相对独立于特定的邻近度度量。
通常，邻近度度量（特别是相似度）被定义为或变换到区间［0,1］中的值。这样做的动机是使用一种适当的尺度，由邻近度的值表明两个对象之间的相似（或相异）程度。这种变换通常是比较直截了当的。例如，如果对象之间的相似度在1（一点也不相似）和10（完全相似）之间变化，则我们可以使用如下变换将它变换到［0，1］区间：，其中s和s′分别是相似度的原值和新值。一般来说，相似度到［0，1］区间的变换由如下表达式给出：，其中max_s和min_s分别是相似度的最大值和最小值。类似地，具有有限值域的相异度也能用映射到［0,1］区间。这是一个线性变换的例子，它保留了点之间的相对距离。换句话说，如果点x1和x2的距离是x3与x4距离的两倍，那么在线性变换之后也是如此。
然而，将邻近度映射到［0，1］区间可能非常复杂。例如，如果邻近度度量原来在区间［0，∞］上取值，则需要使用非线性变换，并且在新的尺度上，值之间不再具有相同的联系。对于从0变化到∞的相异度度量，考虑变换，相异度0、0.5、2、10、100和1000分别被变换到0、0.33、0.67、0.90、0.99和0.999。在原来相异性尺度上较大的值被压缩到1附近，但是否希望如此取决于应用。
请注意，将邻近度度量映射到区间［0，1］也可能改变邻近度度量的含义。例如，相关性（稍后讨论）是一种相似性度量，在区间［-1,1］上取值，通过取绝对值将这些值映射到［0，1］区间丢失了符号信息，而对于某些应用，符号信息可能是重要的（见本章习题22)。
将相似度变换成相异度或反之也是比较直截了当的，尽管我们可能再次面临保持度量的含义问题和将线性尺度改变成非线性尺度的问题。如果相似度（相异度）落在［0，1］区间，则相异度（相似度）可以定义为d=1-s（或s=1-d)。73另一种简单的方法是定义相似度为负的相异度（或相反）。例如，相异度0,1,10和100可以分别变换成相似度0,-1,-10和-100。
负变换产生的相似度结果不必局限于［0，1］区间，但是，如果希望的话，则可以使用变换，s=e^-d或。对于变换，相异度0，1，10，100分别被变换到1，0.5，0.09，0.01；对于s=e-d，它们分别被变换到1.00，0.37，0.00，0.00；对于，它们分别被变换到1.00，0.99，0.90，0.00。在这里的讨论中，我们关注将相异度变换到相似度。相反方向的转换见本章习题23。
一般来说，任何单调减函数都可以用来将相异度转换到相似度（或相反）。当然，在将相似度变换到相异度（或相反），或者在将邻近度的值变换到新的尺度时，也必须考虑一些其他因素。我们提到过一些问题，涉及保持意义、扰乱标度和数据分析工具的需要，但是肯定还有其他问题。

2.4.2　简单属性之间的相似度和相异度

通常，具有若干属性的对象之间的邻近度用单个属性的邻近度的组合来定义，因此我们首先讨论具有单个属性的对象之间的邻近度。考虑由一个标称属性描述的对象，对于两个这样的对象，相似意味什么呢？由于标称属性只携带了对象的相异性信息，因此我们只能说两个对象有相同的值，或者没有。因而在这种情况下，如果属性值匹配，则相似度定义为1，否则为0；相异度用相反的方法定义：如果属性值匹配，相异度为0,否则为1。
对于具有单个序数属性的对象，情况更为复杂，因为必须考虑序信息。考虑一个在标度{poor，fair，OK，good，wonderful}上测量产品（例如，糖块）质量的属性。一个评定为wonderful的产品P1与一个评定为good的产品P2应当比它与一个评定为OK的产品P3更接近。为了量化这种观察，序数属性的值常常映射到从0或1开始的连续整数，例如，{poor=0，fair=1，OK=2，good=3，wonderful=4}。于是，P1与P2之间的相异度d（Pl，P2)=3-2=1，或者，如果希望相异度在0和1之间取值d（P1，P2)=（3-2)/4=0.25；序数属性的相似度可以定义为s=1-d。
序数属性相似度（相异度）的这种定义可能使读者感到有点担心，因为这里假设了属性的连续值之间的间隔相等，而事实并非如此。如果根据实际情况，我们应该计算出区间或比率属性。值fair与good的差真的和OK与wonderful的差相同吗？可能不相同，但是在实践中，我们的选择是有限的，并且在缺乏更多信息的情况下，这是定义序数属性之间邻近度的标准方法。
对于区间或比率属性，两个对象之间的相异性的自然度量是它们的值之差的绝对值。例如，我们可能将现在的体重与一年前的体重相比较，说：“我重了10磅。”在这类情况下，相异度通常在0和∞之间，而不是在0和1之间取值。如前所述，区间或比率属性的相似度通常转换成相异度。
表2.7总结了这些讨论。其中，x和y是两个对象，它们具有一个指明类型的属性，d（x，y)和s（x，y)分别是x和y之间的相异度和相似度（分别用d和s表示）。尽管其他方法也是可能的，但是表中的这些是最常用的。

下面两节介绍更复杂的涉及多个属性的对象之间的邻近度度量：（1）数据对象之间的相异度；（2）数据对象之间的相似度。这样分节可以更自然地展示使用各种邻近度度量的基本动机。然而，我们要强调的是使用上述技术，相似度可以变换成相异度，反之亦然。

2.4.3　数据对象之间的相异度

本节讨论各种不同类型的相异度。我们从讨论距离（距离是具有特定性质的相异度）开始，然后给出一些更一般的相异度类型的例子。

距离

首先给出一些例子，然后使用距离的常见性质更正式地介绍距离。一维、二维、三维或高维空间中两个点x和y之间的欧几里得距离（Euclidean distance)d由如下熟悉的公式定义：

其中，n是维数，而xk和yk分别是x和y的第k个属性值（分量）。用图2.15、表2.8和表2.9解释该公式，它们展示了这个点集、这些点的x和y坐标以及包含这些点之间距离的距离矩阵（distance matrix）。

式（2.1）给出的欧几里得距离可以用式（2.2）的闵可夫斯基距离（Minkowski distance)来推广：

其中，r是参数。下面是闵可夫斯基距离的三个最常见的例子。

• r=1，城市街区（也称曼哈顿、出租车、L1范数）距离。一个常见的例子是汉明距离（Hamming distance)，它是两个具有二元属性的对象（即两个二元向量）之间不同的二进制位的个数。
• r=2，欧几里得距离（L2范数）。
• r=∞，上确界（Lmax或L∞范数）距离。这是对象属性之间的最大距离。更正式地，L∞距离由式（2.3）定义：

  

  
  

注意不要将参数r与维数（属性数）n混淆。欧几里得距离、曼哈顿距离和上确界距离是对n的所有值（1，2，3，…）定义的，并且指定了将每个维（属性）上的差组合成总距离的不同方法。

表2.10和表2.11分别给出表2.8中数据的L1距离和L∞距离的邻近度矩阵。注意，所有的距离矩阵都是对称的，即第ij个项与第ji个项相同，例如，在表2.9中，第4行第1列和第1行第4列都包含值5.1。

距离（如欧几里得距离）具有一些众所周知的性质。如果d（x,y）是两个点x和y之间的距离，则如下性质成立：
1） 非负性。（a）对于所有x和y，d（x，y）≥0；（b）仅当x=y时d（x，y)=0。
2） 对称性。对于所有x和y，d（x，y)=d（y，x)。
3） 三角不等式。对于所有x、y和z，d（x，z)≤d（x，y)+d（y，z)。
满足以上三个性质的测度称为度量（metric)。有些人只对满足这三个性质的相异性度量使用术语距离，但在实践中常常违反这一约定。这里介绍的三个性质是有用的，数学上也是令人满意的。此外，如果三角不等式成立，则该性质可以用来提高依赖于距离的技术（包括聚类）的效率（见本章习题25)。尽管如此，许多相异度都不满足一个或多个度量性质。
例2.14给出相关测度的例子。
例2.14 非度量的相异度：集合差　基于集合论中定义的两个集合差的概念举例。设有两个集合A和B，A-B是不在B中的A中元素的集合。例如，如果A={1，2，3，4}，而B={2，3，4}，则A－B={1}，而B－A=，即空集。我们可以将集合A和B之间的距离定义为d（A，B)=size（A-B），其中size是一个函数，它返回集合元素的个数。该距离测度是大于或等于零的整数值，但不满足非负性的第二部分，也不满足对称性，同时还不满足三角不等式。然而，如果将相异度修改为d（A，B)=size（A-B)+size（B-A)，则这些性质都可以成立（见本章习题21)。

2.4.4　数据对象之间的相似度

对于相似度，三角不等式（或类似的性质）通常不成立，但是对称性和非负性通常成立。更明确地说，如果s（x，y)是数据点x和y之间的相似度，则相似度具有如下典型性质。
1） 仅当x=y时s（x，y)=1。（0≤s≤1)
2） 对于所有x和y，s（x，y)=s（y,x)。（对称性)
对于相似度，没有与三角不等式对应的一般性质。然而，有时可以将相似度简单地变换成一种度量距离。稍后讨论的余弦相似性度量和Jaccard相似性度量就是两个例子。此外，对于特定的相似性度量，还可能在两个对象相似性上导出本质上与三角不等式类似的数学约束。
例2.15 非对称相似性度量　考虑一个实验，实验中要求人们对屏幕上快速闪过的一小组字符进行分类。该实验的混淆矩阵（confusion matrix）记录每个字符被分类为自己的次数和被分类为另一个字符的次数。使用混淆矩阵，我们可以将字符x和字符y之间的相似性度量定义为x被错误分类为y的次数，但请注意，此度量不是对称的。例如，假定“0”出现了200次，它被分类为“0”160次，而被分类为“o”40次。类似地，“o”出现200次并且被分类为“o”170次，但是分类为“0”只有30次。如果取这些计数作为两个字符之间相似性的度量，则得到一种相似性度量，但这种相似性度量不是对称的。在这种情况下，通过选取，相似性度量可以转换成对称的，其中s′是新的相似性度量。

2.4.5　邻近度度量的例子

本节给出一些相似性和相异性度量的具体例子。

1.二元数据的相似性度量

两个仅包含二元属性的对象之间的相似性度量也称为相似系数（similarity coefficient），并且通常在0和1之间取值，值为1表明两个对象完全相似，而值为0表明对象一点也不相似。有许多理由表明在特定情形下，一种系数为何比另一种好。
设x和y是两个对象，都由n个二元属性组成。这样的两个对象（即两个二元向量）的比较可生成如下四个量（频率)：

• f00=x取0并且y取0的属性个数；
• f01=x取0并且y取1的属性个数；
• f10=x取1并且y取0的属性个数；
• f11=x取1并且y取1的属性个数。

简单匹配系数（Simple Matching Coefficient，SMC)　一种常用的相似性系数是简单匹配系数，定义如下：

该度量对出现和不出现都进行计数。因此，SMC可以在一个仅包含是非题的测验中用来发现问题回答相似的学生。
Jaccard系数（Jaccard Coefficient）　假定x和y是两个数据对象，代表一个事务矩阵（见2.1.2节）的两行（两个事务）。如果每个非对称的二元属性对应于商店的一种商品，则1表示该商品被购买，而0表示该商品未被购买。由于未被顾客购买的商品数远大于被购买的商品数，因而像SMC这样的相似性度量将会判定所有的事务都是类似的。这样，常常使用Jaccard系数来处理仅包含非对称的二元属性的对象。Jaccard系数通常用符号J表示，由如下等式定义：

例2.16 SMC和Jaccard相似性系数　为了解释这两种相似性度量之间的差别，我们对如下二元向量计算SMC和J：
x=（1,0,0,0,0,0,0,0,0,0)
y=（0,0,0,0,0,0,1,0,0,1)

• f01=2　x取0并且y取1的属性个数
• f10=1　x取1并且y取0的属性个数
• f00=7　x取0并且y取0的属性个数
• f11=0　x取1并且y取1的属性个数

2.余弦相似度

通常，文档用向量表示，向量的每个组件（属性）代表一个特定的词（术语）在文档中出现的频率。尽管文档具有数以百千计或数以万计的属性（词），但是每个文档向量都是稀疏的，因为它具有相对较少的非零属性值。（文档规范化并不对零词目创建非零词目，即文档规范化保持稀疏性。）这样，与事务数据一样，相似性不能依赖共享0的个数，因为任意两个文档多半都不会包含许多相同的词，从而如果统计0-0匹配，则大多数文档都与其他大部分文档非常类似。因此，文档的相似性度量不仅应当像Jaccard度量一样需要忽略0-0匹配，而且还必须能够处理非二元向量。下面定义的余弦相似度（cosine similarity）就是文档相似性最常用的度量之一。如果x和y是两个文档向量，则

其中′表示向量或者矩阵的转置，表示两个向量的内积：

且||x||是向量x的长度，。
两个向量的内积适用于非对称属性，因为它只依赖于两个向量中非零的分量。因此，两个文档之间的相似性只取决于它们中出现的单词。
例2.17 两个文档向量的余弦相似度　该例计算下面两个数据对象的余弦相似度，这些数据对象可能代表文档向量：
x=（3,2,0,5,0,0,0,2,0,0)
y=（1,0,0,0,0,0,0,1,0,2)
〈x,y〉=3×1＋2×0＋0×0＋5×0＋0×0＋0×0＋0×0＋2×1＋0×0＋0×2
＝5
||x||＝3×3＋2×2＋0×0＋5×5＋0×0＋0×0＋0×0＋2×2＋0×0＋0×0
＝6.48
||y||＝1×1＋0×0＋0×0＋0×0＋0×0＋0×0＋0×0＋1×1＋0×0＋2×2
＝2.45
cos（x,y)=0.31
如图2.16所示，余弦相似度实际上是x和y之间夹角（余弦）的度量。这样，如果余弦相似度为1，则x和y之间的夹角为0°，并且除长度之外，x和y是相同的：如果余弦相似度为0，则x和y之间的夹角为90°,并且它们不包含任何相同的词（术语)。

式（2.6）可以写成式（2.8）的形式：

其中，。x和y被它们的长度除，将它们规范化到长度为1。这意味着在计算相似度时，余弦相似度不考虑两个数据对象的量值。（当量值是重要的时候，欧几里得距离可能是一种更好的选择。）对于长度为1的向量，余弦度量可以通过简单地取内积计算。从而，在需要计算大量对象之间的余弦相似度时，将对象规范化，使之为单位长度可以减少计算时间。

3.广义Jaccard系数（Tanimoto系数）

广义Jaccard系数可以用于文档数据，并在二元属性情况下归约为Jaccard系数。该系数用EJ表示，由下式定义：

4.相关性

相关性经常被用来测量两组被观察到的值之间的线性关系。因此，相关性可以测量两个变量（高度和重量）之间或两个对象（一对温度时间序列）之间的关系。相关性可以测量类型和取值尺度差异很大的属性间的相似度，如果两个数据对象中的值来自不同的属性，通常更频繁地使用相关性来度量属性之间的相似度。
更准确地，两个数据对象例如向量x和y之间的皮尔森相关（Pearson’s correlation）系数由下式定义：

这里使用标准的统计学记号和定义：

例2.18 完全相关　相关度总是在-1到1之间取值。相关度为1（-1)意味x和y具有完全正（负）线性关系，即xk=ayk+b，其中a和b是常数。下面两个x和y的值集分别给出相关度为-1和+1的情况。为简单起见，第一组中取x和y的均值为0。

例2.19 非线性关系　如果相关度为0，则两个数据对象的属性之间不存在线性关系。然而，仍然可能存在非线性关系。在下面的例子中，数据对象的属性之间存在非线性关系yk=x2k，但是它们的相关度为0。

x=（-3，-2，-1，0，1,2,3)
y=（　9,　4,　1,0,1,4,9)

例2.20 相关性可视化　通过绘制对应属性值对可以很容易地判定两个数据对象x和y之间的相关性。图2.17给出了一些图，x和y具有30个属性，这些属性的值随机地产生（服从正态分布），使得x和y的相关度从-1到1。图中每个小圆圈代表30个属性中的一个，其x坐标是x的一个属性的值，而其y坐标是y的相同属性的值。

如果通过减去均值，然后规范化使其长度为1来变换x和y，则它们的相关度可以通过求点积来计算。（注意，这与其他情况下使用的标准化不同，比如2.3.7节讨论的先减去均值，并被标准偏差除。）这种变换突出了相关度量和余弦度量之间的有趣关系。特别地，x和y之间的相关性与x′和y′之间的余弦相同。然而，即使x和y与x′和y′具有相同的相关度量，它们之间的余弦也不相同，即使它们都具有相同的相关度量。通常，当两个向量的均值为0时，两个向量之间的相关性仅在特殊情况下等于余弦度量。

5.连续属性度量方法间的差异

我们刚刚定义了三种连续属性的邻近度度量方法：余弦、相关性和闵可夫斯基距离。在这一节中，我们将展示这三个邻近度度量方法之间的差异。具体而言，我们考虑两种常用的数据变换方法，即常数因子缩放（乘）和常数值平移（加法）。如果对数据对象进行数据变换之后，该邻近度度量方法的值保持不变，则该邻近度度量方法被认为对数据变换具有不变性。表2.12比较了余弦、相关性和闵可夫斯基距离度量对于缩放和平移操作的不变性的行为。可以看出，相关性度量对于缩放和平移都有不变性，而余弦度量只对缩放具有不变性。另一方面，闵可夫斯基距离度量对缩放和平移都是敏感的，因此对两者都不具有不变性。

我们用一个例子来说明不同邻近度度量之间的差异的意义。
例2.21 比较邻近度度量　考虑下面两个具有七个数值属性的向量x和y。

x=（1,2,4,3,0,0,0)
y=（1,2,3,4,0,0,0)

可以看出，x和y都有4个非零值，并且两个向量中的值大部分是相同的，除了第三个和第四个分量。两个向量之间的余弦、相关性和欧几里得距离计算如下：

毫无疑问，x和y具有接近1的余弦和相关度量，而它们之间的欧几里得距离很小，表明它们非常相似。现在我们考虑向量ys，它是y（乘以2的常数因子）的缩放版本，以及向量yt，它是通过将y平移5个单位来构造的，如下所示：

ys=2×y=（2,4,6,8,0,0,0)
yt=y+5=（6,7,8,9,5,5,5)

我们感兴趣的是ys和yt是否与原始向量y一样，都跟x邻近度相同。表2.13展示了不同方法计算的向量对（x，y）、（x，ys）和（x，yt）的邻近度。可以看出，即使用ys或yt代替y之后，x和y之间的相关性值保持不变。然而，余弦值在计算（x，y）和（x，ys）时仍然等于0.9667，但当计算为（x，yt）时，余弦值显著降低到0.7940。上诉结果突出展示了与相关性度量相比，余弦只对缩放具有不变性，对平移不具有不变性。另一方面，欧几里得距离对3对向量计算出不同的值，那是因为它对缩放和平移都很敏感。

我们可以从这个例子中观察到，当在数据上应用缩放或平移操作时，不同的邻近度度量表现不同。因此，正确的邻近度度量方法的选择取决于数据对象之间的相似性的特点及对给定应用的意义。例如，如果x和y表示文档项矩阵中不同单词的频率，则使用ys替换y时邻近度保持不变的邻近度度量方法将是有意义的，因为ys只是y的缩放版本，在文档中表示单词出现的分布。然而，yt与y不同，因为它包含大量在y中不存在的非零频率的词。由于余弦对缩放具有不变性，而对平移不具有不变性，因此对这个应用来说余弦将是一个理想的选择。
考虑一个不同的场景，其中x代表某地理位置连续七天的摄氏温度。y、ys和yt为使用三种不同的测量尺度在另一位置测量的温度。注意，不同的温度单位具有不同的偏移量（例如，摄氏和开氏温标）和不同的缩放因子87（例如，摄氏度和华氏度）。我们希望使用邻近度度量方法来捕获温度值之间的邻近度，且不受测量尺度的影响。那么，相关性将是该应用的邻近度测量方法的理想选择，因为它对缩放和平移都具有不变性。
另一个例子，考虑x代表在7个地点测量的降水量（cm）的情景。y、ys、yt为三种不同的模型预测的在这些位置的降水值。理想情况下，我们希望选择一个模型，准确地重建x中的降水量而不产生任何误差。很明显，y在x中提供了一个很好的近似值，而ys和yt提供了较差的降水估计，尽管它们找到了不同地点的降水趋势。因此，我们需要选择一个邻近度度量方法，惩罚来自实际观测与模型估计中的任何差异，并且对缩放和平移操作都敏感。欧几里得距离满足此属性，因此将是该应用的邻近度度量的正确选择。事实上，欧几里德距离通常用于计算模型的准确性，这将在后面的第3章中讨论。

2.4.6　互信息

与相关性一样，互信息被用作两组成对值之间的相似性度量，该值有时被用作相关性的替代物，特别是在值对之间疑为非线性关系时。这一度量方法来自信息论，它是关于如何正式定义和量化信息的研究。事实上，互信息是一组值对另一组提供多少信息的度量方法，这些值成对地出现，例如高度和重量。如果两组值是独立的，即一组值不包含另一组值的任何信息，则它们的互信息是0。另一方面，如果两组值完全依赖，即知道一组值则能知道另一组值，反之亦然，则它们具有最大互信息。互信息不具有最大值，但我们将定义它的标准化版本，其范围在0到1之间。
为了定义互信息，我们考虑两组值X和Y，它们成对出现（X，Y）。我们需要测量一组值中的平均信息，以及它们的值对。这通常用熵来衡量。更具体地，假设X和Y是离散的，也就是说，X可以取m个不同的值，u1，u2，…，um，Y可以取n个不同的值v1，v2，…，vn。然后，它们的个体和联合熵可以根据每个值和一对值的概率来定义：

如果值或组合值的概率为0，则通常将0log2（0）取值为0。
X和Y的互信息可以直接定义如下：

注意H（X，Y)是对称的，即H（X，Y)=H（Y，X)，因此互信息也是对称的，即I（X，Y)=I（Y)。
实际上，X和Y是同一数据集中的两个属性或两行中的值。在例2.22中，两个向量x和y表示这些值，并且利用值或值对出现在x和y中的频率计算每个值或值对的概率（xi，yi）,其中xi表示x的第i个元素，yi表示y的第i个元素。下面用前面的例子来说明。
例2.22 评估非线性关系的互信息　回忆例2.19，其中yk＝x2k，但它们的相关性为0。

x=（-3,-2,-1,0,1,2,3)
y=（　9,　4,　1,0,1,4,9)

从图2.18可知，I（x，y)=H（x)+H（y)-H（x，y)=1.9502。虽然多种方法可以用来规范互信息，参见本例的文献注释，我们将应用一种令互信息除以log2（min（m，n))的方法，并产生0到1之间的结果。这产生的值为1.9502log2（4)=0.9751。因此，x和y是强相关的。它们不是完全相关的，因为给定y的值，除了y＝0之外，关于x的值有一定的歧义。注意，对于y=-x，归一化互信息将是1。

　

2.4.7　核函数

很容易理解相似性和距离在诸如聚类之类的应用中可能是有用的，它试图将相似对象分组在一起。更不明显的是，许多其他数据分析任务，包括预测建模和维归约，可以用数据对象的逐对“邻近度”来表示。更具体地，许多数学分析问题可以被数学公式化为输入，例如一个核矩阵K，它可以被认为是一种邻近度矩阵。因此，使用初始预处理步骤将输入数据转换为内核矩阵，该内核矩阵是数据分析算法的输入。
更正式地说，如果一个数据集有m个数据对象，那么K是m×m的矩阵。如果xi和xj是第i个和第j个数据对象，则Kij是通过核函数计算的K的第ij个熵：kij=κ（xi,xj)（2.16)正如我们将在下面的材料中看到的，核矩阵的使用允许算法对各种数据的更广泛的适用性，还能扩展仅用于检测线性关系的算法到非线性关系上建模的能力。
核使算法数据独立　如果算法使用一个核矩阵，那么它可以与任何类型的数据一起使用，并为该数据设计核函数。算法2.1证明了这一观点。虽然只有一些数据分析算法可以被修改为使用核矩阵作为输入，但是这种方法是非常强大的，因为它允许这样的算法与几乎任何类型的数据一起使用，其中可以为数据定义适当的核函数。因此，一个分类算法可以运用到例如记录数据、字符串数据或图形数据等数据上。如果一个算法可以被重新构造成使用核矩阵，那么它对不同类型的数据的适用性急剧增加。正如将在后面的章节中看到的，许多聚类、分类和异常检测算法只使用相似性或距离，因此，可以很容易地修改为与核函数一起使用。

将数据映射到高维数据空间可以允许非线性关系的建模　基于核的数据分析算法还有另一个同样重要的方面：它们能够用只模拟线性关系的算法来建模非线性关系。通常，这是通过首先将数据从低维数据空间转换（映射）到高维空间来实现的。
例2.23 将数据映射到高维度空间　考虑由下面等式给出的两个变量x和y之间的关系，它定义了两个维度的椭圆关系（见图2.19a）：

我们可以通过创建3个新的变量u、v和w来映射二维数据到三个维度，这些变量被定义如下：

因此，我们现在可以将式（2.17）表示为线性方程。这个方程描述了一个平面的三个维度。椭圆上的点将位于该平面上，而椭圆内和外的点将位于平面的相对侧。如图2.19b所示，这个3D图的视角是沿着分离平面的表面，使得平面以线的形式出现。

核技巧　上面所示的方法显示了将数据映射到高维空间的价值，该操作对于基于核的方法是必需的。从概念上讲，我们首先定义一个函数φ，将数据点x和y映射到高维空间中的数据点φ（x)和φ（y)，使得内积能够给出所期望的x、y邻近度度量的方法。通过使用这样的方法可能会牺牲很多，因为我们大大扩展了数据的大小，增加我们分析的计算复杂性，最终通过计算高维空间中的相似性来解决维数灾难的问题。然而，并不是这样的，因为可以通过定义核函数κ来避免这些问题，该核函数κ可以计算相同的相似性值，但是可以用原始空间中的数据点，即κ（x，y)＝<φ（x)，φ（y)>。这就是所谓的核技巧。核技巧有一个非常坚实的数学基础，是数据分析领域中一个非常强大的方法。
并不是一对数据对象的每一个函数都满足核函数所需的性质，但是可以为各种数据类型设计许多有用的核。例如，三个常见的核函数是多项式、高斯（径向基函数（RBF））和sigmoid核。如果x和y是两个数据对象（特别是两个数据向量），那么这三个核函数可以分别表示如下：

其中，α与c≥0是常数，d是多项式度的整型参数，x-y是向量x-y的长度，σ>0为调整高斯分布的参数。
例2.24 多项式核　注意，在前一节中给出的核函数（将数据映射到更高维空间，然后在高维空间计算数据的内积）计算与我们原始数据相同的相似度值。例如，对于度为2的多项式核，让其成为将二维数据向量x=（x1，x2)映射到高维空间的函数。特别地，

对于更高维的空间，将邻近度定义为φ（x)和φ（y)的内积，如<φ（x)，φ（y)>。接着，如前所述，可以表示为：

其中,κ是由式（2.19)定义的。具体而言，如果x=（x1，x2)和y=（y1，y2)，则

更一般地说，核技巧取决于定义κ和φ，从而使式（2.23）成立。这是为各种各样的核所做的。
这种基于核的方法的讨论只是为了简要介绍这个主题，并省略了许多细节。4.9.4节提供了有关基于核方法的更全面的讨论，在用于分类的非线性支持向量机中讨论了这些问题。基于核分析的更翔实的参考资料可以在本章的文献注释中找到。

2.4.8　Bregman散度

本节，我们简略介绍Bregman散度（Bregman divergence)，它是一组具有共同性质的邻近函数。这样，可以构造使用Bregman散度的一般数据挖掘算法，如聚类算法，具体的例子是K均值聚类算法（7.2节）。注意，本节需要向量计算方面的知识。
Bregman散度是损失或失真函数。为了理解损失函数，考虑如下情况：设x和y是两个点，其中y是原来的点，而x是它的某个失真或近似，例如，x可能是由于添加了一些随机噪声到y上而产生的。损失函数的目的是度量用x近似y导致的失真或损失。当然，x和y越类似，失真或损失就越小，因而Bregman散度可以用作相异性函数。
有如下正式定义。定义2.6（Bregman散度）　给定一个严格凸函数Φ（连同一些通常会满足的适度限制)，由该函数生成的Bregman散度（损失函数）D（x，y)通过下面的公式给出：

其中，Φ（y)是在y上计算的Φ的梯度，x-y是x与y的向量差，而<Φ（y)，（x-y)>是Φ（y)和（x-y)的内积。对于欧几里得空间中的点，内积就是点积。D（x，y)可以写成D（x，y)=Φ（x)-L（x)，其中L（x)=Φ（y)+<Φ（y)，（x-y)>代表在y上正切于函数Φ的平面方程。使用微积分学的术语，L（x)是函数Φ在y点附近的线性部分，而Bregman散度是一个函数与该函数的线性近似之间的差。选取不同的Φ，可以得到不同的Bregman散度。
例2.25 我们使用平方欧几里得距离给出Bregman散度的一个具体例子。为了简化数学计算，我们仅限于一维。设x和y是实数，而Φ（t)是实数值函数，Φ（t)=t2。在此情况下，梯度归结为导数，而点积归结为乘积。例如，式（2.25）变成式（2.26）：

该例的图形在图2.20中给出，其中y=1。在x=2和x=3上给出了Bregman散度。

2.4.9　邻近度计算问题

本节讨论与邻近度度量有关的一些重要问题：（1）当属性具有不同的尺度（scale）或相关时如何处理；（2）当对象包含不同类型的属性（例如，定量属性和定性属性）时如何计算对象之间的邻近度；（3）当属性具有不同的权重（即并非所有的属性都对对象的邻近度具有相等的贡献）时，如何处理邻近度计算。

1.距离度量的标准化和相关性

距离度量的一个重要问题是当属性具有不同的值域时如何处理。（这种情况通常称作“变量具有不同的尺度。”）在前面的例子中，使用欧几里得距离，基于年龄和收入两个属性来度量人之间的距离。除非这两个属性是标准化的，否则两个人之间的距离将被收入所左右。
一个相关的问题是，除值域不同外，当某些属性之间还相关时，如何计算距离。当属性相关、具有不同的值域（不同的方差），并且数据分布近似于高斯（正态）分布时，欧几里得距离的拓展——Mahalanobis距离是有用的。相关变量对标准距离度量有很大影响，因为任何相关变量的变化反映在所有相关变量的变化中。具体地说，两个对象（向量）x和y之间的Mahalanobis距离定义为：

其中，Σ-1是数据协方差矩阵的逆。注意，协方差矩阵Σ是这样的矩阵，它的第ij个元素是第i个和第j个属性的协方差，由式（2.11）定义。
例2.26 在图2.21中有1000个点，其x属性和y属性的相关度为0.6。在椭圆长轴两端的两个大点之间的欧几里得距离为14.7，但Mahalanobis距离仅为6。这是因为Mahalanobis距离不太关注最大方差方向的差异。实践中，计算Mahalanobis距离的代价昂贵，但是对于其属性相关的对象来说是值得的。如果属性相对来说不相关，只是具有不同的值域，则只需要对变量进行标准化就足够了。

2.组合异种属性的相似度

前面的相似度定义所基于的方法都假定所有属性具有相同类型。当属性具有不同类型时，就需要更一般的方法。直截了当的方法是使用表2.7分别计算出每个属性之间的相似度，然后使用一种输出为0和1之间相似度的方法组合这些相似度。一种方法是将总相似度定义为所有属性相似度的平均值。不幸的是，如果某些属性是非对称属性，这种方法的效果不好。例如，如果所有的属性都是非对称的二元属性，则相似性度量先归结为简单匹配系数——一种对于二元非对称属性并不合适的度量。处理该问题的最简单的方法是：如果两个对象在非对称属性上的值都是0，97则在计算对象相似度时忽略它们。类似的方法也能很好地处理缺失值。
概括地说，算法2.2可以有效地计算具有不同类型属性的两个对象x和y之间的相似度。修改该过程可以很轻松地处理相异度。

3.使用权值

在前面的大部分讨论中，所有的属性在计算邻近度时都会被同等对待。但是，当某些属性对邻近度的定义比其他属性更重要时，我们并不希望同等对待。为了处理这种情况，可以通过对每个属性的贡献加权来修改邻近度公式。
属性权重为wk时，式（2.28）变成：

闵可夫斯基距离的定义也可以修改为：

2.4.10　选择正确的邻近度度量

一些一般观察可能会对你有所帮助。首先，邻近度度量的类型应当与数据类型相适应。98对于许多稠密的、连续的数据，通常使用距离度量，如欧几里得距离等。连续属性之间的邻近度通常用属性值的差来表示，并且距离度量提供了一种将这些差组合到总邻近度度量的良好方法。尽管属性可能有不同的取值范围和不同的重要性，但这些问题通常都可以用前面介绍的方法处理，例如规范化和属性加权。
对于稀疏数据，常常包含非对称的属性，通常使用忽略00匹配的相似性度量。从概念上讲，这反映了如下事实：对于一对复杂对象，相似度依赖于它们共同具有的性质数而不是依赖于它们都缺失的性质数目。余弦、Jaccard和广义Jaccard度量对于这类数据是合适的。
数据向量还有一些其他特征需要考虑。之前讨论了欧几里得距离、余弦和相关性对于缩放（乘法）和平移（加法）的不变性。这种考虑的实际意义是，余弦更适合于稀疏的文档数据，因为文档向量中只需要考虑数据的缩放，而相关性更适用于时间序列，因为时间序列中数据的缩放和平移都很重要。当两个数据向量的每个特征取值比较接近时，欧几里得距离或其他类型的闵可夫斯基距离是最合适的。
在某些情况下，需要使用数据变换或规范化去得到合适的相似性度量。例如，时间序列数据可能具有显著影响相似性的趋势或周期模式。此外，正确地计算相似度还需要考虑时间延迟。最后，两个时间序列可能只在特定的时间周期上相似，例如，气温与天然气的用量之间存在很强的联系，但是这种联系仅出现在取暖季节。
实践考虑也是重要的。有时，一种或多种邻近度度量已经在某个特定领域使用，因此，其他人已经回答了应当使用何种邻近度度量的问题。另外，所使用的软件包或聚类算法可能完全限制了选择；如果关心效率，则可能希望选择具有某些性质的邻近度度量，这些性质（如三角不等式）可以用来降低邻近度计算量（见本章习题25)。
然而，如果常见的实践或实践限制并未规定某种选择，则正确地选择邻近度度量可能是一项耗时的任务，需要仔细地考虑领域知识和度量使用的目的。可能需要评估许多不同的相似性度量，以确定哪些结果最有意义。

文献注释

理解待分析的数据至关重要，并且在基本层面，这是测量理论的主题。比如说，定义属性类型的初始动机是精确地指出哪些统计操作对何种数据是合法的。我们给出了测量理论的概述，这些源于S.S.Stevens的经典文章［112］。（表2.2和表2.3取自Stevens［113］。）尽管这是最普遍的观点并且相当容易理解和使用，但是测量理论远不止这些。权威的讨论可以在测量理论基础的三卷系列书［88，94，114］中找到。同样值得关注的是Hand［77］的文章，文中广泛地讨论了测量理论和统计学，并且附有该领域其他研究者的评论。许多关于Stevens论文的评论和扩展见文献［66，97，117］。最后，有许多书籍和文章都介绍了科学与工程学特定领域中的测量问题。
数据质量是一个范围广泛的主题，涉及使用数据的每个学科。精度、偏置、准确率的讨论和一些重要的图可以在许多科学、工程学和统计学的导论性教材中找到。数据质量“适合使用”的观点在Redman［103］中有更详细的解释。对数据质量感兴趣的人一定也会对MIT的总体数据质量管理计划［95，118］感兴趣。然而，处理特定领域的数据质量问题所需要的知识最好是通过考察该领域的研究者的数据质量实践得到。
与其他预处理任务相比，聚集是一个不够成形的主题。然而，聚集是数据库联机分析处理（OLAP）［68，76，102］领域使用的主要技术之一。聚集在符号数据分析领域也起到了一些作用（Bock和Diday［64］)。该领域的一个目标是用符号数据对象汇总传统的记录数据，而符号数据对象的属性比传统属性更复杂。例如，这些属性的值可能是值的集合（类别）、区间、具有权重的值的集合（直方图）。符号数据分析的另一个目标是能够在由符号数据对象组成的数据上进行聚类、分类和其他类型的数据分析。
抽样是一个已经在统计学及其相关领域中透彻研究的主题。许多统计学导论性书籍（如Lindgren［90］）中都有关于抽样的讨论，并且还有通篇讨论该主题的书，如Cochran的经典教科书［67］。Gu和Liu［74］提供了关于数据挖掘抽样的综述，而Olken和Rotem［98］提供了关于数据库抽样的综述。还有许多涉及数据挖掘和数据库抽样的文献也值得关注，包括Palmer和Faloutsos［100］、Provost等［101］、Toivonen［115］、Zaki等［119］。
在统计学中，已经用于维归约的传统技术是多维定标（MDS）（Borg和Groenen［65］，Kruskal和Uslaner［89］）和主成分分析（PCA）（Jolloffe［80］），主成分分析类似于奇异值分解（SVD）（Demmel［70］）。维归约详见附件B。
离散化是一个已经在数据挖掘领域广泛讨论的主题。有些分类算法只能使用分类属性，并且关联分析需要二元数据，这样就有了重要的动机去考察如何最好地对连续属性进行二元化或离散化。对于关联分析，建议读者阅读Srikant和Agrawal［111］，而分类领域离散化的一些有用的参考文献包括Dougherty等［71］、Elomaa和Rousu［72］、Fayyad和Irani［73］以及Hussain等［78］。
特征选择是另一个在数据挖掘领域被彻底研究的主题，Molina等的综述［96］以及Liu和Motada的两本书［91，92］提供了涵盖该主题的广泛资料。其他有用的文章包括Blum和Langley［63］、Kohavi和John［87］和Liu等［93］。
很难提供特征变换主题的参考文献，因为不同学科的实践差异很大。许多统计学书籍都讨论了变换，但是通常都限于特定的目的，如确保变量的规范性，或者确保变量具有相等的方差。我们提供两个参考文献：Osborne［99］和Tukey［116］。
尽管已经讨论了一些最常用的距离和相似性度量，但是还有数以百计的这样的度量，并且更多的度量正在被提出。与本章的其他许多主题一样，许多度量都局限于特定的领域，例如，在时间序列领域，见Kalpakis等［81］、Keogh和Pazzani［83］的文章。聚类方面的书提供了最好的一般讨论，特别是如下书籍：Anderberg［62］、Jain和Dubes［79］、Kaufman和Rousseeuw［82］以及Sneath和Sokal［109］。
尽管基于信息的相似性度量的计算难度大且计算代价高，但是它最近却变得越来越流行。Cover和Thomas［69］很好地阐述了信息理论。如果连续变量遵循一个如高斯等常见的分布，则该连续变量的互信息的计算比较简单。然而，实际情况往往比较复杂，因此许多新技术被提出。Khan等人的文章［85］在短时间序列上研究比较了被提出的各种方法。参见R和Matlab的相关信息包。Resher等人最近发表的论文［104，105］让互信息备受关注。该论文提出了基于互信息的方法，该方法具有很优越的性能。在论文发表初期，得到了一些支持［110］，但是也有研究者提出了该方法的局限性［75，86，108］。
两本较流行的介绍核方法的书籍是文献［106］和文献［107］。后者还给出一个与核方法相关的网站［84］。此外，当前许多数据挖掘、机器学习和统计学习教材都有一些关于核方法的介绍。关于核方法在支持向量机中的使用的参考文献见4.9.4节。

参考文献

习题

1.在第2章的第一个例子中，统计人员说：“是的，字段2和3也有不少问题。”从所显示的三行样本数据，你能解释她为什么这样说吗？
2.将下列属性分类成二元的、离散的或连续的，并将它们分类成定性的（标称的或序数的）或定量的（区间的或比率的）。某些情况下可能有多种解释，因此如果你认为存在二义性，简略给出你的理由。
例子：年龄。回答：离散的、定量的、比率的。
（a) 用AM和PM表示的时间。
（b) 根据曝光表测出的亮度。
（c) 根据人的判断测出的亮度。
（d) 按度测出的0和360之间的角度。
（e) 奥运会上授予的铜牌、银牌和金牌。
（f) 海拔高度。
（g) 医院中的病人数。
（h) 书的ISBN号（查找网上的格式）。
（i) 用如下值表示的透光能力：不透明、半透明、透明。
（j) 军衔。
（k) 到校园中心的距离。105
（l) 用每立方厘米克表示的物质密度。
（m) 外套寄存号码。（出席一个活动时，你通常会将外套交给服务生，然后他给你一个号码，你可以在离开时用它来领取你的外套。）
3.某个地方公司的销售主管与你联系，他相信他已经设计出了一种评估顾客满意度的完美方法。他这样解释他的方案：“这太简单了，我简直不敢相信，以前竟然没有人想到，我只是记录顾客对每种产品的抱怨次数，我在数据挖掘书中读到计数具有比率属性，因此，我的产品满意度度量必定具有比率属性。但是，当我根据顾客满意度度量评估产品并拿给老板看时，他说我忽略了显而易见的东西，说我的度量毫无价值。我想，他简直是疯了，没发现我们的畅销产品满意度最差，因为对它的抱怨最多。你能帮助我摆平他吗？”
（a) 谁是对的，销售主管还是他的老板？如果你的回答是他的老板，你需要做些什么来修正满意度度量？
（b) 对于原来的产品满意度度量的属性类型，你的想法是什么？
4.几个月之后，习题3中提到的那个销售主管又同你联系。这次，他设计了一个更好的方法，用以评估顾客喜爱一种产品超过喜爱其他类似产品的程度。他解释说：“在开发一种新产品时，我们通常创建一些变种并评估顾客更喜欢哪一种。我们的标准做法是同时散发所有的产品变种并要求他们根据喜爱程度对产品变种划分等级，然而，我们的评测题目很不明确，当有两个以上产品时尤其如此，这让测试占用了很长的时间。我建议对产品逐对比较，然后使用这些比较来划分等级，这样，如果我们有3个产品变种，我们就让顾客比较变种1和2，然后是2和3，最后是3和1。使用我的方法，评测时间是原来的三分之一，但是进行评测的雇员抱怨说，他们不能从评测结果得到一致的等级评定。昨天，我的老板想要知道最新的产品评估。另外我还得告诉你，老的产品评估方法就是他提出的。你能帮助我吗？”
（a) 销售主管是否陷入困境？他的方法能够根据顾客的喜好产生产品变种的有序等级吗？解释你的观点。106
（b) 是否有办法修正销售主管的方法？对于基于逐对比较创建序数度量，你做何评价？
（c) 对于原来的产品评估方案，每个产品变种的总等级通过计算所有评测题目上的平均值得到，你是否认为这是一种合理的方法？你会采取哪种方法？
5.标识号对于预测是有用的，你能想象出一种情况吗？
6.一位教育心理学家想使用关联分析来分析测试结果。测试包含100个问题，每个问题有4个可能的答案。
（a) 如何将该数据转换成适合关联分析的形式？
（b) 能得到何种属性类型以及有多少个属性？
7.下面哪种量更可能具有时间自相关性：日降水量和日气温？为什么？
8.讨论：为什么文档词矩阵是具有非对称的离散特征或非对称的连续特征的数据集？
9.许多科学领域依赖于观测而不是（或不仅是）设计的实验，比较涉及观测科学与实验科学和数据挖掘的数据质量问题。
10.讨论测量精度与术语单精度和双精度之间的差别。在计算机科学，单精度和双精度通常分别表示32位和64位浮点数。
11.对于处理存放在文本文件而不是二进制格式中的数据，给出至少两个优点。
12.区别噪声和离群点。确保考虑以下问题：
（a) 噪声曾令人感兴趣或使人期望吗？离群点呢？
（b) 噪声对象可能是离群点吗？
（c) 噪声对象总是离群点吗？
（d) 离群点总是噪声对象吗？
（e) 噪声能将典型值变成例外值吗？反之呢？107
13.考虑发现数据对象的K个最近邻问题。某个程序员为该任务设计了算法2.3。
（a) 如果数据集中存在重复对象，讨论该算法可能存在的问题。假定对于相同的对象，距离函数只返回距离0。
（b) 如何解决该问题？

14.对亚洲象群的成员测量如下属性：重量、高度、象牙长度、象鼻长度和耳朵面积。基于这些测量，可以使用2.4节的哪种相似性度量来对这些大象进行比较或分组？论证你的答案并说明特殊情况。
15.给定m个对象的集合，这些对象划分成K组，其中第i组的大小为mi。如果目标是得到容量为n（a) 从每组随机地选择n×mi/m个元素。
（b) 从数据集中随机地选择n个元素，而不管对象属于哪个组。
16.考虑一个文档词矩阵，其中tfij是第i个词（术语）出现在第j个文档中的频率，而m是文档数。考虑由下式定义的变量变换：

其中，dfi是出现第i个词的文档数，称作词的文档频率（document frequency)。该变换称作逆文档频率（inverse document frequency)变换。
（a) 如果词出现在一个文档中，该变换的结果是什么？如果术语出现在每个文档中呢？
（b) 该变换的目的可能是什么？
17.假定我们对比率属性x使用平方根变换，得到一个新属性x'。作为分析的一部分，你识别出区间（a，b)，在该区间内，x'与另一个属性y具有线性关系。
（a) 换算成x，（a，b)的对应区间是什么？
（b) 给出y关联x的方程。
18.本习题比较和对比某些相似性和距离度量。
（a) 对于二元数据，L1距离对应于汉明距离，即两个二元向量不同的位数。Jaccard相似度是两个二元向量之间相似性的度量。计算如下两个二元向量之间的汉明距离和Jaccard相似度。
x=0101010001
y=0100011000
（b) Jaccard相似度与汉明距离哪种方法更类似于简单匹配系数，哪种方法更类似于余弦度量？解释你的结论。（注意：汉明度量是距离，而其他三种度量是相似性，但是不要被这一点所迷惑。）
（c) 假定你正在根据共同包含的基因的个数比较两个不同物种的有机体的相似性。你认为哪种度量更适合用来比较构成两个有机体的遗传基因，是汉明距离还是Jaccard相似度？解释你的结论。（假定每种动物用一个二元向量表示，其中如果一个基因出现在有机体中，则对应的属性取值1,否则取值0。)
（d) 如果你想比较构成相同物种的两个有机体的遗传基因（例如，两个人），你会使用汉明距离、Jaccard系数，还是一种不同的相似性或距离度量？解释原因。（注意，两个人的相同基因超过99.9%。）
19.对于下面的向量x和y，计算指定的相似性或距离度量。
（a) x=（1，1，1，1)，y=（2，2，2，2)，计算余弦、相关性、欧几里得。
（b) x=（0，1，0，1)，y=（1，0，1，0)，计算余弦、相关性、欧几里得、Jaccard。
（c) x=（0，-1，0，1)，y=（1，0，1，0)，计算余弦、相关性、欧几里得。
（d) x=（1，1，0，1，0，1)，y=（1，1，1，0，0，1)，计算余弦、相关性、Jaccard。
（e) x=（2，-1，0，2，0，-3)，y=（-1，1，-1，0，0，-1)，计算余弦、相关性。
20.这里，进一步考察余弦度量和相关性度量。
（a) 对于余弦度量，可能的值域是什么？
（b) 如果两个对象的余弦度量为1，它们相等吗？解释原因。
（c) 如果余弦度量与相关性度量有关系的话，有何关系？（提示：在余弦和相关性相同或不同情况下，考虑诸如均值、标准差等统计量。）
（d) 图2.22a显示100000个随机生成的点的余弦度量与欧几里得距离之间的关系，这些点已经规范化，L2的长度为1。当向量的L2长度为1时，关于欧几里得距离与余弦相似性之间的关系，你能得出什么样的一般观测结论？

（e) 图2.22b显示100000个随机生成的点的相关性度量与欧几里得距离之间的关系，这些点已经标准化，具有均值0和标准差1。当向量已经标准化，具有均值0和标准差1时，关于欧几里得距离与相关性之间的关系，你能得出什么样的一般观测结论？
（f) 当每个数据对象的L2长度为1时，推导余弦相似度与欧几里得距离之间的数学关系。
（g) 当每个数据点通过减去均值并除以其标准差标准化时，推导相似度与欧几里得距离之间的数学关系。
21.证明下列给出的集合差度量满足2.4.3节的度量公理:

其中，A和B是集合，A-B是集合差。
22.讨论如何将相关值从区间［-1，1］映射到区间［0，1］。注意，你所使用的变换类型可能取决于你的应用。因此，考虑两种应用：对时间序列聚类，给定一个时间序列预测另一个的性质。
23.给定一个在区间［0，1］取值的相似性度量，描述两种将该相似度变换成区间［0，∞］中的相异度的方法。
24.通常，邻近度定义在一对对象之间。
（a) 阐述两种定义一组对象之间邻近度的方法。
（b) 如何定义欧几里得空间中两个点集之间的距离？
（c) 如何定义两个数据对象集之间的邻近度？（除邻近度定义在任意一对对象之间之外，对数据对象不做任何假定。）
25.给定欧几里得空间中一个点集S，以及S中每个点到点x的距离。（x是否属于S并不重要。）
（a) 如果目标是发现点y（y≠x)指定距离ε内的所有点，解释如何利用三角不等式和已经计算得到的到x的距离，来减少必需的距离计算数量。提示：三角不等式d（x，z)≤d（x，y)+d（y，x)可以写成d（x，y)≥d（x，z)-d（y，z)。
（b) x和y之间的距离对距离计算的数量有何影响？
（c) 假定你可以从原来的数据点的集合中发现一个较小的子集S′，使得数据集中的每个点至少到S′中一个点的距离不超过指定的ε，并且你还得到了S′中每对点之间的距离矩阵。描述一种技术——使用这些信息，以最少的距离计算量，从数据集中计算到一个指定点距离不超过β的所有点的集合。
26.证明1-Jaccard相似度是两个数据对象x和y之间的一种距离度量，该度量满足2.4.3节的度量公理。具体地，d（x，y)=1-J（x，y)。
27.证明定义为两个数据向量x和y之间夹角的距离度量满足2.4.3节的度量公理。具体地，d（x，y)=arccos（cos（x，y))。
28.解释为什么计算两个属性之间的邻近度通常比计算两个对象之间的相似度简单。