数据挖掘和机器学习

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

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

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

 

 

 

 

 

数据和数据集

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

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

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

　　属性可以分为四种类型:标称、序数、区间和比率，其中，标称属性的值仅仅是不同的名称，即，标称值提供区分对象的足够信息，如性别、衣服颜色、天气等；序数属性的值可以提供给确定对象的顺序的足够信息，如成绩等级、职称、学生等；区间属性的值之间的差是有意义的，即存在测量单位，如温度、日历日期等；比率属性的值之间的差和比值都是有意义的，如绝对温度、年龄、长度、成绩分数等。

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

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

 

 

 

 

ARFF格式

　　ARFF是一种Weka专用的文件格式，即Attribute-Relation File Format(属性-关系文件格式）。该文件是ASCII文本文件，描述共享一组属性结构的实例列表，由独立且无序的实例组成，是Weka表示数据集的标准方法，ARFF不涉及实例之间的关系。

　　在Weka安装目录下的data子目录中，可以找到名称为weather.numeric.arff的天气数据文件。如下图所示。

 

 

 　　数据集是实例的集合，每个实例包含一定的属性。

　　 属性的数据类型包括如下几类：

　　 标称型(nominal)只能取预定义值列表中的一个；

　　 数字型(numeric)，只能是实数或整数；　　

　　 字符串(string)，这是一个由双引号引用的任意长度的字符列表；

　　  另外还有日期型(date)和关系型(relational)。

　　  ARFF文件就是实例类型的外部表示，其中包括一个标题头(header)，以描述属性的类型，还包含一个用逗号分隔的列表所表示的数据部分(data)。

 

 

 

 

 

 

weather.nominal.arff

 

@relation weather@attribute outlook {sunny, overcast, rainy}@attribute temperature numeric@attribute humidity numeric@attribute windy {TRUE, FALSE}@attribute play {yes, no}@datasunny,85,85,FALSE,nosunny,80,90,TRUE,noovercast,83,86,FALSE,yesrainy,70,96,FALSE,yesrainy,68,80,FALSE,yesrainy,65,70,TRUE,noovercast,64,65,TRUE,yessunny,72,95,FALSE,nosunny,69,70,FALSE,yesrainy,75,80,FALSE,yessunny,75,70,TRUE,yesovercast,72,90,TRUE,yesovercast,81,75,FALSE,yesrainy,71,91,TRUE,no

 

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

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

@attribute outlook{sunny,overcast,rainy}行定义名称为outlook的标称属性，有三个取值：sunny、overcast和rainy。

@attribute temperature numeric行定义

@attribute humidity numeric

@attribute temperature real定义名称为temperature的数值型属性，

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

@attribute windy{TRUE,FALSE}行定义为windy两个标称属性。为TRUE和FALSE。

@attribute play{yes,no}行定义为play两个标称属性。为yes和no。要注意这个属性缺省为用于预测的类别变量。

本例中，类别变量为标称型属性play，它只能取两个值之一，使得天气问题成为二元的分类问题。

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

 

 

 

 

 

 

预处理

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

　　由于无法在数据的源头控制质量，数据挖掘只能通过以下两个方面设法避免数据质量问题：

• 数据质量问题的检测与纠正

• 使用能容忍质量数据的算法。

　　第一种方式在数据挖掘前检测并纠正一些质量问题，这个过程称为数据预处理；第二种方式需要提高算法的健壮性。

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

　　1）聚集

　　聚集(Aggregation)就是将两个或者多个对象合并为单个对象。一般来说，定量数据通常通过求和或平均值的方式进行聚集，定性数据通常通过汇总进行聚集。聚集通过数据规约来减少数据量，所导致的较小数据集只需要较少内存和处理时间的开销，因此，可以使用开销更大的数据挖掘算法。另外，聚集使用高层数据视图，起到了范围或度量转换的作用。

　　2）抽样

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

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

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

　　3）维度归约

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

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

　　4）属性选择

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

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

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

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

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

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

　　5）属性创建

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

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

　　映射数据到新空间，是指使用一种完全不同的视角挖掘数据可能揭示重要而有趣的特征，诸如与人脸高度相关的边和区域等，就可以使用更多的分类技术。

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

　　6）离散化和二元化

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

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

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

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

　　7）变量变换

　　变量变换也称为属性变换，用于变量的所有值的变换。

　　简单函数变换是使用一个简单数学函数分别作用于每一个值。在统计雪中，使用平方根、对数变换和倒数变换等变量变换常用语将不具有高斯分布的数据变换为具有高斯分布的数据。变量的标准化是使整个值的集合具有特定的性质。由于均值和标准差受离群点的影响较大，因此，常常修正上述变换。例如，用中位数替代均值，用绝对标准差替代标准差，等等。

 

 

 

 

 

 

分类与回归

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

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

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

　　1) 决策树分类

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

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

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

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

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

　　2) 贝叶斯分类

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

　　3) k-最近邻分类

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

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

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

　　4) 神经网络分类

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

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

 

　　分类模型学习方法如神经网络分类，值采用某种学习方法从训练样本中学习，将获取的知识存储在网络模型的权值中，模拟人类大脑通过一个脉冲反复刺激下改变神经元之间的神经键连接强度来进行学习。

　　按照各神经元的不同连接方式，神经网络分为前向网络和反馈网络。目前的神经网络模型非常丰富，典型的模型有感知器模型、多层前向传播模型、BP模型、Hopfield网络、SOM自组织网络等。Weka神经网络使用多层感知器实现了BP神经网络。

 

 

 

 

聚类分析

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

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

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

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

　　聚类分析方法主要有：划分的方法、层次的方法、基于密度的方法、基于网格的方法、基于模型的方法等。Weka实现的聚类算法主要有：K均值算法、EM算法和DBSCAN。

 

 

 

 

关联分析

　　典型有啤酒与尿布。这里不多赘述。

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

　　Weka实现了Apriori算法和另一个关联分析的FP-Growth算法。