1.2 基本概念

上节简要介绍了Weka，读者也许迫不及待地想进一步深入了解并使用Weka来完成数据挖掘工作。但是，在此之前，有必要先了解数据挖掘和机器学习的一些基本概念，为进一步的学习打下基础。

1.2.1 数据挖掘和机器学习

数据挖掘和机器学习这两项技术的关系非常密切。机器学习方法构成数据挖掘的核心，绝大多数数据挖掘技术都来自机器学习领域，数据挖掘又向机器学习提出新的要求和任务。

数据挖掘就是在数据中寻找模式的过程。这个寻找过程必须是自动的或半自动的，并且数据总量应该具有相当大的规模，从中发现的模式必须有意义并能产生一定的效益。通常，数据挖掘需要分析数据库中的数据来解决问题，如客户忠诚度分析、市场购物篮分析等。

当今已进入海量数据时代。例如，全世界已经有约一万亿个网页；沃尔玛仅一个小时就有一百万的交易量，其数据库里的数据已有2.5拍（即2.5×1015字节）的信息，等等。

这些海量数据不可能采用手工方式进行处理，因此，迫切要求能进行数据分析的自动化方法，这些都由机器学习提供。

机器学习定义为能够自动寻找数据中的模式的一套方法，然后，使用所发现的模式来预测将来的数据，或者在各种不确定的条件下进行决策。

机器学习分为两种主要类型。第一种机器学习类型称为有监督学习，或称为预测学习，其目标是在给定一系列输入/输出实例所构成的数据集的条件下，学习输入x到输出y的映射关系。这里的数据集称为训练集，实例的个数称为训练样本数。第二种机器学习类型称为无监督学习，或称为描述学习，其目标是在给定一系列仅由输入实例构成的数据集的条件下，发现数据中的有趣模式。无监督学习有时候也称为知识发现，这类问题并没有明确定义，因为我们不知道需要寻找什么样的模式，也没有明显的误差度量可供使用。而对于给定的x，有监督学习可以对所观察到的值与预测的值进行比较，得到明确的误差值。

1.2.2 数据和数据集

根据应用的不同，数据挖掘的对象可以是各种各样的数据，这些数据可以以各种形式进行存储，如数据库、数据仓库、数据文件、流数据、多媒体、网页等。既可以集中存储在数据存储库中，也可以分布在世界各地的网络服务器上。

通常将数据集视为待处理的数据对象的集合。由于历史原因，数据对象有多个别名，如记录、点、行、向量、案例、样本、观测等。数据对象也是对象，因此，可以用刻画对象基本特征的属性来进行描述。属性也有多个别名，如变量、特征、字段、维、列等。

数据集可以类似于一个二维的电子表格或数据库表。在最简单的情形下，每个训练输入xi是一个N维的数值向量，表示特定事物的一些特征，如人的身高、体重。这些特征也可以称为属性。有时xi也可以是复杂结构的对象，如图像、电子邮件、时间序列、语句等。

属性可以分为四种类型：标称（nominal）、序数（ordinal）、区间（interval）和比率（ratio），其中，标称属性的值仅仅是不同的名称，即标称值仅提供区分对象的足够信息，如性别（男、女）、衣服颜色（红、黄、蓝）、天气（阴、晴、雨、多云）等；序数属性的值可以提供确定对象的顺序的足够信息，如成绩等级（优、良、中、及格、不及格）、职称（初级、中级、高级）、学生（本科生、硕士生、博士生）等；区间属性的值之间的差是有意义的，即存在测量单位，如温度、日历日期等；比率属性的值之间的差和比值都是有意义的，如绝对温度、年龄、长度、成绩分数等。

标称属性和序数属性统称为分类的（categorical）或定性的（qualitative）属性，它们的取值为集合，即使使用数值来表示，也不具备数的大部分性质，因此，应该像对待符号一样对待；区间属性和比率属性统称为定量的（quantitative）或数值的（numeric）属性，定量属性采用数值来表示，具备数的大部分性质，可以使用整数值或连续实数值来表示。

大部分数据集都以数据库表和数据文件的形式存在，Weka支持读取数据库表和多种格式的数据文件，其中，使用最多的是一种称为ARFF格式的文件。

1.2.3 ARFF格式

ARFF是一种Weka专用的文件格式，由Andrew Donkin创立，有传言说ARFF代表Andrew's Ridiculous File Format（安德鲁的荒唐文件格式），但在Weka的正式文档中明确说明ARFF代表Attribute-Relation File Format（属性—关系文件格式）。该文件是ASCII文本文件，描述共享一组属性结构的实例列表，由独立且无序的实例组成，是Weka表示数据集的标准方法，ARFF不涉及实例之间的关系。

在Weka安装目录下的data子目录中，可以找到名称为weather.numeric.arff的天气数据文件，其内容如程序清单1.1所示。数据集是实例的集合，每个实例包含一定的属性，属性的数据类型包括如下几类：标称型（nominal），只能取预定义值列表中的一个；数值型（numeric），只能是实数或整数；字符串型（string），这是一个由双引号引用的任意长度的字符列表；另外还有日期型（date）和关系型（relational）。ARFF文件就是实例类型的外部表示，其中包括一个标题头（header），以描述属性的类型，还包含一个用逗号分隔的列表所表示的数据部分（data）。

程序清单1.1 天气数据的ARFF文件

    % This is a toy example, the UCI weather dataset.
    % Any relation to real weather is purely coincidental.

    @relation weather

    @attribute outlook {sunny, overcast, rainy}
    @attribute temperature real
    @attribute humidity real
    @attribute windy {TRUE, FALSE}
    @attribute play {yes, no}
    @data
    sunny,85,85, FALSE, no
    sunny,80,90, TRUE, no
    overcast,83,86, FALSE, yes
    rainy,70,96, FALSE, yes
    rainy,68,80, FALSE, yes
    rainy,65,70, TRUE, no
    overcast,64,65, TRUE, yes
    sunny,72,95, FALSE, no
    sunny,69,70, FALSE, yes
    rainy,75,80, FALSE, yes
    sunny,75,70, TRUE, yes
    overcast,72,90, TRUE, yes
    overcast,81,75, FALSE, yes
    rainy,71,91, TRUE, no

上述代码中，以百分号“%”开始的行称为注释行。与计算机编程语言类似，最前面的注释行应该写明数据集的来源、用途和含义。

@relation行定义内部数据集的名称weather，名称应简洁明了，尽可能容易理解。relation也称为关系。

@attribute outlook {sunny，overcast，rainy}行定义名称为outlook的标称型属性，有三个取值：sunny、overcast和rainy。按照同样的方式，@attribute windy {TRUE，FALSE}行和@attribute play {yes，no}行分别定义windy和play两个标称型属性。要注意的是，最后一个属性默认为用于预测的类别变量，或称为目标属性。本例中，类别变量为标称型属性play，它只能取两个值之一，使得天气问题成为二元（binary）的分类问题。

@attribute temperature real行定义名称为temperature的数值型属性，@attribute humidity real行定义名称为humidity的数值型属性。这两个属性都是实数型。

@data标志后的各行构成数据集。每行为一个实例样本，由采用逗号分隔的值组成，顺序与由@attribute所定义属性的顺序一致。

本例没有使用字符串类型和日期类型，在将来的学习中会遇到这两种类型。

1.2.4 预处理

数据挖掘是在大量的、潜在有用的数据中挖掘出有用模式的过程。因此，源数据的质量直接影响到挖掘的效果，高质量的数据是进行有效挖掘的前提。但是，由于数据挖掘所使用的数据往往不是专门为挖掘准备的，期望数据质量完美并不现实，人的错误、测量设备的限制以及数据收集过程的漏洞都可能导致一些问题，如缺失值（由机械原因或人为原因造成的数据缺失）和离群值（数值与其他数值相比差异较大）。

由于无法在数据的源头控制质量，数据挖掘只能通过以下两个方面设法避免数据质量问题：①数据质量问题的检测与纠正；②使用能容忍低质量数据的算法。第一种方式在数据挖掘前检测并纠正一些质量问题，这个过程称为数据预处理；第二种方式需要提高算法的健壮性。

数据预处理是数据挖掘的重要步骤，数据挖掘者的大部分时间和精力都要花在预处理阶段。Weka专门提供若干过滤器进行预处理，还在探索者界面中提供Select attributes（选择属性）标签页专门处理属性的自动选择问题。数据预处理涉及的策略和技术非常广泛，主要包括如下技术。

1．聚集

聚集（aggregation）就是将两个或多个对象合并为单个对象。一般来说，定量数据通常通过求和或求平均值的方式进行聚集，定性数据通常通过汇总进行聚集。聚集通过数据归约来减少数据量，所导致的较小数据集只需要较少内存和处理时间的开销，因此，可以使用开销更大的数据挖掘算法。另外，聚集使用高层数据视图，起到了范围或度量转换的作用。虽然站在很高的角度去检视问题容易避免“只见树木，不见森林”的弊端，但也可能导致有趣细节的丢失。

2．抽样

如果处理全部数据的开销太大，数据预处理可以使用抽样，只选择数据对象的子集进行分析。使用抽样可以压缩数据量，因此，能够使用效果更好但开销较大的数据挖掘算法。由于抽样是一个统计过程，好的抽样方案就是确保以很高的概率得到有代表性的样本，即样本近似地具有与原数据相同的性质。

抽样方式有多种，最简单的抽样是选取每一个数据行作为样本的概率都相同，这称为简单随机抽样，又分为有放回抽样和无放回抽样两种形式，前者是从N个数据行中以概率1/N分别随机抽取出n个数据行，构成样本子集；后者与有放回抽样的过程相似，但每次都要删除原数据集中已经抽取出来的数据行。显然，有放回抽样得到的样本子集有可能重复抽取到相同的数据行。

当整个数据集由差异较大的数据行构成时，简单随机抽样可能无法抽取到不太频繁出现的数据行，这会导致得到的样本不具代表性。分层抽样（stratified sampling）尽量利用事先掌握的信息，充分考虑保持样本结构和总体结构的一致性以提高样本的代表性。其步骤是，先将数据集按某种特征分为若干不相交的“层”，然后再从每一层中进行简单随机抽样，从而得到具有代表性的抽样数据子集。

3．维度归约

维度是指数据集中属性的数目。维度归约（dimension reduction）是指创建新属性，通过数据编码或数据变换，将一些旧属性合并在一起以降低数据集的维度。

维度归约可以删除不相关的属性并降低噪声，维度降低会使许多数据挖掘的算法变得更好，还能消除由维灾难带来的负面影响。维灾难是指，随着维度的增加，数据在它所占的空间越来越稀疏，对于分类问题，这意味着可能没有足够的数据对象来创建模型；对于聚类问题，点之间的密度和距离的定义失去意义。因此，对于高维数据，许多分类和聚类等学习算法的效果都不理想。维度归约使模型的属性更少，因而可以产生更容易理解的模型。

4．属性选择

除维度归约外，降低维度的另一种方法是只使用属性的一个子集。表面看来这种方法似乎可能丢失信息，但在很多情况下，数据集中存在冗余或不相关的属性。其中，冗余属性是指某个属性包含了其他属性中的部分或全部信息，不相关属性是指对于手头的数据挖掘任务几乎完全没有用处的信息。属性选择是指从数据集中选择最具代表性的属性子集，删除冗余或不相关的属性，从而提高数据处理的效率，使模型更容易理解。

最简单的属性选择方法是使用常识或领域知识，以消除一些不相关或冗余属性。但是，选择最佳的属性子集通常需要系统的方法。理想的属性选择方法是：将全部可能的属性子集作为数据挖掘学习算法的输入，然后选取能产生最好结果的子集。这种方法反映了对最终使用的数据挖掘算法的目的和偏爱。但是，由于n个属性的子集的数量多达2n个，大部分情况下行不通。因此，需要考虑三种标准的属性选择方法：嵌入、过滤和包装。

嵌入方法（embedded approach）将属性选择作为数据挖掘算法的一部分。在挖掘算法运行期间，算法本身决定使用哪些属性以及忽略哪些属性。决策树算法通常使用这种方法。

过滤方法（filter approach）在运行数据挖掘算法之前，使用独立于数据挖掘任务的方法进行属性选择，即先过滤数据集产生一个属性子集。

包装方法（wrapper approach）将学习算法的结果作为评价准则的一部分，使用类似于前文介绍的理想算法，但通常无法枚举出全部可能的子集以找出最佳属性子集。

根据属性选择过程是否需要使用类别信息，属性选择可分为有监督属性选择和无监督属性选择。前者通过度量类别信息与属性之间的相互关系来确定属性子集；后者不使用类别信息，使用聚类方法评估属性的贡献度，根据贡献度来确定属性子集。

5．属性创建

属性创建就是通过对数据集中旧的属性进行处理，创建新的数据集，这样能更有效地获取重要的信息。由于通常新数据集的维度比原数据集少，因此，可以获得维度归约带来的好处。属性创建有三种方法：属性提取、映射数据到新空间和属性构造。

属性提取是指由原始数据创建新的属性集。例如，对照片数据进行处理，提取一些较高层次的特征，诸如与人脸高度相关的边和区域等，就可以使用更多的分类技术。

映射数据到新空间是指使用一种完全不同的视角挖掘数据，这可能会揭示出重要而有趣的特征。例如，对时间序列实施傅里叶变换，将其转换为频率信息，可能会检测到其中的周期模式。

当原始数据集的属性含有必要信息，但其形式不适合数据挖掘算法的时候，可以使用属性构造，通过一个或多个原来的属性构造出新的属性。

6．离散化和二元化

有的数据挖掘算法，尤其是某些分类算法，要求数据是分类属性的形式；发现关联模式的算法要求数据是二元属性的形式。因此，需要进行属性变换。将连续属性转换为分类属性称为离散化（discretization），将连续和离散属性转换为一个或多个二元属性称为二元化（binarization）。

连续属性离散化为分类属性可分为两个子任务：决定需要多少个分类值，以及决定如何将连续属性值映射到这些分类值中。因此，离散化问题就是要决定选择多少个分割点，以及确定分割点的位置，利用少数分类值标签替换连续属性的值，从而减少和简化原来的数据。

根据是否使用类别信息，可以将离散化技术分为两类：使用类别信息的称为有监督的离散化，反之则称为无监督的离散化。

等宽和等频离散化是两种常用的无监督的离散化方法。等宽（equal width）离散化将属性的值域划分为相同宽度的区间，区间的数目由用户指定。这种方式常常会造成实例分布不均匀。等频（equal frequency）离散化也称为等深（equal depth）离散化，它试图将相同数量的对象放进每个区间，区间的数目由用户指定。

7．变量变换

变量变换（variable transformation）也称为属性变换，是指用于变量的所有值的变换。下面讨论两种重要的变量变换：简单函数变换和标准化。

简单函数变换是使用一个简单数学函数分别作用于每一个值。在统计学中，平方根、对数变换和倒数变换等变量变换常用于将不具有高斯分布的数据变换为具有高斯分布的数据。

变量标准化（standardization）的目的是使整个值的集合具有特定的性质。例如，假设是某个属性的均值，sx是其标准差，则变换公式创建一个具有均值0和标准差1的新的变量。由于均值和标准差受离群点的影响较大，因此，常常修正上述变换。例如，用中位数（median）替代均值，用绝对标准差替代标准差等。

1.2.5 分类与回归

分类（classification）与回归（regression）是数据挖掘应用领域的重要技术。分类就是在已有数据的基础上学习出一个分类函数或构造出一个分类模型，这就是通常所说的分类器（classifier）。该函数或模型能够把数据集中的数据映射到某个给定的类别，从而用于数据预测。分类和回归是预测的两种形式，分类预测的输出目标是离散值，而回归预测的输出目标是连续值。因此，在Weka中，分类和回归都归为同一类的问题，都是要构建能对目标进行预测的分类器。

在分类之前，先要将数据集划分为训练集和测试集两个部分。分类分两步：第一步，分析训练集的特点并构建分类模型，常用的分类模型有决策树、贝叶斯分类器、k-最近邻分类等；第二步，使用构建好的分类模型对测试集进行分类，评估分类模型的分类准确度等指标，选择满意的分类模型。

分类模型学习方法主要分为以下几类。

1．决策树分类

决策树分类方法对训练集进行训练，生成一棵二叉或多叉的决策树。决策树包含三种节点，根节点没有入边，但有零条或多条出边；内部节点只有一条入边和两条或多条出边；叶节点只有一条入边，但没有出边。树的叶节点代表某一个类别值，非叶节点代表某个一般属性（非类别属性）的一个测试，测试的输出构成该非叶节点的多个分支。从根节点到叶节点的一条路径形成一条分类规则，一棵决策树能够方便地转化为若干分类规则，挖掘者可以根据分类规则直观地对未知类别的样本进行预测。具体方法是，从树的根节点开始，将测试条件用于检验样本，根据测试结果选择适当的分支，沿着该分支要么到达另一个内部节点，再次使用新的测试规则；要么到达叶节点，结果是将叶节点的类别标号赋值给检验样本。

决策树归纳的学习算法必须解决以下两个问题。

第一，如何分裂训练样本集？树在增长过程中的每个递归步必须选择一个属性作为测试条件，将样本集划分为更小的子集。为了实现该步，算法必须提供为不同类型的属性指定测试条件的方法，并且提供评估每种测试条件的客观度量。

第二，如何停止分裂过程？需要有终止决策树生长过程的结束条件。可能的策略是一直分裂，直到所有的样本都属于同一个类别，或者所有样本的属性值都相同。也可以使用其他策略提前终止树的生长过程。

不同决策树采用的技术不同，目前已经有很多成熟而有效的决策树学习算法，如ID3、C4.5、CART、Random Forest等。具体算法详见后文。

2．贝叶斯分类

贝叶斯分类方法有一个明确的基本概率模型，用以给出某个样本属于某个类别标签的概率。贝叶斯分类方法有两种主要实现：朴素贝叶斯分类器和贝叶斯网络。朴素贝叶斯分类器是基于贝叶斯定理的统计分类方法，它假定属性之间相互独立，但实际数据集中很难保证这一条件。朴素贝叶斯分类器分类速度快且分类准确度高，支持增量学习。贝叶斯网络使用一种称为贝叶斯网络的概率网络来描述属性之间的依赖关系，Weka对贝叶斯网络有很好的支持，详见后文。

3．k-最近邻分类

前面所介绍的决策树分类器是一种积极学习器（eager learner），因为只要训练数据可用，它就开始学习从输入属性到类别标签的映射模型。另一种策略则是推迟对训练模型的建模，直到需要分类测试样本时再进行，对应的分类器称为消极学习器（lazy learner）。k-最近邻分类算法使用的就是后一种策略，它是一种基于实例的学习算法，不需要事先使用训练样本构建分类器，而是直接使用训练集对测试样本进行分类，以确定类别标签。

k-最近邻分类使用具体的训练实例进行预测，不必维护从数据集中抽象出来的模型。这种基于实例的学习算法需要邻近性度量来确定实例间的相似度或距离，还需要分类函数根据测试实例与其他实例的邻近性返回测试实例的预测类别标签。虽然消极学习方法不需要建立模型，但对测试实例进行分类的开销很大，因为需要逐个计算测试样本和训练样本之间的相似度。相反，积极学习方法通常花费大量的计算资源来建立模型，但一旦建立模型之后，对测试实例进行分类就会非常快。k-最近邻分类器基于局部信息进行预测，而决策树分类器则试图找到一个适合整个输入空间的全局模型。由于基于局部分类策略，k-最近邻分类器在k很小的时候对噪声非常敏感。

Weka实现的k-最近邻分类算法称为IBk，可以通过交叉验证选择适当的k值，还可以实现距离加权。

4．神经网络分类

神经网络（neural network）是大量的简单神经元按一定规则连接构成的网络系统，能够模拟人类大脑的结构和功能。它采用某种学习算法从训练样本中学习，将获取的知识存储在网络模型的权值中，通过模拟人类大脑在同一个脉冲的反复刺激下改变神经元之间的神经键连接强度来进行学习。

按照各神经元的不同连接方式，神经网络分为前向网络和反馈网络。目前的神经网络模型非常丰富，典型的模型有感知器模型、多层前向传播模型、BP（反向传播）模型、Hopfield模型、SOM（Self-Organizing Map，自组织映射）模型等。

Weka神经网络使用多层感知器实现了BP神经网络，详见第6章。

1.2.6 聚类分析

聚类（clustering）就是将数据集划分为由若干相似实例组成的簇（cluster）的过程，使得同一个簇中实例间的相似度最大化，不同簇中实例间的相似度最小化。也就是说，一个簇就是由彼此相似的一组对象所构成的集合，不同簇中的实例通常不相似或相似度很低。

聚类分析是数据挖掘和机器学习中十分重要的技术，应用领域极为广泛，如统计学、模式识别、生物学、空间数据库技术、电子商务等。

作为一种重要的数据挖掘技术，聚类是一种无监督的机器学习方法，主要依据样本间相似性的度量标准将数据集自动划分为几个簇，聚类中的簇不是预先定义的，而是根据实际数据的特征按照数据之间的相似性来定义的。聚类分析算法的输入是一组样本以及一个度量样本间相似度的标准，输出是簇的集合。聚类分析的另一个副产品是对每个簇的综合描述，这个结果对于进一步深入分析数据集的特性尤为重要。聚类方法适合用于讨论样本间的相互关联，从而能初步评价其样本结构。

数据挖掘关心聚类算法的如下特性：处理不同类型属性的能力、对大型数据集的可扩展性、处理高维数据的能力、发现任意形状簇的能力、处理孤立点或“噪声”数据的能力、对数据顺序的不敏感性、对先验知识和用户自定义参数的依赖性、聚类结果的可解释性和实用性、基于约束的聚类等。

聚类分析方法主要有划分的方法、层次的方法、基于密度的方法、基于网格的方法、基于模型的方法等。Weka实现的聚类算法主要有k均值算法、EM（期望最大化）算法和DBSCAN算法。

1.2.7 关联分析

商业企业在日复一日的运营中积累了大量的数据。例如，超市的收银台每天都要记录大量的顾客购物数据，这种数据通常称为购物篮事务。商家对分析这些数据很感兴趣，因为分析它可以了解顾客的购买行为。关联分析（association analysis）方法就用于发现隐藏在大型数据集中有意义的联系，这种联系可以用关联规则（association rule）进行表示。例如，商家通过关联分析挖掘商场销售数据，发现顾客的购买习惯，如购买产品X的同时也购买产品Y，于是，超市就可以调整货架的布局，将X产品和Y产品放在一起，以提升销量。因此，关联分析为商场进行商品促销以及货架摆放提供了辅助决策信息。

例如，沃尔玛从销售数据中发现这样一个令人匪夷所思的规则：{尿布}→{啤酒}。该规则表明尿布和啤酒的销售之间存在着很强的联系。原来，美国妇女通常在家照顾孩子，所以她们会经常嘱咐丈夫在下班回家的路上为孩子买尿布，而丈夫在买尿布的同时又会顺手购买自己爱喝的啤酒。得益于所发现的新的交叉销售商机，沃尔玛将啤酒和尿布这两个看上去毫无关联的商品摆放在一起销售，获得了很好的销售收益。

除购物篮数据外，关联分析还可以应用于其他领域，如生物信息学、医疗诊断、网页挖掘和科学数据分析等。例如，通过关联分析挖掘医疗诊断数据，可以发现症状与疾病之间的关联，为医生诊断疾病和治疗提供线索。

关联分析最著名的算法是Apriori算法，其核心是基于两阶段频繁项集思想的递推算法。寻找最大项集（频繁项集）的基本思想是：算法需要对数据集进行多步处理。第一步，简单统计所有含一个元素项集出现的频数，并找出那些不小于最小支持度的项集，即一维最大项集。从第二步开始进行循环处理，直到再没有最大项集生成。循环过程是：在第k步中，根据第k-1步生成的（k-1）维最大项集产生k维候选项集，然后对数据库进行搜索，得到候选项集的支持度，与最小支持度进行比较，从而找到k维最大项集。

Weka实现了Apriori算法和另一个关联分析的FP-Growth（频繁模式增长）算法。